GATE CSE 2009
Q1.
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 the maximum number of data items that can be stored in it. The B+ - tree is initially empty. 10, 3, 6, 8, 4, 2, 1 The maximum number of times leaf nodes would get split up as a result of these insertions isQ2.
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.Q3.
Consider a 4-way set associative cache (initially empty) with total 16 cache blocks. The main memory consists of 256 blocks and the request for memory blocks is in the following order: 0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155. Which one of the following memory block will NOT be in cache if LRU replacement policy is used?Q5.
Let L=L_{1}\cap L_{2} , where L_{1} and L_{2} are languages as defined below: L_{1}= \{a^{m}b^{m} c a^{n} b^{n}|m,n\geq 0 \} L_{2}=\{a^{i}b^{j}c^{k}|i,j,k\geq 0 \} Then L isQ6.
Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes P1, P2, P3 request the sources as follows if executed independently. Which one of the following statements is TRUE if all three processes run concurrently starting at time t=0?Q7.
Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence: 4, 34, 10, 7, 19, 73, 2, 15, 6, 20 Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is used?Q8.
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 sub-sequence (LCS) of x[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of the LCS of x[m] and Y[n] is given below: l(i, j) = 0, if either i=0 or j=0 l(i, j) = expr1, if i,j>0 and x [i-1] = Y [j -1] l(i, j) = expr2, if i,j>0 and x [i-1] != Y [j -1]The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i,j] = l(i,j). Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i,j)?Q9.
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 sub-sequence (LCS) of x[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of the LCS of x[m] and Y[n] is given below: l(i, j) 0, if either i=0 or j=0 = expr1, if i,j>0 and x [i-1] Y [j -1] = expr2, if i,j>0 and x [i-1] Y [j -1] Which one of the following options is correct?Q10.
For the composition table of a cyclic group shown below Which one of the following choices is correct?