Paper 2 CS · UNIT 07 · MOCK TEST

Data Structures and Algorithms — Mock Test 1

25 questions · about 30 minutes. Press End Mock any time to see your score and the correct answers.

0 / 25 answered 00:00

Q1. Match List - I with List - II.

List - I	List - II
A. Merge sort	I. n²
B. Binary search	II. nlogn
C. Quick sort	III. n
D. Search in an unsorted array	IV. logn

Choose the correct answer from the options given below:

AA-I, B-IV, C-II, D-III BA-I, B-II, C-III, D-IV CA-II, B-I, C-III, D-IV DA-II, B-IV, C-I, D-III

Q2. Consider the following AVL tree: root = 60; left child of 60 = 50; right child of 60 = 70; right child of 70 = 80 (a balanced AVL tree of height 2).
What is the maximum number of nodes that can be inserted in the following AVL tree without changing its height?

A2 B4 C3 D5

Q3. In the worst case, the smallest number of comparisons required by any sorting algorithm, which does only binary comparisons, is

A⌈log n⌉ B⌈log n!⌉ C⌈log n(n−1)⌉ D2ⁿ

Q4. A problem of size n requires n² bit operations. What is the largest size instance that can be solved in 1 second, if each bit operation is carried out in 10⁻⁹ second?

A10⁹ B3.16×10⁴ C3.96×10⁷ D2^(10⁹)

Q5. If f(n) = θ(g(n)) and g(n) = O(h(n)), then which of the following is true?

Af(n) = O(h(n)) Bf(n) = θ(h(n)) Ch(n) = O(f(n)) Dh(n) = θ(f(n))

Q6. The number of leaf nodes in a full 4-ary rooted tree of n nodes is

An/2 B(2n − 1) / 4 C(n + 1) / 4 D(3n + 1) / 4

Q7. Which of the following statements maybe false for a decision problem X ∈ NP?

AX can be solved in nondeterministic polynomial time BX can be solved in exponential time CX can be solved in polynomial space DX can be solved in deterministic polynomial time

Q8. A binary search tree is obtained by inserting the words "Mathematics", "Physics", "Geography", "Zoology", "Metrology", "Geology", "Psychology" and "Chemistry" in order. Words are compared by dictionary order. Arrange the following words in increasing order of their level in the tree.
A. Mathematics
B. Zoology
C. Psychology
D. Physics
Choose the correct answer from the options given below:

AA, D, C, B BA, C, D, B CA, D, B, C DC, B, D, A

Q9. In open addressing, how are collisions typically resolved?

ABy probing and finding the next available slot in the table BBy creating a linked list at the point of collision CBy rehashing the entire table DBy storing the colliding elements in a separate array

Q10. What is the height of the binary search tree obtained by inserting the numbers 40, 60, 50, 37, 52, 15, 8, 22 in the given order

A4 B3 C2 D1

Q11. Match the LIST-I with LIST-II.

LIST-I (Data structure)	LIST-II (Characteristics)
A. Stack	I. First-In-First-Out (FIFO) order
B. Queue	II. Last-In-First-Out (LIFO) order
C. Linked list	III. Nodes with two children ordered
D. Binary search tree	IV. Dynamic size, nodes linked sequentially

Choose the correct answer from the options given below:

AA-IV, B-I, C-II, D-III BA-II, B-I, C-IV, D-III CA-III, B-IV, C-I, D-II DA-II, B-I, C-III, D-IV

Q12. How will the following min-heap appear on inserting the key 32?
Original min-heap (level order): 5, 10, 25, 30, 40, 50, 60, 70, 80, 90 (root 5; children of 5 are 10 and 25; children of 10 are 30 and 40; children of 25 are 50 and 60; children of 30 are 70 and 80; the only child of 40 is 90).

