Ics2115:Data Structures Question Paper
Ics2115:Data Structures
Course:Computer Technology
Institution: Meru University Of Science And Technology question papers
Exam Year:2010
INSTRUCTIONS: Answer question one and any other two questions
QUESTION ONE – 30 MARKS
a. Define the following terms as used with data structures and algorithms: (10 Marks)
i. Data item
ii. Data object
iii. Data type
iv. Algorithm
v. Data structure
b. Data structures may be classified as linear, non-linear, static or dynamic. Briefly describe each of these
categories giving an example in each case: (8 Marks)
c. Distinguish between the following: (4 Marks)
i. Complete tree and balanced tree
ii. Weighted graph and ordered graph
d. Outline one area of application of the stack ADT, within a computer system and explain why the stack is
the most appropriate structure for the application. (4 Marks)
e. Briefly describe the merge sort algorithm. (4 Marks)
2
QUESTION TWO – 20 MARKS
a. Data abstraction is an important concept in the implementation of data structures.
i. What is data abstraction? (2 Marks)
ii. Describe the role it plays in the implementation of abstract data types (2 Marks)
b. Briefly describe the following graph concepts. (8 Marks)
i. Vertex
ii. Edge
iii. Traversal
iv. Weight
c. Using an appropriate example to illustrate describe the binary search tree and how it is applied in the
implementation of search algorithms. (8 Marks)
QUESTION THREE – 20 MARKS
a. Queues are special types of lists.
i. Define a queue ADT (2 Marks)
ii. State and briefly describe the two basic operations on a queue ADT. (4 Marks)
b. With the help of an appropriate illustration, describe the process of deleting the last node in a linked list.
(6 Marks)
c. The stack ADT may be implemented as an array list or a linked list:
i. Briefly describe these two implementations (4 Marks)
ii. Give two differences between the two implementations. (4 Marks)
QUESTION FOUR – 20 MARKS
a. Every data structure has a logical view and an implementation. With respect to a two dimension array,
describe this concept. (4 Marks)
b. Define tree traversal and briefly describe five techniques used in tree traversal. (12 Marks)
c. Describe the application of the graph ADT in the following sectors. (4 Marks)
i. Information systems
ii. Transport
QUESTION FIVE – 20 MARKS
a. State and briefly describe three search algorithms. (6 Marks)
b. Arrays are regarded both as data type and data structures. (4 Marks)
i. With respect to these two concepts, describe an array (4 Marks)
ii. With respect to an array, briefly describe the three basic elements of data type specification
(6 Marks)
c. Define recursion and state three conditions necessary for a problem to be solvable by recursion.
(4 Marks)
More Question Papers