Scribd
Upload
0 views

datastructures2

The document outlines the examination details for a Bachelor of Science in Information Technology, focusing on Data Structures and Algorithms. It includes various questions covering topics such as algorithm analysis, data structures, sorting algorithms, and graph representations. The exam consists of five questions, with students required to answer question one and any two additional questions.

Uploaded by

natembeatallia
Copyright
© © All Rights Reserved
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 views

datastructures2

The document outlines the examination details for a Bachelor of Science in Information Technology, focusing on Data Structures and Algorithms. It includes various questions covering topics such as algorithm analysis, data structures, sorting algorithms, and graph representations. The exam consists of five questions, with students required to answer question one and any two additional questions.

Uploaded by

natembeatallia
Copyright
© © All Rights Reserved
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/ 3

UNIVERSITY EXAMINATIONS: 2016/2017

EXAMINATION FOR THE DEGREE IN BACHELOR OF


SCIENCE IN INFORMATION TECHNOLOGY/
BACHELOR OF BUSINESS INFORMATION TECHNOLOGY/
BIT2102 BIT 3101A BBIT 106 DATA STRUCTURES AND
ALGORITHMS
MODE: FULL TIME/PART TIME/DISTANCE LEARNING
ORDINARY EXAMINATIONS
DATE: AUGUST, 2017 DURATION: 2 HOURS

INSTRUCTIONS: Answer question ONE and any other TWO questions

QUESTION ONE [30 MARKS]

a) Differentiate between the following concepts as used in algorithm analysis.


i. Space complexity and time complexity
ii. Big O notation and theta notation
[4 Marks]
b) If you push the letters D, C, B and A in order onto a stack of characters and then pop
them, in what order will they be deleted from the stack?
[4 Marks]
c) Define a recursive function and give any two examples that can be solved recursively.
[4 Marks]
d) The numbers 20, 70, 68, 59,30,15,90,70,60,85 are to be stored for some processing in
that order. Write down the order in which the numbers will be printed if they are:
i. stored in a queue
ii. stored in a stack and
iii. stored in a binary search tree and traversed in order.
[9 Marks]
e) Explain the sufficient conditions for a binary tree to be a heap.
[2 Marks]
f) Design an algorithm for calculating Fibonacci series and estimate its big O.
[7 Marks]
QUESTION TWO [20 MARKS]

a) Write down the algorithm for merge sort and state its big O.
[6 Marks]
b) Performing operations such as delete and insert in a doubly linked list is not easy.
Explain.
[4 Marks]
c) Explain how the divide and conquer technique works. Give two examples.
[4 Marks]
d) Represent the following expression tree: (((A+B)*C+D)*E)-((A+B)*C-D) and write
the prefix and postfix expressions.
[6 Marks]

QUESTION THREE [20 MARKS]


a) Distinguish between preorder and postorder traversal of a binary tree
[4 Marks]
b) Consider the following of a table fields, construct a binary tree to represent them.

[4 Marks]
c) Describe two applications of binary search trees.
[2 Marks]
d) ) Explain why a queue is a two-point structure where a stack is one point structure
[3 Marks]
e) What is an algorithm?
[2 Marks]
f) Describe the following properties that an algorithm must have: precision, uniqueness,
finiteness, input and output.
[5 Marks]

QUESTION FOUR [20 MARKS]


a) Explain what is an in-order traversal for a binary tree?
[2 Marks]
b) Write an algorithm to execute an in-order traversal.
[3 Marks]
c) Estimate the order of magnitude for the expression 3n  2 
2

[4 Marks]
d) Describe two ways of representing a graph ADT.
[4 Marks]
e) Construct a directed graph with the vertices A,B,C,D and E using the information
below.
A B C D E
A 0 0 5 6 0
B 0 0 4 5 2
C 4 5 0 4 6
D 6 0 0 0 0
E 5 0 0 0 0
[5 Marks]
f) Briefly describe the depth first search algorithm as used in graph traversal.
[2 Marks]
QUESTION FIVE [20 MARKS]
a) If two or more values in a hash function, map to the same key, a collision is said to
occur. Collisions are not allowed in a hash table. Briefly describe the following
techniques for resolving collisions.
i. re-hashing
ii. chaining
iii. linear probing.
[6 Marks]
b) Differentiate between dynamic programming and backtracking algorithms. Give one
example for each.
[4 Marks]
c) Describe the guidelines for developing an algorithm using a pseudo code.
[5 Marks]
d) Describe the procedure for insert sort.
[3 Marks]
e) Re-arrange the following numbers in descending order using insert sort.
2,4,8,6,10,16,12,14,20,18.
[2 Marks]

You might also like