ANew node 32 inserted as the right child of 40 (sibling of 90), with no further rearrangement – heap order left unfixed BAfter insertion the heap is re-arranged so that 10's children become 32 and 30, and 32's children become 90 and 40 (25's children remain 50 and 60) CNew node 32 inserted as a second child of 50, leaving the rest of the tree unchanged DNew node 32 inserted deep under 30's subtree below the existing leaves, breaking the complete-tree shape

Q13. Consider the infix expression Q : ((A + B) ∗ D) ↑ (E − F). The equivalent postfix expression of Q is

AAB + D ∗ EF ↑ − BAB + D ∗ − ↑ EF CAB + DE ∗ F − ↑ DAB + D ∗ EF − ↑

Q14. Which of the following trees are height balanced?
A. Binary Search Tree
B. AVL Tree
C. Red-Black Tree
D. B Tree
Choose the correct answer from the options given below:

AA and D Only BA, B and D Only CC and D Only DB, C and D Only

Q15. Which of the following algorithms use the Greedy strategy?
A. Dijkstra's algorithm
B. Kruskal's algorithm
C. Huffman coding
D. Bellman-Ford algorithm
Choose the correct answer from the options given below:

AA, B and D Only BA, B and C Only CC and D Only DA and D Only

Q16. The longest common subsequence of {1,2,3,2,4,1,2} and {2,4,3,1,2,1} is

A2,1,2,3 B1,3,2,1 C2,3,2,1 D2,3,1,2,1

Q17. Match List I (Hashing Collision Handling Method) with List II (Strategy)

List I	List II
A. Chaining	I. Check next slot
B. Linear Probing	II. Use the second hash function
C. Quadratic Probing	III. Linked list at index
D. Double Hashing	IV. Skip slots using quadratic step

AA-II, B-III, C-I, D-IV BA-II, B-III, C-IV, D-I CA-III, B-I, C-IV, D-II DA-IV, B-II, C-I, D-III

Q18. Maintaining a graph in memory by means of its adjacency matrix is known as

AComplete Representation BLinked Representation CCircular Representation DSequential Representation

Q19. Match List I with List II

List I	List II
A. Circular Queue	I. Print Queue
B. Priority Queue	II. CPU Scheduling
C. Double Ended Queue	III. Dijkstra algorithm
D. Simple Queue	IV. Palindrome checking

AA-II, B-III, C-I, D-IV BA-II, B-III, C-IV, D-I CA-III, B-II, C-I, D-IV DA-IV, B-II, C-I, D-III

Q20. The tight asymptotic bound for the recurrence T(n) = 2T(n/4) + √n is

AΘ(√n) BΘ(n log n) CΘ(√n log n) DΘ(n log √n)

Q21. When developing a dynamic programming algorithm, the sequence of steps followed is:
A. Construct an optimal solution from computed information.
B. Recursively define the value of an optimal solution.
C. Characterize the structure of an optimal solution.
D. Compute the value of an optimal solution, typically in a bottom-up fashion.
Choose the correct answer from the options given below:

AB, C, A, D BB, A, C, D CC, B, A, D DC, B, D, A

Q22. The correct sequence of constructing a Huffman tree is
A. Repeat until root formed
B. Create leaf nodes
C. Build priority queue
D. Combine lowest frequency nodes
Choose the correct answer from the options given below:

AB, C, A, D BD, B, A, C CB, C, D, A DC, A, B, D

Q23. Choose the correct statement(s)
A. A problem which is NP-Complete will have the property that it can be solved in polynomial time iff all other NP-complete problems can also be solved in polynomial time.
B. All NP-complete problems are NP-hard problems.
C. If an NP-hard problem can be solved in polynomial time, then all NP-complete problems can be solved in polynomial time.
D. All NP-hard problems are not NP-complete.
Choose the correct answer from the options given below:

AA, C only BB, D only CA, B, C only DA, B, C, D

Q24. Consider the binary tree: A is the root with left child B and right child C; C has left child D and right child E; E has right child F; F has left child G and right child H. What will be the inorder traversal?

ABADCEGFH BGHFEDCBA CBACDEGFH DGHFDEBCA

Q25. Which of the following uses only increment operations for adding and removing elements at either end?

AQueues BStacks CPriority Queues DDeques