Re: Brian Kernighan, maybe I'm not worthy, maybe I'm scum

The Spinoza challenge continues!

I got 79% on the test on Recursion, using C examples, at
http://www.sparknotes.com/cs/recursion/review/quiz.html.

Here are my answers and the correct answers.

Take the test closed book and without prep. Don't discount the
errorneous questions to be fair to everyone taking the Challenge. I
personally won't complain about the errors in the test, since my goal
is to reduce the negative reinterpretations of what people say and who
they are, based on ignorance, which generates the cyber-bullying in
this newsgroup.



.. To recurse is to
(A) Practice recursion
(B) Swear again **** "CORRECT" ANSWER ****
(C) Neither of the above **** MY ANSWER, ("DAMMIT :=)")+

2. To recur is to
(A) Practice recursion **** CORRECT ANSWER ****
(B) Swear again
(C) Neither of the above **** MY ANSWER ****

3. Factorial is
(A) a good introductory example of recursion, but a function better
implemented iteratively for efficiency reasons. **** MY ANSWER/CORRECT
ANSWER ****
(B) a good introductory example of recursion, and a function best
implemented recursively.
(C) a bad introductory example of recursion as it hard to implement
recursively.

4. factorial(0) is
(A) 0
(B) 1 **** CORRECT ANSWER ****
(C) Infinity
(D) Undefined **** MY ANSWER ****
(E) None of the above

5. Recursion is
(A) a powerful construct theoretically, but rarely used in actual
programs.
(B) a weak construct theoretically rarely used in actual programs.
(C) a powerful construct theoretically, often used in certain
applications that benefit from recursive methods. **** MY ANSWER/
CORRECT ANSWER ****

6. Which of the following is not a requirement for a recursive
function?
(A) It has two base cases.
(B) It has a recursive case
(C) Its recursive case approaches a base case. **** MY ANSWER/CORRECT
ANSWER ****

7. The function
int example(unsigned int a)
{
if (a==0) return 0;
else return example(a+1);
}

is a bad recursive function because
(A) it has no recursive case.
(B) it has no base case.
(C) the recursive case does not approach the base case. **** MY ANSWER/
CORRECT ANSWER ****

8. Is the following function circular?
int syracuse(int n)
{
if (n==1) return 0;
else if (n % 2 != 0) return syracuse(n/2);
else return 1 + syracuse(3*n + 1);
}

(A) Yes **** MY ANSWER ****
(B) No
(C) We don't know. **** CORRECT ANSWER ****

9. True or False: A call stack is made up of frames.
(A) True **** MY ANSWER/CORRECT ANSWER ****
(B) False

10. True or False: During program execution, the call stack can be
empty.
(A) True
(B) False **** MY ANSWER/CORRECT ANSWER ****

11. True or False: Because a recursive function calls itself, a
different mechanism than the call stack is used to keep track of the
function calls.
(A) True
(B) False **** MY ANSWER/CORRECT ANSWER ****

12. As a data structure, a call stack is most analogous to
(A) A supermarket line
(B) A cafeteria tray dispenser **** MY ANSWER/CORRECT ANSWER ****
(C) A small family of weebles
(D) A genealogical family chart

13. If you were to draw out the function call tree for Fib3, how many
function calls would there be in terms of big-O notation?
(A) O(n2) **** MY ANSWER ****
(B) O(2n)
(C) O(n!)
(D) O(3n) **** CORRECT ANSWER ****

14. A stack is an example of a ____ data structure.
(A) FIFO
(B) LIFO **** MY ANSWER/CORRECT ANSWER ****

15. A queue is an example of a _____ data structure.
(A) FIFO **** MY ANSWER/CORRECT ANSWER ****
(B) LIFO

16. True or false: Regardless of implementation, the closed-form
solution to the Fibonacci problem is always more efficient than a
recursive implementation.
(A) True
(B) False **** MY ANSWER/CORRECT ANSWER ****

17. True or false: A linearly recursive function always has the
recursive call at the end of the function.
(A) True
(B) False **** MY ANSWER/CORRECT ANSWER ****

18. True or false: Tail recursion is a form of linear recursion.
(A) True **** MY ANSWER/CORRECT ANSWER ****
(B) False

19. The following function is an example of what form of recursion?
int mystery(int n, int k)
{
if (k == 0 || n == k) return(1);
else return(mystery(n-1,k) + mystery(n-1,k-1));
}

