Topical Past Paers 9608

(P4)Topical 4.1 Computational thinking & Problem solving)

with Sir Majid Tahir

4.1. Computational thinking and problem-solving (Pastpapers 2015 – 2018)

4.1.1 Abstraction
4.1.2 Algorithms
4.1.3 Abstract Data Types (ADT)

9608/41/M/J/15
Q. 1 /- A queue Abstract Data Type (ADT) has these associated operations:
create queue
add item to queue
remove item from queue

The queue ADT is to be implemented as a linked list of nodes.

Each node consists of data and a pointer to the next node.

(a) The following operations are carried out:

CreateQueue AddName("Ali")
AddName("Jack")
AddName("Ben")
AddName("Ahmed")
RemoveName
AddName("Jatinder")
RemoveName

Add appropriate labels to the diagram to show the final state of the queue. Use the
space on the left as a workspace. Show your final answer in the node shapes on the
right:

www.majidtahir.com Contact: 03004003666 Email: [email protected]

1
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

(b) Using pseudocode, a record type, Node, is declared as follows:

TYPE Node
DECLARE Name : STRING
DECLARE Pointer : INTEGER
ENDTYPE

The statement

DECLARE Queue : ARRAY[1:10] OF Node

reserves space for 10 nodes in array Queue.

(i) The CreateQueue operation links all nodes and initialises the three pointers that
need to be used: HeadPointer, TailPointer and FreePointer.

Complete the diagram to show the value of all pointers after CreateQueue has been
executed.

(ii) The algorithm for adding a name to the queue is written, using pseudocode, as a
procedure with the header:

PROCEDURE AddName(NewName)

where NewName is the new name to be added to the queue.

www.majidtahir.com Contact: 03004003666 Email: [email protected]

2
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

The procedure uses the variables as shown in the identifier table.

www.majidtahir.com Contact: 03004003666 Email: [email protected]

3
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

Complete the pseudocode for the procedure RemoveName. Use the variables listed in
the identifier table.

www.majidtahir.com Contact: 03004003666 Email: [email protected]

4
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

9608/43/M/J/15
Q2/- A stack Abstract Data Type (ADT) has these associated operations:

create stack
add item to stack (push)
remove item from stack (pop)

The stack ADT is to be implemented as a linked list of nodes.

Each node consists of data and a pointer to the next node.

(a) There is one pointer: the top of stack pointer, which points to the last item added to
the stack.

Draw a diagram to show the final state of the stack after the following operations are
carried out.

Add appropriate labels to the diagram to show the final state of the stack. Use the space
on the left as a workspace. Show your final answer in the node shapes on the right:

www.majidtahir.com Contact: 03004003666 Email: [email protected]

5
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

(b) Using pseudocode, a record type, Node, is declared as follows:

(ii) The algorithm for adding a name to the stack is written, using pseudocode, as a
procedure with the header

PROCEDURE Push (NewName)

Where NewName is the new name to be added to the stack.

The procedure uses the variables as shown in the identifier table.

www.majidtahir.com Contact: 03004003666 Email: [email protected]

6
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

www.majidtahir.com Contact: 03004003666 Email: [email protected]

7
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

9608/41/M/J/16
Q.3/- A linked list abstract data type (ADT) is to be used to store and organise
surnames.

This will be implemented with a 1D array and a start pointer. Elements of the array
consist of a user-defined type. The user-defined type consists of a data value and a link
pointer.

www.majidtahir.com Contact: 03004003666 Email: [email protected]

8
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

(a) (i) Write pseudocode to declare the type LinkedList.

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

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

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

.......................................................................................................................................[3]

(ii) The 1D array is implemented with an array SurnameList of type LinkedList.

Write the pseudocode declaration statement for SurnameList.

The lower and upper bounds of the array are 1 and 5000 respectively.

.......................................................................................................................................[2]

www.majidtahir.com Contact: 03004003666 Email: [email protected]

9
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

9608/42/M/J/17
Q4/- An ordered binary tree Abstract Data Type (ADT) has these associated operations:
create tree
add new item to tree
traverse tree

The binary tree ADT is to be implemented as a linked list of nodes.

Each node consists of data, a left pointer and a right pointer.

www.majidtahir.com Contact: 03004003666 Email: [email protected]

10
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

(a) A null pointer is shown as .

Explain the meaning of the term null pointer.

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

........................................................................................................................................[1]

(b) The following diagram shows an ordered binary tree after the following data have
been added: Dublin, London, Berlin, Paris, Madrid, Copenhagen

www.majidtahir.com Contact: 03004003666 Email: [email protected]

11
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

www.majidtahir.com Contact: 03004003666 Email: [email protected]

12
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

(ii) Give an appropriate numerical value to represent the null pointer for this design.
Justify your answer.

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

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

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

.......................................................................................................................................[2]

(d) A program is to be written to implement the tree ADT. The variables and procedures
to be used are listed below:

www.majidtahir.com Contact: 03004003666 Email: [email protected]

13
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

(i) Complete the pseudocode to create an empty tree.

TYPE Node

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

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

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

ENDTYPE

DECLARE Tree : ARRAY[0 : 9] ................................................................................

DECLARE FreePointer : INTEGER

DECLARE RootPointer : INTEGER

PROCEDURE CreateTree()

DECLARE Index : INTEGER

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

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

FOR Index ← 0 TO 9 // link nodes

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

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

ENDFOR

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

ENDPROCEDURE [7]

www.majidtahir.com Contact: 03004003666 Email: [email protected]

14
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

(ii) Complete the pseudocode to add a data item to the tree.

PROCEDURE AddToTree(BYVALUE NewDataItem : STRING)

// if no free node report an error

IF FreePointer .................................................................................................

THEN
OUTPUT("No free space left")

ELSE // add new data item to first node in the free list

NewNodePointer ← FreePointer

.................................................................................................................................
// adjust free pointer
FreePointer ← .................................................................................................

// clear left pointer

Tree[NewNodePointer].LeftPointer ← ......................................................

// is tree currently empty ?

IF
...........................................................................................................................

THEN // make new node the root node

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

ELSE // find position where new node is to be added

Index ← RootPointer

CALL FindInsertionPoint(NewDataItem, Index, Direction)

IF Direction = "Left"
THEN // add new node on left

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

ELSE // add new node on right

.......................................................................................................
ENDIF
ENDIF
ENDIF
ENDPROCEDURE [8]

www.majidtahir.com Contact: 03004003666 Email: [email protected]

15
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

9608/41/M/J/1
Answers:
Q1/-

www.majidtahir.com Contact: 03004003666 Email: [email protected]

16
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

9608/43/M/J/15
Q2/-

www.majidtahir.com Contact: 03004003666 Email: [email protected]

17
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

www.majidtahir.com Contact: 03004003666 Email: [email protected]

18
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

9608/41/M/J/16
Q.3/-

www.majidtahir.com Contact: 03004003666 Email: [email protected]

19
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

www.majidtahir.com Contact: 03004003666 Email: [email protected]

20
 Topical Past Paers 9608
(P4)Topical 4.1 Computational thinking & Problem solving)
with Sir Majid Tahir

9608/42/M/J/17
Q4/- Answers

www.majidtahir.com Contact: 03004003666 Email: [email protected]

21