Answer the following questions:

1. Suppose an array with five rows and 6 columns is stored in row major order starting at address 140(base 10). If each entry in the array requires two memory cells, what is the address of the entry in the fourth row and third column? (3 points)

2. Rework question 1 assuming column major order rather than row major order. (2 points)

3. The following table represents a portion of a linked list in a computers main memory. The letters are in alphabetical order.Each entry in the list consists of two cells: The first contains a letter of the alphabet; the second contains a pointer to the next list entry. First, alter the pointers so that the letter K is no longer in the list and show that list. (2 points) Then replace the letter Kwith the letter G (i.e. put G in address 38), and show that list (re-order it). (2 points)

AddressContents

30J

3138

32B

3330

34X

3546

36N

3740

38K

3936

40P

4134

4. a. Suppose a queue implemented in a circular fashion is in the state shown in the following diagram. Draw a diagram showing the structure after the letters G and R are inserted, three letters are removed, and the letters D and P are inserted. (3 points)

Head pointerTail pointer

A

L

K

F

U

b. What error occurs in part (a) if the letters G, R, D, and P are inserted before any letters are removed? (2 points)

5. The following table represents the contents of a block of cells in a computers main memory. Some cells contain letters of the alphabet, and each of those cells is followed by two blank cells. Fill in the blank cells so that the memory block represents the tree that follows. Use the first cell following a letter as the pointer to that nodes left child and the next cell as the pointer to the right child. Use 0 for null pointers. (3 points) What value should be in the root pointer? (1 point)

AddressContents

30B

31

32

33K

34

35

36M

37

38

39E

40

41

42J

43

44

45R

46

47

J

B

E

M

K

R

6. The table below represents a stack stored in a contiguous block of memory cells, as discussed in the text. If the base of the stack is at address 22 and the stack pointer contains the value 24, what value is retrieved by a pop instruction? (2 points) What value is in the stack pointer after the pop operation? (2 points)

AddressContents

22G

23D

24A

25C

26E

7. Sometimes a single linked list is given two different orders by attaching two pointers to each entry rather than one. Fill in the table below so that by following the first pointer after each letter one finds the name Petra, but by following the second pointer after each letter one finds the letters in alphabetical order. (2 points) What values belong in the head pointer of each of the two lists represented? (2 points)

AddressContents

74R

75

76

77P

78

79

80E

81

82

83A

84

85

86T

87

88

8. Design a function for combining two sorted contiguous lists into a single sorted contiguous list. Write this in pseudo-code. (2 points)

9. Design a function for reversing the order of a linked list.Write the pseudo-code. (2 points)