25 + Interview Questions in Page Replacement Algorithms in Data Structures & Algorithms Ii Page 1 InterviewSolution

1.	_________ states that, on a page fault, the frame that has been in memory the longest is replaced.(a) Belady’s anomaly(b) Second chance algorithm(c) Partial second chance algorithm(d) LRU replacement algorithmI have been asked this question by my college professor while I was bunking the class.The above asked question is from Page Replacement Algorithms topic in portion Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The correct choice is (a) Belady’s anomaly Easiest explanation - Belady’s anomaly states that, on a PAGE fault, the FRAME that has been in MEMORY the LONGEST is replaced. It occurs in FIFO algorithm.

Discussion

2.	Under which of the following scenarios is page replacement algorithm required?(a) When total memory exceeds physical memory(b) To determine the number of frames for each process(c) When paging and segmentation are to be used(d) Execution of a process, not in memoryI have been asked this question by my school teacher while I was bunking the class.My doubt stems from Page Replacement Algorithms in portion Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The correct choice is (a) When TOTAL memory EXCEEDS physical memory Best explanation: An appropriate page REPLACEMENT algorithm is required when the total memory requirements exceed the physical memory.

Discussion

3.	What is the competitive analysis of the FIFO algorithm?(a) k/k+1(b) k+1(c) k(k+1)(d) k/(k-h+1)The question was posed to me in a job interview.This is a very interesting question from Page Replacement Algorithms in portion Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The correct answer is (d) k/(k-H+1) Easy explanation - The competitive ANALYSIS of a FIFO algorithm is MATHEMATICALLY found to be k/(k-h+1) where k and h are some CONSTANTS USED in page replacement and always, h<=k.

Discussion

4.	FIFO algorithm is used by __________ operating system.(a) Linux(b) Mac(c) Windows(d) VAX/VMSThis question was addressed to me in final exam.Enquiry is from Page Replacement Algorithms in portion Page Replacement Algorithms of Data Structures & Algorithms II
Answer» Correct option is (d) VAX/VMS To EXPLAIN: Of the following GIVEN operating systems, VAX/VMS USES a FIFO algorithm.

Discussion

5.	The cost required to execute a FIFO algorithm is expensive.(a) True(b) FalseI have been asked this question during an online exam.Asked question is from Page Replacement Algorithms in section Page Replacement Algorithms of Data Structures & Algorithms II
Answer» Right ANSWER is (b) False The best I can explain: The cost of a FIFO ALGORITHM is cheap and intuitive and it is used in POOR PRACTICAL applications.

Discussion

6.	In a FIFO algorithm, when a page is to be replaced, which of the following page is chosen?(a) Oldest page(b) Newest page(c) Frequently occurred page in past(d) Frequently occurred page in futureI have been asked this question by my school principal while I was bunking the class.My question is based upon Page Replacement Algorithms topic in section Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The CORRECT answer is (a) OLDEST page Easiest explanation - In FIFO page REPLACEMENT algorithm, when a page is to be replaced, the oldest page is CHOSEN and replaced at the tail of the QUEUE.

Discussion

7.	Which of the following is required to determine the number of page faults in FIFO?(a) Page number(b) Page frame number(c) Memory capacity(d) Segment numberI had been asked this question in an international level competition.My question is from Page Replacement Algorithms topic in portion Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The correct answer is (B) Page FRAME number For explanation: To determine the number of page FAULTS in a page REPLACEMENT algorithm using FIFO, we require page frame number.

Discussion

8.	Which of the following is the main drawback of FIFO page replacement algorithm?(a) Requirement of large memory(b) Frame allocation(c) Reduction in multiprogramming(d) Reduced optimalityThis question was addressed to me by my school teacher while I was bunking the class.My question is from Page Replacement Algorithms topic in division Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The correct choice is (C) Reduction in MULTIPROGRAMMING The explanation is: The main drawback of FIFO page REPLACEMENT algorithm is that it reduces the LEVEL of multiprogramming and also causes Belady’s anomaly.

Discussion

9.	Which of the following page replacement algorithms return the minimum number of page faults?(a) LRU replacement algorithm(b) Optimal page replacement algorithm(c) FIFO(d) Counting based replacementThis question was posed to me by my school principal while I was bunking the class.Asked question is from Page Replacement Algorithms topic in chapter Page Replacement Algorithms of Data Structures & Algorithms II
Answer» RIGHT choice is (B) Optimal page replacement algorithm The best I can explain: Though FIFO is the simplest of all ALGORITHMS, optimal page replacement algorithm returns the minimum NUMBER of page faults.

