CSCE 146 Spring 2001
SECOND MIDTERM EXAM (CLOSED BOOK)
Tuesday 01/04/17
Please sign this permission form: I authorize my midterm
grade to be posted (on the web or otherwise) using the last four digits of my
student number_____________________.
Be concise. The
maximum score is 68 points. (Think: one
point per minute!)
Chapter 4: Linked Lists
Short
Answers---three points each
- Suppose we are using the usual IntNode
class (with instance variables called data and link), and that locate is
referring to a node in a linked list. Write an assignment statement that
will make locate refer to the next node in the list (if there is one). If
there is no next node, then your assignment statement should set locate to
null.
Anwer:
locate = locate.link OR locate =
locate.getLink()
- Implement the following method as a new
static method for the IntNode class. (Use the usual IntNode definition
with instance variables called data and link.)
public static int sum(IntNode head)
// Precondition: head is the head reference of a linked list.
// The list might be empty or it might be non-empty.
// Postcondition: The return value is the sum of all the data components
// of all the nodes. NOTE: If the list is empty, the method returns 0.
Answer:
Sum = 0;
for (cursor = head; cursor != null; cursor = cursor.getLink())
Sum = Sum + cursor.getData();
return Sum;
- Implement the following method as a new
static method for the IntNode class. (Use the usual Node definition with
instance variables called data and link.)
public static boolean dataIsOn(IntNode head, IntNode p)
// Precondition: head is the head reference of a linked list
// (which might be empty, or might be non-empty). The parameter p
// is a non-null reference to some IntNode on some linked list.
// Postcondition: The return value is true if the data in p
// appears somewhere in a data field of a node in head's
// linked list. Otherwise the return value is false.
// None of the nodes on any lists are changed.
Answer:
for (cursor = head; cursor != null; cursor = cursor.getLink())
If (cursor.getData() == p.getData()) return true;
return false;
- Compare the worst-case big-O time
analysis for these two methods: The remove method for the Sequence that is
implemented using an array, and the remove method for the Sequence that is
implemented using a linked list.
Answer:
O(n) and O(1) respectively. Note that
this method is called removeCurrent in the text.
- Describe a situation where storing items
in an array is clearly better than storing items on a linked list.
Answer:
When elements must be retrieved by their position.
Multiple
Choice---One Point Each
- Suppose cursor refers to a node in a linked
list (using the IntNode class with instance variables called data and
link). What statement changes cursor so that it refers to the next node?
- A. cursor++;
- B. cursor = link;
- C. cursor += link;
- D. cursor =
cursor.link;
Answer: D
- In the linked list version of the Bag class an
instance variable manyNodes is used to keep track of how long the linked
list is. Why not just make a call to the IntNode method listLength()?
- A. The listLength()
method is O(n) and the alternative is O(1).
- B. The listLength()
method is private.
- C. The listLength()
method results in an infinite loop for circular lists.
- D. The listLength()
method works only for lists of integers.
Answer: A
- Suppose that the Bag is implemented with a
linked list. Which of these operations are likely to have a constant
worst-case time?
- A. add
- B. countOccurrences
- C. remove
- D. None of (A), (B),
and (C) have a constant worst-case time
- E. TWO of (A), (B),
and (C) have a constant worst-case time
- F. ALL of (A), (B),
and (C) have a constant worst-case time
Answer: A
- What is the expression for generating a
pseudorandom number in the range 1...N?
- A. (int)
(Math.random() * N);
- B. (int)
(Math.random() / N);
- C. (int)
(Math.random() * (N + 1));
- D. (int)
(Math.random() / (N + 1));
- E. (int)
(Math.random() * N) + 1;
Answer: E. (Recall that (int) truncates and that the
value returned by Math.random is always less than 1---See p.223 of textbook.)
- What kind of list is best to answer questions
such as "What is the item at position n?"
- A. Lists implemented
with an array.
- B. Doubly-linked
lists.
- C. Singly-linked
lists.
- D. Doubly-linked or
singly-linked lists are equally best
Answer: A
Chapter 5: Java
Objects and Iterators
Short Answers---three points each
- Suppose that i and j are both Integer objects
(using the Integer wrapper class). Write a statement that will print the
sum of i and j.
Answer:
System.out.println(i.intValue() + j.intValue());
Multiple
choice---one point each
- Suppose that obj is an Object variable and s is
a String variable. Which of the following statements is a
correctly-compiling widening conversion? Don't worry about possible
run-time exceptions.
- A. obj = s;
- B. s = obj;
- C. s = (String) obj;
- D. Two or more answers
are correct.
Answer: A. (A and C will compile correctly, although a
run-time error may arise when executing C, if obj does not contain a string at
the time the assignment is executed.
However, only A is widening.)
- Suppose that obj is an Object variable and that
it refers to an Integer object. If s is a String variable, then which
statement is correct about the assignment
"s = (String) obj;"?
- A. The statement will
not compile.
- B. The statement will
compile, but there will be a run-time exception.
- C. The statement will
compile and run with no exception.
Answer: B
- What is a primary difference between an array
and a Vector from Java's Class Libraries:
- A. Vectors can have
more than one index.
- B. Vectors can have
negative integers as indexes.
- C. Vectors can have
positive double numbers as indexes.
- D. Vectors grow
automatically as needed.
Answer: D
- Suppose that x and y are reference variables
and a program activates x.equals(y). What occurs if x is the null
reference?
- A. A
NullPointerException occurs
- B. It always returns
true.
- C. It always returns
false.
- D. It returns true if
y is also a null reference; otherwise it returns false.
Answer: A
- What is the primary purpose of an Iterator
object?
- A. To add new objects
to a collection.
- B. To step through the
objects of a collection one at a time.
- C. To play an audio
clip.
- D. To display a
graphical object.
Answer: B
Chapter 6: Stacks
Short
Answer---three point each
- I am going to execute this code with THREE
pushes and ONE pop:
IntStack s = new IntStack( );
s.push(1);
s.push(2);
s.push(3);
System.out.println(s.pop( ));
Suppose
that s is represented by a partially filled array. Draw the state of the
private instance variables of s after the above code:
Answer: manyItems is 2 and the data array is drawn below.
_______ __________________________________
manyItems| | data| | | | | |
1 2 3 |______|______|______|______|______|...
[0] [1] [2] [3] [4]
- I am going to execute this code with THREE
pushes and ONE pop:
IntStack s = new IntStack( );
s.push(1);
s.push(2);
s.push(3);
System.out.println(s.pop( ));
Suppose that s is represented by a linked list. Draw the state of the
private member variables of s after the above code:
Answer: manyItems is 2. The list is head->2->1
Multiple
Choice---one point
- Entries in a stack are
"ordered". What is the meaning of this statement?
- A. A collection of
Stacks can be sorted.
- B. Stack entries may
be compared with the '<' operation.
- C. The entries must be
stored in a linked list.
- D. There is a first
entry, a second entry, and so on.
Answer: D
- The operation for adding an entry to a
stack is traditionally called:
- A. add
- B. append
- C. insert
- D. push
Answer: D
- The operation for removing an entry from
a stack is traditionally called:
- A. delete
- B. peek
- C. pop
- D. remove
Answer: C
- Which of the following stack operations
could result in stack underflow?
- A. is_empty
- B. pop
- C. push
- D. Two or more of the
above answers
Answer: B
- Consider the following pseudocode:
declare a stack of characters
while ( there are more characters in the word to read )
{
read a character
push the character on the stack
}
while ( the stack is not empty )
{
pop a character off the stack
write the character to the screen
}
What
is written to the screen for the input "carpets"?
- A. serc
- B. carpets
- C. steprac
- D. ccaarrppeettss
Answer: C
- Here is an INCORRECT pseudocode for the
algorithm which is supposed to determine whether a sequence of parentheses
is balanced:
declare a character stack
while ( more input is available)
{
read a character
if ( the character is a '(' )
push it on the stack
else if ( the character is a ')' and the stack is not empty )
pop a character off the stack
else
print "unbalanced" and exit
}
print "balanced"
Which
of these unbalanced sequences does the above code think is balanced?
- A.
((())
- B.
())(()
- C.
(()()))
- D.
(()))()
Answer: A
- Consider the usual algorithm for determining
whether a sequence of parentheses is balanced. What is the maximum number
of parentheses that will appear on the stack AT ANY ONE TIME when the
algorithm analyzes:
(()(())(()))
?
- A. 1
- B. 2
- C. 3
- D. 4
- E. 5 or more
Answer: C
- Suppose we have an array implementation
of the stack class, with ten items in the stack stored at data[0] through
data[9]. The CAPACITY is 42. Where does the push method place the new
entry in the array?
- A. data[0]
- B. data[1]
- C. data[9]
- D. data[10]
Answer: D
- Consider the implementation of the Stack
using a partially-filled array. What goes wrong if we try to store the top
of the Stack at location [0] and the bottom of the Stack at the last used
position of the array?
- A. Both peek and pop
would require linear time.
- B. Both push and pop
would require linear time.
- C. The Stack could not
be used to check balanced parentheses.
- D. The Stack could not
be used to evaluate postfix expressions.
Answer: B
- In the linked list implementation of the
stack class, where does the push method place the new entry on the linked
list?
- A. At the head
- B. At the tail
- C. After all other
entries that are greater than the new entry.
- D. After all other
entries that are smaller than the new entry.
Answer: A
- In the array version of the Stack class,
which operations require linear time for their worst-case behavior?
- A. is_empty
- B. peek
- C. pop
- D. push when the stack
is below capacity
- E. None of these
operations require linear time.
Answer: E
- In the linked-list version of the Stack
class, which operations require linear time for their worst-case behavior?
- A. is_empty
- B. peek
- C. pop
- D. push
- E. None of these
operations require linear time.
Answer: E
- What is the value of the postfix
expression 6 3 2 4 + - *:
- A. Something between
-15 and -100
- B. Something between
-5 and -15
- C. Something between 5
and -5
- D. Something between 5
and 15
- E. Something between
15 and 100
Answer: A
Chapter 7 Queues
Short
Answer---three points
- I am going to execute this code with
THREE inserts and ONE get_front:
IntQueue q = new IntQueue( );
q.insert(1);
q.insert(2);
q.insert(3);
System.out.println(q.getFront( ));
Suppose
that q is represented by a circular array. Draw the state of these private
instance variables of q after the above code:
Answer:
_______ __________________________________
front| 1 | data| 1 | 2 | 3 | | |
|_______| |______|______|______|______|______|
[0] [1] [2] [3] [4]
- I am going to execute this code with
THREE insert and ONE get_front:
IntQueue q = new IntQueue( );
q.insert(1);
q.insert(2);
q.insert(3);
System.out.println(q.getFront( ));
Suppose
that q is represented by a linked list. Draw the state of the private instance
variables of q after the above code:
_______
front| |
|_2_____|
_______
rear| |
|__3____|
Answer: front->2->3<-rear
- Describe why it is a bad idea to
implement a linked list version a queue which uses the head of the list as
the rear of the queue.
Answer: It is harder to
remove the last item from a linked list, so it would be harder to dequeue. (See discussion on p.362 of textbook.)
Multiple Choice
- One difference between a queue and a stack is:
- A. Queues require
linked lists, but stacks do not.
- B. Stacks require
linked lists, but queues do not.
- C. Queues use two ends
of the structure; stacks use only one.
- D. Stacks use two ends
of the structure, queues use only one.
Answer: C
- If the characters 'D', 'C', 'B', 'A' are placed
in a queue (in that order), and then removed one at a time, in what order
will they be removed?
- A. ABCD
- B. ABDC
- C. DCAB
- D. DCBA
Answer: D
- Which of the following expressions evaluates to
true with approximate probability equal to P? (P is double and 0 <= P
<= 1).
- A. Math.random() <
P
- B. Math.random() >
P
- C. Math.random() <
P * 100
- D. Math.random() >
P * 100
Answer: A
- Suppose we have a circular array implementation
of the queue class, with ten items in the queue stored at data[2] through
data[11]. The current capacity is 42. Where does the insert method place
the new entry in the array?
- A. data[1]
- B. data[2]
- C. data[11]
- D. data[12]
Answer: D
- Consider the implementation of the Queue using
a circular array. What goes wrong if we try to keep all the items at the
front of a partially-filled array (so that data[0] is always the front).
- A. The constructor
would require linear time.
- B. The getFront method
would require linear time.
- C. The insert method
would require linear time.
- D. The isEmpty method
would require linear time.
Answer: B
- In the linked list implementation of the queue
class, where does the insert method place the new entry on the linked
list?
- A. At the head
- B. At the tail
- C. After all other
entries that are greater than the new entry.
- D. After all other
entries that are smaller than the new entry.
Answer: B
- In the circular array version of the Queue
class, which operations require linear time for their worst-case behavior?
- A. getFront
- B. insert when the
capacity has not yet been reached
- C. isEmpty
- D. None of these
operations require linear time.
Answer:
D
- In the linked-list version of the Queue class,
which operations require linear time for their worst-case behavior?
- A. getFront
- B. insert
- C. isEmpty
- D. None of these
operations require linear time.
Answer:
D
- If data is a circular array of CAPACITY
elements, and rear is an index into that array, what is the formula for
the index after rear?
- A. (rear % 1) +
CAPACITY
- B. rear % (1 +
CAPACITY)
- C. (rear + 1) %
CAPACITY
- D. rear + (1 %
CAPACITY)
Answer:
C
- I have implemented the queue with a circular
array, keeping track of front, rear, and manyItems (the number of items in
the array). Suppose front is zero, and rear is one less than the current
capacity. What can you tell me about manyItems?
- A. manyItems must be
zero.
- B. manyItems must be
equal to the current capacity.
- C. count could be zero
or the capacity, but no other values could occur.
- D. None of the above.
Answer: C (But count should
be replaced by manyItems---sorry!)
- I have implemented the queue with a linked
list, keeping track of a front node and a rear node with two reference variables.
Which of these reference variables will change during an insertion into a
NONEMPTY queue?
- A. Neither changes
- B. Only front changes.
- C. Only rear changes.
- D. Both change.
Answer: C. (The code for
insert on p.361 of the textbook is not correct. The correct code is described at the bottom of p.358 and and the
top of p.359. It is also given
correctly in the ObjectLinkedQueue.java class available from the web site for
the textbook.)
- I have implemented the queue with a linked
list, keeping track of a front node and a rear node with two reference
variables. Which of these reference variables will change during an
insertion into an EMPTY queue?
- A. Neither changes
- B. Only front changes.
- C. Only rear changes.
- D. Both change.
Answer: D