DC08 DATA STRUCTURES
TYPICAL QUESTIONS & ANSWERS
PART I
OBJECTIVE TYPE QUESTIONS
Each Question carries 2 marks.
Q.1 If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the
expected number of collisions involving a particular key x is :
(A) less than 1. (B) less than n.
(C) less than m. (D) less than n/2.
Ans:A
Q.2 Let A be an adjacency matrix of a graph G. The ijth entry in the matrix A K , gives
(A) The number of paths of length K from vertex Vi to vertex Vj.
(B) Shortest path of K edges from vertex Vi to vertex Vj.
(C) Length of a Eulerian path from vertex Vi to vertex Vj.
(D) Length of a Hamiltonian cycle from vertex Vi to vertex Vj.
Ans:B
Q.3 The OS of a computer may periodically collect all the free memory space to form contiguous
block of free space. This is called
(A) Concatenation (B) Garbage collection
(C) Collision (D) Dynamic Memory Allocation
Ans:B
Q.4 What is the following code segment doing?
void fn( ){
char c;
cin.get(c);
if (c != ‘\n’) {
fn( );
cout.put(c);
}
}
(A) The string entered is printed as it is.
(B) The string entered is printed in reverse order.
(C) It will go in an infinite loop.
(D) It will print an empty line.
Ans:B
1
,DC08 DATA STRUCTURES
Q.5 You have to sort a list L consisting of a sorted list followed by a few “random” elements.
Which of the following sorting methods would be especially suitable for such a task?
(A) Bubble sort (B) Selection sort
(C) Quick sort (D) Insertion sort
Ans:D
Q.6 B Trees are generally
(A) very deep and narrow (B) very wide and shallow
(C) very deep and very wide (D) cannot say
Ans:D
Q.7 A technique for direct search is
(A) Binary Search (B) Linear Search
(C) Tree Search (D) Hashing
Ans:D
Q.8 If a node having two children is deleted from a binary tree, it is replaced by its
(A) Inorder predecessor (B) Inorder successor
(C) Preorder predecessor (D) None of the above
Ans:B
Q.9 The searching technique that takes O (1) time to find a data is
(A) Linear Search (B) Binary Search
(C) Hashing (D) Tree Search
Ans:C
Q.10 A mathematical-model with a collection of operations defined on that model is called
(A) Data Structure (B) Abstract Data Type
(C) Primitive Data Type (D) Algorithm
Ans:B
Q.11 The number of interchanges required to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort
is
(A) 6 (B) 5
(C) 7 (D) 8
Ans:B
Q.12 The postfix form of the expression (A + B) ∗ (C ∗ D − E ) ∗ F / G is
(A) AB + CD ∗ E − FG /∗ ∗ (B) AB + CD ∗ E − F ∗ ∗G /
(C) AB + CD ∗ E − ∗F ∗ G / (D) AB + CDE ∗ − ∗ F ∗ G /
2
,DC08 DATA STRUCTURES
Ans: A
Q.13 The complexity of multiplying two matrices of order m*n and n*p is
(A) mnp (B) mp
(C) mn (D) np
Ans:A
Q.14 Merging 4 sorted files containing 50, 10, 25 and 15 records will take____time
(A) O (100) (B) O (200)
(C) O (175) (D) O (125)
Ans:A
Q.15 For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is
equal to
(A) 2n (B) (2n-1)/2
(C) 2e (D) e2/2
Ans:C
Q.16 In worst case Quick Sort has order
(A) O (n log n) (B) O (n2/2)
(C) O (log n) (D) O (n2/4)
Ans:B
Q.17 A full binary tree with 2n+1 nodes contain
(A) n leaf nodes (B) n non-leaf nodes
(C) n-1 leaf nodes (D) n-1 non-leaf nodes
Ans:B
Q.18 If a node in a BST has two children, then its inorder predecessor has
(A) no left child (B) no right child
(C) two children (D) no child
Ans:B
Q.19 A binary tree in which if all its levels except possibly the last, have the maximum number of
nodes and all the nodes at the last level appear as far left as possible, is known as
(A) full binary tree. (B) AVL tree.
(C) threaded tree. (D) complete binary tree.
Ans:A
Q.20 A linear list of elements in which deletion can be done from one end (front) and insertion
can take place only at the other end (rear) is known as a
(A) queue. (B) stack.
3
, DC08 DATA STRUCTURES
(C) tree. (D) linked list.
Ans:A
Q.21 What is the postfix form of the following prefix expression -A/B*C$DE
(A) ABCDE$*/- (B) A-BCDE$*/-
(C) ABC$ED*/- (D) A-BCDE$*/
Ans:A
Q.22 A full binary tree with n leaves contains
(A) n nodes. (B) log 2 n nodes.
(C) 2n –1 nodes. (D) 2 n nodes.
Ans:C
Q.23 A sort which relatively passes through a list to exchange the first element with any element
less than it and then repeats with a new first element is called
(A) insertion sort. (B) selection sort.
(C) heap sort. (D) quick sort.
Ans:D
Q.24 Which of the following sorting algorithms does not have a worst case running time of O n 2 ? ( )
(A) Insertion sort (B) Merge sort
(C) Quick sort (D) Bubble sort
Ans:B
Q.25 An undirected graph G with n vertices and e edges is represented by adjacency list. What is
the time required to generate all the connected components?
(A) O (n) (B) O (e)
(C) O (e+n) ( )
(D) O e 2
Ans:C
Q.26 Consider a linked list of n elements. What is the time taken to insert an element after an
element pointed by some pointer?
(A) O (1) (B) O (log 2 n )
(C) O (n) (D) O (n log 2 n )
Ans:A
Q.27 The smallest element of an array’s index is called its
(A) lower bound. (B) upper bound.
(C) range. (D) extraction.
4
TYPICAL QUESTIONS & ANSWERS
PART I
OBJECTIVE TYPE QUESTIONS
Each Question carries 2 marks.
Q.1 If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the
expected number of collisions involving a particular key x is :
(A) less than 1. (B) less than n.
(C) less than m. (D) less than n/2.
Ans:A
Q.2 Let A be an adjacency matrix of a graph G. The ijth entry in the matrix A K , gives
(A) The number of paths of length K from vertex Vi to vertex Vj.
(B) Shortest path of K edges from vertex Vi to vertex Vj.
(C) Length of a Eulerian path from vertex Vi to vertex Vj.
(D) Length of a Hamiltonian cycle from vertex Vi to vertex Vj.
Ans:B
Q.3 The OS of a computer may periodically collect all the free memory space to form contiguous
block of free space. This is called
(A) Concatenation (B) Garbage collection
(C) Collision (D) Dynamic Memory Allocation
Ans:B
Q.4 What is the following code segment doing?
void fn( ){
char c;
cin.get(c);
if (c != ‘\n’) {
fn( );
cout.put(c);
}
}
(A) The string entered is printed as it is.
(B) The string entered is printed in reverse order.
(C) It will go in an infinite loop.
(D) It will print an empty line.
Ans:B
1
,DC08 DATA STRUCTURES
Q.5 You have to sort a list L consisting of a sorted list followed by a few “random” elements.
Which of the following sorting methods would be especially suitable for such a task?
(A) Bubble sort (B) Selection sort
(C) Quick sort (D) Insertion sort
Ans:D
Q.6 B Trees are generally
(A) very deep and narrow (B) very wide and shallow
(C) very deep and very wide (D) cannot say
Ans:D
Q.7 A technique for direct search is
(A) Binary Search (B) Linear Search
(C) Tree Search (D) Hashing
Ans:D
Q.8 If a node having two children is deleted from a binary tree, it is replaced by its
(A) Inorder predecessor (B) Inorder successor
(C) Preorder predecessor (D) None of the above
Ans:B
Q.9 The searching technique that takes O (1) time to find a data is
(A) Linear Search (B) Binary Search
(C) Hashing (D) Tree Search
Ans:C
Q.10 A mathematical-model with a collection of operations defined on that model is called
(A) Data Structure (B) Abstract Data Type
(C) Primitive Data Type (D) Algorithm
Ans:B
Q.11 The number of interchanges required to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort
is
(A) 6 (B) 5
(C) 7 (D) 8
Ans:B
Q.12 The postfix form of the expression (A + B) ∗ (C ∗ D − E ) ∗ F / G is
(A) AB + CD ∗ E − FG /∗ ∗ (B) AB + CD ∗ E − F ∗ ∗G /
(C) AB + CD ∗ E − ∗F ∗ G / (D) AB + CDE ∗ − ∗ F ∗ G /
2
,DC08 DATA STRUCTURES
Ans: A
Q.13 The complexity of multiplying two matrices of order m*n and n*p is
(A) mnp (B) mp
(C) mn (D) np
Ans:A
Q.14 Merging 4 sorted files containing 50, 10, 25 and 15 records will take____time
(A) O (100) (B) O (200)
(C) O (175) (D) O (125)
Ans:A
Q.15 For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is
equal to
(A) 2n (B) (2n-1)/2
(C) 2e (D) e2/2
Ans:C
Q.16 In worst case Quick Sort has order
(A) O (n log n) (B) O (n2/2)
(C) O (log n) (D) O (n2/4)
Ans:B
Q.17 A full binary tree with 2n+1 nodes contain
(A) n leaf nodes (B) n non-leaf nodes
(C) n-1 leaf nodes (D) n-1 non-leaf nodes
Ans:B
Q.18 If a node in a BST has two children, then its inorder predecessor has
(A) no left child (B) no right child
(C) two children (D) no child
Ans:B
Q.19 A binary tree in which if all its levels except possibly the last, have the maximum number of
nodes and all the nodes at the last level appear as far left as possible, is known as
(A) full binary tree. (B) AVL tree.
(C) threaded tree. (D) complete binary tree.
Ans:A
Q.20 A linear list of elements in which deletion can be done from one end (front) and insertion
can take place only at the other end (rear) is known as a
(A) queue. (B) stack.
3
, DC08 DATA STRUCTURES
(C) tree. (D) linked list.
Ans:A
Q.21 What is the postfix form of the following prefix expression -A/B*C$DE
(A) ABCDE$*/- (B) A-BCDE$*/-
(C) ABC$ED*/- (D) A-BCDE$*/
Ans:A
Q.22 A full binary tree with n leaves contains
(A) n nodes. (B) log 2 n nodes.
(C) 2n –1 nodes. (D) 2 n nodes.
Ans:C
Q.23 A sort which relatively passes through a list to exchange the first element with any element
less than it and then repeats with a new first element is called
(A) insertion sort. (B) selection sort.
(C) heap sort. (D) quick sort.
Ans:D
Q.24 Which of the following sorting algorithms does not have a worst case running time of O n 2 ? ( )
(A) Insertion sort (B) Merge sort
(C) Quick sort (D) Bubble sort
Ans:B
Q.25 An undirected graph G with n vertices and e edges is represented by adjacency list. What is
the time required to generate all the connected components?
(A) O (n) (B) O (e)
(C) O (e+n) ( )
(D) O e 2
Ans:C
Q.26 Consider a linked list of n elements. What is the time taken to insert an element after an
element pointed by some pointer?
(A) O (1) (B) O (log 2 n )
(C) O (n) (D) O (n log 2 n )
Ans:A
Q.27 The smallest element of an array’s index is called its
(A) lower bound. (B) upper bound.
(C) range. (D) extraction.
4
