search
Log In
GATE 2009 Computer Science & Information Technology Question Paper with Solution

Recent questions tagged gate2009

2 votes
0 answers
1
Consider this question and its selected answer: https://gateoverflow.in/3690/gate2004-it-47 And this question: https://gateoverflow.in/1314/gate2009-28 Both questions are somewhat similar. In the first one's answer, instruction $I_1$ (when i = 2), the $S_2$ stage is ... there any point that I am missing? PS. From where can I study this? Hamacher book doesn't contain pipelining in this much detail.
asked Nov 4, 2017 in CO and Architecture Rishabh Gupta 2 643 views
29 votes
3 answers
2
A hard disk has $63$ sectors per track, $10$ platters each with $2$ recording surfaces and $1000$ cylinders. The address of a sector is given as a triple $\langle c, h, s \rangle$, where $c$ is the cylinder number, $h$ is the surface number and $s$ is the sector number. Thus, the ... is $\langle 0, 15, 31 \rangle$ $\langle 0, 16, 30 \rangle$ $\langle 0, 16, 31 \rangle$ $\langle 0, 17, 31 \rangle$
asked Apr 23, 2016 in Operating System jothee 4.5k views
39 votes
3 answers
3
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest common ... major order of $L[M, N]$. $L[p, q]$ needs to be computed before $L[r, s]$ if either $p<r$ or $q < s$.
asked Apr 23, 2016 in Algorithms jothee 5.6k views
43 votes
6 answers
4
Consider the following relational schema: $\text{Suppliers}(\underline{\text{sid:integer}},\text{ sname:string, city:string, street:string})$ $\text{Parts}(\underline{\text{pid:integer}}, \text{ pname:string, color:string})$ ... is in $3NF$ but not in $\text{BCNF}$ The schema is in $2NF$ but not in $3NF$ The schema is not in $2NF$
asked Apr 23, 2016 in Databases jothee 11.2k views
59 votes
6 answers
5
Frames of $1000\text{ bits}$ are sent over a $10^6$ bps duplex link between two hosts. The propagation time is $25ms$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). Let $I$ be the minimum number of ... wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time) $16ms$ $18ms$ $20ms$ $22ms$
asked Apr 23, 2016 in Computer Networks jothee 14.3k views
18 votes
4 answers
6
Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on $\left\{25,14,16,13,10,8,12\right\}$ $\left\{14,13,12,10, 8\right\}$ $\left\{14,12,13,8,10\right\}$ $\left\{14,13,8,12,10\right\}$ $\left\{14,13,12,8,10\right\}$
asked Apr 23, 2016 in DS jothee 2.6k views
16 votes
3 answers
7
Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap? $\left\{25,12,16,13,10,8,14\right\}$ $\left\{25,14,13,16,10,8,12\right\}$ $\left\{25,14,16,13,10,8,12\right\}$ $\left\{25,14,12,13,10,8,16\right\}$
asked Sep 22, 2014 in DS Kathleen 2.6k views
81 votes
16 answers
8
Frames of $\text{1000 bits}$ are sent over a $10^6$ $\text{bps}$ duplex link between two hosts. The propagation time is $\text{25 ms}$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). What is the minimum number of bits ... numbers distinctly? Assume that no time gap needs to be given between transmission of two frames. $I=2$ $I=3$ $I=4$ $I=5$
asked Sep 22, 2014 in Computer Networks Kathleen 23.3k views
50 votes
5 answers
9
Consider the following relational schema: $\text{Suppliers}(\underline{\text{sid:integer}},\text{ sname:string, city:string, street:string})$ $\text{Parts}(\underline{\text{pid:integer}}, \text{ pname:string, color:string})$ ... the names of all suppliers who have supplied only non-blue part. Find the names of all suppliers who have not supplied only blue parts.
asked Sep 22, 2014 in Databases Kathleen 14.2k views
28 votes
3 answers
10
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest ... $\text{expr2} = \max\left(l\left(i-1, j-1\right), l\left(i,j\right)\right)$
asked Sep 22, 2014 in Algorithms Kathleen 3.6k views
41 votes
4 answers
11
A hard disk has $63$ sectors per track, $10$ platters each with $2$ recording surfaces and $1000$ cylinders. The address of a sector is given as a triple $\langle c, h, s \rangle$, where $c$ is the cylinder number, $h$ is the surface number and $s$ is the sector ... $\langle 400, 16, 29 \rangle$ corresponds to sector number: $505035$ $505036$ $505037$ $505038$
asked Sep 22, 2014 in Operating System Kathleen 8.7k views
5 votes
1 answer
12
Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE? The cyclomatic complexity of a module is equal to the maximum number of linearly independent circuits in the graph. The cyclomatic complexity of ... paths that should be tested during path coverage testing. I and II II and III I and III I, II and III
asked Sep 22, 2014 in IS&Software Engineering Kathleen 1.6k views
10 votes
2 answers
13
Which of the following statements are TRUE? The context diagram should depict the system as a single bubble. External entities should be identified clearly at all levels of DFDs. Control information should not be represented in a DFD. A data store can be connected wither to another data store or to an external entity. II and III II and III I and III I, II and III
asked Sep 22, 2014 in IS&Software Engineering Kathleen 2.3k views
40 votes
6 answers
14
Let $G(x)$ be the generator polynomial used for CRC checking. What is the condition that should be satisfied by $G(x)$ to detect odd number of bits in error? $G(x)$ contains more than two terms $G(x)$ does not divide $1+x^k$, for any $k$ not exceeding the frame length $1+x$ is a factor of $G(x)$ $G(x)$ has an odd number of terms.
asked Sep 22, 2014 in Computer Networks Kathleen 12.9k views
64 votes
6 answers
15
While opening a $TCP$ connection, the initial sequence number is to be derived using a time-of-day (ToD) clock that keeps running even when the host is down. The low order $32$ bits of the counter of the ToD clock is to be used for the initial sequence numbers. The clock counter ... at which sequence numbers used for packets of a connection can increase? $0.015$/s $0.064$/s $0.135$/s $0.327$/s
asked Sep 22, 2014 in Computer Networks Kathleen 12.2k views
21 votes
4 answers
16
In the RSA public key cryptosystem, the private and public keys are $(e, n)$ and $(d, n)$ respectively, where $n=p \times q$ and $p$ and $q$ are large primes. Besides, $n$ is public and $p$ and $q$ are private. Let $M$ be an integer such that $0<M<n$ ... Which of the above equations correctly represents RSA cryptosystem? I and II I and III II and IV III and IV
asked Sep 22, 2014 in Computer Networks Kathleen 3.7k views
65 votes
1 answer
17
Let $R$ and $S$ be relational schemes such that $R=\{a,b,c\}$ and $S=\{c\}.$ Now consider the following queries on the database: $\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$ ... Select R.a,R.b From R,S Where R.c = S.c Which of the above queries are equivalent? $1$ and $2$ $1$ and $3$ $2$ and $4$ $3$ and $4$
asked Sep 22, 2014 in Databases Kathleen 12.2k views
46 votes
10 answers
18
The following key values are inserted into a $B+$ - tree in which order of the internal nodes is $3$, and that of the leaf nodes is $2$, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is ... $2$, $1$ The maximum number of times leaf nodes would get split up as a result of these insertions is $2$ $3$ $4$ $5$
asked Sep 22, 2014 in Databases Kathleen 13k views
22 votes
2 answers
19
Consider two transactions $T_1$ and $T_2$, and four schedules $S_1, S_2, S_3, S_4$, of $T_1$ and $T_2$ as given below: $T_1: R_1[x]W_1[x]W_1[y]$ $T_2: R_2[x]R_2[y]W_2[y]$ $S_1: R_1[x]R_2[x]R_2[y] W_1[x] W_1[y] W_2[y]$ ... $S_1 \text{ and } S_2$ $S_2 \text{ and } S_3$ $S_3$ only $S_4$ only
asked Sep 22, 2014 in Databases Kathleen 2.8k views
34 votes
2 answers
20
Which of the following statements are TRUE? There exist parsing algorithms for some programming languages whose complexities are less than $\Theta(n^3)$ A programming language which allows recursion can be implemented with static storage allocation. No L-attributed definition can be ... performed at both source language and intermediate code level. I and II I and IV III and IV I, III and IV
asked Sep 22, 2014 in Compiler Design Kathleen 7.6k views
29 votes
8 answers
21
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$.
asked Sep 22, 2014 in Theory of Computation Kathleen 5.6k views
37 votes
7 answers
22
Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below: $L_1= \left \{ a^m b^mca^nb^n \mid m,n \geq 0 \right \}$ $L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$ Then $L$ is Not recursive Regular Context free but not regular Recursively enumerable but not context free.
asked Sep 22, 2014 in Theory of Computation Kathleen 5.2k views
35 votes
7 answers
23
In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time complexity of the quick sort? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$
asked Sep 22, 2014 in Algorithms Kathleen 8.3k views
18 votes
3 answers
24
Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm? $\text{(b, e) (e, f) (a, c) (b, c) (f, g) (c, d)}$ $\text{(b, e) (e, f) (a, c) (f, g) (b, c) (c, d)}$ $\text{(b, e) (a, c) (e, f) (b, c) (f, g) (c, d)}$ $\text{(b, e) (e, f) (b, c) (a, c) (f, g) (c, d)}$
asked Sep 22, 2014 in Algorithms Kathleen 2.8k views
26 votes
4 answers
25
What is the maximum height of any AVL-tree with $7$ nodes? Assume that the height of a tree with a single node is $0$. $2$ $3$ $4$ $5$
asked Sep 22, 2014 in DS Kathleen 13.7k views
24 votes
2 answers
26
The keys $12, 18, 13, 2, 3, 23, 5$ and $15$ are inserted into an initially empty hash table of length $10$ using open addressing with hash function $h(k) = k \mod 10$ ...
asked Sep 22, 2014 in DS Kathleen 2.4k views
21 votes
3 answers
27
The running time of an algorithm is represented by the following recurrence relation: $T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$ Which one of the following represents the time complexity of the algorithm? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$
asked Sep 22, 2014 in Algorithms Kathleen 4k views
28 votes
2 answers
28
A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because It reduces the memory access time to read or write a memory location. It helps to reduce the size of page table needed ... process It is required by the translation lookaside buffer. It helps to reduce the number of page faults in page replacement algorithms.
asked Sep 22, 2014 in Operating System Kathleen 6.5k views
37 votes
11 answers
29
The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows: void enter_CS(X) { while(test-and-set(X)); } void leave_CS(X) { X = 0; } In the above solution, $X$ is a memory location associated with the $CS$ ... $CS$ at the same time Which of the above statements are TRUE? (I) only (I) and (II) (II) and (III) (IV) only
asked Sep 22, 2014 in Operating System Kathleen 10.7k views
22 votes
3 answers
30
In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state: Now consider the following statements: If a process makes a transition $D$, it would result in another process making transition $A$ ... uses non-preemptive scheduling. Which of the above statements are TRUE? I and II I and III II and III II and IV
asked Sep 22, 2014 in Operating System Kathleen 5.3k views
...