search
Log In
GATE Computer Science 2007 questions and solutions

Recent questions tagged gate2007

0 votes
4 answers
1
1 vote
0 answers
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
asked Dec 17, 2016 in Digital Logic aditya kuppa 1 272 views
40 votes
15 answers
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$
asked Jul 6, 2016 in Algorithms Arjun 12.3k views
25 votes
3 answers
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$
asked Apr 23, 2016 in CO and Architecture jothee 4.1k views
27 votes
5 answers
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$
asked Apr 23, 2016 in CO and Architecture jothee 3.4k views
19 votes
3 answers
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$
asked Apr 23, 2016 in Theory of Computation jothee 1.9k views
24 votes
3 answers
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$
asked Apr 23, 2016 in Algorithms jothee 2.9k views
18 votes
2 answers
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$
asked Apr 23, 2016 in Compiler Design jothee 1.9k views
27 votes
4 answers
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$
asked Apr 23, 2016 in CO and Architecture jothee 3.5k views
15 votes
4 answers
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$
asked Apr 23, 2016 in Operating System jothee 2.4k views
26 votes
4 answers
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}$
asked Apr 23, 2016 in Combinatory jothee 2.8k views
20 votes
5 answers
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$
asked Dec 21, 2015 in Algorithms pC 2.5k views
62 votes
11 answers
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
asked Oct 4, 2014 in Databases Aravind 7.2k views
31 votes
6 answers
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
asked Sep 22, 2014 in Combinatory Kathleen 4.5k views
15 votes
5 answers
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$
asked Sep 22, 2014 in Operating System Kathleen 3.2k views
60 votes
10 answers
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$
asked Sep 22, 2014 in CO and Architecture Kathleen 11.6k views
19 votes
2 answers
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$
asked Sep 22, 2014 in Compiler Design Kathleen 3.6k views
21 votes
1 answer
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$
asked Sep 22, 2014 in Algorithms Kathleen 3.9k views
27 votes
6 answers
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^*$
asked Sep 22, 2014 in Theory of Computation Kathleen 3.6k views
39 votes
4 answers
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$
asked Sep 22, 2014 in CO and Architecture Kathleen 8.5k views
19 votes
4 answers
21
Match the following: ... $\text{P - 1, Q - 4, R - 2, S - 5}$ $\text{P - 2, Q - 4, R - 1, S - 3}$
asked Sep 22, 2014 in Computer Networks Kathleen 4.2k views
36 votes
8 answers
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$
asked Sep 22, 2014 in Computer Networks Kathleen 7.1k views
20 votes
4 answers
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$
asked Sep 22, 2014 in Computer Networks Kathleen 9.4k views
39 votes
13 answers
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.
asked Sep 22, 2014 in Computer Networks Kathleen 13.9k views
8 votes
2 answers
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.
asked Sep 22, 2014 in Computer Networks Kathleen 6.2k views
22 votes
3 answers
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}$
asked Sep 22, 2014 in Computer Networks Kathleen 4.6k views
19 votes
6 answers
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.
asked Sep 22, 2014 in Databases Kathleen 2.9k views
32 votes
6 answers
28
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$
asked Sep 22, 2014 in Databases Kathleen 11k views
47 votes
5 answers
29
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
asked Sep 22, 2014 in Databases Kathleen 7.3k views
49 votes
4 answers
30
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
asked Sep 22, 2014 in Databases Kathleen 9.1k views
...