# Data Structures and Algorithm Analysis Set 18

## Data Structures and Algorithm Analysis

### Questions 171 to 180

171.
Consider the following Traveling salesperson problem instance matrix. What would be the value of g(1, {2, 3})?
 ∞ 8 5 1 ∞ 7 2 3 ∞

 (a) 2 (b) 12 (c) 14 (d) 17 (e) 9
172.
The running time complexity of graph coloring problem is
 (a) O(nm) (b) O(mn) (c) O(mnm) (d) O(nmn) (e) O(mnnm).
173.
What is the time taken by the binary search algorithm to search a key ‘k’ in a sorted array of ‘n’ elements?
 (a) O(log2 n) (b) O(n) (c) (n log2 n) (d) O(n2) (e) O(1).
174.
Name the function which is used to kill live nodes without generating all their children in state space tree using backtracking method
 (a) Solution function (b) Bounding function (c) Optimal function (d) State Space function (e) Randomized function.
175.
Which of the following search method will always find a goal node nearest to the root of the tree?
 (a) Depth first search (b) Binary search (c) Breadth first search (d) Heuristic search (e) Randomized search.
176.
What do we call the selected keys in quick sort?
 (a) Recombine key (b) Inner key (c) Outer key (d) Pivot key (e) Median key.
177.
This sort finds location ‘pos’ of smallest elements in a(i), …. , a(n) and then interchange a(pos) with a(i) for i = 1, …., n – 1.
 (a) Selection sort (b) Quick sort (c) Heap sort (d) Bubble sort (e) Insertion sort.
178.
Adjacency matrix of a digraph is
 (a) Identity matrix (b) Symmetric matrix (c) Asymmetric matrix (d) Sparse matrix (e) Zero matrix.
179.
We can efficiently reverse a string using
 (a) Linear queue (b) Stack (c) Circular queue (d) Doubly linked list (e) Circular linked list.
180.
The technique of linear probing for collision resolution can lead to
 (a) Underflow (b) Radix ordering (c) Efficient storage utilization (d) Overflow (e) Clustering.