*Multiple Choice Questions on Data Structure*

*Q1. Given a binary search tree, which traversal type would print the values in the nodes in*

*sorted order?*

*A. Post-order*

*B. Pre-order*

*C. In-order**D. None of the above*

*Q2. What is the running time of the following code fragment?*

*for(int i=0; i<10; i++)*

*for(int j=0; j<N; j++)*

*for(int k=N-2; k<N+2; k++)*

*cout << i << " " << j << endl;*

*A. O(N log N)*

*B. O( log N)*

*C. O(N)**D. O(N*2)*

*Q3. Suppose we’re debugging a quicksort implementation that is supposed to sort an array in*

*ascending order. After the first partition step has been completed, the contents of the array*

*are in the following order:*

*3 9 1 14 17 24 22 20*

*Which of the following statements is correct about the partition step?*

*A. The pivot could have been either 14 or 17**B. The pivot could have been 14, but could not have been 17*

*C. The pivot could have been 17, but could not have been 14*

*D. Neither 14 nor 17 could have been the pivot*

*Q4. Which of the following statements about binary trees is NOT true?*

*A. Every binary tree has at least one node.**B. Every non-empty tree has exactly one root node.*

*C. Every node has at most two children.*

*D. Every non-root node has exactly one parent.*

*Q5. How many times is the symbol ’$’ printed by the call dolar(4)?*

*void dolar (int i)*

*{*

*if (i > 1)*

*{*

*dolar (i/2);*

*dolar (i/2);*

*}*

*cout << "$";*

*}*

*A. 4*

*B. 6*

*C. 7**D. 2*

*Q6. A class template in C++ has the following structure*

*template <class T> class TemplatedClass*

*{*

*…*

*};*

*What is the meaning of T in the above declaration?*

*A. It is a placeholder for a pointer value*

*B. It is a placeholder for a type name**C. It must be an integer constant*

*D. It must be a function name*

*Q7. Are there any dynamic memory management errors in the following code?*

*int *p = new int;*

*int *q = new int;*

*int *r;*

**p = 17;*

*r = q;*

**q = 42;*

*p = q;*

*delete r;*

*A. No, there are no errors*

*B. Yes, a memory leak**C. Yes, misuse of a dangling pointer*

*D. Yes, a dangling chad*

*Q8. Is this a binary search tree?*

*55*

*/ \*

*16 65*

*/ \ / \*

*5 25 45 195*

*/ \ \*

*2 13 59*

*A. Yes*

*B. No**C. Both*

*D. None of the above*

*Q9. What is the expected time required to search for a value in a binary search tree containing n*

*nodes? (You should make reasonable assumptions about the structure of the tree.)*

*A. O(1)*

*B. O(log n)**C. O(n)*

*D. O(n log n)*

*Q10. If we use mergesort to sort an array with n elements, what is the worst case time required*

*for the sort?*

*A. O(1)*

*B. O(log n)*

*C. O(n)*

*D. O(n log n)*

*Q11. There are several factors that affect the efficiency of lookup operations in a hash table.*

*Which of the following is not one of those factors?*

*A. Number of elements stored in the hash table*

*B. Size of elements stored in the hash table**C. Number of buckets in the hash table*

*D. Quality of the hash function*

*Q12. What is the complexity of the following code expressed in O( ) notation? If more than one*

*answer is correct, choose the smallest one.*

*for (int j = n; j > 0; j--)*

*{*

*for (int k = 1; k < j; k = k+k)*

*{*

*cout << j+k << “ ”;*

*}*

*cout << endl;*

*}*

*A. O(log n)*

*B. O(n)*

*C. O(n log n)**D. O(n2)*

*E. O(2n)*

*Q13. What is the infix version of the following postfix expression?*

*x 12 + z 17 y + 42 * / +*

*Hint: Try using a stack to evaluate the postfix expression and see what happens.*

*A. (x + 12 + z) / (17 + y * 42)*

*B. x + 12 + z / 17 + y * 42*

*C. x + 12 + z / (17 + y) * 42*

*D. x + 12 + z / ((17 + y) * 42)*

*Thanks*

*Mukesh Rajput*
## No comments:

## Post a Comment

Thanks

Mukesh Rajput