Design and Analysis MCQ Unit- III

 

Unit-III

1.      How many directions do queens attack each other?

A.    4
B.     2
C.    3

D.    5

2.      State space is
A.       All paths from root to other nodes define the state space of the problem
B.        Are rules, which restrict, each vector element to be chosen from given set
C.        All rules which determine which tuples in the solution space satisfy the criterion function

D.       None of these

 

3.      Explicit Constraints is

A.    All paths from root to other nodes define the state space of the problem

B.     Are rules, which restrict, each vector element to be chosen from given set

C.     All rules which determine which tuples in the solution space satisfy the criterion function
D.    None of these

 

4.      Which one not returns optimal solution?

A.    Backtracking

B.     Dynamic Programming
C.     Branch and Bounding

D.    Greedy Method

 

5.      Statement- I: Backtracking involves feasibility function.   
    Statement-II: Branch-and-Bound involves a bounding function.
    Statement III: Branch-and-Bound traverses the tree in any manner, DFS or BFS.Statement IV:             Backtracking traverses the state space tree by DFS[Depth First Search] manner.

A.    All are Correct
B.     Only IV is Wrong
C.     Only III is Wrong
D.    Only I,II is Wrong

 

6.      Which of the problems can be solved by backtracking method?

A.    4-queen problem
B.     insertion sort
C.     Travelling Salesman Problem
D.    Merge sort
 

7.      Backtracking is

A.    Depth first search with some bounding function
B.     Depth first search no bounding function
C.     Breath first search with some bounding function
D.    Breath first search no bounding function
 

 8.      Minimum number of unique colors required for vertex coloring of a graph is called?

 
A.    vertex matching
B.     chromatic number
C.     chromatic index
D.    color number
 
 
9.      Backtracking algorithm is
A.    Depth first search with some bounding function
B.     Depth first search no bounding function
C.     Breath first search with some bounding function
D.    Breath first search no bounding function
 
10.  Which of the problems can be solved by backtracking method?
A.    4-queen problem
B.     insertion sort
C.     Travelling Salesman Problem
D.    Merge sort
 
11.  Which one not returns optimal solution?
A.    Backtracking
B.     Dynamic Programming
C.     Branch and Bounding
D.    Greedy Method
 
12.  Backtracking used to solve
A.    Logical problems
B.     Exhaustive search
C.     Arithmetic problems
D.    Combinatorial problems
 
13.  What is vertex coloring of a graph?
 
A.     A condition where any two vertices having a common edge should always have same color.
B.     A condition where any two vertices having a common edge should not have same color.
C.     A condition where all vertices should have a different color.
D.    A condition where all vertices should have same color.
 
14.  Which one provides an optimal solution for 4-queens problem?
A.    (2,3,1,4)
B.     (4,3,2,1)
C.     (4,2,3,1)
D.    (3,1,4,2)
 
15.  Branch and bound is a __________
A.    problem solving technique
B.     data structure
C.     sorting algorithm
D.    type of tree
 
 
16.  Which of the following can traverse the state space tree only in DFS manner?
A.    branch and bound
B.     dynamic programming
C.     greedy algorithm
D.    backtracking
 
 
17.  Choose the correct statement from the following.
A.    branch and bound is more efficient than backtracking
B.     branch and bound is not suitable where a greedy algorithm is not applicable
C.    branch and bound divides a problem into at least 2 new restricted sub problems
D.    backtracking divides a problem into at least 2 new restricted sub problems
 
 
18.  The travelling salesman problem can be solved using _________
A.    A spanning tree
B.     A minimum spanning tree
C.     Bellman – Ford algorithm
D.    DFS traversal
 
19.  Which of the problems cannot be solved by backtracking method?
A.    n-queen problem
B.     subset sum problem
C.     Hamiltonian circuit problem
D.    travelling salesman problem
 
 
20.  Backtracking algorithm is implemented by constructing a tree of choices called as?
A.    State-space tree
B.     State-chart tree
C.     Node tree
D.    Backtracking tree
 
 
21.  What happens when the backtracking algorithm reaches a complete solution?
A.    It backtracks to the root
B.     It continues searching for other possible solutions
C.     It traverses from a different route
D. Recursively traverses through the same route
 
 
22.  In what manner is a state-space tree for a backtracking algorithm constructed?
A.    Depth-first search
B.     Breadth-first search
C.     Twice around the tree
D.    Nearest neighbour first
 
 
23.  The problem of placing n queens in a chessboard such that no two queens attack each other is called as?
A.    n-queen problem
B.     eight queens puzzle
C.     four queens puzzle
D.    1-queen problem
    
 
24.  For how many queens was the extended version of Eight Queen Puzzle applicable for n*n squares?
A.    5
B.     6
C.     8
D.    n
 
25.  What is the condition for proper coloring of a graph?
A.    two vertices having a common edge should not have same color
B.     two vertices having a common edge should always have same color
C.     all vertices should have a different color
D.    all vertices should have same color
 
 
26.  The number of colors used by a proper coloring graph is called?
A.    k coloring graph
B.     x coloring graph
C.     m coloring graph
D.    n coloring graph
 
 
27.  What is a chromatic number?
A.    The maximum number of colors required for proper edge coloring of graph
B.     The maximum number of colors required for proper vertex coloring of graph
C.    The minimum number of colors required for proper vertex coloring of graph
D.    The minimum number of colors required for proper edge coloring of graph
 
28.  What will be the chromatic number for an empty graph having n vertices?
A.    0
B.     1
C.     2
D.    n
 
29.  What will be the chromatic number for an bipartite graph having n vertices?
A.0
B.1
C.2
D. n
 
 
30.  What will be the chromatic number for a line graph having n vertices?
A.0
B.1
C.2

D.n