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?
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.
How did you do?
Did this page help you?
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
State the purpose of pointerValue
How did you do?
Did this page help you?
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.
State the purpose of the pointers queueHead
and queueTail
.
How did you do?
Did this page help you?
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 one difference between a stack and a queue.
How did you do?
Describe one difference between an array and a list.
How did you do?
Did this page help you?
A tree is one example of a data structure.
Give two characteristics of a tree data structure
How did you do?
Describe how a leaf node is deleted from a binary search tree.
How did you do?
Identify the order that the nodes will be visited in a depth-first (post-order) traversal of this binary search tree.
How did you do?
Did this page help you?
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.
Fig. 3
State the purpose of headPointer
and freeListPointer
in the linked list shown in Fig. 3.
How did you do?
Did this page help you?
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.
Fig. 3
State the meaning of the pointers with the value NULL in the Figure
How did you do?
Did this page help you?
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.
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.
How did you do?
Did this page help you?
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:
Fig. 2
Identify the root node in the binary tree shown in Fig.2
How did you do?
Identify two leaf nodes in the binary tree shown in Fig. 2
How did you do?
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
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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.
State one way a directed graph is different to an undirected graph.
How did you do?
State one way a graph data structure is different to a tree data structure.
How did you do?
Did this page help you?
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.
Give one reason why the graph is a visualisation of the problem.
How did you do?
Did this page help you?
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.
State the name of the type of data structure described above.
How did you do?
Did this page help you?
Fig. 1
State why the tree shown in Fig. 1 is not an example of a binary search tree.
How did you do?
State what type of pointers are used to store nodes I, F, J and H so they do not point to any other nodes.
How did you do?
Did this page help you?
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
Describe the purpose of freeListPointer
How did you do?
State the purpose of headPointer
.
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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.
Complete the tree diagram above to show where Martyn, Louise, Alex and Anna would be added to this binary search tree.
How did you do?
Did this page help you?
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()
.
How did you do?
Did this page help you?
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
How did you do?
Did this page help you?
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
How did you do?
Describe how a binary search tree can be searched for a value.
How did you do?
Explain how backtracking is used in depth-first (post-order) traversals.
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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)
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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”.
How did you do?
Compare the efficiency of a binary search tree to a linked list when searching for data.
How did you do?
Compare the efficiency of a binary search tree to a hash table when searching for data.
How did you do?
Did this page help you?
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
How did you do?
Did this page help you?
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.
How did you do?
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’.
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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()
.
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?
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 == __________________________
How did you do?
Did this page help you?
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.
How did you do?
Did this page help you?