Suggest a suitable structure for a given situation.


Teaching Note:


Sample Question - FORMER CURRICULUM:

An application is running on a computer. The main program calls up a subprogram.
When the subprogram finishes, control is passed back to the main program.

(a) Explain how a stack would be used to ensure that the correct sequence
of instructions is followed. Reference should be made to the use of the
program counter. [3 marks]

Sample Question - FOMER CURRICULUM:

An application requires a list of names to be held in alphabetical order in the main
memory. The program must allow for insertion or deletion of names from this list.

(a) Explain why a linked list would be an appropriate data structure for holding
these names. [3 marks]

(b) Describe the steps required to insert the name Guillen into the list. (It can be
assumed that it will not be inserted either at the beginning or at the end.) [3 marks]

(c) (i) Identify another data structure that would be suitable for maintaining this
list of names. [1 mark]

(ii) For this new structure, discuss the advantages and disadvantages of
maintaining a list of names over the original linked list. [3 marks]

JSR Notes:

When deciding between static or dynamic structures, you would choose a static structure like an array because of its simplicity, but you would only pick it in a case where either
- you know exactly how many elements you will be working with
- or the number of elements is very small for the device you are working with; so for example, an array of 100 elements run on a laptop computer.

You would pick a dynamic structure like a linked list or a tree when
- the size of the structure is either presently unknown or is variable
- it is a priority to conserve memory, so you don't want to waste even a few bytes

In terms of picking between a tree or a list,
- you would pick a list when you want to access from only one end, as in a stack or a queue, and/or searching is not a priority
- you would pick a tree when searching will be necessary