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

  1. 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()

 

  1. 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;
 
  1. 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;
  1. 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.

 

  1. 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

 

 
  1. 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?

Answer: D

 

  1. 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()?

Answer: A

  1. Suppose that the Bag is implemented with a linked list. Which of these operations are likely to have a constant worst-case time?

 

Answer: A

  1. What is the expression for generating a pseudorandom number in the range 1...N?

Answer: E.  (Recall that (int) truncates and that the value returned by Math.random is always less than 1---See p.223 of textbook.)

 

  1. What kind of list is best to answer questions such as "What is the item at position n?"

Answer: A

Chapter 5: Java Objects and Iterators

Short Answers---three points each

 
  1. 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

 

  1. 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.

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.)

  1. 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;"?

Answer: B

  1. What is a primary difference between an array and a Vector from Java's Class Libraries:

Answer: D

  1. Suppose that x and y are reference variables and a program activates x.equals(y). What occurs if x is the null reference?

Answer: A

 

  1. What is the primary purpose of an Iterator object?

Answer: B

Chapter 6: Stacks

Short Answer---three point each

  1. 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]
  1. 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

 

  1. Entries in a stack are "ordered". What is the meaning of this statement?

Answer: D

  1. The operation for adding an entry to a stack is traditionally called:

Answer: D

  1. The operation for removing an entry from a stack is traditionally called:

Answer: C

  1. Which of the following stack operations could result in stack underflow?

Answer: B

 

  1. 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"?

Answer: C

 

  1. 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?

Answer: A

 

  1. 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: (()(())(()))?

Answer: C

 

  1. 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?

Answer: D

 

  1. 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?

Answer: B

 

  1. In the linked list implementation of the stack class, where does the push method place the new entry on the linked list?

Answer: A

  1. In the array version of the Stack class, which operations require linear time for their worst-case behavior?

Answer: E

 

  1. In the linked-list version of the Stack class, which operations require linear time for their worst-case behavior?

Answer: E

 

  1. What is the value of the postfix expression 6 3 2 4 + - *:

Answer: A

 

Chapter 7 Queues

Short Answer---three points

  1. 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]
  1. 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    
  1. 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

 

  1. One difference between a queue and a stack is:

Answer: C

 

  1. 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?

Answer: D

 

  1. Which of the following expressions evaluates to true with approximate probability equal to P? (P is double and 0 <= P <= 1).

Answer: A

 

  1. 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?

Answer: D

 

  1. 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).

Answer: B

 

  1. In the linked list implementation of the queue class, where does the insert method place the new entry on the linked list?

Answer: B

 

  1. In the circular array version of the Queue class, which operations require linear time for their worst-case behavior?

Answer: D

 

  1. In the linked-list version of the Queue class, which operations require linear time for their worst-case behavior?

Answer: D

 

  1. 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?

Answer: C

 

  1. 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?

Answer: C (But count should be replaced by manyItems---sorry!)

  1. 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?

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.)

  1. 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?

Answer: D