Data Structure II Practice Test 6

1. Which structure can be modelled by using Bipartite graph?

2. How many spanning trees does a complete bipartite graph contain?

3. How many times is the function recursive_get_len() called when the following code is executed?

#include<stdio.h>
#include<stdlib.h>
struct Node
{
      int val;
      struct Node *next;
}*head;
int recursive_get_len(struct Node *current_node)
{
      if(current_node == 0)
        return 0;
      return 1 + recursive_get_len(current_node->next);
}
int main()
{
      int arr[10] = {-1,2,3,-3,4,5}, n = 6, i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      temp = head;
      for(i=0; i<n; i++)
      {
          newNode = (struct Node*)malloc(sizeof(struct Node));
          newNode->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = recursive_get_len(head->next);
      printf("%d",len);
      return 0;
}

4. If Matrix A is of order X*Y and Matrix B is of order M*N, then what is the order of the Matrix A*B given that Y=M?

5. What is the time complexity of the following recursive implementation used to find the length of the string?

#include<stdio.h>
int recursive_get_len(char *s, int len)
{
      if(s[len] == 0)
        return 0;
      return 1 + recursive_get_len(s, len+1);
}
int main()
{
      char *s = "abcdef";
      int len = recursive_get_len(s,0);
      printf("%d",len);
      return 0;
}

6. What is the GCD of 48, 18, 0?

7. Recursion is a method in which the solution of a problem depends on ____________

8. Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity?

9. What will happen when the below code snippet is executed?

void my_recursive_function()
{
   my_recursive_function();
}
int main()
{
   my_recursive_function();
   return 0;
}

10. What is the time complexity of the above recursive implementation used to reverse a string?