This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Skip List”.
1. The nodes in a skip list may have many forward references. their number is determined
Explanation: The skip list algorithm is probabilistic since the number of forward references is determined probabilistically.
2. Are the below statements true about skiplists?
In a sorted set of elements skip lists can implement the below operations
i.given a element find closest element to the given value in the sorted set in O(logn)
ii.find the number of elements in the set whose values fall a given range in O(logn)
Explanation: Add a few more items, including partial counts, to accomplish the above operations.
3. 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
Explanation: Consider a two-level skip list as an example. The level-2 skip list will, on average, skip one node and, in some cases, two nodes, depending on probabilities. As a result, O (logn).
4. Is a skip list like balanced tree?
Explanation: Since nodes of different heights are matched up equally, the skip list acts as a balanced tree with a high likelihood and can be commented as such.
5. 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 known as the number of bottom layer links that each higher layer element traverses. For example, all level-1 nodes in a level-2 skip list have a width of 1, while level-2 nodes have a width of 2.
6. 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’s a datastructure that speeds up sorted linked list searches in the same way that binary search trees and sorted arrays (using binary search) do.
7. 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: The nodes 20, 30, and 40 will be referred to as top lines, and the nodes in between will be referred to as regular lines. The benefit of skip lists is that we can skip all elements between the top line elements if necessary.
8. Skip lists are similar to which of the following datastructure?
C) binary search tree
D) balanced binary search tree
Explanation: The asymptotic time complexity of skip lists is the same as that of a balanced binary search tree. After one comparison with the root part, we skip almost half of the nodes in a Balanced Binary Search Tree. In the skip lists, the same thing is done. As a result, skip lists resemble balanced Binary search trees.
9. 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: By adding more layers to the Skip list, we can skip some of the elements. The skip list is similar to balanced binary search trees in this case. As a result, the time complexity can be changed from O (n) to O (n) (logn)
10. 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
Explanation: 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.
A skip list is a data structure that is based on probability. With a linked list, the skip list is used to store a sorted list of elements or data. It enables the elements or data to be viewed efficiently. It skips multiple elements of the entire list in a single move, which is why it’s called a skip list. This quasi-randomness has the advantage of not giving away nearly as much level-structure dependent knowledge to an adversarial consumer as the de-randomized version. This is advantageous since a malicious user who knows which nodes are not at the lowest level will reduce output by simply removing higher-level nodes.