Ics 2105: Data Structures And Algorithms Question Paper
Ics 2105: Data Structures And Algorithms
Course:Bachelor Of Science In Computer Science
Institution: Meru University Of Science And Technology question papers
Exam Year:2013
University Examinations 2012/2013
FIRST YEAR, SECOND SEMESTER EXAMINATION FOR THE DEGREE OF BACHELOR OF
SCIENCE IN COMPUTER SCIENCE
AND
FIRST YEAR, SECOND SEMESTER EXAMINATION FOR THE DEGREE OF BACHELOR OF
SCIENCE IN MATHEMATICS AND COMPUTER SCIENCE
ICS 2105: DATA STRUCTURES AND ALGORITHMS
DATE: APRIL 2013 TIME: 2 HOURS
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.
i. Data item (2 Marks)
ii. Data object (2 Marks)
iii. Data abstraction (2 Marks)
iv. Abstract data type (2 Marks)
v. Data structure (2 Marks)
b. With the help of an appropriate example describe the logical concept and physical implementation of a data type, in such a way as to illustrate their difference. (6 Marks)
c. Data structures may be linear, non-linear, static and dynamic.
i. Describe these categories of data structures. (8 Marks)
ii. Give an example of a data structure in each category. (4 Marks)
d. Distinguish between a weighted graph and un weighted graph. (2 Marks)
QUESTION TWO – 20 MARKS
a. With the help of an appropriate example, describe the burble sort algorithm. (10 Marks)
b. Define the queue ADT and describe the two basic operations on a queue. (6 Marks)
c. Lists may be implemented as linked lists or array lists. Give two differences between these two implementations. (4 Marks)
QUESTION THREE – 20 MARKS
a. Briefly describe the following concepts as used with tree data structures.
i. Root node (2 Marks)
ii. Leaf node (2 Marks)
iii. Order of a tree (2 Marks)
iv. Depth of a tree (2 Marks)
v. Descendant (2 Marks)
b. Define an adjacency matrix and describe how it is used to represent a graph ADT. Use an appropriate example to illustrate your answer. (6 Marks)
c. Briefly describe two area of application of the stack ADT. (4 Marks)
QUESTION FOUR – 20 MARKS
a. Every data type has specification and an implementation
i. State and briefly describe the three elements of data type specification (6 Marks)
ii. State and briefly describe the two elements of data type implementation. (4 Marks)
b. Using an appropriate illustration and code segment, describe how you would insert a new node at the end of a linked list. (10 Marks)
QUESTION FIVE – 20 MARKS
a. Briefly describe the following data structures giving one area where each is applied: (12 Marks)
i. Huffman tree
ii. Binary search tree
iii. Red black tree
iv. Hash tables
b. Using the following values 32, 14, 5, 23, 17, 10 30 construct a binary search tree. (6 Marks)
c. Distinguish between a compound data type and a simple data type. (2 Marks
More Question Papers