This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Least Recently Used Algorithm (LRU)”.
1. Which of the following is a page replacement algorithm?
a) Least recently used algorithm
b) DSW algorithm
c) Simplex algorithm
d) Aging algorithm
View Answer
Explanation: A page replacement algorithm in operating systems, is used to decide which page should be evicted when the new page comes in. The least recently used (LRU) algorithm is a page replacement algorithm, which evicts the page that hasn’t been used for the longest time.
2. Which type of exception is raised by computer hardware when a code tries to access a block of memory that is not stored in physical memory?
a) Null pointer exception
b) Segmentation error
c) Page fault
d) File not found exception
View Answer
Explanation: A page fault is an error that occurs when a program requests a page in the main memory and the page cannot be found at the requested location. Page faults are indicators, that tell you to increase the amount of memory available to processes.
3. Which data structures can be used to implement least recently used cache?
a) Doubly linked list and a hash map
b) Singly linked list and a hash map
c) Triply linked list and a hash map
d) Unrolled linked list and a hash map
View Answer
Explanation: Least recently used cache is implemented by pairing a doubly linked list with a hash map. Hash map holds the key and refers to the nodes of the linked list. When the cache is full, this caching strategy evicts the elements which are not used for the longest period of time, to make room for new elements.
4. Consider the given page reference string 6, 1, 0, 3, 1, 2, 1, 5, 3, 2, 0, 1, 3. How many page faults will occur if the program has 4-page frames available to it and it uses the least recently used algorithm?
a) 6
b) 7
c) 8
d) 9
View Answer
Explanation: All the slots are empty initially, 6 1 0 3 are allocated → 4 page faults. 1 is already present → 0 page fault. When 2 came, the least recently used was 6, hence 2 will take its place → 1 page fault. 1 is already present → 0 page fault. When 5 came, the least recently used was 0, hence 5 will take its place → 1 page fault. 3 is already present → 0 page fault. 2 is already present → 0 page fault. When 0 came, the least recently used was 1, hence 0 will take its place → 1 page fault. When 1 came, the least recently used was 5, hence 1 will take its place → 1 page fault. 3 is already present → 0 page fault. Hence, total 8 page faults.
5. In the least recently used algorithm, if the current page doesn’t exist in the set then it is replaced with the recently used page.
a) True
b) False
View Answer
Explanation: In the least recently used algorithm, the page that has not been used for the longest period of time is evicted. It looks for the pages which are already page faulted. Hence, if the current page doesn’t exist in the set, it is replaced by the page that hasn’t been used for the longest time.
6. What will be the output of the following code in java?
import java.util.ArrayList; public class LRU { public static void main(String[] args) { int page_frame = 3; int page_ref_string[] = {1, 2, 4, 1, 0, 3, 2, 0, 5, 4}; ArrayList<Integer> s=new ArrayList<>(page_frame); int count=0; int page_faults=0; for(int i:page_ref_string) { if(!s.contains(i)) { if(s.size()==page_frame) { s.remove(0); s.add(page_frame-1,i); } else s.add(count,i); page_faults++; ++count; } else { s.remove((Object)i); s.add(s.size(),i); } } System.out.println(page_faults); } }
a) 7
b) 8
c) 9
d) 10
View Answer
Explanation: The following java code is the implementation of the least recently used algorithm. All the slots are empty initially, 1 2 4 are allocated → 3 page faults. 1 is already present → 0 page fault. When 0 came, the least recently used was 2, hence 0 will take its place → 1 page fault. When 3 came, the least recently used was 4, hence 3 will take its place → 1 page fault. When 2 came, the least recently used was 1, hence 2 will take its place → 1 page fault 0 is already present → 0 page fault. When 5 came, the least recently used was 3, hence 5 will take its place → 1 page fault. When 4 came, the least recently used was 2, hence 1 will take its place → 1 page fault. Hence, total 8-page faults.
Output: 8
7. Least recently used cache has the space complexity of O(n).
a) True
b) False
View Answer
Explanation: Least recently used cache can be implemented by pairing a doubly linked list with a hash map. For tracking n items in the least recently used cache, a hash map holding n elements and a linked list of length n is required. Hence, it has the space complexity of O(n).
8. Which of the following best represents the time complexity to access an item in the least recently used cache?
a) O(n)
b) O(1)
c) O(n2)
d) O(log n)
View Answer
Explanation: In the least recently used cache, the elements are stored from most recently used to least recently used. It takes constant time to access both the elements. Hence, it takes O(1) time to access an element in the least recently used cache.
9. Which among the following is an application of the least recently used algorithm?
a) Paging for memory management
b) Dynamic memory allocation
c) Priority scheduling
d) Disk scheduling
View Answer
Explanation: Paging, used in memory management by the operating systems, uses page replacement algorithms. They are needed to decide which page should be evicted when the new page comes in. The least recently used is one of the page replacement algorithms which is used to reduce the number of page faults.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Programming MCQs
- Practice Computer Science MCQs
- Check Design and Analysis of Algorithms Books
- Apply for Computer Science Internship
- Practice Data Structure MCQ
