15-100 Sections U-V-AA / Spring 2009 / Midterm Exam #2
Exam Date: Thu 30-Apr-2009
4 Parts (25 points each) / 80 Minutes
Note: Unicode
'A' is 65,
'a' is 97, and '0' is 48.
Part I: Short Answers
1.
If a given
implementation of insertionsort takes 3 seconds to sort 10,000 random integers,
how long would you expect the same program on the same computer to sort 50,000
random integers? Show your work.
2.
List one sort algorithm that we have studied that requires a temporary
array of the same size as the array being sorted:
3. Bubblesort is most like which of these other sorts (circle one):
insertionsort selectionsort mergesort
4. Given
the array { 0, 3, 5, 6, 11, 12, 13, 15 }, list the values (not the indexes!), in order, that
binary search would check in order to confirm that the value 14 does not occur in
the array.
5. Sort the
array { 5, 3, 8, 2 } by mergesort. Just list the array after each entire pass.
6. Sort the
array { 5, 3, 8, 2 } by selectionsort. Just list the array after each
swap.
7. In an event-based program, event-handling methods like keyPressed or
mousePressed do not directly call the paint method. Instead, in just two
or three words, how do they tell the paint method what to paint?
8. Write one line of code that paints a circle of radius 10 centered at 50, 100.
Assume "page" is initialized for you.
9. Write one line of code that prints "true" if the already-initialized
two-dimensional array of integers, a, is a square matrix (that is, if it is
non-null and it has the same number of rows as it does columns), and "false"
otherwise.
10. In just a few words, when we wrote the adventure game in class, why did we
use an ArrayList rather than an array to store the Things in our inventory?
Part II: Write the
following methods:
11.
A
"square-free" number is a positive integer that is not divisible by any perfect
square except 1. For example, 10 is square-free but 18 is not, as it is
divisible by 9 = 32. The smallest square-free numbers are:
1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, ...
Write a method that takes an integer and returns true if it is square-free
and false otherwise. By definition, all integers less than 1 are not
square-free.
12.
Write a method that takes an
array of integers and returns an ArrayList of the odd values in the original
array. If the array is either empty or null, your method should return a
non-null but empty ArrayList.
For example, given this array:
{ 4, 2, 3, 8, 7, 6 }
Your method would return this ArrayList:
[ 3, 7 ]
Part III: Understanding code.
13.
What will this code print?
int[]
a = { 2, 1, 4, 5, 6, 3 };
for (int i=0; i<a.length-1; i+=2)
a[i+1] -= a[i];
System.out.println(Arrays.toString(a));
14.
What will this code print?
String
s = "abc";
for (int i=0; i<10; i++)
if (i % s.length() == 1) s += i;
System.out.println(s);
15.
In general,
and in just a few words of plain English, when does this method return true?
public static boolean f(int x) {
if (x < 0) x = -x;
int y = 0;
while (x > 0) {
y += (x % 10);
x /= 10;
}
return (y == 1);
}
16.
In general,
and in just a few words of plain English, what does this program do? You
may draw a picture or two if that helps you explain it.
import java.awt.*;
class MyCode extends JComponentWithEvents {
private int w;
public void start() { w = 1; }
public void timerFired() { w = (w + 1) % 100; }
public void paint(Graphics2D page) { page.fillRect(w, 20, w, 20); }
public static void main(String[] args) { launch(500,500); }
}
Part IV: Write the following
classes.
17.Write the Note and the Song classes so that the following code passes all its tests. Do not worry about any test cases besides those given here (for example, do not worry about sharps or flats or octaves -- keep it very simple, just to pass these tests). Note: You do not need to know anything about music to solve this problem.
private static void testNoteAndSongClasses() {
System.out.print("Running Note and Song class tests... ");
// Note Constructor, toString, accessors, and mutators
Note note = new Note("B", 3); // a B played for 3 beats
assert(note.toString().equals("Note(pitch=B, beats=3)"));
assert(note.getPitch().equals("B"));
assert(note.getBeats() == 3);
note.setPitch("D");
assert(note.toString().equals("Note(pitch=D, beats=3)"));
note.doubleBeats();
assert(note.toString().equals("Note(pitch=D, beats=6)"));
// Another constructor
note = new Note();
assert(note.toString().equals("Note(pitch=C, beats=1)"));
// Natural ordering
Note[] notes = { new Note("C", 3),
new Note("B", 2),
new Note("C", 1),
new Note("A", 4)
};
Arrays.sort(notes); // sort using Notes's natural ordering, which is
// by pitch (A,B,C,D,E,F,G) then by beats (1,2,3...)
assert(notes[0].toString().equals("Note(pitch=A, beats=4)"));
assert(notes[1].toString().equals("Note(pitch=B, beats=2)"));
assert(notes[2].toString().equals("Note(pitch=C, beats=1)"));
assert(notes[3].toString().equals("Note(pitch=C, beats=3)"));
// A Song is a collection of Notes
Song song = new Song();
assert(song.totalBeats() == 0);
song.add(new Note("E", 2));
song.add(new Note("C", 3));
song.add(new Note("E", 4));
song.add(new Note("A", 1));
assert(song.totalBeats() == 10); // 2 + 3 + 4 + 1 = 10
song.removeAll("E"); // remove all the E notes
assert(song.totalBeats() == 4); // just the C and the A remain!
System.out.println("Passed all tests!!!");
}
Part V: Bonus
18.
Bonus/Optional: what will this code print?
char a = 1, b = 50;
while (a < 11) b += a += 3 + a % 1;
for (int i=0; i<4; i++) {
System.out.print(b);
b += a;
a = (char)(a < 5 ? -a : a%10);
}
19.
Bonus/Optional: what will this code print?
String[][] a = { { "ab", "c32", "a45" },
{ "d", "ee", "ab", "q45", "xyz" },
{ "f", "ghi", "j", "k" },
null,
{ null },
{ "null" }
};
for (int i=0; a[i]!=null; i++)
for (int j=0; j<=i+1; j++)
if (a[i][j].length() == a[i].length) {
System.out.println(i + "," + j + "," + a[i][j]);
a[i+1][j+1] += 567;
}
carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem