Assignment 8

Contents:

  • Overview
  • Internet Requirements
  • Practice Problems
  • Problems to be Submitted
  • Extra Credit

    • Overview

    Topic: Data Structures
    Related Reading: Ch. 9.1-9.2, 9.7 and notes
    Due:

    Internet Requirements

    You may want an Internet connection for several practice problems. However you do not necessarily need the connection for completing the assignment, other than for submission.

    Practice Problems
  • The following data is a representation of a linked list. Each "node" of the list is represented using two cells of memory. The first of the two cells stores a letter of the alphabet and the second of the two cells stores a "pointer" to the cell of memory which begins the following node in the linked list. The "head" of the list is cell 11. A pointer value of 0 designates the end of the list.

    Memory Contents
    (in decimal)    		 Cell 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
    Value Z 15 X 11 C 13 V 1 B 0 N 5 M 7 L 9
    1. Give the sequence of characters contained in the linked list.
    2. We would like you to delete the letter "V" from the linked list. Please show the contents of all memory cells after the deletion has been performed.
    3. We would like you to insert the letter "K" into the linked list so that it is sequenced after the letter L. (You may use any pair of cells for this new entry which were "unused" in the previous list). Please show the contents of all memory cells after the insertion has been performed.
    (answer)
  • Exercise 57 of Ch. 9 (p. 328); answer in back of text
  • Exercise 58 of Ch. 9 (p. 328); answer at the bottom of this page
  • You may also quiz yourself by playing with some demos:
  • Linked List Demo
  • Binary Search Tree Demo

    • Problems to be Submitted (20 points)
    1. (3 points)
      Fill in the missing values for the following memory contents in a way so that it represents a linked list containing the sequence of characters "ANSWER". Which cell is the head of your list?
      Memory Contents
      (in decimal)      		 Cell 1 2 3 4 5 6 7 8 9 10 11 12
      Value R
      		W
      		E
      		S
      		A
      		N
    2. (9 points)
      The following data is a representation of a linked list. The "head" of the list is at cell 7. A pointer value of 0 designates the end of the list.

      Memory Contents
      (in decimal)      		 Cell 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
      Value Q 0 W 11 E 12 R 3 T 15 Y 9 U 13 P 1

      1. Give the sequence of characters contained in the linked list, beginning with the "R" stored at the head of the list in cell 7.
      2. We would like you to insert the letter "G" into the linked list so that it is sequenced immediately following the letter "T" in the list. (You may use any pair of cells for this new entry which were "unused" in the previous list). Please show the contents of all memory cells after the insertion has been performed.
      3. Having inserted "G" from the previous step, please continue by performing a deletion of the entry containing "W" from the list. Please show the contents of all memory cells after the deletion has been performed.
    3. (4 points)
      Consider the tree on page 328.  List the exact sequence of elements in the tree against which each target is compared to see whether the target is in the tree.
      a.  jim   b.  andy    c.  katherine   d.  susy
    4. (4 points)
      For this problem, consider the binary search tree from Figure 9.19 on p. 317 of the text.
      1. If "michael" were inserted into this tree, where would the item be placed?
      2. If "kim" were inserted into this tree, where would the item be placed?
      3. If "jill" were inserted into this tree, where would the item be placed?
      4. If "louis" were inserted into this tree, where would the item be placed?
    Overall, please type your answers to all of the problems in a single document to be submitted electronically. Please see details about the submission process.

    Extra Credit (2 points)

    The extra credit involves gaining a deeper familiarity with the recursive procedure for printing the information in a binary tree, as described by the Print algorithm on p. 318. Though this is described in relation to a binary search tree, the procedure can be used on an arbitrary binary tree.

    Your extra credit task is the following. We want you to trace through the recursive execution of the procedure Print when applied to the tree which is displayed in Figure 9.16 on p. 312.

      As demonstrated in the chapter, the procedure Print will get applied many times with varying parameters. Also, there is a difference between the order in which nodes become the parameter for a call to the Print routine and the order in which nodes get written to output by the Write command.
    1. Please give the exact sequence of calls to this routine, reporting the root of each subtree in the order the applications are applied.

      Hint: the first application is Print(the tree rooted at "1").

    2. The only output generated by the procedure is from the command Write within that routine. In what order will the values be printed to output, when starting the process on the original tree?

      Hint: You will find that this is NOT the same order as you report for the previous question. For example, "1" is NOT the first item in the output.

    problem 58
           25
          /  \
        15    30
       /     /  \
      7    26   40
     / \       /
    2   8     35
    Last modified: 25 Oct 2004