(A) Linear recursion
(B) Binary recursion **** MY ANSWER/CORRECT ANSWER ****
(C) Nested recursion
(D) Mutual recursion

20. The following function implements what recursive function?
int mystery(char *s)
{
if (*s=='\0') return 0;
else return(1 + mystery(s+1));
}

(A) strlen() **** MY ANSWER/CORRECT ANSWER ****
(B) strcmp()
(C) strstr()
(D) strchr()

21. What does the following function do?
int strcmp_i(char *s, char *t)
{
for(; *s==*t && *s!='\0'; s,t);
return(*s - *t);
}

(A) strlen()
(B) strcmp() **** MY ANSWER/CORRECT ANSWER ****
(C) strstr()
(D) strchr()

22. True or False: Merge sort is an example of a divide-and-conquer
sort.
(A) True **** MY ANSWER/CORRECT ANSWER ****
(B) False

23. True or False: All recursive functions can be implemented
iteratively.
(A) True **** MY ANSWER ****
(B) False **** CORRECT ANSWER ****

24. True or False: All iterative functions can be implemented
recursively.
(A) True **** MY ANSWER/CORRECT ANSWER ****
(B) False

25. What does this function do?
void mystery(int num)
{
if (num / 8) mystery(num / 8);
putchar(num % 8 + '0');
}

(A) Counts the number of bits that are 1 in a number.
(B) Sums all the bits in a number.
(C) Prints out a number in decimal notation.
(D) Prints out a number in octal notation. **** MY ANSWER/CORRECT
ANSWER ****

26. This function is an example of what type of recursion?
int fib_r(int n)
{
if (n<=1) return 1;
else return(fib_r(n-1) + fib_r(n-2));
}

(A) Linear recursion
(B) Tail recursion
(C) Binary recursion **** MY ANSWER/CORRECT ANSWER ****
(D) Nested recursion

27. Which of the following data structures could be considered a
recursive data structure?
(A) Linked lists
(B) Trees
(C) Both of the above **** MY ANSWER/CORRECT ANSWER ****
(D) None of the above

28. A recursive data structure is what?
(A) A data structure that is used in a recursive function.
(B) A data structure that contains no references to itself.
(C) A data structure that contains references to itself. **** MY
ANSWER/CORRECT ANSWER ****
(D) None of the above

29. fib(5) is
(A) 2
(B) 3
(C) 5 **** CORRECT ANSWER ****
(D) 8 **** MY ANSWER ****

30. factorial(4) is
(A) 0
(B) 24 **** MY ANSWER/CORRECT ANSWER ****
(C) 12
(D) 36

31. True or False: If a recursive function does not have a base case,
the compiler will detect this and display a compiler error.
(A) True
(B) False **** MY ANSWER/CORRECT ANSWER ****

32. True or False: A recursive function must have a void return type.
(A) True
(B) False **** MY ANSWER/CORRECT ANSWER ****

33. True or False: Recursive calls are usually contained within a
loop.
(A) True
(B) False **** MY ANSWER/CORRECT ANSWER ****

34. True or False: It is possible to have more than one recursive call
within a function.
(A) True **** MY ANSWER/CORRECT ANSWER ****
(B) False

35. True or False: Binary search can only be written recursively.
(A) True
(B) False **** MY ANSWER/CORRECT ANSWER ****

36. Which of these statements is true about the following code?
int mystery(int n)
{
if (n>0) return n + mystery(n-1);
return 0;
}

(A) The base case for this recursive method is an argument with any
value which is less than or equal to zero. **** MY ANSWER/CORRECT
ANSWER ****
(B) The base case for this recursive method is an argument with any
value which is greater than zero.
(C) The base case for this recursive function is an argument with the
value zero.
(D) There is no base case.

37. Which of the following iterative functions is not equivalent to
this recursive function?
int mystery(int n)
{
if(n > 0) return (n + mystery(n - 1));
return 0;
}

(A)
int mystery(int n)
{
int sum = 0;
while (n > 0) {
sum = sum + n;
n--;
}
return sum;
}

(B)
int mystery(int n)
{
int j = 0, sum = 0;
while (j < n) {
j++;
sum = sum + j;
}
return sum;
}

