DATA STRUCTURE AND ALGORITHMS MCQ GATE NET SET – 10

This entry was posted in DATA STRUCTURE AND ALGORITHMS MCQ on March 23, 2017 by nikhilarora

---

101. The maximum number of comparisons needed to sort 7 items using radix sort is (assume each item is a 4 digit decimal number)
     1. 280
     2. 40
     3. 47
     4. 38

102. If each node in a tree has a value greater than every value in its left sub tree and has value less than every value in its right sub tree, the binary tree is known as
     1. Complete binary tree
     2. Full binary tree
     3. Binary search tree
     4. Threaded binary tree
103. 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 as possible, is known as
     1. full binary tree
     2. 2-tree
     3. threaded tree
     4. Complete binary tree

104. You are asked 15 randomly generated numbers. You should prefer
     1. bubble sort
     2. quick sort
     3. merge sort
     4. heap sort

105. Which data structure is needed to convert infix notation to post fix notation
     1. B-tee
     2. Queue
     3. Tree
     4. Stack

106. The time required to search an element in a binary search tree having n elements is
     1. O(1)
     2. O(log₂ n)
     3. O(n)
     4. O(n log₂ n)

107. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is
     1. log₂ n
     2. n-1
     3. n
     4. 2ⁿ

108. A tree, for which at every node the height of its left sub tree and right sub tree differ at most by one is a/an
     1. Binary search tree
     2. AVL tree
     3. Complete binary tree
     4. Threaded binary tree

109. Which of the following sorting algorithms does not have a worst case running time complexity of O(n²)?
     1. Insertion sort
     2. Merge sort
     3. Quick sort
     4. Bubble sort

110. Which of the following is not a correct statement
     1. internal sorting is used if the number of items to be sorted is very large
     2. External sorting is used if the number of items to be sorted is very large
     3. External sorting needs auxiliary storage
     4. Internal sorting needs auxiliary storage

111. There are 4 different algorithms A1,A2,A3,A4 to solve a given problem with the order log(n),log(log(n)),nlog(n),n/log(n) respectively. Which is the best algorithm?
     1. A1
     2. A2
     3. A3
     4. A4

112. Which of the following algorithms exhibits the unusual behavior that, minimum numbers of comparisons are needed if the list to be sorted is in the reverse order and maximum numbers of comparisons are needed if they are already in sorted order?
     1. Heap tree
     2. Radix sort
     3. Binary insertion sort
     4. Selection sort
113. You want to check whether a given set of items is sorted. Which of the following sorting methods will be the most efficient if it is already in sorted order?
     1. bubble sort
     2. selection sort
     3. insertion sort
     4. merge sort
114. The way a card game player arranges his cards as he picks them up one by one , is an example of
     1. bubble sort
     2. selection sort
     3. insertion sort
     4. merge sort
115. Which of the following sorting algorithm has the worst time complexity of nlog(n)?
     1. Heap sort
     2. Quick sort
     3. Insertion sort
     4. Selection sort

116. Which of the following sorting methods sorts a given set of items that is already in sorted order or in reverse sorted order with equal speed?
     1. Heap sort
     2. Quick sort
     3. Insertion sort
     4. Selection sort

117. Which of the following sorting methods will be the best if number of swapping done, is the only measure of efficiency?
     1. bubble sort
     2. insertion sort
     3. selection sort
     4. heap sort

118. As part of the maintenance work, you are entrusted with the work of rearranging the library books in a shelf in proper order, at the end of each day. The ideal choice will be
     1. bubble sort
     2. insertion sort
     3. selection sort
     4. heap sort

119. Sorting is not useful for
     1. report generation
     2. minimizing the storage needed
     3. making searching easier and efficient
     4. responding to queries easily

120. A machine took 200 sec to sort 200 names, using bubble sort. In 800 sec. it can approximately sort _ _ _ _ _ _ _ _ _ names
     1. 400
     2. 800
     3. 750
     4. 1600

122. A sorting method with _ _ _ _ _ _ _ _ is the most efficient method
     1. O(log n)
     2. O(n)
     3. O(1)
     4. O(n²)

