Sample Data Structures Questions
Chapter 3
Container Classes

Data Structures and Other Objects Using C++
Fourth Edition
by Michael Main and Walter Savitch
ISBN 0132129485


The Purpose of These Questions

These are typical exam questions from Chapter 3 of the textbook. These exact questions might not be on your exam, but if you research and find the right answers to these questions, that should be good preparation for a real exam. (It's also possible that some of this material was not covered in your class.) At the moment there are 6 short answer questions and 15 multiple choice questions in this file.

Short Answers

    Short Answers
    Section 3.1
    The Bag ADT
  1. The bag class has a member function with this prototype:
    void insert(const value_type& entry);
    Where is the value_type defined and why is it better to have such a definition (rather than just using an int)?

  2. Suppose that you are storing a collection of items in a partially-filled array. You will declare the array and perhaps a constant to indicate the array's size. What else must you keep track of?

  3. In Chapter 3, the CAPACITY of a bag is declared as a static member constant. In this context, what is the meaning of the word "static"?

  4. Help! I have written the following for-loop to print 42 Ouches, but it's not working as I intended. Why?
    std::size_t i;
    for (i = 41; i >= 0; --i)
        cout << "Ouch!" << endl;
    
    Short Answers
    Section 3.2
    The Sequence ADT
  5. Suppose that I have the following declarations:
        int data[100];
        size_t i;
    
    Write a small segment of C++ 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].

  6. Suppose that I have the following declarations:
        int data[100];
        size_t i;
    
    Write a small segment of C++ 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.

Multiple Choice

    Multiple Choice
    Section 3.1
    The Bag ADT
  1. For the bag class in Chapter 3 (using a fixed array and a typedef statement) what steps were necessary for changing from a bag of integers to a bag of double values?
    • A. Change the array declaration from
      int data[CAPACITY] to double data[CAPACITY] and recompile.
    • B. Change the int to double in the typedef statement and recompile.
    • C. Round each double value to an integer before putting it in the bag.
    • D. Round each double value to an integer after taking it out of the bag.

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

  3. Suppose that the bag is implemented with a fixed-size array. Which of these operations are likely to have a constant worst-case time?
    • A. insert
    • B. count
    • C. erase_one
    • 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

  4. Suppose that foo is a new class and you want to declare an array of 10 foo objects. Which constructor will be used to initialize the 10 foo components of the array?
    • A. Only the copy constructor can be used
    • B. Only the default constructor can be used
    • C. Any constructor can be used

  5. Suppose that the bag class is efficiently implemented with a fixed array with a capacity of 4000, as in Chapter 3 of the class text. Choose the best description of b's member variables after we execute these statements:
        bag b;
        b.insert(5);
        b.insert(4);
        b.insert(6);
    
    What will be the values of b.used and b.data after the statements?
    • A. b.used is 3, b.data[0] is 4, b.data[1] is 5, and b.data[2] is 6
    • B. b.used is 3, b.data[0] is 5, b.data[1] is 4, and b.data[2] is 6
    • C. b.used is 3, b.data[0] is 6, b.data[1] is 4, and b.data[2] is 5
    • D. b.used is 3, b.data[0] is 6, b.data[1] is 5, and b.data[2] is 4

  6. Suppose that the bag class is efficiently implemented with a fixed array with a capacity of 4000, as in Chapter 3 of the class text. We execute these statements:
        bag b;
        b.insert(5);
        b.insert(4);
        b.insert(6);
        b.erase_one(5);
    
    • A. b.used is 2, b.data[0] is 4, b.data[1] is 6
    • B. b.used is 2, b.data[0] is 6, b.data[1] is 4
    • C. b.used is 3, b.data[0] is 4, b.data[1] is 6
    • D. b.used is 3, b.data[0] is 6, b.data[1] is 4

  7. 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++)
            cout << data[i] << endl;
    
    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.

  8. Suppose that you are working on a machine where arrays may have up to 4,000,000,000 items. What is the guaranteed range of the size_t data type?
    • A. Negative 4,000,000,000 to positive 4,000,000,000.
    • B. Zero to positive 32,767
    • C. Zero to positive 65,535
    • D. Zero to 4,000,000,000
    • E. Zero to 8,000,000,000

    Multiple Choice
    Section 3.2
    The Sequence ADT

  9. In Chapter 3, there was a suggested implementation of the sequence class with a fixed CAPACITY and these private member variables:
        class sequence
        {
        public:
            typedef double value_type;
            typedef std::size_t size_type;
            static const size_type CAPACITY = 30;
            ...
        private:
            value_type data[CAPACITY];
            size_type used;
        };
    
    The sequence's constructor sets used to zero, but does not place any values in the data array. Why?
    • A. Integer arrays are automatically initialized to zero.
    • B. The first activation of insert or attach initializes the entire array.
    • C. The array initialization was part of the project that was left to the student.
    • D. The programmer who uses the sequence is responsible for initializing the array.
    • E. When a sequence is first created, none of the array is being used.

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

  11. Suppose that the sequence is implemented with a fixed-size array. Which of these operations are likely to have a constant worst-case time?
    • A. insert
    • B. count
    • C. erase_one
    • 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

  12. Suppose the bag and sequence are both implemented with a fixed-size array as in Chapter 3. What is the difference between the private member variables of the bag and the private member variables of the sequence?
    • A. The bag has an extra array of Items.
    • B. The bag has one extra size_t variable.
    • C. The sequence has an extra array of Items.
    • D. The sequence has one extra size_t variable.

  13. 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 erase_one operations.
    • A. Both removal functions 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 function has constant worst-case run time.

  14. Suppose that the bag is implemented with a fixed-size array. Which of these operations are likely to have a constant worst-case time?
    • A. insert
    • B. count
    • C. erase_one
    • D. TWO of the above are likely to have a constant worst-case time.
    • D. ALL of (A), (B), and (C) are likely to have a constant worst-case time.

    Multiple Choice
    Section 3.3
    Interactive Test Programs

  15. What is the best C++ statement to use when a program must choose between several alternatives that are controlled by the value of a single variable?
    • A. do-while statement
    • B. for-statement
    • C. if-else statement
    • D. switch statement
    • E. while statement


Data Structures and Other Objects Using C++

Michael Main (main@colorado.edu)
and
Walter Savitch (wsavitch@ucsd.edu)

Thank you for visiting http://www.cs.colorado.edu/~main/questions/chap03q.html
Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group