0% found this document useful (0 votes)

128 views136 pages

9618 Computer Science

Uploaded by

Abishek Shanmuganathan

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

128 views136 pages

9618 Computer Science

Uploaded by

Abishek Shanmuganathan

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 136

Cambridge International AS & A Level

* 4 7 5 7 0 1 8 5 5 9 *

COMPUTER SCIENCE 9618/32

Paper 3 Advanced Theory May/June 2021

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

INSTRUCTIONS
● Answer all questions.
● Use a black or dark blue pen.
● Write your name, centre number and candidate number in the boxes at the top of the page.
● Write your answer to each question in the space provided.
● Do not use an erasable pen or correction fluid.
● Do not write on any bar codes.
● You may use an HB pencil for any diagrams, graphs or rough working.
● Calculators must not be used in this paper.

INFORMATION
● The total mark for this paper is 75.
● The number of marks for each question or part question is shown in brackets [ ].
● No marks will be awarded for using brand names of software packages or hardware.

This document has 12 pages.

DC (LK/CB) 205788/1
© UCLES 2021 [Turn over
2

1 Real numbers are stored in a computer system using floating-point representation with:

• 10 bits for the mantissa

• 6 bits for the exponent
• Two’s complement form for both the mantissa and the exponent.

(a) Calculate the normalised floating-point representation of –7.25 in this system.

Show your working.

Mantissa Exponent

Working .....................................................................................................................................

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

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

(b) Calculate the denary value of the given binary floating-point number.
Show your working.

Mantissa Exponent

1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1

Working .....................................................................................................................................

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

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

© UCLES 2021 9618/32/M/J/21

(c) The given binary floating-point number is not normalised.

Normalise the floating-point number. Show your working.

Mantissa Exponent

0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1

Mantissa Exponent

Working .....................................................................................................................................

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

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

(d) The denary number 513 cannot be stored accurately as a normalised floating-point number in
this computer system.

(i) Explain the reason for this.

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

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

(ii) Describe an alteration to the way floating-point numbers are stored to enable this number
to be stored accurately using the same total number of bits.

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

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

© UCLES 2021 9618/32/M/J/21 [Turn over

2 (a) Describe the purpose of a user-defined data type.

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

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

(b) Define, using pseudocode, the following enumerated data types:

(i) SchoolDay to hold data about the days students are usually in school.

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

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

(ii) WeekEnd to hold data about the days that are not school days.

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

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

• first name and last name

• the two days they attend:
○ one on a school day
○ one not on a school day.

Use the enumerated types you created in part (b).

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

............................................................................................................................................. [4]

© UCLES 2021 9618/32/M/J/21

3 (a) Draw one line to connect each Operating System (OS) term to the most appropriate
description about it.

OS term Description

Using secondary storage to simulate

additional main memory
Multi-tasking

Managing the processes running on

the CPU
Paging

Managing the execution of many programs

that appear to run at the same time

Interrupt handling

Locating non-contiguous blocks of data and

relocating them

Scheduling
Transferring control to another routine when
a service is required

Virtual memory
Reading/writing same-size blocks of data
from/to secondary storage when required

[5]

(b) Explain how an interpreter executes a program without producing a complete translated
version of it.

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

............................................................................................................................................. [4]

© UCLES 2021 9618/32/M/J/21 [Turn over

4 (a) (i) Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of
expressions.

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

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

(ii) Identify, with reasons, a data structure that could be used to evaluate an expression
in RPN.

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

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

(b) Write the infix expression in RPN.

(a – b) * (a + c) / 7

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

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

(c) Write the RPN expression as an infix expression.

a b / 4 * a b + -

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

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

(d) Evaluate the RPN expression:

a b + c d / /

where a = 17, b = 3, c = 48 and d = 12.

Show your working.

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

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

© UCLES 2021 9618/32/M/J/21

5 (a) Calculate the shortest distance between the base and each of the other towns in the diagram
using Dijkstra’s algorithm.

Show your working and write your answers in the table provided.

Base
4
5

Town 1 2
1 Town 2
8

Town 3

7 3 Town 6
1

5
6
Town 4 Town 5

Working .....................................................................................................................................

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

Answers

Town 1 Town 2 Town 3 Town 4 Town 5 Town 6

[5]

© UCLES 2021 9618/32/M/J/21 [Turn over

(b) Explain the use of graphs to aid Artificial Intelligence (AI).

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

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

6 Give two benefits and two drawbacks of packet switching.

Benefit 1 ...........................................................................................................................................

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

Benefit 2 ...........................................................................................................................................

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

Drawback 1 ......................................................................................................................................

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

Drawback 2 ......................................................................................................................................

..........................................................................................................................................................
[4]

© UCLES 2021 9618/32/M/J/21

7 The diagram shows a logic circuit.

A P
Y
B

C R

Z
Q

(a) Complete the truth table for the given logic circuit. Show your working.

Inputs Working space Outputs

A B C P Q R Y Z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
[3]
(b) State the name of the logic circuit.

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

(c) Write the Boolean expressions for the two outputs Y and Z in the truth table as
sum-of-products and state the purpose of each output.

Y = ............................................................................................................................................

Purpose ....................................................................................................................................

Z = ............................................................................................................................................

Purpose ....................................................................................................................................
[4]

© UCLES 2021 9618/32/M/J/21 [Turn over

8 (a) State two factors that may affect the performance of a sorting algorithm.

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

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

(b) The given algorithm is a simple bubble sort that arranges a set of scores stored in a one-
dimensional array into descending order, and orders the corresponding students’ names
stored into a two-dimensional array in the same order as the scores. All the arrays are indexed
from 1.

The contents of both arrays after sorting are shown.

Name
Score
1 2
1 98 1 Smithfield Tom
2 97 2 Johnson Jane

… …

248 5 248 Peters Jade

249 3 249 Allen John

YearSize 249 ←
Flag ←
TRUE
WHILE Flag = TRUE
Flag FALSE←
FOR Student ←
1 TO YearSize - 1
IF Score[Student] < Score[Student + 1] THEN
Temp1 ←
Score[Student]
Temp2 ←
Name[Student,1]
Temp3 ←
Name[Student,2]
Score[Student] Score[Student + 1] ←
Name[Student,1] Name[Student + 1,1] ←
Name[Student,2] Name[Student + 1,2] ←
Score[Student + 1] Temp1 ←
Name[Student + 1,1] Temp2 ←
Name[Student + 1,2] Temp3 ←
Flag TRUE ←
ENDIF
NEXT Student
ENDWHILE

© UCLES 2021 9618/32/M/J/21

Write an algorithm, using pseudocode, that will perform the same task using an insertion sort.

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

............................................................................................................................................. [6]

© UCLES 2021 9618/32/M/J/21 [Turn over

9 (a) Describe what is meant by an imperative (procedural) programming language.

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

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

(b) Describe what is meant by a declarative programming language.

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

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

Program code example Programming paradigm

male(john).
female(ethel).
parent(john, ethel).
FOR Counter = 1 TO 20
X = X * Counter
NEXT Counter
Start: LDD Counter
INC ACC
STO Counter
public class Vehicle
{
private speed;
public Vehicle()
{
speed = 0;
}
}
[4]

Permission to reproduce items where third-party owned material protected by copyright is included has been sought and cleared where possible. Every
reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the
publisher will be pleased to make amends at the earliest possible opportunity.

To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge
Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download
at www.cambridgeinternational.org after the live examination series.

Cambridge Assessment International Education is part of the Cambridge Assessment Group. Cambridge Assessment is the brand name of the University of
Cambridge Local Examinations Syndicate (UCLES), which itself is a department of the University of Cambridge.

© UCLES 2021 9618/32/M/J/21

Cambridge International AS & A Level
* 7 9 2 0 7 5 1 8 6 5 *

COMPUTER SCIENCE 9618/32

Paper 3 Advanced Theory October/November 2021

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

This document has 16 pages. Any blank pages are indicated.

DC (RW/SW) 206388/2
© UCLES 2021 [Turn over
2

1 (a) Numbers are stored in a computer using floating-point representation with:

• 12 bits for the mantissa

• 4 bits for the exponent
• two’s complement form for both the mantissa and exponent.

(i) Write the normalised floating-point representation of the following unsigned binary
number using this system.

1011100.011001
Working .............................................................................................................................

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

Mantissa Exponent

[2]

(ii) State the consequence of storing the binary number in part (a)(i) as a floating-point
number in this system. Justify your answer.

Consequence ....................................................................................................................

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

Justification .......................................................................................................................

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

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

(b) Explain the reason why binary numbers are stored in normalised form.

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

............................................................................................................................................. [3]
© UCLES 2021 9618/32/O/N/21
3

2 Draw one line from each programming paradigm to its most appropriate description.

Programming paradigm Description

Programs using the instruction set of a

processor

Declarative
Programs based on events such as user
actions or sensor outputs

Imperative
Programs using the concepts of class,
inheritance, encapsulation and
polymorphism
Low-level

Programs with an explicit sequence of

commands that update the program state,
Object-oriented with or without procedure calls

Programs that specify the desired result

rather than how to get to it

[4]

3 Enumerated and pointer are two non-composite data types.

(a) Write pseudocode to create an enumerated type called Parts to include these parts sold in
a computer shop:

Monitor, CPU, SSD, HDD, LaserPrinter, Keyboard, Mouse

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

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

(b) Write pseudocode to create a pointer type called SelectParts that will reference the
memory location in which the current part name is stored.

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

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

© UCLES 2021 9618/32/O/N/21 [Turn over

4 The following syntax diagrams for a particular programming language show the syntax of:

• a digit
• a capital letter
• a character.

digit capital letter

0 A

1 E

2 I

3 O

4 U

5 character
$

6
%

7
&

8
*

9
#

(a) Write the Backus-Naur Form (BNF) notation of the syntax diagram for character.

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

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

© UCLES 2021 9618/32/O/N/21

(b) A password must begin with a character and be followed by one or more digits or capital
letters.

(i) State an example of a valid password.

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

(ii) A valid password is represented by the syntax diagram:

password
character digit

capital letter

Write the BNF notation of the syntax diagram for password.

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

..................................................................................................................................... [4]

© UCLES 2021 9618/32/O/N/21 [Turn over

5 (a) Compare sequential and serial methods of file organisation.

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

............................................................................................................................................. [4]

(b) State the most suitable method of file access when a record is referenced by a unique
address on a disk-type storage medium.

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

(c) State the most suitable method of file access when a bank stores its data records in ascending
order of account number.

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

© UCLES 2021 9618/32/O/N/21

6 (a) Explain how packet switching is used to transfer messages across the internet.

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

............................................................................................................................................. [5]

(b) Outline the function of a router in packet switching.

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

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

© UCLES 2021 9618/32/O/N/21 [Turn over

7 (a) Write the Boolean expression that corresponds to the given truth table as a sum-of-products.

INPUT OUTPUT

A B C D Z

0 0 0 0 0

0 0 0 1 0

0 0 1 0 0

0 0 1 1 0

0 1 0 0 0

0 1 0 1 0

0 1 1 0 0

0 1 1 1 0

1 0 0 0 0

1 0 0 1 1

1 0 1 0 0

1 0 1 1 1

1 1 0 0 1

1 1 0 1 1

1 1 1 0 1

1 1 1 1 1

Z = ............................................................................................................................................

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

© UCLES 2021 9618/32/O/N/21

(b) (i) Complete the Karnaugh map (K-map) for the given truth table.

CD 00 01 11 10

[2]

(ii) Draw loop(s) around appropriate group(s) of 1s in the K-map to produce an optimal
sum-of-products. [2]

(iii) Write the Boolean expression from your answer to part b(ii) as a simplified
sum-of-products.

Z = .....................................................................................................................................

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

(iv) Write the simplified Boolean expression for your answer to part b(iii).

Z = .....................................................................................................................................

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

© UCLES 2021 9618/32/O/N/21 [Turn over

8 (a) Describe the purpose of the Secure Sockets Layer (SSL) and Transport Layer Security (TLS)
protocols.

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

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

(b) Explain how SSL/TLS protocols are used when a client-server communication is initiated.

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

............................................................................................................................................. [4]

© UCLES 2021 9618/32/O/N/21

9 (a) The diagram shown represents an artificial neural network.

Output
Layer
Input
Layer
Hidden Hidden
Layer 1 Hidden Layer 3
Layer 2

(i) State the reason for having multiple hidden layers in an artificial neural network.

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

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

(ii) Explain how artificial neural networks enable machine learning.

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

..................................................................................................................................... [4]

© UCLES 2021 9618/32/O/N/21 [Turn over

(b) Find the shortest path between the Home and School nodes using the A* algorithm.
Show your working in the table provided.

The first two rows in the table have been completed.

h = 10 Home 9
g=1 4
A 5 C
3
7
B 6
2
6
D 6
3
7
F
1
2
3
E
3 5
School

Node Cost from Home node (g) Heuristic (h) Total (f = g + h)

Home 0 14 14

A 1 10 11

Final path
[5]

© UCLES 2021 9618/32/O/N/21

10 (a) State three essential features of recursion.

1 ................................................................................................................................................

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

2 ................................................................................................................................................

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

3 ................................................................................................................................................

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

(b) Explain the reasons why a stack is a suitable Abstract Data Type (ADT) to implement
recursion.

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

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

(c) Identify two ADTs other than a stack.

1 ................................................................................................................................................

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

© UCLES 2021 9618/32/O/N/21 [Turn over

(d) The function StackFull() checks whether a stack is full.

The function uses the variable TopOfStack to represent the pointer to the most recent
position used on the stack, and the variable Max to represent the maximum size of the stack.
Assume TopOfStack and Max are global variables.

FUNCTION StackFull() RETURNS BOOLEAN

IF TopOfStack = Max THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION

An algorithm AddInteger is required to add a new integer data element to a stack.

The stack is implemented as an array ArrayStack.

The function AddInteger() calls StackFull() and returns an appropriate message.

Complete the pseudocode for the function AddInteger().

FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING

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

ENDFUNCTION
[5]

© UCLES 2021 9618/32/O/N/21

BLANK PAGE

© UCLES 2021 9618/32/O/N/21

BLANK PAGE

© UCLES 2021 9618/32/O/N/21

Cambridge International AS & A Level
* 9 7 4 0 2 6 7 5 7 0 *

COMPUTER SCIENCE 9618/32

Paper 3 Advanced Theory October/November 2022

1 hour 30 minutes

You must answer on the question paper.

No additional materials are needed.

This document has 12 pages. Any blank pages are indicated.

DC (RW/CGW) 302516/4
© UCLES 2022 [Turn over
2

1 Normalised floating-point numbers are stored in a computer system using two’s complement for
both the mantissa and the exponent with:

• 11 bits for the mantissa

• 5 bits for the exponent.

(a) Write the largest positive two’s complement binary number that can be stored in this system.

Mantissa Exponent

[1]

(b) Calculate the denary value of the given binary floating-point number.
Show your working.

Mantissa Exponent

1 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1

Working .....................................................................................................................................

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

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

(c) State when underflow occurs in a binary floating-point system.

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

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

© UCLES 2022 9618/32/O/N/22

2 Lexical analysis and syntax analysis are stages in the compilation of a program.

(a) Identify two other stages that take place during the compilation of a program.

1 ................................................................................................................................................

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

2 ................................................................................................................................................

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

(b) Outline the purpose of syntax analysis.

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

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

3 (a) Explain why a protocol is used in communication between computers.

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

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

(b) The TCP/IP protocol implementation can be viewed as a stack.

Complete the diagram for the TCP/IP protocol stack.

Transport

Link
[2]

(c) Describe the purpose of the IMAP protocol.

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

............................................................................................................................................. [2]
© UCLES 2022 9618/32/O/N/22 [Turn over
4

4 A program to manage regular flight details at an airport requires some user-defined data types.

(a) Write pseudocode statements to declare the enumerated data type Aircraft to hold data
about the types of aircraft used for a flight.

These types of aircraft are: C300, C350, D242, E757, X380.

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

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

(b) Write pseudocode statements to declare the composite data type Flight to hold data about
flights to a specific destination. These include:

• flight number, which could be any combination of letters and numbers

• destination
• date of departure
• type of aircraft used.

Use the enumerated data type you created in part (a).

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

............................................................................................................................................. [4]

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

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

© UCLES 2022 9618/32/O/N/22

(ii) Write pseudocode to store the details of the following flight in the variable you set up in
part (c)(i).

Field Data
flight number XA782
destination Cambridge
date of departure 12/12/2022
type of aircraft used C350

Use the field names you created in part (b).

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

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

5 Describe what is meant by a virtual machine.

Include in your answer two benefits and two drawbacks of using a virtual machine.

Description .......................................................................................................................................