Discussion

10.	As the number of frames available increases, the number of page faults decreases.(a) True(b) FalseThis question was addressed to me in quiz.This key question is from Page Replacement Algorithms in section Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The correct option is (a) True Easy explanation - One of the rules of the page REPLACEMENT algorithm is that, as the number of FRAMES AVAILABLE increases, the number of page faults DECREASES.

Discussion

11.	__________ algorithm associates with each page the time when the page was brought into memory.(a) Optimal page replacement(b) FIFO(c) LRU replacement algorithm(d) Counting based replacementThe question was asked in quiz.My question comes from Page Replacement Algorithms topic in chapter Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The correct choice is (b) FIFO The BEST explanation: FIFO algorithm associates with each page the TIME when the page was BROUGHT into memory. The new page is inserted at the tail of the queue.

Discussion

12.	Which of the following is the simplest page replacement algorithm?(a) FIFO(b) Optimal page replacement(c) LRU replacement(d) Counting based replacementThis question was posed to me during an online interview.My enquiry is from Page Replacement Algorithms in portion Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The CORRECT answer is (a) FIFO The explanation is: FIFO is the simplest page REPLACEMENT algorithm SINCE LRU and optimal replacement algorithms REQUIRE past and FUTURE data patterns respectively.

Discussion

13.	________is a typical online problem from the competitive analysis to determine the optimal solution.(a) Page replacement algorithm(b) Segmentation(c) Paging(d) Segmentation with pagingThe question was posed to me during an online interview.I'd like to ask this question from Page Replacement Algorithms topic in chapter Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The correct OPTION is (a) PAGE replacement algorithm The EXPLANATION is: Page replacement is a TYPICAL online problem from the competitive analysis. They determine which PAGES to page out or write to disk.

Discussion

14.	Consider a reference string 1,2,3,2,1,5,2,1,6,2,5,6,3,1,3,6,1,2,4,3 of frame size 3. Calculate the number of page faults using optimal page replacement algorithm.(a) 12(b) 16(c) 14(d) 15I have been asked this question during an interview.I'm obligated to ask this question of Page Replacement Algorithms topic in portion Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The CORRECT answer is (c) 14 The best I can explain: For the given reference STRING, the number of PAGE faults USING optimal page REPLACEMENT algorithm is said to be 14.

Discussion

15.	Consider a reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 of frame size 4. Calculate the number of page faults using optimal page replacement algorithm.(a) 7(b) 9(c) 8(d) 6This question was addressed to me during an online exam.This question is from Page Replacement Algorithms topic in portion Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The correct option is (c) 8 For explanation: For the GIVEN reference string, the NUMBER of page faults using optimal page replacement algorithm is said to be 8. It is SOLVED in the given diagram.

Discussion

16.	Consider a reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 of frame size 3. Calculate the number of page faults using optimal page replacement algorithm.(a) 10(b) 9(c) 8(d) 7I have been asked this question during an interview.This question is from Page Replacement Algorithms topic in portion Page Replacement Algorithms of Data Structures & Algorithms II
Answer» RIGHT option is (b) 9 The EXPLANATION is: For the GIVEN string, the number of page faults USING optimal page replacement algorithm is 9. It is solved in the given diagram.

Discussion

17.	When all software that runs on a system is known beforehand, optimal page replacement algorithm can be used in a general-purpose operating system.(a) True(b) FalseThis question was addressed to me during an interview.My query is from Page Replacement Algorithms in chapter Page Replacement Algorithms of Data Structures & Algorithms II
Answer» Correct ANSWER is (a) True The best explanation: The algorithm can be implemented in a general-purpose algorithm if the SOFTWARE is known BEFOREHAND and if it is amenable to the static ANALYSIS of the memory.

Discussion

18.	In a stack algorithm, the set of pages in a k-frame memory is always a subset of pages in a __________ frame memory.(a) k-1(b) k(c) k+1(d) k(k+1)This question was posed to me in an online interview.I'd like to ask this question from Page Replacement Algorithms in division Page Replacement Algorithms of Data Structures & Algorithms II
Answer» CORRECT OPTION is (c) k+1 Best explanation: Stack ALGORITHM is satisfied if the set of pages in a k-FRAME MEMORY is always a subset of pages in a k+1 frame memory.

Discussion

