Data Structure II Practice Test 4

1. What is the total running time of the binary GCD algorithm?

O(log N)

O(N²)

O(N)

O(N log N)

2. Given the program of naïve method.

for i=1 to n do
   for j=1 to n do
       Z[i][j]=0;
       for k=1 to n do 
            ___________________________

Fill in the blanks with appropriate formula

Z[i][j] = Z[i][j] * X[i][k] + Y[k][j]

Z[i][j] = Z[i][j] * X[i][k]*Y[k][j]

Z[i][j] = Z[i][j] + X[i][k]*Y[k][j]

Z[i][j] = Z[i][j] + X[i][k] + Y[k][j]

3. What will be the output of the following code?

#include<iostream>
using namespace std;
int list[200];
void func(int n, int m = 0)
{
    int i;
    if(n == 0)
    {
         for(i = 0; i < m; ++i)
         printf("%d ", list[i]);
         printf("\n");
         return;
    }
    for(i = n; i > 0; --i)
    {
         if(m == 0 || i <= list[m - 1])
         {
             list[m] = i;
             func(n - i, m + 1);
         }
    }

}
int main()
{
	int n=3;
	func(n,0);
	return 0;
}

  3 
  2 1
  1 1 1

  1 1 1
  2 1
  3

   3
   1 2
   1 1 1

  1 1 1
  1 2
  3

4. What is the correct formula for generating random numbers in the range (lower,upper) using rand()?

rand() + lower

rand() % (upper - lower)

(rand()%(upper-lower)) + lower

(rand()%(upper-lower+1)) + lower

5. What is the running time of Chan’s algorithm?

O(n log h)

O(n log n)

O(log h)

O(log n)

6. Which of the following represent the correct pseudo code for non recursive DFS algorithm?

 
procedure DFS-non_recursive(G,v):
  //let St be a stack 
  St.push(v)
  while St is not empty
    v = St.pop()
    if v is not discovered:
      label v as discovered
      for all adjacent vertices of v do
        St.push(v)

procedure DFS-non_recursive(G,v):
  //let St be a stack 
  St.push(v)
  while St is not empty
    v = St.pop()
    if v is not discovered:
      label v as discovered
      for all adjacent vertices of v do
        St.push(a) //a being the adjacent vertex

procedure DFS-non_recursive(G,v):
  //let St be a stack 
  St.pop(v)
  while St is not empty
    v = St.pop()
    if v is not discovered:
      label v as discovered
      for all adjacent vertices of v do
        St.push(a) //a being the adjacent vertex

procedure DFS-non_recursive(G,v):
  //let St be a stack 
  St.pop()
  while St is not empty
    v = St.push(v)
    if v is not discovered:
      label v as discovered
      for all adjacent vertices of v do
        St.push(a) //a being the adjacent vertex

7. How many approaches can be applied to solve quick hull problem?

8. What is the recurrence relation used in Strassen’s algorithm?

7T(n/2) + O(n²)

7T(n/2) + Theta(n²)

8T(n/2) + Theta(n²)

8T(n/2) + O(n²)

9. Strassen’s algorithm is quite numerically stable as the naïve method.

True

False

10. Who invented the concept of inclusion-exclusion principle?

Daniel Silva

Abraham de Moivre

Sieve

J.J. Sylvester