To which datastructure are skip lists similar to in terms of time complexities in worst and best cases?
a) balanced binary search trees
b) binary search trees
c) binary trees
d) linked lists
The nodes in a skip list may have many forward references. their number is determined
a) probabilistically
b) randomly
c) sequentially
d) orthogonally
Explanation: The number of forward references are determined probabilistically, that is why skip list is a probabilistic algorithm.
Is a skip list like balanced tree?
a) true
b) false
Explanation: Skip list behaves as a balanced tree with high probability and can be commented as such because nodes with different heights are mixed up evenly.
What is indexed skip list?
a) it stores width of link in place of element
b) it stores index values
c) array based linked list
d) indexed tree
Explanation: The width is defined as number of bottom layer links that are being traversed by each of higher layer elements. e.g: for a level-2 skip lists, all level-1 nodes have 1 as width, for level-2 width will be 2.