19.	Optimal page replacement algorithm is said to satisfy __________(a) Online algorithm(b) Stack algorithm(c) Queue algorithm(d) Array algorithmI had been asked this question during an interview.This intriguing question comes from Page Replacement Algorithms topic in portion Page Replacement Algorithms of Data Structures & Algorithms II
Answer» Right option is (b) STACK algorithm For explanation: Optimal page REPLACEMENT algorithm is said to satisfy the stack algorithm. It is ALSO called as inclusion property.

Discussion

20.	Optimal page replacement algorithm is implemented in __________(a) General-purpose operating system(b) Special-purpose operating system(c) In any kind of operating system(d) In Windows onlyI had been asked this question during an online interview.The doubt is from Page Replacement Algorithms in division Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The CORRECT answer is (B) Special-purpose OPERATING SYSTEM The best I can explain: Optimal page replacement algorithm is used in special-purpose operating system because it is impossible to compute time before which a page is used.

Discussion

21.	Analysis of the optimal paging problem has been done through___________(a) Deterministic algorithm(b) Online algorithm(c) Euclid algorithm(d) Optimal algorithmThe question was posed to me in examination.My question is from Page Replacement Algorithms topic in portion Page Replacement Algorithms of Data Structures & Algorithms II
Answer» Right option is (B) Online ALGORITHM Explanation: Analysis of the OPTIMAL paging algorithm is done through an online algorithm. EFFICIENCY is calculated through AMORTIZED analysis.

Discussion

22.	A page that is not going to be used for the next 7 seconds will be swapped out over a page that is going to be used within the next 0.7 seconds.(a) True(b) FalseThe question was posed to me in examination.The above asked question is from Page Replacement Algorithms topic in chapter Page Replacement Algorithms of Data Structures & Algorithms II
Answer» Right OPTION is (a) True Easiest EXPLANATION - In an optimal PAGE replacement ALGORITHM, the page that is to be used LATER in the future is swapped out over a page that is to be used immediately.

Discussion

23.	In a optimal page replacement algorithm, when a page is to be replaced, which of the following pages is chosen?(a) Oldest page(b) Newest page(c) Frequently occurred page in the future(d) Not frequently occurred page in the futureThis question was posed to me in semester exam.Origin of the question is Page Replacement Algorithms topic in chapter Page Replacement Algorithms of Data Structures & Algorithms II
Answer» The CORRECT OPTION is (d) Not frequently occurred page in the future The EXPLANATION is: The page which doesn’t OCCUR more frequently in the future is CHOSEN to be replaced with the page in the frame.

Discussion

24.	Optimal page replacement algorithm is also called as __________(a) LIFO(b) NRU(c) Clairvoyant replacement algorithm(d) Page bufferingThis question was addressed to me by my college director while I was bunking the class.My question is based upon Page Replacement Algorithms topic in section Page Replacement Algorithms of Data Structures & Algorithms II
Answer» Right OPTION is (c) Clairvoyant REPLACEMENT ALGORITHM For explanation: Optimal page replacement algorithm is ALSO called a Clairvoyant replacement algorithm or Belady’s optimal replacement algorithm.

Discussion

25.	__________ has the lowest fault rate of all the page replacement algorithms.(a) Optimal page replacement algorithm(b) LRU replacement algorithm(c) FIFO(d) Counting basedThis question was posed to me during an interview for a job.This question is from Page Replacement Algorithms topic in section Page Replacement Algorithms of Data Structures & Algorithms II
Answer» CORRECT CHOICE is (a) Optimal page replacement ALGORITHM Easiest EXPLANATION - Optimal page replacement algorithm has the lowest FAULT rate as it has the knowledge of all the pages beforehand.

Discussion

Explore topic-wise InterviewSolutions in .

What is the competitive analysis of the FIFO algorithm?(a) k/k+1(b) k+1(c) k(k+1)(d) k/(k-h+1)The question was posed to me in a job interview.This is a very interesting question from Page Replacement Algorithms in portion Page Replacement Algorithms of Data Structures & Algorithms II

FIFO algorithm is used by __________ operating system.(a) Linux(b) Mac(c) Windows(d) VAX/VMSThis question was addressed to me in final exam.Enquiry is from Page Replacement Algorithms in portion Page Replacement Algorithms of Data Structures & Algorithms II

The cost required to execute a FIFO algorithm is expensive.(a) True(b) FalseI have been asked this question during an online exam.Asked question is from Page Replacement Algorithms in section Page Replacement Algorithms of Data Structures & Algorithms II

As the number of frames available increases, the number of page faults decreases.(a) True(b) FalseThis question was addressed to me in quiz.This key question is from Page Replacement Algorithms in section Page Replacement Algorithms of Data Structures & Algorithms II