Assessment Test
Unit 7 Data structures
Final assessment test
1. A hospital has asked for a program that will control the order in which the arrivals are seen
in the accident and emergency department.
(a) A priority queue has been chosen to store the arrival information.
(i) State the property of a priority queue that makes it suitable for this application. [1]
(ii) The priority queue is implemented using a circular queue.
State an advantage of a circular queue which makes it more efficient in use of
memory. [1]
(b) A test version of the priority circular queue consists of 5 cells. Arrival information
consists of a severity rating and a last name. The severity scale is 3 (least severe),
2 (moderately severe), and 1 (most severe). For example, Mr Jones has a severity
rating of 2. His arrival record would be ‘2 Jones’.
Complete the diagram to show the results after the following operations. [4]
Note: The first element in the queue has an index of 0.
arrivals
[0] [1] [2] [3] [4] count front rear returned
1 Black 1 Singh 2 Jones 3 Reeve 4 0 3
Dequeue
Enqueue
‘3 Mason’
Enqueue
‘2 Ing’
Dequeue
2. A stack is an important data structure in computer science.
(a) Define the term stack. [2]
(b) A call stack is used when subroutines are called.
Name two items that may be put on a call stack. [2]
1
Assessment Test
Unit 7 Data structures
(c) Explain how a recursive algorithm could cause a system to crash. [2]
(d) State one other use of a stack in a computing system. [1]
3. (a) Describe the difference between a dynamic and a static data structure. [2]
(b) Nodes in a linked list consist of a data field and a pointer to the next node:
The linked list is implemented in an array.
(i) Show how the array is initialised with a start pointer and a nextfree pointer. [2]
index name pointer
0
start =
1
2
3
nextfree =
4
5
6
(ii) Names are added to the linked list in the sequence Charles, Amy, Tasmin, Gerri.
Show the array and pointers after these names have been added. [2]
index name pointer
0
1 start =
2
3
4 nextfree =
5
6
2
Assessment Test
Unit 7 Data structures
(iii) The function ListProcess is defined as follows:
function ListProcess
x = 0
currentPtr = start
while currentPtr <> null
x = x + 1
currentPtr = subjectList[currentPtr].pointer
endwhile
print (x)
endfunction
(c) (i) Complete the following trace table to show the operation of function
ListProcess when it is processes the linked list below. [2]
(ii) What is its purpose? [1]
Trace table: subjectList
x currentptr OUTPUT Index subject pointer
0 Maths null
1 English 3 start = 1
2 History 0
3 Geography 2 nextfree = 4
4 null
(d) Amend the algorithm so that it prints all the names in the linked list. [1]
4. Hashing is often used when large amounts of data need to be stored.
(a) Explain how a hashing algorithm works. [3]
(b) A particular hashing algorithm sums all the individual digits in a number and takes the
remainder after division by 11 as the address in the hash table. Apply this algorithm to
7823901. [1]
3
Assessment Test
Unit 7 Data structures
(c) In the following hash table, collision resolution is done by storing the item in the next
free slot.
[0]
[1]
[2] Jones
[3] Wilson
[4] Smith
[5] Brown
[6]
[7]
[8] Green
[9]
[10
Gold
]
(i) The value “Redmond” needs to be added to the table. The hash value is 6.
State the value of the table index where “Redmond” is stored. [1]
(ii) The value “Farmer” needs to be added to the table. The hash value is 10.
State the value of the table index where “Farmer” is stored. [1]
(d) The performance of a particular large hash table has degraded as the table fills up.
(i) Explain why this might be the case. [1]
(ii) Explain one possible way of improving the performance of the hash table.
[2]
5. Towns and the connections between them can be represented as a graph which has a set
of nodes connected by edges. This representation is an abstraction.
(a) Define the term data abstraction. [2]
4
Assessment Test
Unit 7 Data structures
(b) Complete the adjacency list for this graph. [2]
A {C:7}
B
C
D
(c) Complete the adjacency matrix for this graph. [2]
A B C D
A
B
C
D
6. (a) Here is a binary tree.
Complete the array implementation of this tree. [2]
left data right
A[0] 3 H 1
A[1]
A[2] 5 R -1
A[3] -1 F -1
A[4] -1 X -1
A[5]
(ii) List the nodes in the order in which they are visited for each traversal. [3]
5
Assessment Test
Unit 7 Data structures
Pre-order:
In-order:
Post-order:
(c) Add the following items to a binary tree so that it may be quickly searched to find a
particular item:
Liam, Mary, Zoe, Carla, David, Lucy, Adam [2]
(d) Write a pseudocode for a recursive procedure to output the names in post-order
traversal of the tree. [5]
The first line of the procedure is given below.
procedure postOrderTraverse (root)
[Total 50 marks]
