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

No Explaination.

Workspace

Report

The running time of an algorithm is represented by the following recurrence relation:

**A. ** θ(n)

**B. ** θ(n log n)

**C. ** θ(n^{2})

**D. ** θ(n^{2 }log n)

**Answer : ****Option A**

**Explaination / Solution: **

No Explaination.

Which one of the following represents the time complexity of the algorithm?

No Explaination.

Workspace

Report

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. ** θ(n^{2})

**D. ** θ(n^{2 }log n)

**Answer : ****Option B**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

In which one of the following page replacement policies, Belady’s anomaly may occur?

**A. ** FIFO

**B. ** Optimal

**C. ** LRU

**D. ** MRU

**Answer : ****Option A**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

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. ** θ(n^{2 }log n)

**Answer : ****Option A**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

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. **

**Answer : ****Option C**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

Consider the following graph:

**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)

**Answer : ****Option D**

**Explaination / Solution: **

No Explaination.

Which of the following is NOT the sequence of edges added to the minimum spanning tree using
Kruskal’s algorithm?

No Explaination.

Workspace

Report

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

**Answer : ****Option C**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

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}

**Answer : ****Option C**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

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.

**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))

**Answer : ****Option C**

**Explaination / Solution: **

No Explaination.

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?

No Explaination.

Workspace

Report