GATE 2006 IT Questions and Solutions

# Recent questions tagged gate2006-it 1 vote
1
Let M be a context-free language and L a regular language. Then the language L ∩ M is then what happen ???
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$
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
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
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
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\}$
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
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$
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$
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
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$
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
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
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$
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)$
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$
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$
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$
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$
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$
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$
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$
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)}$
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$
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
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$
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$
1 vote
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)$