Data Structure II Practice Test 7

1. When was the first solution to Eight Queen Puzzle published?

2. What is the space complexity of the following for loop method used to compute the nth fibonacci term?

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   prevFib = curFib
           curFib = nextFib
       return curFib

3. In dynamic programming, the technique of storing the previously calculated values is called ___________

4. When was the Eight Queen Puzzle published?

5. Which of the problems cannot be solved by backtracking method?

6. We can solve any recurrence by using Master’s theorem.

7. What is the bidirectional variant of selection sort?

8. What will be the recurrence relation of the following code?

int xpowy(int x, int n)
if (n==0) return 1;
if (n==1) return x;
if ((n % 2) == 0)
return xpowy(x*x, n/2);
else
return xpowy(x*x, n/2) * x;

9. What is the output of the following code?

#include<stdio.h>
#include<stdlib.h>
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      while(temp -> next != 0)
      {
            if(temp->val == value)
            return 1;
            temp = temp->next;
      }
      return 0;
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(60);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
     return 0;
}

10. If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________