Data structures practice questions.

A program reads a long text and must keep a running total of how many times each of the 26 letters of the alphabet has appeared. Which structure is the most suitable store for those totals?

• A stack of 26 integers, one pushed for each letter
• A queue holding the letters in the order they are read
• Twenty-six separately named integer variables, one per letter
• An array of 26 integers, one position per letter

Answer: An array of 26 integers, one position per letter

The position of a letter in the alphabet can be turned into an index, so one array element can be found and increased in a single step. A stack or queue only gives access at one end, so reaching the total for a letter would mean dismantling the structure.

A sorted array of 1000 values is held in order and a new value has to be inserted at position 400 so that the order is preserved. What must happen?

• The array is left unchanged and a pointer records the new value
• Every element from position 400 onwards moves up one place
• The new element is written at the end and the array is re-sorted
• Only the element currently at position 400 has to be moved

Answer: Every element from position 400 onwards moves up one place

Array elements occupy consecutive positions, so making room in the middle means shifting about six hundred elements, and the cost of an insertion grows with the size of the array. This is the weakness that a linked structure removes, at the cost of no longer being able to reach element n directly.

The values 3, then 8, then 5 are added to an empty stack and, in that same order, to an empty queue. One item is then removed from each structure. Which single observation tells the two structures apart?

• The stack releases 3 while the queue releases 5, because both give up their oldest item.
• The stack releases 5, the most recent value, while the queue releases 3.
• Both structures release 5, because the newest item is always the reachable one.
• Both structures release 3, because the first value added is always available first.

Answer: The stack releases 5, the most recent value, while the queue releases 3.

A stack is last-in first-out, so its removal takes 5, the value added most recently. A queue is first-in first-out, so its removal takes 3, the value that has waited longest. Both structures hold the same three values and differ only in which one is reachable.

A drawing program must let the user undo the actions they have carried out, always taking back the most recent action first. Which store of the actions makes the next undo the correct one every time?

• A queue, because the action that has waited longest is released next.
• A one-dimensional array that is always read from index 0 upwards.
• A stack, because the action taken off is the one added most recently.
• A collection whose items can only be reached in the order they were added.

Answer: A stack, because the action taken off is the one added most recently.

Undo needs last-in first-out order, which is exactly the rule a stack applies. A queue, or a list read from its first place upwards, would offer the oldest action next, which is the wrong end of the history.

A data structure whose number of elements is decided when it is created and cannot change while the program runs is described as ___. (one word)

Answer: static

The defining feature is that the memory is reserved once and never renegotiated, which is why an array can overflow but never shrink. A dynamic structure asks for and releases memory while the program is running.

A two-dimensional array is declared with 4 rows and 6 columns. State the number of elements it can hold in total. (give a whole number)

Answer: 24

Both indices start at zero in the house pseudocode, so the valid row indices run from 0 to 3 and the column indices from 0 to 5 even though the counts are 4 and 6. Reading the largest index as the count is the standard off-by-one in two dimensions as well as in one.