# CS GATE 2009 (Test 3)

Tag: cs gate 2009
Topic: Algorithms Tag: CS GATE 2009
Q.1
Consider the program below:
#include<stdio.h>
int fun (int n, int *fp)
{
int t, f;
if ( n<= 1)
{
*fp = 1;
return 1;
}
t = fun(n - 1, fp);
f = t+ * fp;
*fp = t;
return f;
}
int main( )
{
int x = 15;
printf (“%d\n”, fun (5, &x));
return 0;
}
The value printed is
A. 6
B. 8
C. 14
D. 15
Explaination / Solution:
No Explaination.

Workspace
Report
Topic: Algorithms Tag: CS GATE 2009
Q.2
The running time of an algorithm is represented by the following recurrence relation:

Which one of the following represents the time complexity of the algorithm?
A. θ(n)
B. θ(n log n)
C. θ(n2)
D. θ(nlog n)
Explaination / Solution:
No Explaination.

Workspace
Report
Topic: Algorithms Tag: CS GATE 2009
Q.3
In quick sort, for sorting n elements, the (n/4)th the smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
A. θ(n)
B. θ(n log n)
C. θ(n2)
D. θ(nlog n)
Explaination / Solution:
No Explaination.

Workspace
Report
Q.4
In which one of the following page replacement policies, Belady’s anomaly may occur?
A. FIFO
B. Optimal
C. LRU
D. MRU
Explaination / Solution:
No Explaination.

Workspace
Report
Q.5
What is the number of swaps required to sort n elements using selection sort, in the worst case?
A. θ(n)
B. θ(n log n)
C. θ(n2)
D. θ(nlog n)
Explaination / Solution:
No Explaination.

Workspace
Report
Q.6
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
A.
B.
C.
D.
Explaination / Solution:
No Explaination.

Workspace
Report
Q.7
Consider the following graph:

Which of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?
A. (b,e) (e,f) (a,c) (b,c) (f,g) (c,d)
B. (b,e) (e,f) (a,c) (f,g) (b,c) (c,d)
C. (b,e) (a,c) (e,f) (b,c) (f,g) (c,d)
D. (b,e) (e,f) (b,c) (a,c) (f,g) (c,d)
Explaination / Solution:
No Explaination.

Workspace
Report
Q.8
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 is
A. 2
B. 3
C. 4
D. 5
Explaination / Solution:
No Explaination.

Workspace
Report
Q.9
Which one of the following array represents a binary max-heap?
A. {25, 12, 16, 13, 10, 8, 14}
B. {25, 14, 13, 16, 10, 8, 12}
C. {25, 14, 16, 13, 10, 8, 12}
D. {25, 14, 12, 13, 10, 8, 16}
Explaination / Solution:
No Explaination.

Workspace
Report
Q.10
A subsequence 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 subsequence (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 option is correct?
A. expr1 ≡ l(i - 1, j) + 1
B. expr1 ≡ I(i, j - 1)
C. expr2 ≡ max(I(i - 1, j), I(i, j - 1))
D. expr2 ≡ max(I(i - 1, j - 1), I(i, j))