CHAPTER 12
Abstract Data Types
Review Questions
1.An abstract data type is a data declaration packaged together with the operationsthat 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 operationremoves 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 couldput the queue in an overflow state while the dequeue could put the queue in anunderflow 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 onelevel 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 vertexare processed before going to the next level.15.A network is a graph with weighted lines.
Multiple-Choice Questions
17.19.21.23.25.27.29.
dcaabda
3
4CHAPTER 12ABSTRACT DATA TYPES
31.33.35.37.39.41.43.45.47.49.51.53.ccddcbadabba
Exercises
55.(top) 6 5 (bottom)57.
moveStack
Input: Source stack (s1) and destination stack (s2)1. While s1 is not empty 1.1 push ( s2, pop(s1) ) End loopEnd59.
catStack
Input: Source stack (s2) and destination stack (s1)1. While s2 is not empty 1.1 push ( s1, pop(s2) ) End loopEnd61.
compareStack
Input: The two stacks to compare (s1 and s2)
1. Allocate memory for two temporary stacks (Temp1 and Temp2)2. copyStack ( s1, Temp1 ) (see #58)3. copyStack ( s2, Temp2 ) (see #58)
4. While Temp1 is not empty AND Temp2 is not empty 4.1 TempValue1 = pop ( Temp1 ) 4.2 TempValue2 = pop ( Temp2 )
4.3 If TempValue1 is not equal to TempValue2
SECTION 5
4.3.1 Return false End if End loop
5. If Temp1 is not empty OR Temp2 is not empty 5.1 Return false End if6. Return trueEnd63.
emptyQueue
Input: Queue to empty (q3)1. While q3 is not empty 1.1 dequeue( q3 ) End loopEnd65.
copyQueue
Input: Source queue (q2) and destination queue (q3)1. Allocate memory for a temporary queue (Temp)2. While q2 is not empty
2.1 enqueue ( Temp, dequeue(q2) ) End loop
3. While Temp is not empty
3.1 TempValue = dequeue(Temp) 3.2 enqueue ( q2, TempValue ) 3.3 enqueue ( q3, TempValue ) End loopEnd67.
compareQueue
Input: The two queues to compare (q1 and q2)
1. Allocate memory for two temporary queues (Temp1 and Temp2)2. copyQueue ( q1, Temp1 ) (see #65)3. copyQueue ( q2, Temp2 ) (see #65)4. While Temp1 is not empty AND Temp2 is not empty 4.1 TempValue1 = dequeue ( Temp1 ) 4.2 TempValue2 = dequeue ( Temp2 )
4.3 If TempValue1 is not equal to TempValue2 4.3.1 Return false End if
6CHAPTER 12ABSTRACT DATA TYPES
End loop
5. If Temp1 is not empty OR Temp2 is not empty 5.1 Return false End if
6. Return trueEnd
69. See Figure 12.1Figure 12.1Exercise 69
JCBAEDFGIH71.This tree cannot be drawn because it is not a valid binary tree. Node C must be the
root because it is listed last in the postorder traversal. From the inorder traversal,we see that nodes A, B, and D must be in the left subtree (because they are listed tothe left of the root) and that nodes E, F, and G are in the right subtree. Lookingback at the postorder list, however, we see that nodes G and F are listed first,which is not possible.
73.Assuming that arcs are stored in sequence by their destination, the traversal is: A,
G, F, H, D, E, C, B75.See Figure 12.2. Figure 12.2Exercise 75
AABCDEFGHABCDEFGH04300010B40003000C30080500D00800005E03000060F00500027G10006200H00050700VertexVectorAdjacencyMatrixSECTION 7
77.See Figure 12.3.Figure 12.3Exercise 77
A2313624236BFE11221CD8CHAPTER 12ABSTRACT DATA TYPES
