Chapter 21: Custom Generic Data Structures
21.1 Q1: Which statement is false?
a. Linked lists are collections of data items “lined up in a row”— insertions and deletions can be made
anywhere in a linked list.
b. Insertions and deletions are made only at one end of a stack, its top.
c. Insertions and deletions are made only at one end of a queue, its tail.
d. Binary trees facilitate high-speed searching and sorting of data.
21.2 Q1: A __________ class contains a reference member that refers to an object of the same class type.
a. self-determining.
b. self-pointing.
c. self-linking.
d. self-referential.
21.2 Q2: Usually a _________ in Java code indicates the end of a data structure.
a. backslash character.
b. forward slash character
c. null reference.
d. null pointer.
21.3 Q1: Java performs automatic __________ of objects that are no longer referenced in a program.
a. memory distribution.
b. garbage collection.
c. storage compression.
d. trash aggregation.
21.3 Q2: If no memory is available, keyword new throws an __________.
a. OutOfMemoryException.
b. OutOfMemoryEvent.
c. OutOfMemoryExhaustion.
d. OutOfMemoryError.
21.4 Q1: Which statement is false?
a. A linked list is a linear collection of self-referential class objects called nodes connected by
reference links.
b. A linked list is appropriate when the number of data elements to be represented in the data structure
is unpredictable.
c. A linked list is a fixed-size data structure.
d. By convention, the link reference in the last node of a list is set to null to mark the end of the list.
21.4 Q2: An isEmpty method you write to test whether a linked list is empty is called a __________
method.
a. predefined.
b. predicate.
c. preemption.
d. preorder.
21.4.1 Q1: List nodes normally are not necessarily stored in contiguous memory. Rather, they’re ________
contiguous.
a. physically
b. approximately
c. comparably
d. logically
21.4.3 Which of the following statements is true?
a. Predicate methods typically test a condition and modify the object on which they’re called.
b. Predicate methods typically do not test a condition and do not modify the object on which they’re called.
c. Predicate methods typically test a condition and do not modify the object on which they’re called.
d. Predicate methods typically do not test a condition and modify the object on which they’re called.
21.4.10 Q1: A package is:
a. A directory structure used to organize classes and interfaces.
b. A mechanism for software reuse.
c. A group of related classes and interfaces.
d. All of the above.
21.4.10 Q2: A class within a package must be declared public if
a. It will be used only by other classes in the same package.
b. It will be used by classes that are not in the same package.
c. It is in the same directory as the other classes in the package.
d. It has a unique name.
21.4.10 Q3: When compiling a class in a package, the javac command-line option ________ causes the
javac compiler to create appropriate directories based on the class’s package declaration.
a. -p.
b. -a.
c. -d.
d. -dir.
21.4.10 Q4: The import declaration import java.util.*; is known as a ________.
a. single-type-import declaration.
b. all-type-import declaration.
c. multiple-import declaration.
d. type-import-on-demand declaration.
21.4.10 Q5: The import declaration import *; ________.
a. causes a compilation error.
b. imports all classes in the library.
c. imports the default classes in the library.
d. imports the classes in package java.lang.
21.4.10 Q6: The classpath consists of a list of directories or archive files, each separated by a ________ on
Windows or a ________ on UNIX/Linux/Max OS X.
a. colon (:), semicolon (;).
b. semicolon (;), colon (:).
c. comma (,), semicolon (;).
d. semicolon (;), comma (,).
21.4.10 Q7: By default, the classpath consists only of the ________. However, the classpath can be
modified by providing the ________ option to the javac compiler.
a. root directory of the package, -d.
b. current directory, -d.
c. root directory of the package, -classpath.
d. current directory, -classpath.
21.5 Q1: A stack is a __________ data structure.
a. FILO.
b. FOLI.
c. LOFI.
d. LIFO.
21.5 Q2: The technique of implementing each stack method as a call to a List method is called
__________.
a. delegation.
b. delimiting.
c. assigning.
d. shifting responsibility.
21.5 Q3: Which statement is false?
a. When a method call is made, the called method must know how to return to its caller, so the return
address is pushed onto the program execution stack.
b. Stacks support recursive method calls in the same manner as conventional, nonrecursive method
calls.
c. The program execution stack contains the space created for a method’s global variables on each
invocation of that method during a program’s execution.
d. When a method returns to its caller, the memory for that method’s local variables is popped off the
stack and those variables are no longer known to the program.
21.6 Q1: A queue is a __________ data structure.
a. FOFI.
b. FIFO.
c. OFIF.
d. IFOF.
21.6 Q2: Queue nodes are removed only from the __________ of the queue, and are inserted only at the
__________ of the queue.
a. tail, tail.
b. tail, head.
c. head, tail.
d. head, head.
21.6 Q3: Which is not a typical application of queues?
a. Routing packets in a computer network.
b. File server handling file access requests from many clients.
c. High-speed sorting.
d. Print spooling.
21.7 Q1: Which statement about trees is false?
a. A tree is a nonlinear, two-dimensional data structure.
b. Each node in a tree contains two links.
c. The children of a node are called siblings.
d. A node with no children is called a leaf node.
21.7 Q2: Which statement is false?
a. The shape of a binary search tree that corresponds to a set of data can vary, depending on the order
in which the values are inserted into the tree.
b. A node can be inserted at any point in a binary search tree.
c. The process of creating a binary search tree actually sorts the data, and thus this process is called the
binary tree sort.
d. The binary search tree facilitates duplicate elimination.
21.7 Q3: Which statement is false?
a. In a tightly packed binary tree, each level contains about twice as many elements as the previous
level.
b. When searching a tightly packed 1,000,000-element binary search tree, approximately 20
comparisons need to be made.
c. The level-order traversal of a binary tree visits the nodes of the tree row-by-row starting at the root
node level.
d. Searching a binary tree for a value that matches a key value is slow for loosely packed trees.
•