Saturday, 21 October 2017

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