Data Structure II Practice Test 7

1. Under what case of Master’s theorem will the recurrence relation of stooge sort fall?

2. Under what case of Master’s theorem will the recurrence relation of binary search fall?

3. When was the Eight Queen Puzzle published?

4. The six queen puzzle has a fewer solution than the five queen puzzle.

5. What happens when the backtracking algorithm reaches a complete solution?

6. What is the output of the following code?

#include<stdio.h>
int recursive_search_num(int *arr, int num, int idx, int len)
{
     if(idx == len)
      return -1;
     if(arr[idx] == num)
      return idx;
     return recursive_search_num(arr, num, idx+1, len);
}
int main()
{
      int arr[8] ={-11,2,-3,0,3,5,-6,7},num = -2,len = 8;
      int indx = recursive_search_num(arr,num,0,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

7. What is the bidirectional variant of selection sort?

8. From the following given tree, what is the code word for the character ‘a’?

9. You are given infinite coins of denominations v1, v2, v3,.....,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________

10. What is the result of the recurrences which fall under second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=n^c?