CSC115 F01

Midterm Exam 3 (duration: 50 minutes)

November 25, 2002

 

Student ID Number______________________________

 

 

Student Name__________________________________

 


Signature__________________________________

 

Instructions:

This exam is a closed book, no notes, no calculator exam.  This midterm is worth 15% of your final grade for this course, but will be marked out of 100 marks.  There are 7 questions in total.  Point form for the “short answer” questions is acceptable.

 

For all questions write your answers on the exam and hand in all pages of the exam.

There should be 8 pages including this page, please check you have all pages before you begin.  If you use the back of the pages for your answers, make sure you indicate on the front side.

 

Please write your student number and name at the top of this page, and sign in the space provided.

 

 

Note:  You may not leave during the last 15 minutes of the exam. 

Good luck!

 

 

Question 1

/15

Question 2

/16

Question 3

/16

Question 4

/11

Question 5

/12

Question 6

/18

Question 7

/12

Bonus!

/5

Total:

/100

1.      Multiple choice question, circle the correct answer

(Total of 15 marks)

 

         i.      Which of the following is not typically a method supplied by a priority queue interface:  (3 marks)

a.       insert(object)

b.      find(object)

c.       size()

d.      isEmpty()

e.       deleteMin()


       ii.      The running time of a sorting algorithm implemented using a Heap is: (4 marks)

a.       O(n)

b.      O(log n)

c.       O(n2)

d.      None of the above.         O(nlogn)


      iii.      The running time of a deleteMin operation of a priority queue implemented as a Heap is:  (4 marks)

a.       O(1)

b.      O(n)

c.       O(log n)

d.      None of the above.


     iv.      Given the following piece of code, what will the output of f(3) be:  (4 marks)

public static int f(int n) {

   if (n==0)  return 1;

   else if (n==1) return 1;

   else return f(n-2)+f(n-1);

}

 

public static void main ( String[] args ) {    

      for (int i = 0; i <= 3; i++)

            System.out.println(f(i));    

}

a.       1, 1, 1, 1, 1, 1, 1, 1, 1, …….

b.      1, 2, 3

c.       3, 2, 1

d.      1, 1, 3, 2

e.       1, 1, 2, 3

f.        3, 2, 1, 1

 

 

2.  Priority Queues  (16 marks)

 

The following is an incomplete implementation of a sorting algorithm using a Priority Queue data structure.  Fill in the missing pieces of code in the boxes below:

 

void pqSort(Integer a[]) {

   SomePQ pq = new SomePQ();

   for (int k=0; k<a.length; k++) {

pq.insert(a[k]);

 
 
  
   } // for

   k = 0;

   while ( !pq.empty()                ){

      a[k] = pq.deleteMin();

      k++;

 
 
 
  
   } // while

} // pqSort
3.  Heap operations (16 marks)

For the following queue, which is implemented as a heap as shown, show graphically what happens when you try to insert a new element with value 1 (i.e.

draw trees to show each step of the algorithm).

Step 0                                                 


 

 



       Step 1 (Insert 1 in next node)                      Step 2 Swap 1 and 6                          

 


     Step 3  Swap 1 and 3                           Step 4  Swap 1 and 2

                                   

 

 

 

 

4.       Hash functions (11 marks)

The following pseudocode shows a hash function for mapping strings to hash buckets. 

 

Let s be a key of type String and

hashCode be the ordinal value of the first character of s and

N be the hashtable size where N is a prime number > =13

k = hashcode % N

 

a.       Why is this not a very good hash function?    (5 marks)

All words starting with the same letter will hash to the same entry… and lots of words in the English language start with the same letter!









b.       Describe how you could improve this hashing function: (6 marks)

 

 

 

Let hashCode be the sum of the ordinal values of the characters of s … this is sufficient for full marks…..



 

 

5.   Hash Tables  (12 marks)

Using the hash function that we provided in the last question (i.e. do not use your improved solution), show how you would enter the following key “qed” into the following hash table using the quadratic collision scheme.

 

Assume the ordinal value of “a” is 1, “b” is 2, … etc.

 

(Hints:  If you don’t understand the hash function in question 4, then provide a description of the quadratic collision scheme for part marks).

 

 

 


