This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Self Organizing List”.
1. In _____________ method, whenever a node is accessed, it might move to the head of the list if its number of accesses becomes greater than the records preceding it.
A) least recently used
Explanation: The number of times a node has been accessed is counted and stored in a counter variable associated with each node in the count process. The nodes are then ordered in descending order based on the number of times they have been accessed. The node with the most accesses is at the top of the list.
2. Symbol tables during compilation of program is efficiently implemented using __________
A) a singly linked list
B) a doubly linked list
C) a self organizing list
D) an array
Explanation: Self-organizing lists allow for quick sequential searches, and they’re easy to set up and don’t take up any extra space. The symbol table is implemented using a self-organizing list.
3. Which of the following method performs poorly when elements are accessed in sequential order?
A) count method
B) move to front method
C) transpose meth
D) ordering method
Explanation: When elements are accessed in sequential order, the move-to-front method performs poorly, particularly if the sequential order is repeated multiple times.
4. The self organizing list improves _____
A) average access time
D) binary search
Explanation: The nodes in the self-organizing list are rearranged based on their access probabilities. As a result, the necessary elements can be found quickly. As a result, the self-organizing list is mostly used to reduce average access time.
5. Which of the following is not the rearranging method used to implement self-organizing lists?
A) count method
B) move to front method
C) ordering method
D) least frequently used
Explanation: A buffer replacement policy is the least commonly used, while the other three are strategies for reordering nodes in self-organizing lists based on their access probability.
6. The self organizing list improves the efficiency of _______
A) binary search
B) jump search
C) sublist search
D) linear search
Explanation: The time complexity of linear search in a connected list is O. (n). The self-organizing list is used to increase the performance of the linear search. By shifting the most commonly accessed items to the top of the list, a self-organizing list increases the efficiency of linear search.
7. 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
Explanation: The element that is being searched is moved to the front of the list using the Move-To-Front Method. And if a node is searched even once, it is pushed to the top of the list and granted top priority, even if it is unlikely to be accessed again in the near future. Over-rewarding is the term for a case like this.
8. 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: If any node is checked in the Transpose process, it is swapped with the node in front unless it is the first in the list. As a result, the searched node is swapped with its predecessor in the Transpose process.
9. The worst case running time of a linear search on the self organizing list is ____
Explanation: The worst case scenario is when the element is at the very end of the list. As a result, n comparisons to the locate element are needed. As a result, the worst-case linear search time on a self-organizing list is O. (n).
10. Which of the following data structure is preferred to have lesser search time when the list size is small?
A) search tree
B) sorted list
C) self organizing list
D) linked list
Explanation: Self-organizing lists are easier to use and execute than search trees, and they take up no extra space. When the list size is limited, it is preferable to use a self-organizing list.
A self-organizing list is one that reorders the elements to increase average access time using a self-organizing heuristic. The aim of a self-organizing list is to make linear search more efficient by moving frequently accessed objects to the top of the list. In the best case, a self-organizing list achieves near constant time for element access. A reorganising algorithm is used by a self-organizing list to respond to different query distributions at runtime.