# Data Structures and Algorithm Analysis Set 17

## Data Structures and Algorithm Analysis

### Questions 161 to 170

161.
The optimal solution to a problem is a combination of optimal solutions to its sub-problems. This is known as
 (a) Principle of Duality (b) Principle of Equality (c) Principle of Feasibility (d) Principle of Optimality (e) Principle of Dynamicity.
162.
Which of the following versions of merge sort algorithm does uses space efficiently?
 (a) Contiguous version (b) Array version (c) Linked version (d) Structure version (e) Heap version.
163.
Identify the correct problem for multistage graph from the list given below.
 (a) Resource allocation problem (b) Traveling salesperson problem (c) Producer consumer problem (d) Barber’s problem (e) Dining philosopher problem.
164.
How many edges are there in a Hamiltonian cycle if the edge cost is ‘c’ and the cost of cycle is ‘cn’
 (a) c (b) 2n (c) cn (d) 2c (e) n.
165.
A problem L is NP-complete iff L is NP-hard and
 (a) L ≈ NP (b) L α NP (c) L ε NP (d) L = NP (e) L ≠ NP.
166.
What would be the cost value for any answering node of a sub tree with root ‘r’ using branch-bound algorithm?
 (a) Maximum (b) Minimum (c) Optimal (d) Average (e) Negative.
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
 (a) Partitioning (b) Hashing (c) Validating (d) Profiling (e) Verifying.
168.
What would be the hash address for the following function by using the folding method
Hk = H(4326)?
 (a) 69 (b) 32 (c) 46 (d) 105 (e) 42
169.
Name the node which has been generated but none of its children nodes have been generated in state space tree of backtracking method.
 (a) Dead node (b) Live node (c) E-Node (d) State Node (e) Bounded Node.
170.
How many nodes are there in a full state space tree with n = 6?
 (a) 65 (b) 64 (c) 63 (d) 32 (e) 31

 161 Answer : (d) Reason:  According to the principle of optimality, the optimal solution to a problem is a combination of optimal solutions to its sub-problems 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 NP-class, NP-complete and NP-hard class problems. 166 Answer : (b) Reason:  Because the objective in branch-bound 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 2n-1 ( i.e. 26-1 = 63 ).

<< PrevNext >>