GATE IT 2005
Q1.
Traceroute reports a possible route that is taken by packets moving from some host A to some other host B. Which of the following options represents the technique used by traceroute to identify these hosts:Q2.
Consider the three commands : PROMPT, HEAD and RCPT. Which of the following options indicate a correct association of these commands with protocols where these are used?Q3.
An instruction set of a processor has 125 signals which can be divided into 5 groups of mutually exclusive signals as follows: Group 1 : 20 signals, Group 2 : 70 signals, Group 3 : 2 signals, Group 4 : 10 signals, Group 5 : 23 signals. How many bits of the control words can be saved by using vertical microprogramming over horizontal microprogramming?Q4.
A hardwired CPU uses 10 control signals S_1 to S_{10}, in various time steps T_1 to T_5, to implement 4 instructions I_1 to I_4 as shown below: \begin{array}{|c|c|c|c|c|c|}\hline&\bf{T_1}&\bf{T_2}&\bf{T_3}&\bf{T_4}&\bf{T_5}\\\hline\bf{I_1}&S_1,S_3,S_5&S_2,S_4,S_6&S_1,S_7&S_{10}&S_3,S_8\\\hline\bf{I_2}&S_1,S_3,S_5&S_8,S_9,S_{10}&S_5,S_6S_7&S_{6}&S_{10}\\\hline\bf{I_3}&S_1,S_3,S_5&S_7,S_8,S_{10}&S_2,S_6,S_{9}&S_{10}&S_1,S_3\\\hline\bf{I_4}&S_1,S_3,S_5&S_2,S_6,S_7&S_5,S_{10}&S_{6},S_9&S_{10}\\\hline\end{array} Which of the following pairs of expressions represent the circuit for generating control signals S_5 and S_{10} respectively? ((I_j + I_k)T_n indicates that the control signal should be generated in time step T_n if the instruction being executed is l_j or l_k)Q5.
Let a and b be two sorted arrays containing n integers each, in non-decreasing order. Let c be a sorted array containing 2n integers obtained by merging the two arrays a and b. Assuming the arrays are indexed starting from 0, consider the following four statements I. a[i] \geq b [i] \Rightarrow c[2i] \geq a [i] II. a[i] \geq b [i] \Rightarrow c[2i] \geq b [i] III. a[i] \geq b [i] \Rightarrow c[2i] \leq a [i] IV. a[i] \geq b [i] \Rightarrow c[2i] \leq b [i] Which of the following is TRUE?Q6.
Let a be an array containing n integers in increasing order. The following algorithm determines whether there are two distinct numbers in the array whose difference is a specified number S > 0. i = 0; j = 1; while (j < n ){ if (E) j++; else if (a[j] - a[i] == S) break; else i++; } if (j < n) printf("yes") else printf ("no"); Choose the correct expression for E.Q7.
The following C function takes two ASCII strings and determines whether one is an anagram of the other. An anagram of a string s is a string obtained by permuting the letters in s. int anagram (char *a, char *b) { int count [128], j; for (j = 0; j < 128; j++) count[j] = 0; j = 0; while (a[j] && b[j]) { A; B; } for (j = 0; j < 128; j++) if (count [j]) return 0; return 1; } Choose the correct alternative for statements A and B.Q8.
A binary search tree contains the numbers 1,2,3,4,5,6,7,8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5,3,1,2,4,6,8,7. If the tree is traversed in post-order, the sequence obtained would beQ9.
The numbers 1, 2, .\dots n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must beQ10.
A line L in a circuit is said to have a stuck-at-0 fault if the line permanently has a logic value 0. Similarly a line L in a circuit is said to have a stuck-at-1 fault if the line permanently has a logic value 1. A circuit is said to have a multiple stuck-at fault if one or more lines have stuck at faults. The total number of distinct multiple stuck-at faults possible in a circuit with N lines is