Consider supporting us on Patreon. Help us keep revisedeck free.
10. Data Types and Structures
A section of Computer Science, 9618
Listing 10 of 14 questions
A binary search or a linear search can be used to look for a specific value in an array. Complete this pseudocode algorithm for a linear search. DECLARE MyList : ARRAY[0:9] OF INTEGER DECLARE MaxIndex : INTEGER DECLARE Index : INTEGER DECLARE Found : BOOLEAN DECLARE ValueToFind : INPUT ValueToFind Found ← FALSE Index ← 0 MaxIndex ← REPEAT IF MyList = ValueToFind THEN Found ← TRUE ENDIF Index ← UNTIL Found OR Index > MaxIndex IF Found THEN OUTPUT "Value found at position ", Index ELSE OUTPUT ENDIF State the necessary condition for a binary search. Describe how to perform a binary search. Explain how the performance of a binary search varies according to the number of values in the array. Compare the performance of the algorithms for a binary search and a linear search using Big O notation for order of time complexity.
9618_s22_qp_32
THEORY
2022
Paper 3, Variant 2
View
Pseudocode is to be written to implement a queue Abstract Data Type (ADT) with items of the string data type. This will be implemented using the information in the table. Identifier Data type Description FrontPointer INTEGER points to the start of the queue RearPointer INTEGER points to the end of the queue Length INTEGER the current size of the queue Queue STRING 1D array to implement the queue A constant, with identifier MaxSize, limits the size of the queue to 60 items. Write the pseudocode to declare MaxSize, FrontPointer, RearPointer, Length and Queue. Complete the following pseudocode for the function Dequeue to remove the front item from the queue. FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING > 0 THEN Item ← IF Length = 0 THEN CALL Initialise // reset the pointers ELSE IF FrontPointer > MaxSize THEN ← 1 ENDIF ENDIF ELSE OUTPUT "The print queue was empty – error!" Item ← "" ENDIF RETURN Item ENDFUNCTION Explain how a new element can be added to the queue if it is implemented using two stacks.
9618_s23_qp_31
THEORY
2023
Paper 3, Variant 1
View
The pseudocode shown represents a queue Abstract Data Type (ADT) with procedures for initialisation and to add new items. It is incomplete. CONSTANT MaxLength = 50 DECLARE FrontPointer : INTEGER DECLARE RearPointer : INTEGER DECLARE Length : INTEGER DECLARE Queue : ARRAY[0 : MaxLength – 1] OF STRING // initialisation of queue PROCEDURE Initialise FrontPointer ‑1 ENDPROCEDURE // adding a new item to the queue PROCEDURE Enqueue(NewItem : STRING) IF THEN RearPointer IF RearPointer > MaxLength – 1 THEN RearPointer ENDIF Length Length + 1 ENDIF ENDPROCEDURE Study the pseudocode and insert the identifiers to complete this table. Identifier Data type Description STRING An array to store the contents of the queue. INTEGER Points to the last item of the queue. INTEGER Indicates the number of items in the queue. INTEGER Points to the first item of the queue. Complete the given pseudocode. Explain the reasons why a queue ADT works better than a stack ADT in organising print jobs.
9618_s23_qp_32
THEORY
2023
Paper 3, Variant 2
View
Pseudocode is to be written to implement a queue Abstract Data Type (ADT) with items of the string data type. This will be implemented using the information in the table. Identifier Data type Description FrontPointer INTEGER points to the start of the queue RearPointer INTEGER points to the end of the queue Length INTEGER the current size of the queue Queue STRING 1D array to implement the queue A constant, with identifier MaxSize, limits the size of the queue to 60 items. Write the pseudocode to declare MaxSize, FrontPointer, RearPointer, Length and Queue. Complete the following pseudocode for the function Dequeue to remove the front item from the queue. FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING > 0 THEN Item ← IF Length = 0 THEN CALL Initialise // reset the pointers ELSE IF FrontPointer > MaxSize THEN ← 1 ENDIF ENDIF ELSE OUTPUT "The print queue was empty – error!" Item ← "" ENDIF RETURN Item ENDFUNCTION Explain how a new element can be added to the queue if it is implemented using two stacks.
9618_s23_qp_33
THEORY
2023
Paper 3, Variant 3
View
Questions Discovered
14