Q.67 The constructed datatype of C is known as

(A) Pointers (B) String

(C) Structure (D) Array

Ans: C

Q.69 The number of nodes in a complete binary tree of depth d (with root at depth 0) is

(A) 2 1 d−1+

(B) 2 1 d+1−

(C) 2 1 d−1−

(D) 2 1 d+1+

Ans: (B)

Q.70 The average case of quick sort has order

(A) ( 2 ) O n (B) O(n)

(C) O(n log n) (D) O(log n)

Ans: (C)

AC05 Programming & Problem Solving Through ‘C’

AC06 Data Structures

14

Q.71 Inorder to get the information stored in a BST in the descending order, one should

traverse it in which of the following order?

(A) left, root, right (B) root, left, right

(C) right, root, left (D) right, left, root

Ans: (C)

Q.72 Every internal node in a B-tree of minimum degree 2 can have

(A) 2, 3 or 4 children (B) 1, 2 or 3 children

(C) 2, 4 or 6 children (D) 0, 2 or 4 children

Ans: (B)

Q.73 Which sorting algorithm is the best if the list is already in order?

(A) Quick sort (B) Merge sort

(C) Insertion sort (D) Heap sort

Ans: (C)

Q.74 In _________ the difference between the height of the left sub tree and height of right

sub tree, for each node, is not more than one

(A) BST (B) Complete Binary Tree

(C) AVL-tree (D) B-tree

Ans: (C)

Q.75 The number of comparisons required to sort 5 numbers in ascending order using bubble

sort is

(A) 7 (B) 6

(C) 10 (D) 5

Ans: (C)

Q.76 The complexity of adding two matrices of order m*n is

(A) m + n (B) mn

(C) max(m, n) (D) min(m, n)

Ans: (B)

Q.77 The second largest number from a set of n distinct numbers can be found in

(A) O(n) (B) O(2n)

(C) ( 2 ) O n (D) O(log n)

Ans: (A)

Q.78 If the inorder and preorder traversal of a binary tree are D,B,F,E,G,H,A,C and

A,B,D,E,F,G,H,C respectively then the postorder traversal of that tree is

(A) D,F,G,A,B,C,H,E (B) F,H,D,G,E,B,C,A

(C) C,G,H ,F,E,D,B,A (D) D,F,H,G,E,B,C,A

AC05 Programming & Problem Solving Through ‘C’

AC06 Data Structures

15

Ans: (D)

Q.79 In a binary tree, the number of terminal or leaf nodes is 10. The number of nodes with

two children is

(A) 9 (B) 11

(C) 15 (D) 20

Ans: (A)

Q.80 Which amongst the following cannot be a balance factor of any node of an AVL tree?

(A) 1 (B) 0

(C) 2 (D) –1

Ans: (C)

Q.81 How many distinct binary search trees can be formed which contains the integers 1, 2,

3?

(A) 6 (B) 5

(C) 4 (D) 3

Ans: (B)

Q.82 The sort which inserts each elements A(K) into proper position in the previously sorted

sub array A(1), ..., A(K–1)

(A) Insertion sort (B) Radix sort

(C) Merge sort (D) Bubble sort

Ans: (A)

Q.83 Direct or random access of elements is not possible in

(A) Linked list (B) Array

(C) String (D) None of these

Ans: (A)

Q.84 Level of any node of a tree is

(A) Height of its left subtree minus height of its right subtree

(B) Height of its right subtree minus height of its left subtree

(C) Its distance from the root

(D) None of these

Ans: (C)

Q.85 A desirable choice for the partitioning element in quick sort is

(A) First element of the list

(B) Last element of the list

(C) Randomly chosen element of the list

(D) Median of the list

Q.87 The result of evaluating the following postfix expression is

5, 7, 9, *, +, 4, 9, 3, /, +, -

(A) 50 (B) 65

(C) 61 (D) 69

Ans: (C)

Q.88 A graph with n vertices will definitely have a parallel edge or self loop if the total

number of edges are

(A) more than n (B) more than n+1

(C) more than (n+1)/2 (D) more than n(n-1)/2

Ans: (D)

Q.89 Out of the following, the slowest sorting procedure is

(A) Quick Sort (B) Heap Sort

(C) Shell Sort (D) Bubble Sort

Ans: (D)

Q.90 In ________, it is possible to traverse a tree without using stacks either implicitly or

explicitly.

(A) Threaded binary trees. (B) AVL Tree

(C) B+ tree (D) Heap

Ans: (C)

Q.91 The order of a B-Tree with 2, 3, 4 or 5 children in every internal node is

(A) 2 (B) 3

(C) 4 (D) 5

Ans: (C)

Q.92 The number of nodes that have no successors in a complete binary tree of depth 4 is

(A) 0 (B) 8

(C) 16 (D) 4

Ans: (B)

Q.93 One can make an exact replica of a Binary Search Tree by traversing it in

(A) Inorder (B) Preorder

(C) Postorder (D) Any order

Ans: (B)

Q.94 A complete Binary Tree with 15 nodes contains________edges

(A) 15 (B) 30

(C) 14 (D) 16

Ans: (C)

Q.95 The minimum number of comparisons required to find the largest number from 4

different numbers are

(A) 4 (B) 3

(C) 5 (D) 6

Ans: (B)

Q.96 An infix expression can be converted to a postfix expression using a

(A) Stack (B) Queue

(C) Dequeue (D) None of these

Ans: (A)

Q.97 A data structure in which an element is added and removed only from one end, is known

as

(A) Queue (B) Stack

(C) In-built structure (D) None of the above

Ans: (B)

Q.98 A complete binary tree with the property that the value of each node is at least as

large as the values of its children is known as

(A) Binary Search Tree. (B) AVL Tree.

(C) Heap. (D) Threaded Binary Tree.

Ans: (C)

Q.99 A sorting algorithm is stable if

(A) its time complexity is constant irrespective of the nature of input.

(B) preserves the original order of records with equal keys.

(C) its space complexity is constant irrespective of the nature of input.

(D) it sorts any volume of data in a constant time.

Ans: (B)

18

Q.100 A tree in which, for every node, the difference between the height of its left subtree

and right subtree is not more than one is

(A) AVL Tree. (B) Complete Binary Tree.

(C) B – Tree. (D)

+

B Tree.

Ans: (A)

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.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 [1] 2 n − (B) log 1 [1] 2 n +

(C)

---

log 1

---

 2 n + (D)

---

log 1

---

 2 n −

Ans: (C)

AC05 Programming & Problem Solving Through ‘C’

AC06 Data Structures

19

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

AC05 Programming & Problem Solving Through ‘C’

AC06 Data Structures

20

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

AC05 Programming & Problem Solving Through ‘C’

AC06 Data Structures

21

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)