Paper 2 CS · UNIT 07 · MOCK TEST

Mock 2 – Trees, Heaps & Hashing (Part 1)

Unit 7: Data Structures and Algorithms · 21 questions · about 25 minutes. Press End Mock any time to see your score and the correct answers.

All 11 topic-wise mocks in this unit

0 / 21 answered 00:00

Q1. 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

Q2. 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

Q3. 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

Q4. 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

Q5. 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

Q6. 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

Q7. 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

Q8. 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

Q9. 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

Q10. Arrange the following steps of the inorder traversal of a binary tree in the correct order.
A. Visit the left subtree
B. Visit the root node
C. Visit the right subtree
D. Start traversing by visiting the nodes in the rooted tree
E. Repeat the above three steps.
Choose the correct answer from the options given below:

AA, B, C, D, E BE, A, B, C, D CD, A, B, C, E DD, A, E, B, C

Q11. Which of the following description(s) is/are true?
A. Red-Black Tree – guarantees worst case O(log n) time for search, insert & delete.
B. Trie – used for efficient prefix-based searches.
C. AVL Tree – self-balancing binary search tree with stricter balance criteria.
D. B-Tree – allows efficient search, insert, delete operations in disk-based systems.
Choose the correct answer from the options given below:

AA & B only BC & D only CB only DA, B, C & D

Q12. ______ is a self-balancing binary search tree where the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.

AExpression tree BGame tree CRed-Black tree DThreaded tree

Q13. Which of the following is TRUE?

AThe cost of searching an AVL tree is Θ(log n) but that of a binary search tree is O(n) BThe cost of searching an AVL tree is Θ(log n) but that of a complete binary tree is Θ(n log n) CThe cost of searching a binary tree is O(log n) but that of an AVL tree is Θ(n) DThe cost of searching an AVL tree is Θ(n log n) but that of a binary search tree is O(n)

Q14. Which data structure is typically used to implement a hash table?

ALinked list BArray CBinary tree DStack

Q15. Which collision resolution technique involves maintaining a linked list of collided keys?

ALinear probing BQuadratic probing CChaining DDouble hashing

Q16. 2-3-4 trees are B-trees of order 4. They are isometric to ______ trees.

AAVL BAA C2-3 DRed-Black

Q17. Consider the following statements about the heap sort algorithm:
A. The MAX-HEAPIFY procedure, which runs in O(lg n) time, is the key to maintaining the max-heap property.
B. The BUILD-MAX-HEAP procedure, which runs in O(lg n) time, produces a max-heap from an unordered input array.
C. The MAX-HEAP-INSERT procedure, which runs in O(lg n) time, implements the insertion operation.
D. The HEAP-INCREASE-KEY procedure runs in O(n lg n) time to set the key of a new node to its correct value.
Choose the correct answer from the options given below:

AA, B only BA, C only CB, D only DA, B, C, D

Q18. A B-tree used as an index for a large database table has four levels including the root node. If a new key is inserted into this index, the maximum number of nodes that could be newly created in the process is

A5 B4 C3 D2

Q19. Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R.
Assertion A: AVL trees are more balanced than red-black trees, but they may cause more rotations during insertion and deletion.
Reason R: A red-black tree with n nodes has height greater than 2 log₂(n + 1), and an AVL tree with n nodes has height less than log_φ(√5 (n + 2)) − 2 (where φ is the golden ratio).

ABoth A and R are true and R is the correct explanation of A BBoth A and R are true but R is NOT the correct explanation of A CA is true but R is false DA is false but R is true

Q20. Consider a hash table of size 7 with starting index 0 and hash function (6x + 3) mod 4. Assuming the table is initially empty, which of the following is the content of the table when the sequence 1, 3, 8, 10, 5 is inserted using closed hashing (linear probing)? Here '_' denotes an empty location.

A1, 3, 8, 10, 5, _, _ B3, 8, 1, _, 10, _, 5 C_, 3, 8, 1, _, 10, 5 D_, 1, 3, 8, 10, 5, _

Q21. The height of a binary search tree built by inserting the words banana, peach, apple, pear, coconut, mango and papaya (in this order, alphabetical comparison) is:

A2 B3 C4 D5

Next: Mock 3 – Trees, Heaps & Hashing (Part 2) →