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})?


172.

The
running time complexity of graph coloring problem is


173.

What
is the time taken by the binary search algorithm to search a key ‘k’ in a
sorted array of ‘n’ elements?


174.

Name
the function which is used to kill live nodes without generating all their
children in state space tree using backtracking method


175.

Which of the
following search method will always find a goal node nearest to the root of
the tree?


176.

What
do we call the selected keys in quick sort?


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.


178.

Adjacency
matrix of a digraph is


179.

We
can efficiently reverse a string using


180.

The
technique of linear probing for collision resolution can lead to


Answers
171.

Answer : (e)
Reason : This is g( 1, {2,3}) = min( C_{12 }+ g( 2,
{3}), C_{13 }+ g( 3, {2})
= min( 8+9, 5+4 ) =
9.

172.

Answer : (d)
Reason: According to the complexity analysis of the
algorithm.

173.

Answer : (a)
Reason: According to the mathematical analysis
binary search takes ( log_{2} n ) time.

174.

Answer : (b)
Reason: Because, in state space tree generation of
backtracking approach a bounding function is used to kill live nodes without
generating all their children, if that node is not promising the solution.

175.

Answer : (c)
Reason: Because in this method nodes are generated
level by level and hence the goal node is found nearest to root node.

176.

Answer : (d)
Reason: Because, in quick sort division is made
along the pivotal element.

177.

Answer : (a)
Reason: As this process is the key process for the
selection sort algorithm.

178.

Answer : (c)
Reason: Because, in a diagraph for directed edge <a, b>; b is
adjacent to a, but reverse is not true. Hence the adjacency matrix is
asymmetric matrix.

179.

Answer : (b)
Reason: This is nothing but pushing the characters
of the string in a stack and then popping the stack to get the reversed order
of the string.

180.

Answer : (e)
Reason: Because, if we follow the linear probing
method to resolve the collision then it may lead to the clustering.

No comments :
Post a Comment