(1) Which of the following traversals always gives the sorted sequence of the el
ID: 3770587 • Letter: #
Question
(1) Which of the following traversals always gives the sorted sequence of the elements in a BST?
(a) postorder
(b) inorder
(c) preorder
(d) None of the above
(2) When is a function a pure virtual function?
(a) When it is constant throughout the inheritance hierarchy
(b) Its definition changes in the inheritance hierarchy, but there is a reasonable default
(c) No reasonable default can be provided, and it must be defined in the inheritance hierarchy
(d) When a pointer is involved
The next three questions (3) (4) (5) apply to the following code fragment:
1 for( int i = 0; i < n; i++ )
2 for( int j = 0; j <= i; j++ )
3 sum++;
4 for( int p = n; p > 0; p = p/2 )
5 for( int q = 0; q < n; q++ )
6 sum--;
(3) How many times (in big-Oh notation) is statement 3 executed?
(a) O (n)
(b) O (n2 )
(c) O (n log n)
(d) O (log n)
(4) How many times (in big-Oh notation) is statement 6 executed?
(a) O (n)
(b) O (n2 )
(c) O (n log n)
(d) O (log n )
(5) What is the computing time (in big-Oh notation) of this whole code fragment?
(a) O (n)
(b) O (n2 )
(c) O (n log n)
(d) O (n2 log n)
Explanation / Answer
1. Option (b).
Inorder traversals always give the sorted sequence of the elements in a BST. It traverses the left subtree and then visits the root node and then it traverse right subtree of the BST.
2. Option (c).
No reasonable default can be provided, and it must be defined in the inheritance hierarchy then the function is a pure virtual function.
3. Option (b)
The statement (3) sum++; will executes n (n+1)/2 times and big oh notation is O(n2).
for( int i = 0; i < n; i++ )
for( int j = 0; j <= i; j++ )
sum++;
The 1st for loop runs for n times and the 2nd for loop runs for n+1/2 time. Therefore, the statement sum++ runs for n(n+1)/2 times.
The big-Oh notation for this statement is n(n+1)/2 = n2+1/2 = O(n2).
4. Option (c).
The statement (6) sum--; executes for O (nlogn) times.
for( int p = n; p > 0; p = p/2 )
for( int q = 0; q < n; q++ )
sum--;
The 1st for loop runs for log n times and the 2nd for loop runs for n time. Therefore, The statement (6) sum-- runs for O(nlogn) times.
5. Option (b).
The whole code fragment runs for O(n2).
O(n2)+O (nlogn)=O(n2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.