GATE Computer Science 2007 questions and solutions

# Recent questions tagged gate2007

1
1 vote
2
Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of variables. What is the minimum size of the multiplexer needed? A.2^n line to 1 line B.2^(n+1) line to 1 line C.2^(n-1) line to 1 line D.2^(n-2) line to 1 line
3
Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is: $\lceil \log_2n \rceil +1$ $n$ $\lceil \log_2n \rceil$ $\lfloor \log_2n \rfloor +1$
4
Consider the following program segment. Here $\text{R1, R2}$ and $\text{R3}$ ... interrupt occurs during the execution of the instruction INC R3 , what return address will be pushed on to the stack? $1005$ $1020$ $1024$ $1040$
5
Consider the following program segment. Here $\text{R1, R2}$ and $\text{R3}$ ... Assume that the memory is word addressable. After the execution of this program, the content of memory location $2010$ is: $100$ $101$ $102$ $110$
6
Consider the following Finite State Automaton: The minimum state automaton equivalent to the above FSA has the following number of states: $1$ $2$ $3$ $4$
7
Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\dfrac{1}{2}, \dfrac{1}{4}, \dfrac{1}{8}, \dfrac{1}{16}, \dfrac{1}{32}, \dfrac{1}{32}$, respectively. What is the average length of the Huffman code for the letters $a, \,b, \,c, \,d, \,e, \,f$? $3$ $2.1875$ $2.25$ $1.9375$
8
Consider the CFG with $\left\{S, A, B\right\}$ as the non-terminal alphabet, $\{a, b\}$ as the terminal alphabet, $S$ as the start symbol and the following set of production rules: $S \rightarrow aB$ $S \rightarrow bA$ $B \rightarrow b$ $A \rightarrow a$ ... $B \rightarrow aBB$ $S \rightarrow bAA$ For the string $aabbab$, how many derivation trees are there? $1$ $2$ $3$ $4$
9
Consider a machine with a byte addressable main memory of $2^{16}$ bytes. Assume that a direct mapped data cache consisting of $32$ lines of $64$ bytes each is used in the system. A $50$ x $50$ two-dimensional array of bytes is stored in the main memory starting from memory location $1100H$. ... the second time? line $4$ to line $11$ line $4$ to line $12$ line $0$ to line $7$ line $0$ to line $8$
10
A process, has been allocated $3$ page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): $1, 2, 1, 3, 7, 4, 5, 6, 3, 1$ Least Recently Used ... the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy? $0$ $1$ $2$ $3$
11
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $(i,j)$ then it can move to either $(i + 1, j)$ or $(i,j + 1)$ ... $^{20}\mathrm{C}_{10} - ^{8}\mathrm{C}_{4}\times ^{11}\mathrm{C}_{5}$
12
Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below. Which of the following is not a topological ordering? $1$ $2$ $3$ $4$ $5$ $6$ $1$ $3$ $2$ $4$ $5$ $6$ $1$ $3$ $2$ $4$ $6$ $5$ $3$ $2$ $4$ $1$ $6$ $5$
13
Information about a collection of students is given by the relation $\text{studInfo(}\underline{\text{studId}},\text{ name, sex)}$. The relation $\text{enroll(}{\text{studId}},{\text{ courseId}})$ gives which student has enrolled for (or taken) what ... enrolled. Courses in which a proper subset of female students are enrolled. Courses in which only male students are enrolled. None of the above
14
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $(i,j)$ then it can move to either $(i + 1, j)$ or $(i,j + 1)$. How many distinct paths are there for the robot to reach the point $(10,10)$ starting from the initial position $(0,0)$? $^{20}\mathrm{C}_{10}$ $2^{20}$ $2^{10}$ None of the above
15
A process has been allocated $3$ page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): $\mathbf{1, 2, 1, 3, 7, 4, 5, 6, 3, 1}$ If optimal page replacement policy is used, how many page faults occur for the above reference string? $7$ $8$ $9$ $10$
16
Consider a machine with a byte addressable main memory of $2^{16}$ bytes. Assume that a direct mapped data cache consisting of $32$ lines of $64$ $bytes$ each is used in the system. A $50$ x $50$ two-dimensional array of bytes is stored in the main memory starting from ... of the data cache do not change in between the two accesses. How many data misses will occur in total? $48$ $50$ $56$ $59$
17
Consider the CFG with $\left\{S, A, B\right\}$ as the non-terminal alphabet, $\{a, b\}$ as the terminal alphabet, $S$ as the start symbol and the following set of production rules: $S \rightarrow aB$ $S \rightarrow bA$ $B \rightarrow b$ ... $B \rightarrow aBB$ $S \rightarrow bAA$ Which of the following strings is generated by the grammar? $aaaabb$ $aabbbb$ $aabbab$ $abbbba$
18
Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \frac{1}{32}$, respectively. Which of the following is the Huffman code for the letter $a, \,b, \,c, \,d, \,e, \,f$? $0$, $10$, $110$ ... $11$, $10$, $011$, $010$, $001$, $000$ $11$, $10$, $01$, $001$, $0001$, $0000$ $110$, $100$, $010$, $000$, $001$, $111$
19
Consider the following Finite State Automaton: The language accepted by this automaton is given by the regular expression $b^*ab^*ab^*ab^*$ $(a + b)^*$ $b^*a(a+b)^*$ $b^*ab^*ab^*$
20
Consider the following program segment. Here $\text{R1, R2}$ and $\text{R3}$ ... that the memory is word addressable. The number of memory references for accessing the data in executing the program completely is $10$ $11$ $20$ $21$
21
Match the following: ... $\text{P - 1, Q - 4, R - 2, S - 5}$ $\text{P - 2, Q - 4, R - 1, S - 3}$
22
The distance between two stations $M$ and $N$ is $L$ kilometers. All frames are $K$ bits long. The propagation delay per kilometer is $t$ seconds. Let $R$ bits/second be the channel capacity. Assuming that the processing delay is negligible, the $\text{minimum}$ number of bits for the ... $\lceil \log_2 \frac{2LtR +K}{K} \rceil$ $\lceil \log_2 \frac{2LtR +2K}{2K} \rceil$
23
The message $11001001$ is to be transmitted using the CRC polynomial $x^3 +1$ to protect it from errors. The message that should be transmitted is: $11001001000$ $11001001011$ $11001010$ $110010010011$
24
The address of a class $B$ host is to be split into subnets with a $6$-$bit$ subnet number. What is the maximum number of subnets and the maximum number of hosts in each subnet? $62$ subnets and $262142$ hosts. $64$ subnets and $262142$ hosts. $62$ subnets and $1022$ hosts. $64$ subnets and $1024$ hosts.
25
In a token ring network the transmission speed is 10$^7$ bps and the propagation speed is 200 meters/$\mu$s. The 1-bit delay in this network is equivalent to: 500 meters of cable. 200 meters of cable. 20 meters of cable. 50 meters of cable.
26
There are $n$ stations in slotted LAN. Each station attempts to transmit with a probability $p$ in each time slot. What is the probability that ONLY one station transmits in a given time slot? $np(1-p)^{n-1}$ $(1-p)^{n-1}$ $p(1-p)^{n-1}$ $1-(1-p)^{n-1}$
27
Consider the following schedules involving two transactions. Which one of the following statements is TRUE? $S_1 :r_1(X); r_1(Y); r_2(X); r_2(Y); w_2(Y); w_1(X)$ $S_2 :r_1(X); r_2(X); r_2(Y); w_2(Y); r_1(Y); w_1(X)$ Both $S_1$ ... and $S_2$ is not conflict serializable. $S_1$ is not conflict serializable and $S_2$ is conflict serializable. Both $S_1$ and $S_2$ are not conflict serializable.
The order of a leaf node in a B$^+$ - tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is $1K$ $bytes$, data record pointer is $7$ $bytes$ long, the value field is $9$ $bytes$ long and a block pointer is $6$ $bytes$ long, what is the order of the leaf node? $63$ $64$ $67$ $68$
Which one of the following statements is $\text{FALSE}$? Any relation with two attributes is in $\text{BCNF}$ A relation in which every key has only one attribute is in $2NF$ A prime attribute can be transitively dependent on a key in a $3NF$ relation A prime attribute can be transitively dependent on a key in a $\text{BCNF}$ relation
Consider the table employee(empId, name, department, salary) and the two queries $Q_1, \, Q_2$ below. Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary than anyone in the department 5, which one of the statements ... $Q_2$ is the correct query Both $Q_1$ and $Q_2$ produce the same answer Neither $Q_1$ nor $Q_2$ is the correct query