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.

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 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 ).

<< Prev  Set 1  Set 2  Set 3  Set 4  Set 5  Set 6  Set 7  Set 8  Set 9  Set 10  Set 11  Set 12  Set 13  Set 14  Set 15  Set 16  Set 17  Set 18  Set 19  Set 20  Set 21  Set 22  Set 23  Set 24  Set 25  Set 26  Set 27  Set 28  Set 29  Set 30  Next >>