Chapter Exercises

What is a data structure?

Define each of the following terms: collection, container, and sequence.

What is a Bag ADT and how does it differ from Python's list type?

What is an iterator and why should a container type implement an iterator?

What is some of the criteria used to select a data structure for implementing an abstract data type?

The Map ADT is a container, but is a linear structure? Explain your answer.

Complete the Map class that uses parallel lists for storing the map entries by implementing the clear, remove, and valueOf methods.

Complete the Map class that uses a single lists for storing the map entries with storage objects by implementing the clear, remove, and valueOf methods.

Add a new operation keyList to the Map class that returns a Python list containing all of the keys stored in the map. The list of keys should be in no particular order.

Add Python operators to the Map class that can be used to perform similar operations to those already defined by named methods:

Design and implement the iterator class MapIterator for use with the Map ADT implemented using a single Python list.

Implement the totalCount method of the Histogram class.

A Grab Bag ADT is similar to the Bag ADT with one difference. A grab bag does not have a remove operation, but in place of it has a grabItem operation, which allows for the random removal of an item from the bag. Implement the Grab Bag ADT.

A Counting Bag ADT is just like the Bag ADT but includes the numOf(item) operation, which returns the number of occurrences of the given item in the bag. Implement the Counting Bag ADT and defend your selection of data structure.

Design and implement an ADT to represent a standard deck of 52 playing cards.

Anyone who is involved in many activities typically uses a calendar to keep track of the various activities. Colleges commonly maintain several calendars such as an academic calendar, a school events calendar, and a sporting events calendar. We have defined an Activities Calendar ADT below that can keep track of one activity per day over a given range of dates. Select a data structure and implement the ADT.

• ActivitiesCalendar(dateFrom, dateTo)
  Creates a new empty activities calendar initialized to the given range of dates. The date range can be specified for any non-overlapping period. The only requirements are that dateFrom must precede dateTo and dateTo cannot overlap the day and month of dateFrom for the next year.
• length()
  Returns the number of activities on the calendar.
• getActivity(date)
  Returns the string that describes the activity for the given date if an activity exists for the given date; otherwise, None is returned.
• addActivity(date, activity)
  Adds the given activity description to the calendar for the given date. The date must be within the valid date range for the calendar.
• displayMonth(month)
  Displays to standard output all activities for the given month. The display includes the year and name of the month and the list of activities for the month. The display of each activity includes the day of the month on which the activity occurs and the description of~the activity.