WorksheetsRMP-2025-SOC23-D1.A1
Total questions: 30
Worksheet time: 30mins
Name
Class
Date
1.
How will you remove a left horizontal link in an AA-tree?
a)
by performing right rotation
b)
by performing left rotation
c)
by deleting both the elements
d)
by inserting a new element
2.
In an AA-tree, we process split first, followed by a skew.
a)
True
b)
False
3.
How many different shapes does maintenance of AA-Tree need to consider?
a)
7
b)
5
c)
2
d)
3
4.
Who is the inventor of AA-Tree?
a)
Arne Anderson
b)
Daniel Sleator
c)
Rudolf Bayer
d)
Jon Louis Bentley
5.
What is the prime condition of AA-tree which makes it simpler than a red-black tree?
a)
Only right children can be red
b)
Only left children can be red
c)
Right children should strictly be black
d)
There should be no left children
6.
Which of the following trees is similar to that of an AA-Tree?
a)
Splay Tree
b)
B+ Tree
c)
AVL Tree
d)
Red-Black Tree
7.
Associative arrays can be implemented using __________
a)
B-tree
b)
A doubly linked list
c)
A single linked list
d)
A self balancing binary search tree
8.
The minimum height of self balancing binary search tree with n nodes is
a)
log2(n)
b)
n
c)
2n + 1
d)
2n – 1
9.
Which of the following is not the self balancing binary search tree?
a)
AVL Tree
b)
2-3-4 Tree
c)
Red – Black Tree
d)
Splay Tree
10.
The binary tree sort implemented using a self – balancing binary search tree takes ______ time is worst case.
a)
O(n log n)
b)
O(n)
c)
O(n2)
d)
O(log n)
11.
An AVL tree is a self – balancing binary search tree, in which the heights of the two child sub trees of any node differ by _________
a)
At least one
b)
At most one
c)
Two
d)
At most two
12.
Binary tree sort implemented using a self balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort.
a)
True
b)
False
13.
Self – balancing binary search trees have a much better average-case time complexity than hash tables.
a)
True
b)
False
14.
Which of the following is a self – balancing binary search tree?
a)
2-3 tree
b)
Threaded binary tree
c)
AA tree
d)
Treap
15.
A self – balancing binary search tree can be used to implement ________
a)
Priority queue
b)
Hash table
c)
Heap sort
d)
Priority queue and Heap sort
16.
In which of the following self – balancing binary search tree the recently accessed element can be accessed quickly?
a)
AVL tree
b)
AA tree
c)
Splay tree
d)
Red – Black tree
17.
What is the space complexity of the in-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)
a)
O(1)
b)
O(nlogd)
c)
O(logd)
d)
O(d)
18.
What is the time complexity of level order traversal?
a)
O(1)
b)
O(n)
c)
O(logn)
d)
O(nlogn)
19.
Which of the following graph traversals closely imitates level order traversal of a binary tree?
a)
Depth First Search
b)
Breadth First Search
c)
Depth & Breadth First Search
d)
Binary Search
20.
In a binary search tree, which of the following traversals would print the numbers in the ascending order?
a)
Level-order traversal
b)
Pre-order traversal
c)
Post-order traversal
d)
In-order traversal
21.
What is the time complexity of pre-order traversal in the iterative fashion?
a)
O(1)
b)
O(n)
c)
O(logn)
d)
O(nlogn)
22.
What is the space complexity of the post-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)
a)
O(1)
b)
O(nlogd)
c)
O(logd)
d)
O(d)
23.
To obtain a prefix expression, which of the tree traversals is used?
a)
Level-order traversal
b)
Pre-order traversal
c)
Post-order traversal
d)
In-order traversal
24.
Consider the following data. The pre order traversal of a binary tree is A, B, E, C, D. The in order traversal of the same binary tree is B, E, A, D, C. The level order sequence for the binary tree is
a)
A, C, D, B, E
b)
A, B, C, D, E
c)
A, B, C, E, D
d)
D, B, E, A, C
25.
Consider the following data and specify which one is Preorder Traversal Sequence, Inorder and Postorder sequences.
S1: N, M, P, O, Q
S2: N, P, Q, O, M
S3: M, N, O, P, Q
a)
S1 is preorder, S2 is inorder and S3 is postorder
b)
S1 is inorder, S2 is preorder and S3 is postorder
c)
S1 is inorder, S2 is postorder and S3 is preorder
d)
S1 is postorder, S2 is inorder and S3 is preorder
26.
A binary search tree contains values 7, 8, 13, 26, 35, 40, 70, 75. Which one of the following is a valid post-order sequence of the tree provided the pre-order sequence as 35, 13, 7, 8, 26, 70, 40 and 75?
a)
7, 8, 26, 13, 75, 40, 70, 35
b)
26, 13, 7, 8, 70, 75, 40, 35
c)
7, 8, 13, 26, 35, 40, 70, 75
d)
8, 7, 26, 13, 40, 75, 70, 35
27.
In postorder traversal of binary tree right subtree is traversed before visiting root.
a)
True
b)
False
28.
What is the possible number of binary trees that can be created with 3 nodes, giving the sequence N, M, L when traversed in post-order.
a)
15
b)
3
c)
5
d)
8
29.
The post-order traversal of a binary tree is O P Q R S T. Then possible pre-order traversal will be
a)
T Q R S O P
b)
T O Q R P S
c)
T Q O P S R
d)
T Q O S P R
30.
Which of the following pair’s traversals on a binary tree can build the tree uniquely?
a)
post-order and pre-order
b)
post-order and in-order
c)
post-order and level order
d)
level order and preorder
100 %
