Deck 7: Software Engineering

Question 1

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

Answer 1

C

Question 2

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

Answer 2

C

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 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 5

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?

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

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

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 nil pointer is represented by 00 and the tree's root pointer contains 50, which of the following is a picture of the tree?

A)
B)
C)

Question 8

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 9

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 10

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) NIL pointer

Question 11

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) Traditional linked list
B) Stack
C) Queue
D) Tree

Question 12

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 13

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?

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

Question 14

The nodes in which of the trees below will be printed in alphabetical order by the following recursive procedure?

A)
B)
C)

Question 15

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^{n + 1} nodes
B) 2²ⁿ nodes
C) 2^{n + 1} - 1 nodes
D) 2^{n + 2} nodes

Question 16

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 17

Which of the following is a FIFO structure?

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

Question 18

Which of the following is not used when determining the location of an entry in a two-dimensional homogeneous 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 19

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 20

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

Question 21

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

Question 22

What is the distinction between direct addressing and indirect addressing?

Question 23

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 nil 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 24

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 25

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

Question 26

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

Question 27

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

Question 28

What condition indicates that a linked list is empty?

Question 29

If the variable named Box had the user-defined type RectangleType defined by What expression would be used to reference the length of Box?
_________________

Question 30

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 nil 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 31

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 nil 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 32

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 33

Define each of the following:
A. Primitive data type
B. User-defined data type
C. Abstract data type

Question 34

Why is a queue normally implemented as a circular queue?