2. The table following shows a dynamic implementation of a list of characters. Some of
the locations contain a letter, and each is followed by a location that holds a pointer to
the next letter in the list.
Notice that a pointer points to a character. For example, assume there is a pointer
called list pointing to the first character in the list. Say list has the value 62,
then the first character is E.
0 is used for the NULL pointer.
What are the characters in the list in the correct order?
list is: ____E____________________________________
3. The table following shows a dynamic implementation of a list. The pointer to the
first item in the list has value 40.
What is the list?
list is: ________________________________________
4. The table following shows the contents of main memory. Put addresses into the
empty pointer fields to build a list of the characters in alphabetical order. Use 0 for
the NULL pointer.
If a pointer called list is to point to the first letter in the list, what would be the
value of list?
value of list: ___________
5. Unlike static implementations, deleting items from dynamic data structures is
Given that the list below is to remain in alphabetical order, alter whichever pointers
are necessary to delete T. (The list begins with C.)
6. Inserting a new item is similarly efficient.
Below is the previous list. First cross-out the letter T in the table and write-in the
letter H. Now update whatever pointers are necessary to insert H into the list,
maintaining the list in alphabetical order. The list begins with C.
7. Which of the following pseudocode algorithms correctly inserts a record called
new_record immediately after the record called current_record in a linked
(HINT: to help you solve the problem, draw a picture of a linked list with 3 items,
where current_record is the middle item. Draw new_record outside the list,
then follow the steps of each algorithm to see how the list is changed.)
1. set the pointer field of current_record to point to new_record
2. set the pointer field of new_record to point to the record pointed to by
1. set the pointer field of new_record to point to the record pointed to by
2. set the pointer field of current_record to point to new_record
correct algorithm is: ________________________
briefly, what is wrong with the other algorithm?
8. A record in a dynamic data structure can contain more than one pointer field. Given
the table following, fill-in the first location after each letter to build a list of the letters
in alphabetical order. Set the second location after each letter so that the letters are
found in reverse alphabetical order. Make sure that each list ends correctly, using 0
for the NULL pointer.
If the pointer alpha points to the start of the list in alphabetical order and reverse
points to the start of the reverse order list, what are the values of these two pointers?
value of alpha is: _______
value of reverse is: _______
9. Each node in a binary tree can be stored using 3 memory locations. The first holds
the key value of the node (a letter here), the second contains a pointer to the node’s
left child and the third contains a pointer to the right child. Using this representation
method, fill-in the pointer fields so that the table represents the tree given below.
What should the value of the root pointer be?
i s z
Value of root pointer is: _______