1. Which of the following is also known as Rope data structure?
a) Cord
b) String
c) Array
d) Linked List
Answer: a
Explanation:
Array is a linear data structure. Strings are a collection and sequence of codes, alphabets or characters. Linked List is a linear data structure having a node containing data input and the address of the next node. The cord is also known as the rope data structure.
2. Which type of data structure does rope represent?
a) Array
b) Linked List
c) Queue
d) Binary Tree
Answer: d
Explanation:
Tango tree is an example of binary search tree which was developed by four famous scientists Erik Demaine, Mihai Patrascu, John Lacono and Harmon in the year 2004.
3. What is the time complexity for finding the node at x position where n is the length of the rope?
a) O (log n)
b) O (n!)
c) O (n2)
d) O (1)
Answer: a
Explanation:
In order to find the node at x position in a rope data structure where N is the length of the rope, we start a recursive search from the root node. So the time complexity for worst case is found to be O (log N).
4. What is the time complexity for creating a new node and then performing concatenation in the rope data structure?
a) O (log n)
b) O (n!)
c) O (n2)
d) O (1)
Answer: d
Explanation:
In order to perform the concatenation on the rope data structure, one can create two nodes S1 and S2 and then performing the operation in constant time that is the time complexity is O (1).
5. What is the time complexity for splitting the string into two new string in the rope data structure?
a) O (n2)
b) O (n!)
c) O (log n)
d) O (1)
Answer: c
Explanation:
In order to perform the splitting on the rope data structure, one can split the given string into two new string S1 and S2 in O (log n) time. So, the time complexity for worst case is O (log n).
6. Which type of binary tree does rope require to perform basic operations?
a) Unbalanced
b) Balanced
c) Complete
d) Full
Answer: b
Explanation:
To perform the basic operations on a rope data structure like insertion, deletion, concatenation and splitting, the rope should be a balanced tree. After performing the operations one should again re-balance the tree.
7. What is the time complexity for inserting the string and forming a new string in the rope data structure?
a) O (log n)
b) O (n!)
c) O (n2)
d) O (1)
Answer: a
Explanation:
In order to perform the insertion on the rope data structure, one can insert the given string at any position x to form a new string in O (log n) time. So, the time complexity for worst case is O (log n). This can be done by one split operation and two concatenation operations.
8. Is insertion and deletion operation faster in rope than an array?
a) True
b) False
Answer: a
Explanation:
In order to perform the insertion on the rope data structure, the time complexity is O (log n). In order to perform the deletion on the rope data structure, the time complexity for worst case is O (log n). While for arrays the time complexity is O (n).
9. What is the time complexity for deleting the string to form a new string in the rope data structure?
a) O (n2)
b) O (n!)
c) O (log n)
d) O (1)
Answer: c
Explanation:
In order to perform the deletion on the rope data structure, one can delete the given string at any position x to form a new string in O (log n) time. So, the time complexity for worst case is O (log n). This can be done by two split operations and one concatenation operation.
10. Is it possible to perform a split operation on a string in the rope if the split point is in the middle of the string.
a) True
b) False
Answer: a
Explanation:
In order to perform the splitting on the rope data structure, one can split the given string into two new string S1 and S2 in O (log n) time. So, the time complexity for worst case is O (log n). The split operation can be performed if the split point is either at the end of the string or in the middle of the string.
11. Which operation is used to break a preferred path into two sets of parts at a particular node?
a) Differentiate
b) Cut
c) Integrate
d) Join
Answer: b
Explanation:
A preferred path is broken into two parts. One of them is known as top part while other is known as bottom part. To break a preferred path into two sets, cut operation is used at a particular node.
12. What is the upper bound for a tango tree if k is a number of interleaves?
a) k+2 O (log (log n))
b) k O (log n)
c) K2 O (log n)
d) k+1 O (log (log n))
Answer: d
Explanation:
Upper bound is found to analyze the work done by a tango tree on a given set of sequences. In order to connect to the tango tree, the upper bound is found to be k+1 O (log (log n)).
13. What is the time complexity for searching k+1 auxiliary trees?
a) k+2 O (log (log n))
b) k+1 O (log n)
c) K+2 O (log n)
d) k+1 O (log (log n))
Answer: d
Explanation:
Since each search operation in the auxiliary tree takes O (log (log n)) time as auxiliary tree size is bounded by the height of the reference tree that is log n. So for k+1 auxiliary trees, total search time is k+1 O (log (log n)).
14. What is the time complexity for the update cost on auxiliary trees?
a) O (log (log n))
b) k-1 O (log n)
c) K2 O (log n)
d) k+1 O (log (log n))
Answer: d
Explanation:
The update cost also is bounded by the upper bound. We perform one cut as well as one join operation for the auxiliary tree, so the total update cost for the auxiliary tree is found to be k+1 O (log (log n)).
15. Which of the following is the self-adjusting binary search tree?
a) AVL Tree
b) Splay Tree
c) Top Tree
d) Ternary Tree
Answer: b
Explanation:
Splay tree is a self – adjusting binary search tree. It performs basic operations on the tree like insertion, deletion, loop up performing all these operations in O (log n) time.
16. Reversal algorithm and juggling algorithm for array rotation have the same time complexity.
a) True
b) False
Answer: a
Explanation:
Time complexity of juggling algorithm is O(n) which like that of reversal algorithm. They also have the same space complexity
