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:

 

Choice of a Static Structure

You would choose a static structure like an array in three general cases:

1. You know exactly, or at least roughly, how many elements you will be working with
So often when related to static physical numbers of things; physical things that can't or won't likely change.

Examples
- The pixels on a monitor; at certain resolutions there are exactly a certain number of rows and columns - for example 1024 by 768. So any and all data structures related to those pixels could be static arrays of those fixed sizes.
- Or perhaps a theatre that has exactly 776 seats.

2. 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. With such small arrays, even if a lot of the element remain empty, you are not going to "break the bank" in terms of memory. And keep in mind that each node of a dynamic structure actually, by definition, takes up more memory, because each node needs one or two pointers to the next node(s)

Examples
- If there are 10 airbags in a car, a static data structure is fine, even if you leave room for extensibility, and set the array size to 20.
- If there are a couple of dozen courses offered in a particular school department; even if you make the array bigger than the maximum possible number of courses, say 20, these are small numbers, and so small amounts of memory.

3. If direct access (also more properly, but misleadingly refered to as "random access") is a priority.
With arrays, this can be done through hashing, in which a mathematical calculation is able to determine exactly what element a data item is at, so no searching whatsoever is necessary.

(And, more generally, you just want to be able to search/access quickly, either through a binary search or hashing.)

Examples
-You want to be able to directly access, quickly, the license plate of a vehicle at the front gate of the school, to know if it is registered with security. Using hashing, this can be done very quickly.
- Security access of the key cards to doors of the Math Quad. When swiped you don't want to wait even a second for a search result, so you hash it and get it almost immediately.

 

Choice of a Dynamic Structure

You would pick a dynamic structure like a linked list or a tree when:

1. The size of the structure is either presently unknown or is variable. A good general category of when this is the case is most database structures.

Examples
-As clear, straight-forward examples, you can think of a school with changing enrollment, or demographics databases working with varying populations. If the changes are only limited, then maybe it's easier to just use an array, but there comes a point where you start wasting more memory than you deem fit, so that's the line you cross over to the suitability of a dynamic structure.

2. It is a priority to conserve memory, so you don't want to waste even a few bytes, like on a small device

Examples
- Anything being stored in the limited memory of a small micro-controller like the ones found in air conditioners, fridges, and other household appliances.
- Any safety critical device in that has a limited amount of memory.

3. You will be working with something that acts like a stack or a queue

Examples
- See below.

 

List vs Tree

A. Lists as Stack
You would pick a list as a stack when you want to work with data at only one end, in a LIFO manner,
And, also, searching, or anything else that works with the whole data structure is not a priority.

Examples
- Refer back to the list notes, but IT situations like method calling, exception stacking, etc.

B. List as Queue
You would pick a list as a queue when you want to work with data at opposite ends, in a FIFO manner.

Examples
- Refer back to the queue notes, but mirroring real life situations like the functioning of a cafeteria line up.

C. Tree
You would pick a tree when quick searching will be necessary
AND, not wasting memory is a priority.

Examples
- A database for a school to be accessed from small devices, such as simple phones or simple tablet computers.

 

Example Questions

What would be the best choice of structure for the following situations:

(a.) A program for a small "fitbit" kind of wearable device, which requires searching through a bunch of database information related to each "fitness activity" ever recorded by the device.

(b.) A program for an automobile assembly line which has 668 different robots, any of which may need to be urgently located and communicated with.

(c.) The air traffic control system at Istanbul New Airport, which controls which aircraft are to take off next.

 

Answers:

(a.) Binary search tree. Definitely dynamic, since for a small device with memory limitations, working with an unknown number of "activities". And it needs to be searched, so binary search tree is the best.

(b.) An array. A static number, so a static structure. And likely not memory issues with the controlling server, so fine if it's made to be more than 668, which could be needed if new robots are added, say going up to 1000 elements. And note that to have the fastest access, hashing and direct access could be possible.

(c.) List treated as a queue. A queuing situation calls for a queue. And also note that this is a non-static, dynamic situation.