Data Structure and Algorithm Analysis

Data Structure and Algorithm Analysis
1.
If all c(i, j )s and r(i, j)s are calculated, then OBST algorithm in worst case
takes one of the following time.
(a) O(n log n)
(b) O(n3)
(c) O(n2)
(d) O(log n)
(e) O(n4).
2.
The following is a weighted binary tree, then what is the weighted array for
the TVS problem?
(a)
(b)
(c)
(d)
(e)
3.
[9, 2, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 4]
[9, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 4, 6]
[9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 6, 7, 4]
[9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 6, 4]
[9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 6, 4, 0, 0].
What are the entries of the array TREE[ ] for the above weighted binary tree
for the TVS problem.
(a) [1, 2, 3, 4, 5, 6, 0, 0]
(b) [1, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 4, 5, 6]
(c) [1, 2, 3, 0, 0, 0, 0, 4, 5, 6]
(d) [1, 2, 3, 0, 0, 0, 0, 0, 4, 5, 6]
(e) [1, 2, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 5, 6].
4. For a 15-puzzle problem let the initial arrangement be the following one, then
answer the questions 4 7 with the following arrangement.
10
9
12
11
13
1
2
15
4
8
5
7
14
6
3
What is the value of x used to find the reachability of the solution?

(a) 1
(b) 0
(c) 8
(d) 10
(e) 13.
5.
The values for the position(i), position(j) where i = 14 and j =11, are
(a) 2, 8
(b) 8, 2
(c) 8, 13
(d) 2, 13
(e) 13, 8.
6. The values for less(i), less(j) where i =5, j =7 are
(a) 0, 6
(b) 6, 0
(c) 2, 4
(d) 2, 6
(e) 1, 6.
7.
What is the value to find the reachability of the problem with which you can
say the solution is reachable or not?
(a) 71
(b) 72
(c) 73
(d) 69
(e) 68.
8. The upper bound on the time complexity of the nondeterministic sorting

algorithm is
(a) O(n)
(b) O(n log n)
(c) O(1)
(d) O( log n)
(e) O(n2).
9. The worst case time complexity of the nondeterministic dynamic knapsack
algorithm is
(a) O(n log n)
(b) O( log n)
(c) O(n2)
(d) O(n)
(e) O(1).
10. For the LCBB solution of knapsack problem with the data (p1p4) =
(10,10,12,18) and (w1w4) = (2, 4, 6, 9) and m = 18, then the values of u(1)
and (1) respectively are
(a) -38, -44
(b) -44, -38
(c) -44, -32
(d) -32, -44
(e) -32, -38.
Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10 Set 11 Set 12 Set
13 Set 14 Set 15 Set 16 Set 17 Set 18 Set 19 Set 20 Set 21 Set 22 Set 23 Set 24 Set
25 Set 26
Set 27 Set 28 Set 29 Set 30
Answers
uare.
(1) + -( 6/9*18) ].
11 If for the above problem, the tree is created following the FIFOBB, then the
. values for (5) and u(5) respectively are
(a) -40, -40
(b) -40, -38
(c) -40, -32
(d) -22,
-32
(e) -32, -22.
12 There is a chain of 20 stores; each of the store having 5 departments. Then,
. which of the following is a correct representation of array size?
(a) 5 * 20
(b) 6 * 21
(c) 20 * 5
(d) 21 *
6
(e) 19 * 4.
13 From the following, select the valid data structure which reflects hierarchical
. relationship between the elements.
(a) Graph
(b) Queue
(c) Linked list
(d)
Stack
(e) Tree.
14 Which of the following matrix does have high proportions of zero entries as the
. elements?
(a) Inverse Matrix
(b) Sparse Matrix
(c)
Determinant Matrix
(d) Square Matrix
(e) Transpose Matrix.
15 Let there is a queue whose initial values for Front and Rear are 0 and 1
. respectively. Later queue found to be having the elements 3, 2, 1, 5. If a new
element is inserted in the queue, then which of the following statements is

correct?
(a) Front = 0 and Rear = 5
(b) Front = 0 and Rear = 4
(c) Front = 1 and Rear = 4
(d) Front = 1 and Rear = 5
(e) Insertion is not possible as there is no space in the queue.
16 One from the following is also known as Pre-Order traversal. What that one is?
. (a) LNR
(b) LRN
(c) RLN
(d) RNL
(e) NLR.
17 Which of the following data structure is the best example for the multitasking
. systems?
(a) Tree
(b) Queue
(c) Stack
(d) Linked List
(e) Graph.
18 The initial configuration of the queue is having the elements x, y, z, a forming
. a queue. To get the new configuration a, z, y, x one needs a minimum of
(a) 3 additions and 4 deletion
(b) 3 deletions and 4 additions
(c) 3 deletions and 2 additions
(d) 3 deletions and 3 additions
(e) 4 deletions and 4 additions.
19 To form the new configuration in the above problem, what best data structure is
. seems to be used?
(a) Tree
(b) Queue
(c) Linked List
(d) Circular
Queue (e) Stack.
20 Recursive algorithms are based on
. (a) Divide and conquer approach
(b) Top-down approach
(c) Bottom-up approach
(d) Hierarchical approach
(e) Heuristic approach.
Answers
21. What do you call the selected keys in the quick sort method?
(a) Outer key (b) Inner Key
(c) Partition key
(d) Pivot key (e) Recombine key.
22. Primary clustering occurs in
(a) Linear probing
(b) Quadratic probing
(c) Mid-square method (d) Order probing
(e)
Chaining.
23. How many nodes do a full binary tree with N leaves contain?
(a) 2N nodes
(b) N nodes (c) 2N-1 nodes
(d) N-1 nodes
(e) 2(N-1) nodes.
24. How many nodes does a complete binary tree of level 5 have?
(a) 16 (b) 15 (c) 32
(d) 31 (e) 64.
25. How do you determine the cost of a spanning tree?
(a) By the sum of the costs of the edges of the tree
(b) By the sum of the costs of the edges and vertices of the tree
(c) By the sum of the costs of the vertices of the tree
(d) By the sum of the costs of the edges of the graph
(e) By the sum of the costs of the edges and vertices of the graph.
26. What would be the depth of tree whose level is 9?
(a) 10 (b) 8
(c) 9
(d) 11 (e) 7.
27. A node of a directed graph G having no out-degree and a positive in-degree
is called
(a) Source node (b) Sink node
(c) Sibling node
(d) Null node (e) In-node.
28. The time complexity of the normal quick sort, randomized quick sort
algorithms in the worst case is
(a) O(n2), O(n log n)
(b) O(n2), O(n2)
2
(c) O(n log n), O(n )
(d) O(n log n), O(n log n)
2
(e) O(n log n), O(n log n).
29. Let there be an array of length N, and the selection sort algorithm is used to
sort it, how many times a swap function is called to complete the execution?
(a) N log N times
(b) log N times (c) N2 times
(d) N-1 times
(e) N times.
30. The Sorting method which is used for external sort is
(a) Bubble sort (b) Quick sort
(c) Merge sort
(d) Radix sort
(e) Selection sort.
Answers
31. In analysis of algorithm, approximate relationship between the size of the job
and the amount of work required to do is expressed by using _________
(a) Central tendency
(b) Differential equation
(c) Order of execution
(d) Order of magnitude
(e) Order of Storage.
32. Pick the correct prefix form to the given infix expression
{a*[b/(c-d)*f]/g}/[e+h]
(a) //*a/b*-cdfg+ch (b) abcd-f*/g/*eh+/
(c) //*a*/b-cdfg+eh (d) //*ab*/-cdfg+eh
(e) -//*a*/bcdfg+eh.
33. For recursive MinMax algorithm, the average, worst cases are __________
(a)
(b)
(c)
(d)
(e)
34. P, Q and R are pointer variables. The statements below are intended to swap
the contents of the nodes pointed to by P and Q. rewrite it so that it will work
as intended.
P = Q; R = Q; Q = R;
(a) R=Q; P=R; Q=R;
(b) R=P; P=P; Q=Q;
(c) P=P; P=Q; R=Q;
(d) R=P; P=Q; Q=R;
(e) P=R; R=Q; Q=R;

35. For defining the best time complexity, let f (n) = log n and g (n) = n,
_________
(a) f (n) (g(n)), but g(n) (f(n))
(b) f (n) (g(n)), but g(n)
(f(n))
(c) f (n) (g(n)), and g(n) (f(n))
(d) f (n) (g(n)), and g(n)
(f(n))
(e) Cant be defined for best case.
36. If f, r are the front, rear pointers respectively in a circular queue then the
condition (( f r + size) % size == 1) && ( (f != 0) || (r != -1) ) represents
(a) Queue has only one element
(b) Two
Elements
(c) More than 2 elements but not full
(d) Impossible
values
(e) Queue is full.
37. For the following two statements, choose the correct answer.
I. n2O(n3).
II. n = ((n+1)!).
(a) (I) and (II) are TRUE
(b) (I), (II) are FALSE
(c) (I) is FALSE, but (II) is TRUE
(d) (I) is TRUE and (II) is FALSE
(e) (I) is TRUE but (II) cant be defined.
38. The statement head->Link->Link->Link = NULL terminates a linked list after its
__________ node.
(a) 2nd
(b) 4th
(c) 5th
(d) 3rd
(e) first.
39. For analyzing an algorithm, which is better computing time?
(a) O (100 Log N)
(b) O (N)
(c) O (2N)
(d) O (N log N)
(e) O (N2).
40. To implement the Round Robin algorithm, which of the following data structure
is used?
(a) Stack
(b) Linear Queue
(c) Circular Queue
(e) Double Stack.
(d) Priority Queue
Answers
41. Let f, t: NR 0, and t (n) O (f (n)) iff t(n) c.f (n) where c is positive real
constant and
n no, then no is ___________
(a) Upper bound
(b) Lower bound
(c) Duality value
(d) Threshold value
(e)
Maximum value.
42. In a circular queue, we can disambiguate empty from full queue by
(a) Using a gap in the array
(b) Incrementing queue positions by 2 instead of 1
(c) Keeping a count of the number of elements
(d) (a) and (c) above
(e) (a), (b), and (c) above.
43. In a graph, a vertex with degree one is known as ___________
(a) Pendant vertex (b) Leaf
(c) Root
(d) End vertex
(e) Internal.
44. Consider the usual algorithm for determining whether a sequence of
parentheses is balanced. What is the maximum number of parentheses that
will appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()
(())(()))
(a) 1
(b) 2
(c) 3
(d) 4
(e)
5 or more.
45. If a graph G = (N, E), where E= {}, then the corresponding adjacency matrix
is _____
(a) Unit Matrix
(b) Identity Matrix
(c) Having Diagonal elements Zero
(d) Matrix with all 1s
(e) Zero Matrix.
46. Suppose we have an array implementation of the stack class, with ten items in
the stack stored at data[0] through data[9]. The SIZE is 42. Where does the
push method place the new entry in the array?

