NEW
Font size
S
M
L
XL
WorksheetsVCE-ALPHA-22.11.2023-AN
Total questions: 15
Worksheet time: 15mins
Name
Class
Date
1.
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
2.
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
3.
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
4.
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
5.
Cartesian trees solve range minimum query problem in constant time.
a)
true
b)
false
6.
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
7.
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
8.
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
9.
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
10.
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
11.
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
12.
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
13.
AA Trees are implemented using?
a)
Colors
b)
Levels
c)
Node size
d)
Heaps
14.
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
15.
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)
Reset
