Question 1

In the backtracking algorithm, if it is determined that a partial solution would end in a dead end, then the algorithm ____.

1. terminates

2. restarts

3. removes the most recently added part and tries other possibilities

4. was designed incorrectly

Question 2

void decToBin(int num, int base)
{
if(num > 0)
{
decToBin(num/base, base);
cout< }
}

Question 3

Given the recursive function above, what is the result of decToBin(39, 2)?

1. 10111

2. 10011

3. 100111

4. 110111

Question 4

int func1(int m, int n) {
if (m==n || n==1)
return 1;
else
return func1(m-1,n-1) + n*func1(m-1,n);
}

Question 5

Which of the following function calls would result in the value 1 being returned?

1. func1(0, 1)

2. func1(1, 0)

3. func1(2, 0)

4. func1(1, 2)

Question 6

int func2(int m, int n) {
if (n == 0)
return 0;
else
return m + func2(m, n-1);

}

Question 7

What is the output of func2(2, 3)?

1. 2

2. 3

3. 5

4. 6

Question 8

int func2(int m, int n) {
if (n == 0)
return 0;
else
return m + func2(m, n-1);
}

Question 9

Which of the following statements about the code above is always true?

1. func2(m,n) = func2(n, m) for m >= 0

2. func2(m,n) = m * n for n >=0

3. func2(m,n) = m + n for n >=0

4. func2(m, n) = n * m for n >=0

Question 10

int func1(int m, int n) {
if (m==n || n==1)
return 1;
else
return func1(m-1,n-1) + n*func1(m-1,n);
}

Question 11

How many base cases are in the function above?

1. 0

2. 1

3. 2

4. 3

Question 12

int func3(int m, int n) {
if (m < n)
return 0;
else
return 1 + func3(m-n, n);
}

Question 13

What is the value of func3(9, 7), based on the code above?

1. 0

2. 1

3. 2

4. 7

Question 14

int rFibNum(int a,int b,int n)
{
if(n==1)
return a;
else if(n==2)
return b;
else
return rFibNum(a,b,n-1) + rFibNum(a,b,n-2);
}

Question 15

What is the limiting condition of the code above?

n >= 0

a >= 1

b >= 1

n >= 1

Question 16

int exampleRecursion (int n)
{
if (n==0)
return 0;
else
return exampleRecursion(n-1) + n*n*n;
}

Question 17

What does the code above do?

1. Returns the cube of the number n

2. Returns the sum of the cubes of the numbers, 0 to n

3. Returns three times the number n

4. Returns the next number in a Fibonacci sequence

Question 18

int exampleRecursion (int n)
{
if (n==0)
return 0;
else
return exampleRecursion(n-1) + n*n*n;
}

Question 19

What is the output of exampleRecursion(3) ?

1. 25

2. 32

3. 36

4. 42