mark schemes

Question 1

Comparing data structures

Answer 1

• compare static or dynamic (and why this is applicable)
• compare contiguous memory locations or non-contiguous memory locations (and why this is applicable)
• compare how and how quickly items are accessed (and why this is applicable)

Question 2

Binary tree searches

Answer 2

• write comparison
• write result (go left, go right)
• repeat

Question 3

Data structure definitions

Answer 3

• is static or is dynamic

- how is data held (2 points)

Question 4

Adding Nodes Linked Lists

Answer 4

• new item is placed in address at next free
• next free is incremented
• penultimate node’s pointer is adjusted to point to new item’s pointer
• new item’s pointer is set to null to indicate that it is at the end of the list

Question 5

Statistic data structure definition

Answer 5

• size is fixed at creation

- size can’t change during processing

Question 6

Dynamic data structure definition

Answer 6

• size can change as needed

- during processing

Question 7

Adjacency List over Matrix

Answer 7

• graph is sparse
• edges are rarely changed
• prescence/abscence of specific edges don’t need to be noted

Question 8

Tree Properties

Answer 8

• connected
• undirected
• with no cycles

Question 9

How a value is stored in a hash table

Answer 9

• hashing algorithm is applied to the key
• result is the address in which the value is stored
• in the event of a collision (different keys generating the same address)
• the value is placed in the next address

Question 10

Purpose of rehashing

Answer 10

• large number of possible addresses in a hash table are filled
• this makes searching and management inefficient

Question 11

Rehashing Steps

Answer 11

• larger hash table is created

- each value in the existing table added to the new table using a hashing algorithm

Question 12

how are collisions resolved

Answer 12

item has the same address as _, add one to the address until a free space is found

Question 13

stack for back button

Answer 13

-A (data structure) that operates on a first in last out basis
(1)
-When going back a page you want to go back to the last
page visited/when displaying the history we want to start
with the most recent first (1)

Question 14

dynamic data structure - advantages

Answer 14

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);

Question 15

dynamic data structure - disadvantages

Answer 15

Additional memory needed for pointers;

Can result in memory leak (if memory that is no longer needed is not returned to
the heap);

Can take longer to access an item directly (for data structures that allow this);

Question 16

describing adding to (static) queue

Answer 16

Check that the queue is not already ful (rear = max)l;

(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;

Question 17

describing removing from (static) queue

Answer 17

check that the queue is not empty (front = -1)

add 1 to the value of the front/start pointer

return the value at the position indicated by the front pointer - 1

Question 18

adding item priority queue

Answer 18

Starting with the item at the rear of the queue move each item back one place in the array;
Until you (reach the start of the queue or) find an item with the same or higher priority than
the item to add;
NE. same priority
NE. higher priority
Add the new item in the position before that item