Previous Section
 < Free Open Study > 
Next Section


Exercises

  1. Given the following specification of the Top operation:

    Assume that the Pop operation returns the item and Top is not defined. Write this function as client code, using operations from the StackType class. Remember-the client code has no access to the private members of the class.

  2. Implement the following operation as a member function of the StackType class.

  3. Implement the following operation as a member function of the StackType class.

  4. Given the following specification of a Front operation:

    1. Write this function as client code, using operations from the QueType class. Remember-the client code has no access to the private members of the class.

    2. Write this function as a new member function of the QueType class.

  5. Implement the following operation as a member function of the QueType class.

  6. Implement the following specification for an integer function that returns the number of items in a queue. This function is a member function of the QueType class.

  7. Exercise 1 in Chapter 3 asked you to add a member function IsThere to the Unsorted List ADT. Rewrite the function definitions using a linked structure. You may assume a templated class where ItemType has the == operator defined.

  8. Exercise 2 in Chapter 3 asked you to add a member function IsThere to the Sorted List ADT. Rewrite the function definitions using a linked structure. You may assume a templated class where ItemType has the == and > operators defined.

  9. Write a member function that merges two instances of the Sorted List ADT using the following specification.

    Assume that SortedType is a templated class and that the relational operators are defined for ItemType.

    1. Write the prototype for MergeLists.

    2. Write the code for the function.

    3. Describe the algorithm in terms of Big-O notation.

  10. A list ADT is to be extended by the addition of the member function SplitLists, which has the following specification:

    You may assume that UnsortedType and SortedType are templated classes and that the relational operators are defined for ItemType.

    1. Implement SplitLists as a member function of the Unsorted List ADT.

    2. Implement SplitLists as a member function of the Sorted List ADT.

    3. Compare the algorithms used in parts (a) and (b).

  11. The specification for the Unsorted List ADT states that the item to be deleted is present in the list. Assume that UnsortedType is a templated class and that the relational operators are defined for ItemType.

    1. Rewrite the specification for DeleteItem so that the list is unchanged if the item to be deleted is not present in the list.

    2. Implement DeleteItem as specified in part (a).

    3. Rewrite the specification for DeleteItem so that all copies of the item to be deleted are removed if they exist; otherwise, the list is unchanged.

    4. Implement DeleteItem as specified in part (c).

  12. The specifications for the Sorted List ADT state that the item to be deleted is present in the list.

    1. Rewrite the specification for DeleteItem so that the list is returned unchanged if the item to be deleted is not present in the list.

    2. Implement DeleteItem as specified in part (a).

    3. Rewrite the specification for DeleteItem so that all copies of the item to be deleted are removed if they exist; otherwise, the list is unchanged.

    4. Implement DeleteItem as specified in part (c).

    1. Explain the difference between a sequential and a linked representation of a list.

    2. Give an example of a problem for which a sequential list would be the better solution.

    3. Give an example of a problem for which a linked list would be the better solution.

  13. True or false? If you answer false, correct the statement.

    1. An array is a random-access structure.

    2. A sequential list is a random-access structure.

    3. A linked list is a random-access structure.

    4. A sequential list is always stored in a statically allocated structure.

    5. A stack is not a random-access structure.

    6. A queue is a random-access structure.

    Use the linked list pictured below in Exercises 15-18.

    Click To expand
  14. Give the values of the following expressions:

    1. ptr1->info

    2. ptr2->next->info

    3. listData->next->next->info

  15. Are the following expressions true or false?

    1. listdata->next == ptr1

    2. ptr1->next->info == 60

    3. ptr2->next == NULL

    4. listData->info == 25

  16. Decide whether the syntax of each of the following statements is valid or invalid. If it is valid, mark it as such; if it is invalid, explain what is wrong.

    1. listData->next = ptr1->next;

    2. listData->next = *(ptr2->next);

    3. *listData = ptr2;

    4. ptr2 = ptr1->next->info;

    5. ptr1->info = ptr2->info;

    6. ptr2 = ptr2->next->next;

  17. Write one statement to do each of the following:

    1. Make listData point to the node containing 45.

    2. Make ptr2 point to the last node in the list.

    3. Make listData point to an empty list.

    4. Set the info member of the node containing 45 to 60.

If memory locations are allocated as shown in the second column of the following table, what is printed by the statements in the first column? Fill in the last column in the following table for Exercises 19-24. The exercise number is in the first-column comments.

Statements

Memory Allocated

What Is Printed?

int value;

value is at

location 200

 

value = 500;
   

char* charPtr;

charPtr is at location 202

 

char string[10] = "Good luck";

string [0] is at location 300

 

charPtr = string;
   

cout << &value;      // Exercise 19

& means "the address of"

 

cout << value;       // Exercise 20
   

cout << &charPtr;    // Exercise 21

& means "the address of"

 

cout << charPtr;     // Exercise 22

cout << *charPtr;    // Exercise 23

cout << &string[2];  // Exercise 24


Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)