Review Questions

I l @ ve RuBoard

Review Questions

1. What's involved in defining a data type?

2. Why can the linked list in Listing 17.2 can be traversed in only one direction? How could you modify the struct film definition so that the list could be traversed in both directions?

3. What's an ADT?

4. The EmptyList() function took a list as an argument, but the EmptyQueue() function took a pointer to a queue as an argument. What are the advantages and disadvantages of each approach?

5. The stack is another data form from the list family. In a stack, additions and deletions can be made from only one end of the list. Items are said to be " pushed onto" the top of the stack and to be "popped off" the stack. Therefore, the stack is a LIFO structure, that is, Last In, First Out .

   1. Devise an ADT for a stack.

   2. Devise a C programming interface for a stack.

6. What is the maximum number of comparisons a sequential search and a binary search would need to determine that a particular item is not in a sorted list of 3 items? 1,023 items? 65,535 items?

7. Suppose a program constructs a binary search tree of words, using the algorithm developed in this chapter. Draw the tree, assuming words are entered in the following orders:

   1. nice food roam dodge gate office wave

   2. wave roam office nice gate food dodge

   3. food dodge roam wave office gate nice

   4. nice roam office food wave gate dodge

8. Consider the binary trees constructed in Review Question 7. What would each one look like after the word food was removed from each tree using the algorithm from this chapter?

I l @ ve RuBoard