DAA Unit IV Quiz

Consider the following graph for Travelling Salesman Problem. Compute the bound value for root node

• 28

• 25

• 27

• 29

What is the data structure used to implement backtracking technique?

• Queue

• Stack

• Trees

• Linked List

The state space tree is used in
------------- technique to construct the solution.

• Greedy

• Dynamic

• Backtracking

• Brute Force

In the Sum of Subsets Problem the state space tree will be in the form of a ------------

• Binary Search Tree

• Binary Tree

• Heap

• AVL Tree

How many Hamiltonian paths does the following graph have?

• 1

• 2

• 3

• 4

Which of the following is a Hamilton circuit of the graph?

• ABCDEFGA

• CEGBADFC

• CBGEDFAC

• ACBEGFDA

Consider the knapsack instance: n = 6; (p1, p2, p3, p4, p5, p6) = (40,35,18,4,10,2); (w1, w2, w3, w4, w5, w6) = (5,7,2,4,5,1) and M = 15. What is the upper bound value with item 3, item 1, without item 5 and with item 6.

• 93

• 94

• 95

• 96

What is a subset sum problem?

• Finding a subset of a set that has sum of elements equal to a given number

• Finding the sum of elements present in a set

• Finding the sum of all the subsets of a set

• Checking for the presence of a subset that has sum of elements equal to a given number

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

• Dead node

• Start node

• Live node

• E-node

In Knapsack problem, the best strategy to get the optimal solution, where Pi, Wi is the Profit, Weight associated with each of the Xi^th object respectively is to____________

• Arrange the values Pi/Wi in ascending order

• Arrange the values Pi/Xi in descending order

• Arrange the values Pi/Wi in descending order

• Arrange the values Pi/Xi in ascending order