Sample Data Structures Questions
Chapter 3
Collection Classes

Data Structures and Other Objects Using Java (Third Edition)
by Michael Main
ISBN 0-321-37525-4

The Purpose of These Questions

Short Answers

Short Answers Section 3.1 A Review of Java Arrays

1. Write a Java method called zero_some with one parameter x that is an array of double numbers. The method changes x[0], x[2], x[4], ... all to zero. If you activate zero_some(a) for an actual array a, will some components of a be changed to zero?

2. Write a fragment of Java code that creates an array of 42 integers and puts the numbers 0, 10, 20, ... in the components of the array.

3. Draw a picture of memory after these statements:

       int[ ] m = new int[2];
       m[0] = 0;
       m[1] = 1;
       int[ ] p = m;
       p[0] = 4;
       p[0] = 5;
   

4. Draw a picture of memory after these statements:

       int[ ] m = new int[2];
       m[0] = 0;
       m[1] = 1;
       int[ ] p = (int[ ]) m.clone( );
       p[0] = 4;
       p[0] = 5;
   

   Short Answers Section 3.2 The Bag ADT

5. What happens if you call new but the heap is out of memory?

6. Suppose that you are storing a collection of items in a partially-filled array. You will declare the array with some initial size. What else must you keep track of?

7. Consider the Bag from Chapter 3 (using an array). What happens if the insert method is activated, and the array is already full? Does the method work even if the array had a weird length of zero?

8. Chapter 3 provides a Bag class that stores the items in an array. Use an example with pictures to explain what goes wrong if we implement the clone method by activating super.clone and then forget to do additional work of creating a new array for the clone.

9. Consider the Bag from Chapter 3 (using an array). The reference to the array is an instance variable called data, and the number of elements in the partially-filled array is the instance variable manyItems. Write the following new method:

       public void triple_capacity( )
       // Postcondition: The capacity of this Bag's array has been
       // tripled. This Bag still contains the same items that it previously
       // had.
   

   Do not use the ensureCapacity method. Do use System.arraycopy.

   Short Answers Section 3.3 The Sequence ADT

10. Suppose that I have the following declarations:

        int[ ] data = new int[100];
        int i;
    

    Write a small segment of Java code that will shift data[50]...data[98] up one spot to the locations data[51]...data[99]. Then insert the number 42 at location data[50]. Use a for loop (not System.arraycopy).

11. Suppose that I have the following declarations:

        int[ ] data = new int[100];
        int i;
    

    Write a small segment of Java code that will shift data[51]...data[99] down one spot to the locations data[50]...data[98]. The value of data[99] remains at its original value. Use a for loop (not System.arraycopy).

Multiple Choice

Multiple Choice Section 3.1 A Review of Java Arrays

1. Suppose I have int b = new int[42]. What are the highest and lowest legal array indexes for b?
   • A. 0 and 41
   • B. 0 and 42
   • C. 1 and 41
   • D. 1 and 42

2. Consider the following statements:

       int[ ] p = new int[100];
       int[ ] s = p;
   

   After these statements, which of the following statements will change the last value of p to 75?
   • A. p[99] = 75;
   • B. p[100] = 75;
   • C. s[99] = 75;
   • D. s[100] = 75;
   • E. Two or more of the answers will change i to 75.

3. Consider the following statements:

       int[ ] p = new int[100];
       int[ ] s = (int[ ]) p.clone( );
   

   After these statements, which of the following statements will change the last value of p to 75?
   • A. p[99] = 75;
   • B. p[100] = 75;
   • C. s[99] = 75;
   • D. s[100] = 75;
   • E. Two or more of the answers will change i to 75.

4. Which is the best approach to copying elements from part of one array b to another array c?
   • A. Use a for loop.
   • B. Use b.clone( ).
   • C. Use the assignment operator c = b.
   • D. Use System.arraycopy.

5. Suppose we have this method:

      public static foo(int[ ] b)
      {
         b[0]++;
      }
   

   What is printed by these statements?

      int[ ] x = new int[100];
      x[0] = 2;
      foo(x);
      System.out.println(x[0]);
   

   • A. 0
   • B. 1
   • C. 2
   • D. 3

6. Suppose you have the following function prototype and variable declaration:

       public void goop(int[ ] z)
       int[ ] x = new int[10];
   

   Which is the correct way to call the goop method with x as the argument:
   • A. goop(x);
   • B. goop(x[ ]);
   • C. goop(x[10]);
   • D. goop(&x);
   • E. goop(&x[ ]);

   Multiple Choice Section 3.2 The Bag ADT

7. Which statement is true for the Chapter 3 bag (with an array)?
   • A. A programmer who uses the bag must call ensureCapacity as items are added, otherwise the bag might not be big enough for more items.
   • B. A programmer may optionally call ensureCapacity, but if he doesn't then the bag will grow as more items are added.

8. Who needs to know about the invariant of an ADT?
   • A. Only the programmer who implements the class for the ADT.
   • B. Only the programmer who uses the class for the ADT.
   • C. Both the programmer who implements the class and the programmer who uses the class.
   • D. Neither the programmer who implements the class nor the programmer who uses the class.

