Data structure MCQ Set-10

1. 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
  • Live node
  • E-Node
  • State Node
2. How many nodes are there in a full state space tree with n = 6?
  • 65
  • 64
  • 63
  • 32
3. This algorithm scans the list by swapping the entries whenever pair of adjacent keys are out of desired order.
  • Insertion sort.
  • Bubble sort.
  • Shell sort.
  • Quick sort.
4. The  notation is
  • Symmetric
  • Reflexive
  • Transitive
  • B & C only
5. From the following chose the one which belongs to the algorithm paradigm other than to which others from the following belongs to.
  • Minimum & Maximum problem
  • Knapsack problem.
  • Selection problem.
  • Merge sort.
6. To calculatec(i, j )’s, w( i, j)’s and r(i, j)’s; the OBST algorithm in worst case takes the following time.
  • O(log n)
  •  O (n4)
  • O (n3)
  • O (n log n)
7. What is the type of the algorithm used in solving the 4 Queens problem?
  • Greedy
  • Dynamic
  • Branch and Bound
  • Backtracking.
8. In Knapsack problem, the best strategy to get the optimal solution, where Pi, Wi is the Profit, Weight associated with each of the Xith object respectively is to
  • Arrange the values Pi/Wi in ascending order
  • Arrange the values Pi/Xi in ascending order
  • Arrange the values Pi/Wi in descending order
  • Arrange the values Pi/Xi in descending order
9. Greedy job scheduling with deadlines algorithms’ complexity is defined as
  • O(N)
  • Ω( n log n)
  • O (n2 log n)
  • O ( n log n)
10. The divide and conquer merge sort algorithm’s time complexity can be defined as
  •  (long n)
  •  (n)
  • Ω (n log n)
  •   (n log n)