Q.101 The data structure needed to convert a recursion to an iterative procedure is
(A) Queue. (B) Graph.
(C) Stack. (D) Tree.
Ans: (C)
Q.102 A binary tree stored using linked representation can be converted to its mirror image
by traversing it in
(A) Inorder. (B) Preorder.
(C) Postorder. (D) Any order.
Ans: (B)
Q.103 The prefix form of an infix expression A+B-C*D is
(A) +AB-*CD. (B) -+A B C * D.
(C) -+A B * C D. (D) – + *ABCD.
Ans: (C)
Q.104 The number of edges in a simple, n-vertex, complete graph is
(A) n*(n-2). (B) n*(n-1).
(C) n*(n-1)/2. (D) n*(n-1)*(n-2)
Ans: (C)
Q.105 The largest and the second largest number from a set of n distinct numbers can be
found in
(A) O (n). (B) O (2n).
(C) O ( 2 ) n . (D) O (log n).
Ans: (A)
Q.106 To implement Sparse matrix dynamically, the following data structure is used
(A) Trees (B) Graphs
(C) Priority Queues (D) Linked List
Ans: (D)
Q.107 The depth dn, of complete binary tree of n nodes, where nodes are labeled from 1 to n
with root as node 1 and last leaf node as node n is
(A) log 1 2 n − (B) log 1 2 n +
(C) log 1 2 n + (D) log 1 2 n −
Ans: (C)
Q.108 The balance factor for an AVL tree is either
(A) 0,1 or –1 (B) –2,–1 or 0
(C) 0,1 or 2 (D) All the above
Ans: (A)
Q.109 Applications of Linked List are
(A) Simulation , event driven systems
(B) Postfix and prefix manipulations
(C) Dictionary systems, polynomial manipulations
(D) Fixed block storage allocation, garbage collection
Ans: (D)
Q.110 AVL trees have LL, LR, RR, RL rotations to balance the tree to maintain the balance
factor (LR : Insert node in Right sub tree of Left sub tree of node A, etc). Among
rotations the following are single and double rotations
(A) LL, RL and LR, RR (B) LL, RR and LR, RL
(C) LR, RR and LL, RL (D) LR, RL and LR, RL
Ans: (B)
Q.111 Hashing collision resolution techniques are
(A) Huffman coding, linear hashing (B) Bucket addressing, Huffman coding
(C) Chaining, Huffman coding (D) Chaining, Bucket addressing
Ans: (D)
Q.112 The running time of the following sorting algorithm depends on whether the
partitioning is balanced or unbalanced
(A) Insertion sort (B) Selection sort
(C) Quick sort (D) Merge sort
Ans: (C)
Q.113 Graphs are represented using
(A) Adjacency tree (B) Adjacency linked list
(C) Adjacency graph (D) Adjacency queue
Ans: (B)
Q.114 The average case complexity of Insertion Sort is
(A) O(2n) (B) O(n3)
(C) O(n2) (D) O(2n)
Ans: (C)
Q.115 Infinite recursion leads to
(A) Overflow of run-time stack (B) Underflow of registers usage
(C) Overflow of I/O cycles (D) Underflow of run-time stack
Ans: (A)
Q.116 The number of unused pointers in a complete binary tree of depth 5 is
(A) 4 (B) 8
(C) 16 (D) 32
Ans: (C)
Q.117 The running time for creating a heap of size n is
(A) O (n) (B) O (log n)
(C) O (n log n) (D) O (n2)
Ans: (C)
Q.118 What would be returned by the following recursive function after we call test (0, 3)
int test (int a, int b)
{
if (a==b) return (1);
else if (a>b) return(0);
else return (a+test(a+1, b));
}
(A) 1 (B) 2
(C) 3 (D) 4
Ans: (D)
Q.119 The extra key inserted at the end of the array is called a
(A) End Key (B) Stop Key
(C) Sentinel (D) Transposition
Ans: (C)
Q.120 Which of the following operations is performed more efficiently by doubly linked
list than by singly linked list
(A) Deleting a node whose location is given.
(B) Searching of an unsorted list for a given item.
(C) Inserting a new node after node whose location is given.
(D) Traversing the list to process each node.
Ans: (A)
Q.121 One can determine whether a Binary tree is a Binary Search Tree by traversing it in
(A) Preorder (B) Inorder
(C) Postorder (D) Any of the three orders
Ans: (B)
Q.122 The spanning tree of connected graph with 10 vertices contains
(A) 9 edges (B) 11 edges
(C) 10 edges (D) 9 vertices
Ans: (A)
Q.123 A sorted file contains 16 items. Using binary search, the maximum number of
comparisons to search for an item in this file is
(A) 15 (B) 8
(C) 1 (D) 4
Ans: (D)
Q.124 One can determine whether an infix expression has balanced parenthesis or not by using
(A) Array (B) Queue
(C) Stack (D) Tree
Ans: (C)
Q.125 The average number of key comparisons done in successful sequential search in a list of
length n is
(A) log n (B) (n-1)/2
(C) n/2 (D) (n+1)/2
Ans: (D)
Q.126 The maximum number of nodes in a binary tree of depth 5 is
(A) 31 (B) 16
(C) 32 (D) 15
Ans: (A)
Q.127 n elements of a Queue are to be reversed using another queue. The number of “ADD”
and “REMOVE” operations required to do so is
(A) 2*n (B) 4*n
(C) n (D) The task cannot be accomplished
Ans: (D)
Q.128 A complete binary tree with n leaf nodes has
(A) n+1 nodes (B) 2n-1 nodes
(C) 2n+1 nodes (D) n(n-1)/2 nodes
Ans: (B)
Q.129 A binary tree can be converted in to its mirror image by traversing it in
(A) Inorder (B) Preorder
(C) Postorder (D) Anyorder
Ans: (B)
Q.130 One can convert an infix expression to a postfix expression using a
(A) stack (B) Queue
(C) Deque (D) none of these
Ans: (A)
Q.131 Which of the following types of expressions do not require precedence rules for
evaluation?
(A) fully parenthesised infix expression
(B) postfix expression
(C) partially parenthesised infix expression
(D) more than one of the above
Ans: (A)
Q.132 Overflow condition in linked list may occur when attempting to_____
(A) Create a node when free space pool is empty.
(B) Traverse the nodes when free space pool is empty.
(C) Create a node when linked list is empty.
(D) None of these.
Ans: (A)
Q.133 Linked lists are not suitable data structures for which one of the following problems
(A) insertion sort (B) binary search
(C) radix sort (D) polynomial manipulation
Ans: (B)
Q.134 The sorting technique where array to be sorted is partitioned again and again in such a
way that all elements less than or equal to partitioning element appear before it and
those which are greater appear after it, is called
(A) merge sort (B) quick sort
(C) selection sort (D) none of these
Ans: (B)
Q.135 The search technique for searching a sorted file that requires increased amount of space is
(A) indexed sequential search (B) interpolation search
(C) sequential search (D) tree search
Ans: (A)
The search technique for searching a sorted file that requires increased amount of space
is indexed sequential search. Because in this search technique we need to maintain a
separate index file which requires additional storage space.
Q.136 The postfix form of A ^ B * C – D + E/ F/ (G + H),
(A) AB^C*D-EF/GH+/+ (B) AB^CD-EP/GH+/+*
(C) ABCDEFGH+//+-*^ (D) AB^D +EFGH +//*+
Ans: (A)
Q.137 The prefix of (A+B)*(C-D)/E*F
(A) /+-AB*CD. (B) /*+-ABCD*EF.
(C) */*+AB-CDEF. (D) **AB+CD/EF.
Ans: (C)
Prefix of (A+B) * (C – D) / E*F
(+AB) * (-CD) / E*F
*+AB-CD E*F
*/*+AB-CDEF
Q.138 A sorting technique which uses the binary tree concept such that label of any node is
larger than all the labels in the subtrees, is called
(A) selection sort. (B) insertion sort.
(C) Heap sort. (D) quick sort.
Ans: (C)
A Sorting technique which uses the binary tree concept such that label of any node is
larger than all the, labels in the sub trees, is called Heap sort because heap sort works on
a complete binary tree with the property that the value at any node ‘N’ of the tree should
be greater than or equal to the value at all its children nodes.
Q.139 A full binary tree with ‘n’ non-leaf nodes contains
(A) log2 n nodes . (B) n+1 nodes.
(C) 2n nodes. (D) 2n+l nodes.
Ans: (D)
Q.140 A graph ‘G’ with ‘n’ nodes is bipartite if it contains
(A) n edges. (B) a cycle of odd length.
(C) no cycle of odd length. (D) n2 edges.
Ans: (C)
Q.141 Recursive procedures are implemented by using ____ data tructure.
(A) queues. (B) stacks.
(C) linked lists. (D) strings.
Ans: (B)
Recursive procedures are implemented by using stacks because stacks are LIFO data
structure and we need this feature to store return addresses of various recursive calls
in recursive procedures.
Q.142 In ______, the difference between the height of the left sub tree and height of the right
tree, for each node, is almost one.
(A) Binary search tree (B) AVL – tree
(C) Complete tree (D) Threaded binary tree
Ans: (B)