Options:
1. Graph A only
2. Graph B only
3. Both the graphs
4. None of the two graphs
Solution: Graph A can be redrawn like this:
Hence it can be seen Graph A is planar. But Graph B isn’t planar. In fact this is complete graph on 5 vertices, called K5 and it is the graph with minimum number of vertices which isn’t planar. All graphs with less number of vertices are planar. Correct option is 1.
Question 84: What will be the output of the following program:
if ( fork() )
{ printf(“Parent Process\n”);
wait(NULL);
printf(“Waited for child\n”);
}
else
{ printf(“Child Process\n”);
}
1. Parent Process
Child Process
Waited for child
2. Child Process
Parent Process
Waited for child
3. Parent Process
Waited for child
Child Process
4. Both A and B are possible
Solution: Since both parent and child process can execute first depending on the scheduling policy, it is indeterminate. The only thing is that child process has to be killed before parent can go ahead of wait(). The correct answer is option 4.
Question 83: Context switches among processes are expensive. Before a process can be switched its process control block (PCB) must be saved by the operating system. Which of the following is not part of PCB?
Options:
Solution: Each of the options depict something that is process specific. But notice that kernel level threads are managed by kernel, and the user process is not responsible for these. Hence this information is not needed to be saved by the process. Hence the correct option is the fourth one.
Question 83: What is the CFG for {a^i b^j | i <= 2j }?
X -> aXb | aaXb | ∈
2. S -> aaXb | aXb | Xb
X -> aXb | aaXb | ∈ | Xb
3. S -> aaXb | aXb
X -> aXb | aaXb | ∈ | Xb
4. S -> aaXb | Xb
X -> aaXb | ∈ | Xb
Solution: Grammar from option 1 & 3 can’t produce string ‘bb’ which is valid. Grammar from option D can’t produce string ‘ab’ which is valid.The correct answer is option 2.
This is in continuation with Question 79
Question 81: If there are total 4 page frames in the system, how many page faults will be there?
Solution: Following will be the sequence of pages in memory, pages in red will be the ones which will be replaced.
| Newest Page | 3 | 2 | 1 | 0 | 0 | 0 | 4 | 3 | 2 | 1 | 0 | 4 |
| 3 | 2 | 1 | 1 | 1 | 0 | 4 | 3 | 2 | 1 | 0 | ||
| 3 | 2 | 2 | 2 | 1 | 0 | 4 | 3 | 2 | 1 | |||
| Oldest Page | 3 | 3 | 3 | 2 | 1 | 0 | 4 | 3 | 2 |
This is an example of Belady’s anomaly, that is, increasing number of page frames results in increase in the number of page faults. Hence, the correct answer is option 4.
Question #80: Consider a (2n) x (2n) maze. A mouse is present at cell(0,0) and some cheese is present at cell(n,n). The mouse is only allowed to move right & up, and cannot move left or down from any cell. In how many different ways can the mouse reach the cheese?
Options:
1. P (2n, n)
2. C (2n, n)
3. n*n
4. 2n
Solution: To reach the cheese, mouse has to take exactly ‘n’ steps right & ‘n’ steps up. But these can be taken in any order, so the solution is a permutation of ‘2n‘ steps. The possible permutations can be written as:
(2n)! / (n! * n!) => C (2n, n)
So, the correct option is 2nd one.
Using FIFO page replacement policy, assume that the page request follows the following order:
3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
Question 79: If there are total 3 page frames in the system, how many page faults will be there?
Solution: Following will be the sequence of pages in memory, pages in red will be the ones which will be replaced.
| Newest Page | 3 | 2 | 1 | 0 | 3 | 2 | 4 | 4 | 4 | 1 | 0 | 0 |
| 3 | 2 | 1 | 0 | 3 | 2 | 2 | 2 | 4 | 1 | 1 | ||
| Oldest Page | 3 | 2 | 1 | 0 | 3 | 3 | 3 | 2 | 4 | 4 |
Hence, the correct answer is option 3.
Question 78: Kernel also requires memory for storing its code and various other segments, processes specific data etc. How should this kernel memory be implemented?
Solution: Kernel pages perform critical functions and shouldn’t be swapped out. Example, page fault handler is part of kernel, if the code for it is not itself present in memory and a page fault occurs for some user process then there is no way to deal with it. Hence, the correct answer is option 3.
The following push down automata accepts equal number of a’s and b’s. In the left are the transitions shown and in the right, the equivalent automaton is designed.
Question 78: What will be the stack contents after seeing string abbabbaabbab? (from top to bottom)
Solution:
The number of b’s are two more than number of a’s. The correct answer is option 1
Question 76: Remove null production from the following grammar:
Options:
1. S -> AB | A | B
A -> aAA | a
B -> bBB | b
2. S -> AB
A -> aAA | aA | a
B -> bBB | bB | b
3. S -> AB | A | B
A -> aAA | aA | a
B -> bBB | bB | b
4. S -> AB | A | B
A -> aA | a
B -> bB | b
Solution: In option 1, the productions of A don’t have aA. In option 2, the productions of S don’t have A and B alone. In option 4, the productions of A don’t have aAA. The correct answer is option 3.
Bytes of the day 