1.1 Data structures

Question 1

What is a data structure

Answer 1

a collection or group of related data items

Question 2

why are data structures useful

Answer 2

collects together basic data types (e.g. integer, real etc.) and allows data to be organised in a convenient, logical manner related to the program being developed.

can be accessed, searched, sorted etc. more quickly than data held in a file as data structures are held in memory

Question 3

name 2 types of data structure

Answer 3

arrays, records

Question 4

give an example of data to be stored in a 2 dimensional array

Answer 4

the sales of different products (downwards column) per month (across column)

Question 5

give an example of data stored in a 3d array

Answer 5

the test scores of different students, per form group

Question 6

what is a record data structure and where would it be used?

Answer 6

The record data structure allows items of data relating to something to be grouped together into a single record type.

cam be used in e.g. pseudocode

Question 7

What is a stack data structure

Answer 7

a stack is a LIFO data structure

is a limited access data structure

is used as e.g.

run time stack mechanism (keep track of where it is up to with procedure calls)

undo feature in an application

Question 8

explain adding an item to a stack

Answer 8

increment the stackpointer (add 1 to) and place the new item in the position indicated by the stackpointer

Question 9

explain removing an item from a stack

Answer 9

display the item indicated by stack pointer (e.g. pressing undo in a web browser displays the previous page) and the decrement (take 1 from) stackpointer

Question 10

how could a stack be implemented using an array and variable

Answer 10

the array stores the items in the stack, the variable (e.g. the stack pointer) always points at the last element added to the stack

Question 11

pseudocode procedure to add data to a stack

Answer 11

Procedure AddToStack
Get Item
IF Stack pointer = limit
Error message “stack full”
ELSE
Stackpointer := Stackpointer + 1
Stack[Stackpointer] := Item
END IF
End Procedure

Question 12

pseudocode procedure to remove data from stack

Answer 12

Procedure RemoveFromStack
IF Stack pointer = 0
Error “Stack empty”
ELSE
Output stack[Stackpointer]
Stack pointer := Stackpointer –1
END IF
END Proc

Question 13

what is a queue data structure and how is it implemented

Answer 13

a FIFO data structure (First In First Out)

e.g. queuing up in a shop, processes in a ‘round-robin scheduling policy’

often implemented using an array and two pointers to indicate the start and the end of a queue

Question 14

explain removing an item from a queue data structure

Answer 14

involves displaying the data in position indicated by start pointer (front of queue) and then incrementing (+1) the start pointer

Question 15

explain adding an item to a queue data structure

Answer 15

involves incrementing (+1) the end pointer (back of queue) and putting data into that position

Question 16

what happens when the end pointer goes beyond the end

Answer 16

the queue is circular so if the end pointer goes beyond the end of the queue, it starts again at 1.

Question 17

draw a diagram to represent the stack data structure, add an item to it, and remove an item

Question 18

draw a diagram to represent the queue data structure, add an item to it, and remove an item

Question 19

pseudocode algorithm to add an item to a queue data structure

Answer 19

Procedure AddtoQueue
If Endpointer < MaxSize then
Queue[Endpointer]= newitem
Endpointer = Endpointer + 1
Else
Output “queue is full”
End if
End Procedure

Question 20

pseudocode algorithm to remove item from queue data structure

Answer 20

Procedure RemoveFromQueue
If startpointer <> Endpointer then
Output Queue[startpointer]
Queue[startpointer] = null
startpointer = startpointer + 1
else
output “queue is empty”
end if
end procedure

Question 21

What is a linked list and what does it consist of

Answer 21

a linked list is a dynamic data structure (its size can be increased and decreased as required, unlike an array)

items can be added to a linked list without having to move the existing items to make space

items can be removed from a linked list without having to shift the other items to fill the gap left

consists of:
start pointer which points to the first item in the list, which will have a pointer to the next item and so on.

there is also another linked list of free locations, items that are deleted from the normal linked list are added onto the front of this free list. Items added to the linked list are obtained from the front of the free list.

Question 22

advantages of a linked list

Answer 22

A linked list is a dynamic data structure: its size can be increased and decreased as required. An array is static and therefore its size is fixed.

Items can be added into a linked list without having to move the existing items to make space.

Items can be removed from a linked list without having to shift the other items to fill in the gap left

Question 23

disadvantages of a linked list

Answer 23

more complex to program than an array

extra programming required to access the data in the opposite direction

can only be accessed in a linear manner

Question 24

what is a binary tree data structure and what could it be used for

Answer 24

a type of tree where all nodes can either have 0, 1 or 2 children, each node having a left pointer and right pointer to their children (which could be empty/null)

we could use binary trees to keep an ordered list for searching using the rule that:
-anything ‘less than’ or before the data in the alphabet is to the left

-anything ‘greater than’ or after the data is to the right

Question 25

how would a new item be added in an ordered binary tree

Answer 25

Starting at the root node of the tree;

Compare the data you want to add to the current node;

If the new data is less than the node then follow the left pointer else follow the right pointer;

Repeat this until you reach the end of the tree;

Update the pointers of the last node to point to the new one.

Question 26

redraw a tree with a specified node deleted

Question 27

removing data from a binary tree

Answer 27

Removing data from a binary tree is a little trickier compared to adding an item. The steps you will follow will depend on the type of node being deleted.

There are 3 possible cases:
A node has no children - remove the node and the pointer which pointers to it

A node with 1 child - remove the node and its pointers, the node it was connected to has a pointer to the node that the one that was removed points to

A node with 2 children (find min in right node) - find the value of the smallest node to the right pointer of the one to be removed. You then replace that node with the one to be removed and remove the small node with the pointer that points to it.

Question 28

the three steps in pre-order traversal

Answer 28

the root node is visited first

then the left subtree

then the right subtree

Question 29

in-order traversal

Answer 29

left subtree visited first

then the root node

then the right subtree

Question 30

post-order traversal

Answer 30

left subtree visited first

then the right subtree

then the root node

Question 31

advantages of a binary tree

Answer 31

if the tree is balanced (same number of items on each side) then it can be quick to find data in a tree, this is because the number of items being searched is effectively halved each level down the tree

may be more idk

Question 32

disadvantages of a binary tree

Answer 32

find some

Question 33

draw a representation of an unbalanced binary tree and what is the side effect

Answer 33

all go down the same pointer

side effect is that it will slow the search down

Question 34

what is a hash table and what does it consist of

Answer 34

has 2 components:
table where the data is stored
a mapping function (e.g. hashing algorithm)

The hashing algorithm uses data that is going to be stored to generate the location in the table where it will be stored.

Question 35

What is separate chaining in hash tables

Answer 35

e.g. if the hashing algorithm produces the same index value for 2 different pieces of data, a collision occurs and a linked list is created to hold both sets of data.

However, it will slow the process of finding data again down, as once the hash location has been computed, the linked list will need to be searched aswell.

Question 36

in hash tables, why should we ensure that there is an evenly distributed spread of data

Answer 36

collisions could occur otherwise

Question 37

What would be the pseudocode to display all of the items in a linked list?

Answer 37

Procedure DisplayAll
p = start
While p <> -1
Display data(p)
p = next (p)
End While
End procedure