Test Bank—Chapter Eight (Data Abstractions)
Multiple Choice Questions
1. Which of the following is a LIFO structure?
A. Array B. Stack C. Queue D. Tree
2. Which of the following is a FIFO structure?
A. Array B. Stack C. Queue D. Tree
3. Which of the following is static in the sense that it does not change size or shape as information is stored
and retrieved?
A. Array B. Stack C. Queue D. Tree
4. Suppose you were going to retrieve items of data that you would later need to process in the opposite
order from that in which they were retrieved. Which of the following would be the best structure in which
to store the items?
A. Tree B. Stack C. Queue D. Traditional linked list
5. Suppose a binary tree contained the nodes W, X, Y, and Z. If W and X were children of Y, and Z had no
children, which node would be the root?
A. W B. X C. Y D. Z
6. Suppose a binary tree contained the nodes W, X, Y, and Z, and each node had at most one child. How
many terminal nodes would be in the tree?
A. One B. Two C. Three D. Undetermined
7. If the two-dimensional array X were stored in row-major order, then in the block of main memory
containing X, which of the following would be true?
A. The entry X[1,2] would appear before X[2,1].
B. The entry X[1,2] would appear after X[2,1].
C. The entry X[1,2] would be in the same location as X[2,1].
D. None of the above
8. Which of the following is not used when determining the location of an entry in a two-dimensional array
stored in row-major order?
A. Indices B. Number of rows in the array
C. Address polynomial D. Number of columns in the array
9. Which of the following is not a means of locating an entry in a linked storage structure?
A. head pointer B. child pointer C. root pointer D. null pointer
10. If a stack contained the entries w, x, y, z (from top to bottom), which of the following would be the
contents after two entries were removed and the entry r was inserted?
A. w, x, r B. y, z, r C. r, y, z D. r, w, x
11. If a queue contained the entries w, x, y, z (from head to tail), which of the following would be the
contents after two entries were removed and the entry r was inserted?
A. w, x, r B. y, z, r C. r, y, z D. r, w, x
12. If the number of nodes in a binary tree is 2n (where n is a positive integer), then the entire tree would
contain at least
A. 2n + 1 nodes B. 22n nodes C. 2n + 1 – 1 nodes D. 2n + 2 nodes
13. If the longest path in a binary tree contained exactly four nodes, what is the maximum number of nodes
that could be in the entire tree?
A. 4 B. 7 C. 15 D. 31
14. The nodes in which of the trees below will be printed in alphabetical order by the following recursive
procedure?
def printTree (Tree):
if (Tree is not None):
print(Tree.Value)
printTree(Tree.Right)
printTree(Tree.Left)
A. B. C.
15. The nodes in which of the trees below will be printed in alphabetical order by the following recursive
procedure?
def printTree (Tree):
if (Tree is not None):
printTree(Tree.Left)
printTree (Tree.Right)
print(Tree.Value)
A. B. C.
16. The table below represents a portion of a computer’s main memory containing a binary tree. Each node
consists of three cells, the first being data, the second being a pointer to the node’s left child, and the third
being a pointer to the node’s right child. If the null pointer is represented by 00 and the tree’s root pointer
contains 50, which of the following is a picture of the tree?
Address Contents
50 A
51 56
52 53
53 B
54 00
55 00
56 C
57 00
58 00
A. B. C.
17. Suppose a binary tree is implemented as a linked structure in which each node contains both a left child
pointer and a right child pointer. Which of the following statements is false?
A. The number of nodes in the tree is always at least the number of nodes on the longest path in
the tree.
B. The number of null pointers in the tree is always greater than the number of nodes in the tree.
C. Each terminal node in the tree is always at the end of a path that is as least as long as any other
path in the tree.
D. Both the left child and right child pointers of every terminal node are null.
18. The table below represents a portion of a computer’s main memory containing a binary tree stored row
by row in a contiguous block as described in the chapter. What is the left child of the node V?
Address Contents
50 T
51 U
52 V
53 W
54 X
55 Y
56 Z
A. W B. X C. Y D. Z
19. The table below represents a portion of a computer’s main memory containing a binary tree stored row
by row in a contiguous block as described in the chapter. What is the parent of the node Z?
Address Contents
50 T
51 U
52 V
53 W
54 X
55 Y
56 Z
A. T B. U C. V D. Y
20. In a machine language, the technique in which the data to be manipulated by an instruction is included
within the instruction itself is called
A. Immediate addressing B. Direct addressing C. Indirect addressing
21. In a machine language, the technique in which an instruction contains the location of a pointer to the
data to be manipulated is called
A. Immediate addressing B. Direct addressing C. Indirect addressing
Fill-in-the-blank/Short-answer Questions
1. Answer the following questions in terms of the tree below.
A. The root node is ________ .
B. Three nodes that are siblings are _______ , ________, and ________ .
C. The terminal nodes are _________________________________________ .
D. The node with only one child is _________ .
2. Two special forms of lists are the LIFO structures known as _______________ , in which entries are
inserted and removed from the ______________ , and FIFO structures known as ________________ ,
in which entries are removed from the ________________ and inserted at the ________________ .
3. Suppose the expression X[1, 1] referred to the first-row, first-column entry in a two-dimensional array
with 5 rows and 7 columns. If the array is stored in row-major order beginning at memory address x and
each entry in the array requires n memory cells, what address polynomial would be used to compute the
address of the beginning of the entry X[I, J]?
________________
4. Suppose the expression X[0, 0] referred to the first-row, first-column entry in a two-dimensional array
with 5 rows and 7 columns. If the array is stored in column-major order beginning at memory address x and
each entry in the array requires n memory cells, what address polynomial would be used to compute the
address of the beginning of the entry X[I, J]?
________________
5. If a queue contained the entries B, C, D (from head to tail), what would be the contents of the queue
(again from head to tail) after one entry was removed and the entry A was inserted?
6. Suppose a queue contained the entries A, B, C, D (from head to tail) and suppose that the entries were
removed and pushed on a stack one at a time until the queue was empty. What would be the contents of the
queue (again from head to tail) if the entries were then popped from the stack and inserted back in the
queue one at a time.
________________
7. In which direction does an unchecked queue crawl through memory (in the direction of its head or in the
direction of its tail)?
________________
8. The table below represents a portion of a computer’s main memory containing a linked list. Each list
entry consists of two cells, the first being data and the second being a pointer to the next list entry. If the
null pointer is represented by 00 and the list’s head pointer contains 56, what are the data entries in the list?
(List the entries in the order they occur in the list.)
Address Contents
50 AA
51 00
52 BB
53 58
54 CC
55 50
56 DD
57 54
58 EE
59 00
_________________
9. What sequence of nodes from the tree
would be printed if the following recursive procedure were applied to it?
def printTree(Tree):
if (Tree is not None):
print(Tree.Value)
printTree(Tree.Right)
________________
10. What sequence of nodes from the tree
would be printed if the following recursive procedure were applied to it? (The procedure uses a global stack
called Stack that is assumed to begin empty.)
def printTree(Tree):
if (Tree is not None):
Stack.push(Tree.Value)
printTree(Tree.Right)
if (not Stack.isEmpty()):
print(Stack.pop())
________________
11. What sequence of nodes from the tree
would be printed if the following recursive procedure were applied to it? (The procedure uses a global stack
called Stack that is assumed to begin empty.)
def printTree (Tree)
Stack.push(Tree.Left);
if (Tree.Right != None):
printTree(Tree)
print(Stack.pop())
________________
12. The table below represents a portion of a computer’s main memory containing a binary tree. Each node
consists of three cells, the first being data, the second being a pointer to the node’s left child, and the third
being a pointer to the node’s right child. If the null pointer is represented by 00 and the tree’s root pointer
contains 56, what data is in the left child of the root node?
Address Contents
50 AA
51 53
52 00
53 BB
54 00
55 00
56 CC
57 50
58 00
_________________
13. The table below represents a portion of a computer’s main memory containing a binary tree. Each node
consists of three cells, the first being data, the second being a pointer to the node’s left child, and the third
being a pointer to the node’s right child. If the null pointer is represented by 00 and the tree’s root pointer
contains 53, how many terminal nodes are in the tree?
Address Contents
50 AA
51 00
52 00
53 BB
54 00
55 56
56 CC
57 00
58 00
_________________
14. The table below represents a portion of a computer’s main memory containing a binary tree. Each node
consists of three cells, the first being data, the second being a pointer to the node’s left child, and the third
being a pointer to the node’s right child. If the null pointer is represented by 00 and the tree’s root pointer
contains 53, how many nodes are on the longest path in the tree?
Address Contents
50 AA
51 56
52 00
53 BB
54 00
55 50
56 CC
57 00
58 00
_________________
15. The table below represents a portion of a computer’s main memory containing a binary tree stored row
by row in a contiguous block as described in the chapter. What are the children of the node B?
Address Contents
50 A
51 B
52 C
53 D
54 E
55 F
56 G
16. If the longest path in a binary tree contains five nodes, what is the maximum number of terminal nodes
that could be in the tree?
_________________
17. If the variable named Box had the user-defined type RectangleType defined by
struct RectangleType
{
float length;
float width;
float height
}
What expression would be used to reference the length of Box?
_________________
18. If the type BananaSplit was defined by a statement such as
struct BananaSplit
{
int Banana;
int IceCream;
int Chocolate;
int WhippedCream;
int Nuts;
int Cherry
}
what statement would probably be used to declare the variable Desert to be an instance of that type?
_________________
19. Suppose the following Java code was used to implement an abstract data type for a stack of integers:
class StackOfIntegers implements StackType
{
private int[] StackEntries = new int[20];
private int StackPointer = 0;
public void push(int NewEntry)
{
if (StackPointer < 20)
StackEntries[StackPointer++] = NewEntry;
}
…
A. What would be the value of the variable StackPointer associated with Stack after executing the
statement
StackType Stack;
_______________
B. Then, what would be the value of StackPointer associated with Stack after executing the
statement
Stack.push(5);
_______________
20. Suppose the following Java code was used to implement an abstract data type for a stack of integers:
class StackOfIntegers implements StackType
{
private int[] StackEntries = new int[20];
private int StackPointer = 0;
public void push(int NewEntry)
{
if (StackPointer < 20)
StackEntries[StackPointer++] = NewEntry;
}
…
A. What would be the value of the variable StackPointer associated with Stack2 after executing the
statements
StackType Stack1, Stack2;
Stack1.push(5);
Stack2.push(6);
Stack2.push(7);
_______________
B. What would be the value of StackEntries[0] associated with Stack1 after executing the
statements in part A?
_______________
C. What would be the value of StackEntries[1] associated with Stack2 after executing the
statements in part A?
_______________
D. What would be the value of StackEntries[0] associated with Stack2 after executing the
statements in part A?
_______________
21. The following represents a portion of a computer’s main memory.
Address Contents
50 51
51 56
52 53
53 57
54 58
55 50
56 57
57 52
58 53
A. What would be stored at address 50 after executing the instruction “Copy the contents of the memory
cell at address 54 to address 50”?
________________
B. What would be stored at address 50 after executing the instruction “Copy the contents of the memory
cell pointed to by the cell at address 54 to address 50”?
________________
Vocabulary (Matching) Questions
The following is a list of terms from the chapter along with descriptive phrases that can be used to produce
questions (depending on the topics covered in your course) in which the students are ask to match phrases
and terms. An example would be a question of the form, “In the blank next to each phrase, write the term
from the following list that is best described by the phrase.”
Term Descriptive Phrase
pointer Contains the address at which an entity is stored
address polynomial Used to find entries in an array
abstraction The separation of internal implementation from external functionality
list A general sequential storage structure
stack A LIFO storage structure
queue A FIFO storage structure
array A “rectangular” block of data whose entries are of the same type
tree A storage structure that may contain siblings.
user-defined data type A template for an aggregate
abstract data type A custom-built data type including both data and operations
class A “type” whose instances are objects
instance An entity conforming to a type
linked structure A data storage system in which items are connected via pointers
top The “head” of a stack
root The top node of a tree
null pointer Indicates the end
General Format Questions
1. What condition indicates that a linked list is empty?
2. The table below represents a portion of a computer’s main memory containing a linked list. Each entry
consists of two cells, the first being data, the second being a pointer to the next entry. If the null pointer is
represented by 00 and the list’s head pointer contains 52, modify the memory cells so the data at address 50
replaces the second entry in the list.
Address Contents
50 AA
51 00
52 BB
53 58
54 CC
55 00
56 DD
57 00
58 EE
59 54
3. The table below represents a portion of a computer’s main memory containing a linked list. Each entry
consists of two cells, the first being data, the second being a pointer to the next entry. If the null pointer is
represented by 00 and the list’s head pointer contains 52, modify the memory cells so the data at address 56
is inserted at the end of the list.
Address Contents
50 AA
51 00
52 BB
53 58
54 CC
55 00
56 DD
57 00
58 EE
59 54
4. The table below represents a portion of a computer’s main memory containing a binary tree. Each node
consists of three cells, the first being data, the second being a pointer to the node’s left child, and the third
being a pointer to the node’s right child. If the null pointer is represented by 00 and the tree’s root pointer
contains 53, draw a picture of the tree showing the data in each node?
Address Contents
50 AA
51 56
52 00
53 BB
54 00
55 50
56 CC
57 00
58 00
5. Why is a queue normally implemented as a circular queue?
6. What is the distinction between a user-defined data type and an abstract data type?
7. Define each of the following:
A. Primitive data type B. User-defined data type C. Abstract data type
8. What is the distinction between a type and an instance of that type?
9. What is the distinction between direct addressing and indirect addressing?
10. The table below represents a portion of a computer’s main memory containing a binary tree stored row
by row in a contiguous block as described in the chapter. Draw a picture of the tree.
Address Contents
50 A
51 B
52 C
53 D
54 E
55 F
56 G
11. In a machine language, what advantage does indirect addressing offer over immediate and direct
addressing?