(C) **** MY ANSWER/CORRECT ANSWER ****
int mystery(int n)
{
int sum;
while (n > 0) {
sum = 0;
sum = sum + n;
n--;
}
return sum;
}


38. True or False: When a recursive solution's elegance outweighs its
overhead (memory, time, efficiency, etc), and when it is much less
complex than an iterative solution, you would most likely choose to
use the recursive solution.
(A) True **** MY ANSWER/CORRECT ANSWER ****
(B) False

39. True or False: You should always use a recursive solution rather
than an iterative solution when you are sure that that recursive
solution will not overflow the call stack.
(A) True
(B) False **** MY ANSWER/CORRECT ANSWER ****

40. Recursion can be an inefficient way to implement a solution
because
(A) using the call stack to store states adds significant overhead.
(B) calling a function multiple times could be reduced to looping,
which might better done with a looping structure such as a while
construct.
(C) Both of the above. **** MY ANSWER/CORRECT ANSWER ****

41. True or False: Recursion happens when an algorithm does not use a
loop.
(A) True
(B) False **** MY ANSWER/CORRECT ANSWER ****

42. True or False: A function can be considered recursive if it has a
direct or an indirect call to itself.
(A) True **** MY ANSWER/CORRECT ANSWER ****
(B) False

43. True or False: Infinite recursion can occur when a recursive
algorithm does not contain a base case.
(A) True **** MY ANSWER/CORRECT ANSWER ****
(B) False

44. True or False: Infinite recursion can occur when a recursive
algorithm contains a base case.
(A) True **** MY ANSWER/CORRECT ANSWER ****
(B) False

45. True or False: Infinite recursion can occur when the base case is
never reached by the algorithm.
(A) True **** MY ANSWER/CORRECT ANSWER ****
(B) False

46. A solution to a 64-disk Towers of Hanoi problem requires how many
disks to be moved?
(A) 64 **** CORRECT ANSWER ****
(B) 2^64 - 1 **** MY ANSWER ****
(C) 64^2 - 1
(D) 64^64 - 1
(E) None of the above.

47. The following function implements which operation?
int mystery(tree_t *tree)
{
if (tree != NULL) {
printf("%d ", tree->data);
mystery(tree->left);
mystery(tree->right);
}
}

(A) A pre-order traversal. **** CORRECT ANSWER ****
(B) An in-order traversal. **** MY ANSWER ****
(C) A post-order traversal.
(D) None of the above.
(E) All of the above.

48. The following function implements which operation?
int mystery(tree_t *tree)
{
if (tree != NULL) {
mystery(tree->right);
printf("%d ", tree->data);
mystery(tree->left);
}
}

(A) An in-order traversal.
(B) A post-order traversal. **** MY ANSWER ****
(C) A pre-order traversal.
(D) A backwards in-order traversal. **** CORRECT ANSWER ****
(E) None of the above.
(F) All of the above.
.

Relevant Pages

  • Re: break
    ... outside switch or loop". ... of the code is that you want to return immediately from sum. ... return something, because sum returns int, and from the context it looks ... There are no situations where you MUST use recursion, however, there ...
    (comp.lang.java.programmer)
  • slightly OT: Sudoku solver C source
    ... takes 162 bytes per recursion level, times a maximum of 81 recursion ... void setbox(int n, int x, int bit) ... to indicate an unused square. ... program to restore the bitmask from a previously saved value. ...
    (comp.emulators.apple2)
  • Re: new java programmer with compile error and trouble writting a Recursive Function
    ... public static int handshakes ... When a new person enters the room, does his handshake count really multiply by the previous handshake count? ... Which operation is appropriate for "op" in the recursive function? ... Recursion is a fundamental concept of maths and computer science. ...
    (comp.lang.java.programmer)
  • [PATCH 1/4 v2] tracing: Use the perf recursion protection from trace event
    ... When we commit a trace to perf, we first check if we are recursing in ... The recursion check is desired early before we touch the ... const void *buf, unsigned int len); ... goto fail_buf_nmi; ...
    (Linux-Kernel)
  • [PATCH 1/4] tracing: Use the perf recursion protection from trace event
    ... When we commit a trace to perf, we first check if we are recursing in ... The recursion check is desired early before we touch the ... const void *buf, unsigned int len); ... goto fail_buf_nmi; ...
    (Linux-Kernel)