1.  Consider an undirected graph G with 100 nodes. The maximum number of edges to be included in G so that the graph is not connected is 
A.  2451 
B.  4950 
C.  4851 
D.  9900 
View/Hide Ans 
Correct Answer is C 
Explanation 
If a graph with n vertices has more than ((n  1)*(n  2))/2 edges then it is connected. 
2.  The amortized time complexity to perform ______ operation(s) in Splay trees is O(Ig n). 
A.  Search 
B.  Search & Insert 
C.  Search & Delete 
D.  Search,Insert & Delete 
View/Hide Ans 
Correct Answer is D 
Explanation 
For m operations to be performed on splay tree it requires O(mlogn) steps where n is the size of the tree.On an average the
time complexity of each operation on the splay tree is
Search:Searching for a node in the tree would take O(logn).
Insert:Inserting a node in to the tree takes O(logn).
Delete:Deleting a node from the tree takes O(logn).

3.  Suppose that the splits at every level of Quicksort are in proportion 1β to β, where 0 ‹ β ‹ = 0.5 is a constant. The number of elements in an array is n. The maximum depth is approximately 
A.  0.5 β Ig n 
B.  0.5 (1 − β) Ig n 
C.  β (Ig n)/(Ig β) 
D.  − (Ig n)/Ig (1 − β) 
View/Hide Ans 
Correct Answer is D 
Explanation 
The minimum depth follows a path that always takes the smaller part of partition  i.e, that multiplies the number of elements by β . One iteration reduces the number of
elements from n to β ^{n} , and i iterations reduces the number of elements to β ^{i} n . At a leaf,
there is just one remaining element, and so at a minimum depth leaf of depth m, we have β ^{m}n=1.Thus, β ^{m}=1/n. Taking logs, we get m log β =  log n or m =  log n / log β .
Similarly, maximum depth corresponds to always taking the larger part of the partition,
i.e., keeping a fraction 1  β of the elements each time. The maximum depth M is reached
when there is one element left, that is, when ( 1  β) ^{ M} n = . Thus, M =  lg(n) / lg(1  β ). 
4.  The min. number of nodes in a binary tree of depth d (root at level 0) is 
A.  2^{d} − 1 
B.  2^{d} + 1 − 1 
C.  d + 1 
D.  d 
View/Hide Ans 
Correct Answer is C 
Explanation 
Counting the root node the minimum number of nodes will be d+1. this can be verified by taking either left or right skewed binary tree with any arbitrary depth d. 
5.  The efficient data structure to insert/delete a number in a stored set of numbers is 
A.  Queue 
B.  Linked list 
C.  Doubly linked list 
D.  Binary tree 
View/Hide Ans 
Correct Answer is C 
Explanation 
because in case of doubly linked list only the node to be inserted/deleted needs to be manipulated and no traversals in forward or backward direction required for the operation so it is more efficient. 
6.  Consider the following statements :
(i) A graph in which there is a unique path between every pair of vertices is a tree. (ii) A connected graph with e = v − 1 is a tree.
(iii) A graph with e = v − 1 that has no circuit is a tree.
Which of the above statements is/are true ?

A.  (i) & (iii) 
B.  (ii) & (iii) 
C.  (i) & (ii) 
D.  All of the above 
View/Hide Ans 
Correct Answer is D 
Explanation 
Equivalent definitions of trees
A graph in which there is a unique path between every pair of vertices is a tree.
A connected graph with e = v  1 is a tree.
A graph with e = v  1 that has no circuit(cycle) is a tree.

7.  Consider the Inorder and Postorder traversals of a tree as given below :
Inorder : j e n k o p b f a c l g m d h i
Postorder : j n o p k e f b c l m g h i d a
The Preorder traversal of the tree shall be

A.  a b f e j k n o p c d g l m h i 
B.  a b c d e f j k n o p g l m h i 
C.  a b e j k n o p f c d g l m h i 
D.  j e n o p k f b c l m g h i d a 
View/Hide Ans 
Correct Answer is C 
Explanation 

8.  A simple graph G with n − vertices is connected if the graph has 
A.  (n − 1) (n − 2)/2 edges 
B.  more than (n − 1) (n − 2)/2 edges 
C.  less than (n − 1) (n − 2)/2 edges 
D.  ∑ ^{k}_{(i=1)} C(ni, 2) edges 
View/Hide Ans 
Correct Answer is B 
Explanation 

9.  Linked Lists are not suitable for _____. 
A.  Binary Search 
B.  Polynomial Manipulation 
C.  Insertion 
D.  Radix Sort 
View/Hide Ans 
Correct Answer is A 
Explanation 
Since linked list are not having array like arrangement where middle element can be calculated by just using index positions. This is not available in Linked List due to Dynamic nature. So Linked List does not support Binary Search. 
10.  The time complexity of an efficient algorithm to find the longest monotonically increasing subsequence of n numbers is 
A.  O(n) 
B.  O(n Ig n) 
C.  O(n2) 
D.  None of the above 
View/Hide Ans 
Correct Answer is C 
Explanation 
Let S[1]S[2]S[3]...S[n] be the input sequence.
Let L[i] , 1<=i <= n, be the length of the longest monotonically increasing subsequence of the first i letters S[1]S[2]...S[i] such that the last letter of the subsequence is S[i].
Let P[i] be the position of the letter before S[i] in the longest subsequence of the first i letters such that the last letter is S[i].
T is the resulting subsequence.
Algorithm
1. for i=1 to n do
2. L[i] = 1
3. P[i] = 0
4. for j = 1 to i1 do
5. if S[j] < S[i] and L[j] >= L[i] then
6. L[i]= L[j]+1
7. P[i]= j
8. endif
9. endfor
10. endfor
11. Get the largest value L[k] in L[1]…L[n]
12. i = 1 // backtracking
13. j = k
14. Do
15. T[i] = S[j]
16. i++; j= P[j]
17. Until j=0
18 Output L[k] and the reverse of T.
The loop in line 1 10 only iterate n times, the inner loop line 49 will execute O(n2) times, So the time complexity of the algorithm is O(n2).