0

Deleted

  1

Empty

2

Deleted

3

Deleted

4

“qpr”

5

“rps”

6

“sed”

7

Empty

8

“has”

9

“ism”

10

Deleted

11

Empty

12

Empty

 

6. Recursion and Iteration (18 marks)

Provide code for two versions of a method which takes as a parameter a string, and returns that string in reverse.   One method must use recursion, while the other must use iteration.   Hint some useful string operations are:  length(); charAt(int); substring(i,j).

 

Iterative solution:  (8 marks)

 

public static String ireverse(String s) {
 

    String tmp = "";

    for (int i = (s.length()-1); i>=0; i--) {

      tmp = tmp + s.charAt(i);

    }

    return tmp;



 

 

 

}



Recursive solution:  (10 marks)

public static String rreverse(String s) {

    int len = s.length();  

    if (len <= 1) {

          return s;

    }

    else {

      char lastChar = s.charAt(len-1);

      String remainder = s.substring(0, len-1);

      return lastChar + rreverse(remainder);

    }

 

 

 

}

 

 

 

 

7.  Swing and listeners.  (12 marks)             

Provide the code to add a listener to a button which will result in the button’s background colour changing from white to blue when it is pressed for the first time.  Some of the required code is given below, fill in the blank box.  (Hints:  Javadoc for some of the relevant Java library can be found on the next page and if you can’t remember the exact syntax, provide pseudocode for part marks.)

 

import javax.swing.*;

import java.awt.*;

import java.awt.event.*;

 

public class MyButton extends JFrame {

 

  JButton b1 = new JButton("Hello World");

 

  public MyButton () {

     

   
// anonymous inner class

    ActionListener al = new ActionListener () {

      public void actionPerformed(ActionEvent e){

           ((JButton)e.getSource()).setBackground(Color.blue);

       }

    };

 

    b1.addActionListener(al);

   

 

 

 

 

 

 

b1.setBackground(Color.white);

    Container cp = getContentPane();

    cp.add(b1);  

  }

 

  public static void main(String[] args) {

        JFrame frame = new MyButton();

        frame.pack();

        frame.setVisible(true);

  }

}

 

 

Bonus Question (5 marks): 
List two topics that you would like covered in the review sessions next week.

 

 

 

Question 7 hints:

 

From the Javadoc for Jbutton:

 

Methods inherited from class javax.swing.AbstractButton

addActionListener, addChangeListener, addItemListener, checkHorizontalKey, checkVerticalKey, createActionListener, createActionPropertyChangeListener, createChangeListener, createItemListener, doClick, doClick, fireActionPerformed, fireItemStateChanged, fireStateChanged, getAction, getActionCommand, getActionListeners, getChangeListeners, getDisabledIcon, getDisabledSelectedIcon, getDisplayedMnemonicIndex, getHorizontalAlignment, getHorizontalTextPosition, getIcon, getIconTextGap, getItemListeners, getLabel, getMargin, getMnemonic, getModel, getMultiClickThreshhold, getPressedIcon, getRolloverIcon, getRolloverSelectedIcon, getSelectedIcon, getSelectedObjects, getText, getUI, getVerticalAlignment, getVerticalTextPosition, imageUpdate, init, isBorderPainted, isContentAreaFilled, isFocusPainted, isRolloverEnabled, isSelected, paintBorder, removeActionListener, removeChangeListener, removeItemListener, setAction, setActionCommand, setBorderPainted, setContentAreaFilled, setDisabledIcon, setDisabledSelectedIcon, setDisplayedMnemonicIndex, setEnabled, setFocusPainted, setHorizontalAlignment, setHorizontalTextPosition, setIcon, setIconTextGap, setLabel, setMargin, setMnemonic, setMnemonic, setModel, setMultiClickThreshhold, setPressedIcon, setRolloverEnabled, setRolloverIcon, setRolloverSelectedIcon, setSelected, setSelectedIcon, setText, setUI, setVerticalAlignment, setVerticalTextPosition

 

 

 

From the JavaDoc of the ActionListener interface….

 

Method Summary

 void

actionPerformed(ActionEvent e)

 

-END-