(A) Breadth first search

(B) Depth first search

(C) In-order traversal

(D) Pre-order traversal

View Answer / Hide Answer

**ANSWER: Breadth first search**

(A) 1, _, _, _, _, _, 3

(B) 8, _, _, _, _, _, 10

(C) 1, 8, 10, _, _, _, 3

(D) 1, 10, 8, _, _, _, 3

View Answer / Hide Answer

**ANSWER: 1, 8, 10, _, _, _, 3**

(A) Emin is present in every minimum spanning tree of G

(B) Emax is not present in any minimum spanning tree.

(C) The removal of Emax must disconnect G, if Emax is in a minimum spanning tree.

(D) G has a unique minimum spanning tree.

View Answer / Hide Answer

**ANSWER: Emax is not present in any minimum spanning tree.**

(A) Solves it in time θ (n

(B) Solves it in linear time using a left to right pass of the array

(C) Solves it in linear time using a right to left pass of the array

(D) Solves it using divide and conquer in time θ (n logn)

View Answer / Hide Answer

**ANSWER: Solves it using divide and conquer in time θ (n logn)**

For questions 5 and 6 refer to the data given below:

Table shows the tasks Ti to be completed and the profit Pi that can be earned if the task is completed before the end of the deadline di th unit of time. The execution of each task requires

one unit and at a time only one task can be executed.

(A) All tasks are completed in the schedule time that gives maximum profit.

(B) T4 and T6 are left out

(C) T1 and T8 are left out

(D) T1 and T6 are left out

View Answer / Hide Answer

**ANSWER: T4 and T6 are left out**

(A) 165

(B) 147

(C) 167

(D) 175

View Answer / Hide Answer

**ANSWER: 147**

of leaves in a complete n-array tree. The value of n is

(A) 5

(B) 4

(C) 3

(D) 2

View Answer / Hide Answer

**ANSWER: 5**

For Questions 8 and 9 refer to the data given below:

int f1(int n)

{

if (n == 0 II n == 1)

return n;

else

return (2*f1(n-1) + 3*f1(n-2));

}

int f2(int n)

{

int a;

int X[N], Y[N], Z[N];

X[0] = Y[0] = Z[0] = 0;

X[1] = 1;

Y[1] = 2;

Z[1] = 3;

for(a = 2; a<=n; a++)

{

X[a] = Y[a-1] + Z[a-2];

Y[a] = 2*X[a];

Z[a] = 3*X[a];

}

return X[n];

}

(A) θ (2

(B) θ (n) and θ (2

(C) θ (2

(D) θ (n) and θ (n)

View Answer / Hide Answer

**ANSWER: θ (2 ^{n}) and θ (n)**

(A) 1661 and 1640

(B) 1640 and 1661

(C) 59 and 59

(D) 1640 and 1640

View Answer / Hide Answer

**ANSWER: 1640 and 1640**

For (i = n, j = 0; i > 0; i /=2, j += i). After termination of the for loop the value stored in the variable j is denoted by val (j). The statement, which is true for this, is

(A) val (j) = θ (n/2)

(B) val (j) = θ (log n)

(C) val (j) = θ (2n)

(D) val (j) = θ (n)

View Answer / Hide Answer

**ANSWER: val (j) = θ (n)**

(A) LASTIN = LASTPRE

(B) LASTPRE = LASTPOST

(C) LASTIN = LASTPOST

(D) None of the above.

View Answer / Hide Answer

**ANSWER: LASTIN = LASTPRE**

(A) 3

(B) 2

(C) 1

(D) 0

View Answer / Hide Answer

**ANSWER: 3**

(A) √ logn = O (log log n)

(B) 100n log n = O (nlogn/100)

(C) 2n ≠ O (nk)

(D) If 0

View Answer / Hide Answer

**ANSWER: 2n ≠ O (nk)**

(A) Performing a DFS starting from S

(B) Performing a BFS starting from S

(C) Warshall’s algorithm

(D) Dijkstra’s algorithm starting from S

View Answer / Hide Answer

**ANSWER: Performing a BFS starting from S**

(A) Selection sort

(B) Quick sort

(C) Insertion sort

(D) Heap sort

View Answer / Hide Answer

**ANSWER: Selection sort**

Procedure A(n)

If n<=2

Return (1)

Else

Return (A( √n));

The running time of this algorithm is best described by

(A) O(log n)

(B) O(n)

(C) O(log log n)

(D) O(1)

View Answer / Hide Answer

**ANSWER: O(n)**

(A) There must exist a vertex whose removal disconnects u and v in G

(B) There must exist a vertex adjacent to both u and v in G

(C) There must exist a cycle in G containing u and all its neighbours in G

(D) There must exist a cycle in G containing u and v

View Answer / Hide Answer

**ANSWER: There must exist a cycle in G containing u and all its neighbours in G**

(A) Array implementation of list

(B) Circular doubly linked list

(C) Singly linked list

(D) Doubly linked list

View Answer / Hide Answer

**ANSWER: Circular doubly linked list**

(A) n!

(B) 3

(C) n - 2 n/2 +2

(D) 2

View Answer / Hide Answer

**ANSWER: n - 2 n/2 +2**

(A) 2

(B) n

(C) n!

(D) None of the above

View Answer / Hide Answer

**ANSWER: 2 ^{n(n-1)/2 }**

(A) Stack

(B) Heap

(C) Queue

(D) B-Tree

View Answer / Hide Answer

**ANSWER: Heap**

(A) It uses greedy approach

(B) It uses heuristic search

(C) It uses divide and conquer strategy

(D) It uses backtracking approach

View Answer / Hide Answer

**ANSWER: It uses divide and conquer strategy**

List I List II

u) All pairs shortest paths p) Greedy

v) Quick sort q) Depth first search

