DATASTRUCTURE AND ALGORITHMS MCQ GATE NET SET – 11

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

---

151. Which of the following algorithms solves the all pair shortest path problem?
     1. Diskstra’s algorithm
     2. Floyd algorithm
     3. Prim’s algorithm
     4. Warshall’s algorithm

152. The minimum number of colors required to color a graph having n (n>3) vertices and 2 edges is
     1. 4
     2. 3
     3. 2
     4. 1
153. The maximum degree of any vertex in a simple graph with n vertices is
     1. n
     2. n-1
     3. n+1
     4. 2n-1

154. A graph G with n nodes is bipartite if it contains
     1. n edges
     2. a cycle of odd length
     3. no cycle of odd length
     4. n² edges

155. A graph can be represented as an _ _ _ _ _ _
     1. Linked list
     2. Structure
     3. Union
     4. Queue

156. A graph can be represented as an _ _ _ _ _ _
     1. Array
     2. Structure
     3. Union
     4. Queue

157. The minimum number of edges in a connected cyclic on n vertices is
     1. n-1
     2. n
     3. n+1
     4. n+2

158. Which of he following is useful in traversing a given graph by breadth first search?
     1. Stack
     2. Set
     3. List
     4. Queue

159. Sparse matrices have
     1. many zero entries
     2. many non-zero entries
     3. higher dimensions
     4. lower dimensions

160. The maximum no.of edges in an undirected graph with out loops with n vertices is
     1. n
     2. n*(n-1)
     3. n*(n-1)/2
     4. n-1
161. Which of the following abstract data types can be used to represent a many to many relationship
     1. tree
     2. graph
     3. queue
     4. stack

162. In a directed graph without self loops with n verices , the maximum no.of edges is
     1. n
     2. n*(n-1)
     3. n*(n-1)/2
     4. n-1

163. An n vertex undirected graph with exactly n*(n-1)/2 edges is said to be
     1. Complete graph
     2. Un complete graph
     3. Directed graph
     4. Un directed graph

164. To create a node dynamically in a singly linked list _ _ function in C is used
     1. malloc()
     2. calloc()
     3. alloc()
     4. dealloc()

165. In an undirected graph, the sum of degrees of all the nodes
     1. must be even
     2. is thrice the number of edges
     3. must be odd
     4. need not be even

166. In an undirected graph, the sum of degrees of all the nodes
     1. is thrice the number of edges
     2. is twice the number of edges
     3. must be odd
     4. need not be even

167. _ _ _ function is used to in C to dynamically allocate space for more than one object
     1. malloc()
     2. calloc()
     3. alloc()
     4. dealloc()

168. _ _ _ function is used to in C to dynamically allocate space for one object
     1. malloc()
     2. calloc()
     3. alloc()
     4. dealloc()

169. If n=2, then the value of O(n log n) is
     1. 2
     2. 4
     3. 8
     4. 16

170. Calloc(m,n); is equivalent to
     1. malloc(m*n,0);
     2. memset(0,m*n);
     3. ptr=malloc(m*n);memset(p,0,m*n)
     4. ptr=malloc(m*n);strcpy(p,0)
171. If the sequence of operations push(1),push(2) ,pop, push(1),push(2),pop, pop, pop, push(2),pop, are performed on a stack, the sequence of popped out values are
     1. 2,2,1,1,2
     2. 2,2,1,2,2
     3. 2,1,2,2,1
     4. 2,1,2,2,2

172. return type of a realloc( ) function is
     1. int
     2. float
     3. char
     4. void

173. To delete an element from a queue we use the _ _ _ _ _ operation
     1. pop
     2. push
     3. enqueue
     4. dequeue

174. To add an element to a queue we use the _ _ _ _ _ operation
     1. pop
     2. push
     3. enqueue
     4. dequeue
175. Which of the memory function allocates a contiguous memory
     1. malloc( )
     2. calloc( )
     3. release( )
     4. free( )

176. Return type of a malloc( ) function is
     1. int
     2. float
     3. char
     4. void

177. A queue is a _ _ _ _ _ _ structure
     1. first in-last out
     2. lasting-first-out
     3. first in-first out
     4. last in-last out
178. A queue is a list in which insertion can be done _ _ _ _
     1. any where in the list
     2. only at the beginning
     3. only at the end
     4. only at the middle
179. A _ _ _ _ _ _ is a first in – last out(FIFO) data structure in which insertions are restricted to one end, called the rear, and deletions are restricted to another end ,called the front
     1. Stack
     2. queue
     3. tree
     4. binary tree

180. The pointer(s) in a queue points to
     1. start of the queue
     2. end of the queue
     3. middle of the queue
     4. both start and end of the queue

181. The disadvantage of the queue is
     1. when the item is deleted, the space for that item is not claimed
     2. when the item is deleted, the space for that item is claimed
     3. a non destructive
     4. increases the memory space

182. A queue is a list in which deletion can be done _ _ _ _
     1. any where in the list
     2. only at the beginning
     3. only at the end
     4. only at the middle

183. Read() operation in queue is
     1. non-destructive
     2. additive
     3. push()
     4. destructive

184. In which of the data structure, space for the item is not claimed ,when an item is deleted
     1. queue
     2. circular queue
     3. stack
     4. linked list

185. As the items from a queue get deleted, the space for item is not reclaimed in queue. This problem is solved by
     1. circular queue
     2. stack
     3. linked list
     4. doubly linked list

186. Which of the following operation is used to add an item in a queue
     1. write()
     2. read()
     3. pop()
     4. push()

187. _ _ _ _ no.of pointers are required to implement read and write operations in a queue
     1. two
     2. three
     3. four
     4. five

188. FIFO is
     1. stack
     2. queue
     3. linked list
     4. tree

189. Which of the following operation is used to an item in a queue
     1. write()
     2. read()
     3. pop()
     4. push()

190. The number of swapping needed to sort the numbers 8,22,7,9,31,19,5,13 in an ascending order, using bubble sort is
     1. 11
     2. 12
     3. 13
     4. 14

191. Given two sorted list of size ‘m’ and ‘n’ respectively. The number of comparisons needed by the merge sort algorithm will be
     1. m x n
     2. maximum of m,n
     3. minimum of m,n
     4. m+n-1
192. For merging two sorted lists of sizes m and n into a sorted list of size m+n, requires _ _ _ _ _ _ _ _ no.of comparisons
     1. O(m)
     2. O(n)
     3. O(m+n)
     4. O(log(m)+log(n))
193. The principle of locality justifies the use of
     1. interrupts
     2. DMA
     3. polling
     4. cache memory

194. The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list could be used?
     1. Singly linked list
     2. Doubly linked list
     3. Circularly doubly linked list
     4. Array implementation of list
195. The initial condition of a queue is
     1. front=rear=-1
     2. front=rear
     3. front=rear=n
     4. front=rear=1

196. A sorting technique that guarantees , that records with the same primary key occurs in the same order in the sorted list as in the original unsorted list is said to be
     1. stable
     2. consistent
     3. external
     4. linear

197. The average number of comparisons performed by the merge sort algorithm , in merging two sorted lists of length 2 is
     1. 8/3
     2. 8/5
     3. 11/7 
     4. 1/16

198. Merge sort uses
     1. divide and conquer strategy
     2. backtracking approach
     3. heuristic approach
     4. greedy approach

199. Queue can be used to implement
     1. radix sort
     2. quick sort
     3. recursion
     4. depth first search

---