Algorithms (Cambridge (CIE) A Level Computer Science): Exam Questions

This binary tree shows an ordered list of integers.

A linked list of nodes is used to store the data. Each node consists of a left pointer, the data and a right pointer.

−1 is used to represent a null pointer.

Complete this linked list to represent the given binary tree organisation.

A 2D array is used to store the nodes of the linked list in part (a). Complete the diagram using your answer for part (a)

The linked list in part (a) is implemented using a 1D array of records. Each record contains a left pointer, data and a right pointer.

The following pseudocode represents a function that searches for an element in the array of records LinkList. It returns the index of the record if the element is found, or it returns a null pointer if the element is not found.

Complete the pseudocode for the function.

FUNCTION SearchList(Item : INTEGER) ........................................................................

NullPtr −1

.................................................................... RootPtr

WHILE NowPtr <> NullPtr

IF LinkList[NowPtr].Data < Item THEN

NowPtr LinkList[NowPtr].RightPtr

ELSE

IF ..................................................................... THEN

NowPtr ..............................................................................

ELSE

RETURN NowPtr

ENDIF

ENDIF

ENDWHILE

RETURN NullPtr

ENDFUNCTION

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

Found ← FALSE

NotInList ← FALSE

Count ← TopOfList

WHILE Found = FALSE AND NotInList = FALSE

IF Widgets[Count] = ToFind THEN

Found ← TRUE

ENDIF

Count ← Count + 1

IF Count > EndOfList 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.

Show how the contents of the following stack will change as the RPN expression in part (a)(i) is evaluated.

Explain how a stack can be used to evaluate RPN expressions.

A stack is to be set up using the information in the table.

A constant, with identifier Capacity, limits the size of the stack to 25 items.

Write the pseudocode for the required declarations.

Complete the pseudocode function Pop() to pop an item from Stack.

// popping an item from the stack

FUNCTION Pop()...............................................................................

DECLARE Item : REAL

Item0 ........................................BasePointer THEN

Item ........................................

TopPointer ..................................................

ELSE

OUTPUT "The stack is empty – error"

ENDIF

.........................................................................

ENDFUNCTION

Compare and contrast the queue and stack Abstract Data Types (ADT).

The Reverse Polish Notation (RPN) expression:

a b * 2 / c d / *

is to be evaluated where a = 20, b = 3, c = 10 and d = 5.

Show the changing contents of the following stack as the RPN expression is evaluated.