123. Which of the following statement is false?
     1. Optimal binary search construction can be performed efficiently using dynamic programming
     2. Breadth-first search cannot be used to find connected components of a graph
     3. Given the prefix and postfix walks of a binary tree, the binary cannot be uniquely reconstructed
     4. Depth-first search can be used to find the connected components of a graph
124. The average successful search time for sequential search on ‘n’ items is
     1. n/2
     2. (n-1)/2
     3. (n+1)/2
     4. log(n)+1
125. A hash function f defined as f(key)=key mod 7, with linear probing, is used to insert the keys 37,38,72,48,98,1,56, into a table indexed from 0 to 6. What will be the location of key 11?
     1. 3
     2. 4
     3. 5
     4. 6
126. The order of the binary search algorithm is
     1. n
     2. n²
     3. nlog(n)
     4. log(n)

127. Linked lists are not suitable for implementing
     1. insertion sort
     2. binary search
     3. radix sort
     4. polynomial manipulation

128. Stack is useful for
     1. radix sort
     2. breadth first search
     3. heap sort
     4. depth first search

129. Which of the following algorithm design technique is used in the quick sort algorithm?
     1. Dynamic programming
     2. Backtracking
     3. Divide and conquer
     4. Greedy method

131. A 3-ary tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will be
     1. 10
     2. 17
     3. 23
     4. 13

132. Which of the following traversal techniques lists the nodes of a binary search tree in ascending order?
     1. post-order
     2. In-order
     3. Pre-order
     4. No-order

133. A general linear list is a list in which operations, such as retrievals, insertions, changes, and deletions can be done _ _ _ _ _ _ _ _ _
     1. any where in the list
     2. only at the beginning
     3. only at the end
     4. only at the middle

134. A(n) _ _ _ _ _ _ _ is a collection of elements and relationship Among them.
     1. abstract data type
     2. array
     3. data structure
     4. standard type
135. Data that consists of a single, non decomposable entity are known as _ _ _ _ _ _
     1. atomic data
     2. array
     3. data structure
     4. standard type

136. A binary tree has n leaf nodes. The number of nodes of degree 2 in this tree is
     1. logn
     2. n-1
     3. n
     4. 2ⁿ

137. A full binary tree with n leaf nodes contains
     1. n nodes
     2. log₂ n nodes
     3. 2n-1 nodes
     4. 2n nodes
138. The number of binary trees with 3 nodes which when traversed in post-order gives the sequence A,B,C is
     1. 3
     2. 9
     3. 7
     4. 5

139. Which of the following need not be a binary tree?
     1. Search tree
     2. Heap
     3. AVL-tree
     4. B-tree

140. A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree.Such a tree with 10 leaves
     1. cannot be more than 19 nodes
     2. has exactly 19 nodes
     3. has exactly 17 nodes
     4. can not have more than 17 nodes

141. Find the odd man out
     1. binary tree
     2. Avl tree
     3. graph
     4. queue

142. The depth of a complete binary tree with n nodes(log is to the base two)
     1. log(n+1)-1
     2. log(n)
     3. log(n+1)+1
     4. log(n)+1

143. The following is an example of a non-linear data structure
     1. stack
     2. queue
     3. tree
     4. linear list
144. If a graph is represented as a linked list, _ _ _ _ _ _ _ _ _ no.of list nodes are required
     1. 1
     2. 2
     3. 3
     4. 4

145. The number of possible binary trees with 4 nodes is
     1. 12
     2. 14
     3. 13
     4. 15

146. The number of possible binary trees with 3 nodes is
     1. 12
     2. 13
     3. 5
     4. 15
147. The number of possible ordered trees with 3 nodes A,B,C is
     1. 16
     2. 12
     3. 6
     4. 10

148. A tree is a _ _ _ _ _ data structure
     1. non-recursive
     2. recursive
     3. linear
     4. non-linear

149. A node that does not have any sub-tree is called a _ _ _ _ _ _ _
     1. terminal node
     2. root node
     3. left node
     4. right node

150. The number of edges in a regular graph of degree d and n vertices is
     1. maximum of n, d
     2. n+d
     3. nd
     4. nd/2

---