1. What does the term semi-generic mean?
2. What are the principal issues that need to be resolved before implementing a list ADT?
3. What is the difference between a queue and a stack?
4. What is a table?
5. The table was implemented using a linked list structure. What is it not correct to assert that a table is a linked list?
6. What is a tree?
7. What is a binary tree?
8. What does a root lack that every other node has?
9. What do leaves lack that other nodes have?
10. What does an interior node always have?
11. What is the degree of a node in a binary tree?
12. A binary tree with eight levels is full. What is the number of occupied nodes?
13. Explain the two different senses of the word full when applied to a binary tree.
14. Why is a binary search tree a more efficient data structure than a linked list when it comes to searching through large data aggregates?
15. Both a two way linked list and a binary tree have two node pointers. What is the difference between these structures?
16. What does the term ISAM mean?
17. What is "hashing?"
18. Describe the three different forms of tree traversal.
19. Suppose a tree were ternary (degree three). How many different ways would there be of traversing it?
20. In the entable procedure of the module CountryTable, suppose the line Assign (data, temp^.item); is replaced with the line temp^.item := data; What differnence will this make? Predict what will happen, then try it.
21. In the insert procedure of the module CountryBinaryTree, suppose the line Assign (data, temp^.item); is replaced with the line temp^.item := data; What differnence will this make? Predict what will happen, then try it.
22. Carefully examine and complete a detailed commenting of the implementation module Lists in section 14.2.
23. Carefully examine and complete a detailed commenting of the implementation modules TextQueues and AnAdtQueues in section 14.3.
24. Carefully examine and complete a detailed commenting of the implementation module CountryTable in section 14.5.
25. Carefully examine and complete a detailed commenting of the implementation module CountryBinaryTree in section 14.8.
26. You have a stamp collection to keep track of. Implement an abstract data type Stamp with fields for the country name, year of issue, name of stamp, condition, and current value. Now implement a list structure of these using the simple modifications to the list type discussed in this chapter.
27. Implement and test the module anADTStacks in section 14.4.
28. Revise (and test) the Table data type as a SortedTable type. Invent your own data type to entable.
29. A priority queue or sorted queue incorporates new items into the queue in a sorted fashion according to the value of some field. Serving is still done at the head of the queue as before. Modify the semi-generic queue in this chapter to be a priority queue for some key field.
30. Re-implement the text queue using a linked list of characters.
31. Re-implement anAdtQueues without the need to obtain a data node ahead of time, finding another way to report the error and determine the full condition. Hint: look at the other ADTs in this chapter.
32. A dequeue or double-ended queue allows items to be entered and served at either end. Thus it has headEnque, tailEnqueue, headServe, and tailServe routines. Implement and test this structure.
33. A stack pair is a pair of stacks in a single structure. Implement this as an array with one stack pointer crawling forward from zero as items are pushed and back as they are pulled and the other stack pointer moving back from the maximum index as items are pushed and forward as they are pulled. Thus, it has push1, pull1, push2, and pull2 routines. Both stacks are full (only one procedure needed) if the two pointers collide. Test your implementation.
34. Adapt the example in section 12.2 of the last chapter to the semi-generic methods of this chapter and create a linked list with two sets of links to enlist data consisting of people's names and their ages in two different sorted orders.
35. Another way of solving the last problem is to have only one set of links in the linked lists but two keys for sorting and two of the lists. Solve the problem this way.
36. Develop an airline flight reservation list. The passenger records should have last name, first name, smoker or non-smoker, and final destination. Set it up to read in any passenger's information and print out flight lists in alphabetical order and by destination. For each flight you should be able to select from a menu that allows you to add a passenger, delete a passenger, or print a list. Each flight is a list, so a main menu will have to control starting and ending flights.
37. Represent a polynomial as a linked list where each term is of the following type:
TYPE
Term =
RECORD
toPoint : Point;
coefficient : INTEGER;
exponent : CARDINAL
END
Each linked list is one polynomial and has as many records in the chain as there are terms in the polynomial. Write and test the routines to add, subtract, and multiply such polynomials, and to display the result.
38. Write a program module that will take data input from the keyboard and sort it into a tree. Each record tree consists of a person's name, age, sex, and whether they eat raspberry ice cream or not. Test your module by having your application program write it all out in alphabetical order by last name.
39. Add to the traversals in the semi-generic binary tree reverse in, pre, and post order traversals. Test all three.
40. Write a module to implement a data base to keep track of your library. The important information includes the publisher, author, title, subject, and ISBN number. Your data structure(s) must keep track of each of these in alphanumeric order, sorting items as they are read in from the keyboard or from the disk file where they are stored. Routines must be available to add to the list, store and retrieve via the disk and print it out on the screen or printer in order by selected category. Remember, sorting is to be done at input time, not at the printing stage. All five fields will be printed in any case; only the order is to be different.
41. Write a program similar in structure to the above, but designed to keep an inventory--say of chemicals, equipment, or merchandise for sale. Appropriate data items might include price paid, stock number, name of item, sale price, and date of acquisition. The print routines should output the data in a neat table ordered on one of four (or more) of the fields.
42. Look up and implement AVL balanced trees as an ADT.
43. Develop an ADT FamilyTree that allows you to express family relationships. Include the capability to express successive marriages for one person.
44. Define and implement an ADT Table for data that has two key types and three other data fields.