w) Minimum weight spanning tree r) Dynamic programming

x) Connected components s) Divide and conquer

(A) u – r, v – s, w – p, x - q

(B) u – r, v – p, w – s, x - q

(C) u – q, v – p, w – r, x - s

(D) u – p, v – s, w – r, x - q

View Answer / Hide Answer

**ANSWER: u – r, v – s, w – p, x - q**

(A) T(n) = 2T(n-2) + 2

(B) T(n) = 2T(n-2) + 1

(C) T(n) = 2T(n-1) + 1

(D) T(n) = 2T(n-1) + 2

View Answer / Hide Answer

**ANSWER: T(n) = 2T(n-1) + 1**

(A) f(n) = O(g(n)) and g(n) = O(f(n))

(B) f(n) ≠ O(g(n)) and g(n) ≠ O(f(n))

(C) f(n) = O(g(n)) and g(n) ≠ O(f(n))

(D) f(n) ≠ O(g(n)) and g(n) = O(f(n))

View Answer / Hide Answer

**ANSWER: f(n) ≠ O(g(n)) and g(n) ≠ O(f(n))**

For the Questions 26 and 27 refer to the data given below:

The probability of letters a = 1/2, b = 1/4, c = 1/8, d = 1/16, e = 1/32, f = 1/32.

(A) 10, 110, 1111, 1010, 1100, 00110

(B) 11, 10, 01, 001, 0001, 0000

(C) 1, 11, 111, 1110, 11000, 10000

(D) 0, 10, 110, 1110, 11110, 11111

View Answer / Hide Answer

**ANSWER: 0, 10, 110, 1110, 11110, 11111**

(A) 1.9375

(B) 2.3546

(C) 4

(D) 3.3241

View Answer / Hide Answer

**ANSWER: 1.9375**

(A) 6

(B) 5

(C) 3

(D) 4

View Answer / Hide Answer

**ANSWER: 3**

(A) Vertices a, b, c, d

(B) Vertices a, e, f, g, h

(C) Only vertex a

(D) All the vertices

View Answer / Hide Answer

**ANSWER: Vertices a, b, c, d**

(A) O (log a + log b)

(B) O (a + b)

(C) O (a)

(D) O (b)

View Answer / Hide Answer

**ANSWER: O (a + b)**

(A) It uses divide and conquer technique

(B) It takes O (n) space

(C) It takes O (n log n) time

(D) It maintains the relative order of occurrence of non-distinct elements

View Answer / Hide Answer

**ANSWER: It maintains the relative order of occurrence of non-distinct elements**

(A) 2

(B) 2

(C) 2

(D) 2

View Answer / Hide Answer

**ANSWER: 2 ^{h+1} - 1**

For questions 33 and 34 refer to the data given below:

Double func(int n)

