1 CHAPTER 12 Abstract Data Types Solutions to Practice Set Review Questions 1 An abstract data type ADT is a data declaration packaged together with the oper ations that are meaningful for the data type In an ADT the operations used to access the data are known but the implementation of the operations are hidden 2 A stack is a restricted linear list in which all additions and deletions are made at one end called the top If we insert a series of data into a stack and then remove it the order of the data will be reversed This reversing attribute is why stacks are known as a last in first out LIFO data structure Four basic stack operations defined in this chapter are stack push pop and empty 3 A queue is a linear list in which data can only be inserted at one end called the rear and deleted from the other end called the front These restrictions ensure that the data are processed through the queue in the order in which they are received In other words a queue is a first in first out FIFO structure Four basic queue oper ations defined in this chapter are queue enqueue dequeue and empty 4 A general linear list is a list in which operations such as insertion can be done anywhere in the list that is at the beginning in the middle or at the end of the list Six common general linear list operations defined in this chapter are list insert delete retrieve traverse and empty 5 A tree consists of a finite set of elements called nodes or vertices and a finite set of directed lines called arcs that connect pairs of the nodes If the tree is not empty one of the nodes called the root has no incoming arcs The other nodes in a tree can be reached from the root following a unique path which is a sequence of consecutive arcs A binary tree is a tree in which no node can have more than two subtrees A binary search tree BST is a binary tree with one extra property the key value of each node is greater than the key values of all nodes in each left sub tree and smaller than the value of all nodes in each right subtree 6 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 2 7 A graph is an ADT made of a set of nodes called vertices and set of lines connect ing the vertices called edges or arcs Graphs may be either directed or undirected In a directed graph or digraph each edge which connects two vertices has a direction arrowhead from one vertex to the other In an undirected graph there is no direction 8 Four stack applications are reversing data pairing data postponing data usage and backtracking steps 9 General linear lists are used in situations where the elements are accessed ran domly or sequentially For example in a college a linear list can be used to store information about the students who are enrolled in each semester 10 Binary trees have many applications in computer sciences two of which are Huff man coding and expression trees Binary search trees are used when we want to have a list that can be searched using an efficient search algorithm such as binary search Multiple Choice Questions Exercises 26 27 11 b12 d13 b14 b15 d16 a 17 a18 c19 c20 c21 b 22 c 23 a24 d25 b while NOT empty S2 pop S2 x x will be discarded stack Temp while NOT empty S1 pop S1 x push Temp x Temp is a temporary stack while NOT empty Temp pop Temp x push S2 x 3 28 29 30 Figure S11 30 shows the contents of the stack and the value of the variables 31 Algorithm S12 31 shows the pseudocode stack Temp while not empty S1 pop S1 x push Temp x Temp is a temporary stack while not empty Temp pop Temp x push S1 x push S2 x stack Temp while NOT empty S2 pop S2 x push Temp x Temp is a temporary stack while NOT empty Temp pop Temp x push S2 x Figure S11 30Exercise 30 Algorithm S12 31Exercise 47 Algorithm Palindrome String 1 n Purpose It checks if a string is a palindrome Pre Given a string Post Return true the string is a palindrome or false the string is not a palindrome stack S i 1 while i n S1S1S1S1S1S1S1 x2y3 5 3 5 2 3 5 3 5 6 55 4 32 Algorithm S12 32 shows the pseudocode Algorithm S12 31Exercise 31 Continued C string i push S C i i 1 i 1 while i n pop S x if x sting i return false return true Algorithm S12 32Exercise 32 Algorithm CompareStack S1 S2 Purpose Check if two stacks are the same Pre Given S1 and S2 Post Return true S1 S2 or false S1 S2 flag true Stack Temp1 Stack Temp2 while NOT empty S1 and NOT empty S2 pop S1 x push Temp1 x pop S2 y push Temp2 y if x y flag false if NOT empty S1 or NOT empty S2 flag false while NOT empty Temp1 and NOT empty Temp2 pop Temp1 x push S1 x pop Temp2 y push S2 y return flag 5 33 34 35 36 while NOT empty Q dequeue Q x x will be discarded while NOT empty Q1 dequeue Q1 x enqueue Q2 x while NOT empty Q2 First we empty Q2 dequeue Q2 x while NOT empty Q1 dequeue Q1 x enqueue Temp x while NOT empty Temp dequeue Temp x enqueue Q1 x enqueue Q2 x while NOT empt