Problem 1
Draw pictures showing how the array below appears in a machine's memory when stored in row major order and in column major order: $$ \begin{array}{|c|c|c|c|} \hline A & B & C & D \\ \hline E & F & G & H \\ \hline I & J & K & L \\ \hline \end{array} $$
Problem 2
Suppose an array with six rows and eight columns is stored in row major order starting at address 50 (base ten). If each entry in the array requires two memory cells, what is the address of the entry in the fifth row and seventh column? What will it be if each entry requires three memory cells?
Problem 4
Design a function that takes in an \(\mathrm{M} \times \mathrm{N}\) matrix as a parameter and modifies it such that if an element in it is 0 , its entire row and column are set to 0 .
Problem 5
Why is a contiguous list considered to be a convenient storage structure for implementing static lists, but not for implementing dynamic lists?
Problem 6
Suppose you want to insert the number 3 into the list of numbers \(1,2,4,5,6,7\),
Problem 7
The following table represents the contents of some cells in a computer's main memory along with the address of each cell represented. Note that some of the cells contain letters of the alphabet, and each such cell is followed by an empty cell. Place addresses in these empty cells so that each cell containing a letter together with the following cell form an entry in a linked list in which the letters appear in alphabetical order. (Use zero for the null pointer.) What address should the head pointer contain? $$ \begin{array}{lc} \text { Address } & \text { Contents } \\ 0 \times 11 & \text { 'C' } \\ 0 \times 12 & \\ 0 \times 13 & ' G \text { ' } \\ 0 \times 14 & \\ 0 \times 15 & ' E^{\prime} \\ 0 \times 16 & \\ 0 \times 17 & ' B \text { ' } \\ 0 \times 18 & \\ 0 \times 19 & \text { 'U' } \\ 0 \times 1 A & \\ 0 \times 1 B & \text { 'F' } \\ 0 \times 1 C \end{array} $$
Problem 8
The following table represents a portion of a linked list in a computer's main memory. 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. Alter the pointers so that the letter ' \(N\) ' is no longer in the list. Then replace the letter ' \(N\) ' with the letter ' \(G\) ' and alter the pointers so that the new letter appears in the list in its proper place in alphabetical order. $$ \begin{array}{cc} \text { Address } & \text { Contents } \\ 0 \times 30 & ' J \text { ' } \\ 0 \times 31 & 0 \times 38 \\ 0 \times 32 & ' B \text { ' } \\ 0 \times 33 & 0 \times 30 \\ 0 \times 34 & ' \times ' \\ 0 \times 35 & 0 \times 41 \\ 0 \times 36 & ' N \text { ' } \end{array} $$ $$ \begin{array}{cc} \text { Address } & \text { Contents } \\ 0 \times 37 & 0 \times 3 \mathrm{~A} \\ 0 \times 38 & ' \mathrm{~K} \text { ' } \\ 0 \times 39 & 0 \times 36 \\ 0 \times 3 \mathrm{~A} & ' \mathrm{P}^{\prime} \\ 0 \times 3 \mathrm{~B} & 0 \times 34 \end{array} $$
Problem 9
The table below represents a linked list using the same format as in the preceding problems. If the head pointer contains the value \(0 \times 44\), what name is represented by the list? Change the pointers so that the list contains the name Jean. $$ \begin{array}{cc} \text { Address } & \text { Contents } \\ 0 \mathrm{x} 40 & ' \mathrm{~N} \text { ' } \\ 0 \mathrm{x} 41 & 0 \mathrm{x} 46 \\ 0 \mathrm{x} 42 & ' \mathrm{I} \text { ' } \\ 0 \mathrm{x} 43 & 0 \mathrm{x} 40 \\ 0 \mathrm{x} 44 & ' \mathrm{~J} \text { ' } \\ \text { 0x45 } & 0 \mathrm{0x} 4 \mathrm{~A} \\ 0 \mathrm{x} 46 & ' \mathrm{E} \text { ' } \\ \text { 0x47 } & 0 \mathrm{x} 00 \\ 0 \mathrm{x} 48 & ' \mathrm{M} \text { ' } \\ \text { 0x49 } & 0 \mathrm{0x} 42 \\ \text { 0x4A } & ' \mathrm{~A} \text { ' } \\ \text { 0x4B } & 0 \mathrm{x} 40 \end{array} $$
Problem 10
Which of the following routines correctly inserts NewEntry immediately after the entry called PreviousEntry in a linked list? What is wrong with the other routine? Routine 1: 1\. Copy the value in the pointer field of Previousentry into the pointer field of NewEntry. 2\. Change the value in the pointer field of PreviousEntry to the address of NewEntry. Routine 2: 1\. Change the value in the pointer field of Previousentry to the address of NewEntry. 2\. Copy the value in the pointer field of Previousentry into the pointer field of NewEntry.
Problem 11
Design a function to find the \(k\) th element in a single linked list with \(\mathrm{n}\) elements.