{

int j;

double sum;

if(j ==0)

return 1.0;

else

{

sum = 0.0;

for(j = 0; j

return sum;

}

}

(A) O(n!)

(B) O(n)

(C) O(n

(D) O(log n)

View Answer / Hide Answer

**ANSWER: O(n!)**

significantly. What is the space complexity of the modified function?

(A) O(n!)

(B) O(n)

(C) O(n²)

(D) O(log n)

View Answer / Hide Answer

**ANSWER: O(n)**

(A) Between every pair of vertex there are two vertex-disjoint paths.

(B) Between every pair of vertex there are two edge-disjoint paths

(C) There are at least two edges for the minimum cut in G.

(D) At most 2k-2 edges are present in the induced subgraph for every subset of k vertices

View Answer / Hide Answer

**ANSWER: Between every pair of vertex there are two vertex-disjoint paths.**

(A) NQMPOR

(B) MNOPQR

(C) QMNPOR

(D) QMNPRO

View Answer / Hide Answer

**ANSWER: QMNPRO**

(A) (n-1)/2

(B) (n-1)/3

(C) (2n + 1)/3

(D) n/2

View Answer / Hide Answer

**ANSWER: (2n + 1)/3**

(A) T(n) = θ (n log n)

(B) T(n) = O(n log n)

(C) T(n) = O(n

(D) T(n) = Ω (n

View Answer / Hide Answer

**ANSWER: T(n) = θ (n log n)**

(A) θ (log2 n)

(B) θ (log2 log2 n)

(C) θ (log2 n/2)

(D) θ (n)

View Answer / Hide Answer

**ANSWER: θ (log2 n)**

(A) n/2

(B) (n + 1)(n)/2

(C) n+1

(D) n(n-1)/2

View Answer / Hide Answer

**ANSWER: (n + 1)(n)/2**

(A) T(n) = θ (2n)

(B) T(n) = θ (n)

(C) T(n) = θ (log log n)

(D) T(n) = θ (log)

View Answer / Hide Answer

**ANSWER: T(n) = θ (log log n)**

(A) 6

(B) 5

(C) 4

(D) 3

View Answer / Hide Answer

**ANSWER: 3**

(A) T1 = T2

(B) T1 < T2

(C) T1 > T2

(D) T1 = T2 + 5 log 5

View Answer / Hide Answer

**ANSWER: T1 = T2**

(A) 0

(B) 1

(C) 2

(D) 3

View Answer / Hide Answer

**ANSWER: 2**

(A) 10

(B) 14

(C) 8

(D) 24

View Answer / Hide Answer

**ANSWER: 14**

I) It always finds a negative weighted cycle, if one exists.

II) It finds whether any negative weighted cycle is reachable from the source.

(A) Only II holds true

(B) Only I holds true

(C) Both I and II holds true

(D) Neither I nor II holds true

View Answer / Hide Answer

**ANSWER: Only II holds true**

For questions 48 and 49 refer to the data given below:

Consider the matrix W given below where entry Wij is the weight of the edge {i, j}. We have a complete undirected graph with vertex set {0, 1, 2, 3, 4}.

(A) 4

(B) 7

(C) 10

(D) 5

View Answer / Hide Answer

**ANSWER: 10**

(A) 9

(B) 8

(C) 7

(D) 6

View Answer / Hide Answer

**ANSWER: 8**

I. 9679, 1989, 4199 hash to the same value.

II. 1472, 1671 hash to the same value

III. All elements hash to the same value

IV. Each element hashes to a different value.

(A) Only I

(B) I and IV

(C) II and III

(D) I and II

View Answer / Hide Answer

**ANSWER: I and II**

{

if(a%b == 0)

return b;

a = a%b;

return func(b, a);

}

In the above function let a = b. The number of recursive calls made by this function is

(A) θ (log2 n)

(B) θ (log2 log2 n)

(C) θ (log2 n/2)

(D) θ (n)

View Answer / Hide Answer

**ANSWER: θ (log2 n)**

(A) θ (logn)

(B) θ (n)

(C) θ (n/2)

(D) θ (n

View Answer / Hide Answer

**ANSWER: θ (n)**

f(n) = 2

(A) h(n) = O(f(n)); g(n) = Ω (f(n))

(B) g(n) = O(f(n)); h(n) = O(f(n))

(C) f(n) = O(g(n)); g(n) = O(h(n))

(D) f(n) = Ω (g(n)); g(n) = O(h(n))

View Answer / Hide Answer

**ANSWER: h(n) = O(f(n)); g(n) = Ω (f(n))**

(A) Independent of the storage scheme.

(B) Best if both the array will be in column-major

(C) Best if array A will be in row-major and array B will be in column-major order

(D) Best if both the array will be in row-major

View Answer / Hide Answer

**ANSWER: Best if array A will be in row-major and array B will be in column-major order**

I) 1, 2, 3 …… n

II) n, n-1, n-2, …… 2, 1

For the inputs given above the number of comparisons that are to be made is represented by C1 and C2. Then,

(A) C1 > C2

(B) C1 = C2

(C) C1 < C2

(D) None of the above

View Answer / Hide Answer

**ANSWER: C1 = C2**

(A) Membership and cardinality

(B) Union only

(C) Intersection and membership

(D) Union and intersection

View Answer / Hide Answer

**ANSWER: Union and intersection**

(A) θ (n logn)

(B) θ (n

(C) θ (n)

(D) θ (n

View Answer / Hide Answer

**ANSWER: θ (n ^{²})**

(A) 6

(B) 10

(C) 2

(D) 5

View Answer / Hide Answer

**ANSWER: 6**

(A) (b, e) (a, c) (e, f) (b, c) (f, g) (c, d)

(B) (b, e) (e, f) (a, c) (b, c) (f, g) (c, d)

(C) (b, e) (e, f) (b, c) (a, c) (f, g) (c, d)

(D) (b, e) (e, f) (a, c) (f, g) (b, c) (c, d)

View Answer / Hide Answer

**ANSWER: (b, e) (e, f) (b, c) (a, c) (f, g) (c, d)**

(A) Unique minimum spanning tree of cost n-1

(B) No minimum spanning tree (MST)

(C) Multiple spanning trees of different costs

(D) Multiple distinct MST’s, each of cost n-1

View Answer / Hide Answer

**ANSWER: Multiple distinct MST’s, each of cost n-1**