45 Javanotes 9.0, Quiz on Chapter 9

Quiz on Chapter 9

Question 1:

Explain what is meant by a recursive subroutine.

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.print("]");
    }
}

Show the output that would be produced by the subroutine calls
printStuff(0), printStuff(1), printStuff(2), and
printStuff(3).

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 count the number of zeros that occur in a given
linked list of ints. The subroutine should have a parameter of type ListNode
and should return a value of type int.

Question 4:

Let ListNode be defined as in the previous
problem. Suppose that head is a variable of type
ListNode that points to the first node in a
linked list. Write a code segment that will add the number 42 in a new
node at the end of the list. Assume that the list is not empty.
(There is no “tail pointer” for the list.)

Question 5:

List nodes can be used to build linked data structures that do not have
the form of linked lists. Consider the list node class shown on the left and
the code shown on the right:

class ListNode {                        ListNode one = new ListNode(10);
    int item;                           ListNode two = new ListNode(20);
    ListNode next;                      ListNode three = new ListNode(30);
    Listnode(int i) {                   ListNode four = new ListNode(40);
        item = i;                       one.next = two;
        next = null;                    two.next = three;
    }                                   three.next = four;
}                                       four.next = two;

Draw the data structure that is constructed by the code. What happens if
you try to print the items in the data structure using the usual code for
traversing a linked list:

ListNode runner = one;
while (runner != null) {
    System.out.println(runner.item);
    runner = runner.next();
}

Question 6:

What are the three operations on a stack?

Question 7:

What is the basic difference
between a stack and a queue?

Question 8:

What is an activation
record? What role does a stack of activation records play in a
computer?

Question 9:

Suppose that a binary tree of integers
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.

Question 10:

Let TreeNode be the same class as in the previous
problem. Write a recursive subroutine that makes a copy of a binary tree.
The subroutine has a parameter that points to the root of the tree that is
to be copied. The return type is TreeNode,
and the return value should be a pointer to the root of the copy.
The copy should consist of newly created nodes, and it should have exactly
the same structure as the original tree.

Question 11:

What is a postorder traversal of a binary tree?

Question 12:

Suppose that a binary sort tree of integers is initially empty and
that the following integers are inserted into the tree in the order shown:

5   7   1   3   4   2   6

Draw the binary sort tree that results. Then list the integers in the
order that is produced by a post-order traversal of the tree.

Question 13:

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.)

Question 14:

Explain what is meant by parsing a computer program.

See the Answers