NATIONAL OPEN UNIVERSITY OF NIGERIA

UNIVERSITY VILLAGE, PLOT 91, CASDASTRAL ZONE, NNAMDI AZIKIWE EXPRESS WAY, JABI, ABUJA.
FACULTY OF SCIENCES
MARCH/APRIL 2016 EXAMINATION

COURSE CODE:                                                         CIT 341                                                         

COURSE TITLE:                                                        Data Structures

DURATION:                                                               3 Hours

INSTRUCTIONS:                                                       Answer any Five (5) Questions out of seven

 Q1a.   Briefly explain the difference between linear and non-linear data structures.

 Q1b.   Write a brief note on each of the following:

            i.          List

            ii.         Array

 Q1c.    Distinguish between a stack and a queue making sure to illustrate your answer.

Q2a.     Consider the following operations carried out on a queue Q. provide the content of the

queue and the returned value, after each operation, to complete the table.

Q2b.    Using a simple example explain the process of storing a queue in a dynamic data structure illustrating how a node can be added and removed.

Q2c.     Explain briefly two modes of stack storage.

Q3a.     Explain clearly what a hash function is.

Q3b.    Write down three characteristics of a good hash function.

Q3c.     Briefly describe what a hash table is giving an example of its application.

Q4a.     Briefly describe the mathematical definition of a tree giving its salient properties.

Q4b.    Explain the recursive nature of the definition of a tree.

Q4c.     Using an example describe the inverted pictorial representation of a tree.

Q5a.     Briefly describe what a search tree is listing its main properties.

Q5b.    Concisely define what a perfect binary tree is.

Q5c.     Using the simple tree shown in the figure below as an example, describe the following traversal methods.

            i.          Preorder

            ii.         In order

            iii.        Postorder

Q6a.     Briefly explain the concept of garbage accumulation in a Java Programme

Q6b.    Write short notes on the following garbage collection techniques.

            i.          Reference Counting

            ii.         Mark-and-Sweep

Q6c.     Briefly describe four Memory Allocation methods.

Q7a.     Explain clearly what greedy algorithm is.

Q7b.    Describe four functions of greedy algorithm

Q7c.     Briefly describe the three phases of the divide-and-conquer paradigm.