This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Treap”.
1. Several other operations like union set difference and intersection can be done in treaps.
Explanation: In addition to insertion, deletion, and search, treaps can perform operations such as union, intersection, and set difference.
2. What is the average running time of a treap?
B) O(N log N)
C) O(log N)
D) O(M log N)
Explanation: The average case and worst case analysis of a treap was considered to be O mathematically (log N).
3. Which node has the lowest priority in a treap?
A) root node
B) leaf node
C) null node
D) centre node
Explanation: Since the priority of a node is determined by heap order, the root node has the lowest priority in a heap.
4. What is the priority of a null node?
C) random number
Explanation: In a treap, the priority of a null node is set to infinity such that when it is deleted, the priority of that node is set to infinity, rotated, and freed.
5. Who invented treaps?
A) Cecilia and Raimund
B) Arne Andersson
C) Donald Shell
D) Harris and Ross
Explanation: Treaps was created by Cecilia and Raimund. AA – Trees was created by Arne Andersson. Shell sort was conceived by Donald Shell, and the full flow problem was formulated by Harris and Ross.
6. What is the space complexity of a treap algorithm?
B) O(log N)
C) O(log N)
Explanation: A treap’s average and worst case space complexity is considered to be O in mathematics (N).
7. A treap is a combination of a tree and a heap.
Explanation: A treap is the product of combining a tree and a heap. The fact that a heap is heap-ordered determines the structure of the heap.
8. Which is the simplest of all binary search trees?
A) AVL tree
C) Splay tree
D) Binary heap
Explanation: The shortest binary search tree is the treap. The implementation is non-recursive and each node is assigned a numerical priority.
9. What is the reason behind the simplicity of a treap?
A) Each node has data and a pointer
B) Each node is colored accordingly
C) It is a binary search tree following heap principles
D) Each node has a fixed priority field
Explanation: The treap is the easiest of them all because we don’t have to think about changing a node’s priority.
10. What is the condition for priority of a node in a treap?
A) a node’s priority should be greater than its parent
B) a node’s priority should be at least as large as its parent
C) the priority is randomly assigned and can have any value
D) a node’s priority is always given in decreasing order
Explanation: The priority of a node should correspond to the heap order. That is, the priority of each node should be at least equal to that of its parent.
The treap and the randomised binary search tree are two binary search tree data structures that keep a dynamic collection of ordered keys and enable binary searches between them. The shape of the tree after any sequence of key insertions and deletions is a random variable with the same probability distribution as a random binary tree; in particular, its height is proportional to the logarithm of the number of keys with high probability, implying that each search, insertion, or deletion operation takes logarithmic time.