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

Accepted Answer

Given that each node can have at most one child, the structure forms a linear chain rather than a branching tree. Regardless of the order of W, X, Y, and Z, there will always be one node without a child, making it the single terminal node.

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

Accepted Answer

In a binary tree stored in a contiguous block, the parent of a node at index $i$ is at index $(i-1)//2$. For node Z at index 6 (address 56), the parent is at index $(6-1)//2 = 2$, which is V.

Question 3

Which of the following is a LIFO structure?
A) Array
B) Stack
C) Queue
D) Tree

Accepted Answer

LIFO stands for "last in, first out," which means the last element added to the structure will be the first one to be removed. This property is found in the Stack data structure, making it the best choice for this question. Arrays, Queues, and Trees do not have the LIFO property.

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

Accepted Answer

Stacks operate on a Last In, First Out (LIFO) principle. Removing two entries from the top (w, x) and then inserting r would leave r at the top, followed by the remaining original entries (y, z).

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

Accepted Answer

A stack is a Last-In-First-Out (LIFO) data structure where the last item added to the stack will be the first one to be removed. This means that if we retrieve data and push it onto a stack, we can later pop the items off the stack in reverse order to process them in the opposite order in which they were retrieved. This makes a stack the best choice for storing items of data that need to be processed in the opposite order from which they were retrieved. Trees and traditional linked lists do not guarantee the order of the items when retrieving them and a queue retrieves items in the same order in which they were added, which does not fit the requirement for processing items in the opposite order.

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

Accepted Answer

Since W and X are children of Y, it means that Y is the parent node of W and X. Also, Z has no children. Therefore, Y must be the root node of the tree as it does not have any parent node, and all the rest of the nodes are children (either direct or indirect) of Y.

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

Accepted Answer

According to the formula, the number of nodes in a full binary tree with height n is 2ⁿ ⁺ ¹ - 1. Therefore, if the number of nodes in a binary tree is 2ⁿ, then the minimum number of nodes in the tree would be 2ⁿ ⁺ ¹ - 1. Option C is the closest to this value.

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

Accepted Answer

Immediate addressing is a technique in which the data to be manipulated by an instruction is included within the instruction itself. This means that the operand is specified directly in the instruction, rather than being stored in memory or accessed through a register. Immediate addressing is useful for operations that involve constant values, such as setting a register to a specific value or adding a fixed constant to a value. In contrast, direct addressing involves specifying an operand as a memory address, while indirect addressing involves using a memory address to access the actual operand value.

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

Accepted Answer

If two entries are removed from the head of the queue, then we remove w and x. So, the queue now contains y, z. After inserting r, the contents of the queue will be y, z, r.

Question 10

Which of the following is a FIFO structure?
A) Array
B) Stack
C) Queue
D) Tree

Accepted Answer

Queue is a FIFO (First-In-First-Out) structure where the first element inserted is the first element to be removed. Arrays and Trees do not have any inherent ordering, and Stacks are LIFO (Last-In-First-Out) structures.

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

Accepted Answer

In row-major order, the location of an entry is determined by its indices, the number of columns in the array (to calculate the offset within a row), and the address polynomial (which is used to calculate the actual memory address based on these indices and dimensions). The number of rows in the array is not directly used in calculating the location of an entry.

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

Accepted Answer

To determine the left child of the node V, we need to look at the row immediately below it in the binary tree. From the given portion of the memory, we can see that the row below V is:
0010 1110 1010 0011
This can be split into two segments, each of 16 bits:
0010111010100011
We know that the left child of V will be the 16 bits immediately following the 16 bits representing V in memory. Therefore, the left child of V is represented by:
10100011 10001101
This corresponds to the node Y in the binary tree, which is represented by the memory address:
11ea32c0_19c8_2ca3_96e7_3fc43a23e80b_TB1806_09
Therefore, the correct answer is option C, Y.

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

Accepted Answer

In row-major order, the elements are stored in consecutive memory locations row by row. So, X[1][1] is followed by X[1][2], which is followed by X[1][3], and so on. Therefore, X[1][2] would appear before X[2][1] in main memory.

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

Accepted Answer

A null pointer is used to mark the end of a list or that a pointer does not point to any valid location in memory, not to locate an entry in a linked storage structure. Head, child, and root pointers are used to locate entries.

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

Accepted Answer

Arrays are data structures that have a fixed size and shape, meaning once they are initialized, they do not change in size or shape as data is stored or retrieved. This makes them static in nature, making them the best choice for this question. On the other hand, stacks, queues, and trees can grow or shrink in size as new elements are added or removed, making them dynamic data structures.

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)

Accepted Answer

The answer of The table below represents a portion of...

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)

Accepted Answer

In order to print the nodes in alphabetical order, we need to do an inorder traversal. And inorder traversal of the binary search tree gives the nodes in alphabetical order. The tree in option B is a binary search tree which means the inorder traversal will give the nodes in alphabetical order. Therefore, option B is the best choice.

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

Accepted Answer

If the longest path in a binary tree contains exactly four nodes, then the tree must be at least a height of 2, with two nodes at each level. This can be visualized as a root node with two child nodes, each with two child nodes, for a total of 5 nodes. However, if any one of these child nodes has a child node of its own, then we have a longer path of at least 5 nodes. Therefore, the binary tree with the longest path of exactly 4 nodes is a full binary tree of height 3, with 7 nodes in total. Since all other binary trees with a longest path of exactly 4 nodes will be smaller than this full binary tree, we can conclude that the maximum number of nodes in the entire tree is 15, which is the number of nodes in a full binary tree of height 4.

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.

Accepted Answer

The answer of Suppose a binary tree is implemented as...

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)

Accepted Answer

The answer of The nodes in which of the trees...

Quiz 8: Data Abstractions

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?

Which of the following is a LIFO structure?

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?

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?

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?

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

In a machine language,the technique in which the data to be manipulated by an instruction is included within the instruction itself is called

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?

Which of the following is a FIFO structure?

Which of the following is not used when determining the location of an entry in a two-dimensional array stored in row-major order?

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?

Which of the following is not a means of locating an entry in a linked storage structure?

Which of the following is static in the sense that it does not change size or shape as information is stored and retrieved?

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)

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?

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?

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)