COMPUTER SCIENCE 9618
PSEUDO-CODE - ABSTRACT DATA TYPES [ ADT’s ]
9618/21/M/J/25/Q5 < ADT’s >
Q5) Stacks and queues are both abstract data types.
[
A stack uses a top-of-stack pointer to indicate the location of the last item
added to the stack.
A queue uses two pointers:
• a front pointer to indicate the location of the next item to be removed from the queue
• a rear pointer to indicate the location of the next item to be added to the queue.
A queue can be used to reverse the items stored on a stack.
For example, if a stack contains six items:
Initial state of the
stack: 
Final state of the stack
when the items have been reversed: 
Describe how the queue could be used to reverse the items that are currently stored on the stack. [7]
Your description must include how the pointers are used in both the stack and queue.
Assume:
• The stack initially contains an unknown number of items.
• The queue can store all the items currently stored on the stack.
• The queue is initially empty.
9618/22/M/J/25/Q6(a.i) < ADT’s >
Q6) Two arrays Data and Pointer are accessed by the procedure Place()
Data and Pointer are both global arrays of type INTEGER
The contents of these two arrays are shown:
(a) (i) Complete the trace table below by dry running the procedure Place() when it is called by the statement:
9618/22/M/J/25/Q6(a.ii) < ADT’s >
(ii) Complete the diagram showing the contents of the global arrays Data and Pointer after the procedure Place() has run to completion when called as shown in part (a)(i). [3]
9618/22/M/J/25/Q6(b) < ADT’s >
(b) The operation carried out by procedure Place() together with the arrays form part of the implementation of an Abstract Data Type (ADT).
Identify the ADT and state the operation carried out by procedure Place() [2]
9618/23/M/J/25/Q2(a.i) < ADT’s >
Q2) A programmer uses a number of Abstract Data Types (ADT) in the programs that she is developing.
(a) A stack using memory locations 400 to 409 is used in one program. The diagram represents the current state of the stack.
A variable TopOfStack pointer indicates the last value added to the stack.
(i) Complete the answer column in the following table:
MARK SCHEME:
9618/23/M/J/25/Q2(a.ii) < ADT’s >
(ii) The diagram shows the current state of the stack.
The following sequence of operations are performed:
Complete the following diagram to show the state of the stack after the operations have been performed.
MARK SCHEME:
9618/23/M/J/25/Q2(b.i) < ADT’s >
(b) In a different program, the programmer decides to implement a linked list using an array of records.
(i) The array is represented in the diagram.
A pointer value of –1 indicates the end of the linked list.
Complete the pointer field to produce a linked list that is in alphabetical order. [3]
Mark Scheme:
9618/23/M/J/25/Q2(b.ii) < ADT’s >
(ii) The variable StartPointer contains the index of the first item in the linked list.
State the value of the variable StartPointer [1]
MARK SCHEME: 3
9618/23/M/J/25/Q2(c) < ADT’s >
(c) A third program is also being created to manage a queue.
Describe two features of a queue. [2]
9618/21/M/J/24/Q3(a) < ADT’s >
Q3) The diagram shows an Abstract Data Type (ADT) representation of a linked list after data items have been added.
• PS is the start pointer.
• PF is the free list pointer.
• Labels Df, Dc, Db and Dy represent the data items of nodes in the list.
• Labels Fg, Fh, Fm and Fw represent the data items of nodes in the free list.
• The symbol Ø represents a null pointer.
(a) Describe the linked list immediately after initialisation, before any data items are added. [3]
9618/21/M/J/24/Q3(b) < ADT’s >
(b) A program will be written to include a linked list to store alphanumeric user IDs.
The design uses two variables and two 1D arrays to implement the linked list.
Each array element contains data of a single data type and not a record.
The statements below describe the design.
Complete the statements. [5]
MARK SCHEME:
9618/22/O/N/24/Q3(a.i) < ADT’s>
Q3) A program uses a stack to hold up to 60 numeric values.
The stack is implemented using two integer variables and a 1D array.
The array is declared in pseudocode as shown:
DECLARE ThisStack : ARRAY[1:60] OF REAL The stack operates as follows:
• Global variable SP acts as a stack pointer that points to the next available stack location. The value of SP represents an array index.
• Global variable OnStack represents the number of values currently on the stack.
• The stack grows upwards from array element index 1.
(a) (i) Give the initial values that should be assigned to the two variables. [1]
9618/22/O/N/24/Q3(a.ii) < ADT’s>
(ii) Explain why it is not necessary to initialise the array elements before the stack is used. [2]
9618/22/O/N/24/Q3(b) < ADT’s>
(b) A function to add a value to ThisStack is expressed in pseudocode as shown. The function will return a value to indicate whether the operation was successful or not.
Complete the pseudocode by filling in the gaps.
9618/23/O/N/24/Q3(a.i) < ADT’s>
Q3) The implementation of a linked list uses an integer variable and a 1D array List of type Node.
Record type Node is declared in pseudocode as follows:
The array List is declared in pseudocode as follows:
DECLARE List : ARRAY[1:200] OF Node
The linked list will operate as follows:
• Integer variable HeadPointer will store the array index for the first node in the linked list.
• The Pointer field of a node contains the index value of the next array element (the next node) in the linked list.
• The value 0 is used as a null pointer
(a) (i) State why the value 0 has been selected as the null pointer. [1]
9618/23/O/N/24/Q3(a.ii) < ADT’s>
(ii) Give the range of valid values that could be assigned to variable HeadPointer. [1]
9618/23/O/N/24/Q3(b) < ADT’s>
(a) The array List will be initialised so that each node points to the following node.
The last node will contain a null pointer.
Complete the program flowchart to represent the algorithm for this operation. [4]
9618/23/O/N/24/Q3(c) < ADT’s>
(c) An algorithm outputs the Data field from all nodes in the array List.
The order the Data is output should be the same order it is stored in the linked list.
Describe the algorithm in four steps.
Do not use pseudocode statements in your answer. [4]
9618/22/M/J/23/Q3(a.i) < ADT’s>
Q3) A program stores data in a text file. When data is read from the file, it is placed in a queue.
(a) The diagram below represents an Abstract Data Type (ADT) implementation of the queue. Each data item is stored in a separate location in the data structure. During initial design, the queue is limited to holding a maximum of 10 data items.
The operation of this queue may be summarised as follows:
• The Front of Queue Pointer points to the next data item to be removed.
• The End of Queue Pointer points to the last data item added.
• The queue is circular so that locations can be reused.
(i) Describe how the data items Orange and Yellow are added to the queue shown in the diagram. [4]
9618/22/M/J/23/Q3(a.ii) < ADT’s>
(ii) The following diagram shows the state of the queue after several operations have been performed. All queue locations have been used at least once.
State the number of data items in the queue. [1]
MARK SCHEME: 7
9618/22/M/J/23/Q3(b) < ADT’s>
(a) The design of the queue is completed and the number of locations is increased.
A function AddToQueue() has been written. It takes a string as a parameter and adds this to the queue. The function will return TRUE if the string was added successfully.
A procedure FileToQueue() will add each line from the file to the queue. This procedure will end when all lines have been added or when the queue is full.
Describe the algorithm for procedure FileToQueue(). Do not use pseudocode in your answer. [5]
9618/23/M/J/23/Q3(a.i) < ADT’s>
Q3) A program processes data using a stack. The data is copied to a text file before the program ends.
(a) The following diagram shows the current state of the stack. The operation of this stack may be summarised as follows:
• The TopOfStack pointer points to the last item added to the stack.
• The BottomOfStack pointer points to the first item on the stack.
• The stack grows upwards when items are added.
(i) An error will be generated if an attempt is made to POP a value when the stack is empty.
State the maximum number of consecutive POP operations that could be performed on the stack shown above before an error is generated. [1]
MARK SCHEME : 6
9618/23/M/J/23/Q3(a.ii) < ADT’s>
(ii) The following operations are performed:
1. POP and store value in variable Data1
2. POP and store value in variable Data2
3. PUSH value AAA
4. PUSH value BBB
5. POP and discard value
6. POP and store value in variable Data2
Complete the diagram to show the state of the stack and the variables after the given operations have been performed. [4]
MARK SCHEME:
9618/23/M/J/23/Q3(b.i) < ADT’s>
(b) The data is copied to a text file before the program ends.
(i) State an advantage of writing the data from the stack to a text file before the program ends. [1]
9618/23/M/J/23/Q3(b.ii) < ADT’s>
(ii) A module SaveStack() will write the data from the stack to a text file.
Express an algorithm for
SaveStack() as five steps that could be used to produce pseudocode.
Write the five steps. [5]
MARK SCHEME:
9618/21/O/N/23/Q3(a) < ADT’s>
Q3) The diagram represents an Abstract Data Type (ADT).
The operation of this stack may be summarised as follows:
• The TopOfStack pointer points to the last item added to the stack.
• The BottomOfStack pointer points to the first item on the stack.
(a) The stack is implemented using two variables and a 1D array of 8 elements as shown.
The variables are used to reference individual elements of the array, in such a way that:
• the array is filled from the lowest indexed element towards the highest
• all the elements of the array are available for the stack.
Complete the diagram to represent the state of the stack as shown above. [3]
9618/21/O/N/23/Q3(b) < ADT’s>
(b) A function Push() will add a value onto the stack by manipulating the array and variables in part (a).
Before adding a value onto the stack, the algorithm will check that space is available.
If the value is added to the stack, the function will return TRUE, otherwise it will return FALSE.
The algorithm is expressed in five steps.
Complete the steps. [5]
9618/22/O/N/23/Q3(a) < ADT’s>
Q3) The diagram represents a linked list Abstract Data Type (ADT).
• Ptr1 is the start pointer. Ptr2 is the free list pointer.
• Labels D40, D32, D11 and D100 represent the data items of nodes in the list.
• Labels F1, F2, F3 and F4 represent the data items of nodes in the free list.
• The symbol Ø represents a null pointer.
(a) The linked list is implemented using two variables and two 1D arrays as shown.
The pointer variables and the elements of the Pointer array store the indices (index numbers) of elements in the Data array
Complete the diagram to show how the linked list as shown above may be represented using the variables and arrays. [5]
MARK SCHEME:
9618/22/O/N/23/Q3(b) < ADT’s>
(b) The original linked list is to be modified. A new node D6 is inserted between nodes D32 and D11.
9618/23/O/N/23/Q3(a) < ADT’s>
Q3) The diagram represents a queue Abstract Data Type (ADT).
The organisation of this queue may be summarised as follows:
• The FrontOfQueue pointer points to the next data item to be removed.
• The EndOfQueue pointer points to the last data item added.
The queue is implemented using three variables and a 1D array of eight elements
as shown. The variable NumItems stores the number of items in the queue.
The pointer variables store indices (index numbers) of the array.
(a) Complete the diagram to represent the state of the queue as shown above. [3]
9618/23/O/N/23/Q3(b) < ADT’s>
(b) A module AddTo() will add a value to the queue by manipulating the array and variables in part (a).
Before a value can be added to the queue, it is necessary to check the queue is not full.
The algorithm to add a value to the queue is expressed in six steps.
Complete the steps: [6]
9618/21/M/J/22/Q4(a) < ADT’s>
Q4) A stack is created using a high-level language. Memory locations 200 to 207 are to be used to store the stack.
The following diagram represents the current state of the stack.
TopOfStack points to the last value added to the stack.
(a) Complete the following table by writing the answers. [2]
MARK SCHEME:
9618/21/M/J/22/Q4(b) < ADT’s>
(b) The following diagram shows the current state of the stack:
The following operations are performed:
Complete the diagram to show the state of the stack after the operations have been performed.
MARK SCHEME:
9618/21/O/N/22/Q4(a.i) < ADT’s >
Q4a) The following diagram shows an Abstract Data Type (ADT) representation of an ordered linked list. The data item stored in each node is a single character. The data will be accessed in alphabetical order.
The symbol Ø represents a null pointer.
(i) Nodes with data 'A' and 'K' are added to the linked list. Nodes with data 'J' and 'L' are deleted.
After the changes, the data
items still need to be accessed in alphabetical order.
Complete the diagram to show the new state of the linked list. [4]
MARK SCHEME:
9618/21/O/N/22/Q4(a.ii) < ADT’s >
(ii) The original data could have been stored in a 1D array in which each element stores a character. For example:
Explain the advantages of making the changes described in part (a)(i) when the data is stored in the linked list instead of an array. [2]
9618/21/O/N/22/Q4(a.iii) < ADT’s >
(iii) Explain the disadvantages of making the changes described in part (a)(i) when the data is stored in the linked list instead of an array. [2]
9618/21/O/N/22/Q4(b) < ADT’s >
(b) A program will store data using a linked list like the one shown in part (a).
Explain how the linked list can be implemented. [4]
MARK SCHEME:
9618/22/O/N/22/Q3(a) < ADT’s >
(a) A stack is an example of
an Abstract Data Type (ADT).
Identify one other example of an ADT and describe its main features. [3]
MARK SCHEME:
9618/22/O/N/22/Q3(b) < ADT’s >
(b) Explain how the stack can be implemented using an array. [5]
MARK SCHEME:
9618/22/O/N/22/Q3(c) < ADT’s >
(b) A second stack is used in the program. The diagram below shows the
initial state of this stack. Value X is at the top of the stack and was the
last item added.
Upper-case letters are used to represent different data values. Stack
operations are performed in three groups as follows:
Complete the diagram to show the state of the stack after each group of operations has been performed.
Include the current stack pointer (SP) after each group.
MARK SCHEME:
9618/23/O/N/22/Q4(b.i) < ADT’s >
(b) A programmer decides to implement a queue Abstract Data Type (ADT) in order to store characters received from the keyboard. The queue will need to store at least 10 characters and will be implemented using an array.
(i) Describe two operations that are typically required when implementing a queue.
State the check that must be carried out before each operation can be completed. [4]
9618/23/O/N/22/Q4(b.ii) < ADT’s >
(ii) Describe the declaration and initialisation of the variables and data structures used to implement the queue. []
9618/21/M/J/21/Q6(a) < ADT’s >
Q6) The following diagram represents an Abstract Data Type (ADT) for a linked list.
The free list is as follows:
(a) Explain how a node containing data value B is added to the list in alphabetic sequence. [4]
9618/21/M/J/21/Q6(b) < ADT’s >
(b) Describe how the linked list in part (a) may be implemented using variables and arrays. [2]
9618/22/M/J/21/Q3(a) < ADT’s >
Q3) The following diagram represents an Abstract Data Type (ADT).
(a) Identify this type of ADT. [1]
MARK SCHEME : Linked List
9618/22/M/J/21/Q3(b) < ADT’s >
(b) Give the technical term for the item labelled A in the diagram. [1]
MARK SCHEME: Start Pointer
9618/22/M/J/21/Q3(c) < ADT’s >
(c) Give the technical term for the item labelled B in the diagram.
Explain the meaning of the value given to this item. [2]
MARK SCHEME:
9618/22/M/J/21/Q3(d) < ADT’s >
(d) Complete the diagram to show the ADT after the data has been sorted in alphabetical order. [2]
MARK SCHEME:
9618/21/O/N/21/Q3(a.i) < ADT’s >
Q3a) The diagram below represents a queue Abstract Data Type (ADT) that can hold a maximum of eight items. The operation of this queue may be summarised as follows:
• The front of queue pointer points to the next item to be removed.
• The end of queue pointer points to the last item added.
• The queue is circular so that empty storage elements can be reused.
(i) Describe how “Octopus” is added to the given queue. [2]
9618/21/O/N/21/Q3(a.ii) < ADT’s >
(ii) Describe how the next item in the given queue is removed and stored in the variable AnimalName.
9618/21/O/N/21/Q3(a.iii) < ADT’s >
(iii) Describe the state of the queue when the front of queue and the end of queue pointers have the same value. [1]
9618/21/O/N/21/Q3(b.i) < ADT’s >
(b) Some operations are carried out on the original queue given in part (a).
(i) The current state of the queue is:
Complete the diagram to show the state of the queue after the following operations: Add “Wasp”, “Bee” and “Mouse”, and then remove two data items. [3]
MARK SCHEME:
9618/21/O/N/21/Q3(b.ii) < ADT’s >
(ii) The state of the queue after other operations are carried out is shown:
Complete the following diagram to show the state of the queue after the following operations:
Remove one item, and then add “Dolphin” and “Shark”. [2]
MARK SCHEME:
9618/21/O/N/21/Q3(c) < ADT’s >
(c) The queue is implemented using a 1D array.
Describe the algorithm that should be used to modify the end of queue pointer when adding an item to the queue.
Your algorithm should detect any potential error conditions. [3]
0 Reviews