WorksheetsCPS02-Day2-NWC -Set01
Total questions: 30
Worksheet time: 30mins
Name
Class
Date
1.
What is a splay operation?
a)
moving parent node to down of child
b)
moving a node to root
c)
moving root to leaf
d)
removing leaf node
2.
Which of the following options is an application of splay trees?
a)
cache Implementation
b)
networks
c)
send values
d)
receive values
3.
What are splay trees?
a)
self adjusting binary search trees
b)
self adjusting binary trees
c)
a tree with strings
d)
a tree with probability distributions
4.
Which of the following property of splay tree is correct?
a)
it holds probability usage of the respective sub trees
b)
any sequence of j operations starting from an empty tree with h nodes at most, takes O(jlogh) time complexity
c)
sequence of operations with h nodes can take O(logh) time complexity
d)
splay trees are unstable trees
5.
Why to prefer splay trees?
a)
easier to program
b)
space efficiency
c)
easier to program and faster access to recently accessed items
d)
quick searching
6.
When we have red-black trees and AVL trees that can perform most of operations in logarithmic times, then what is the need for splay trees?
a)
no there is no special usage
b)
In real time it is estimated that 80% access is only to 20% data, hence most used ones must be easily available
c)
redblack and avl are not upto mark
d)
they are just another type of self balancing binary search trees
7.
Is it true that splay trees have O(logn) amortized complexity?
a)
true
b)
false
8.
What is the disadvantage of using splay trees?
a)
height of a splay tree can be linear when accessing elements in non-decreasing order.
b)
splay operations are difficult
c)
no significant disadvantage
d)
splay tree performs unnecessary splay when a node is only being read
9.
What does the other nodes of an expression tree(except leaves) contain?
a)
only operands
b)
only operators
c)
both operands and operators
d)
expression
10.
What are the operations that could be performed in O(logn) time complexity by red-black tree?
a)
insertion, deletion, finding predecessor, successor
b)
only insertion
c)
only finding predecessor, successor
d)
for sorting
11.
When to choose Red-Black tree, AVL tree and B-trees?
a)
many inserts, many searches and when managing more items respectively
b)
many searches, when managing more items respectively and many inserts respectively
c)
sorting, sorting and retrieval respectively
d)
retrieval, sorting and retrieval respectively
12.
Which of the following is an application of Red-black trees and why?
a)
used to store strings efficiently
b)
used to store integers efficiently
c)
can be used in process schedulers, maps, sets
d)
for efficient sorting
13.
When it would be optimal to prefer Red-black trees over AVL trees?
a)
when there are more insertions or deletions
b)
when more search is needed
c)
when tree must be balanced
d)
when log(nodes) time complexity is needed
14.
What is the below pseudo code trying to do, where pt is a node pointer and root pointer?
redblack(Node root, Node pt) :
if (root == NULL)
return pt
if (pt.data < root.data)
{
root.left = redblack(root.left, pt);
root.left.parent = root
}
else if (pt.data > root.data)
{
root.right = redblackt(root.right, pt)
root.right.parent = root
}
return root
a)
insert a new node
b)
delete a node
c)
search a node
d)
count the number of nodes
15.
Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?
a)
no they are not preferred
b)
because of resizing issues of hash table and better ordering in redblack trees
c)
because they can be implemented using trees
d)
because they are balanced
16.
How can you save memory when storing color information in Red-Black tree?
a)
using least significant bit of one of the pointers in the node for color information
b)
using another array with colors of each node
c)
storing color information in the node structure
d)
using negative and positive numbering
17.
What is the special property of red-black trees and what root should always be?
a)
a color which is either red or black and root should always be black color only
b)
height of the tree
c)
pointer to next node
d)
a color which is either green or black
18.
Why do we impose restrictions like
. root property is black
. every leaf is black
. children of red node are black
. all leaves have same black
a)
to get logarithm time complexity
b)
to get linear time complexity
c)
to get exponential time complexity
d)
to get constant time complexity
19.
What is the speciality of cartesian sorting?
a)
it sorts partially sorted set of data quickly
b)
it considers cartesian product of elements
c)
it sorts elements in less than O(logn)
d)
it is a self balancing tree
20.
Cartesian trees solve range minimum query problem in constant time.
a)
true
b)
false
21.
What is a Cartesian tree?
a)
a skip list in the form of tree
b)
a tree which obeys cartesian product
c)
a tree which obeys heap property and whose inorder traversal yields the given sequence
d)
a tree which obeys heap property only
22.
Consider a sequence of numbers to have repetitions, how a cartesian tree can be constructed in such situations without violating any rules?
a)
use any tie-breaking rule between repeated elements
b)
cartesian tree is impossible when repetitions are present
c)
construct a max heap in such cases
d)
construct a min heap in such cases
23.
What happens if we apply the below operations on an input sequence?
i. construct a cartesian tree for input sequence
ii. put the root element of above tree in a priority queue
iii. if( priority queue is not empty) then
iv. search and delete minimum value in priority queue
v. add that to output
vi. add cartesian tree children of above node to priority queue
a)
constructs a cartesian tree
b)
sorts the input sequence
c)
does nothing
d)
produces some random output
24.
Which of the below statements are true?
i. Cartesian tree is not a height balanced tree
ii. Cartesian tree of a sequence of unique numbers can be unique generated
a)
both statements are true
b)
only i. is true
c)
only ii. is true
d)
both are false
25.
Cartesian trees are most suitable for?
a)
searching
b)
finding nth element
c)
minimum range query and lowest common ancestors
d)
self balancing a tree
26.
A treap is a cartesian tree with ___________
a)
additional value, which is a priority value to the key generated randomly
b)
additional value, which is a priority value to the key generated sequentially
c)
additional heap rule
d)
additional operations like remove a range of elements
27.
What are the two different operations done in an AA-Tree?
a)
shift and color
b)
skew and split
c)
zig and zag
d)
enqueue and dequeue
28.
AA Trees are implemented using?
a)
Colors
b)
Levels
c)
Node size
d)
Heaps
29.
Which of the following is the correct definition for a horizontal link?
a)
connection between node and a child of equal levels
b)
connection between two nodes
c)
connection between two child nodes
d)
connection between root node and leaf node
30.
What is the worst case analysis of an AA-Tree?
a)
O(N)
b)
O(log N)
c)
O( N log N)
d)
O(N2)
100 %
