Data Structures (OCR A Level Computer Science): Exam Questions

2 hours38 questions
11 mark

A stack is one data structure that is available for Sundip to use. She could also use a queue, list, linked list, array or tuple.

State how a tuple is different to a list.

Did this page help you?

21 mark

A computer uses a stack data structure, implemented using an array, to store numbers entered by the user.

The array is zero based and has 100 locations.

Fig. 8 shows the current contents of the stack and the first 9 locations of the array

Diagram of an array with indexes 0-8. Values listed are 10, 5, 6, 23, 1 at indexes 0-4, respectively. Pointer value is 5.

State the purpose of pointerValue

Did this page help you?

32 marks

A printer buffer is a storage area that holds the data, known as jobs, that are to be printed by a printer.

A simulation of the printer buffer uses a queue data structure to store jobs that are waiting to be printed. The queue is not circular.

The printer buffer is represented as a zero-indexed 1D array with the identifier buffer.

Fig. 2 shows the current contents of the queue buffer and its pointers.

Diagram of a queue showing queueHead at 0 and queueTail at 3. Entries 0-3 contain jobs 124-127, with positions 4-6 empty.

State the purpose of the pointers queueHead and queueTail.

Did this page help you?

4a2 marks

Sundip writes an algorithm to carry out addition and subtraction. The algorithm will use an initially empty stack with the identifier numbers and will take input from the user

The action the algorithm takes depends on the value input by the user. These actions are listed in Fig. 2.

Table showing operations: A adds, S subtracts, E outputs and ends, other values push to stack. Operations involve stack manipulation.

A stack is one data structure that is available for Sundip to use. She could also use a queue, list, linked list, array or tuple.

Describe one difference between a stack and a queue.

4b2 marks

Describe one difference between an array and a list.

Did this page help you?

5a2 marks

A tree is one example of a data structure.

Give two characteristics of a tree data structure

5b2 marks

Describe how a leaf node is deleted from a binary search tree.

5c4 marks

Identify the order that the nodes will be visited in a depth-first (post-order) traversal of this binary search tree.

Hierarchical diagram with 'H' at the top, branching to 'C' and 'P', then 'C' splits into 'A' and 'F', while 'P' splits into 'L' and 'T'.

Did this page help you?

62 marks

A program stores data in a linked list.

The current contents of the linked list are shown in Fig. 3, along with the linked list pointers.

Data structure diagram with headPointer at 1, freeListPointer at 4, and a table listing locations, data words, and pointers, including NULL entries.

Fig. 3

State the purpose of headPointer and freeListPointer in the linked list shown in Fig. 3.

Did this page help you?

71 mark

A program stores data in a linked list.

The current contents of the linked list are shown in Fig. 3, along with the linked list pointers.

Data structure diagram with headPointer at 1, freeListPointer at 4, and a table listing locations, data words, and pointers, including NULL entries.

Fig. 3

State the meaning of the pointers with the value NULL in the Figure

Did this page help you?

82 marks

A program stores data in a linked list.

The current contents of the linked list are shown in Fig. 3, along with the linked list pointers.

Data structure diagram with headPointer at 1, freeListPointer at 4, and a table listing locations, data words, and pointers, including NULL entries.

Fig.3

A procedure outputs the data in the linked list shown in Fig.3 from the first item in the list, to the last item.

Give the output from the procedure.

Did this page help you?

9a1 mark

A computer program is being written to store data about students.

Fig. 2 shows a binary search tree that stores data about students.

Each student is represented by their ID number. The current contents of the binary search tree are:

A hierarchical tree diagram with top number 2005, branching to 1920 and 2350, showing further subdivisions down to 1952 and 2000 at the bottom.

Fig. 2

Identify the root node in the binary tree shown in Fig.2

9b2 marks

Identify two leaf nodes in the binary tree shown in Fig. 2

9c4 marks

Four more students are added to the binary search tree shown in Fig. 2 in this order:

1420 2050 2780 2600

Complete the binary search tree here by adding the new students to it

A tree diagram shows numbers: 2005 at the top, branching to 1920 and 2350, with further branches to 1500, 1985 (with 1952 and 2000), 2100, and 2560.

