Bharati Padhy, $\text{Gate}\; 2020, \text{GS-}624, \text{AIR-}1531, \text{Jest}\; (2020)\; \text{AIR-}75$
Some memory based questions:
1. $R_{1}$ and $R_{2}$ are equivalence relation then which of the following is true?
- $R_{1} \cup R_{2}$ is equivalence
- $R_{1} \cap R_{2}$ is not equivalence
- $R_{1} \cap R_{2}$ is not transitive
- None of the above
2. $C(n,k)$ means choosing $k$ numbers from $n$ numbers. Write the recurrence relation for this:
- $C(n,k) = C(n-1,k-1) + C(n-1,k)$
- $C(n,k) = C(n-1,k-1) + C(n-1,k)$
- $C(n,k) = C(n-1.k) + C(n,k-1)$
- $C(n,k) = C(n,k-1) + C(n-1,k)$
3. $N\times N$ grid which has $n^2$ cells, you have to travel from bottom left corner to the top right corner. You can take only up and right path. How many such path possible?
- $(2n)!/n! n!$
- $n^2$
- $C(2n,n)$
- $n(n-1)/2$
4. There are n guests in a party. Each and every person in the party will handshake with each other exactly once. How many distinct handshakes possible. Recurrence relation?
- $T(n) = T(n-1) +1$
- $T(n) = 2T(n-1)$
- $T(n) = T(n-1) + T(n-2)$
- $T(n) = T(n-1) + n-1$
5. Number of relations which are reflexive and symmetric both.
- $2^C(n,2)$
- $2^P(n,2)$
- $2^((n^2+n)/2)$
- $2^n$
6.
while(1) {
int *I = (int *) malloc (sizeof(int));
}
printf(“Hello world”);
- Hello world
- Segmentation fault
- Infinite loop
- Stack overflow
7. There is a polynomial time function which calls constant times some other functions which also take polynomial time what is the total complexity?
- Polynomial
- Exponential
- Super exponential
- None
8. NP problem is best known as
- It is decidable in polynomial time
- It is verifiable in polynomial time
- It have an algorithm of exponential time
- It does not have any algorithm
9. There is a polynomial with highest degree $2.$
$\begin{array}{c c c c c} X & 1 & 2 & 3 & 4 \\ F(X) & 3 & ? & 13 & 21 \end{array}$
Find value of $f(2)$
- ____
- $25/3$
- ____
- None
10. Find the remainder of $7^{222} \mod 11$
- $7$
- $5$
- $2$
- $0$
11. What is the size of page table if CPU generates $32$ bit address, page size is $4$ KB and PTE size is $4$ Byte.
- $8$ MB
- $2$ MB
- $4$ MB
- ____
12. You have $m$ resources $,n$ process competing for them each having $j$ number of resources requirement(consider all $m,n$ and $j$ are positive). Find the proper inequality which MUST ensure freedom from deadlock
- $M=n+j+1$
- $(m-1)>= n(j-1)$
- ____
- ____
13. Which of the following is/are true
- $\text{L1}$ cache is generally faster than $\text{L2}$ cache
- $\text{L1}$ cache is generally smaller than $\text{L2}$ cache
- $\text{L2}$ is generally faster than middleware
- RAM is faster than $\text{L1}$ cache
14.Which of the following is/are false
- Preemptive schedule means longer delay for the shorter processes.
- Round robin scheduling follows FIFO
- In SJF we need prior knowledge of process running time
- SRTF is a non-preemptive version of SJF
15.Which of the following is/are true
- There is no polynomial time algorithm to find the graph is Euler is not
- There is a polynomial time algorithm to find the graph is Hamiltonian
- Dijsktra’s all pair shortest path algorithm will not work properly when there is a negative edge.
- None of the above
