CIS 265506

Summer 2008

Exam #2

Name: ______

Score ______/ 100

Exam Version A B C

The versions differ in exam structure only

For multiple choice & true/false questions, circle the correct letter (or answer). You will need to choose the most correct answer from the list. Don’t “read into” the question – answer what is asked. For short answer, essays, and code completion, completely answer the question. When writing code, use plenty of comments so your work can be followed. There is no partial credit for the multiple choice or true/false questions.

Exams are closed notes, closed book. No electronic devices of any kind are permitted. All papers, books, book bags, beverages/food (and containers), computer bags, electronic devices, coats/jackets, and hats must be under your desk (on the floor). Do your own work. The people sitting around you will have a different version of this exam.

Objective Section (40 points)

Choose 20 of the following questions. If you answer more than thirty, only the first thirty answered questions will be graded.

  1. Suppose you push 10, 20, 30, and then 40 onto a stack. Then, you pop three items. What is left on the stack?
  2. 10
  3. 20
  4. 30
  5. 40
  1. Suppose you insert 15, 25, 35, and then 45 on to a queue. You then remove three items. What is left in the queue?
  2. 15
  3. 25
  4. 35
  5. 45
  1. The term priority in a priority queue means that
  2. The highest priority items are inserted first
  3. The programmer must prioritize access to the underlying array
  4. The underlying array is sorted by the priority of the array
  5. The lowest priority items are deleted first
  1. Which of the following is not true? A reference to a class object:
  2. Can be used to access public methods in the object
  3. Has a size dependent on its class
  4. Has the data type of the class
  5. Does not hold the object itself
  1. The disadvantage of mergesort is that
  2. It is not recursive
  3. It uses more memory
  4. Although faster than the insertion sort, it is much slower than quicksort
  5. It is complicated to implement
  1. Besides a loop, a ______(data structure)___ can often be used instead of recursion.
  1. The Shellsort works by
  2. Partitioning the array
  3. Swapping adjacent elements
  4. Dealing with widely separated elements
  5. Starting with the normal insertion sort
  1. Partitioning is
  2. putting all the elements larger than a certain value on one end of the array
  3. dividing an array in half
  4. partially sorting parts of an array
  5. sorting each half of an array separately
  1. You can speed up quicksort if you stop portioning when the partition size is 5 and finish using a different sort
  2. True
  3. False
  1. When dealing with a stack, the pop operation
  2. Permanently removes the top item from the stack
  3. Permanently removes the bottom item from the stack
  4. Removes the top item from the stack without changing the state of the stack
  5. Removes the bottom item from the stack without changing the state of the stack
  1. The time complexity of the Boolean operation IsEmptyStack() is
  2. O(N)
  3. O(N2)
  4. O(NlogN)
  5. O(1)
  1. The (pre-existing) Java class called Stack exists in what package?
  2. java.io
  3. java.stack
  4. java.util
  5. java.package
  1. What is A + B * C in Postfix Notation?
  2. +ABC*
  3. A+BC*
  4. *+ABC
  5. ABC*+
  1. A queue is a ______list
  2. LIFO
  3. FIFO
  4. LILO
  5. FILO
  1. A linear list is ______
  2. A list that is contiguous in memory
  3. A list in which every element has a unique successor
  4. A list in which all the elements have a straight line
  5. None of the above
  1. A circular linked list is one that
  2. the NEXT pointer of the last element is NULL
  3. the NEXT pointer of the last element points to itself
  4. the NEXT pointer of the last element points to the previous element
  5. the NEXT pointer of the last element points to the first element in the list
  1. The first property of recursion is: one or more ______that have a straightforward, non-recursive solution
  1. The second property of recursion is: everything else is redefined in terms of the ______
  1. The Towers of Hanoi example requires how many moves?
  2. 2*(n-1)
  3. 2n-1
  4. 2n-1
  5. 2n
  1. In a linked list implementation of a queue, what condition must hold for front and rear to be equal?
  2. When the list is full
  3. When the list is empty
  4. Neither
  5. Both
  1. Place the following growth rates in order from lowest to highest:

O(1), O(n x log(n)) , O(n3), O(log(n)), O(n2), O(n!), O(n)

  1. Items can be added only to the rear of the queue and viewed only from the front of the queue
  2. True
  3. False

23.The Java class named ______is the only true superclass in the Java programming language because all other classes extend it.

24.The keyword ______has two uses, one is to call the constructor for an object and the other is to allocate memory for an array.

25. When a program has finished with a file, it should ______the file.

26. Can an array be passed as an argument to a method? ______(yes or no)

Java Data Structures Programming (60 points)

Be complete, specific, and accurate. Use proper Java syntax. Answer all three questions.

1. Write a method to recursive to calculate Euclid’s Algorithm for finding the greatest common divisor (gcd) of two positive integers. The greatest common divisor is the largest integer that divides both values without producing a remainder.

Example: the GCD of 4 and 12 is 4. The GCD of 18 and 42 is 6.

public int gcd(int num1, int num2) {

/*****************************************************

Algorithm:

gcd(num1, num2) is num2 if num2 <= num1 and num2 divides num1

gcd(num1, num2) is gcd(num2, num1) if num1 < num2

gcd(num1, num2) is gcd(num2, num1 % num2) otherwise

*****************************************************/

}

For questions 2 and 3: Please use the following classes to help answer the questions.

publicclass MyLink {

public Object data;

public MyLink next;

public MyLink(Object d) {

data = d;

}

publicvoid displayLink() {

System.out.print(" " + data.toString());

}

public String toString() {

returndata.toString();

}

}

publicclass MyLinkedList {

private MyLink first;

private MyLink last; //

public MyLinkedList() {

first = null;

last = null;

}

publicboolean isEmpty() {

return (first == null);

}

publicvoid insertFirst(Object d) {

// code deleted

}

public MyLink deleteFirst() {

// code deleted

}

publicvoid insertLast(Object d) {

// code deleted

}

publicvoid displayList() {

System.out.print("List (first to last) is ");

// code deleted

}

public MyLink find(Object key) {

// code deleted

}

public MyLink delete(Object key) {

// code deleted

}

publicvoid makeEmpty() {

// code deleted

}

publicvoid push(Object j) {

insertFirst(j);

}

public Object pop() {

return deleteFirst();

}

publicvoid enqueue(Object j){

insertLast(j);

}

public Object dequeue() {

return deleteFirst();

}

publicvoid insertSorted(Object key){

// code deleted

}

privateboolean isGreaterThan(Object k, Object d){

// code deleted

}

}

For questions 2 and 3: Please use the previous classes to help answer the questions.

2. Create a method that will print – to the console – a string backwards. You must use the classes above (and relevant String methods), and cannot directly reverse the string. Remember the rules about the data structures we have discussed.

publicstaticvoid Q2() {

String string1 = "Simple String";

}

Your output should be “gnirtS elpmiS”

3. Create a method that takes a string called s1, divides the string in to characters, and places each character in a separate node in a linear list. Examine the string called s1, and count the number of lower case ‘s’s that occur. Delete all the ‘s’s in the list. Print the list contents. Remember the rules about the data structures we have discussed.

publicstaticvoid Q3() {

MyLinkedList l1 = new MyLinkedList();

String s1 = "Mississippi";

}

Your output should be:

List (first to last) is M i i i p p i

/ code deleted have discussed. ject oriented programming are: ______and ______

CIS 265/506

Exam Number 2

Exam2_A.doc

Page 1 of 9