Paper 2 CS · UNIT 07 · MOCK TEST

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

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. Which of the following are true for a complete (full) binary tree?
A. It always has an odd number of vertices.
B. With i internal vertices, it has i + 1 leaves.
C. With l leaves, it has 2l − 1 vertices.
D. With 2n − 1 vertices, it has n leaves.
Choose the correct answer from the options given below:

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

Q2. In a ______ the left and right subtrees of some node differ in height by more than one.

ABalanced binary tree BWeight-balanced binary tree CHeight-balanced tree DUnbalanced binary tree

Q3. Given six weights 4, 15, 25, 5, 8, 16, construct a 2-tree (extended binary tree) with minimum weighted path length. What is the minimum weighted path length?

A231 B172 C73 D77

Q4. Suppose we store n keys in a hash table of size m = n² using a hash function h chosen randomly from a universal class of hash functions. Then the probability that there are any collisions is ______

Agreater than 1/5 Bgreater than 1/2 Cless than 1/2 Dless than 1/5

Q5. Which of the following rotations are correctly explained in the context of an AVL tree?
A. LL rotation: the new node is inserted in the left subtree of the left subtree of the critical node.
B. RR rotation: the new node is inserted in the right subtree of the right subtree of the critical node.
C. LR rotation: the new node is inserted in the right subtree of the left subtree of the critical node.
D. RL rotation: the new node is inserted in the left subtree of the right subtree of the critical node.
Choose the correct answer from the options given below:

AA, D only BA, C Only CA, B, C and D DB, C Only

Q6. Match List I with List II

List I	List II
A. Linear Program	I. Prim's Algorithm
B. Predicate Logic	II. In order
C. Tree Traversal	III. Simplex Algorithm
D. Minimum Spanning Tree Problem	IV. First order logic

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

Q7. How many different binary trees are possible with n nodes?

An − 1 B2ⁿ − 1 C2ⁿ D(1/(n+1)) · C(2n, n)

Q8. The number of nodes of height h in any n-element heap is at most

A⌈n / 2^h+1⌉ B⌈n / 2^h−1⌉ C⌈n / 2^h⌉ D⌈(n − 1) / 2^h−1⌉

Q9. Consider a B-tree of height h and minimum degree t ≥ 2 that contains n keys, n ≥ 1. Which of the following is correct?

Ah ≥ log_t((n + 1)/2) Bh ≤ log_t((n + 1)/2) Ch ≥ log_t((n − 1)/2) Dh ≤ log_t((n − 1)/2)

Q10. Consider a hash table of size 11 that uses open addressing with linear probing, with h(k) = k mod 11. Records with keys 43, 36, 92, 87, 11, 47, 11, 13, 14 are inserted into an initially empty table with bins 0–10. What is the index of the bin into which the last record is inserted?

A8 B7 C10 D4

Q11. Consider the traversals of a tree:
Preorder → ABCEIFJDGHKL
Inorder → EICFJBGDKHLA
Which of the following is the correct postorder traversal?

AEIFJCKGLHDBA BFCGKLHDBUAE CFCGKLHDBAEIJ DIEJFCGKLHDBA

Q12. How many rotations are required during the construction of an AVL tree if the following elements are inserted in the given sequence?
35, 50, 40, 25, 30, 60, 78, 20, 28

A2 left rotations, 2 right rotations B2 left rotations, 3 right rotations C3 left rotations, 2 right rotations D3 left rotations, 1 right rotation

Q13.

Which of the following trees are height balanced?

A. Binary Search Tree

B. AVL Tree

C. Red-Black Tree

D. B Tree

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

Q14.

Match List I with List II

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

Q15.

Considering the binary tree shown (A has children B and C; C has children D and E; E has right child F; F has children G and H), what will be the inorder traversal?

ABADCEGFH BGHFEDCBA CBACDEGFH DGHFDEBCA

Q16.

The height of a binary search tree for the words banana, peach, apple, pear, coconut, mango and papaya using alphabetical order is :

A2 B3 C4 D5

Q17.

Which of the following are true for a complete binary tree?

A. It has always odd number of vertices.

B. With i internal vertices, it has i+1 leaves.

C. With l leaves, it has 2l-1 vertices.

D. With 2 n-1 vertices, it has n leaves.

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

Q18.

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 search 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)

Q19.

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

AAVL BAA C2-3 DRed-Black

Q20.

Given below are two statements: one is labelled as Assertion A and the other is labelled as

Reason R.

Assertion A: The AVL trees are more balanced as compared to Red Black trees, but they may cause more rotations during insertion and deletion

Reason R: A Red Black tree with n nodes has 2 log (n + 1) height that is greater than 2 and the AVL tree with n nodes has height less than – log (√5(n + 2)) − 2( Φ Φ where is golden ratio) In the light of the above statements, choose the correct answer from the options given below.

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

Q21.

Consider a hash table of size seven with starting (6x + 3) mod 4 index zero and a hash function . Assuming the hash table is initially empty. Which of the following is the content of the table when 1, 3, 8, 10, 5 the sequence , is inserted into the table using closed hashing? Here "__ " denotes an empty location in the table.

A1,3,8,10,5_,_ B3,8,1,_,10_,5 C_3,8,1,_,10,5 D_1,3,8,10,5_ C + +

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