Republic of Rwanda

Ministry of Education
TVET NATIONAL COMPREHENSIVE ASSESSMENT
ACADEMIC YEAR 2019

EXAM TITLE: Algorithms fundamentals /100Marks

RTQF LEVEL IV
OPTION: SOFTWARE DEVELOPMENT
DURATION: 3HOURS
INSTRUCTION TO CANDIDATES:
This exam has three section A, B and C
Section A: Answer all questions 55Marks
Section B: Choose Three Questions 30Marks
Section C: Choose one question 15Marks

SECTION ONE: Answer all questions 55Marks

1. Define the following terms: 6marks

a. Algorithm
b. Flowchart
c. Variable
d. Loop
e. Array
2. Convert 1101.1012 into decimal system. 3Marks
3. Draw the flowchart to show the use of for loop. 3Marks
4. Differentiate while loop from do while loop 4Marks
5. When an algorithm is written in the form of a programming language, it becomes a
……………
a) Flowchart 2Marks
b) Program

Page 1 of 13
 c) Pseudo code
d) Syntax
6. From the following sorting algorithms which algorithm needs the minimum
number of swaps?
a. Bubble sort
b. Quick sort 2Marks
c. Merge sort
d. Selection sort
7. From the following sorting algorithms which has the lowest worst case complexity?
a. Bubble sort
b. Quick sort 2Marks
c. Merge sort
d. Selection sort
8. What are the difference between compiler and interpreter? 6Marks
9. In data structure, there are two types of searching techniques. List and explain
them. 4Marks
10. Demonstrate (show) by the truth table the following De Morgan theorems.
5Marks
a.
b.
11. Write an algorithm which receives a number and informs the user whether it is
positive or negative. 5Marks
12. 12. (a) Convert 62010 into hexadecimal 3Marks
(b) Convert 11101001102 into hexadecimal 3Marks
13. Write an algorithm which receives student note and it displays the grade as
follows: 5Marks
Note form 16 and above: Grade A
Note 14-16 : Grade B
Note 12-14 : Grade C
Note below 12 : Grade D

14. How bubble sort works in data structure? 2marks

Page 2 of 13
SECTION TWO: Choose Three Questions 30Marks

15. Copy and complete the following table 10Marks

Name of the symbol Diagram Description

Oval ……………………. …………………….

…………………………. ………………………. It is used for data processing

……………………. …………………..

Circle …………………… ………………………….

…………………….. ……
…………………….

16. Write algorithm and the flowchart for the problem that allow the user to input
three numbers and display the sum, the average and the product of them.
10marks
17. List any five-logic gate by drawing its symbols. 10Marks
18. Describe five qualities of good algorithm 10Marks
19. (a) List any five operators available in algorithm 5marks
(b) What are the main difference between primitive and non-primitive data
types? 5Marks

SECTION THREE: Choose One question 15Marks

20. Write an algorithm allows entering a number of students in a class and the
marks obtained by those students, then calculate the sum of those marks and
their average and display the number of students, the marks, sum and average on
the screen. 15Marks
21. Write an algorithm to find the largest among three different numbers entered
by user. 15Marks

Page 3 of 13
MAKING GUIDE:

SECTION ONE: Answer all questions 55Marks

01. Define:
a. Algorithm: is a sequence of unambiguous instructions for solving a problem.
Is just a detailed sequence of simple steps that are needed to solve a problem.
1.5Marks
b. Flowchart: is a diagrammatic representation that illustrates the sequence of
operations to be performed to get the solution of a problem. Or
Is a graphical representation of an algorithm. 1.5Marks
c. Variable: A variable is the name for a place in the computer's memory where you
store some data. Or
A symbolic name associated with a value and whose associated value may be
changed. 1.5Marks
d. Loop: loop is a way of repeating a statement a number of times until some way of
ending the loop occurs. 1.5Marks
e. Array: a data structure used to store items having the same type. 1.5Marks

02. 1101.1012=1x23+1x22+0x21+1x20+1x2-1+0x2-2+1x2-3 2Marks

=8+4+0+1+0.5+0+0.125
=13.62510 1mark
03. Flowchart of For loop 3Marks

Page 4 of 13
04. The difference between the while and do-while loop is in the place where the condition
is to be tested. In the while loop, the condition is tested following the while statement and
then the body gets executed. Whereas as in do-while, the condition is checked at the end of
the loop.

The do while loop will execute at least one time even if the condition is false initially, the
do while executes until the condition becomes false. 4Marks

O5. (b) or program 2marks

06. (d) or Selection sort 2marks
07. (c) or Merge sort 2marks
08.
Compiler Interpreter

Scans the entire program and Translates program one statement at

translates it as a whole into machine a time. 1mark
code. 1mark

It generates the error message only Continues translating the program

after scanning the whole program. until the first error is met, in which
Hence debugging is comparatively case it stops. Hence debugging is
hard. 1mark easy. 1mark

It takes large amount of time to It takes less amount of time to

analyze the source code but the analyze the source code but the
overall execution time is overall execution time is slower.
comparatively faster. 1mark 1mark

09. Searching technique are:

 Linear Search or Sequential Search 1mark

 Binary Search 1mark

Page 5 of 13
Linear search: In this technique of searching, the element to be found in searching the
elements to be found is searched sequentially in the list. This method can be performed on
a sorted or an unsorted list 1mark

Binary search is a very fast and efficient searching technique. It requires the list to be in
sorted order. In this method, to search an element you can compare it with the present
element at the center of the list 1mark

10. Demonstration of Morgan Low

5marks

11. . Variable a: integer 0.5mark

START
WRITE (“enter a number”) 0.5 mark
READ (a) 0.5mark
IF (a>0) THEN 1mark
WRITE (“the number is positive”) 0.5mark
ELSE 1mark
WRITE (“ the number is negative”) 0.5mark
END IF 0.5mark
END
12. (a) 62010 = ( )16

 620

2Marks

Then, the answer will be written from right to left like this: 62010 = (26C)16 1Mark
Page 6 of 13
(b) 11101001102 =( )16 Here we have to make (form) the groups of 4 digits each, from right
to left. If it is necessary, we add the zeros on the last group where the bits are less than 4.
Lastly, we translate every quadruple to its equivalent hexadecimal.

The answer will be:

 0011 1010 0110 = ( )16 2marks

3 A 6
= 3A616 1mark

13. Var Note as integer o.5marks

Start

Write(“enter the note”)

Read(Note)

If (Note>=16) then 0.5marks

Write(“Grade A”) o.5marks

Else if(Note>=14)then 1mark

Write(“Grade B”) o.5marks

Else if (Note>=12)then 1mark

Write(“Grade C”) o.5marks

Else

Write(“Grade D”) o.5marks

End if

end

14. Bubble Sort Algorithm is used to arrange N elements in ascending order, and for that,
you have to begin with 0th element and compare it with the first element. If the 0 th element
is found greater than the 1st element, then the swapping operation will be performed, i.e.,
Page 7 of 13
the two values will get interchanged. In this way, all the elements of the array get
compared. 2Marks

SECTION TWO: Choose Three Questions 30Marks

15.

Name of the symbol Diagram Description

Oval It used to start or/and to

end a flowchart /1Mark
/1Mark

Rectangle /1Mark /1Mark It is used for data

processing

Rhombus /1Mark It is used for writing a

condition /1Mark

Circle /1Mark It is used to join more

flow lines /1Mark

Parallelogram It is used to input data

/1Mark and to display result
/1Mark

16. Algorithm:
Variables num1, num2, num3, sum, ave, product: integers 0.5marks
BEGIN
WRITE ("Enter three numbers :”) 0.5marks
READ (num1, num2, num3)
sum ←num1+num2+num3 1mark
ave ←sum/3 1mark

Page 8 of 13
 product ←num1*num2*num3 1mark
WRITE ("the sum of ”, num1,num2 ,” and ”,num3,” is ”, sum, ” their average is
”, ave, ” and their product is ”, product) 1mark
END

Flowchart: 5Marks
Begin

Input Three numbers

Read num1,num2,num3

sum ←num1+num2+num3
ave ←sum/3
sum ←num1*num2*num3

Display the value of

Sum, ave and Product

End

17. Draw the logical symbols of gates:

a. AND: 1Mark

1Mark
b. XOR 1Mark

1Mark
c. NOT 1Mark

1Mark

Page 9 of 13
 d. NOR 1Mark

1Mark
e. XNOR 1Mark

1Mark
18. Qualities of good algorithm:

a) Input: 1Mark The algorithm must take zero or more input. 1Mark
b) Output: 1Mark The algorithm may produce one or more outputs. 1Mark

c) Finiteness or Termination: 1Mark an algorithm should terminate infinite number of

steps and each step must finish in finite amount of time. 1Mark

d) Generality: 1Mark an algorithm must be generalized in order to handle a range of input

data. 1Mark

e) Definiteness: 1Mark Each step of algorithm must be defined unambiguously. 1Mark

f) Effectiveness: 1Mark A human should be able to calculate the exact values involved in
the procedure of the algorithm using paper & pencil. 1Mark
19. (a) Some operators: select only five 1mark per each

a) Arithmetic operators
b) Relational operators
c) Logical operators
d) Assignment operators
e) Increment &decrement operators
f) Conditional operators
g) Bitwise operators
h) Special operators

(b)The main difference between primitive and non-primitive data types are:

Page 10 of 13
  Primitive types are predefined (already defined). Non-primitive types are created by
the programmer and is not defined. 1mark
 Non-primitive types can be used to call methods to perform certain operations, while
primitive types cannot. 1mark
 A primitive type has always a value, while non-primitive types can be null. 1mark
 A primitive type starts with a lowercase letter, while non-primitive types starts with
an uppercase letter. 1mark
 The size of a primitive type depends on the data type, while non-primitive types have
all the same size. 1mark

SECTION THREE: Choose One question 15Marks

20.

var ,sum,,average as reals

var i,n as integers
array marks(n) as real
START
WRITE(“enter the number of students ”)
READ(n);
WRITE(“enter the marks of students”)
FOR i0 TO n
READ(marks(i))
NEXT i
sum0
FOR i0 TO n
sumsum+marks(i)
NEXT i
averagesum/n
WRITE(“the number of students is”, n)
WRITE(“ the students’ marks are”,marks(i))
WRITE(“sum of those mark is”,sum)
WRITE(“average is”, average)
Page 11 of 13
 END

21.

Var A,B,C as integer

START

Write (“ enter three numbers”)

Read (A,B,C)

If (A>B) && (A>C) then

Write(“A is largest number”)

Elseif (B>C)then

Write (“ B is the largest number”)

Else

Write(“C is the largest number”)

End if

End

Page 12 of 13
Page 13 of 13