yen tiORS \ jiyyite UTR ) ack {0b 40h sity UNIVERSITY EXAMINATION 2024/2025 SCHOOL OF COMPUTING AND INFORMATICS DEPARTMENT OF INFORWATION TECHNOLOGY/ENTERPRISE COMPUTING BEDA/BECS/BCCS/BBIT/BIT REGULAR UNIT CODE: BIT2203 UNIT TITLE: DATA STRUCTURES & ALGORITHMS : TUE 17™ DEC, 2024 17.00AM MAIN EXAM TIME: 2 HOURS INSTRUCTIONS: ANSWER QUESTION ONE AND ANY OTHER TWO UESTION ONE a) Suppose you are to deve'op an application for a mobile phone book. Suggest the data structure that you will use. What are the factors that will guide you for your choice. (10 Marks) '») Proper choice of a data siructure will result and best possible algorithm and ultimately, results in a good program. Explain. (5 Marks) c) Given the binary tree beldw, construct the equivalent array representation showing all the positions. (6 Marks) Page 1d) Differentiate between space complexity and time complexity. (4 Marks) e) Draw a binary Tree for the expression : (6 Marks) A*B-(C+D)* (P/Q) n, i QUESTIONTWO,~ | 1 a) Using well labeled diagram(s) explain the following concepts of a tree, ) (10 Marks) i) root I | : ii) Size : iii) Depth i AM iv)leaf Your LEARNING PAR TNE v) path TEL: 0706 464 292 b) Whatis an ‘algorithm? Outline FIVE desirable characteristics of an algorithm. (6 Marks) ©) Compare the usage of linked lists to arrays as technique of implementing ADTs. (4 Marks) QUESTION THREE @) Outline any FIVE areas in which data structures are applied extensively? ; (5 Marks) b) Convert the following infix expression into bina Use the tree to perform i) prefix and ! ii) postfix traversal ry tree: (24y) ~ (ab). (9 Marks) ©) Explain three types (measures) of time complexity of an algorithm. (6 Marks) QUESTION FOUR * @) i) Whatis a stack? (1 Mark ii) Define the term sequential search, and explain its performance relative to the element population, (4 Marks) b) You have been contracted to write a program to simulate the inbox of mobile phone, 4 i) Which data structure will you choose? ii) Write a function to insert a, new element into the structure in (i) above aa TS IERIImmeenseeenee ee Paper one Page 2DANFAM Contin aoNs] YOUR LEARNING pantweR TEL: 0706 464 292 (10 Marks) ©) Give the adjacency matrix A for the following graph G based on the order: a,b,c,d? (5 Marks) QUESTION FIVE K a)i) Whatis a heap? (2 Marks) ji) Map the array below into a heap. (4 Marks) L 80 l 60 73 35 40 50 70 30 | 20 | 39 b) i) Explain how straight selection sort works. (4 Marks) ii)Perform a selection sort the array below. (5 Marks) 84, 69, 76, 86, 94, 91 ©) Explain five applications of Queue ADT. (5 Marks)Mount i , University : UNIVERSITY EXAMINATION 2020/2024 SCHOOL OF COMPUTING AND INFORMATICS DEPARTMENT OF INFORMATION MMCHNOLOGY/SNTERPRISE COMPUTING wy BIT + DULAR UNIT CODE: BIT2203 UNIT TITLE: DATA STRUCTURES AND ALGORITHMS DATE: TUE 207 APRIL 2023 12.0¢eM MAIN EXAM ME:2 HOURS INSTRUCTIONS: Question One is Compulsory (30 Maiks) and any other Two Questions. The other Questions are 20 Marks cach, Guestion One a) Define the following terms; (6 Marks) i. Data Structure ii. Algorithmn iil, Arrays iv. Linked lists v. Abstract Data Type (ADT) vi. Binary Trees b) State and briefly describe any three characteristics of an algorithm. (6 Marks) ©) Design an algorithm to multiply the two numbers x and y and display the result in z (6 Marks) d) Briefly describe the mergesort. (4 Marks) Paper One Page i —————ee DANFAM COMMUNICATIONS, YOUR LEARNING PARTNER “TEL: 0706461292 e) Briefly discuss the classification of data stuctures. (8 Marks) n Two a) Describe the algorithm for carrying out ih bubble sort. (6 Marks) ») Briefly explain Why is the bubble sort so slow. (4 Marks) ©) Describe three ways stacks and queues cifler From arrays. (6 Marks) dl) Big O notation specifies a relationship lw veen two variables. Describe the two ‘ variables, (4 Marks) _ uestion Three '@) There are three cases which are usually ised to compare various data structure's execution time in a relative manner. Stes and briefly describe the three cases. (6 Marks) » .- b) Let's consider an array arr = {1, 5, 7, §, 13, 19, 20, 23, 29}. Find the location of the item 23 in the array using binary si arch. (14 Marks) sion Four 1) Selection sort Is a simple sorting algorit! m. Write a pseudocode for the selection sort. (10 Marks) 2. ) Linear search is mostly usec! to search an unordered list in which the items are not sorted. write the algorithm ‘or tinear search, (10 Marks) Question Five a) Briefly describe the operation of the quicksort algorithm. (4 Marks) b) Briefly describe the recursive solution to the Towers of Hanoi puzzle. (4 Marks) ©) Briefly describe any two properties of ar. array. (4 Marks) @) Discuss why data Structures cre widely sed in almost every aspect of Computer Science and information technology. (8 Marks) e One Page 2 [YOUR LFARHIEG pay rry TEL: 0706 461 202 | Mount Kenya /*) University UNIVERSITY EXAMINATION 2024/2025 SCHOOL OF COMPUTING AND INFORMATICS DEPARTMENT OF INFORMATION TECHNOLOGY/ ENTERPRISE COMPUTING BACHELOR OF BUSINESS INFORMATION TECHNOLOGY/BACHELOR OF SCIENCE IN INFORMATION TECHNOLOGY REGULAR UNIT CODE: BIT2203 UNIT TITLE: DATA STRUCUTRES AND COMPUTER. ALGORITHMS DATE: TUE 22"? APRIL, 2025 11:00AM MAINEXAM TIME: 2 HOURS INSTRUCTIONS: QUESTION ONE IS COMPULSARY AND ANY OTHER TWO QUESTIONS QUESTION ONE a) Define the term data structures. (2 Marks) b) Differentiate between data abstraction and data types. (4 Marks) ¢) Explain why the study of data structures is important. (6 Marks) d) Define the term Algorithms. : (2 Marks) ¢) Name and explain any two types Graph Algorithms. (4 Marks) 1) Using examples differentiate between linear inequalities and linear equations. (2 Marks) g) Explain the term greedy Algorithm and give two exampies of it.(5 Marks) ce Paper One a Page 1 &h) Differentiate between @-Notation(same order) and O-Notation(upper Bound) in analysis of algorithms. (4 Marks) QUESTION TWO a) Discuss algorithm anelysis and name two interpretation of the upper bound. : (6 Marks) bj Explain the following 3 types of sorting algorithms. (6 Marks) i) Merge sort ii) Quick sort iii) selection sort ©) Explain four functions that found in any greedy algorithm. (8 Marks) QUESTION THREE a) Explain the difference between Kruskal's Algorithm andOPrim's Algorithm. (4 Marks) b) Explain Depth-First Search in algorithms. (4 Marks) ©) Explain four application areas of graph theory. (8 Marks) 4) Define the following terms as used in analysis of algorithms. (4 Marks) i) Buler circuit. ii) Complete Graph. QUESTION FOUR a) Explain the structure Greedy Algorithm. (5 Marks) b) Using an example explain Dijkstra algorithm, ( Marks) ¢} Discuss two main areas of applications for Binary First Search.(6 Marks) d) Study the following algorithm, 1. LookUpAig(A, N, VAL) 2. Step 1: (INITIALIZE) SET POS = - 8. Step 2: (INITIALIZE) SETI = 1 4. Step 3: Repeat Step 4 while I<=N. 5. Step 4: IF A()) = VAL SET POS = 1 SS Paper One Page 2PRINT POS Go to Step 6 (END OF IF) SETI=1+1 (END OF Loop) 6. Step 5: IF POS = -1 PRINT " VALUE IS NOT PRESENTIN THE ARRAY " (END OF IF) 7. Step 6: EXIT State the kind of algorithm and what it is supposed to achieve. (4 Marks) QUESTION FIVE a) Using a real life situation explain how Activity Selection Problem can be useful, use a pseudo code to explain your answer. (7 Marks) b) Explain the difference between forward and back edge in graph algorithm. (4 Marks) ©) Differentiate between a recursive algorithm and recursive procedure. (4 Marks) 4) Using mathematical induction, Prove that n2+2>2n for all positive integer n. (S Marks) | Pape One(TEL, 0706 dot e9e | Mount Kenya A University UNIVERSITY EXAMINATION 2023/2024 SCHOOL OF COMPUTING AND INFORMATICS DEPARTMENT OF INFORMATION TECHNOLOGY/ENTERPRISE COMPUTING BIT/BBIT/BSCCS REGULAR UNIT CODE: BIT2203 UNIT TITLE: DATA STRUCTURES AND ALGORITHMS DATE: FRI 23®° AUG, 2024 8.00AM MAIN EXAM TIME: 2 HOURS INSTRUCTIONS: ANSWER QUESTION ONE AND ANY OTHER TWO QUESTION ONE (30 MARKS) a) Explain the following concepts: i) Data structure (2 Marks) ji) | Double Linked List (2 Marks) iii) | Binary Search Tree (2 Marks) b) Explain two key types of complexities of interest in Performance Analysis of an algorithm. (4 Marks) c) Consider the binary tree given below Perform the following types of the tree traversal: Paper One Page 1(3 Marks) i) Pre-order traversal ia Marke) ii) Post-Order Traversal d) Write the algorithm for: '3 Marks) Jue into the Queue ¢ i) Inserting valu eee) ii) Removing a value from the Queue elp of illustratioris, demonstrate how the queue ADT can be e) With hel implemented using: i) Array (4 Marks) ji) Linked list 4 (4 Marks) QUESTION TWO (20 MARKS), a) Differentiate between dynamic data structures and static data structures. Give examples. (4 Marks) b) Sort the array given below using heap sort algorithm. (6 Marks) 30] 20[6/15/8[3] 4] c) ‘Explain the algorithm for pushing element on the stack. (3 Marks) d) Apart from popping state other three operations of a stack. Give their syntax. (3 Marks) e) Explain two forms of storing data structure in a computer system. (4 Marks) QUESTION THREE (20 MARKS) a) Discuss four the key operations of ADT queue and give the syntax for each operation. (8 Marks) b) State four suitable applications of ADT trees in computing. (4 Marks) c) Given the expression: (8-4/2)+3*4 i) Convert it into postfix expression (3 Marks) ii) Generate a binary expression tree from the expression. (3 Marks) Paper One Page 2 s 2 e & = 3 z 3 s S TEL: 0706 461 292ii ii) Evaluate the results of the expression using the expression tree. (2 Marks) QUESTION FOUR (20 MARKS) a) Explain why stack is regarded as ‘one-ended data structure’. (2 Marks) b) Write sample code to that implements the following stack operations: i) Push operation (4 Marks) ii) Pop operation (4 Marks) ¢) Using illustration, demonstrate how linked list is used to implement ADT stacks. (4 Marks) d) Discuss three limitations of using array in implementing abstract data types. (6 Marks) QUESTION FIVE (20 MARKS) a) In terms of big (O) expression, compare the performance of sequential and binary searches and show how each works. (6 Marks) equ b) Ube the heap sort algorithm, to-sort the-array-given-below. (8 Marks) c) With help of diagram, discuss three types of binary trees. (6 Marks) Paper One Page 362 TARTNE / 8 461 293K University UNIVERSITY EXAMINATION 2022/2023 SCHOOL OF COMPUTING AND INFORMATICS DEPARTMENT OF INFORMATION TECHNOLOGY/ENTERPRISE COMPUTING BSCIS/BBIT/BiT/BED REGULAR UNIT CODE: BiT2203 UNIT TITLE: DATA STRUCTURES AND ALGORITHMS DATE: MON 24" APRIL, 2023 2.00PM MAIN EXAM TIME: 2 HOURS INSTRUCTIONS: ANSWER QUESTION ONE AND ANY OTHER TWO QUESTION ONE a) Define the following terms; (4 Marks) Directed graph Abstract data type (ADT) Pendant iv. Heap b) Discuss any TWO advantages of linked list over linear lst. (4 Marks) ©) Write a C++ statement that checks whether a circular queuie if full or empty (8 Marks) d) Outline any FIVE data structures that are used in Programming, (5 Marks) €) Cite any three areas where trees can be applied in information systems, (3 Marks) Page 1YOUR LEARNING Pg ree TEL: 706 ¢6 299 i i it (3 Marks) 1) Define data encapsulation and identify any its merits. ¢ Pi apeee> g) Define space complexity. Why is it important in analysis of algorithms? (3 Marks) QUESTION TWO a) Define a string ADT (2 Marks) b) Write a C++ program that achieves the following in an array list ADT Implementation. (5 Marks) i) Add anew item at position / ii) Deletes item at position / ©) i) Discuss the operations performed on a heap. (4 Marks) ii) Represent the array below in a binary tree. Perform a heap sort on it (5 Marks) [70 (1) | 60 (2) | 12 3) | 40 (4) | 30 6)/8 © | 10 d) Write a C++ code section for merge sort algorithm. (4 Marks) QUESTION THREE a) i) Define a stack ADT (2 Marks) ji) Compare sequential search with binary search (2 Marks) b) Show how the following items; 40 50 30 can be implemented on a Stack ADT that uses en array (2 Marks) Paper One et es ee Page 29) Trace the behavior of the following operation on the ADT in (b) above: PUSH (70) PUSH (80) PUSH (90) POP () PUSH (77) POP () (3 Marks) d) Give all orders of traversal for following binary tree (6 Marks) ie 7» @) Write a pseudo code for a binary search tree. Assume the array is already sorted, (5 Marks) QUESTION FOUR 2) Given the equation in infix (A+B)*C, A+B*C and A-B4+C formulate the equivalent pre fix and post fix notation (6 Marks) Pp) Mrite a C++ code to implement the POP and PUSH functions of stack ADT (6 Marks) ¢) Define a binary search tree and outline four of its properties. (4 Marks) d) Write an algorithm for performing a sequential search. (4 Marks)DANFAM Cons TIONS) YOUR LEARRING ol TEL: G70 26+ 25) QUESTION FIVE : i - b) Given t!.e graph below find the shortest path using Dijkstras algorithm (7 Marks) ©) Explain any four desirable traits of a good algorithm. (4 Marks) d) Given the tree below perform a down-heap followed by up-heap of value 10 (6 Marks) e) Define the following term in relation to trees using examples i. Siblings (3 Marks) ii. Depth iii, Leaf Paper One Page 4y [= LEARNING ParTugR —~TEL.0706.461.292 Mount ixenya Mi ' University UNIVERSITY EXAMINATION 2019/2020 SCHOOL OF COMPUTING AND INFORMATICS DEPARTMENT OF INFORMATION TECHNOLOGY BACHELOR OF SCIENCE IN INFORMATION TECHNOLOGY/ BACHELOR OF BISINESS INFORMATION TECHNOLOGY REGULAR UNIT CODE: BIT2203 UNIT TITLE: DATA STRUCTURES AND ALGORITHMS ‘TUES 17™ DECEMBER, 2019 8:00AM MAIN EXAM ‘TIME:2 HOURS INSTRUCTIONS: ANSWER QUESTION ONE AND ANY OTHER TWO QUESTIONS Question 1 (30marks) a) Define the term. algorithm (2 Marks) b) Outline four characteristics of a good algorithm. (4 Marks) ©) Explain the function of the following ADT primitives. Write the relevant syntax. (2 Marks) (2 Marks) (2 Marks) iii) IndexOf() d) One of the applications of stacks in computing is to evaluste postfix expression. From the given expression 5+4*6-3 i) Convert the expression into postfix expression, (2 Marks) Paper One Page 1[_rexsaragaan 84 ii) Using stack ADT, show how the expression will be evaluated. (4 Marks) e) A queue is implemented using ADT list to presents its items. Discuss the efricletey of the queue insertion and deletion operations when the ADT list implementation is: i) Array based. ii) Pointer based. (6 Marks) ) Outline four possible application of ADT Queue in computing. (4 Marks) 9) In context of arrays, explain the term index. Show an example. (2 Marks) Question 2 (20marks) a) Using examples differentiate between a binary tree and general tree. (4 Marks). °* b) Write a two dimensional array to explain the concept of row major order. (6 Marks) ° Explain two types of complexities of study in data structures, (4 Marks) aaah d) Give the algebraic expression: (a-b/c)+d*e. i. Convert it into postfix expression. (8 Marks) ii, Generate a binary tree from the expression, (3 Marks) Question 3 (20marks) ' @) Give three reasons why you would choose linked list over array. (3 Marks) b) Name and explain three input cases and the effect on running time of an algorithm. (3 Marks) eS : = Paper One Page 2"YOUR LEARNING PARTNER 1706.46) 292. ©) Describe the concept and motivation of circular QUEUE. Use illustration. (5 Marks) d) In terms of computational complexity, using big 0, Explain the cost of i) Inserting element at the end of array list (3 Marks) il) Inserting elementat end linked list (3 Marks) e) Write down the algorithms for inserting a new element into stack, (3 Marks) Question 4 (20marks) a) Define the term “Algorithm analysis". Explain two important quantitative metrics of interest in algorithm analysis. (4 Marks) b) Sort the array given below using INSERTION sort algorithm. (6 Marks) 30 20 6 [is sys 4 ©) _ Explain three characteristics of ADT Linked list. (6 Marks) d) Using illustrative diagram, show how a new element is added in-between other elements in linked list (4 Marks) Question 5 (20marks) a) Explain two data types used to implement ADTs. (4 Marks) b) Perform Pre-Order, In-order and Post-Order traversal on the following tree. (6 Marks)| DANFAM COMMUNICATIONS D YOUR LEARNING PARTNER TEL-0706.461 202 fe] z K ¢ \ M ; als ole ¢) Discuss five benefits of studying data structures and algorithms by software developers. (10 Marks)HO PANEER: y [res 0706 464299 | Mount Kenya A University UNIVERSITY EXAMINATION 2023/2024 SCHOOL OF COMPUTING AND INFORMATICS DEPARTMENT OF INFORMATION TECHNOLOGY/COMPUTING ENTERPRISE BBIT/BSCIT/BIS/BSS/BSCAS REGULAR UNIT CODE: BIT2203 UNIT TITLE: DATA STRUCTURES AND ALGORITHMS DATE: MON 4TH DEC, 2023 _ 2.00PM MAIN EXAM TIME: 2 HOURS INSTRUCTIONS: ANSWER QUESTION ONE AND ANY OTHER TWO QUESTIONS QUESTION ONE (30 MARKS) a) Distinguish between primitive data type and abstract data type. Give Examples. (4 Marks) b) Giving examples, describe recursion. (4 Marks) «) Give an algorithm for concatenating two strings STRING_A and STRING_B (4 Marks) d) Give three reasons why you would choose linked list over array. (3 Marks) ) Name and explain three input cases and the effect on running time of an algorithm. : (3 Marks) f) Describe the concept and motivation of circular QUEUE. Use illustration. ( Marks) 9) Using an Example, demonstrate how quick sort works. (7 Marks) 5 SRE SS SESS Paper One ) Page 1 Di (vanyy gill Arlont cy “| your [0 PARTRER) Ti QUESTION TWO (20 MARKS) : 2 a) What data structures are used to perform recursion? 6 Marks) ~ (5 Marks) b) What is a heap? Use Example. c) Explain the differences between ARRAY and STACK. (6 Marks) d) List four applications of STACK data structure. (4 Marks) QUESTION THREE (20 MARKS) a) Using illustration, demonstrate how dequeue could be represented by Doubly linked list. (6 Marks) b) Using the array given below, create a binary tree. (5 Marks) 12°«7 5 8 3 W 9 13°°4 2 ©) From the binary tree created above in Q3 (b), perform pre-order, in- order and post order tree traversal. (9 Marks) QUESTION FOUR (20 MARKS) a) Make a comparison between array and pointer based implementation of ADT stack. (6 Marks) Array b) Write down the algorithms for the following stack operations: i) Insert a new element into stack. (4 Marks) ii) Remove an element from the stack (4 Marks) ©) Make a comparison between sequential and binary search algorithms. (6 Marks) QUESTION FIVE (20 MARKS) a) Explain two data types used to implement ADTs. (4 Marks) b) Describe four applications of data structures in computing. (4 Marks) ©) In terms of computational complexity, using big 0, Explain the cost of: (6 Marks) i) Inserting element at the end of array list ii) Inserting element at end linked list ili) Deleting element in front of a list. RE Paper One Page 2