(1) Starting from the root and performing ____________, level order traversal of a rooted tree can be done.

(B) Depth first search
(C) In-order traversal
(D) Pre-order traversal

(2) We have a hash function and a hash table. The size of hash table is 7 with starting index zero. The hash function is (3x+4) mod 7. Assume that initially the hash table is empty and the sequence 1, 3, 8, 10 is inserted into the table using closed hashing. The content of the table is (‘_’ denotes an empty location in the table)

(A) 1, _, _, _, _, _, 3
(B) 8, _, _, _, _, _, 10
(C) 1, 8, 10, _, _, _, 3
(D) 1, 10, 8, _, _, _, 3

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

(3) Which one of the following statement is false if G is an undirected graph with distinct edge weight, Emax is the edge with maximum weight and Emin is the edge with minimum weight?

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

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

(4) Consider an array L. If an element in an array L is greater than all elements to the right of it then it is called a leader. The best algorithm to find all leaders in an array

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

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. (5) Which one of the following statement is true?

(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

ANSWER: T4 and T6 are left out

(6) The maximum profit that can be earned is

(A) 165
(B) 147
(C) 167
(D) 175

(7) Consider a complete n-array tree. This tree is such that each node has either n number of children or no children. Let l = 10 be the number of internal nodes and L = 41 be the number

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

(A) 5
(B) 4
(C) 3
(D) 2

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 = Y = Z = 0;
X = 1;
Y = 2;
Z = 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];
}

(8) What is the running time of f1(n) and f2(n) respectively?

(A) θ (2n) and θ (2n)
(B) θ (n) and θ (2n)
(C) θ (2n) and θ(n)
(D) θ (n) and θ (n)

ANSWER: θ (2n) and θ (n)

(9) What is the return value of f1(8) and f2(8) respectively?

(A) 1661 and 1640
(B) 1640 and 1661
(C) 59 and 59
(D) 1640 and 1640

(10) Let i, j and n be the integer variables of the C program fragment given below.

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)

ANSWER: val (j) = θ (n)

(11) In a complete binary tree, LASTPOST denotes the last vertex visited in a post order traversal, LASTIN denotes the last vertex visited in an inorder traversal and LASTPRE denotes the last vertex visited in a preorder traversal. The statement, which always holds true, is

(A) LASTIN = LASTPRE
(B) LASTPRE = LASTPOST
(C) LASTIN = LASTPOST
(D) None of the above.

(12) For the graph shown below the number of articulation points is (A) 3
(B) 2
(C) 1
(D) 0

(13) Which one of the following statement is false?

(A) √ logn = O (log log n)
(B) 100n log n = O (nlogn/100)
(C) 2n ≠ O (nk)
(D) If 0x = O (ny)

(14) Consider an unweighted, undirected connected graph. In terms of time complexity, the shortest path from a node S to every other node is most efficiently computed by

(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

ANSWER: Performing a BFS starting from S

(15) _____________ in place sorting algorithm needs the minimum number of swaps.

(A) Selection sort
(B) Quick sort
(C) Insertion sort
(D) Heap sort

(16) The algorithm is as given below:

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)

(17) Consider an undirected graph G whose depth first search tree is T and vertices u and v are the leaves of this tree. The degrees of both u and v in G are at least 2. The statement that holds true is

(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

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

(18) _____________ is used if the concatenation of two lists is to be performed on O(1) time?

(A) Array implementation of list

(19) The vertices of a cycle with n nodes is to be coloured in such a way that no two adjacent nodes have the same colour. The minimum number of colours required is

(A) n!
(B) 3
(C) n - 2 n/2 +2
(D) 2

ANSWER: n - 2 n/2 +2

(20) A set V = {v1, v2,…., vn} has n number of vertices. Out of this given set, the number of undirected graphs (not necessarily connected) that can be constructed are

(A) 2n(n-1)/2
(B) n
(C) n!
(D) None of the above

(21) Which data structure is to be used to implement Dijkstra’s shortest path algorithm on unweighted graphs so that runs in linear time?

(A) Stack
(B) Heap
(C) Queue
(D) B-Tree

(22) Which one of the following option is true for merge sort?

(A) It uses greedy approach
(B) It uses heuristic search
(C) It uses divide and conquer strategy
(D) It uses backtracking approach

ANSWER: It uses divide and conquer strategy

(23) Match the following:

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

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

(24) The recurrence relation capturing the optimal execution time of the towers of Hanoi problem with n discs is

(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

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

(25) Consider two positive function of n: f(n) = n² log n and g(n) = n(log n) 10. The statement which is correct for these two functions, is

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

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.

(26) The Huffman code for the letter a, b, c, d, e, f is

(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

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

(27) The average length of the correct answer to question 26 is

(A) 1.9375
(B) 2.3546
(C) 4
(D) 3.3241

(28) To evaluate polynomial x (j) = m0 + m1j + m2j² + m3j³ where mi ≠ 0, the minimum number of multiplications needed on the input j is

(A) 6
(B) 5
(C) 3
(D) 4

(29) Consider the graph shown below. When Dijkstra’s single source shortest path algorithm run from vertex a, it computes the correct shortest path distance to (A) Vertices a, b, c, d
(B) Vertices a, e, f, g, h
(C) Only vertex a
(D) All the vertices

ANSWER: Vertices a, b, c, d

(30) We have two sorted lists whose sizes are a and b. For merging these two lists into a sorted list of size a + b, we require comparisons of

(A) O (log a + log b)
(B) O (a + b)
(C) O (a)
(D) O (b)

(31) The technique of sorting is called stable if and only if

(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

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

(32) What is the maximum number of nodes in a binary tree whose height is h where height is the maximum number of edges in any root to leaf path?

(A) 2h+1
(B) 2h+1 - 1
(C) 2h
(D) 2h-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 sum += func(j);
return sum;
}
}

(33) What is the space complexity of the above function?

(A) O(n!)
(B) O(n)
(C) O(n²)
(D) O(log n)

(34) When the above function func() is modified and store the values of func(j), 0<=j
significantly. What is the space complexity of the modified function?

(A) O(n!)
(B) O(n)
(C) O(n²)
(D) O(log n)

(36) Consider a graph G on vertices n and 2n-2 edges. The statement that does not hold true for graph G, when the edges of the graph G is partitioned into two edge-disjoint spanning trees, is

(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

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

(37) The implementation of Breadth first search algorithm has been done using queue data structure. In the graph shown below, one possible order of visiting the nodes is (A) NQMPOR
(B) MNOPQR
(C) QMNPOR
(D) QMNPRO

(38) Consider a rooted tree with n nodes. Each node is having 0 or 3 children. The number of leaf nodes in the rooted tree is

(A) (n-1)/2
(B) (n-1)/3
(C) (2n + 1)/3
(D) n/2

(39) T(n) = 2T(n/2) + n and T(0) = T(1) = 1. The statement, which is not true, is

(A) T(n) = θ (n log n)
(B) T(n) = O(n log n)
(C) T(n) = O(n²)
(D) T(n) = Ω (n²)

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

(40) We have a Max heap, which is represented by an array, and the process of inserting an element into it is going on. How many comparisons are done to find the position for the newly inserted element if we perform a binary search on the path from the new leaf to the root?

(A) θ (log2 n)
(B) θ (log2 log2 n)
(C) θ (log2 n/2)
(D) θ (n)

(41) What is the maximum number of edges in an n-node unidirectional graph without self loops?

(A) n/2
(B) (n + 1)(n)/2
(C) n+1
(D) n(n-1)/2

(42) Which one of the following statement is true for the recurrence T(n) = 2T([√n]) + 1, T(1) = 1?

(A) T(n) = θ (2n)
(B) T(n) = θ (n)
(C) T(n) = θ (log log n)
(D) T(n) = θ (log)

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

(43) From the scratch a B-tree of the order of 4 is built by 10 successive iterations. The maximum number of node splitting operations that may take place is

(A) 6
(B) 5
(C) 4
(D) 3

(44) T1 and T2 are the time taken by the Quicksort program P to sort the inputs [1 2 3 4] and [5 4 3 2 1] in ascending order respectively. The statement that holds true is

(A) T1 = T2
(B) T1 < T2
(C) T1 > T2
(D) T1 = T2 + 5 log 5

(45) To convert the array 8, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70 into a heap with maximum elements at the root, the minimum number of interchanges needed are

(A) 0
(B) 1
(C) 2
(D) 3

(46) Out of 4 distinct keys the number of distinct binary search trees that can be created is

(A) 10
(B) 14
(C) 8
(D) 24

(47) Consider the statements given below and find the correct option regarding Bellman-Ford shortest path algorithm.

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

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}. (48) The minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T is

(A) 4
(B) 7
(C) 10
(D) 5

(49) The minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges is

(A) 9
(B) 8
(C) 7
(D) 6

(50) We have hash function x mod 10 and the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199). From the statements given below the one, which holds true, is

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

(51) int func(a, b)
{
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)

(52) In the worst-case scenario, the number of swaps required to sort n elements using selection sort is

(A) θ (logn)
(B) θ (n)
(C) θ (n/2)
(D) θ (n²)

(53) We have the functions as given below:

f(n) = 2n , g(n) = n! and h(n) = nlog n. The statement that holds true about the asymptotic behaviour of functions f(n), g(n) and h(n) is

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

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

(54) Matrix M1 is to be stored in array A and matrix M2 is to be stored in array B. Considering each array to be stored either in row-major or column-major order in contiguous memory locations, the time complexity of an algorithm to compute M1xM2 will be

(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

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

(55) Two inputs that are to be sorted in ascending order using quicksort are given below:

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

(56) Consider that each set is represented as a linked list with elements in arbitrary order. Which one of the following operations is the slowest?

(A) Membership and cardinality
(B) Union only
(C) Intersection and membership
(D) Union and intersection

(57) Consider n number of elements whose median can be found in O(n) time. The statement that is correct about the complexity of quick sort, in which median is selected as a pivot is

(A) θ (n logn)
(B) θ (n²)
(C) θ (n)
(D) θ (n³)

(58) Package A and package B are the two alternative packages for processing a database that has 10k records. To process n records package A takes 0.0001n² time units and package B takes 10nlog10n time units. The smallest value of k for which package B will be preferred over package A is

(A) 6
(B) 10
(C) 2
(D) 5

(59) The graph is as shown below. From the options given below the one, which is not the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm, is (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)

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

(60) The adjacency matrix of an undirected graph G that has n nodes is given by an nxn square matrix whose diagonal and non-diagonal elements are 0’s and 1’s respectively. Graph G has

(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