**UNIVERSITY EXAMINATIONS: 2018/2019**

**EXAMINATION FOR THE DIPLOMA IN BUSINESS INFORMATION **

**TECHNOLOGY**

**DBIT305 DATA STRUCTURES & ALGORITHMS**

**DATE: AUGUST, 2019 TIME: 2 HOURS**

**INSTRUCTIONS: Answer Question One and ANY other two questions.**

**QUESTION ONE [20 MARKS]**

(a) List and explain two parameters used to estimate the complexity of an algorithm

[4 Marks]

(b) Describe three advantages and two disadvantages of pseudo code as an algorithm

development tool [5 Marks]

(c) Compare and contrast arrays and structures. [4 Marks]

(d) With aid of suitable illustrations, explain the following terms with regard to tree data

structure:-

(i) Root [2 Marks]

(ii) Height [2 Marks]

(iii)Path [2 Marks]

(iv)Leaf [2 Marks]

(e) Describe three applications of queues in computers [3 Marks]

(f) A linked list consists of a collection of nodes where each node in the list has two key

components.

Required: Explain these two key components [4 Marks]

(g) Explain the term “data structure” [2 Marks]

**QUESTION TWO [20 MARKS]**

(a) Convert the following infix expressions into postfix using stack Abstract Data Type (ADT):

(i) B*((A+D)/C-F) [4 Marks]

(ii) D*(A+B/C) [4 Marks]

(b) Write C or C++ code to implement a union data structure named students that has the

following members:-

(i) studentIDNumber

(ii) Firstname -an array of 7 characters

(iii)Weight

(iv)Feebalance

Note: create an object named James from the students data structure [7 Marks]

(c) Outline the steps of designing an algorithm [5 Marks]

**QUESTION THREE [20 MARKS]**

(a) Outline four guidelines of designing flowcharts [4 Marks]

(b) Explain five features of good algorithm [5 Marks]

(c) Figure 1 below shows a typical data structure. Use it to answer the questions that follow:

Figure 1

Required:

(i) State two limitations and two advantages of this data structure [4 Marks]

(ii) Outline three data operations supported by the above data structure [3 Marks]

(iii)Write a C++/ C program statement to:

(i) Declare the data structure above [2 Marks]

(ii) Initialize the data structure [2 Marks]

**QUESTION FOUR [20 MARKS]**

(a) The KCA University Electoral voting system involves voting by students pressing a number

representing the candidate of their choice. The numbers used range from 1 to 5. The recent

polls had five candidates whose identification numbers and philosophical messages were as

follows:

Required:

(i) Design an algorithm using flowchart for a C/C++ program that prompts the voter to

enter a number representing his/ her preferred candidate. The program then outputs

philosophical message depending on the choice made. [9 Marks]

(ii) Outline two advantages of flowcharts [2 Marks]

(b) Outline five examples of algorithm designing tools. [5 Marks]

(c) Explain the following terms:-

(i) Dynamic data structures [2 Marks]

(ii) Linear data structures [2 Marks]

**QUESTION FIVE [20 MARKS]**

(a) Discuss two techniques of testing an algorithm [4 Marks]

(b) Write a C or C++ program segment that adds the following elements into a stack named

Marks and reads and returns the total number of elements stored in the stack:-

60, 49,60,39,70 [7 Marks]

(c) State and justify the most appropriate data structure to use in the following applications:

(i) Deleting characters from a word document using backspace key [2 Marks]

(ii) Serving customers in a restaurant [2 Marks]

(iii)Storing and retrieving books information at KCA University library [2 Marks]

Page 4 of 4

(d) Explain the purpose of the following operations as used in queues data structure:-

[3 Marks]

(i) Dequeue

(ii) Enqueue()

(iii)Top()