Get premium membership and access revision papers, questions with answers as well as video lessons.
Ics 2105: Data Structures And Algorithms Question Paper
Ics 2105: Data Structures And Algorithms
Course:Bachelor Of Science In Computer Science
Institution: Dedan Kimathi University Of Technology question papers
Exam Year:2013
1 | P a g e
DEDAN KIMATHI UNIVERSITY OF TECHNOLOGY
University Examinations 2012/2013
FIRST YEAR SUPPLEMENTARY/SPECIAL EXAMINATION FOR THE DEGREE OF BACHELOR OF SCIENCE IN COMPUTER SCIENCE
ICS 2105: DATA STRUCTURES AND ALGORITHMS
DATE: 2ND JULY 2013 TIME: 11.00AM-1.00PM
Question 1 (30 marks)
a) Define the following terms
i. Data structures.
ii. ADTs
iii. Algorithms
(6 marks)
b) Consider the following eight numbers 50, 33, 44, 22, 77, 35, 60 and 40. Display the construction of the binary by inserting the above numbers in the given order (4 marks)
c) Draw the expression tree of the following infix expression. Convert it in to Prefix and Postfix expressions.
((a + b)+ c * (d + e)+ f )* (g + h) (6 marks)
d) Outline algorithm of inserting an element say X into a an array. (6 marks)
e) Explain the function “Is Empty” in a stack.(2 marks)
.
f) Write pseudo code for ‘push’ and ‘pop’ operations of a stack (6 marks)
2 | P a g e
Question 2(20 marks)
a) Define the following terms as used in digraphs using an appropriate example. (6 marks)
i) Reachable
ii) Path
iii) Acyclic graph
b) Provide the algorithm to execute the enqueue operation implementation of the Queue ADT: Enqueue (x). (6 marks)
c) What is quick sort? Sort the following array using quick sort method. (5 marks)
24 56 47 35 10 90 82 31
Question 3(20 marks)
a) Write an algorithm to delete a node in a circular queue. (4 marks)
b) Explain three ways in which insertions can take place in a linked list. (6 marks)
c) Explain any two reasons why an IT student needs to learn data structures (2 marks)
d) Write an algorithm for searching a key from a sorted list using binary search technique.
(8 marks)
Question 4
a) Using array to implement the queue structure, write an algorithm/program to (6 marks)
b) Define the minimal spanning tree. . (4 marks)
c) Explain how the djikstra algorithm works. (4 marks)
d) Traverse the given tree using Inorder, Preorder and Postorder traversals(6 marks)
3 | P a g e
Question 5(20 marks)
a) Discuss factors considered while analyzing performance of an algorithm. Differentiate between lower and upper bound of an algorithm. Give an example in each case. The factors considered are time and memory, but mostly time. (4 marks)
b) With the aid of an algorithm explain how push() and pop() functions work in stack
(8 marks)
c) Find the location of the following elements given the hush function H(i)=(3i+3)mod 7.
[14, 46, 17, 91, 18, 5, 23, 6]. Draw the table. (8 marks)
More Question Papers
Popular Exams
Return to Question Papers