(a) data[0]
(b) data[1]
(c) data[9]
(d) data[10]
(e) data[11].
47. Breadth first search __________
(a) Scans each incident node along with its children.
(b) Scans all incident edges before moving to other node.
(c) Is same as backtracking
(d) Scans all the nodes in random order.
(e) Scans all the nodes in pre-order manner.
48. Provided the space is available, then to insert an element in the queue, we
can use for the following structure
struct queue
{
int Q[20];
int f, r;
}Q;
(a) ++Q.Q[Q.r] = x;
(b) Q.Q[++Q.r] =
x;
(c) Q.Q[Q.r]++ = x;
(d) Syntax error
(e) Q.Q[Q.r++] = x;
49. Which method of traversal does not use stack to hold nodes that are waiting to
be processed?
(a) Dept First
(b) D-search
(c) Breadth first
(d) Back-tracking
(e) Bounding.
50. If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then
removed one at a time, in what order will they be removed?
(a) ABCD
(b) ABDC
(c) DCAB
(d) DCBA
(e) ACDB.
Answers
41. Answer : (d)

Reason : According to the mathematical definition of the big Oh notation, this is the Threshold value
defines the upper limit on the size of the instance.
42. Answer : (d)
Reason : The option B is not the suitable one and not correct also, while the other two(a, c ) can be
used
43. Answer : (a)
Reason : According to the definition of the graph, and the degrees of the vertex.
44. Answer : (c)
Reason : Use stack and increment counter by one if opening bracket is encountered, and decrement it
by one if a closing bracket is encountered.
45. Answer : (e)
Reason : As E = empty set, means there is no any edge between any two set of vertices. And hence it is
zero matrix.
46. Answer : (d)
Reason : As it is Stack always the items are pushed at the top of the stack if there is any space. Also
data[10] is the next space as data[0] to data[9] are already filled.
47. Answer : (b)
Reason : As BFS always make use of the Queue.
48. Answer : (b)
Reason : Because first we have to increment the rear pointer and at that place we can insert an
element.
49. Answer : (c)
Reason : As D search, DFS uses stack, so BFS only uses queue and not the stack.
50. Answer : (d)
Reason : As Queue follows FIFO structure.
51. The Knapsack problem where the objective function is to minimize the profit is
______
(a) Greedy
(b) Dynamic 0 / 1
(c) Back tracking
(d) Branch & Bound 0/1
(e) NP Knapsack.
52. I have implemented the queue with a linked list, keeping track of a front node
and a rear node with two reference variables. Which of these reference
variables will change during an insertion into a NONEMPTY queue?
(a) Neither changes
(b) Only front changes
(c) Only rear changes
(d) Both change
(e) (a) or (d) above.
53. For the given 5 jobs with penalties 6,3,4,8,5 respectively, the static state space
tree is generated, then if the first job is selected but not the second job for the
first two jobs consideration, then the rank of such situational node is ______
(a) 6
(b) 3
(c) 0
(d) 9 (e) 20.
54. Which of the following statements is/are TRUE?
i) ADTs define how data is stored and manipulated.
ii) Every linked list has to have at least one external pointer.
iii) Recursive solutions may be easier to understand.
(a) (i),(ii) and (iii) above
(b) Only (i) above
(c) Only (ii) above
(d) Only (iii)above
(e) Only (ii) and (iii) above.
55. Choose the correct answer for the following statements:
I. The theory of NPcompleteness provides a method of obtaining a
polynomial time for NPalgorithms.
II. All NP-complete problem are NP-Hard.
(a) I is FALSE and II is TRUE
(b) I is TRUE and II is FALSE
(c) Both are TRUE
(d) Both are FALSE
(e) II is TRUE, I cant be determined.
56. Having the address of the node to be deleted in doubly linked list, the node can
be deleted
(a) Without traversing the list
(b) Only after traversing the list from the head

(c) Only after traversing the list from the tail
(d) (b) or (c) above
(e) Cant be deleted.
57. The Hamiltonian cycles problem uses the following line of code to generate a
next vertex, provided x[ ] is a global array and k th vertex is under consideration:
(a) x[k] (x[k] + 1) mod n
(b) x[k] (x[k]) mod (n)
(c) x[k] (x[k] + 1) mod (n+1)
(d) x[k] x[k+1] mod n
(e) x[k] x[k+1] mod (n + 1)
58. Suppose cursor refers to a node in a linked list, what statement changes cursor
so that it refers to the next node?
(a) cursor++;
(b) cursor = link;
(c) cursor += link;
(d) cursor = cursor->link;
(e) (a) and (c) above.
(Note:
struct cursor {
int data;
struct cursor *link;
};
59. The graph coloring algorithms time can be bounded by _________
(a) O(mnm) (b) O(nm) (c) O(nm. 2n)
(d) O(mn.2n)
(e) O(nmn).
60. For 0/1 KNAPSACK problem, the algorithm takes ________ amount of time for
memory table, and ______time to determine the optimal load, for N objects and
W as the capacity of KNAPSACK.
(a) O(N+W), O(NW)
(b) (NW), O(N+W)
(c) O(N), O(NW)
(d) O(NW), O(N)
(e) O(N+W),
O(N+W).
Answers
61. List out the areas in which data structures are applied extensively.
(a) Compiler Design
(b) Operating System
(c)
Database Management System
(d) Both (a) and (b) above
(e) (a), (b) and (c) above.
62. What is the major data structure used in the Network data model?
(a) Stack
(b) Array
(c)
Tree
(d) Graph
(e) Queue.
63. The data structure used in the Hierarchical data model is
(a) Array
(b) Tree
(c)
Graph
(d) Stack
(e) Queue.
64. Minimum number of queue(s) needed to implement the priority queue is(are)
(a) Two
(b) One
(c)
Three
(d) Four
(e) Depends upon the application.
65. What data structure is used to perform recursion?
(a) Queue
(b) Linked List
(c)
Stack
(d) Double Linked List
(e) Circular Queue.
66. For the expression ((A + B) * C (D E) ^ (F + G)), the equivalent Postfix
notation is
(a) AB + C * DE - - ^ FG +
(b) AB + CDE - - * FG + ^
(c)
AB + C * DE - FG + - ^
(d) AB + C * DE - - FG + ^
(e) AB + C - DE - * FG + ^.
67. The Prefix notation for the above infix expression is
(a) - * +ABC - DE ^ + FG
(b) ^ - * +ABC - DE + FG
(c)
^ - +AB * C - DE + FG
(d) ^ - + * ABC - DE + FG
(e) - ^ * + ABC - DE + FG.
68. Sorting is not possible by using which of the following methods?

(a) Insertion
(b) Selection
(c)
Deletion
(d) Exchange
(e) Partitioning.
69. The number of null branches for a binary tree with 20 nodes is
(a) 21
(b) 20
(c)
22
(d) 19
(e) 18.
70. What is the type of the algorithm used in solving the 8 Queens problem?
(a) Greedy
(b) Dynamic
(c)
Branch and Bound
(d) Divide and Conquer
(e) Backtracking.
Answers
61.
Answer : (e)
Reason : As the data structure can be used in all the application areas right from the
compiler design to operating systems and even in database management
system design.
62.
Answer : (d)
Reason : As the graph is the suitable data structure to represent the connectivity
between the nodes as edges.
63.
Answer : (b)
Reason : As tree data structure is used to represent the Hierarchical relationship

between the nodes as parent and children.
64.
Answer : (a)
Reason : Two : One queue is used for actual storing of data and another for storing
priorities.
65.
Answer : (c)
Reason : Because of its LIFO (Last In First Out) property it remembers its caller so
knows whom to return when the function has to return. Recursion makes use
of system stack for storing the return addresses of the function calls.
66.
Answer : (d)
Reason : As per the precedence and associativity of the operators, brackets are
evaluated first and then multiplication operators followed by addition,
subtraction operators.
67.
Answer : (b)
Reason : As per the precedence and associativity of the operators, brackets are
evaluated first and then multiplication operators followed by addition,
subtraction operators.
68.
Answer : (c)
Reason : Using insertion we can perform insertion sort, using selection we can
perform selection sort, using exchange we can perform the bubble sort (and
other similar sorting methods) and using the portioning we can perform
merge sort(and other similar sorting methods) But no sorting method can be
done just using deletion.
69.
Answer : (a)
Reason : A binary tree with n nodes has exactly n+1 null nodes.
70.
Answer : (e)
Reason : As the other types of algorithms are not suitable to find the solution for the
given problem.
71. The Following is a binary tree. Answer questions (11 13) considering the
below given tree.
The In-order traversal of the above tree is

(a) H D E B F I J G C A
(b) D H B E A F C I G J
(c)
ABDHECFGIJ
(d) H D B E A F C I G J
(e) D H B E A I G J F C.
72. The Pre-order traversal for the tree in question -11 is
(a) A B D H E C F G J I
(b) A B D E H C F G I J
(c)
D H B EAF C I G J
(d) A B D H E C F G I J
(e) H D E B F I J G C A.
73. The Post-order traversal for the tree in question -11 is
(a) H D E B I J G F C A
(b) D H B E A F C I G J
(c)
HDEBFIJGCA
(d) H D E B F I J G A C
(e) A B D H E C F G I J.
74. There are four trees named A, B, C and D having 8, 15, 13, 14 nodes in them
respectively. Which of them could have formed a full binary tree?
(a) A
(b) B
(c)
C
(d) D
(e) No any tree can be a full binary tree.
75. In the given binary tree if the nodes are stored in an array, then where the
node 4 can be stored?
(a) At location 6
(b) At location 5
(c)
At location 4
(d) At location 3
(e) Cant be stored at any location.
76. Of the following tree structure, which is efficient, considering space and time
complexities?
(a) Incomplete Binary Tree
(b) Complete Binary Tree
(c)
Full Binary Tree
(d) Binary Search Tree
(e) AVL Tree.
77. Consider the following two statements and choose the correct option:
I. According to Access strategies Linked List is a linear one.
II. According to Storage Linked List is a Non-linear one.
(a) (I) is true but (II) is false
(b) (I) is false but (II) is true
(c)
Both (I) and (II) are true
(d) Both (I) and (II) are false
(e) Cant be determined.
78. Which of the following are differences between structures and arrays?
(a) Structures and arrays use different operators to access their elements
(b) Structures are not limited to containing variables of a single data type
(c)
Structures can contain elements that are pointers but arrays not
(d) Structures are passed by value while arrays are passed by reference
(e) Structures and arrays contains the different elements.
79. Which of the following pairs of statements are identical?
(a) (*ptr) element AND ptr.element
(b) *ptr.element AND ptrelement
(c)
*ptrelement AND ptr.element
(d) *(ptr.element) AND ptrelement
(e) (*ptr).element AND ptrelement.
80. A "stack" is also known as what?
(a)
(b)
(c)
(d)
(e)
A FIFO
A Queue
A LIFO
A Linked List
A FOLI.
Answers
71. Answer : (b)

on : Because the rules for traversing the binary tree in In-order are:
Traverse the left sub tree in In-order
Traverse the root
iii.
Traverse the right sub tree in In-order
72. Answer : (d)

on : Because the rules for traversing the binary tree in Pre-order are:
Traverse the root
Traverse the left sub tree in Pre-order
iii.
Traverse the right sub tree in Pre-order
73. Answer : (c)

on : Because the rules for traversing the binary tree in Post-order are:
Traverse the left sub tree in Post-order
Traverse the right sub tree in Post-order
iii.
74.
Traverse the root
Answer : (b)
Reason : In general there are 2n-1 nodes in a full binary tree.
By the method of elimination: Full binary trees contain odd number of nodes.
So there cannot be full binary trees with 8 or 14 nodes, so rejected. With 13
nodes you can form a complete binary tree but not a full binary tree. So the
correct answer is 15.
75.
Answer : (a)
Reason : At location 6
1
Root
1
LC1
2
RC1
3
LC2
4
RC2
5
LC3
6
RC3
7
LC4
8
RC4
9
where LCn means Left Child of node n and RCn means Right Child of node
n. Top row represents the node values and bottom row represents the
positions.
76.
Answer : (b)
Reason : Complete Binary Tree.
By the method of elimination: Full binary tree loses its nature when
operations of insertions and deletions are done. For incomplete binary trees,
extra storage is required and overhead of NULL node checking takes place.
So complete binary tree is the better one since the property of complete
binary tree is maintained even after operations like additions and deletions
are done on it
77.
Answer : (c)
Reason : As the linked list nodes do not have any index and hence they must be
accessed in linear order always. Also they are stored in discrete locations and
not in contiguous memory locations.
78.
Answer : (d)
Reason : As this is the most suitable option when compared to the other options. Also
option c, e are wrong.
79.
Answer : (e)
Reason : As both the operators [ and (*). ] are used to access the members of the
structure through pointers. All the other options have the syntax errors.
80.
Answer : (c)
Reason : As the Stack behaves in Last In First Out manner.
Answers:
71. Answer : (b)

on : Because the rules for traversing the binary tree in In-order are:
Traverse the left sub tree in In-order
Traverse the root
iii.
Traverse the right sub tree in In-order
72. Answer : (d)

on : Because the rules for traversing the binary tree in Pre-order are:
Traverse the root
Traverse the left sub tree in Pre-order
iii.
Traverse the right sub tree in Pre-order
73. Answer : (c)

on : Because the rules for traversing the binary tree in Post-order are:
Traverse the left sub tree in Post-order
Traverse the right sub tree in Post-order
iii.
74.
Traverse the root
Answer : (b)
Reason : In general there are 2n-1 nodes in a full binary tree.
By the method of elimination: Full binary trees contain odd number of nodes.
So there cannot be full binary trees with 8 or 14 nodes, so rejected. With 13
nodes you can form a complete binary tree but not a full binary tree. So the
correct answer is 15.
75.
Answer : (a)
Reason : At location 6
1
Root
1
LC1
2
RC1
3
LC2
4
RC2
5
LC3
6
RC3
7
LC4
8
RC4
9
where LCn means Left Child of node n and RCn means Right Child of node
n. Top row represents the node values and bottom row represents the
positions.
76.
Answer : (b)
Reason : Complete Binary Tree.
By the method of elimination: Full binary tree loses its nature when
operations of insertions and deletions are done. For incomplete binary trees,
extra storage is required and overhead of NULL node checking takes place.
So complete binary tree is the better one since the property of complete
binary tree is maintained even after operations like additions and deletions
are done on it
77.
Answer : (c)
Reason : As the linked list nodes do not have any index and hence they must be
accessed in linear order always. Also they are stored in discrete locations and
not in contiguous memory locations.
78.
Answer : (d)
Reason : As this is the most suitable option when compared to the other options. Also
option c, e are wrong.
79.
Answer : (e)
Reason : As both the operators [ and (*). ] are used to access the members of the
structure through pointers. All the other options have the syntax errors.
80.
Answer : (c)
81. A "queue" is also known as what?

(a) A FIFO
(b) A stack
(c)
A LIFO
(d) A Linked List
(e) A FOFI.
82. A "linked list" always contains elements that can be described as
(a) Redundant
(b) Recursive
(c)
Sentinel
(d) Bidirectional
(e) Self-referential.
83. In tree construction, which is the suitable and efficient data structure?
(a) Array
(b) Linked list
(c)
Stack
(d) Queue
(e) Graph.
84. The following are the statements regarding the NP problems. Chose
the right option from the following options:
I. All NP-complete problems are not NP-hard.
II. Some NP-hard problems are not known to be NP-complete.
(a) Both (I) and (II) are true
(b) Both (I) and (II) are false
(c)
Only (I) is true
(d) Only (II) is true
(e) (I) is true but (II) is not always true.
85. Let G be a graph with n nodes and let m be the chromatic number of the
graph. Then the time taken by the backtracking algorithm to color it is

(a) O(nm)
(b) O(n+m)
(c)
O(mnm)
(d) O(nm)
(e) O(nmn).
86. The time complexity of the shortest path algorithm can be bounded by
(a) O(n2)
(b) O(n4)
(c)
O(n3)
(d) O(n)
(e) O(n log n ).
87. Read the following statements carefully and pick the correct option:
I. The worst time complexity of the Floyds algorithm is O(n 3).
II. The worst time complexity of the Warshalls algorithm is O(n 3).
(a) (I) is false but (II) is true
(b) (I) is true but (II) is false
(c)
Both (I) and (II) are true
(d) (I) is true and (II) is not true always
(e) Both (I) and (II) are false.
88. The asymptotic notation for defining the average time complexity is
(a) Equivalence
(b) Symmetric
(c)
Reflexive
(d) Transitive
(e) Both (c) and (d) above.
89. The suitable data structure to represent the IDs of employees is
(a) Stack
(b) Queue
(c)
Linked List
(d) Array
(e) Tree.
90. The number of nodes a null tree can have is
(a) One
(b) Two
(c)
Three
(d) Zero
(e) Null tree is invalid tree.
Answers
81.
Answer : (a)
82.
Answer : (e)
Reason : There should be a self referential structure in linked list so as to point to the
other node in the link list. The other options are wrong.
83.
Answer : (b)
Reason : If a linked list is used then a node can hold the address of both the left child
and right child. Stack, Queue and Graph can never be used. Arrays can also
be used but careful indexing is required to be done and hence is not a valid
data structure.
84.
Answer : (d)
Reason : According to the theory of NP-complete and NP-hard problems.

85.
Answer : (e)
Reason : As the number of internal nodes in the state space tree are m n, and O(mn)
is the time spent by the NextValue algorithm to determine the children
corresponding to legal colorings. Hence the total time is bounded by O(nm n).
86.
Answer : (c)
Reason : As the algorithm contains three for loops nested together running from 1 to
n and hence the total time is O(n3).
87.
Answer : (c)
Reason : As the both the algorithms contains three for loops nested together running
from 1 to n and hence the total time is O(n3) for both the algorithms.
88.
Answer : (a)
Reason : This is a theta notation which is Reflexive, Symmetric and Transitive and
hence it is an Equivalence relation.
89.
Answer : (d)
Reason : As the type of all Id for all the employees is same then a simple array is
enough to store the values.
90.
Answer : (d)
Reason : As a null tree is a valid tree with zero number of nodes.
91. For the bubble sort algorithm, what is the time complexity of the best/worst
case? (assume that the computation stops as soon as no more swaps in one
pass)
(a) best case: O(n)
worst case: O(n*n)
(b) best case: O(n)
worst case: O(n*log(n))
(c) best case: O(n*log(n)) worst case: O(n*log(n))
(d) best case: O(n*log(n)) worst case: O(n*n)
(e) best case: O( 1) worst case: O( n ).
92. For the quick sort algorithm, what is the time complexity of the best/worst
case?
(a) best case: O(n)
worst case: O(n*n)
(b) best case: O(n)
worst case: O(n*log(n))
(c) best case: O(n*log(n)) worst case: O(n*log(n))
(d) best case: O(n*log(n)) worst case: O(n*n)
(e) best case: O(n*log(n)) worst case: O(n*n*n).
93. In an arbitrary tree ( not a search tree) of order M. Its size is N, and its height
is K. The computation time needed to find a data item on T is
(a) O(K*K)
(b) O(M*M)
(c)
O(N)
(d) O(K)
(e) O( 1 ).
94. When we organize our data as an ordered list, what is the time complexity of
inserting/deleting a data item to/from the list?
(a) O(length_of_list*length_of_list)
(b) O(length_of_list)
(c) O(log(length_of_list * length_of_list))
(d) O(1)
(e) O( log(length_of_list)*length_of_list ).
95. Five statements about B-trees are below. Four of them are correct. Which one
is INCORRECT?
(a) All B-trees are also search trees
(b) The word B-tree stands for balanced tree
(c)
The word B-tree also stands for binary tree
(d) All leaves of a B-tree must be on the same level
(e) B-tree is not same as B+-tree.
96. For any B-tree of height H (H>1), after inserting a new key, is it possible for a
key, K, which was located in a leaf-node to move up to the root in this regard
which of the following is correct?
(a) Cant be defined without data
(b) Never
(c)
Yes, only if H=2
(d) Yes, only when the half of the keys in the root are less than K and the other
half of the keys in the root are greater than K
(e) Yes.
97. When we say the order of a tree is M, we mean
(a) Every non-leaf node must have M subtrees
(b) Every non-leaf node must have M keys
(c)
Every non-leaf node can have at most M subtrees
(d) Every non-leaf node can have at most M keys
(e) The Height of the tree is M.
98. T is a search tree of order M, its size is N, and its height is K. The computation
time needed to INSERT/DELETE a data item on T is
(a) O( 1 )
(b) O( M )
(c)
O( Log K )
(d) O( N )
(e) O( K ).
99. Suppose that we have a data file containing records of famous people, and we
need to build a hash table to find a record from the person's birthday. The size
of the hash table is 4096. The following are hash functions which convert a
birthday to an integer. Which of the following function is the best?
(a)
h1( day/month/year ) = day + month + year
(b)
h2( day/month/year ) = day + month*31 + year
(c)
h3( day/month/year ) = (day + month*31 + year*365) mod 4096
(d)
h4( day/month/year ) = (day + month*31 + year*365) mod 4093
(e)
h5(day/month/year ) = (day + month*31 + year*365).
100 What is collision resolution with open addressing?
.
(a) When collision happens, we create a new memory location outside of the
(b)
(c)
(d)
(e)
existing table, and use a chain to link to the new memory location
When collision happens, we enlarge the hash table
When collision happens, we look for an unoccupied memory location in the
existing table
We use an extra table to collect all collided data
We use indexed hash table to resolve collision.
Answers
91. Answer : (a)
Reason: Best Case is the one in which it is already sorted, and hence it takes O(n) time, otherwise it takes O(n 2)
time.
92. Answer : (d)
Reason: The worst case here is, if the list is already sorted in descending order and we want to sort it in
ascending order. In this case it takes O(n2) time. Otherwise it takes O( n * log(n) ) time.
93. Answer : (c)
Reason: As the size is N, we have to traverse almost entire tree to look for a node ( because it is not a binary
search tree). And hence it takes O(N) time.
94. Answer : (b)
Reason: Because we have to search for deletion/insertion both in the ordered list. And the algorithm takes O(n) in
this case[ best option in the given options].
95. Answer : (c)
Reason: As B-tree is not a binary tree, but a balanced m-way tree
96. Answer : (e)
Reason: Yes, this is the best option given because, if the insertion in a node causes the node to contain the keys
equal to order of the tree, then the middle key of the node will be passed to one level up (it can be a root
also ). A common mistake is to tick D. But, the condition stated in D is too strong. We were only asking
whether a key can move up to the root, and we were not asking whether a key can become a new root!
97. Answer : (c)
Reason: Here in the answer can is most important. That is every non-leaf node can have at most M subtrees
98. Answer : (e)
Reason: In this case it is a search tree ( BST ). And hence the search time is proportional to the height of the tree.
This answer assumes that M < K If M >> K, you could answer B However, M is a fixed number, but K
grows when the size of data grows. Therefore, e is a better answer.
99. Answer : (d)
Reason: With the answer a some of the entries in the hash table, say 3000-4000, are never used. A similar
problem also applies to b, e. In the answer c, 4096 is a bad choice. It should a prime number.
100. Answer : (c)
Reason: The meaning of the open addressing it self is to look and probe for unoccupied and open location to
place the incoming key.
101 What of the following cases is a so-called "collision"?

.
(a) A hash function produces the same address for two different keys:
h( key1 ) = h( key2 ) where key1 =\= key2
(b) Two different hash functions produce the same address for a given key:
h1( key ) = h2( key )
(c)
Two different hash functions produce the same address for two different keys:
h1( key1 ) = h2( key2 ) where key1 =\= key2
(d) A hash function produces the same address for two different keys with different
lengths: h( key1 ) = h( key2 ) where length(key1) =\= length (key2)

(e) A hash function produces the same address for two keys of the same length:
h( key1 ) = h( key2 ) where length(key1) = length(key2).
102 Which of the following statements is INCORRECT when the
.
differences/similarities between binary search trees and heaps?
(a) Both binary search trees and heaps are binary trees
(b) Both binary search trees and heaps require ascending order between sibling
nodes
(c)
With heaps the smallest value is stored at the root, while with binary trees the
smallest value is on the leftmost leaf
(d) In heaps no gaps are allowed apart from the right side of the leaves' level, but
in binary search trees gaps are allowed
(e) The order of root, left, right nodes are different for both the trees.
103 Find the odd one out from the following categories of algorithms.
.
(a) TVSP
(b) OBST
(c)
N-Queens
(d) 15-Puzzle
(e) Bin-Packing.
104 For the ease of searching in a linked list, the linked list be created in
.
(a) Descending order
(b) Ascending order
(c)
Without underflow condition
(d) Any order
(e) With underflow condition.
105 The time complexity of binary search in best, worst cases for an array of size
.
N is
(a) N, N2
(b) 1, Log N
(c)
Log N, N2
(d) 1, N log N
(e) N, N.
106 Folding is a method of generating
.
(a) A hash function
(b) Index function for a triangular matrix
(c)
Linking the tail node to the head node in linked list
(d) Linear probing
(e) Chaining.
107 Which of following algorithm scans the list by swapping the entries whenever
.
pair of adjacent keys are out of desired order?
(a) Insertion sort
(b) Quick sort
(c)
Shell sort
(d) Bubble sort
(e) Radix sort.
108 What is the linked list that contains a variable whose value is the address of
.
the location of the other node in the list?
(a) Integer
(b) Float
(c)
Char
(d) Void
(e) Pointer.
109 The mathematical definition for Omega can be defined as, provided
.
f,g:NR+ and c is a positive constant and n > n0,
(a) f(n) c. g(n) n
(b) f(n) = c. g(n) n
(c)
f(n) c + g(n) n
(d) f(n) = c + g(n) n
(e) f(n) = g(n) n.
110. The notation is
(a) Symmetric
(b) Reflexive
(c)
Transitive
(d) Both (b) and (c) above
(e) (a), (b) and (c) above.
Answers
101. Answer : (a)
Reason: Collision happens if the hash function produces the same address for two different keys in the prime
area.
102. Answer : (b)
Reason: As this statement is totally wrong as Binary search trees require ascending order between siblings node,
but heaps don't.
103. Answer : (e)
Reason: This one belongs to NP-Class category.
104. Answer : (d)
Reason: What ever the order it may be, always we have to search for a node in the entire linked list, which is
always organized in discrete locations. Hence no any particular order is needed.
105. Answer : (b)
Reason: Best case is; if the element to search is there at mid of he list. Worst case is; if the element we are
searching is either not there in the list or at the beginning of the list or end of the list.
106. Answer : (a)
Reason: Folding is one of the methods in hashing functions. It can be shift folding or rounded folding.
107. Answer : (d)
Reason: Bubble sort only is the algorithm from the given options which compares the adjacent keys.
108. Answer : (e)
Reason: A self referential pointer variable is used to hold the address of the next node in the list.
109. Answer : (a)
Reason: According to the mathematical definition of the Asymptotic notations.
110. Answer : (e)
Reason: Because notation is equivalence relationship in nature.
111. Which of the following belongs to the algorithm paradigm?

(a) Minimum & Maximum problem
(b) Knapsack problem
(c)
Selection problem
(d) Merge sort
(e) Quick sort.
112. If f, t: N R+, then t (n) (f (n)), iff f(n) O (t (n)) is known as
(a) Limit rule
(b) Rule of inference
(c)
Duality rule
(d) Rule of consequences
(e) Rule of symmetricity.
113.How many children do an external node of a binary tree of order N contains?
(a) N exactly
(b) N-1 exactly
(c)
One exactly
(d) 0 exactly
(e) N/2 exactly.
114.To calculate c(i, j )s, w( i, j)s and r(i, j)s; Howmuch time does the OBST
algorithm in worst case takes?
(a) O(log n)
(b) O (n4)
(c)
O (n3)
(d) O (n log n)
(e) O (n2).
115.Which of the following in breadth first search uses data structures as an
auxiliary structure to hold nodes for future processing?
(a) Queue
(b) Linked list
(c)
Graph
(d) B-Tree
(e) Stack.
116.The number of loop(s) of a node in a simple graph of N nodes is
(a) One
(b) N
(c)
Zero
(d) Exactly two
(e) N-1.
117.The time taken by NP-class sorting algorithm is
(a) O(1)
(b) O(log n)
(c)
O(n2)
(d) O(n log n)
(e) O(n).
118.Pick the correct one from the following by reading carefully the below
statements
I. Floyds algorithm takes n3 among of time.
Warshalls algorithm takes n3 among of time.
(a)
I is true but II is false
(b)
(c)
(d)
(e)
I is false but II is true

Both are false
Both are true
I is true and II takes n4 amount of time.
What
119.defines the average case for the functions f, g : N > R for all n,
n >
f(n)/g(n) =
(a) f(n) ( g(n)), and f(n) ( g(n))

(b) f(n) ( g(n)), but f(n) ( g(n))
(c)
f(n) ( g(n)), but f(n) ( g(n))
(d) f(n) ( g(n)), but g(n) ( f(n))
(e) f(n) ( g(n)), but f(n) ( g(n)).
120 For the functions f, g : N > R for all n, f(n) = n and g(n) = n log n then
.
(a) f(n) ( g(n)), but g(n) ( f(n))
(b) f(n) ( g(n)), but g(n) ( f(n))
(c)
g(n) ( f(n)), but f(n) ( g(n))
(d) f(n) ( g(n)), and g(n) ( f(n))
(e) f(n) ( g(n)), but f(n) ( g(n)).
Answers
111. Answer : (b)
Reason: Remaining all belongs to divide and conquer paradigm.
112. Answer : (c)
Reason: According to the asymptotic notation rules. And this rule is used to apply the limit rule for the omega
notated values.
113. Answer : (d)
Reason: Because, the leaf nodes cant have the children.
114. Answer : (c)
Reason: Because, we have to calculate all c(i, j )s, w( i, j)s and r(i, j)s for the tree of n identifiers.
115. Answer : (a)
Reason: As in BFS, all the adjacent nodes are traversed first, before traversing the descendent nodes. And hence
a queue is used.
116. Answer : (c)
Reason: Because, the simple graph should not contain any loop in the entire graph.
117. Answer : (e)
Reason: Here only one loop from one to n is there. And hence it runs for n times only.
118. Answer : (d)
Reason: As there are three nested loops running from 1 to n in both of the algorithms. And hence it is O(n 3)
119. Answer : (b)
Reason: According to the limit rules for big Oh notation.
120. Answer : (a)
Reason: According to the limit rules for big Oh notation.
121. Consider that a heap is implemented using a partially filled array called data, and
the array contains n elements (n > 0), where is the entry with the greatest value?
(a) data[0]
(b) data[n-1]
(c) data[n]
(d) data[2*n + 1]
(e) data[2*n + 2].
122. Which of the following are used to represent the sparse matrices?
(a) Singly Linked List where each node contains nonzero elements of the matrix
(b) Circular Linked List for each row, column with each node corresponding to nonzero element
(c) Doubly Linked List
(d) Cant be represented using Linked List, but with arrays only
(e) Can be represented only by queues.
123. Which of the following has a desired key is searched, starting itself from hash
address, sequentially in a table?
(a) Quadratic probing
(b) Random probing
(c) Reverse probing
(d) Chaining
(e) Linear probing.
124. Consider A is an array of order m*n stored in a Row Major order. If the address
of the first element in the array is K which is there at A[0, 0], then What is the address
of A[i, j]?
(a) K + (i-1) * m + j 1
(b) K + (i-1) * n + j 1
(c) K + i * m + j
(d) K + (j-1) * m + j 1
(e) K + j * n + i.
125. Which of the following is used in conversion of an infix expression to a postfix
expression?
(a) Circular list
(b) Array
(c) Stack
(d) Queue
(e) Dequeue.
126. What is the output of the following function when it is called?
void disp( node *first )
if( first->next )
{
{
printf("%4d", first->data);
disp( first->next );
}
}
(a) Display the data of next node always in the list
(b) Display the data of all nodes of the list
(c) Does not execute
(d) Display the data of the first node only
(e) Display the data of the last node only.
127. With the wrap around implementation of a queue, which of the following code
should be used to work out the next location of deletion?
(a) front++
(b) front-(c) front = (front % max_queue_size) + 1
(d) front = (front ++) % max_queue_size
(e) front = 0.
128. Consider the order of a tree is represented by M. Then, which of the following is
true?
(a) Every non-leaf node must have M subtrees
(b) Every non-leaf node must have M keys
(c) Every non-leaf node can have atmost M subtrees
(d) Every non-leaf node can have atmost M keys
(e) The Height of the tree is M.
129. What are the time complexities of binary search for an array of size N in best and
worst cases respectively?
(a) N, N2
(b) 1, Log N
(c) Log N, N2
(d) 1, N Log N
(e) N, N.
130. What is the algorithm, which scans the list by swapping the entries whenever pair
of adjacent keys is out of desired order?
(a) Insertion sort
(b) Quick sort
(c) Shell sort
(d) Bubble sort

(e) Radix sort.
Answers
121. Answer : (a)
Reason: if a heap is implemented using a partially filled array called data, and the array contains n
elements (n > 0), then the entry with the greatest value is data[0] .
122. Answer : (a)
Reason: To represent the sparse matrices, we have Singly Linked List where each node contains nonzero elements of the matrix
123. Answer : (e)
Reason: Linear Probing has a desired key is searched, starting itself from hash address, sequentially
in a table.
124. Answer : (b)
Reason: If A is an array of order m*n stored in a Row Major order. If the address of the first element in
the array is K which is there at A[0, 0], then the address of A[i, j] is K + (i-1) * n + j 1
125. Answer : (c)
Reason: Stack is used in conversion of an infix expression to a postfix expression.
126. Answer : (b)
Reason: if the following function is called.
void disp( node *first )
if( first->next )
{
{
printf("%4d", first->data);
disp( first->next );
}
}
then it Display the data of all nodes of the list.
127. Answer : (d)
Reason: With the ``wrap around'' implementation of a queue, front = (front ++) %
max_queue_size should be used to work out the next location of deletion.
128. Answer : (c)
Reason: if the order of a tree is represented by M. Then , Every non-leaf node can have at most M
subtrees is true.
129. Answer : (b)
Reason: 1, Log N are the time complexities of binary search for an array of size N in best and worst
cases respectively
130. Answer : (d)
Reason: Bubble sort is the algorithm, which scans the list by swapping the entries whenever pair of
adjacent keys is out of desired order.
131 The in-order traversal of some binary tree produced the sequence HFIEJGZ, and the post-order
.
traversal of the same tree produced the sequence HIFJZGE. What will be the total number of
nodes in the left sub tree of the given tree?
(a)
1
(b)
2
(c)
3
(d)
4
(e)
5.
132 Which of the following shows the difference between a queue and a stack?
.
(a)
Queues require linked lists, but stacks do not
(b)
Stacks require linked lists, but queues do not
(c)
Queue is used for complex programs and stack for simple programs
(d)
Stacks use two ends of the structure, queues use only one
(e)
Queues use two ends of the structure; stacks use only one.
133 Which of the following is generated by Folding method?
.
(a)
A hash function
(b)
Index function for a triangular matrix
(c)
Linking the tail node to the head node in linked list
(d)
Linear probing
(e)
Chaining.
134 From the following choose the one which belongs to the algorithm paradigm other than to which
.
others from the following belongs to.
(a)
Minimum & Maximum problem
(b)
Knapsack problem
(c)
Selection problem
(d)
Merge sort
(e)
Quick sort.
135 Which of the following data structures is used by breadth first search as an auxiliary structure to
.
hold nodes for future processing?
(a)
Queue
(b)
Linked list
(c)
Graph
(d)
B-Tree
(e)
Stack.
136 Pick the correct statement(s) from the following set of statements.
.
In the Kruskals algorithm, for the construction of minimal spanning tree for a graph, the selected
edges always form a forest.
In Prims algorithm, for the construction of minimal spanning tree for a graph, the selected edges
always form an orchard.
III. DFS, BFS algorithms always make use of a queue, and stack respectively.
(a)
Only (I) above
(b)
Only (II) above
(c)
Only (III) above
(d)
Both (I) and (III) above
(e)
Both (II) and (III) above.
137 Which of the following methods of collision processing has some of their addresses may remain
.
unchecked?
(a)
Linked collision processing
(b)
Quadratic collision processing
(c)
Linear collision processing
(d)
Random collision processing
(e)
Clustering collision processing.
138 Consider a tree t has two subtrees t 1 and t2. Identify the tree where the subtree t 1 has minimum
.
height and the subtree t2 has maximum height.
(a)
Fibonacci
(b)
B+
(c)
Sparse
(d)
Complete binary
(e)
B.
139 Which of the following is used to select the first entry which has the free block equal to or more
.
than required one in memory allocation?
(a)
Best fit method
(b)
Average fit method
(c)
Worst fit method
(d)
Big fit method
(e)
First fit method.
140 What is the total number of nodes at every level (L) of a complete binary tree?
.
(a)
2L
(b)
2L1
(c)
2L1
(d)
2L1
(e)
2L.
Answers
161. The optimal solution to a problem is a combination of optimal solutions to its subproblems. This is known as
(a) Principle of Duality
(b) Principle of Equality

(c) Principle of Feasibility
(d) Principle of Optimality
(e) Principle of Dynamicity.
162. Which of the following versions of merge sort algorithm does uses space efficiently?
(a) Contiguous version
(b) Array version
(c) Linked version
(d) Structure version
(e) Heap version.
163. Identify the correct problem for multistage graph from the list given below.
(a) Resource allocation problem
(b) Traveling salesperson problem
(c) Producer consumer problem
(d) Barbers problem
(e) Dining philosopher problem.
164. How many edges are there in a Hamiltonian cycle if the edge cost is c and the cost of
cycle is cn
(a) c
(b) 2n
(c) cn
(d) 2c
(e) n.
165. A problem L is NP-complete iff L is NP-hard and
(a) L NP
(b) L NP
(c) L NP
(d) L = NP
(e) L NP.
166. What would be the cost value for any answering node of a sub tree with root r using
branch-bound algorithm?
(a) Maximum
(b) Minimum
(c) Optimal
(d) Average
(e) Negative.
167. Name the process which executes a correct program on data sets measuring the time
and space of a program, in order to compute the results
(a) Partitioning
(b) Hashing
(c) Validating
(d) Profiling
(e) Verifying.
168. What would be the hash address for the following function by using the folding method
Hk = H(4326)?
(a) 69
(b) 32
(c) 46
(d) 105
(e) 42.
169. Name the node which has been generated but none of its children nodes have been
generated in state space tree of backtracking method.
(a) Dead node
(b) Live node
(c) E-Node
(d) State Node
(e) Bounded Node.
170. How many nodes are there in a full state space tree with n = 6?
(a)
(b)
(c)
(d)
(e)
65
64
63
32
31.
Answers
161. Answer : (d)

Reason: According to the principle of optimality, the optimal solution to a problem is a combination of optimal
solutions to its sub-problems which are optimum.
162. Answer : (c)
Reason: Because, in linked version auxiliary memory is not required, as needed in array version.
163. Answer : (a)
Reason: Because, the resource allocation problem also same as allocating the right resource to appropriate
person. The remaining options are not suitable.
164. Answer : (e)
Reason: Because. Simple in Hamiltonian graph there should be exactly n edges to connect all the nodes exactly
once to form a Hamiltonian cycle.
165. Answer : (c)
Reason: According to the definitions of NP-class, NP-complete and NP-hard class problems.
166. Answer : (b)
Reason: Because the objective in branch-bound algorithms is to minimize the objective function.
167. Answer : (d)
Reason: Because, in order to compute the results the profiling process executes the correct program on data sets
measuring the time and space of a program. The remaining options are invalid.
168. Answer : (a)
Reason: Because, according to folding method this is 43+26 which is 69.
169. Answer : (b)
Reason: Because in state space tree organization live node is a node which has been generated but none of its
children nodes have been generated, but are being generated.
170. Answer : (c)
Reason: As this is 2n-1 ( i.e. 26-1 = 63 ).
171. Consider the following Traveling salesperson problem instance matrix. What would be
the value of g(1, {2, 3})?
8
5
1
7
2
3
(a) 2
(b) 12
(c) 14
(d) 17
(e) 9.
172. The running time complexity of graph coloring problem is
(a) O(nm)
(b) O(mn)
(c) O(mnm)
(d) O(nmn)
(e) O(mnnm).
173. What is the time taken by the binary search algorithm to search a key k in a sorted
array of n elements?
(a) O(log2 n)
(b) O(n)
(c) (n log2 n)
(d) O(n2)
(e) O(1).
174. Name the function which is used to kill live nodes without generating all their children in
state space tree using backtracking method
(a) Solution function
(b) Bounding function
(c) Optimal function
(d) State Space function
(e) Randomized function.
175. Which of the following search method will always find a goal node nearest to the root of
the tree?
(a) Depth first search
(b) Binary search
(c) Breadth first search
(d) Heuristic search
(e) Randomized search.
176. What do we call the selected keys in quick sort?
(a) Recombine key
(b) Inner key
(c) Outer key
(d) Pivot key
(e) Median key.
177. This sort finds location pos of smallest elements in a(i), . , a(n) and then interchange
a(pos) with a(i) for i = 1, ., n 1.
(a) Selection sort
(b) Quick sort
(c) Heap sort
(d) Bubble sort

(e) Insertion sort.
178. Adjacency matrix of a digraph is
(a) Identity matrix
(b) Symmetric matrix
(c) Asymmetric matrix
(d) Sparse matrix
(e) Zero matrix.
179. We can efficiently reverse a string using
(a) Linear queue
(b) Stack
(c) Circular queue
(d) Doubly linked list
(e) Circular linked list.
180. The technique of linear probing for collision resolution can lead to
(a) Underflow
(b) Radix ordering
(c) Efficient storage utilization
(d) Overflow
(e) Clustering.
Answers
171. Answer :
(e)
Reason : This is g( 1, {2,3}) = min( C12 + g( 2, {3}), C13 + g( 3, {2})
min( 8+9, 5+4 ) = 9.
172. Answer : (d)
Reason: According to the complexity analysis of the algorithm.
173. Answer : (a)
Reason: According to the mathematical analysis binary search takes ( log2 n ) time.
174. Answer : (b)
Reason: Because, in state space tree generation of backtracking approach a bounding function is used to kill live
nodes without generating all their children, if that node is not promising the solution.
175. Answer : (c)
Reason: Because in this method nodes are generated level by level and hence the goal node is found nearest to
root node.
176. Answer : (d)
Reason: Because, in quick sort division is made along the pivotal element.
177. Answer : (a)
Reason: As this process is the key process for the selection sort algorithm.
178. Answer : (c)
Reason: Because, in a diagraph for directed edge <a, b>; b is adjacent to a, but reverse is not
true. Hence the adjacency matrix is asymmetric matrix.
179. Answer : (b)
Reason: This is nothing but pushing the characters of the string in a stack and then popping the stack to get the
reversed order of the string.
180. Answer : (e)
Reason: Because, if we follow the linear probing method to resolve the collision then it may lead to the clustering.
181 For the smart bubble sort algorithm, what is the time complexity of the best
.
and worst case?
(a) best case: O(n)
worst case: O(n2)
(b) best case: O(n)
worst case: O(n*log n)
(c) best case: O(n*log n)
worst case: O(n*log n)
(d) best case: O(n*log n)
worst case: O(n2)
(e) best case: O(1 )
worst case: O(n).
182 There are two sorted lists L1 and L2. Their lengths are n1 and n2 respectively.
.
You are asked to design an algorithm to generate a sorted
list L3 from L1 and L2. That is, for example,
if L1=[1,5,30] andL2=[3,6,12,24,43] then L3=[1,3,5,6,12,24,30,43]. Which of the
following methods is the most efficient?
(a) Taking elements from L1 one by one, and inserting them into L2such that the
order of L2 remains unchanged
(b) Appending two lists (i.e. join one list's beginning to the other one's end), then
applying quick sort to the appended list.
(c)
Using a merge method that compares two elements at the head of both lists.
The smaller one is then taken out and inserted at the end of L3 while the larger
one is kept its location unchanged. Repeat this until either L1 or L2 is empty.
(d) Append two lists and apply Shell sort.
(e) Append two lists and apply Selection sort.
183 What is the time complexity of the algorithm a in question 2?
.
(a) O(log(n1)*n2)
(b) O(n1*log(n2))
(c)
O(n1+n2)
(d) O(max(n1,n2))
(e) O(n1*n2).
184 What is the best choice for the time complexity of the algorithm C in question
.
2?
(a) O(n1*n2)
(b) O(n1*log(n2))
(c)
O(n1+n2)
(d) O(max(n1,n2))
(e) O(log(n1)*n2).
185 What is the Postfix form of the following in fix expression?
.
(2+3)*(4+(5*6)/(7*8/9*1))
(a) 23+456*78*9/1*/+*
(b) 23+456*78*91/*/+*
(c) 23+456*78*91*//+*
(d) 23+456*78*91*//*+
(e) 23+456*+78*91*//*.
186 The direct or random access of element is not possible in
.
(a) Array
(b) String
(c)
Linked List
(d) Both (a) and (b) above
(e) Both (b) and (c) above.
187 If for a given Queue initially f=0 and r=-1, then f = r refers to
(a) Queue is empty

(b) Queue is full
(c)
Queue has two elements
(d) Exactly one element is there
(e) Not possible at all.
188 Any string of bits of length n represents a unique non-negative integer
.
between
(a) 0 and 2n-1-1
(b) 0 and 2n 1
(c)
2n-1
(d) 0 and 2n
(e) 0 and 2n-1.
189 Pick the statement(s) which is(are) not true
.
(a) ADT is useful tool for specifying the logical properties of data type
(b) While defining the ADT as a mathematical concept, the space efficiency isnt a
major concern
(c)
Every ADT can be implemented using any programming language
(d) ADT helps us to hide the organization of the data
(e) A & B.
190 Using arrays the most efficient implementation of the QUEUE is as
.
(a) Linear queue
(b) Circular queue
(c)
Linked queue
(d) Cant be implemented
(e) Priority queue.
Answers
191 One has implemented the queue with a circular array, keeping track offirst, last,
.
and count (the number of items in the array). Suppose first is zero, and last is
SIZE-1. What can you tell me about count?
(a) count must be zero
(b) count must be SIZE
(c)
count could be zero or SIZE, but no other values could occur
(d) count must be SIZE+1
(e) count must be SIZE-2.
192 When we say the order of a tree is M, we mean
.
(a) every non-leaf node must have M subtrees
(b) every non-leaf node must have M keys
(c)
every non-leaf node can have at most M keys
(d) every non-leaf node can have at most M subtrees
(e) the Height of the tree is M.
193 Find the odd one out from the following categories of algorithms
.
(a) Bin-packing
(b) OBST
(c)
N-Queens
(d) 15-Puzzle
(e) TVSP.
194 This algorithm scans the list by swapping the entries whenever pair of
.
adjacent keys are out of desired order.
(a) Insertion sort.
(b) Bubble sort.
(c)
Shell sort.
(d) Quick sort.
(e) Radix sort.
195 The mathematical definition for Omega can be defined as, provided f,g:NR+
.
and c is a positive constant and n > n0,
(a) f(n) = g(n)
n
(b)
f(n) = c. g(n)
(c)
f(n) c + g(n)
(d)
f(n) = c + g(n)
(e)
f(n) c. g(n)
n.
196 Let f, t: N R+, then t (n) (f (n)), iff f(n) O (t (n)) is known as what?
.
(a) Limit rule
(c)
Duality rule
(d) Rule of consequences
197 The notation is
.
(a) Symmetric
(b) Reflexive
(c)
Transitive
(d) B & C only

(e) A, B, & C.
198 How many children do an external node of a binary tree of order N contains.
.
(a) N exactly
(b) N-1 exactly
(c)
One exactly
(d) 0 exactly
(e) N/2 exactly.
199 From the following chose the one which belongs to the algorithm paradigm
.
other than to which others from the following belongs to.
(a) Minimum & Maximum problem.
(b) Knapsack problem.
(c)
Selection problem.
(d) Merge sort.
(e) Quick sort.
200 To calculate c(i, j )s, w( i, j)s and r(i, j)s; the OBST algorithm in worst case
.
takes the following time.
(a) O(log n)
(b) O (n4)
(c)
O (n3)
(d) O (n log n)
(e) O (n2).
Answers
201 The time taken by NP-class sorting algorithm is

.
(a) O(1)
(b) O(log n)
(c)
O(n2)
(d) O(n log n)
(e) O(n).
202 For the functions f, g : N > R for all n, f(n) = n and g(n) = n log n then
.
(a) f(n) ( g(n)), but g(n) ( f(n))
(b) f(n) ( g(n)), but g(n) ( f(n))
(c)
g(n) ( f(n)), but f(n) ( g(n))
(d) f(n) ( g(n)), and g(n) ( f(n))
(e) f(n) ( g(n)), but f(n) ( g(n)).
203 What is the type of the algorithm used in solving the 8 Queens problem?
.
(a) Greedy
(b) Dynamic
(c)
Branch and Bound
(d) Divide and Conquer
(e) Backtracking.
204 Let G be a graph with n nodes and let m be the chromatic number of the
.
graph. Then the time taken by the backtracking algorithm to color it is
(a) O(nmn)
(b) O(n+m)
(c)
O(mnm)
(d) O(nm)
(e) O(nm).
205 What is the major data structure used in the Network data model?
.
(a) Stack
(b) Array
(c)
Graph
(d) Tree
(e) Queue.
206 Minimum number of queue(s) needed to implement the priority queue is(are)
.
(a) Four
(b) Three
(c)
Two
(d) One
(e) Depends upon the application.
207 Sorting is not possible by using which of the following methods?
.
(a) Insertion
(b) Selection
(c)
Exchange
(d) Deletion
(e) Partitioning.
208 The number of null branches for a binary tree with 20 nodes is
.
(a) 21
(b) 20
(c)
22
(d) 19
(e) 18.
209 The time complexity of binary search in best, worst cases for the array of size
.
N is
(a) N, N2
(b) N, N
(c)
1, logN
(d) 1, NlogN
(e) logN, N2.
210 A desired key in a table is searched, starting itself from hash address,
.
sequentially for the following.
(a) Quadratic probing
(b) Linear probing
(c)
Random probing
(d) Chaining
(e) Reverse probing.
Answers
ded by O(nm n).
ort (and other similar sorting methods) and using the portioning we can perform merge sort(and other similar sortin
211. Find the correct sequence for the Big Oh values for all n > 2
(a)
O(1) < O( n) < O( log n) < O(n log n) < O(n2) < O(n3) < O(2n)
(b)
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n3)
(c)
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)
(d)
O(1) < O(n) < O(log n) < O(n log n) < O(n2) < O(2n) < O(n3)
(e)
O(1) < O(log n) < O(n) < O(n2) < O(n log n) < O(n3) < O(2n).
The
notation
is
212
I. Reflexive.
II. Symmetric.
III. Transitive.
(a)
(b)
(c)
(d)
(e)
Only (I) above

Only (III) above
Both (I) and (II) above
Both (II) and (III) above
All (I), (II) and (III) above.
213 Data structure

(a)
May be helpful to develop efficient algorithms in different phases of data
.
processing
(b)
Need not give relationship between data items
(c)
Is programming language dependent
(d)
Is procedural language dependent
(e)
Need to describe the relationship among data items.
214 Modular programming uses
(a)
Only top-down method
.
(b)
Only bottom-up method
(c)
Both (a) and (b) above
(d)
Procedural approach
(e)
Object oriented approach.
215 In Knapsack problem, the best strategy to get the optimal solution,
.
where Pi, Wi is the Profit, Weight associated with each of the
Xith object respectively is to
(a)
Arrange the values Pi/Wi in ascending order
(b)
Arrange the values Pi/Xi in ascending order
(c)
Arrange the values Pi/Wi in descending order
(d)
Arrange the values Pi/Xi in descending order
(e)
Arrange the values Wi/ Xi in decreasing order.
In
the
following
weighted graph, the length of the minimum spanning tree is
216
(a)
39
.
(b)
41
(c)
43
(d)
52
(e)
depends on the starting vertex.
The
time
complexities of Max Min recursive and non-recursive algorithms are
217
(a)
1, 2
.
(b)
, 2
(c)
2, 1
(d)
,
(e)
3n 2, 3n 1.
218 Greedy job scheduling with deadlines algorithms complexity is defined as
(a)
O(N)
.
(b)
( n log n)
(c)
O (n2 log n)
(d)
O ( n log n)
(e)
(N2).
219 The divide and conquer merge sort algorithms time complexity can be defined as
(a)
(long n)
.
(b)
(n)
(c)
(d)
(e)
(n log n)
(n log n)
(n2 log n).
220 In analysis of algorithm, approximate relationship between the size of the job and
the amount of work required to do it is expressed by using
.
(a)
Order of magnitude or Big - O
(b)
Central tendency
(c)
Differential equation
(d)
Polynomial equation
(e)
Space complexity.
Answers
221 In linked list, a node contains atleast

(a)
Node address field, data field
.
(b)
Node number, data field
(c)
Next address field, information field
(d)
Node number, information field
(e)
Node address field, information field.
222 Which of the following is the correct big-O expression for 1 + 2 + 3 + ... + n?
(a)
O(log n)
.
(b)
O(n)
(c)
O(n log n)
(d)
O(n)
(e)
O(2n).
223 A B-tree of order n is also called
(a) (nn) 1 tree
.
(b)
n(n2) tree
(c)
(n1)n tree
(d)
n(n1) tree
(e)
n1 tree.
224 The minimum number of keys contained in each non root node of a
.
B-tree of order 11 are
(a)
4
(b)
5
(c)
3
(d)
2
(e)
6.
225 Row-major order in two dimensional array refers to
.
(a)
All elements of a row are stored in memory in sequence followed by next row
in sequence and so on
(b)
All elements in the sorted order according to their column sequence
(c)
All elements of a column in sequence and so on
(d)
All elements in the sorted order according to their row sequence
(e)
All elements of a row are stored in memory in sequence followed by next
column in sequence and so on.
226 Null pointer is used to define
I. End of linked list.
.
II. Empty pointer field of a structure.
III. The linked list is empty.
(a)
(b)
(c)
(d)
(e)
Only (I) above

Only (II) above
Only (III) above
227 Direct or random access of element is not possible in

(a)
Linked list
.
(b)
Array
(c)
String
(d)
Queue
(e)
Double linked list.
228 Get a node, store new element and insert the new node at the top
.
refers to insert operation in non empty
(a)
Stack
(b)
Queue
(c)
Array
(d)
Linked list
(e)
Tree.
229 A technique which collects all deleted spaces onto free storage list is
.
called
(a)
Static memory allocation
(b)
Garbage collection
(c)
Calloc
(d)
Dynamic memory allocation
(e)
Malloc.
230 datatype *s;
datatype *p;
.
datatype *i;
p = malloc(100); t=p; s=p+ (100/size of (datatype))-sizeof (datatype);
Func(datatype j )
{ if (p > s) {printf (overflow/n); return:}

*p= j; p++;}
is referring to
(a)
Push operation of stack
(b)
Pop operation of stack
(c)
Push operation of queue
(d)
Pop operation of queue
(e)
Push and pop of the stack.
Answers
231 malloc() returns pointer to

.
(a)
Integer
(b)
Structure
(c)
Character
(d)
Boolean
(e)
Float.
232 If a binary tree is threaded for an in order traversal order, a NULL
.
right link of any node is replaced by the address of its
(a)
Successor
(b)
Predecessor
(c)
Root
(d)
Postdecessor
(e)
None of these.
If graph G has no edges then corresponding adjacency matrix is
233
(a)
Unit matrix
.
(b)
Zero matrix
(c)
Matrix with all 1s
(d)
Diagonal matrix
(e)
Upper diagonal matrix.
Worst
case
efficiency of binary search is
234
(a)
log2 n + 1
.
(b)
n
(c)
N2
(d)
2n
(e)
log n.
235 The property that is not expected from good hashing technique should
(a)
Produce keys uniformly distributed over the range
.
(b)
Easy to program
(c)
Produce no collisions
(d)
Produces collisions
(e)
All above properties are expected.
236 Graph structure is available in
(a)
C
.
(b)
C++
(c)
Pascal
(d)
Java
(e)
Data structures.
237 The element at the root of heap is
(a)
Largest
.
(b)
Smallest
(c)
Depending on type of heap it may be smallest or largest
(d)
Fixed
(e)
Unlimited.
238 Worst case efficiency of which search is O(n)?
(a)
Sequential search
.
(b)
Binary search
(c)
Indexed search
(d)
Hashing
(e)
Depth first search.
Breadth
first search
239
(a)
Scans
all incident edges before moving to other vertex
.
(b)
Scans adjacent unvisited vertex as soon as possible
(c)
Is same as backtracking
(d)
Computes a path between two vertices of graph or equivalently reporting that
no such path exists
(e)
Scans for cycle in graph, that no such cycle exists.
240 Which of the following searching methods requires that all keys must reside in
internal memory?
.
(a)
Binary search
(b)
Sequential search
(c)
Hashing
(d)
Depth first search
(e)
Breadth first search.
Answers
241. Standard queue operations are

(a) empty(), fill(), place(), remove()
(b) enque(), dequeue(), isempty(), isfull()
(c) init(), delete(), add()
(d) isempty(), isfull(), fill(), remove()
(e) isempty(), isfull(), init(), delete(), add().
242. Assume that variable A is a sorted array of integers of length L. Consider the following code
segment:
int k=1, flag=0;
for ( ; k<L; k++ )
{
if (A[k-l] == A[k] ) flag = 1;
}
Which of the following best describes when variable flag is 1 after this code segment executes?
Always
Never
If and only if array A really is sorted
If and only if array A contains adjacent duplicate values
If and only if all values in array A are the same.
243. Consider using binary search to look for a given value in an array of integers. Which of the
following must be true in order for the search to work?
The values in the array are stored in sorted order.
The array does not contain any duplicate values.
The array does not contain any negative values.
(a) Only (I) above
(b) Only (II) above (c) Both (I) and (II) above
(d) Both (I) and (III) above
(e) Both (II) and (III) above.
244. A program is required to store and process information about the solar system. Which types of
data structure would be most appropriate for storing the following respectively : (i) A list of the
names of the planets, (ii) full details of a planet including distance from sun, diameter,
atmospheric composition, etc, (iii) a predetermined list of scientific observations made of the
planet.
(i) linked list
(ii) structure
(iii) linked list
(i) array
(ii) structure
(iii) linked list
(i) linked list
(ii) array
(iii) array
(i) linked list
(ii) linked list (iii) linked list
(i) array
(ii) structure
(iii) array.
245. If data is a circular array of CAPACITY elements, and R is an rear index into that array, what is
the formula for the index after R?
(a) (R + 1) % CAPACITY
(b) R % (1 + CAPACITY)
(c) (R % 1) + CAPACITY
(d) R + (1 % CAPACITY)
(e) R = R + 1.
246. In the linked list implementation of the queue, where does the insert method place the new
entry on the linked list?
At the head
At the tail
After all other entries that are greater than the new entry
After all other entries that are smaller than the new entry
This operation is not possible.
247. One difference between a queue and a stack is:
Queues require linked lists, but stacks do not
Stacks require linked lists, but queues do not
Queue is used for complex programs and stack is used for simple programs
Stacks use two ends of the structure, queues use only one
Queues use two ends of the structure; stacks use only one.
248. Suppose cursor refers to a node in a linked list. What boolean expression will be true when
cursor refers to the tail node of the list?
(a) cursor.next == null
(b) cursor == null (c) cursor.data
== null
(d) cursor.data == 0
(e) cursor.next == cursor.
249. Five statements about lists and stacks are below. Four of them are correct. Which one
isincorrect?
Lists can be implemented by using arrays or linked lists
Lists are the dynamic data structures
A stack is a special kind of list in which all insertions and deletions take place at one end
A list is a sequence of one or more data items
Stacks are easier to implement than lists.
250. For questions 10-11, refer to the following:
Queue q;
int i=1;
const int value = 10;
for ( ; i < value; i++) insert(i, q);
printf(%d, frontofqueue(q) ) ;
delete(q);
delete(q);
printf(%d, frontofqueue(q) ) ;
while (! isempty(q))
delete(q);
What is the output for the above code?
(a) 1, 3
(b) 1, 4
(c) No output
Answers
(d) 9, 6
(e) 9, 7.
251. At the end of this code segment the queue

(a) Contains numbers 1 to 8
(b) Contain numbers 1 to 10 but we can't see them
(c) Is empty
(d) Contains numbers 3 to 10
(e) Contains only 1.
252. What is the correct post fix form of the given infix expression a+b/(c+d)%e*(g-h/(i+j)*k)?
(a) abcd+/e%ghij+/k**-+
(b) abcd+e/%ghij+/k**-+
(c) ab+cd/e%ghij+/k**(d) ab+cd+/e%ghij+/k*-*
(e) abcd+/e%ghij+/k*-*+.
253. With the wrap around implementation of a queue, which of the following code should be used
to work out the next location of deletion?
front++
front-front = (front % max_queue_size) + 1
front = (front ++) % max_queue_size
front = 0.
254. Which boolean expression indicates whether the number in two nodes (p and q) are the
same? Assume that neither p nor q is null.
(a) p == q
(b) p.data == q.data
(d) p.link = q.link
(e) p.data = q.data.
255. Which of the following statements is not true?
(c) p.link == q.link
An array is a data structure containing a number of items of the same type

An array is normally used to store two or more items of data
The lower bound of an array can be declared as any unsigned value
The elements of an array can be initialized when the array is declared
The number of elements in an array must be declared at compile time.
256. Consider searching for a given value in a large, sorted array. Under which of the following
conditions is sequential search slower than binary search?
Always
Never
When the value being searched for is the first element in the array
When the value being searched for is the second element in the array
When the value being searched for is the last element in the array.
257. The following data structure is used to store the values of the extreme ends of the freely
hanging simple pendulum for every oscillation.
(a) Linked List
(b) Priority Queue (c) Deque
(d) Double Stack
(e) Array.
258. The linked list which can be processed in either of the direction is
(a) Single linked list
(b) Circular linked list
(c) Stack implemented as linked list
(d) Queue implemented as linked list
(e) Double linked list.
259. What does a run-time analysis usually count?
The number of arithmetic and other operations required for the program to run
The number of megabytes required for the program to run
The number of seconds required for the program to run
The number of seconds plus the number of megabytes
The number of seconds times the number of megabytes.
260. Which of these is the correct big-O expression for 1+2+3+...+n?
(a) O(log n)
(b) O(n)
(c) O(n log n)
(d) O(n)
(e) O(1).
Answers
261. Which of the following formulas in Omega notation best represent the expression n+35n+6?
(a) (n)
(b) (n)
(c) (n)
262. What term is used to describe an O(n) algorithm?
(a) Constant
(d) (35)
(b) Non Polynomial Deterministic
(e) (6).
(c) Logarithmic
(d) Quadratic
263. Express the formula (n - 2)*(n - 4) using notation:
(e) Linear.
(a) (n2)
(b) (8)
(c) (log n)
(d) (n)
264. Read the following statements carefully and pick the right most option.
(e) (1).
A linear algorithm to solve a problem must perform faster than a quadratic algorithm to solve
the same problem.
An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of
size n=10.
Both (I) and (II) are TRUE
Both (I) and (II) are FALSE
Only (I) is true but (II) depends upon the instance size.
(I) is TRUE but (II) is FALSE
(I) is FALSE and (II) is TRUE.
265. Which of the following are essential statement types for describing algorithms?
(a) Sequence
(b) Selection
(c) Repetition
(d) All the above
(e) A and B only.
266. When we say an algorithm has a time complexity of O (n), what does it mean?
The algorithm has n nested loops
The computation time taken by the algorithm is proportional to n
The algorithm is n times slower than a standard algorithm
There are n number of statements in the algorithm
The computation time taken by the algorithm is less than n seconds.
267. Can we read a data item at any location of a list within a constant time (i.e. O(1))?
Yes
Yes, only if the list is implemented by pointers (i.e. linked-list)
Yes, only if the list is implemented by an array
No, we need O(n) computation steps no matter what kind of implementation is used
No, as constant time is not possible for algorithms.
268. Sequential search has a time complexity of O(n), and binary search has a time complexity
ofO(log(n)). What difference will it make when the size n is 1000?
(a) You would not notice much difference because computers run very fast anyway
(b) As n is 1000, binary search is twice as fast as sequential search
(c) As n is 1000, binary search is 10 times as fast as sequential search
(d) As n is 1000, binary search is 10 times as slow as sequential search
(e) As n is 1000, binary search is 100 times as fast as sequential search.
269. Read the following statements carefully, and choose the correct answer.
I. The notation is Anti Symmetric.
II. The big Oh notation is Semi Equivalence.
(a) (I) is FALSE but (II) is TRUE
(b) Both (I), (II) are TRUE
(c) (I) is TRUE but (II) is FALSE
(d) Both (I), (II) are FALSE
(e) (II) is TRUE and (I) cannot be defined.
270. Find the odd one out.
(a) Bin-Packing Problem
Problem
(d) OBST Problem
(b) TVSP Problem

(e) Sum of Sub Sets Problem.
Answers:
(c) Knap Sack
271. The suitable data structure to represent the data of rainfall of week days in ten cities of three
states is __________
Stack
(b) Queue
(c) Array
Multi way tree
(e) Connected graph.
272. The data structure which allows the insertion at both the ends, but allows the deletion at only
one end is ________
Output restricted Deque
Input restricted Deque
Circular queue
Linear queue
Priority queue.
273. Searching the linked list requires linked list be created in _________
Ascending order
(b) Descending order
With underflow condition
(d) Any order
(e) Without underflow condition.
274. The time complexity of binary search in best, worst cases for an array of size N is
N, N2
(b) N, N
(c) Log N, N2
(d) 1, N log N
(e) 1, log N.
275. How many minimum number of spanning trees, one can have from a given connected graph
with N nodes is having different weights for the edges.
N-1
(b) One
(c) 1/(N+1) 2NCN
(d) 2NCN
(e) N.
276. How many children do an external node of a binary tree of order N contains.
N at least
(b) 2 exactly
(c) More than two
(d) 0
(e) N at most.
277. In-order traversal of binary search tree implies visiting the nodes in __________
Post-order
The order of increasing magnitude of their key
Pre-order
The order of decreasing magnitude of their key N
Arbitrary order.
278. For a binary tree the In-order traversal was found to be as HIGCEFD. Once the post-order
traversal was conducted the output is IHGFEDC. What is the per-order for the given tree?
CGDHEIF
(b) GHICDEF
(c) CGHIDEF
CDEFGHI
(e) Data insufficient and hence cant be answered.
279. Breadth first search uses __________ as an auxiliary structure to hold nodes for future
processing.
Stack
(b) Linked list
(c) Graph
280. Folding is a method of generating ________
(d) B-Tree
(e) Queue.
A hash function
Index function for a triangular matrix
Header node for a circular linked list
Linear probing
Chaining.
Answers:
Answer
271. : (c)
Reason: As the array can keep the data for multiple dimension values which is not possible by using
any other data structure given in the question.
Answer
272. : (a)
Reason: Because in Deque insertion and deletion can take place at any end, but in the question it is
given as deletion is allowed only at one end. Hence it is Output restricted Deque
Answer
273. : (d)
Reason: Because the reference of the next node is stored in the node itself with which one can go to
next node, and hence a particular order is not required.
Answer
274. : (e)
Reason: Because if the list is either small or the element is present at the mid position for the first
call to the function or for the first iteration then it takes one unit of time. In worst case it
takes log n time,
Answer
275. : (b)
Reason: Because one can have at most one tree which is minimum, also the weights are different.
Answer
276. : (d)
Reason: Because external node is a leaf node, that cant have the children
Answer
277. : (b)
Reason: Because if we traverse a BST in in-order, then it is nothing but traversing in the order of
increasing magnitude of their key.
Answer
278. : (c)
Reason: Draw the tree according to the asked in-order and post-order and traverse the tree in preorder.
Answer
279. : (e)
Reason: As this requires the traversing of nodes on the same level before traversing the nodes at
next level of the tree, it requires queue.
Answer
280. : (a)
Reason: Because folding is one of the method of hashing function to locate the key.
281. This algorithm scans the list by swapping the entries whenever pair of adjacent keys are out of
desired order.
Insertion sort (b) Quick sort
(c) Shell sort
(d) Bubble sort
282. At a given node of a simple graph, the number of loops are _________
(e) Radix sort.
More than one

(b) Not more than one
(c) Zero
Exactly two
(e) Equal to the number of nodes of the graph.
283. In the linked list implementation of the stack, where does the push member function place the
new entry on the linked list?
At the head
At the tail
After all other entries those are greater than the new entry
After all other entries those are smaller than the new entry
At null node.
284. I have implemented the queue with a circular array, keeping track of first, last, and count (the
number of items in the array). Suppose first is zero, and last is SIZE-1. What can you tell me
about count?
count must be zero.
count must be SIZE
count must be SIZE-2
count must be SIZE+1
count could be zero or SIZE, but no other values could occur.
285. Convert the following postfix expression to a fully-parenthesized infix expression:
ABC-DE+*F*+
(A + ((B - C) * (D + E) * F))
(A + (((B - C) * (D + E)) * F))
A + (((B - C) * (D + E)) * F)
(A + ((B - C) * (D + E)) * F)
A + ((B - C) * (D + E)) * F.
286. The linked list would be able to make use of a ------------- whose value is the address of the
location which stores the node.
integer
(b) float
(c) char
(d) void
(e) pointer.
287. What kind of list is best to answer questions such as "What is the item at position n?"
Lists implemented with an array
Doubly-linked lists
Singly-linked lists
Doubly-linked or singly-linked lists are equally best
Circular linked list implemented with priorities.
288. Consider the following pseudo code:
declare a stack of characters
while (there are more characters in the word to read ) {
read a character
push the character on the stack
while ( the stack is not empty) {
pop a character off the stack
write the character to the screen
What is written to the screen for the input "carpets"?
serc
(b) steprac
(c) carpets
(d) ccaarrppeettss (e) stepr.
289. What is the value of the postfix expression 6 3 2 4 + - *
Something between 5 and 15
Something between -5 and -15
Something between 5 and -5
Something between -15 and -100
Something between 15 and 100.
290. Suppose we have a circular array implementation of the queue type, with ten items in the
queue stored at data[2] through data[11]. The current SIZE is 22. Where does the insert
method place the new entry in the array?
data[1]
(b) data[22]
(c) data[12]
(d) data[11]
(e) data[21].
Answers:
Answer
281. : (d)
Reason: As in bubble sort always we swap the adjacent keys if they are not in desired order
Answer
282. : (c)
Reason:
Answer
283. :
Reason:
Answer
284. :
Reason:
285.
286.
287.
Reason:
Answer
288. :
Reason:
Answer
289. :
Reason:
Answer
290. :
Reason:
Because in simple graphs the loops are not allowed.

(a)
Because in stack implemented using linked list, head always points to the top most node.
(e)
Because first = 0 and rear = size-1 means either the stack is full or it was made to empty by
after filling it to full. (Since this is a circular queue).
Answer : (b)
Reason: As the fully parenthesized expression requires its sub parts to be in the
parenthesis
Answer : (e)
Reason: Because the pointer is used to hold the address of the next node in the list.
Answer : (a)
Because index is required to locate a particular position, and in arrays this index can be
used to locate an element.
(b)
This nothing but pushing the characters on the stack and popping them from the stack and
hence it will print the input in the reverse because of LIFO manner.
(d)
Because the answer is -18.
(c)
Because still the space is there in the queue and the next available location is 12 thindexed
one, therefore new element is inserted at that location.
291. The mathematical definition for Omega can be defined as, provided f,g:NR+ and c is a
positive constant and n > n0,
f(n) c. g(n) n
f(n) c. g(n) n
f(n) c + g(n) n
f(n) c + g(n) n
f(n) g(n) n.
292. The notation is __________
Symmetric.
Reflexive.
Transitive.
Only (I) above
Only (II) above
Only (III) above
293. From the following pick the one which does not belongs to the same paradigm to which others
belongs to.
Minimum & Maximum problem
Knapsack problem
Selection problem
Merge sort
Quick sort.
294. The OBST algorithm in worst case takes _______ time if all c(i, j )s and r(i, j)s are calculated.
O(log n)
(b) O(n4)
(c) O(n3)
(d) O(n log n)
295. Read the following statements carefully, and choose the correct answer
For the Backtracking algorithms stack data structure is used.
(e) O(n2).
For the Branch-and-bound algorithms queue data structure is used.

(I) is FALSE but (II) is TRUE
(I) and (II) both are FALSE
(I) is TRUE but (II) is FALSE
(I) and (II) both are TRUE
(II) is TRUE and (I) cant be defined.
296. The weighted array used in TVS problems for the following binary tree is __________
(a)
(b)
(c)
(d)
(e)
[1,2,3,0,0,4,0,5,6]
[1,2,3,0,0,4,0,5,0,0,0,0,6]
[1,2,3,4,5,6]
[1,2,3,0,0,4,5,6]
[1,3,5,2,4,6].
297. Let f, t: N R+, then t (n) (f (n)), iff f(n) O (t (n)) is known as __________
Limit rule
(c) Duality rule
Rule of consequences
298. Let f, t: NR 0, and t (n) O (f (n)) iff t(n) c.f (n) where c is positive real constant and n
no, then no is ___________
Upper bound (b) Lower bound
(c) Duality value
Threshold value (e) Maximum value.
299. For the 15-puzzle problem if the initial arrangement is as follows, then the value of x used to
find the reachability is ________
1
9
2
10
3
11
4
12
5
14
8
15
7
6
13
0
(b) 1
(c) 8
(d) 14
300. The time taken by nondeterministic sorting algorithm is ______
O(1)
(b) O(log n)
(c) O(n2)
(d) O(n log n)
(e) 13.
(e) O(n).
Answers
Answer
291. : (a)
Reason: According to the definition of the Omega notation.
Answer
292. : (e)
Reason: According to the asymptotic notational rules, notation is equivalence one
Answer
293. :
Reason:
Answer
294. :
Reason:
Answer
295. :
Reason:
(b)
The remaining all belongs to divide and conquer paradigm.
(c)
Because of the memory functions in OBST we calculate c(i, j )s, r(i, j)s and w(i , j)s.
(d)
According to the need of the traverse, Backtracking algorithm uses stack and Branch-andbound algorithms uses queue.
Answer
296. : (b)
Reason: For any null node in the full binary tree it stores zeros.
Answer
297. : (c)
Reason:
Answer
298. :
Reason:
Answer
299. :
Reason:
According to the asymptotic notational rules.

(d)
According to the definition of Big Oh ( O )
(a)
Accordingly the EMPTY cell is there in non shaded position and hence value of x is 0,
otherwise value of x is 1.
Answer
300. : (e)
Reason: As there it sorts the entries in one loop. Because in nondeterministic sorting algorithms the
abstractions are used which cant be programmed.

Data Structure and Algorithm Analysis

Uploaded by

Copyright:

Available Formats

Data Structure and Algorithm Analysis

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Structure and Algorithm Analysis

Uploaded by

Copyright:

Available Formats

Data Structure and Algorithm Analysis

What is the value of x used to find the reachability of the solution?

8. The upper bound on the time complexity of the nondeterministic sorting

element is inserted in the queue, then which of the following statements is

(e) P=R; R=Q; Q=R;

(d) Priority Queue

push method place the new entry in the array?

41. Answer : (d)

(b) Only after traversing the list from the head

68. Sorting is not possible by using which of the following methods?

Reason : As tree data structure is used to represent the Hierarchical relationship

The In-order traversal of the above tree is

71. Answer : (b)

Traverse the right sub tree in In-order

72. Answer : (d)

Traverse the right sub tree in Pre-order

73. Answer : (c)

Traverse the root

Reason : As the Stack behaves in Last In First Out manner.

71. Answer : (b)

Traverse the right sub tree in In-order

72. Answer : (d)

Traverse the right sub tree in Pre-order

73. Answer : (c)

Traverse the root

Reason : As the Stack behaves in Last In First Out manner.

81. A "queue" is also known as what?

graph. Then the time taken by the backtracking algorithm to color it is

Reason : As the Stack behaves in Last In First Out manner.

Reason : According to the theory of NP-complete and NP-hard problems.

Reason : As a null tree is a valid tree with zero number of nodes.

101 What of the following cases is a so-called "collision"?

lengths: h( key1 ) = h( key2 ) where length(key1) =\= length (key2)

111. Which of the following belongs to the algorithm paradigm?

I is true but II is false

I is false but II is true

(a) f(n) ( g(n)), and f(n) ( g(n))

(d) Bubble sort

(b) Principle of Equality

161. Answer : (d)

(d) Bubble sort

(a) Queue is empty

(d) B & C only

201 The time taken by NP-class sorting algorithm is

ded by O(nm n).

Only (I) above

213 Data structure

221 In linked list, a node contains atleast

Only (I) above

227 Direct or random access of element is not possible in

{ if (p > s) {printf (overflow/n); return:}

231 malloc() returns pointer to

If graph G has no edges then corresponding adjacency matrix is

241. Standard queue operations are

251. At the end of this code segment the queue

(c) p.link == q.link

An array is a data structure containing a number of items of the same type

(b) Non Polynomial Deterministic

(b) TVSP Problem