Design and Analysis of Algorithms Mid - II, November - 2014

1.To identify articulation points in a graph _________ is useful.
  • Game tree
  • in order traversal
  • dfs
  • none
Answer: C
2.The solid edges of the depth first spanning tree of the gragh are called _____ edges.
  • heavy
  • light
  • dark
  • tree
Answer: D
3.Two biconnected components can have at least _________ in common.
  • one vertex
  • two vertices
  • no vertex
  • one edge
Answer: A
4.In backtracking _______ constraints are the rules that determine the tuples of solution space.
  • explicit
  • implicit
  • bounding functions
  • permutation tree
Answer: A
5.The name backtrack was first coined by _____________
  • lehmer
  • Ullman
  • Thompson
  • bellman
Answer: A
6.If we represent solution space in the form of a __________tree.
  • BFS
  • DFS
  • State space
  • min cost spanning tree
Answer: C
7.A node is generated but its children not generated called ____ node.
  • live
  • dead
  • expaned
  • x
Answer: A
8.If n = 4 the possible leaf nodes in the tree organization are ___________
  • 4
  • 8
  • 20
  • 16
Answer: D
9.Branch and bound technique is applicable for ________ problem.
  • minimization
  • maximization
  • reliability
  • BFS
Answer: A
10.A graph cannot be drawn on a plane without cross over between its edges called ______.
  • planar
  • non planar
  • euler
  • directed
Answer: B
11.Number of external nodes in a binary tree with n identifiers is ________________.
Answer: Dynamic programming
12.The ______________ states that what ever the intial state and decision are, the remaining decisions must constitute an optimal decision sequence.
Answer: N
13.Each node in the problem state space is called ______________.
Answer: Optimal
14.In n-queens problem nodes are numbered as in ______________.
Answer: E-node
15._____________ constraints describe the way in which xi must relate to each other.
Answer: 24
16.A dead node cannot be __________________,
Answer: State space
17.A dead node cannot be __________________,
Answer: Expanded
18.All deterministic search algorithms have time complexity of ______________.
Answer: Decision problem
19.The computing time for choice, success and failure is _______________
Answer: Polynomial
20.____________ algorithms have the property that the result of every operation is uniquely defined.
Answer: Deterministic