计算机科学导论第12章参考答案.pdf
CHAPTER 12
Abstract Data Types
Review Questions
1. An abstract data type is a data declaration packaged together with the operations
that are meaningful for the data type with the implementation hidden from the user.
3. A linear list is a list in which each element has a unique successor.
5. Two common implementations of a general list are an array and a linked list.
7. A push operation adds an element to the top of the stack while a pop operation
removes an element from the top of the stack. A push can put the stack in an over-
flow condition while a pop can put the stack in an underflow condition.
9. The enqueue operation adds an element to the rear of a queue. The dequeue opera-
tion removes the element at the front of the queue. The enqueue operation could
put the queue in an overflow state while the dequeue could put the queue in an
underflow state.
11. A depth first traversal processes all of the nodes in one subtree before processing
all of the nodes in the other subtree. In a breadth first traversal, all the nodes at one
level are processed before moving on to the next level.
13. In a depth-first traversal, all of a vertex's descendents are processed before moving
to an adjacent vertex. In a breadth-first traversal, all adjacent vertices of a vertex
are processed before going to the next level.
15. A network is a graph with weighted lines.
Multiple-Choice Questions
17. d
19. c
21. a