9. Suppose that the Bag is implemented with an array. Which of these operations will always 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

10. Suppose that the Bag is implemented with an array and that you have two Bags b1 (with size n1) and b2 (with size n2). The capacity of b1 is currently n1+n2, and the capacity of b2 is currently just n2. What are the time requirements for b1.addAll(b2)? What
    • A. O(n1)
    • B. O(n2)
    • C. O(n1+n2)
    • D. O(n1*n2)

11. Suppose that the Bag is implemented with an array and that you have two Bags b1 (with size n1) and b2 (with size n2). The capacity of b1 is currently n1+n2, and the capacity of b2 is currently just n2. What are the time requirements for b2.addAll(b1)? What
    • A. O(n1)
    • B. O(n2)
    • C. O(n1+n2)
    • D. O(n1*n2)

12. Suppose that the Bag class is efficiently implemented with an array with a capacity of 4000, as in Chapter 3 of the class notes. Choose the best description of b's instance variables after we execute these statements:

        Bag b;
        b.add(5);
        b.add(4);
        b.add(6);
    

    What will be the values of b.manyItems and b.data after the statements?
    • A. b.manyItems is 3, b.data[0] is 4, b.data[1] is 5, and b.data[2] is 6
    • B. b.manyItems is 3, b.data[0] is 5, b.data[1] is 4, and b.data[2] is 6
    • C. b.manyItems is 3, b.data[0] is 6, b.data[1] is 4, and b.data[2] is 5
    • D. b.manyItems is 3, b.data[0] is 6, b.data[1] is 5, and b.data[2] is 4

13. Suppose that the Bag class is efficiently implemented with an array with a capacity of 4000, as in Chapter 3 of the class notes. We execute these statements:

        Bag b;
        b.add(5);
        b.add(4);
        b.add(6);
        b.remove(5);
    

    What will be the values of b.manyItems and b.data after the statements?
    • A. b.manyItems is 2, b.data[0] is 4, b.data[1] is 6
    • B. b.manyItems is 2, b.data[0] is 6, b.data[1] is 4
    • C. b.manyItems is 3, b.data[0] is 4, b.data[1] is 6
    • D. b.manyItems is 3, b.data[0] is 6, b.data[1] is 4

14. I have an array named data, which contains n integers. I want to print all of the numbers, starting at data[0]. BUT if the number 42 occurs, then I want to stop my printing just before the 42 (without printing the 42!) Here is most of my for-loop to accomplish my goal:

        for (i = 0;  ___________________________________________; i++)
           System.out.println(data[i]);
    

    What is the correct way to fill in the blank? (If there is more than one correct answer, please select E.)
    • A. (data[i] != 42) && (i < n)
    • B. (data[i] != 42) || (i < n)
    • C. (i < n) && (data[i] != 42)
    • D. (i < n) || (data[i] != 42)
    • E. More than one of the above answers is correct.

15. Here is a small function that uses the Bag class from Chapter 3:

        public static void quiz( )
        {
            int i;                               // Line 1
            IntArrayBag b = new IntArrayBag( );  // Line 2
    
            b.add(42);                           // Line 3
            i = b.size( );                       // Line 4
            System.out.println(i);               // Line 5
        }
    

    When is the Bag's array created?
    • A. During the execution of Line 2.
    • B. During the execution of Line 3.
    • C. Just after Line 4 and before line 5.
    • D. After Line 5.

    Multiple Choice Section 3.3 The Sequence ADT

16. In Chapter 3, there was a suggested implementation of the Sequence class with these private member variables:

        class Sequence
        {
            int[ ] data;
            int manyItems;
            int currentIndex;
        };
    

    The Sequence's constructor creates a new array for data to refer to, but does not place any values in the data array. Why?
    • A. The first activation of addAfter or addBefore initializes the entire array.
    • B. The array initialization was part of the project that was left to the student.
    • C. The programmer who uses the Sequence is responsible for initializing the array.
    • D. When a Sequence is first created, none of the array is being used.

17. This question is appropriate if you implemented the Sequence class. The Sequences's addBefore member method normally puts a new item before the current item. What does addBefore do if there is no current item?
    • A. The addBefore precondition is violated.
    • B. The new item is put at the beginning of the list.
    • C. The new item is put at the end of the list.
    • D. None of the above.

18. Suppose that the Sequence is implemented with an array. Which of these operations are likely to have a constant worst-case time?
    • A. addBefore
    • 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

19. Suppose the Bag and Sequence are both implemented with an array as in Chapter 3. What is the difference between the private instance variables of the Bag and the private instance variables of the Sequence?
    • A. The Bag has an extra array of integers.
    • B. The Bag has one extra int instance variable.
    • C. The Sequence has an extra array of integers.
    • D. The Sequence has one extra int instance variable.

20. Suppose that the Bag and the Sequence have both been implemented with partially filled arrays. Which statement is true about the worst-case run time of the remove operations.
    • A. Both removal methods have constant worst-case run times.
    • B. The Bag's removal is constant time, but the Sequence's removal is not.
    • C. The Sequence's removal is constant time, but the Bag's removal is not.
    • D. Neither removal method has constant worst-case run time.