What is a skip list?
a) a linkedlist with size value in nodes
b) a linkedlist that allows faster search within an ordered sequence
c) a linkedlist that allows slower search within an ordered sequence
d) a tree which is in the form of linked list
Explanation: It is a datastructure, which can make search in sorted linked list faster in the same way as binary search tree and sorted array (using binary search) are faster.
Consider the 2-level skip list
How to access 38?
a) travel 20-30-35-38
b) travel 20-30-40-38
c) travel 20-38
d) travel 20-40-38
Explanation: Let us call the nodes 20, 30, 40 as top lines and the nodes between them as normal lines. the advantage of skip lists is we can skip all the elements between the top line elements as required.
Skip lists are similar to which of the following datastructure?
a) stack
b) heap
c) binary search tree
d) balanced binary search tree
What is the time complexity improvement of skip lists from linked lists in insertion and deletion?
a) O(n) to O(logn) where n is number of elements
b) O(n) to O(1) where n is number of elements
c) no change
d) O(n) to O(n2) where n is number of elements
Explanation: In Skip list we skip some of the elements by adding more layers. In this the skip list resembles balanced binary search trees. Thus we can change the time complexity from O (n) to O (logn)
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.
