GATE 2006 IT Questions and Solutions

# Recent questions tagged gate2006-it

1 vote
2 answers
1
Let M be a context-free language and L a regular language. Then the language L ∩ M is then what happen ???
48 votes
9 answers
2
Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are did and cid respectively and the records are stored in ascending order of these primary keys as given in the tables. No indexing is available in the database. ... using primary key, then $n$ lies in the range: $36 - 40$ $44 - 48$ $60 - 64$ $100 - 104$
16 votes
4 answers
3
Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are did and cid respectively and the records are stored in ascending order of these primary keys as given in the tables. No indexing is available in the database ... R.cid = C.cid and C.colour = 'green' ) Karthikeyan, Boris Sachin, Salman Karthikeyan, Boris, Sachin Schumacher, Senna
2 votes
2 answers
4
A software project has four phases P1, P2, P3 and P4. Of these phases, P1 Is the first one and needs to be completed before any other phase can commence. Phases P2 and P3 can be executed in parallel. Phase P4 cannot commence until both P2 and P3 are completed. ... that can be spent on crashing so that ALL paths are critical are, respectively. 100 and 1000 100 and 1200 150 and 1200 200 and 2000
2 votes
2 answers
5
A software project has four phases P1, P2, P3 and P4. Of these phases, P1 Is the first one and needs to be completed before any other phase can commence. Phases P2 and P3 can be executed in parallel. Phase P4 cannot commence until both P2 and P3 are completed. The optimistic, most likely, ... and the slack of P2 are, respectively, P1-P2-P4, 1 day P1-P3-P4, 1 day P1-P3-P4, 2 days P1-P2-P4, 2 days
33 votes
4 answers
6
Let $L$ be a regular language. Consider the constructions on $L$ below: $\text{repeat} (L) = \{ww \mid w \in L\}$ $\text{prefix} (L) = \{u \mid \exists v : uv \in L\}$ $\text{suffix} (L) = \{v \mid \exists u: uv \in L\}$ ... of $L$ is best suited to support your answer above? $(a + b)^*$ $\{\epsilon, a, ab, bab\}$ $(ab)^*$ $\{a^nb^n \mid n \geq 0\}$
20 votes
2 answers
7
Let $L$ be a regular language. Consider the constructions on $L$ below: repeat $(L) = \{ww \mid w \in L\}$ prefix $(L) = \{u \mid ∃v : uv \in L\}$ suffix $(L) = \{v \mid ∃u : uv \in L\}$ half $(L) = \{u \mid ∃v : | v | = | u | \text{ and } uv \in L\}$ Which of the constructions could lead to a non-regular language? Both I and IV Only I Only IV Both II and III
36 votes
4 answers
8
A pipelined processor uses a 4-stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The ... ID stage is used. The number of clock cycles required to complete the sequence of instructions is $10$ $12$ $14$ $16$
40 votes
2 answers
9
A pipelined processor uses a $4-$stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well as the load and store operations are carried out in the EX stage. The sequence of instructions ... the sequence of instructions are, respectively, $2, 2, 4$ $3, 2, 3$ $4, 2, 2$ $3, 3, 2$
0 votes
1 answer
10
$x + y/2 = 9$ $3x + y = 10$ What can be said about the Gauss-Siedel iterative method for solving the above set of linear equations? it will converge It will diverse It will neither converge nor diverse It is not applicable
0 votes
1 answer
11
x + y/2 = 9 3x + y = 10 The value of the Frobenius norm for the above system of equations is $0.5$ $0.75$ $1.5$ $2.0$
0 votes
2 answers
12
void swap(float* A1, float* A2) { float temp; if (*A1 = = *A2) return; temp = *A1; *A1 = *A2; *A2 = temp; return; } The program effort for the above module using Halstead's method is 315 330 393 403
0 votes
1 answer
13
void swap(float* A1, float* A2) { float temp; if (*A1 = = *A2) return; temp = *A1; *A1 = *A2; *A2 = temp; return; } The program volume for the above module using Halstead's method is 60 63 66 69
33 votes
3 answers
14
An array $X$ of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If the root node is at level $0$, the level of element $X[i]$, $i \neq 0$, is $\left \lfloor \log _2 i \right \rfloor$ $\left \lceil \log _2 (i+1)\right \rceil$ $\left \lfloor \log _2 (i+1) \right \rfloor$ $\left \lceil \log _2 i \right \rceil$
24 votes
3 answers
15
An array $X$ of $n$ distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of $O (n)$ $O (\log n)$ $O (n \log n)$ $O (n \log \log n)$
29 votes
5 answers
16
An array $X$ of $n$ distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. The index of the parent of element $X[i], i \neq 0$, is? $\left \lfloor \dfrac i 2 \right \rfloor$ $\left \lceil \dfrac{i-1}{2} \right \rceil$ $\left \lceil \dfrac i 2 \right \rceil$ $\left \lceil \dfrac i 2 \right \rceil - 1$
30 votes
2 answers
17
A subnetted Class $B$ network has the following broadcast address: $144.16.95.255$ Its subnet mask is necessarily $255.255.224.0$ is necessarily $255.255.240.0$ is necessarily $255.255.248.0$ could be any one of $255.255.224.0$, $255.255.240.0$,$255.255.248.0$
35 votes
10 answers
18
A program on machine $X$ attempts to open a $UDP$ connection to port $5376$ on a machine $Y$, and a $TCP$ connection to port $8632$ on machine $Z$. However, there are no applications listening at the corresponding ports on $Y$ and $Z$. An $ICMP$ Port Unreachable error will be generated by $Y$ but not $Z$ $Z$ but not $Y$ Neither $Y$ nor $Z$ Both $Y$ and $Z$
28 votes
8 answers
19
On a wireless link, the probability of packet error is $0.2$. A stop-and-wait protocol is used to transfer data across the link. The channel condition is assumed to be independent of transmission to transmission. What is the average number of transmission attempts required to transfer $100$ packets? $100$ $125$ $150$ $200$
37 votes
2 answers
20
A link of capacity $100$ $\text{Mbps}$ is carrying traffic from a number of sources. Each source generates an on-off traffic stream; when the source is on, the rate of traffic is $10$ $\text{Mbps}$, and when the source is off, the rate of traffic is zero. The duty cycle, which is the ratio of ... , $10$ $\text{and}$ $30$ $12$ $\text{and}$ $25$ $5$ $\text{and}$ $33$ $15$ $\text{and}$ $22$
57 votes
7 answers
21
A router has two full-duplex Ethernet interfaces each operating at $100$ $\text{Mb/s}$. Ethernet frames are at least $84$ $\text{bytes}$ long (including the Preamble and the Inter-Packet-Gap). The maximum packet processing time at the router for wirespeed forwarding to be possible is (in micro­seconds) $0.01$ $3.36$ $6.72$ $8$
28 votes
6 answers
22
In the $4B/5B$ encoding scheme, every $4$ bits of data are encoded in a $5$-bit codeword. It is required that the codewords have at most $1$ leading and at most $1$ trailing zero. How many are such codewords possible? $14$ $16$ $18$ $20$
48 votes
5 answers
23
Suppose that it takes $1$ unit of time to transmit a packet (of fixed size) on a communication link. The link layer uses a window flow control protocol with a window size of $N$ packets. Each packet causes an ack or a nak to be generated by the receiver, and ack/nak transmission times are negligible. Further, ... is $1- \dfrac{ N}{i}$ $\dfrac{i}{(N + i)}$ $1$ $1 - e^{\left(\frac{i}{N}\right)}$
23 votes
5 answers
24
A router uses the following routing table: \begin{array}{|l|l|l|} \hline \textbf {Destination} & \textbf { Mask} & \textbf{Interface} \\\hline \text {144.16.0.0} & \text{255.255.0.0} & \text{eth$0$} \\\hline\text {144.16.64.0} & \text{255.255.224.0} ... } Packet bearing a destination address $144.16.68.117$ arrives at the router. On which interface will it be forwarded? eth$0$ eth$1$ eth$2$ eth$3$
0 votes
0 answers
25
Consider the following XML DTD describing course information in a university: <!ELEMENT Univ (Course+, Prof+)> <!ELEMENT Course (Title, Eval*)> <!ATTLIST Course Number ID #REQUIRED Instructor IDREF #IMPLIED> <!ELEMENT Title (#PCDATA)> <! ... all their course evaluations above the university average The course with the lowest evaluation Courses with all evaluations above the university average
24 votes
3 answers
26
In a database file structure, the search key field is $9$ $bytes$ long, the block size is $512$ $bytes$, a record pointer is $7$ $bytes$ and a block pointer is $6$ $bytes$. The largest possible order of a non-leaf node in a$B+$ tree implementing this file structure is $23$ $24$ $34$ $44$
17 votes
4 answers
27
Consider a relation R with five attributes $V, W, X, Y,$ and $Z.$ The following functional dependencies hold: $VY→ W, WX → Z,$ and $ZY → V.$ Which of the following is a candidate key for $R?$ $VXZ$ $VXY$ $VWXY$ $VWXYZ$
0 votes
1 answer
28
Consider the following structure chart diagram. The boxes have function names embedded in them, while the variables are indicated along the arcs. Given below are a set of statements relevant to the above diagram. F3 and F6 can be in the same module. F4 and F6 can be in the same ... it as a control variable. Which combination of these statements is TRUE? III and IV I and IV II and IV I, II and IV
3 votes
2 answers
29
A software program consists of two modules M1 and M2 that can fail independently, but never simultaneously. The program is considered to have failed if any of these modules fails. Both the modules are 'repairable' and so the program starts working again as soon as the repair is done. Assume that the ... + T2R2)) ((R1R2)/(T1R1 + T2R2)) ((T1T2)/(T1T2 + T1R1 + T2R2)) ((T1T2)/(T1T2 + T1R2 + T2R1))
19 votes
3 answers
30
The wait and signal operations of a monitor are implemented using semaphores as follows. In the following, $x$ is a condition variable, mutex is a semaphore initialized to $1$, $x$_sem is a semaphore initialized to $0$, $x$_count is the number of processes waiting on semaphore $x$_sem, initially $0$, next is ... $P(x\_sem), V(next)$ $V(next), P(x\_sem)$ $P(next), V(x\_sem)$ $P(x\_sem), V(x\_sem)$