NATIONAL OPEN UNIVERSITY OF NIGERIA

UNIVERSITY VILLAGE, PLOT 91, CASDASTRAL ZONE, NNAMDI AZIKIWE EXPRESS WAY, JABI, ABUJA.
FACULTY OF SCIENCES
MAY/JUNE 2012 EXAMINATION

COURSE CODE:                                                         CIT341                                                          

COURSE TITLE:                                                        Data Structures

DURATION:                                                               3 Hours

INSTRUCTIONS:                                                       Answer any Five (5) Questions

Q1.a     Explain the notion of ‘Interface’ within the context of Java programming language       (6 marks)

      b.   List the basic components of a ‘Statement’.                                                                        (3 marks)

      c.    State the main goal of the sorting algorithm.                                                                      (5 marks)

      d.   State the hash function for a set of keys, K and a positive constant, M.                                      (6 marks)

Q2a.     State three (3) reasons for suballocations.                                                                         (9 marks)

     b.    What are the characteristics of a good hash function?                                                     (3 marks)

     c.     Give a brief description of the following:

                        (i)        Fragmentation                       (ii)       Best Fit                                      (4 marks each)   

Q3a.     Write a program in Java to declare an integer named day of the week, whose value is the program should display the name of the day of the week using the Switch statement.                                                                                                                  (15 marks) 

     b.    State the principal of optimality.                                                                                          (5 marks)  

Q4.a     Draw the queue data structure showing the insertion and deletion.                             (10 marks)

      b.   State the function of the following primitive operation:

                        (i)        Add                 (ii)       Set                   (iii)      Remove

                        (iv)      Get                  (v)       IndexOf                                                               (2 marks each)                 

Q5.a     List any two (2) reference types.                                                                                         (4 marks)

      b.   Distinguish between public and private modifiers.                                                            (4 marks)

      c.    Give a brief definition of these terms:

                        (i)        Parameters                (ii)       Fields              (iii) Local variables       (4 marks each)

Q6.a     Name and describe two basic operations of a stack.                                                       (16 marks)

      b.   Determine the linear expression of DIMY (6, 10)                                                                         (4 marks)  

Q7.a     State four main steps involved in Dynamic programming design.                                  (10 marks)

     b.    What is the transpose of the following digraph G = (V, E)?                                              (4 marks)

     c.     Specify the effect of the following operation on a stack:

(i)        IsEmpty                      (ii)       IsFull               (iii) Initialise                             (6marks)