Did this page help you?

101 mark

A bubble sort will sort an array of 50 integer values called numberArray.

State why the integer values are stored in an array instead of separate variables.

Did this page help you?

11a1 mark

Fig. 5 shows a graph data structure representing a small section of a parcel delivery network. Each node represents an address where deliveries need to be made. The edges show the possible routes and distances between these deliveries.

Diagram of a graph with nodes A to H connected by lines. Lines are labelled with numbers: 3, 7, and 11, indicating weights. Nodes form a network.

State one way a directed graph is different to an undirected graph.

11b1 mark

State one way a graph data structure is different to a tree data structure.

Did this page help you?

121 mark

Fig. 5 shows a graph data structure representing a small section of a parcel delivery network. Each node represents an address where deliveries need to be made. The edges show the possible routes and distances between these deliveries.

Diagram of a graph with nodes A to H connected by lines. Lines are labelled with numbers: 3, 7, and 11, indicating weights. Nodes form a network.

Give one reason why the graph is a visualisation of the problem.

Did this page help you?

131 mark

A business uses an array with the identifier wNames to store workers’ names. A variable with the identifier top is used to store the index of the last element to be added to the array, which is also the element which will next be removed.

A table titled "wNames" with names Kirstie, Martyn, Louise, Alex, and Anna in columns 0-4; columns 5 and 6 are empty. Below is "top" with number 4.

State the name of the type of data structure described above.

Did this page help you?

14a1 mark
Tree diagram with nodes labelled A to J. Node A is the root, branching to B, C, and E. Further nodes are connected as shown, forming a hierarchy.

Fig. 1

State why the tree shown in Fig. 1 is not an example of a binary search tree.

14b1 mark

State what type of pointers are used to store nodes I, F, J and H so they do not point to any other nodes.

Did this page help you?

15a2 marks

Barney is writing a program to store data in a linked list. He is writing the initial program for a maximum of 10 data items.

Each node in the linked list has a data value and a pointer (to the next item).

A null pointer is stored with the value –1.

Fig. 3 shows the current contents of the linked list including the head and free list pointer values.

Diagram displaying a table with columns for index, data, and pointer, showing linked list structure. Head pointer is 0; free list pointer is 4.

Fig.3

Describe the purpose of freeListPointer

15b1 mark

State the purpose of headPointer.

Did this page help you?

13 marks

Sundip writes an algorithm to carry out addition and subtraction. The algorithm will use an initially empty stack with the identifier numbers and will take input from the user.

The action the algorithm takes depends on the value input by the user. These actions are listed in Fig. 2.

Table showing actions for input values. 'A': Add and push result. 'S': Subtract and push result. 'E': Output and end. Other: Push input to stack.

A stack is one data structure that is available for Sundip to use. She could also use a queue, list, linked list, array or tuple.

Describe how the second item in a linked list would be accessed using pointer values.

Did this page help you?

23 marks

A computer uses a stack data structure, implemented using an array, to store numbers entered by the user.

The array is zero based and has 100 locations.

The program is amended to include the use of several queue data structures

Describe how an array can be used to implement a queue data structure.

Did this page help you?

34 marks

A business uses an array with the identifier wNames to store workers’ names. A variable with the identifier top is used to store the index of the last element to be added to the array, which is also the element which will next be removed.

wNames

0

1

2

3

4

5

6

Kirstie

Martyn

Louise

Alex

Anna

top

4

The same workers’ names are stored in a binary search tree which is ordered alphabetically

Kirstie is set as the root node, with Martyn, Louise, Alex and Anna added one by one.

box enclose Kirstie

Complete the tree diagram above to show where Martyn, Louise, Alex and Anna would be added to this binary search tree.

Did this page help you?

45 marks

A printer buffer is a storage area that holds the data, known as jobs, that are to be printed by a printer.

A simulation of the printer buffer uses a queue data structure to store jobs that are waiting to be printed. The queue is not circular.

The printer buffer is represented as a zero-indexed 1D array with the identifier buffer.

Fig. 2 shows the current contents of the queue buffer and its pointers.

Queue diagram showing job processing: queueHead at 0, queueTail at 3. Job names: job-124 to job-127 in positions 0 to 3.

