Skip List | Data Structure MCQs


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

Answer: Option 'A'

Skip lists are similar to any randomly built binary search tree. a BST is balanced because to avoid skew tree formations in case of sequential input and hence achieve O(logn) in all 3 cases. now skip lists can gurantee that O(logn) complexity for any input.


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

Answer: Option 'A'

O(n) to O(logn) where n is number of elements


Skip lists are similar to which of the following datastructure?

   A.) heap
   B.) balanced binary search tree
   C.) stack
   D.) binary search tree

Answer: Option 'B'

balanced binary search tree
As all elements lesser than the top line elements are placed infront of it and greater ones after it. please refer question for clarity. skip lists have the same asymptotic time complexities as balanced trees.


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

Answer: Option 'A'

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.


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

Answer: Option 'B'

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.


The nodes in a skip list may have many forward references. their number is determined

   A.) probabilistically
   B.) sequentially
   C.) randomly
   D.) orthogonally

Answer: Option 'A'

The number of forward references are determined probabilistically, that is why skip list is a probabilistic algorithm.


How to maintain multi-level skip list properties when insertions and deletions are done?

   A.) design each level of a multi-level skip list with varied probabilities
   B.) that cannot be maintained
   C.) rebalancing of lists
   D.) reconstruction

Answer: Option 'A'

for example consider a 2 level skip list. the level-2 skip list can skip one node on a average and at some places may skip 2 nodes, depending on probabilities. this ensures O(logn).

Skip List | Data Structure MCQs Download Pdf