Computational Thinking and Problem-solving
39 questions· page 1 of 4
A linked list of nodes is used to store an ordered list of integers. Each node consists of the data, a left pointer and a right pointer, for example:
The linked list will be organised as a binary tree.
is used to represent a null pointer.
Complete the binary tree, including null pointers, to show how the data will be organised after the following integers have been added:
6, 15, 41, 66
Describe what is meant by recursion.
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
.............................................................................................................................................
A binary tree is a suitable Abstract Data Type (ADT) that a designer can implement using recursive algorithms.
Identify one other ADT that a designer can implement using recursive algorithms.
.............................................................................................................................................
A linked list of nodes is used to store an ordered list of strings. Each node consists of the data, a left pointer and a right pointer.
The linked list will be organised as a binary tree.
0 is used to represent a null pointer.
Complete the binary tree, including null pointers, to show how the data will be organised after the following strings have been added:
Aa, Mm, Ss, Xx
A binary tree can be used to implement recursion.
Identify one feature of an algorithm that makes it beneficial to use recursion.
Give one example of an application that could use a recursive algorithm.
Feature .....................................................................................................................................
...................................................................................................................................................
Example ....................................................................................................................................
An array is an Abstract Data Type (ADT).
Identify two other ADTs.
1 ................................................................................................................................................
2 ................................................................................................................................................
A 1D array DataArray holds up to 1000 elements of type integer and needs to be sorted in ascending order.
Write the pseudocode for an insertion sort to sort the array into ascending order.
Use the identifiers from the table in your algorithm.
You do not need to declare any arrays or variables for this algorithm. You may assume this has already been done.
| Identifier | Data type | Description |
|---|---|---|
| Index | INTEGER | counter for outer loop |
| Position | INTEGER | counter for inner loop – insertion position |
| DataArray | INTEGER | 1D array to store up to 1000 integers |
| Value | INTEGER | value to insert |
The first line has been written for you.
FOR Index ← 2 to 1000
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
Describe two ways in which the performance of a sort routine is affected by the data to be sorted.
1 ................................................................................................................................................
...................................................................................................................................................
2 ................................................................................................................................................
...................................................................................................................................................
The recursive procedure Delete() is defined as follows:
PROCEDURE Delete(Index, Target)
IF Numbers[Index] > 0 THEN
IF Numbers[Index] >= Target THEN
Numbers[Index] ← Numbers[Index + 1]
ENDIF
Index ← Index + 1
CALL Delete(Index, Target)
ENDIF
ENDPROCEDURE
An array Numbers is used to store a sorted data set of non-zero positive integers.
Unused cells contain zero.
The contents of the array at the start of the algorithm are:
| Numbers | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |
| 2 | 3 | 7 | 11 | 15 | 17 | 19 | 23 | 0 | 0 |
Complete the trace table for the algorithm for the procedure call:
CALL Delete(1, 15)
| Numbers | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Index | Target | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |
| 2 | 3 | 7 | 11 | 15 | 17 | 19 | 23 | 0 | 0 | ||
Complete the pseudocode for the function to remove a data item from the stack.
FUNCTION Pop() ...........................................................................................................
DECLARE DataItem : STRING
DataItem ← ""
IF .................................................................................................................... THEN
DataItem ← .......................................................................................................
Top ← ..................................................................................................................
ELSE
DataItem ← "You cannot remove data; the stack is empty"
ENDIF
......................................................................................................................................
ENDFUNCTION
Write the pseudocode to output the data item removed from the stack with an appropriate message.
...........................................................................................................................................
.....................................................................................................................................
A stack is used to implement recursion.
State the three essential features of recursion.
1 ................................................................................................................................................
...................................................................................................................................................
2 ................................................................................................................................................
...................................................................................................................................................
3 ................................................................................................................................................
...................................................................................................................................................
Complete the pseudocode for the procedure to add a data item onto the stack.
PROCEDURE Push(.........................................................................................)
IF Top < Max – 1 THEN
Top ← ...............................................................................................
...................................................................................... ← NewData
ELSE
OUTPUT ...............................................................................................
ENDIF
ENDPROCEDURE
Write pseudocode to declare the variables, constant and array required to implement the stack.
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
.............................................................................................................................................
Write pseudocode for a procedure to initialise the top and bottom pointers of the stack to appropriate values.
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
.............................................................................................................................................
Describe when the use of recursion would be beneficial and give an example.
Description .......................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
..........................................................................................................................................................
Example ...........................................................................................................................................
..........................................................................................................................................................
State a condition that must be true for an array to be searchable for a binary search.
...................................................................................................................................................
.............................................................................................................................................
Complete the given pseudocode to find an item in a 1D array Names of type STRING using a binary search.
DECLARE Names : ARRAY[1:100000] OF STRING
DECLARE TopOfList : INTEGER
DECLARE EndOfList : INTEGER
DECLARE CurrentItem : INTEGER
DECLARE ToFind : STRING
DECLARE Found : BOOLEAN
DECLARE NotInList : BOOLEAN
TopOfList ← 1
EndOfList ← 100000
OUTPUT "Which name do you wish to find? "
INPUT ToFind
...................................................................................................................................................
NotInList ← FALSE
WHILE ................................................ AND ................................................
CurrentItem ← (TopOfList + EndOfList) DIV 2
IF ........................................................................................................... THEN
Found ← TRUE
ELSE
IF TopOfList >= EndOfList THEN
...........................................................................................................
ELSE
IF ToFind > Names[CurrentItem] THEN
...........................................................................................................
ELSE
EndOfList ← CurrentItem – 1
ENDIF
ENDIF
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Item found at position ", CurrentItem, " in array"
ELSE
OUTPUT "Item not in array"
ENDIF
Describe the performance of a binary search in relation to the number of data items in the array being searched. Refer to Big O notation in your answer.
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
.............................................................................................................................................
Complete the pseudocode to find an item in a 1D array Widgets of type STRING, using a linear search.
DECLARE Widgets : ARRAY[1:50000] OF STRING
DECLARE TopOfList : INTEGER
DECLARE EndOfList : INTEGER
DECLARE Count : INTEGER
DECLARE ToFind : STRING
DECLARE Found : BOOLEAN
DECLARE NotInList : BOOLEAN
TopOfList ← 1
EndOfList ← 50000
OUTPUT "Enter the name of the item you wish to find "
INPUT ToFind
.....................
NotInList ← FALSE
Count ← TopOfList
WHILE ..................... AND .....................
IF ..................... THEN
Found ← TRUE
ENDIF
Count ← Count + 1
IF ..................... THEN
NotInList ← TRUE
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Item found at position ", Count - 1, " in array"
ELSE
OUTPUT "Item not in array"
ENDIF
Compare the methods used by the linear and binary search algorithms to find an item in an array. Refer to Big O notation in your answer.