Sample Quiz Answers
For Chapter 11
THIS PAGE CONTAINS SAMPLE ANSWERS to the Quiz on
Chapter 11 of this on-line
Java textbook. Note that in many cases, there are lots of correct
answers to a given question.
Question 1:
Explain what is meant by a recursive subroutine.
Answer:
A recursive subroutine is simply one that calls itself either directly
or through a chain of calls involving other subroutines.
Question 2:
Consider the following subroutine:
static void printStuff(int level) {
if (level == 0) {
System.out.print("*");
}
else {
System.out.print("[");
printStuff(level - 1);
System.out.print(",");
printStuff(level - 1);
System.out.println("]");
}
}
Show the output that would be produced by the subroutine
calls printStuff(0), printStuff(1), printStuff(2),
and printStuff(3).
Answer:
The outputs are:
printStuff(0) outputs: *
printStuff(1) outputs: [*,*]
printStuff(2) outputs: [[*,*],[*,*]]
printStuff(3) outputs: [[[*,*],[*,*]],[[*,*],[*,*]]]
(Explanation: For printStuff(0), the value of the parameter is 0, so the
first clause of the if is executed, and the output is just *.
For printStuff(1), the else clause is executed. This else clause
contains two recursive calls to printStuff(level-1). Since
level is 1, level-1 is 0, so each call to
printStuff outputs a *. The overall output from
printStuff(1) is [*,*]. In a similar way, printStuff(2)
includes two recursive calls to printStuff(1). Each call
to printStuff(1) outputs [*,*]. And printStuff(2)
just takes two copies of this and puts them between [ and ] separated
by a comma: [[*,*],[*,*]]. Finally, the output from
printStuff(3) outputs two copies of [[*,*],[*,*]]
separated by a comma and enclosed between brackets. Once you
recognize the pattern, you can do printStuff(N) for any
N without trying to follow the execution of the subroutine
in detail.)
Question 3:
Suppose that a linked list is formed from objects that belong to the class
class ListNode {
int item; // An item in the list.
ListNode next; // Pointer to next item in the list.
}
Write a subroutine that will find the sum of all the ints in
a linked list. The subroutine should have a parameter of type ListNode
and should return a value of type int.
Answer:
I'll give both a non-recursive solution and a recursive solution.
For a linked list, the recursion is not really necessary, but
it does nicely reflect the recursive definition of ListNode
static int listSum( ListNode head ) {
int total; // The sum of all the items.
ListNode runner; // For running along the list.
total = 0;
runner = head; // Start at the beginning of the list.
while (runner != null) {
total += runner.item; // Add in the item in this node.
runner = runner.next; // Advance to the next node.
}
return total;
}
static int recursiveListSum( ListNode head ) {
if ( head == null) {
// The sum of the items in an empty list is zero.
return 0;
}
else {
// Add the item in the head to the sum of the other items.
return head.item + recursiveListSum(head.next);
}
}
Question 4:
What are the three operations on a stack?
Answer:
The three stack operations are push, pop, and isEmpty.
The definitions of these operations are:
push(item) adds the specified item to the top of the stack;
pop() removes the top item of the stack and returns it; and
isEmpty() is a boolean-valued function that returns
true if there are no items on the stack.
Question 5:
What is the basic difference between a stack and a queue?
Answer:
In a stack, items are added to the stack and removed from the stack
on the same end (called the "top" of the stack). In a queue,
items are added at one end (the "back") and removed at the other
end (the "front"). Because of this difference, a queue is a FIFO
structure (items are removed in the same order in which they were
added), and a stack is a LIFO structure (the item that is popped from
a stack is the one that was added most recently).
Question 6:
What is an activation record? What role does a
stack of activation records play in a computer?
Answer:
When a subroutine is called, an activation record is created to hold
the information that is needed for the execution of the subroutine,
such as the values of the parameters and local variables. This
activation record is stored on a stack of activation records.
A stack is used since one subroutine can call another, which can
then call a third, and so on. Because of this, many activation
records can be in use at the same time. The data structure is
a stack because an activation record has to continue to exist
while all the subroutines that are called by the subroutine
are executed. While they are being executed, the stack of
activation records can grow and shrink as subroutines are
called and return.
Question 7:
Suppose that a binary tree is formed from objects belonging to the class
class TreeNode {
int item; // One item in the tree.
TreeNode left; // Pointer to the left subtree.
TreeNode right; // Pointer to the right subtree.
}
Write a recursive subroutine that will find the sum of all the nodes in
the tree. Your subroutine should have a parameter of type TreeNode,
and it should return a value of type int.
Answer:
static int treeSum( TreeNode root ) {
// Find the sum of all the nodes in the
// tree to which root points.
if ( root == null ) {
// The sum of the nodes in an empty tree is zero.
return 0;
else {
// Add the item in the root to the sum of the
// items in the left subtree and the sum of the
// items in the right subtree.
int total = root.item;
total += treeSum( root.left );
total += treeSum( root.right );
return total;
}
}
Question 8:
What is a postorder traversal of a binary tree?
Answer:
In a traversal of a binary tree, all the nodes are processed in
some way. (For example, they might be printed.) In a postorder
traversal, the order of processing is defined by the rule:
For each node, the nodes in the left subtree of that node are
processed first. Then the nodes in the right subtree are processed.
Finally, the node itself is processed.
Question 9:
Suppose that a <multilist> is defined by the BNF rule
<multilist> ::= <word> | "(" [ <multilist> ]... ")"
where a <word> can be any sequence of letters. Give five
different <multilist>'s that can be generated by this rule.
(This rule, by the way, is almost the entire syntax of the programming
language LISP! LISP is known for its simple syntax
and its elegant and powerful semantics.)
Answer:
Here are five possibilities (out of an infinite number of possibilities),
with some explanation:
fred -- A <multilist> can just be a word, such as "fred".
( ) -- The [ ]... around <multilist> means that there can be
any number of nested <multilist>'s, including zero. If
there are zero, then all that's left is the empty
parentheses.
( fred mary chicago ) -- A <multilist> consisting of three
<multilist>'s -- "fred", "mary", and
"chicago" -- inside parentheses
( ( able ) ( baker charlie ) ) -- A <multilist> containing two
<multilist>'s.
( ( a ( b ) ) ( c ( d e ) g ) ) -- Even more nesting.
Question 10:
Explaining what is meant by parsing a computer program.
Answer:
To parse a computer program means to determine its syntactic structure,
that is, to figure out how it can be constructed using the
rules of a grammar (such as a BNF grammar).
