Skip List Questions and Answers

[Solved] What is indexed skip list?

What is indexed skip list? a) it stores width of link in place of elementb) it stores index valuesc) array based linked listd) indexed tree Answer: aExplanation: The width is defined as a number of bottom layer links that are being traversed by each of the higher layer elements. e.g: for level-2 skip lists, all …

[Solved] What is indexed skip list? Read More »

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

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 probabilitiesb) that cannot be maintainedc) rebalancing of listsd) reconstruction Answer: aExplanation: For example consider a 2 level skip list. the level-2 skip list can skip one node on an average and …

[Solved] How to maintain multi-level skip list properties when insertions and deletions are done? Read More »

[Solved] To which data structure are skip lists similar to in terms of time complexities in worst and best cases?

To which data structure are skip lists similar to in terms of time complexities in worst and best cases? a) balanced binary search treesb) binary search treesc) binary treesd) linked lists Answer: aExplanation: Skip lists are similar to any randomly built binary search tree. a BST is balanced because to avoid skew tree formations in …

[Solved] To which data structure are skip lists similar to in terms of time complexities in worst and best cases? Read More »

[Solved] What is the time complexity improvement of skip lists from linked lists in insertion and deletion?

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 the number of elementsb) O(n) to O(1) where n is the number of elementsc) no changed) O(n) to O(n2) where n is the number of elements Answer: aExplanation: In Skip list, we …

[Solved] What is the time complexity improvement of skip lists from linked lists in insertion and deletion? Read More »

[Solved] Skip lists are similar to which of the following data structure?

Skip lists are similar to which of the following data structure? a) stackb) heapc) binary search treed) balanced binary search tree Answer: dExplanation: Skip lists have the same asymptotic time complexity as balanced binary search trees. For a Balanced Binary Search Tree, we skip almost half of the nodes after one comparison with the root …

[Solved] Skip lists are similar to which of the following data structure? Read More »