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
Explanation: 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).
Is a skip list like balanced tree?
a) true
b) false
Explanation: Skip list behaves as a balanced tree with high probability and can be commented as such because nodes with different heights are mixed up evenly.
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 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.
The self-organizing list improves the efficiency of………….
a) binary search
b) jump search
c) sublist search
d) linear search
Which of the following is true about the Move-To-Front Method for
rearranging nodes?
a) node with highest access count is moved to head of the list
b) requires extra storage
c) may over-reward infrequently accessed nodes
d) requires a counter for each node
What technique is used in Transpose method?
a) searched node is swapped with its predecessor
b) node with highest access count is moved to head of the list
c) searched node is swapped with the head of list
d) searched nodes are rearranged based on their proximity to the head node
Explanation: In Transpose method, if any node is searched, it is swapped with the node in front unless it is the head of the list. So, in Transpose method searched node is swapped with its predecessor.