The array, buffer and pointer values are declared with global scope.

The function dequeue returns null if the array is empty, and the contents of the next element if not empty. The queue is not circular.

Write an algorithm, using pseudocode or program code, for the function dequeue().

Did this page help you?

55 marks

The function dequeue outputs and removes the next data item in the queue.

The procedure enqueue adds the job passed as a parameter to the queue.

Show the final contents of the queue and pointer values after the following instructions have been run on the queue buffer shown in Fig. 2.

dequeue()
dequeue()
enqueue(job-128)
dequeue()
enqueue(job-129)

Diagram showing a queue with boxes for queueHead and queueTail, and a table with seven rows numbered 0 to 6 on the side.

Fig.2

Did this page help you?

6a4 marks

A tree is one example of a data structure.

The following data is entered into a binary search tree.

22 13 5 36 55 14 8

Draw the binary search tree when the given data is entered in the order given

6b4 marks

Describe how a binary search tree can be searched for a value.

6c1 mark

Explain how backtracking is used in depth-first (post-order) traversals.

Did this page help you?

74 marks

A program stores data in a linked list.

The current contents of the linked list are shown in Fig. 3, along with the linked list pointers.

A table displays locations with data ("blue", "red", etc.) and pointers. Head pointer is 1, free list pointer is 4. Some pointers lead to NULL.

A new item needs to be added to the linked list.

Describe how a new item is added to a linked list.

Did this page help you?

82 marks

A card game uses a set of 52 standard playing cards. There are four suits; hearts, diamonds, clubs and spades. Each suit has a card with a number from; 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13.

The card game randomly gives 2 players 7 cards each. The unallocated cards become known as the deck.

The players then take it in turns to turn over a card. A valid move is a card of the same suit or the same number as the last card played.

The winner is the first player to play all of their cards.

The cards are held in the 2D array cards. The first index stores the card number and the second index stores the suit, both as strings.

Write a pseudocode statement or program code to declare the array cards.

Did this page help you?

92 marks

A computer uses a stack data structure, implemented using an array, to store numbers entered by the user.

The array is zero based and has 100 locations.

Fig. 8 shows the current contents of the stack and the first 9 locations of the array

Diagram showing an array with indices 0-8. Data values include 10, 5, 6, 23, and 1 at indices 0, 1, 2, 3, and 4. Pointer value is 5.

The function pop() removes an item from the stack.

The function push() adds an item to the stack that is passed in as a parameter.

Show the contents of the stack and pointer from Fig. 8 after the following subroutines calls have run.

pop()
pop()
push(3)
push(6)
push(7)

Diagram of an indexed array with indices 0-8 and a pointer value box, showing a structure for storing and accessing data.

Did this page help you?

104 marks

A business uses an array with the identifier wNames to store workers’ names. A variable with the identifier top is used to store the index of the last element to be added to the array, which is also the element which will next be removed.

Table showing names Kirstie, Martyn, Louise, Alex, and Anna with indices 0 to 4 under 'wNames'. Below, 'top' displays the number 4.

Using pseudocode, write an algorithm that allows the user to enter a name which is then pushed onto the data structure above, checking first that the data structure is not full.

Did this page help you?

11a3 marks

A business uses an array with the identifier wNames to store workers’ names. A variable with the identifier top is used to store the index of the last element to be added to the array, which is also the element which will next be removed.

Table showing names Kirstie, Martyn, Louise, Alex, and Anna with indices 0 to 4 under 'wNames'. Below, 'top' displays the number 4.

The same workers’ names are stored in a binary search tree which is ordered alphabetically.

Kirstie is set as the root node, with Martyn, Louise, Alex and Anna added one by one.

Family tree diagram showing Kirstie at the top, branching to Alex and Martyn. Alex connects to Anna, and Martyn connects to Louise.

Describe the process of using the binary search tree above to search for the name “Zoe”.

11b2 marks

Compare the efficiency of a binary search tree to a linked list when searching for data.

11c2 marks

Compare the efficiency of a binary search tree to a hash table when searching for data.

Did this page help you?

121 mark

Kira wants the program to traverse the tree to evaluate the range of possible moves. She is considering using a breadth-first traversal or a depth-first (post-order) traversal.

Show how a breadth-first traversal would traverse the tree shown in Fig. 1

Hierarchical tree diagram with node A at the top, branching to B, C, E; C branches to F, G; E to H; B to D; D to I; G to J.

Fig 1

Did this page help you?

13a3 marks
Hierarchical tree diagram with node A at the top, branching to B, C, E; C branches to F, G; E to H; B to D; D to I; G to J.

Fig . 1

Kira wants to make some changes to the data that is stored in the tree structure shown in Fig. 1.

The move represented by node ‘E’ needs to be deleted.

Describe the steps an algorithm will follow to delete node ‘E’ from the tree.

13b3 marks

The move represented by the node ‘K’ needs to be added. Node ‘K’ needs to be joined to node ‘G.’

Describe the steps the algorithm will follow to add node ‘K’ to the right of node ‘G’.

Did this page help you?

144 marks

Kira is creating a computer game where the user can play against the computer.

In each turn, each character can make one move from a selection of possible moves.

Kira uses a tree data structure to identify the range of possible moves the computer can make from starting position A. Each connection is a move, with each node representing the result of the move.

Kira could have used a graph data structure to represent the moves in her game.

Give two similarities and two differences between a tree and a graph data structure.

Did this page help you?

155 marks

Hugh has written a recursive function called thisFunction() using pseudocode.

01 function thisFunction(theArray, num1, num2, num3)
02   result = num1 + ((num2 - num1) DIV 2)
03   if num2 < num1 then
04     return -1
05   else
06     if theArray[result] < num3 then
07       return thisFunction(theArray, result + 1, num2, num3)
08     elseif theArray[result] > num3 then
09       return thisFunction(theArray, num1, result - 1, num3)
10     else
11       return result
12     endif
13   endif
14 endfunction

The function DIV calculates integer division, e.g. 5 DIV 3 = 1

theArray has the following data:

Index:

0

1

2

3

4

5

6

7

Data:

5

10

15

20

25

30

35

40

Trace the algorithm, and give the final return value, when it is called with the following statement:

thisFunction(theArray, 0, 7, 35)

You may choose to use the table below to give your answer.

Did this page help you?

166 marks

A printer buffer is a storage area that holds the data, known as jobs, that are to be printed by a printer.

A simulation of the printer buffer uses a queue data structure to store jobs that are waiting to be printed. The queue is not circular.

The printer buffer is represented as a zero-indexed 1D array with the identifier buffer.

Fig. 2 shows the current contents of the queue buffer and its pointers.

Diagram showing a queue with head at index 0, tail at index 3. Queue contains jobs 124 to 127. Unoccupied positions are indices 4 to 6.

The function enqueue returns -1 if there is no space at the end of the queue to add data, and returns 1 if the parameter was added to buffer. The array buffer contains a maximum of 100 elements.

Write an algorithm, using pseudocode or program code, for the function enqueue().

Did this page help you?

174 marks

Barney is writing a program to store data in a linked list. He is writing the initial program for a maximum of 10 data items.

Each node in the linked list has a data value and a pointer (to the next item).

A null pointer is stored with the value –1.

Fig. 3 shows the current contents of the linked list including the head and free list pointer values.

Diagram displaying a table with columns for index, data, and pointer, showing linked list structure. Head pointer is 0; free list pointer is 4.

Fig.3

Show the contents of the linked list from Fig. 3 and the pointer values when the node with data 6.9 is deleted.

Diagram of a pointer-based data structure with a table. Columns: index, data, pointer. Rows 0-9. Two text fields: headPointer and freeListPointer.

Did this page help you?

186 marks

Barney is writing a program to store data in a linked list. He is writing the initial program for a maximum of 10 data items.

Each node in the linked list has a data value and a pointer (to the next item).

A null pointer is stored with the value –1.

Fig. 3 shows the current contents of the linked list including the head and free list pointer values.

Diagram displaying a table with columns for index, data, and pointer, showing linked list structure. Head pointer is 0; free list pointer is 4.

Fig.3

The function findNodePath() takes the data item to find in the linked list as a parameter and follows the pointers to find the required node.

