Data Structures and Algorithm Analysis
Questions 161 to 170
161.

The optimal solution to a problem is a combination of
optimal solutions to its subproblems. This is known as


162.

Which of the following versions of merge sort algorithm
does uses space efficiently?


163.

Identify
the correct problem for multistage graph from the list given below.


164.

How
many edges are there in a Hamiltonian cycle if the edge cost is ‘c’ and the
cost of cycle is ‘cn’


165.

A
problem L is NPcomplete iff L is NPhard and


166.

What
would be the cost value for any answering node of a sub tree with root ‘r’
using branchbound algorithm?


167.

Name
the process which executes a correct program on data sets measuring the time
and space of a program, in order to compute the results


168.

What
would be the hash address for the following function by using the folding
method
H_{k} = H(4326)?


169.

Name
the node which has been generated but none of its children nodes have been
generated in state space tree of backtracking method.


170.

How many
nodes are there in a full state space tree with n = 6?

Answers
161.

Answer : (d)
Reason: According to the principle of optimality,
the optimal solution to a problem is a combination of optimal solutions to
its subproblems which are optimum.

162.

Answer : (c)
Reason: Because, in linked version auxiliary memory
is not required, as needed in array version.

163.

Answer : (a)
Reason: Because, the resource allocation problem
also same as allocating the right resource to appropriate person. The
remaining options are not suitable.

164.

Answer : (e)
Reason: Because. Simple in Hamiltonian graph there
should be exactly ‘n’ edges to connect all the nodes exactly once to form a
Hamiltonian cycle.

165.

Answer : (c)
Reason: According to the definitions of NPclass,
NPcomplete and NPhard class problems.

166.

Answer : (b)
Reason: Because the objective in branchbound
algorithms is to minimize the objective function.

167.

Answer : (d)
Reason: Because, in order to compute the results the
profiling process executes the correct program on data sets measuring the
time and space of a program. The remaining options are invalid.

168.

Answer : (a)
Reason: Because, according to folding method this is
43+26 which is 69.

169.

Answer : (b)
Reason: Because in state space tree organization
live node is a node which has been generated but none of its children nodes
have been generated, but are being generated.

170.

Answer : (c)
Reason: As this is 2^{n}1 ( i.e. 2^{6}1
= 63 ).

No comments :
Post a Comment