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?

Address —Contents

52————- V

53 ————-0

54————- M

55 ————-58

56 ————-T

57 ————-54

58————- S

59 ————-52

60 ————-W

61 ————-56

62 ————-E

63 ————-60

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?

Address— Contents

32 ————-I

33 ————-38

34 ————-P

35 ————-0

36 ————-S

37 ————-34

38 ————-S

39 ————-42

40 ————-Q

41 ————-32

42 ————-C

43 ————-36

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?

Address –Contents

40 ————-N

41

42————- U

43

44 ————-B

45

46 ————-J

47

48 ————-W

49

50 ————-F

51

value of list: ___________

 

 

5. Unlike static implementations, deleting items from dynamic data structures is

extremely efficient.

Given that the list below is to remain in alphabetical order, alter whichever pointers

are necessary to delete T. (The list begins with C.)

Address —Contents

14————- Y

15————- 0

16 ————-I

17 ————-20

18 ————-T

19————- 14

20 ————-K

21 ————-18

22 ————-F

23 ————-16

24 ————-C

25 ————-22

 

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.

Address –Contents

14 ————-Y

15 ————-0

16 ————-I

17 ————-20

18 ————-T

19 ————-14

20 ————-K

21 ————-18

22————- F

23 ————-16

24 ————-C

25 ————-22

 

7. Which of the following pseudocode algorithms correctly inserts a record called

new_record immediately after the record called current_record in a linked

list?

(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.)

Algorithm #1

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

current_record

Algorithm #2

1. set the pointer field of new_record to point to the record pointed to by

current_record

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?

Address —Contents

30 ————-Y

31

32

33 ————-C

34

35

36————- A

37

38

39————- G

40

41

42 ————-W

43

44

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?

Address —Contents

30 ————-T

31

32

33 ————-Z

34

35

36 ————-S

37

38

39————- I

40

41

42 ————-R

43

44

45 ————-K

46

47

 

         R

        /    

      k       t

   /            /  

i              s   z

Value of root pointer is: _______