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

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.

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.

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.

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

top

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.

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

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.

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().

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)

Fig.2

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

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

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

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 new item needs to be added to the linked list.

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

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.

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

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)

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.

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.

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.

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.

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

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

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

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

Fig 1

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.

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’.

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.

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:

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.

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.

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().

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.

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.

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.

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.

Fig. 8 shows a binary search tree that contains the names of different towns in Ireland.

The binary search tree is held in a 2-dimensional array called towns with 8 rows and 3 columns.

In the 2-dimensional array towns:

• the first column contains a pointer to the left side

• the second column contains the data

• the third column contains a pointer to the right side.

Leaf nodes have the pointer null.

Complete the table showing the contents of the towns array to store the binary search tree shown in Fig. 8.

Four more towns are added to the binary search tree shown in Fig. 8 in this order

• Mallow

• Cavan

• Tuam

• Wexford

Complete this binary search tree by adding the new towns to it.

A computer game has a building containing 7 rooms. There are secret passages between each room. Fig. 3 shows the rooms and the passages between the rooms represented as a graph data structure.

State four ways that a graph data structure is different from a tree data structure.

The contents of a stack are stored in the 1-dimensional array called numbers.

topStack stores the index of the next free space in the stack.

The array is declared with space for 100 elements.

The function pop() returns the next item from the stack and updates the appropriate pointers.

Describe the steps in the function pop().

A computer game stores tasks that the player has requested. Each task has:

• an identification (ID) number e.g. Task A

• a real number to be processed e.g. 123456.789

• an integer number to represent the order the tasks should be accessed e.g. 1.

The task that needs to be processed the earliest is given the order number 1.

Two or more tasks can have the same order number. For example, two tasks can have an order number 1.

The tasks will be stored in a binary search tree before they are processed. They are stored in ascending order by their order number.

Tick (✓) one column in each row to identify whether each statement applies to a depth-first (post-order) tree traversal, a breadth-first tree traversal, or neither of these two traversals, when performed on a binary search tree.

The tasks currently stored in the binary search tree are shown here.

When a new task is inserted with the same order number as a pre-existing task, it is classed as having a higher order number.

For example, task G has the same order number as task A. Since task G was inserted after task A it is classed as a higher number.

Change the diagram to show the contents of the binary search tree after the following tasks are inserted in the order given:

• Task X with order number 12

• Task Y with order number 7

• Task Z with order number 11

A game is being written that makes use of object-oriented programming. A prototype for one part of the game is being designed that includes a character, a road and a prize to collect.

The road will have 50 spaces that a character can move along. Each space on the road will store a null value or a prize object for the user to collect. Each space is numbered sequentially from the first space (position 0) to the last space (position 49) and will not change during the game. As the player travels down the road, the position the player is on the road will be output.

The road is designed to be a 1-dimensional array with the identifier road.

Explain why an array is a suitable data structure to represent the road.

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.

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.

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.

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.

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.

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.

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 == __________________________

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.

A binary search tree is used to store student names.

Describe the steps required to delete the node “Ben” when it has two children.

In your answer, you must refer to the in-order successor and explain how pointers are updated to maintain the binary search tree property.

A stack is implemented using a static array of size 5, with topStack pointing to the next free space.

Initially, the array contains [10, 20, 30, None, None] and topStack = 3.

Trace the state of the array and the value of topStack after the following operations:
push(40), pop(), push(50), push(60), push(70)

Analyse the result of a final push(80) operation.

Recursive algorithms are often criticised for their high memory overhead compared to iterative solutions.

Explain the relationship between stacks and recursion.

In your answer, you should refer to stack frames, local variables, and explain why a base case is critical to preventing system failure.

A circular queue of size 4 uses front and rear pointers.

Initially, front = 0, rear = 2, and the array is [A, B, C, None].

Trace the pointers and array contents after the operations enqueue(D), dequeue(), dequeue(), enqueue(E).

You must use modulo arithmetic to justify the final position of the rear pointer.

A network server receives data packets of varying importance, including standard web traffic and emergency system alerts.

Evaluate why a priority queue is more suitable for this scenario than a linear queue.

In your answer, refer to latency for critical tasks and explain how items are inserted into each structure.

A programmer implements a linear queue in a static array of size 100 to handle print jobs. After several hours, the system reports a Queue Overflow error, even though there are only 5 active jobs in the queue.

Evaluate why this error occurred and justify why a circular queue using modulo arithmetic is a superior solution for this scenario.

Evaluate the impact on performance and memory usage when using a linked list instead of an array to store an ordered list of 1,000,000 records.

You must discuss random access and contiguous memory in your answer.

A linked list is stored in a 2D array.
headPointer = 1, freeListPointer = 4

Index 0: [Blue, 2]
Index 1: [Red, 0]
Index 2: [Green, NULL]
Index 3: [Empty, 5]
Index 4: [Empty, NULL]

Describe the exact steps required to delete “Blue” and add “Yellow” to the end of the list.

You must state the updated values for all relevant pointers.

A developer is choosing between linear probing and chaining (linked lists) for a hash table that is expected to store a high volume of data.

Evaluate how each method affects the time complexity of retrieval as the table approaches maximum capacity.

A company uses a hash table to store customer records using an 8-character alphanumeric ID as the key.

Explain how an address is generated from the key and justify why a one-way hash function is used