La Trobe University, Bendigo

FINAL EXAMINATION JUNE 2003

BITDST Data Structures

Examiner:  Mary Martin                                                                                                               Time Allowed: 3 hours         _____________________________________________________________________

Instructions to Candidates:

1.               Answer all questions.

2.               Figures to the right indicate marks.

3.               Make suitable assumptions where necessary.

4.               Clearly state any assumptions made.


 Question 1.

All parts of this question refer to Java  code below.  

import java.io.*;
import java.util.*;
/** Class EmployeeDetails: an employee description
 ** Date written: 2003-02-20
 ** @author Mild Mal <br>
 ** modified Milder Mary
 ** @version 2 created , 2003-09-21
 **/
public class EmployeeDetails {
    private String lName,fName, division, eNumber;
      //constructors
      EmployeeDetails(){}      
      EmployeeDetails(String lName,String fName,String division,String eNumber){
         this.lName = lName;
         this.fName = fName;
         this.division = division;
         this.eNumber = eNumber;
      }
      //get (accessor) methods
      public String getName(){
         return lName+Ó, Ň +fName;
      }
      public String getNumber(){
         return eNumber;
      }
      public static EmployeeDetails createEmployee (String aLine)
         String lName, fName, division, eNumber;
         StringTokenizer tokens;
         EmployeeDetails anEmployee = null;
         if(aLine != null){
            tokens  = new StringTokenizer(aLine, ",");
            if (tokens.countTokens()==4){
               lName = tokens.nextToken();
               fName = tokens.nextToken();
               division = tokens.nextToken();
               eNumber = tokens.nextToken();
               anEmployee = new EmployeeDetails(lName, fName, division, eNumber);
            }else
              System.out.println("Incorrect number of details!!!!!!!");
         }else
            System.out.println("Data in incorrect Format!!!!!!!");
         return anEmployee;
      }
      public String toString(){
         return (fName + " "+lName+"\t"+division+"\t"+eNumber);
      }
      public static void main(String[] argv){
         EmployeeDetails anEmployee = new EmployeeDetails("bok","joe","IT","5432");
         System.out.println(anEmployee);
      }
 }

                 

  1. Explain the purpose of the statement:
    import java.io.*;
    import java.util.*;
  2. In the statement: this.fName = fName;
    Why is identifier thisnecessary ?
  3. What does the keyword  or modifier static  mean?
  4. Explain the effect of the keywords  public and  private.
  5. Explain what happens when the following statement  is executed:
    anEmployee = EmployeeDetails.createEmployee("luk,lucy,IT,7654");
  6. Assuming correct coding give the output you would expect from running the executable code generated  from compiling this class and identify the methods which are executed.
  7. Identify and briefly describe the two types of commenting found in the code. 
  8. What is the purpose of the parameter  String[] argv  in the main method?
     

( 2 + 2 + 2 + 2 + 4 + 4 + 2 + 2 = 20 marks)

Question 2.

  1. Draw diagrams to show the linear list structures which could be created when using objects of the following classes to store each item in a list:

    public class NodeType1{   
        double data;   
        NodeType1 next;
   
        NodeType1(double d){      
      data = d;
        }
    }

public class NodeType2{  
    double data;   
    NodeType2 next;   
    NodeType2 prev; 
  
    NodeType2(double d){      
       data = d;   
    }
}
  2. The class NodeType2 has one more instance variable (prev) than class NodeType1. What is the advantage in having this extra instance variable? Identify the type of linked list which can be created with NodeType2.
  3. Most lists created using class NodeType2 have a "dummy" node as the first node in the list. Why is it a good idea to have this dummy node?
  4. Using pseudocode or Java write a method to print the contents of a list created with class NodeType1. The method is passed a parameter of NodeType1.
  5. Two abstractions of the linear list data structure which you studied this semester were the stack and the queue
    1. Briefly define each abstraction by describing the basic operations of each, giving an example of when the abstraction might be used.
    2. Both abstractions can be represented in arrays as well as linked lists.  Briefly compare the two representations giving the advantages and disadvantages of each.

 

 

 

(2 + 3  + 2 + 3 + (6 + 4) = 20 marks)

Question 3.

 

  1. Using java or pseudocode write a program that will read in a list of numbers from standard input and then print them out in reverse order. You must use a recursive method to solve this problem.
  2. Using the quicksort algorithm that you studied in the semester, sort the following data showing the state of the list after each call of the partition module.

10    50   20   30   65   5   60   15    55    35

 (5 + 5 = 10 marks)


 Question 4.

The data items listed below are to be used to answer the following parts to this question:

                  24     10     15     21     27     11     13     44     29

  1. Create a binary search tree for the data items drawing a diagram to show the final tree after all items have been inserted.
  2. Write the contents of the tree using:
  3. Create an AVL tree for the data items using diagrams to show the structure of the tree before and after a data item is inserted which requires a single or double rotation.
  4. Create a heap data structure for the data items by drawing the initial binary tree and showing the state of the tree after each level has been inspected.
  5.  The heap is a data structure which is suitable for physical representation in an array. Why?
  6. Name two common applications of the heap data structure.

(2 + 5 + 5 + 5 + 1 + 2 = 20  marks)

Question 5.
 

For the binary search tree given below:


     

Using diagrams and text description, show each step which must be taken, and the final tree for the following deletions  (NB: start with the original tree for each deletion):

                  i)          delete node   S

                  ii)         delete node   G        

                  iii)        delete node   N

 (3 + 3 + 4 = 10 marks)

Question 6.

  1. Using Java or pseudocode develop a class called StudentRec to represent a student by listing the data (instance variables) required to represent the student and the methods it must have to provide access to the data. The student's details to be stored are: student name, student number, home town  and URL of the studentŐs image. (For each instance variable and method make sure you include the proposed name, datatype and a short description of its purpose.)

  2. The university wishes to maintain a student database which will provide:

    The student details are stored in a text file which is read by the program when it starts and written when the program exits. The user interface to the program is graphical (GUI).

    Using the Object-Oriented Approach, carry out an initial analysis and identify the major objects necessary for the application to be developed. For each object you identify, suggest a name and give a short description of its purpose. 

    ( 5 + 5 = 10 marks)