Data Structure Questions and Answers-Skip List

YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

CLICK HERE TO DOWNLOAD

Data Structure Questions and Answers-Skip List

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 1 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.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 2 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.

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Skip lists are similar to which of the following datastructure?
A
stack
B
heap
C
binary search tree
D
balanced binary search tree
Question 3 Explanation: 
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.

Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 4 Explanation: 
None.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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
Question 5 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.

There are 5 questions to complete.