Get premium membership and access revision papers, questions with answers as well as video lessons.
Ics2115:Data Structures Question Paper
Ics2115:Data Structures
Course:Computer Technology
Institution: Meru University Of Science And Technology question papers
Exam Year:2012
INSTRUCTIONS: Answer Question one and any other two questions.
QUESTION ONE – (30 MARKS)
a) Define the following terms: (8 marks)
i) Abstract data type
ii) Data object
iii) Algorithm complexity
iv) Abstraction
b) Briefly describe the following data structures: (4 marks)
i) Huffman tree
ii) Weighted graph
c) Consider the binary tree below
Insert the values 5,23,7,2,10,16,13 in the tree using:
2
i) Pre-order traversal (4 marks)
ii) Post-order traversal (4 marks)
d) Briefly describe two areas of application of the stack ADT (4 marks)
e) A queue can be implemented as either an array or a linked list. In the
linked list implementation, it is not necessary to check whether the queue
is full, whereas this is essential in the array implementation. Briefly
explain why this is the case. (4 marks)
f) Distinguish between directed graph and undirected graph (2 marks)
g) With respect to a tree data structure, define the following terms (4 marks)
i) Complete tree
ii) Order of a tree
QUESTION TWO (20 MARKS)
a) Briefly describe the two basic operations on a queue ADT (4 marks)
b) Consider the numbers 23, 5, 91, 17, 12, 78, 13, 4, 7, 18. Describe the
bubble sort procedure by sorting the numbers, showing the resulting list
in each step. (10 marks)
c) Consider two algorithms one having a complexity of order Olog(n) and
the other having an complexity of order On2. Which of the two
algorithms is more efficient and why? (4 marks)
d) State the two types of algorithm complexity. (2 marks)
QUESTION THREE (20 MARKS)
a) Define a linked list ADT (2 marks)
b) Give two differences between a linked list and an array (4 marks)
c) With the help of a relevant illustration, describe the steps you would take
to delete the last node from a linked list. (4 marks)
d) What is a hash function, and how is it used in sorting data? (4 marks)
e) Briefly describe the two basic operations a queue ADT (4 marks)
f) State two applications of a tree data structure (2 marks)
QUESTION FOUR (20 MARKS)
a) Recursion is a very powerful technique for implementing algorithms, as
an alternative to iterative operation (loops).
i) What is recursion? (2 marks)
3
ii) State the three conditions that a problem must meet for it to be
solvable by recursion. (3 marks)
iii) Using the binary search as an example, describe the recursive and
stopping cases of a recursive procedure. (4 marks)
b) Briefly outline the algorithm for an insertion sort implementation. (7 marks)
c) You wish to implement a patient scheduling system for a hospital. State
the data structure you would use and explain why. (4 marks)
More Question Papers
Popular Exams
Return to Question Papers