Deck 8: Data Abstractions

Question 1

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

Answer 1

A

Question 2

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?
$\begin{array} { c c } \text { Address } & \text { Contents } \\50 & \mathrm {~T} \\51 & \mathrm { U } \\52 & \mathrm {~V} \\53 & \mathrm {~W} \\54 & \mathrm { X } \\55 & \mathrm { Y } \\56 & \mathrm { Z }\end{array}$

A) T
B) U
C) V
D) Y

Answer 2

V

Question 3

Which of the following is a LIFO structure?

A) Array
B) Stack
C) Queue
D) Tree

Answer 3

B

Question 4

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

Question 5

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

Question 6

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

Question 7

If the number of nodes in a binary tree is 2ⁿ (where n is a positive integer),then the entire tree would contain at least

A) 2ⁿ ⁺ ¹ nodes
B) 2²ⁿ nodes
C) 2ⁿ ⁺ ¹ - 1 nodes
D) 2ⁿ ⁺ ² nodes

Question 8

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

Question 9

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

Question 10

Which of the following is a FIFO structure?

A) Array
B) Stack
C) Queue
D) Tree

Question 11

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

Question 12

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?

$\begin{array}{l}\text { Address Contents }\\\begin{array} { l l } 50 & \text { T } \\51 & \text { U } \\52 & \text { V } \\53 & \text { W } \\54 & \text { X } \\55 & \text { Y } \\56 & \text { Z }\end{array}\end{array}$

A) W
B) X
C) Y
D) Z

Question 13

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

Question 14

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

Question 15

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

Question 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? $\begin{array} { c c } \text { Address } & \text { Conten } \\50 & \mathrm {~A} \\51 & 56 \\52 & 53 \\53 & \mathrm {~B} \\54 & 00 \\55 & 00 \\56 & \mathrm { C } \\57 & 00 \\58 & 00\end{array}$

A)
B)
C)

Question 17

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)

Question 18

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

Question 19

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.

Question 20

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)

Question 21

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

Question 22

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?

Question 23

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?

Question 24

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?

Question 25

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]?

Question 26

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

Question 27

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?

Question 28

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?

Question 29

In which direction does an unchecked queue crawl through memory (in the direction of its head or in the direction of its tail)?

Question 30

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)

Question 31

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?

Question 32

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.)
$\begin{array} { c c } \text { Address } & \text { Contents } \\50 & \text { AA } \\51 & 00 \\52 & \text { BB } \\53 & 58 \\54 & \text { CC } \\55 & 50 \\56 & \text { DD } \\57 & 54 \\58 & \text { EE } \\59 & 00\end{array}$

Question 33

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.

Question 34

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?

Question 35

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

Question 36

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

Question 37

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?

Question 38

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

Question 39

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]?
________________

Question 40

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

Question 41

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.

Question 42

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?

Question 43

What is the distinction between a user-defined data type and an abstract data type?

Question 44

In a machine language,what advantage does indirect addressing offer over immediate and direct addressing?

Question 45

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?

Question 46

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.

Question 47

What is the distinction between a type and an instance of that type?

Question 48

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.

Question 49

The following represents a portion of a computer's main memory.
$\begin{array}{l}\text { Address}& \text { Contents }\\50 & 51 \\51 & 56 \\52 & 53 \\53 & 57 \\54 & 58 \\55 & 50 \\56 & 57 \\57 & 52 \\58 & 53\end{array}$
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"?

Question 50

What condition indicates that a linked list is empty?

Question 51

Define each of the following:

A.Primitive data type
B.User-defined data type
C.Abstract data type

Question 52

Why is a queue normally implemented as a circular queue?

Question 53

What is the distinction between direct addressing and indirect addressing?