Data Types and Structures
138 questions· page 1 of 14
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.
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.
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
....................................................................................................................................................
An algorithm will:
• input 100 integer values, one value at a time
• store the first value input into the first location of the array Number
• store the next input value in the next unused location of the array Number
• output the contents of Number array in the opposite sequence to that in which the values were input.
Complete the program flowchart to represent the algorithm.
Variable declarations are not required.
Complete the trace table below by dry running the procedure Place() when it is called by the statement:
CALL Place(1043, 2, 8)
| Value | Start | Unused | New | Last | Current |
|---|---|---|---|---|---|
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).
| Data | Pointer | ||
|---|---|---|---|
| 1 | 1018 | 1 | |
| 2 | 1007 | 2 | |
| 3 | 1010 | 3 | |
| 4 | 1056 | 4 | |
| 5 | 1092 | 5 | |
| 6 | 1062 | 6 | |
| 7 | 1034 | 7 | |
| 8 | 8 | ||
| 9 | 9 | ||
| 10 | 10 |
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()
A customer can claim a free coffee for every 11 loyalty points.
The programmer has defined a second program module:
| Module | Description |
|---|---|
PointsReport() | • output the customer ID for each customer who has 11 or more loyalty points • output the average loyalty points for all customers in the Loyalty array along with an appropriate message |
Write efficient pseudocode for module PointsReport()
Assume the array contains the data for at least one customer.
Explain how a 1D array could be used to store both the loyalty points and the amended customer ID.
Complete the answer column in the following table:
| Answer | |
|---|---|
| the memory location of the value that has been on the stack for the longest time | |
the number of consecutive push operations that will result in the TopOfStack variable containing 409 |
The diagram shows the current state of the stack.
The following sequence of operations are performed:
PUSH 'T'
POP
POP
PUSH 'Z'
PUSH 'X'
POP
PUSH 'Y'
Complete the following diagram to show the state of the stack after the operations have been performed.
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.
| Index | Data | Pointer |
|---|---|---|
| 0 | "Neptune" | |
| 1 | "Jupiter" | |
| 2 | "Saturn" | |
| 3 | "Earth" | |
| 4 | "Mercury" | |
| 5 | "Uranus" |
The variable StartPointer contains the index of the first item in the linked list.
State the value of the variable StartPointer
.....................................................................................................................................
A third program is also being created to manage a queue.
Describe two features of a queue.
Feature one ..............................................................................................................................
...................................................................................................................................................
Feature two ...............................................................................................................................
...................................................................................................................................................
Data is a global 1D array containing 30 elements of type STRING
An algorithm will output:
- all non-blank elements (elements that do not contain an empty string)
- the final total of the number of elements output.
Complete the program flowchart to represent the algorithm:
A 1D array Rental containing 500 elements is used to store the data for all rental records.
Write pseudocode to declare the Rental array.
Complete the pseudocode for Store()
All variables used in the algorithm must be declared.
PROCEDURE Store()
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
ENDPROCEDURE
A second module is defined:
| Module | Description |
|---|---|
ReturnBook() | • called with two parameters of type STRING representing a StudentID and a BookID • searches the array for the relevant loan record • when found, sets OnLoan to FALSE and returns TRUE • if a loan record is not found, or the book has already been returned, then returns FALSE |
Write efficient pseudocode for the module ReturnBook()
Assume that each student is only allowed to borrow each book only once. That means that there will be no more than one loan record for a given combination of student and book.
It is decided to introduce a system of fines for books that have been borrowed for too long.
Two new requirements are defined:
- Each loan has a maximum length, represented as a number of days.
- Each book in the library will be assigned one of three categories. Each category has a different maximum loan length.
Record structure and program design changes are needed to meet these two requirements.
Outline the changes that are necessary to meet the two requirements.
Data is a global 1D array containing 20 elements of type REAL
An algorithm will:
- input a sequence of real values, one at a time
- assign each value to consecutive array elements, starting from index 1
- end when the value 99.9 is input, or all 20 elements have been assigned (the value 99.9 must not be stored in the array).
Complete the program flowchart to represent the algorithm: