TVET NATIONAL COMPREHENSIVE ASSESSMENT

SCHOOL YEAR 2020-2021

SECTOR: ICT

TRADE: SOFTWARE DEVELOPMENT

RTQF LEVEL: 4

MODULE CODE AND TITLE: (SFDAF401) ALGORITHM FUNDAMENTALS

DURATION : 3HOURS

INSTRUCTIONS TO CANDIDATE:

SECTION A: Attempt all questions in section A /55 MARKS

SECTION B: Attempt all questions in section B /30 MARKS

SECTION C: Choose one (1) question in section C /15 MARKS

SECTION A: ATTEMPT ALL QUESTION IN SECTION A /55 MARKS

QUESTION1: Define the following terms: 5 Marks

MARKING SCHEME:
 a. Algorithm: a set of instruction step by step to solve a given
problem(1mark)
b. Flowchart: graphical representation of algorithm(1mark)
c. Variable: memory location that hold value that can be
change(1mark)
d. Loop: a loop is a programming structure that repeats a sequence
of instructions until a specific condition is met. (1mark)
e. linked list is a linear collection of data elements whose order is
not given by their physical placement in memory. Instead, each
element points to the next. It is a data structure consisting of a
collection of nodes which together represent a sequence(1mark)
REFERENCE: Lu1: Describe basic concept of algorithm
REFERENCE: Lu2: Apply programming structures, iterative
constructs and structured programming

REFERENCELU3: Describe data structure

QUESTION2: describe various operation which can be performed from a

linked list (5marks)
MARKING SCHEME:

Basic Operations on Linked List

Traversal: To traverse all the nodes one after another. (1mark)

Insertion: To add a node at the given position. (1mark)

Deletion: To delete a node. (1mark)

Searching: To search an element(s) by value. (1mark)

Updating: To update a node. (1mark)

Sorting: To arrange nodes in a linked list in a specific order (1mark)

REFERENCE LU3: Describe data structure

QUESTION3: write a simple algorithm to add two numbers(2Marks)

MARKING SCHEME:

Step 1: Start (0.5Mark)

Step 2: Declare variables num1, num2 and sum. (1Mark)

Step 3: Read values num1 and num2. (1Mark)

Step 4: Add num1 and num2 and assign the result to sum.

sum←num1+num2(1Mark)

Step 5: Display sum (1Mark)

Step 6: Stop(0.5Mark)

REFERENCE: Lu1: Describe basic concept of algorithm

QUESTION4: convert the following binary number to their decimal

equivalent:
A) 11100.001(2.5Marks)
B) 110011.10011(2.5Marks)
MARKING SCHEME:

REFERENCE: Lu1: Describe basic concept of algorithm

QUESTION5: Draw the flowchart to show the use of for loop. (2Marks)
MARKING SCHEME:
REFERENCE: Lu1: Describe basic concept of algorithm
QUESTION6: Differentiate while loop from do while loop 5Marks
MARKING SCHEME:

REFERENCE: Lu2: Apply programming structures, iterative

constructs and structured programming

QUESTION7. I. How can we define an array? defend your answer

(2.5Marks)

A. The Array shows a hierarchical structure.

 B. Arrays are immutable.

C. Container that stores the elements of similar types

D. The Array is not a data structure

MARKING SCHEME:

Answer: c(1.5Marks)

Explanation: The answer is c because array stores the elements in

a contiguous block of memory of similar types. Therefore, we can
say that array is a container that stores the elements of similar
types(1Marks)

REFERENCELU3: Describe data structure

II. Which of the following is the disadvantage of the array? (2.5Marks)

A. Stack and Queue data structures can be implemented through

an array.

B. Index of the first element in an array can be negative

C. Wastage of memory if the elements inserted in an array are

lesser than the allocated size

D. Elements can be accessed sequentially.

MARKING SCHEME:

c(2.5Marks)

Explanation: The answer is c. For example, if we have an array of size

10 elements and we have inserted only 5 elements in an array then
there is a wastage of 5 memory blocks which cannot be utilized by
another variable.
 REFERENCELU3: Describe data structure

QUESTION8: Sorting Algorithms are methods of reorganizing a large

number of items into some specific order such as highest to lowest, or vice-
versa, or even in some alphabetical order. List 5 sorting algorithm you know
(5Marks)

MARKING SCHEME:

1. Quick Sort (1Mark)

2. Bubble Sort(1Mark)
3. Merge Sort(1Mark)
4. Insertion Sort(1Mark)
5. Selection Sort(1Mark)
6. Heap Sort(1Mark)
7. Radix Sort(1Mark)
8. Bucket Sort(1Mark)

NB: ONLY FIVE ARE CONSIDERED

REFERENCELU3: Describe data structure

QUESTION9: Different algorithms play different roles in programming. You

only need to define your problem then select the right algorithm to use. write
at least 5 types of algorithm you know (5Marks)

1) Searching algorithms(1Mark)

2) Pathfinding algorithm(1Mark)

3) Sorting algorithms(1Mark)

4) Compression algorithms(1Mark)

5) Tree and graph-based algorithms(1Mark)

6) Pattern matching algorithm among many others(1Mark)

 REFERENCELU3: Describe data structure

QUESTION 10: Write an algorithm which receives a number and calculate

its factorial(5Marks)

MARKING SCHEME:

Step 1: Start(0.5Marks)

Step 2: Declare variables n, factorial and i. (0.5Marks)

Step 3: Initialize variables

factorial ← 1(0.5Marks)

i ← 1(0.5Marks)

Step 4: Read value of n(0.5Marks)

Step 5: Repeat the steps until i = n(0.5Marks)

5.1: factorial ← factorial*i(0.5Marks)

5.2: i ← i+1(0.5Marks)

Step 6: Display factorial(0.5Marks)

Step 7: Stop(0.5Marks)

REFERENCE: Lu2: Apply programming structures, iterative

constructs and structured programming

QUESTION 11: Draw a flowchart to determine a student’s final grade and

indicate whether it is passing or failing according to the marks obtained in 4
subject. The pass marks should be 50 and above (5Marks)

MARKING SCHEME:
QUESTION12: Discuss the Characteristics of an Algorithm (5Marks)
MARKING SCHEME:

An algorithm should have the following characteristics −

• Unambiguous − Algorithm should be clear and unambiguous. Each of its
steps (or phases), and their inputs/outputs should be clear and must lead to
only one meaning. (1Mark)

• Input − An algorithm should have 0 or more well-defined inputs. (1Mark)

• Output − An algorithm should have 1 or more well-defined outputs, and

should match the desired output. (1Mark)

• Finiteness − Algorithms must terminate after a finite number of steps.

(1Mark)

• Feasibility − Should be feasible with the available resources. (1Mark)

• Independent − An algorithm should have step-by-step directions, which
should be independent of any programming code. (1Mark)
REFERENCE: Lu1: Describe basic concept of algorithm

SECTION B: ATTEMPT ALL QUESTION IN SECTION B /30 MARKS

QUESTION 13: Copy and complete the following table 10Marks

NB: Each contains one mark
MARKING SCHEME:

Symbol Symbol Name Purpose

Used at the beginning and end of the

Start/Stop algorithm to show start and end of the
program.

Indicates processes like mathematical

Process operations.

Used for denoting program inputs and

Input/ Output
outputs.

Stands for decision statements in a

program, where answer is usually Yes or
Decision No.

Shows relationships between different

Arrow shapes.

Connects two or more parts of a flowchart,

On-page which are on the same page.
Connector
 REFERENCE: Lu1: Describe basic concept of algorithm

QUESTION14 List any five-logic gate by drawing its symbols .

MARKING SCHEME:

10Marks
NB: Each symbol and name take 2 marks.
REFERENCE: Lu1: Describe basic concept of algorithm

QUESTION15. What is the difference between a PUSH and a POP? 10Marks

MARKING SCHEME:
1. The acronyms stand for Pushing and Popping operations performed
on a stack. These are ways data is stored and retrieved.
(2.5MARKS)

2. PUSH is used to add an item to a stack, while POP is used to remove

an item. (2.5MARKS)

3. PUSH takes two arguments, the name of the stack to add the data to
and the value of the entry to be added. POP only needs the name of
the stack. (2.5MARKS)

4. When the stack is filled and another PUSH command is issued, you
get a stack overflow error, which means that the stack can no longer
 accommodate the last PUSH. In POP, a stack underflow error occurs
when you’re trying to POP an already empty stack. (2.5MARKS)

REFERENCELU3: Describe data structure

SECTION C: CHOOSE ONE (1) QUESTION IN SECTION C /15 MARKS

QUESTION16: Draw the flowchart of the following algorithm 15 Marks

Step 1: Start

Step 2: Declare variables a,b and c.

Step 3: Read variables a,b and c.

Step 4: If a > b

If a > c

Display a is the largest number.

Else

Display c is the largest number.

Else

If b > c

Display b is the largest number.

Else

Display c is the greatest number.

Step 5: Stop

MARKING SCHEME:
 REFERENCE: Lu1: Describe basic concept of algorithm

QUESTION17: We know that an algorithm in a set of instruction to solve a

problem, it guides the programmer to the logic of program. Therefore, to
solve any programming problem goes under 4 steps for better logic and
better output. As a future programmer discuss about four steps in solving
programming problem. 15 Marks

MARKING SCHEME:

Four Main Problem Solving Steps:

 Understand the Problem. Solving the right problem is the
most important part of problem solving
 Design a Solution. Formulate an algorithm to solve your problem.
 Implement your Solution. Write the code to solve your problem.
 Check your Solution.
REFERENCE: Lu1: Describe basic concept of algorithm