GATE IT 2007
Q1.
Consider the C program given below : #include < stdio.h > int main () { int sum = 0, maxsum = 0, i, n = 6; int a [] = {2, -2, -1, 3, 4, 2}; for (i = 0; i < n; i++) { if (i == 0 || a [i] < 0 || a [i] < a [i - 1]) { if (sum > maxsum) maxsum = sum; sum = (a [i] > 0) ? a [i] : 0; } else sum += a [i]; } if (sum > maxsum) maxsum = sum ; printf ("%d\n", maxsum); } What is the value printed out when this program is executed?Q2.
Consider the B^{+} tree in the adjoining figure, where each node has at most two keys and three links. Now the key K50 is deleted from the B^{+} tree resulting after the two insertions made earlier. Consider the following statements about the B^{+} tree resulting after this deletion. i.The height of the tree remains the same. ii.The node (disregarding the links) is present in the tree. iii.The root node remains unchanged (disregarding the links)1 Which one of the following options is true ?Q3.
Consider the B^+ tree in the adjoining figure, where each node has at most two keys and three links.Keys K15 and then K25 are inserted into this tree in that order. Exactly how many of the following nodes (disregarding the links) will be present in the tree after the two insertions?Q4.
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70, 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?Q5.
Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute b^n \bmod{m}, 0 \leq b, n \leq m ?Q6.
The two grammars given below generate a language over the alphabet \{x, y, z\} G1 : S \rightarrow x \mid z \mid x \ S \mid z \ S \mid y \ B B \rightarrow y \mid z \mid y \ B \mid z \ B G2 : S \rightarrow y \mid z \mid y \ S \mid z \ S \mid x \ B B \rightarrow y \mid y \ S Which one of the following choices describes the properties satisfied by the strings in these languages?Q7.
The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. The head is initially positioned at track number 180. Which of the request sets will cause the head to change its direction after servicing every request assuming that the head does not change direction if there is a tie in SSTF and all the requests arrive before the servicing starts?Q8.
The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. What is the maximum cardinality of the request set, so that the head changes its direction after servicing every request if the total number of tracks are 2048 and the head can start from any track?Q9.
A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the DFS call to the vertex u terminates. Which of the following statements is always TRUE for all edges (u, v) in the graph ?Q10.
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.