1. Fill in True (T) or False (0) in the blank for each of the following statemen
ID: 3770598 • Letter: 1
Question
1. Fill in True (T) or False (0) in the blank for each of the following statements:
(1) ________Linear insertion sort performs better for partially sorted lists than for random lists.
(2) ________Simple selection sort performs better for partially sorted lists than for random lists.
(3) ________The STL makes abundant use of inheritance and virtual functions.
(4) ________ STL containers are class templates library.
2. What are the three cornerstones of object oriented programming? Explain each of them.
3. Complete the codes, which are left as blanks in the following functions according to our discussions in the classes
(a) Recursive binary search
template
int binarySearch( const vector & v,
const T & x, int low, int high )
{
if( low > high )
return ________________________________;
int mid = ________________________________;
if( v[ mid ] < x )
return ________________________________;
else if( x < v[ mid ] )
return ________________________________;
else
return ________________________________;
}
(b) The following items are inserted into a binary search tree: 3, 9, 7, 2, 5, 11, 1, which node is the deepest? Show the BST you construct.
4. Complete the following table by giving the general average running times in big-O notations for the
indicated operations and data structure, where there are n data items for each. (Consider the operations on random data.)
// Your answers:
//print 1:
//print 2 :
//print 3:
//print 4:
Computing Times Insert (Add) Find (Search) Array Binary Search Tree Linked List StackExplanation / Answer
Multiple Questions: Answering 1:
(1) True.
Insertion sort takes time O(n + the number of inversions).
An inversion is a pair (i, j) such that i < j && a[i] > a[j]. That is, an out-of-order pair.
One measure of being "almost sorted" is the number of inversions---one could take "almost sorted data" to mean data with few inversions. If one knows the number of inversions to be linear (for instance, you have just appended O(1) elements to a sorted list), insertion sort takes O(n) time.
(2)False. The comparison doesnot stop even if the list is sorted . Hence O(n2) comparisons.
(3)False .These were avoided for performance reasons.
(4)True. A container is a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements.
Post multiple questions differently.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.