The function returns the array indexes of all the nodes it visits and joins this to a suitable message stating whether the data was found or not found and then returns this as one string.

Describe how the function findNodePath() will search for the data item and return the required message.

Did this page help you?

13 marks

A printer buffer is a storage area that holds the data, known as jobs, that are to be printed by a printer.

A simulation of the printer buffer uses a queue data structure to store jobs that are waiting to be printed. The queue is not circular.

The printer buffer is represented as a zero-indexed 1D array with the identifier buffer.

Fig. 2 shows the current contents of the queue buffer and its pointers.

Queue diagram showing job processing: queueHead at 0, queueTail at 3. Job names: job-124 to job-127 in positions 0 to 3.

Some print jobs can have different priorities. The higher the priority the sooner the job needs to be printed.

Describe how the program could be changed to deal with different priorities.

Did this page help you?

28 marks

A printer buffer is a storage area that holds the data, known as jobs, that are to be printed by a printer.

A simulation of the printer buffer uses a queue data structure to store jobs that are waiting to be printed. The queue is not circular.

The printer buffer is represented as a zero-indexed 1D array with the identifier buffer.

Fig. 2 shows the current contents of the queue buffer and its pointers.

Queue diagram showing job processing: queueHead at 0, queueTail at 3. Job names: job-124 to job-127 in positions 0 to 3.

Some print jobs can have different priorities. The higher the priority the sooner the job needs to be printed.

The function dequeue returns null if the array is empty, and the contents of the next element if not empty. The queue is not circular.

The function enqueue returns -1 if there is no space at the end of the queue to add data, and returns 1 if the parameter was added to buffer. The array buffer contains a maximum of 100 elements.

The array, buffer and pointer values are declared with global scope

Write, using pseudocode or program code, an algorithm for the main program of the simulation. It should:

  • In the main program of the simulation the user is asked whether they want to add an item to the queue or remove an item.

  • If they choose to add an item they have to input the job name, and the function enqueue is called.

  • If they choose to remove an item, the function dequeue is called and the job name is output.

  • Appropriate messages are output if either action cannot be run because the queue is either empty or full.

Did this page help you?

33 marks

The procedure printLinkedList() follows the pointers to print all of the elements in the linked list.

01 procedure printLinkedList(headPointer) 
02   tempPointer = headPointer - 1 
03   dataToPrint = ″″ 
04   if tempPointer == -1 then 
05     print(″List is full″) 
06   else 
07     while linkedList[pointer].getPointer() != -1 
08       dataToPrint = dataToPrint + ″ ″ + linkedList[tempPointer,0] 
09       linkedList[tempPointer].getPointer() = tempPointer 
10     endwhile 
11   print(dataToPrint + ″ ″ + linkedList[tempPointer].getData() 
12   endif 
13 endprocedure

The procedure has a number of errors.

Identify three lines that contain an error and write the corrected line.

Did this page help you?

45 marks

Sundip writes an algorithm to carry out addition and subtraction. The algorithm will use an initially empty stack with the identifier numbers and will take input from the user.

The action the algorithm takes depends on the value input by the user. These actions are listed in Fig. 2.

Table with value inputs and actions: A adds, S subtracts values in stack; E outputs and ends program; others push input to stack.

Complete the pseudocode here to implement Sundip’s algorithm.

do
  value = input("Enter a value")
  if ________________________ then
    num = numbers.pop()
    print(num)
  elseif value == "A" or __________________ then
    numone = numbers.pop()
    numtwo = numbers.pop()
    if value == "A" then
      numbers.push______________________
    elseif value == "S" then
      numbers.push(numtwo - numone)
    endif
  else
    numbers.push(____________)
  endif
until value == __________________________

Did this page help you?

53 marks

The function dequeue outputs and removes the next data item in the queue.

The procedure enqueue adds the job passed as a parameter to the queue.

The queue is changed to make it a circular queue.

Describe how the functions enqueue and dequeue will need to be changed to allow buffer to work as a circular queue.

Diagram of a queue with two labelled boxes: queueHead and queueTail, and a vertical 7-slot array numbered 0 to 6.

Did this page help you?