Topic Two Assessment Past paper Questions

Question 1

Explain how a single stack can be used to reverse the order of the items in a queue.

Answer 1

(Until the queue is empty) repeatedly remove/delete (the front item) from the queue and push it onto the stack;
(Until the stack is empty) repeatedly pop items from the stack and add them to the (rear of the) queue;

Question 2

Define the term binary tree.

Answer 2

Rooted (tree);
Where each node has at most two child nodes;

Question 3

State two components of a stack frame.

Answer 3

local variables;
return address;
parameters;
register values;

Question 3

Describe the steps involved in adding a record to a hash table.

Answer 3

Hash algorithm applied;
to key value; NE. to data/item
result is location in table where the record should be stored;
if location is not empty;
then use next free location;

Question 3

Discuss the advantages and disadvantages of dynamic data structures compared to
static data structures

Answer 3

Max 2 for advantages of dynamic data structures
No wasted memory;
Can grow as more data is added to the data structure // no limit on number of
items that can be added (except due to hardware limitations);
Resources only allocated as they are needed (with static data structures they are
allocated at creation even if not needed until later);
Max 2 for disadvantages of dynamic data structures
Additional memory needed for pointers;
Can result in memory leak (if memory that is no longer needed is not returned to
the heap);

Question 4

Describe the steps involved in adding an item to a linear queue that has been implemented as a static data structure using an array.

Answer 4

Check that the queue is not already full;
(if it isn’t) then add 1 to the value of the rear pointer;
then add the new item to the position indicated by the rear pointer