Sample Data Structures Questions
Chapter 1
The Phases of Software Development

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


The Purpose of These Questions

These are typical exam questions from Chapter 1 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 11 short answer questions and 19 multiple choice questions in this file.

Short Answers

    Short Answers
    Section 1.1
    Specification and Design
  1. Describe one good method for precisely specifying what a function must do, without indicating how the function accomplishes its work. Provide an example, using a small function.

  2. What is a precondition? What is a postcondition?

  3. It's recommended that the precondition be checked at the start of a function. What's a good approach if a function discovers that its precondition is not true?

  4. Is it always possible for a function to check that its precondition is true?

  5. Suppose that you accidently call a correctly implemented function, but the precondition is false. Is the function guaranteed to halt with a nice message? Is the function allowed to erase everything on your hard drive?

  6. Write the first few lines of this function so that it uses the assert facility to check its precondition:
        void exam(int i)
        // Precondition: i is not equal to 42.
        ... 
    

    Short Answers
    Section 1.2
    Running Time Analysis

  7. Give a concise formula that gives the approximate number of digits in a positive integer. The integer is written in base 10.

  8. Why is the order of an algorithm generally more important than the speed of the processor?

  9. Convert each time formula to the best possible big-O notation. Do not include any spurious constants in your big-O answer.

    Time FormulaBig-O
    10n.
    2n².
    3 times log (base 2) of n.
    2n² + 10n.

  10. Write the simplest big-O expression to describe the number of operations required for the following algorithm:
        for (i = 1; i < N; ++i)
        {
            ...statements that require exactly i operations...
        }
    

    Short Answers
    Section 1.3
    Testing and Debugging

  11. You are at a computer science cocktail party and you meet a student who has just started working with a debugger. With about three or four sentences, explain the basic features of your debugger and how they help you find bugs.

Multiple Choice

    Multiple Choice
    Section 1.1
    Specification and Design
  1. Why is writing easily modifiable code important?
    • A. Easily modifiable code generally has a quicker run time.
    • B. Most real world programs require change at some time.
    • C. Most text editors make it easy to modify code.
    • D. Several people may be writing the same function at the same time.

  2. Which phase of the software life-cycle is usually the most expensive?
    • A. Analysis and specification of the task
    • B. Design
    • C. Implementation
    • D. Maintenance and evolution

  3. What will happen if a function is executed and the precondition for the function is not met?
    • A. An error message will be printed.
    • B. The program will loop indefinitely.
    • C. The system will crash.
    • D. Any of the above results could happen.

  4. Answer true or false for this statement: When programming in teams, the specification of a function should be written by the person writing the code for the function.
    • TRUE.
    • FALSE.

  5. Answer true or false for this statement: When programming individually (not in a team), there is no need to write a specification for a function
    • TRUE.
    • FALSE.

  6. If the precondition fails, it is a good idea to write a useful error message and then halt the program. Why is the program halted?
    • A. Most operating systems forbid continuation.
    • B. The function is no longer guaranteed to make the postcondition true.
    • C. The function's memory requires have become exponential (or worse).
    • D. The function's running time has become exponential (or worse).

  7. Which of these is used to stop the program execution when a precondition is not met.
    • A. assert();
    • B. exit();
    • C. return();
    • D. void();

  8. Which of these statements will always cause a program to halt? (x is an int variable).
    • A. assert(10 > 0);
    • B. assert(10 < 0);
    • C. assert(x < 0);
    • D. None of the above will always cause a program to halt.

    Multiple Choice
    Section 1.2
    Running Time Analysis

  9. What does a run-time analysis usually count?
    • A. The number of arithmetic and other operations required for the program to run
    • B. The number of megabytes required for the program to run
    • C. The number of seconds required for the program to run
    • D. The number of seconds plus the number of megabytes
    • E. The number of seconds times the number of megabytes

  10. Which of these is the correct big-O expression for 1+2+3+...+n?
    • A. O(log n)
    • B. O(n)
    • C. O(n log n)
    • D. O(n²)

  11. Which of the following formulas in big-O notation best represent the expression n²+35n+6?
    • A. O(n³)
    • B. O(n²)
    • C. O(n)
    • D. O(42)

  12. Answer true or false for this statement: For all possible inputs, a linear algorithm to solve a problem must perform faster than a quadratic algorithm to solve the same problem.
    • TRUE.
    • FALSE.

  13. Answer true or false for this statement: True or false: An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of size n=10.
    • TRUE.
    • FALSE.

  14. What term is used to describe an O(n) algorithm.
    • A. Constant
    • B. Linear
    • C. Logarithmic
    • D. Quadratic

  15. Here is some code for an integer variable n:
        while (n > 0)
        {
            n = n/10; // Use integer division
        }
    
    What is the worst-case time analysis for the above loop?
    • A. O(1)
    • B. O(log n)
    • C. O(n)
    • D. O(n²)

  16. Express the formula (n - 2)*(n - 4) using big-O notation:
    • A. O(1)
    • B. O(8)
    • C. O(log n)
    • D. O(n)
    • E. None of the above

    Multiple Choice
    Section 1.3
    Testing and Debugging

  17. Why is it important to test boundary values when testing programs?
    • A. Calculating by hand, it's easy to find the right answers for boundary values.
    • B. Debuggers are easier to use when testing boundary values.
    • C. In practice, a large proportion of errors arise from boundary values.
    • D. The correct execution of a function on all boundary values proves a function is correct.

  18. How may boundary values for a function be found?
    • A. Pick values that are one step away from different behavior.
    • B. Pick values that make the precondition equal to the postcondition.
    • C. Pick values where the precondition is false.
    • D. Pick values where the postcondition is false.

  19. Which software tool will best help you determine whether your test cases are fully exercising your code?
    • A. Compiler
    • B. Debugger
    • C. Make
    • D. Pine
    • E. Profiler


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/chap01q.html
Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
Sample Data Structures Questions - Chapter 2

Sample Data Structures Questions
Chapter 2
Abstract Data Types and C++ Classes

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


The Purpose of These Questions

These are typical exam questions from Chapter 2 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 14 short answer questions and 11 multiple choice questions in this file.

Short Answers

    Short Answers
    Section 2.1 - 2.2
    Introduction to Classes
  1. Here is part of the throttle declaration:
    
        class throttle
        {
        public:
            void shut_off();
            double flow();
            ...
        private:
            int position;
         };
    
    Write several lines of C++ code to declare a throttle called quiz, activate the member function that shuts off quiz's flow, and then print the current flow from quiz.

  2. The public part of the throttle declaration from class notes is shown below. Mark each function member header as follows: Mark C for any constructor; mark X for any function that is forbidden from changing the throttle's data fields.
    
        class throttle
        {
        public:
            throttle( );
            throttle(int size);
            void shut_off( );
            void shift(int amount);
            double flow( ) const;
            bool is_on( ) const;
            ...
    

  3. What is an automatic default constructor, and what does it do?

  4. What is an inline member function, and when might one be used? Give a small example as part of your answer.

    Short Answers
    Section 2.3
    The Header File and the Implementation File

  5. What is a macro guard in a header file, and what is its purpose? Give a small example as part of your answer.

  6. Suppose that the throttle class is implemented with a header file (throttle.h) and an implementation file (throttle.cxx), and that it is part of the namespace main_savitch_2A. Write the include directive and the using directive that are needed for a program to use the throttle class.

    Short Answers
    Section 2.4
    Classes and Parameters

  7. When is it appropriate to use a const reference parameter? Give a small example as part of your answer.

  8. Suppose a function has a parameter named x, and the body of the function changes the value of x. When should x be a value parameter? When should it be a reference parameter? With this function, could x ever be a const reference parameter?

  9. Write one clear sentence telling me when it would be appropriate to use a const reference parameter.

  10. Write one clear sentence telling me when it would be appropriate to use a reference parameter.

    Short Answers
    Section 2.5
    Operator Overloading and Friends

  11. Here is a small class definition:
    
        class small
        {
        public:
            small( );
            void k() const;
            void h(int i);
            friend f(Small z);
        private:
            int size;
        };
    
    Suppose that x and y are both small objects. Write the word "legal" or "illegal" in each location of this table to indicate whether the indicated statement is legal or illegal in these locations:
    Statement In a main program In the const member function k In the friend function f
    x = y;...
    x.size = y.size;...
    x.size = 3;...
    x.h(42);...

  12. Suppose that you define a new class called foo. For two foo objects x and y, you would like the expression x+y to be a new foo object. What is the prototype of the function that you must write to enable expressions such as x+y?

  13. I have written a class with an operator + which is not a member function, but the operator + implementation does access the private member variables of objects in the class. What did I need to do to gain this access?

  14. Write one clear sentence telling me when it would be appropriate to declare a function as a friend of some class.

Multiple Choice

    Multiple Choice
    Section 2.1 - 2.2
    Introduction to Classes
  1. Here is the start of a class declaration:
    
        class foo
        {
        public:
          void x(foo f);
          void y(const foo f);
          void z(foo f) const;
          ...
    
    Which of the three member functions can alter the PRIVATE member variables of the foo object that activates the function?
    • A. Only x can alter the private member variables of the object that activates the function.
    • B. Only y can alter the private member variables of the object that activates the function.
    • C. Only z can alter the private member variables of the object that activates the function.
    • D. Two of the functions can alter the private member variables of the object that activates the function.
    • E. All of the functions can alter the private member variables of the object that activates the function.

  2. Is it possible for a member function of a class to activate another member function of the same class?
    • A. No.
    • B. Yes, but only public member functions.
    • C. Yes, but only private member functions.
    • D. Yes, both public and private member functions can be activated within another member function.

  3. Can two classes contain member functions with the same name?
    • A. No.
    • B. Yes, but only if the two classes have the same name.
    • C. Yes, but only if the main program does not declare both kinds
    • D. Yes, this is always allowed.

  4. What is the common pattern of class definitions that is used in Chapter 2?
    • A. Member functions and member variables are both private.
    • B. Member functions are private, and member variables are public.
    • C. Member functions are public, and member variables are private.
    • D. Member functions and member variables are both public.

  5. Consider this class definition:
    
        class quiz
        {
        public:
            quiz( );
            int f( );
            int g( ) const;
        private:
            double score;
        };
    
    Which functions can carry out an assignment score=1.0; to the private member variable score?
    • A. Both f and g can carry out the assignment.
    • B. f can carry out the assignment, but not g.
    • C. g can carry out the assignment, but not f.
    • D. Neither f nor g can carry out the assignment.

  6. What is the primary purpose of a default constructor?
    • A. To allow multiple classes to be used in a single program.
    • B. To copy an actual argument to a function's parameter.
    • C. To initialize each object as it is declared.
    • D. To maintain a count of how many objects of a class have been created.

  7. Suppose that the foo class does not have an overloaded assignment operator. What happens when an assignment a=b; is given for two foo objects?
    • A. The automatic assignment operator is used
    • B. The copy constructor is used
    • C. Compiler error
    • D. Run-time error

    Multiple Choice
    Section 2.4
    Classes and Parameters

  8. When should you use a const reference parameter?
    • A. Whenever the data type might be many bytes.
    • B. Whenever the data type might be many bytes, the function changes the parameter within its body, and you do NOT want these changes to alter the actual argument.
    • C. Whenever the data type might be many bytes, the function changes the parameter within its body, and you DO want these changes to alter the actual argument.
    • D. Whenever the data type might be many bytes, and the function does not change the parameter within its body.

  9. Here is a small function definition:
    
        void f(int i, int &k)
        {    
            i = 1;         
            k = 2;
        }                      
    
    Suppose that a main program has two integer variables x and y, which are given the value 0. Then the main program calls f(x,y); What are the values of x and y after the function f finishes?
    • A. Both x and y are still 0.
    • B. x is now 1, but y is still 0.
    • C. x is still 0, but y is now 2.
    • D. x is now 1, and y is now 2.

  10. Here is a function prototype and some possible function calls:
    
        int day_of_week(int year, int month = 1, int day = 1);
        // Possible function calls:
           cout << day_of_week( );
           cout << day_of_week(1995);
           cout << day_of_week(1995, 10);
           cout << day_of_week(1995, 10, 4);
    
    How many of the function calls are legal?
    • A. None of them are legal
    • B. 1 of them is legal
    • C. 2 of them are legal
    • D. 3 of them are legal
    • E. All of them are legal

    Multiple Choice
    Section 2.5
    Operator Overloading and Friends

  11. Which kind of functions can access private member variables of a class?
    • A. Friend functions of the class
    • B. Private member functions of the class
    • C. Public member functions of the class
    • D. All of the above can access private member variables
    • E. None of the above


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/chap02q.html
Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
Sample Data Structures Questions - Chapter 3

Sample Data Structures Questions
Chapter 3
Container Classes

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


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
Sample Data Structures Questions - Chapter 4

Sample Data Structures Questions
Chapter 4
Pointers and Dynamic Arrays

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


The Purpose of These Questions

These are typical exam questions from Chapter 4 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 15 short answer questions and 22 multiple choice questions in this file.

Short Answers

    Short Answers
    Section 4.1
    Pointers and
    Dynamic Memory
  1. Suppose that p is an int* variable. Write several lines of code that will make p point to an array of 100 integers, place the numbers 0 through 99 into the array components, and return the array to the heap. Do not use malloc.

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

  3. Draw a picture of memory after these statements:
        int i = 42;
        int k = 80;
        int* p1;
        int* p2;
        p1 = &i;
        p2 = &k;
    

  4. Suppose that we execute the statements from the previous question, and then we execute these statements:
        *p1 = *p2;
    
    Draw a picture of memory after this additional statement.

  5. Draw a picture of memory after these statements:
        int i = 42;
        int k = 80;
        int* p1;
        int* p2;
        p1 = &i;
        p2 = &k;
        p1 = p2;
    

    Short Answers
    Section 4.2
    Pointers and Arrays
    as Parameters

  6. Here is a function prototype:
        void exam(const double data[]);
    
    Write two or three sentences to tell me all the information that you know about the parameter.

  7. Consider the following prototype:
        function foo (const int * p);
    
    What restriction does the const keyword provide within the implementation of foo?

    Short Answers
    Section 4.3
    The Bag ADT with
    a Dynamic Array

  8. Chapter 4 provides a bag class that stores the items in a dynamic array. Use an example with pictures to explain what goes wrong if the automatic assignment operator is used for this bag.

  9. Consider the bag from Chapter 4 (using a dynamic array). If the insert function is activated, and the bag is full, then the bag is resized with the statement:
        reserve(used + 1);
    
    Describe a problem with this approach, and provide a better solution.

  10. Consider the bag from Chapter 4 (using a dynamic array). The pointer to the dynamic array is called data, and the size of the dynamic array is stored in a private member variable called capacity. Write the following new member function:
        void bag::triple_capacity( )
        // Postcondition: The capacity of the bag's dynamic array has been
        // tripled. The bag still contains the same items that it previously
        // had.
    
    Do not use the reserve function, do not use realloc, and do not cause a heap leak. Do make sure that both data and capacity have new values that correctly indicate the new larger array.

    Short Answers
    Section 4.6
    The Polynomial

  11. Implement functions to meet the following specificaions. In each case, you should make an appropriate choice for the kind of parameter to use (a value parameter, a reference parameter, or a const reference parameter). These functions are neither member functions nor friends.
    • A. A void function with one parameter (a polynomial p). The function prints the value of p evaluated at x=1, x=2, x=3,..., up to x=10.
    • B. A void function with one parameter (a polynomial p). The function deletes the largest term in p, and this change should affect the actual argument.

  12. This question is relevant if you implemented the polynomial class with a dynamic array. Which of the polynomial operators needed a nested loop in its implementation?

  13. This question is relevant if you implemented the polynomial class with a dynamic array. Draw a picture of the values in the first five elements of your dynamic array and tell me the value of the current degree after these statements:
    polynomial p(3);
    p.assign_coef(4.1, 4);
    p.assign_coef(2.1, 2);
    

  14. Suppose that a main function has executed the three statements shown in the previous problem. Give an example of one statement that can now be executed by the main function, causing the degree of p to drop to 2.

  15. This question is relevant if you implemented a polynomial that included some calculus-based operations such as derivative and integral. Write a new function that meets the following specification:
    double slope(const polynomial& p, double x)
    // POSTCONDITION: The return value is equal to the slope of the
    // polynomial p, evaluated at the point x.
    

Multiple Choice

    Multiple Choice
    Section 4.1
    Pointers and
    Dynamic Memory
  1. Consider the following statements:
        int *p;
        int i;
        int k;
        i = 42;
        k = i;
        p = &i;
    
    After these statements, which of the following statements will change the value of i to 75?
    • A. k = 75;
    • B. *k = 75;
    • C. p = 75;
    • D. *p = 75;
    • E. Two or more of the answers will change i to 75.

  2. Consider the following statements:
       int i = 42;
       int j = 80;
       int *p1;
       int *p2;
       p1 = &i;
       p2 = &j;
       *p1 = *p2;
       cout << i << j << endl;
    
    What numbers are printed by the output statement?
    • A. 42 and then another 42
    • B. 42 and then 80
    • C. 80 and then 42
    • D. 80 and then another 80

  3. What is printed by these statements?
        int i = 1;
        int k = 2;
        int *p1;
        int *p2;
        p1 = &i;
        p2 = &k;
        p1 = p2;
        *p1 = 3;
        *p2 = 4;
        cout << i;
    
    • A. 1
    • B. 2
    • C. 3
    • D. 4

  4. What is printed by these statements?
         int i = 1;
         int k = 2;
         int* p1;
         int* p2;
         p1 = &i;
         p2 = &k;
         p1 = p2;
         *p1 = 3;
         *p2 = 4;
         cout << k;
    
    • A. 1
    • B. 2
    • C. 3
    • D. 4

  5. What is printed by these statements?
         int i = 1;
         int k = 2;
         int* p1;
         int* p2;
         p1 = &i;
         p2 = &k;
         *p1 = *p2;
         *p1 = 3;
         *p2 = 4;
         cout << i;
    
    • A. 1
    • B. 2
    • C. 3
    • D. 4

  6. When allocating an array of objects, what constructor is used to initialize all of the objects in the array?
    • A. The automatic copy constructor.
    • B. The constructor specified at the declaration.
    • C. The default constructor.
    • D. None of the above.

  7. In which location do dynamic variables reside?
    • A. The code segment.
    • B. The data segment.
    • C. The heap.
    • D. The run-time stack.

    Multiple Choice
    Section 4.2
    Pointers and Arrays
    as Parameters

  8. When should a pointer parameter p be a reference parameter?
    • A. When the function changes p, and you want the change to affect the actual pointer argument.
    • B. When the function changes p, and you do NOT want the change to affect the actual pointer argument.
    • C. When the function changes *p, and you want the change to affect the the object that is pointed at.
    • D. When the function changes *p, and you do NOT want the change to affect the the object that is pointed at.
    • E. When the pointer points to a large object.

  9. Suppose you have the following function prototype and variable declaration:
        void goop(int z[ ]);
        int x[10];
    
    Which is the correct way to call the goop function with x as the argument:
    • A. goop(x);
    • B. goop(x[ ]);
    • C. goop(x[10]);
    • D. goop(&x);
    • E. goop(&x[ ]);

  10. Suppose that the goop function from the previous question changes the value of z[1]. Does this change effect the value of the actual argument?
    • A. Yes
    • B. No

  11. Here is a function declaration:
        void goo(int* x)
        {
            *x = 1;
        }
    
    Suppose that a is an int* variable pointing to some integer, and *a is equal to zero. What is printed if you print *a after the function call goo(a)?
    • A. 0
    • B. 1
    • C. address of a
    • D. address of x
    • E. None of the above

    Multiple Choice
    Section 4.3
    The Bag ADT with
    a Dynamic Array

  12. Here is a small function that uses the dynamic bag class from Chapter 4:
        void quiz( )
        {
            bag::size_type i;   // Line 1
            bag b;              // Line 2
    
            b.insert(42);       // Line 3
            i = b.size( );      // Line 4
            cout << i;    // Line 5
        }
    
    When is the bag's dynamic array allocated?
    • 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.

  13. Here is a small function that uses the dynamic bag class from Chapter 4:
        void quiz( )
        {
            bag::size_type i;  // Line 1
            bag b;             // Line 2
    
            b.insert(42);      // Line 3
            i = b.size( );     // Line 4
            cout << i;   // Line 5
        }
    
    When is the bag's dynamic array returned to the heap?
    • 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.

  14. The + operator which combines two bags was not declared as a member function of the bag class. How can this function access the private data members of the two bags passed as arguments?
    • A. It cannot.
    • B. The operator is declared to be a friend to the class.
    • C. The operator is implemented in the header file containing the bag class definition.
    • D. The operator is implemented in the same implementation file as the bag class.

  15. Suppose that a new foo class has this prototype for an overloaded assignment operator:
        void operator =(const foo& source);
    
    In an assignment statement a = b, what will be the actual argument for the parameter source?
    • A. a
    • B. b

  16. Suppose you are implementing an assignment operator, a copy constructor, and an operator +=. For which of these functions do you need to worry about possible "self-application" (where the argument is the same as the object that activates the function):
    • A. Only one of the three functions has possible self-application
    • B. The assignment operator and the copy construtor have possible self-application
    • C. The assignment operator and the operator += have possible self-application
    • D. The copy construtor and the operator += have possible self-application
    • E. All three functions have possible self-application

  17. What is the usual worst-case performance for resizing a container class that stores its data in a dynamic array?
    • A. Constant time
    • B. Logarithmic time
    • C. Linear time
    • D. Quadratic time

    Multiple Choice
    Section 4.4
    Prescription for a
    Dynamic Class

  18. When a class uses dynamic memory, what member functions should be provided by the class?
    • A. The assignment operator.
    • B. The copy constructor.
    • C. A destructor.
    • D. All of the above.

  19. Which situation does not use the copy constructor?
    • A. Calling a function with a reference parameter
    • B. Calling a function with a value parameter
    • C. Declaring a variable to be a copy of another existing object
    • D. Returning a value from a function
    • E. All of the above situations use the copy constructor

    Multiple Choice
    Section 4.5
    The String ADT

  20. Suppose that you want to declare an array of characters to hold a C++ string with exactly 9 letters. Which declaration is best?
    • A. char s[8];
    • B. char s[9];
    • C. char s[10];
    • D. char s[11];
    • E. char s[12];

  21. Suppose that x and y are two C++ strings. Which expression will return true whenever x and y contain the same sequence of characters?
    • A. (x = y)
    • B. (x == y)
    • C. (x != y)
    • D. (strcmp(x, y))

  22. Suppose that you want to develop two different + operators that calculate and return an object of some class. Which statement is correct?
    • A. One operator must be a friend and the other must not.
    • B. One operator must be public and the other private.
    • C. The operators must have a different parameter lists.
    • D. It is not possible to have two different + operators.


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/chap04q.html
Copyright #169; 2000 Addison-Wesley Computer and Engineering Publishing Group
Sample Data Structures Questions - Chapter 5

Sample Data Structures Questions
Chapter 5
Linked Lists

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


The Purpose of These Questions

These are typical exam questions from Chapter 5 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.) There are 29 short answer questions and 16 multiple choice questions in this file.

Short Answers

    Short Answers
    Sections 5.1-5.2
    Linked List Fundamentals
    The node definition:
    class node
    {
        // TYPEDEF
        typedef double value_type;
    
        // CONSTRUCTOR
        node(
            const value_type& init_data = value_type( ),
            node* init_link = NULL
        )
        { data_field = init_data; link_field = init_link; }
    	// Member functions to set the data and link fields:
        	void set_data(const value_type& new_data) { data_field = new_data; }
        	void set_link(node* new_link)             { link_field = new_link; }
    
    	// Constant member function to retrieve the current data:
    	value_type data( ) const { return data_field; }
    
    	// Two slightly different member functions to retreive
    	// the current link:
    	const node* link( ) const { return link_field; }
        	node* link( )             { return link_field; }
    	
        private:
    	value_type data_field;
    	node* link_field;
        };
    };
    

  1. What is the one statement that can be used to insert a new node at the head of a linked list. Assume that the list's head_pointer is called head_ptr and the that the data for the new node is called entry.

  2. Suppose that p is a pointer to a node in a linked list, and *p is not the tail node. What are the steps to removing the node after *p? Use one short English sentence for each step.

  3. Suppose we are using the usual node definition (with member functions called data and link). Your program is using a node* variable called head_ptr to point to the first node of a linked list (or head_ptr == NULL for the empty list). Write a few lines of C++ code that will print all the double numbers on the list.

  4. Suppose we are using the usual node definition (with member functions called data and link), and that locate_ptr is pointing to a node in a linked list. Write a statement that will make locate_ptr point to the next node in the list (if there is one). If there is no next node, then your statement should set locate_ptr to NULL.

  5. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link.)
        size_t count_42s(const node* head_ptr);
        // Precondition: head_ptr is the head pointer of a linked list.
        // The list might be empty or it might be non-empty.
        // Postcondition: The return value is the number of occurrences
        // of 42 in the data field of a node on the linked list.
        // The list itself is unchanged.
    

  6. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link.)
        bool has_42(const node* head_ptr);
        // Precondition: head_ptr is the head pointer of a linked list.
        // The list might be empty or it might be non-empty.
        // Postcondition: The return value is true if the list has at least
        // one occurrence of the number 42 in the data part of a node.
    

  7. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link.)
        bool all_42s(const node* head_ptr);
        // Precondition: head_ptr is the head pointer of a linked list.
        // The list might be empty or it might be non-empty.
        // Postcondition: The return value is true if every node in the
        // list contains 42 in the data part. NOTE: If the list is empty,
        // then the function returns true.
    

  8. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link. The data field is an int.)
        int sum(const node* head_ptr);
        // Precondition: head_ptr is the head pointer 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 function returns 0.
    

  9. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link. The data field is an int.)
        int product(const node* head_ptr);
        // Precondition: head_ptr is the head pointer of a linked list.
        // The list might be empty or it might be non-empty.
        // Postcondition: The return value is the product of all the data components
        // of all the nodes. NOTE: If the list is empty, the function returns 1.
    

  10. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link.)
        void list_tail_insert(node* head_ptr, const node::value_type& entry);
        // Precondition: head_ptr is the head pointer of a non-empty
        // linked list.
        // Postcondition: A new node has been added at the tail end
        // of the list. The data in the new node is taken from the
        // parameter called entry.
    

  11. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link.)
        bool data_is_on(const node* head_ptr, const node* p);
        // Precondition: head_ptr is the head pointer of a linked list
        // (which might be empty, or might be non-empty). The pointer p
        // is a non-NULL pointer to some node 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_ptr's
        // linked list. Otherwise the return value is false.
        // None of the nodes on any lists are changed.
    

  12. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link.)
        bool is_on(const node* head_ptr, const node* p);
        // Precondition: head_ptr is the head pointer of a linked list
        // (which might be empty, or might be non-empty). The pointer p
        // is a non-NULL pointer to some node on some linked list.
        // Postcondition: The return value is true if p actually points to
        // one of the nodes in the head_ptr's linked list. For example,
        // p might point to the head node of this list, or the second node,
        // or the third node, and so on. Otherwise the return value is
        // false. None of the nodes on any lists are changed.
    

  13. Implement the following function as a new function for the linked list toolkit. Do not call any of the other toolkit functions from within your implementation. (Use the usual node definition with member variables called data and link.)
        void list_insert_zero(node* previous_ptr);
        // Precondition: previous_ptr is a pointer to a node on a linked list.
        // Postcondition: A new node has been added to the list after
        // the node that previous_ptr points to. The new node contains 0.
    

  14. Suppose that p, q, and r are all pointers to nodes in a linked list with 15 nodes. The pointer p points to the first node, q points to the 8th node, and r points to the last node. Write a few lines of code that will make a new copy of the list. You code should set THREE new pointers called x, y, and z so that: x points to the first node of the copy, y points to the 8th node of the copy, and z points to the last node of the copy. Your code may NOT contain any loops, but it can use the toolkit functions.

    Short Answers
    Section 5.3
    The Bag ADT
    with a Linked List

  15. Suppose that a_ptr and b_ptr are node pointers. Write one clear sentence to tell me when the expression (a_ptr==b_ptr) will be true.

  16. Compare the worst-case big-O time analysis for these two functions: The insert function for the bag that is implemented using a fixed-sized array, and the insert function for the bag that is implemented using a linked list.

  17. Compare the worst-case big-O time analysis for these two functions: The erase_one function for the bag that is implemented using a fixed-sized array, and the erase_one function for the bag that is implemented using a linked list.

    Short Answers
    Section 5.4
    The Sequence ADT
    with a Linked List

  18. Tell me about one of the sequence operations that is more efficient because the class keeps a tail pointer as a private member variable. Provide a specific example showing why the operation would be less efficient without the tail pointer.

  19. Tell me about one of the sequence operations that is easier to program because the class keeps a precursor (rather than just a cursor). Provide a specific example showing why the operation would be harder to program without the precursor.

  20. Compare the worst-case big-O time analysis for these two functions: The insert function for the sequence that is implemented using a fixed-sized array, and the insert function for the sequence that is implemented using a linked list.

  21. Compare the worst-case big-O time analysis for these two functions: The remove function for the sequence that is implemented using a fixed-sized array, and the remove function for the sequence that is implemented using a linked list.

    Short Answer
    Section 5.5
    Dynamic Arrays vs.
    Linked Lists vs.
    Doubly Linked Lists
        class dnode
        {
        public:
    	// CONSTRUCTOR: Creates a dnode containing a specified initial values.
    	dnode(
    	    int init_data = 0,
    	    dnode* init_fore = NULL,
    	    dnode* init_back = NULL
    	    )
    	    {
    		data_field = init_data;
    		link_fore = init_fore;
    		link_back = init_back;
    	    }
    
    	// Member functions to set the fields: 
        	void set_data(int new_data)
    	    { data_field = new_data; }
        	void set_fore(dnode* new_fore)
    	    { link_fore = new_fore; }
        	void set_back(dnode* new_back)
    	    { link_back = new_back; }
    
    	// Const member functions to retrieve current data:
    	int data( ) const { return data_field; }
    
    	// Two slightly different member functions to retrieve each link:
    	const dnode* fore( ) const { return link_fore; }
        	dnode* fore( )             { return link_fore; }
    	const dnode* back( ) const { return link_back; }
        	dnode* back( )             { return link_back; }
    	
        private:
    	int  data_field;
    	dnode *link_fore;
    	dnode *link_back;
        };
    

  22. Write one sentence to describe a situation when a doubly linked list is appropriate.

  23. Describe a situation where storing items in an array is clearly better than storing items on a linked list.

  24. Implement the following function using the dnode class that is shown above. It is NOT a member function).
    int sum_data(const dnode* head_ptr);
    // PRECONDITION: head_pointer is a non-NULL head pointer for a linked list.
    // POSTCONDITION: The return value is the sum of all the data fields
    // of the dnodes in the linked list.
    

  25. Implement the following function using the dnode class that is shown above. It is NOT a member function.
    dnode* find_data(dnode* head_ptr, int target)
    // PRECONDITION: head_pointer is a non-NULL head pointer for a linked list.
    // POSTCONDITION: The return value is a pointer to the first dnode in
    // the linked list that contains the target as its data. If there is no
    // such dnode, then the return value is NULL.
    

  26. Implement the following function using the dnode class that is shown above. It is NOT a member function. Your function should not cause a heap leak.
    void delete_dnode(dnode* p)
    // PRECONDITION: p is a non-NULL pointer to a dnode in a linked list.
    // It is neither the first nor the last dnode.
    // POSTCONDITION: The dnode *p has been removed from the list.
    

  27. Implement the following function using the dnode class that is shown above. It is NOT a member function.
    void insert_dnode(dnode* p, int new_data)
    // PRECONDITION: p is a non-NULL pointer to a dnode in a linked list.
    // It is neither the first nor the last dnode.
    // POSTCONDITION: A new dnode with new_data has been inserted into the
    // linked list after *p.
    

  28. Suppose that a program has declared these three variables using the dnode class shown above.
    dnode *b;
    dnode *h;
    dnode *z;
    
    After executing part of the program, the pointer b is a head pointer for a non-empty linked list. Write some code that can be placed in the program at this point to make a complete copy of b's linked list. At the end of your code, b should be unchanged, h should be the head pointer of the new list, and z should be the tail pointer of the new list. If necessary, you may declare other dnode * variables to use in your algorithm.

  29. This question is appropriate if you have implemented the polynomial with a linked list from www.cs.colorado.edu/~main/projects/chap05d.html. In my dynamic polynomial, the set_recent function includes this line:
        recent_ptr = recent_ptr->fore( );
    
    A. Describe the effect of this statement in one clear English sentence.
    B. The set_recent function is a const member function, which means that normally it is not permitted to change any member variables. Explain why the compiler permits set_recent to change the recent_ptr member variable.

Multiple Choice

  1. Suppose cursor points to a node in a linked list (using the node definition with member functions called data and link). What statement changes cursor so that it points to the next node?
    • A. cursor++;
    • B. cursor = link( );
    • C. cursor += link( );
    • D. cursor = cursor->link( );

  2. Suppose cursor points to a node in a linked list (using the node definition with member functions called data and link). What Boolean expression will be true when cursor points to the tail node of the list?
    • A. (cursor == NULL)
    • B. (cursor->link( ) == NULL)
    • C. (cursor->data( ) == NULL)
    • D. (cursor->data( ) == 0.0)
    • E. None of the above.

  3. Why does our node class have two versions of the link member function?
    • A. One is public, the other is private.
    • B. One is to use with a const pointer, the other with a regular pointer.
    • C. One returns the forward link, the other returns the backward link.
    • D. One returns the data, the other returns a pointer to the next node.

  4. Suppose that p is a pointer variable that contains the NULL pointer. What happens if your program tries to read or write *p?
    • A. A syntax error always occurs at compilation time.
    • B. A run-time error always occurs when *p is evaluated.
    • C. A run-time error always occurs when the program finishes.
    • D. The results are unpredictable.

  5. Suppose that f is a function with a prototype like this:
        void f(________ head_ptr);
        // Precondition: head_ptr is a head pointer for a linked list.
        // Postcondition: The function f has done some computation with
        // the linked list, but the list itself is unchanged.
    
    What is the best data type for head_ptr in this function?
    • A. node
    • B. const node
    • C. node*
    • D. const node*

  6. Suppose that f is a function with a prototype like this:
        void f(________ head_ptr);
        // Precondition: head_ptr is a head pointer for a linked list.
        // Postcondition: The function f has done some manipulation of
        // the linked list, and the list might now have a new head node.
    
    What is the best data type for head_ptr in this function?
    • A. node
    • B. node&
    • C. node*
    • D. node*&

  7. Multiple Choice
    Sections 5.1-5.2
    Linked List Fundamentals
    Multiple Choice
    Section 5.3
    The Bag ADT with
    with a Linked List
  8. In the linked list version of the bag class a member variable many_nodes is used to keep track of how long the linked list is. Why not just make a call to the list toolkit function list_length()?
    • A. The list_length() function is O(n) and the alternative is O(1).
    • B. The list_length() function is private.
    • C. The list_length() function results in an infinite loop for circular lists.
    • D. The list_length() function works only for lists of integers.

  9. Suppose that the bag is implemented with a linked list. 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

  10. The bag class in Chapter 5 has a new grab member function that returns a randomly selected item from a bag (using a pseudorandom number generator). Suppose that you create a bag, insert the numbers 1, 2, and 3, and then use the grab function to select an item. Which of these situations is most likely to occur if you run your program 300 times (from the beginning):
    • A. Each of the three numbers will be selected about 100 times.
    • B. One of the numbers will be selected about 200 times; another number will be selected about 66 times; the remaining number will be selected the rest of the time.
    • C. One of the numbers will be selected 300 times; the other two won't be selected at all.

  11. What is the expression for generating a pseudorandom number in the range 1...N?
    • A. rand() % N;
    • B. rand() / N;
    • C. rand() % (N + 1);
    • D. rand() / (N + 1);
    • E. (rand() % N) + 1;

  12. Which expression computes a pseudorandom integer between -10 and 10 using rand() from stdlib.h?
    • A. (rand( ) % 20) - 10
    • B. (rand( ) % 21) - 10
    • C. (rand( ) % 22) - 10
    • D. (rand( ) % 20) - 11
    • E. (rand( ) % 21) - 11

    Multiple Choice
    Section 5.4
    The List ADT
    with a Linked List

  13. For the linked-list version of the sequence ADT, which operations are constant time operations in the worst case?
    • A. attach is constant time, but not insert
    • B. insert is constant time, but not attach
    • C. Both attach and insert are constant time
    • D. Neither attach nor insert are constant time

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

  15. What is the output of these statements, using your sequence ADT implemented as a linked list with Item defined as integer:
        sequence x;
        sequence y;
        x.insert(41);    // Inserts 41 into the sequence x
        x.insert(42);    // Inserts 42, so that x is now 42, 41 with cursor at front
        y = x;
        x.attach(43);    // Attaches 43 so that x is now 42, 43, 41 with cursor at 43
        y.advance( );
        cout << "y size is " << y.size( );
        cout << " and y current item is " << y.current( ) << endl;
    
    • A. y size is 2 and y current item is 41.
    • B. y size is 2 and y current item is 43.
    • C. y size is 3 and y current item is 41.
    • D. y size is 3 and y current item is 43.
    • E. None of the above.

  16. Suppose that you forgot to override the assignment operator in your sequence ADT implemented as a linked list. What is the most likely output from the previous question?
    • A. y size is 2 and y current item is 41.
    • B. y size is 2 and y current item is 43.
    • C. y size is 3 and y current item is 41.
    • D. y size is 3 and y current item is 43.
    • E. None of the above.

    Multiple Choice
    Section 5.5
    Dynamic Arrays vs.
    Linked Lists vs.
    Doubly Linked Lists

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


    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/chap05q.html
    Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
    Sample Data Structures Questions - Chapter 6

    Sample Data Structures Questions
    Chapter 6
    Software Reuse with Templates

    Data Structures and Other Objects Using C++
    by Michael Main and Walter Savitch
    Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


    The Purpose of These Questions

    These are typical exam questions from Chapter 6 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.) There are 7 short answer questions and 13 multiple choice questions in this file.

    Short Answers

      Short Answers
      Sections 6.1
      Template Functions
    1. Write one or two short sentences to clearly explain the advantage of template functions.

    2. Why must the template parameter appear in the parameter list of the template function?

    3. Consider the code below which is supposed to shift the values from data[0] through data[n-1] rightward one position (so these values now reside in data[1] through data[n]).
      
          size_t i;
          for (i = 0; i < n; ++i)
              data[i+1] = data[i];
      
      There is a bug in the above code. Write one sentence to describe the bug and write new code that does the job correctly.

    4. Why is it a bad idea to have a size_t parameter for a template function?

      Short Answers
      Section 6.2
      Template Classes

    5. Suppose that you convert a bag class to a new template class. Name one place where the word bag remains just bag instead of changing to bag<Item>.

    6. Write one or two short sentences to clearly explain the advantage of template classes.

      Short Answers
      Section 6.4
      The Node Template Class

    7. Complete the body of this template function. Check the precondition as much as possible, and don't cause a heap leak.
      
        template <class Item>
        void list_head_remove(node<Item>*& head_ptr)
        //  Precondition: head_ptr is the head pointer of a linked list,
        //  with at least one node.
        //  Postcondition: The head node has been removed and returned to the heap;
        //  head_ptr is now the head pointer of the new, shorter linked list.
      

    Multiple Choice

      Multiple Choice
      Sections 6.1
      Template Functions
    1. What is the primary purpose of template functions?
      • A. To allow a single function to be used with varying types of arguments
      • B. To hide the name of the function from the linker (preventing duplicate symbols)
      • C. To implement container classes
      • D. To permit the use of the debugger without the -gstabs flag

    2. Consider this prototype for a template function:
      
          template <class Item>
          void foo(Item x);
      
      Which is the right way to call the foo function with an integer argument i?
      • A. foo( i );
      • B. foo<int>( i );
      • C. foo<Item>( i );
      • D. foo(<int> i );
      • E. foo(<Item> i );

    3. Consider the following definition:
      
          template <class Item>
          Item maximal (Item a, Item b)
          {
              if (a > b)
                  return a;
              else
                  return b;
          }
      
      What restrictions are placed on the Item data type for a program that uses the maximal function?
      • A. The Item data type must be either int, double, or float.
      • B. The Item data type must be one of the built-in C++ data types.
      • C. The Item data type must have a copy constructor and a > operator defined.
      • D. None of the above restrictions apply.

    4. When should a function be implemented as a template function?
      • A. When the data types of the parameters all have copy constructors.
      • B. When the function depends on an underlying data type.
      • C. When the function is relatively short (usually just one line).
      • D. When the function only takes one argument.

    5. What is a major difference between the header file for a toolkit of template functions and the header file for a toolkit of ordinary functions?
      • A. The ordinary function toolkit header file must have a #include for the implementation file, but the template version does not have this #include.
      • B. The template function toolkit header file must have a #include for the implementation file, but the ordinary version does not have this #include.
      • C. The ordinary function toolkit header file must have a macro guard, but the template version does not have this macro guard.
      • D. The template function toolkit header file must have a macro guard, but the ordinary version does not have this macro guard.

    6. Why is it a bad idea to have a size_t parameter for a template function?
      • A. Because it would require stdlib.h to be separately compiled.
      • B. Because most compilers would not permit the actual argument to be 42 (an int).
      • C. Because size_t values cannot be negative.
      • D. Because the compiler can tell the size of something without having a size_t parameter.

      Multiple Choice
      Section 6.2
      Template Classes

    7. Our original bag classes in Chapters 3-5 used a typedef to define the Item data type. What problem is solved by using a template bag class instead of these original typedef versions?
      • A. None of the typedef versions permit a program to use a bag of Strings.
      • B. With all of the typedef versions, it is difficult for a program to use several bags with different Item types.
      • C. With all of the typedef versions, the CAPACITY of the bag is fixed during compilation. A program cannot dynamically allocate a bag.
      • D. With all of the typedef versions, the Item data type must be one of the built-in C++ data types (char, int, etc.)

    8. Suppose bag is a template class, what is the syntax for declaring a bag b of integers?
      • A. bag b;
      • B. bag<int> b;
      • C. bag of int b;
      • D. int bag b;

    9. Why is it recommended to first implement a class using a typedef for the Item type, before implementing the template version?
      • A. It is easier to debug the typedef version.
      • B. The typedef version requires less disk space during the design stage.
      • C. The typedef version requires less memory during execution.
      • D. The template version will not compile unless you implement the typedef version first.

    10. When you write a template class, where does the template prefix occur?
      • A. Before the template class definition
      • B. Before each member function implementation.
      • C. Before any other template functions that manipulate the template class.
      • D. TWO of the above answers are correct.
      • E. All of the (A), (B), and (C) are correct.

      Multiple Choice
      Sections 6.3 and 6.4
      STL Classes, Iterators,
      and the Node Template Class

    11. Suppose that a program wants to use both a bag of doubles and a bag of strings. Which version of the bag could you use?
      • A. You can use the array version of the non-template bag
      • B. You can use the linked list version of the non-template bag
      • C. You can use the array version of the template bag
      • D. Two of the above answers are right
      • E. Answers A, B, and C are all right

    12. What technique is used to provide the capability to step through items of a container class?
      • A. A copy constructor.
      • B. A default constructor.
      • C. A destructor.
      • D. An iterator.
      • E. An overloaded assignment operator.

    13. Why does the new node template class require two versions of the data member function, but the node in Chapter 5 needed only one?
      • A. The Chapter 5 node was singly linked, but the node template class is doubly linked.
      • B. The Chapter 5 data function returned a copy of the data, but the data function for the node template class returns a reference to the data.
      • C. The Chapter 5 node had no iterator.
      • D. All of the above.


    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/chap06q.html
    Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
    Sample Data Structures Questions - Chapter 7

    Sample Data Structures Questions
    Chapter 7
    Stacks

    Data Structures and Other Objects Using C++
    by Michael Main and Walter Savitch
    Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


    The Purpose of These Questions

    These are typical exam questions from Chapter 7 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.) There are 6 short answer questions and 16 multiple choice questions in this file.

    Short Answers

      Short Answers
      Sections 7.1 - 7.2
      Stacks and Their
      Applications
    1. Explain what modifications would be needed to make the parenthesis matching algorithm check expressions with different kinds of parentheses such as (), [] and {}'s.

    2. Complete the body of this function. You do not need to check the precondition. You may use the stack template class.
      
        bool balanced(const char p[ ], size_t n)
        // Precondition: p[0]...p[n-1] contains n characters, each of which
        // is '(', ')', '{' or '}'.
        // Postcondition: The function returns true if the characters form a
        // sequence of correctly balanced parentheses with each '(' matching
        // a ')' and each '{' matching a '}'. Note that a sequence such as
        // ( { ) } is NOT balanced because when we draw lines to match the
        // parentheses to their partners, the lines cross each other. On the
        // other hand, ( { } ) amd { ( ) } are both balanced.
      

      Short Answers
      Section 7.3
      Implementations of
      the stack ADT

    3. I am going to execute this code with THREE pushes and ONE pop:
      
         stack<int> s;
         s.push(1);
         s.push(2);
         s.push(3);
         s.pop( );
      
      Suppose that s is represented by a partially filled array. Draw the state of the private member variables of s after the above code:
      
                 _______            __________________________________
            used|       |      data|      |      |      |      |      |
                |_______|          |______|______|______|______|______|
                                     [0]    [1]    [2]    [3]    [4]
      

    4. I am going to execute this code with THREE pushes and ONE pop:
      
         stack<int> s;
         s.push(1);
         s.push(2);
         s.push(3);
         cout << 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:
      
                     _______      
            head_ptr|       |  
                    |_______|     
      

      Short Answers
      Section 7.4
      More Complex
      Stack Applications

    5. Implement the following function. You may use the stack template class and the stack operations of push, pop, peek, is_empty, and size. You may also use cin.peek( ) and use "cin>>i" to read an integer.
      
         int evaluate_postfix_from_cin( )
         // Precondition (Which is not checked): The next input line of cin is a
         // properly formed postfix expression consisting of integers, 
         // the binary operations + and -, and spaces. 
         // Postcondition: The function has read the next input line (including
         // the newline) and returned the value of the postfix expression.
         {
            int i;
            stack<int> s;
      

    6. Consider the usual algorithm to convert an infix expression to a postfix expression. Suppose that you have read 10 input characters during a conversion and that the stack now contains these symbols:
      
                    |       |  
                    |   +   |  
                    |   (   |  
             bottom |___*___|     
      
      Now, suppose that you read and process the 11th symbol of the input. Draw the stack for the case where the 11th symbol is:

      A. A number:

      B. A left parenthesis:

      C. A right parenthesis:

      D. A minus sign:

      E. A division sign:

    Multiple Choice

      Multiple Choice
      Sections 7.1-7.2
      Stacks and Their
      Applications
    1. 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.

    2. The operation for adding an entry to a stack is traditionally called:
      • A. add
      • B. append
      • C. insert
      • D. push

    3. The operation for removing an entry from a stack is traditionally called:
      • A. delete
      • B. peek
      • C. pop
      • D. remove

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

    5. Which of the following applications may use a stack?
      • A. A parentheses balancing program.
      • B. Keeping track of local variables at run time.
      • C. Syntax analyzer for a compiler.
      • D. All of the above.

    6. 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 )
         {
            write the stack's top character to the screen
            pop a character off the stack
         }
      
      What is written to the screen for the input "carpets"?
      • A. serc
      • B. carpets
      • C. steprac
      • D. ccaarrppeettss

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

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

    9. Consider the usual algorithm for determining whether a sequence of parentheses is balanced. Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order). What is the maximum number of parentheses that will ever appear on the stack AT ONE TIME during the computation?
      • A. 1
      • B. 2
      • C. 3
      • D. 4
      • E. 5 or more

      Multiple Choice
      Section 7.3
      Implementations of
      the stack ADT

    10. 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 member function place the new entry in the array?
      • A. data[0]
      • B. data[1]
      • C. data[9]
      • D. data[10]

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

    12. In the linked list implementation of the stack class, where does the push member function 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.

    13. In the array version of the stack class (with a fixed-sized array), 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.

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

      Multiple Choice
      Section 7.4
      More Complex
      Stack Applications

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

    16. Here is an infix expression: 4+3*(6*3-12). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation. What is the maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?
      • A. 1
      • B. 2
      • C. 3
      • D. 4
      • E. 5


    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/chap07q.html
    Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
    Sample Data Structures Questions - Chapter 8

    Sample Data Structures Questions
    Chapter 8
    Queues

    Data Structures and Other Objects Using C++
    by Michael Main and Walter Savitch
    Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


    The Purpose of These Questions

    These are typical exam questions from Chapter 8 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.) There are 5 short answer questions and 13 multiple choice questions in this file.

    Short Answers

      Short Answers
      Sections 8.1 - 8.2
      Queues and Their
      Applications
    1. Complete the body of this function. Use a queue of characters to store the input line as it is being read.
      
          size_t counter( )
          // Precondition: There is a line of input waiting to be read from cin.
          // Postcondition: A line of input has been read from cin, up to but not
          // including the newline character. The return value of the function
          // is the number of times that the LAST character of the line appeared
          // somewhere in this line.
          // EXAMPLE Input: ABBXDXXZX
          // The value returned by counter would be 4 for this input since there
          // are 4 X's in the input line.
          {
              size_t answer = 0;
              queue q;
      

      Short Answers
      Section 8.3
      Implementations of
      the Queue ADT

    2. I am going to execute this code with THREE inserts and ONE get_front:
      
         queue<int> s;
         s.insert(1);
         s.insert(2);
         s.insert(3);
         cout << s.get_front( );
      
      Suppose that s is represented by a circular array. Draw the state of these private member variables of s after the above code:
      
                 _______            __________________________________
           first|       |      data|      |      |      |      |      |
                |_______|          |______|______|______|______|______|
                                     [0]    [1]    [2]    [3]    [4]
      

    3. I am going to execute this code with THREE insert and ONE get_front:
      
         queue<int> s;
         s.insert(1);
         s.insert(2);
         s.insert(3);
         cout << s.get_front( );
      
      Suppose that s is represented by a linked list. Draw the state of the private member variables of s after the above code:
      
                     _______      
           front_ptr|       |  
                    |_______|     
                     _______      
            rear_ptr|       |  
                    |_______|     
      

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

      Short Answers
      Section 8.4
      Priority Queues

    5. Suppose that you want to implement the priority_queue so that insertions occur in constant time, but getting the front item requires linear time. You will use these class definitions:
      
          template 
          class priority_queue
          {
              typedef Item value_type;
              void push(const Item&x  entry);
              value_type top( );
              ...
          private:
              node *head_ptr;
          };
      
      
      (A) Write ONE sentence to describe how the insert member function will work (with constant time). (B) Then implement the top function (which will have linear worst-case time). In your implementation, you DO NOT have to worry about items with equal priority (they may come out of the prioirty queue however you like, without necessarily having FIFO behavior). You may also assume that these two toolkit functions have been modified to work with the priority_queue's node:
      
          void list_head_remove(Node*& head_ptr); // Removes head node of a list
          void list_remove(Node* precursor);      // Removes node after *precursor
      

    Multiple Choice

      Multiple Choice
      Sections 8.1-8.2
      Queues and Their
      Applications
    1. One difference between a queue and a stack is:
      • A. Queues require dynamic memory, but stacks do not.
      • B. Stacks require dynamic memory, 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.

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

    3. Which of the following expressions evaluates to true with approximate probability equal to P? (P is double and 0 <= P <= 1).
      • A. rand() < P
      • B. rand() > P
      • C. rand() < P * RAND_MAX
      • D. rand() > P * RAND_MAX

      Multiple Choice
      Section 8.3
      Implementations of
      the Queue ADT

    4. 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 CAPACITY is 42. Where does the push member function place the new entry in the array?
      • A. data[1]
      • B. data[2]
      • C. data[11]
      • D. data[12]

    5. 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 get_front function would require linear time.
      • C. The insert function would require linear time.
      • D. The is_empty function would require linear time.

    6. In the linked list implementation of the queue class, where does the push member function 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.

    7. In the circular array version of the queue class (with a fixed-sized array), which operations require linear time for their worst-case behavior?
      • A. front
      • B. push
      • C. empty
      • D. None of these operations require linear time.

    8. In the linked-list version of the queue class, which operations require linear time for their worst-case behavior?
      • A. front
      • B. push
      • C. empty
      • D. None of these operations require linear time.

    9. If data is a circular array of CAPACITY elements, and last is an index into that array, what is the formula for the index after last?
      • A. (last % 1) + CAPACITY
      • B. last % (1 + CAPACITY)
      • C. (last + 1) % CAPACITY
      • D. last + (1 % CAPACITY)

    10. I have implemented the queue with a circular array, keeping track of first, last, and count (the number of items in the array). Suppose first is zero, and last is CAPACITY-1. What can you tell me about count?
      • A. count must be zero.
      • B. count must be CAPACITY.
      • C. count could be zero or CAPACITY, but no other values could occur.
      • D. None of the above.

    11. I have implemented the queue with a linked list, keeping track of a front pointer and a rear pointer. Which of these pointers will change during an insertion into a NONEMPTY queue?
      • A. Neither changes
      • B. Only front_ptr changes.
      • C. Only rear_ptr changes.
      • D. Both change.

    12. I have implemented the queue with a linked list, keeping track of a front pointer and a rear pointer. Which of these pointers will change during an insertion into an EMPTY queue?
      • A. Neither changes
      • B. Only front_ptr changes.
      • C. Only rear_ptr changes.
      • D. Both change.

      Multiple Choice
      Section 8.4
      Priority Queues

    13. Suppose top is called on a priority queue that has exactly two entries with equal priority. How is the return value of top selected?
      • A. The implementation gets to choose either one.
      • B. The one which was inserted first.
      • C. The one which was inserted most recently.
      • D. This can never happen (violates the precondition)


    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/chap08q.html
    Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
    Sample Data Structures Questions - Chapter 9

    Sample Data Structures Questions
    Chapter 9
    Recursive Thinking

    Data Structures and Other Objects Using C++
    by Michael Main and Walter Savitch
    Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


    The Purpose of These Questions

    These are typical exam questions from Chapter 9 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 12 short answer questions and 16 multiple choice questions in this file.

    Short Answers

      Short Answers
      Section 9.1
      Recursive
      Functions

    1. What is the importance of the stopping case in recursive functions?

    2. Write a recursive function that has one parameter which is a size_t value called x. The function prints x asterisks, followed by x exclamation points. Do NOT use any loops. Do NOT use any variables other than x.

    3. Implement the following function. Do not use any local variables or loops.
         void pattern(unsigned int n)
         // Precondition: n > 0;
         // Postcondition: The output consists of lines of integers. The first line
         // is the number n. The next line is the number 2n. The next line is
         // the number 4n, and so on until you reach a number that is larger than
         // 4242. This list of numbers is then repeated backward until you get back
         // to n.
         /* Example output with n = 840:
         840
         1680
         3360
         6720
         6720
         3360
         1680
         840
      

    4. Write a recursive function with two unsigned int parameters, m and n. The precondition requires 0 <= m and m <= n. The function prints a line of m asterisks, then a line of m+1 asterisks, and so on up to a line of n asterisks. Then the same pattern is repeated backward: a line of n asterisks, then n-1, and so on down to n. The only loop allowed in your implementation is a loop to print a line of m asterisks. You may have two copies of this loop in different places of the implementation.

    5. This question involves a game with teddy bears. The game starts when I give you some bears. You can then give back some bears, but you must follow these rules (where n is the number of bears that you have):
      1. If n is even, then you may give back exactly n/2 bears.
      2. If n is divisible by 3 or 4, then you may multiply the last two digits of n and give back this many bears. (By the way, the last digit of n is n%10, and the next-to-last digit is ((n%100)/10).
      3. If n is divisible by 5, then you may give back exactly 42 bears.
      The goal of the game is to end up with EXACTLY 42 bears.

      For example, suppose that you start with 250 bears. Then you could make these moves:
      --Start with 250 bears.
      --Since 250 is divisible by 5, you may return 42 of the bears, leaving you with 208 bears.
      --Since 208 is even, you may return half of the bears, leaving you with 104 bears.
      --Since 104 is even, you may return half of the bears, leaving you with 52 bears.
      --Since 52 is divisible by 4, you may multiply the last two digits (resulting in 10) and return these 10 bears. This leaves you with 42 bears.
      --You have reached the goal!

      Write a recursive function to meet this specification:

         bool bears(int n)
         // Postcondition: A true return value means that it is possible to win
         // the bear game by starting with n bears. A false return value means that
         // it is not possible to win the bear game by starting with n bears.
         // Examples:
         //   bear(250) is true (as shown above)
         //   bear(42) is true
         //   bear(84) is true
         //   bear(53) is false
         //   bear(41) is false
         // Hint: To test whether n is even, use the expression ((n % 2) == 0).
      

    6. Write a recursive function with this prototype (using the string type from the new C++ String class):
         void permute(string first, string second)
         // Postcondition: The output consists of lines of Strings. Each String
         // is made by writing some rearrangement of first followed by all
         // of second.
         // For example, if first is "CAT" and second is "MAN", then there will
         // be six lines of output:
         // CATMAN
         // ACTMAN
         // TCAMAN
         // CTAMAN
         // ATCMAN
         // TACMAN
      
      Hints: The stopping case occurs when the length of first is zero (in which case the function prints second). Some string member functions that will help you for a String s:
      • s[s.length( ) - 1] is a copy of the last character of s.
      • s.length( ) is the length of s.
      • cout << s << endl; will print s.
      • s = c + s; will insert the character c at the front of s.
      • s += c; will append the character c to the end of s.
      • s.erase(0, 1); will remove one character from the front of s.
      • s.erase(s.length( )-1, 1) will remove the last character from s.

    7. Write a function with this prototype:
        #include <strclass.h>
        void numbers(ostream& outs, const string& prefix, unsigned int levels);
      
      The function prints output to the ostream outs. The output consists of the string prefix followed by "section numbers" of the form 1.1., 1.2., 1.3., and so on. The levels argument determines how may levels the section numbers have. For example, if levels is 2, then the section numbers have the form x.y. If levels is 3, then section numbers have the form x.y.z. The digits permitted in each level are always '1' through '9'. As an example, if prefix is the string "THERBLIG" and levels is 2, then the function would print 81 strings. In this case, the function starts by printing:
      THERBLIG1.1.
      THERBLIG1.2.
      THERBLIG1.3.
      
      and ends by printing:
      THERBLIG9.7.
      THERBLIG9.8.
      THERBLIG9.9.
      
      The stopping case occurs when levels reaches zero (in which case the prefix is printed once by itself followed by nothing else).

      The string class from <string> has many manipulation functions, but you'll need only the ability to make a new string which consists of prefix followed by another character (such as '1') and a period ('.'). If s is the string that you want to create and c is the digit character (such as '1'), then the following statement will correctly form s:

        s = (prefix + c) + '.';
      
      This new string s can be passed as a parameter to recursive calls of the function.
      Short Answers
      Section 9.2
      Fractals
      and Mazes
    8. Write a function with one positive int parameter called n. The function will write 2^n-1 integers (where ^ is the exponentiation operation). Here are the patterns of output for various values of n:
      n=1: Output is: 1
      n=2: Output is: 1 2 1
      n=3: Output is: 1 2 1 3 1 2 1
      n=4: Output is: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
      And so on. Note that the output for n always consists of the output for n-1, followed by n itself, followed by a second copy of the output for n-1.

    9. What property of fractals lends itself to recursive thinking?

    10. The first step of the maze search algorithm was to step forward and write your name on the ground. What is the importance of writing your name on the ground?

    11. Consider the following function:
          bool dead_end()
          // Postcondition: The return value is true if the direction directly 
          // in front is a dead end (i.e., a direction that cannot contain the 
          // tapestry).
          // Library facilities used: useful.h (from Appendix 1).
          {
              return inquire("Are you facing a wall?")
                     ||
                     inquire("Is your name written in front of you?");
          }
      
      Explain why the function dead_end sometimes asks 2 questions and sometimes asks only 1.

      Short Answers
      Section 9.3
      Reasoning About
      Recursion

    12. What two properties must a variant expression have to guarantee that a recursive function terminates?

    Multiple Choice

      Multiple Choice
      Section 9.1
      Recursive Functions

    1. In a single function declaration, what is the maximum number of statements that may be recursive calls?
      • A. 1
      • B. 2
      • C. n (where n is the argument)
      • D. There is no fixed maximum

    2. What is the maximum depth of recursive calls a function may make?
      • A. 1
      • B. 2
      • C. n (where n is the argument)
      • D. There is no fixed maximum

    3. Consider the following function:
          void super_write_vertical(int number)
          // Postcondition: The digits of the number have been written, 
          // stacked vertically.  If number is negative, then a negative 
          // sign appears on top.  
          // Library facilities used: iostream.h, math.h
          {
              if (number < 0)
              {
                  cout << '-' << endl;
                  super_write_vertical(abs(number));
              }
              else if (number < 10)
                  cout << number << endl;
              else
              {
                  super_write_vertical(number/10);
                  cout << number % 10 << endl;
              }
          }
      
      What values of number are directly handled by the stopping case?
      • A. number < 0
      • B. number < 10
      • C. number >= 0 && number < 10
      • D. number > 10

    4. Consider the following function:
          void super_write_vertical(int number)
          // Postcondition: The digits of the number have been written, 
          // stacked vertically.  If number is negative, then a negative 
          // sign appears on top.  
          // Library facilities used: iostream.h, math.h
          {
              if (number < 0)
              {
                  cout << '-' << endl;
                  super_write_vertical(abs(number));
              }
              else if (number < 10)
                  cout << number << endl;
              else
              {
                  super_write_vertical(number/10);
                  cout << number % 10 << endl;
              }
          }
      
      Which call will result in the most recursive calls?
      • A. super_write_vertical(-1023)
      • B. super_write_vertical(0)
      • C. super_write_vertical(100)
      • D. super_write_vertical(1023)

    5. Consider this function declaration:
          void quiz(int i)
          {
              if (i > 1)
              {
                  quiz(i / 2);
      	    quiz(i / 2);
              }
              cout << "*";
          }
      
      How many asterisks are printed by the function call quiz(5)?
      • A. 3
      • B. 4
      • C. 7
      • D. 8
      • E. Some other number

    6. This question is appropriate if you studied a flood fill (which was not part of the text). Suppose that a flood fill starts at the point marked with an o in this diagram:
       XXXXXXXXXX
       XX    XXXX  This is row number 1
       XX XX XXXX  This is row number 2
       XX   o XXX  This is row number 3
       XXXXXXXXXX
      
      Suppose that the first recursive call is always left; the second recursive call is always right; the third recursive call is always up; the fourth recursive call is always down. How will the rows be completely filled?
      • A. Row 1 is filled first, then row 2, then row 3
      • B. Row 1 is filled first, then row 3, then row 2
      • C. Row 2 is filled first, then row 3, then row 1
      • D. Row 3 is filled first, then row 1, then row 2
      • E. Row 3 is filled first, then row 2, then row 1

    7. In a real computer, what will happen if you make a recursive call without making the problem smaller?
      • A. The operating system detects the infinite recursion because of the "repeated state"
      • B. The program keeps running until you press Ctrl-C
      • C. The results are nondeterministic
      • D. The run-time stack overflows, halting the program

    8. When the compiler compiles your program, how is a recursive call treated differently than a non-recursive function call?
      • A. Parameters are all treated as reference arguments
      • B. Parameters are all treated as value arguments
      • C. There is no duplication of local variables
      • D. None of the above

    9. When a function call is executed, which information is not saved in the activation record?
      • A. Current depth of recursion.
      • B. Formal parameters.
      • C. Location where the function should return when done.
      • D. Local variables.

    10. Consider the following function:
          void test_a(int n)
          {
             cout << n << " ";
             if (n>0)
                test_a(n-2);
          }
      
      What is printed by the call test_a(4)?
      • A. 0 2 4
      • B. 0 2
      • C. 2 4
      • D. 4 2
      • E. 4 2 0

    11. Consider the following function:
          void test_b(int n)
          {
             if (n>0)
                test_b(n-2);
             cout << n << " ";
          }
      
      What is printed by the call test_b(4)?
      • A. 0 2 4
      • B. 0 2
      • C. 2 4
      • D. 4 2
      • E. 4 2 0

      Multiple Choice
      Section 9.2
      Fractals
      and Mazes

    12. Suppose you are exploring a rectangular maze containing 10 rows and 20 columns. What is the maximum number of calls to traverse_maze that can be generated if you start at the entrance and call traverse_maze?
      • A. 10
      • B. 20
      • C. 30
      • D. 200

    13. Suppose you are exploring a rectangular maze containing 10 rows and 20 columns. What is the maximum depth of recursion that can result if you start at the entrance and call traverse_maze?
      • A. 10
      • B. 20
      • C. 30
      • D. 200

    14. What is the relationship between the maximum depth of recursion for traverse_maze and the length of an actual path found from the entrance to the tapestry?
      • A. The maximum depth is always less than or equal to the path length.
      • B. The maximum depth is always equal to the path length.
      • C. The maximum depth is always greater than or equal to the path length.
      • D. None of the above relationships are always true.

      Multiple Choice
      Section 9.3
      Reasoning about
      Recursion

    15. What would a suitable variant expression be for the traverse_maze function which could be used to prove termination? Assume N is the number of rows in the maze and M is the number of columns.
      • A. N + M
      • B. N + M + 1
      • C. N * M
      • D. The number of unexplored spaces in the maze.

    16. What technique is often used to prove the correctness of a recursive function?
      • A. Communitivity.
      • B. Diagonalization.
      • C. Mathematical induction.
      • D. Matrix Multiplication.


    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/chap09q.html
    Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
    Sample Data Structures Questions - Chapter 10

    Sample Data Structures Questions
    Chapter 10
    Trees

    Data Structures and Other Objects Using C++
    by Michael Main and Walter Savitch
    Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


    The Purpose of These Questions

    These are typical exam questions from Chapter 10 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 20 short answer questions and 20 multiple choice questions in this file.

    Short Answers

      Short Answers
      Section 10.1
      Introduction
      to Trees

    1. Here is a small binary tree:
             14
            /  \
           2    11
          / \   / \
         1  3  10  30
               /  /            
              7  40
      
      Circle all the leaves. Put a square box around the root. Draw a star around each ancestor of the node that contains 10. Put a big X through every descendant of the node the contains 10.

    2. Draw a full binary tree with at least 6 nodes.

      Short Answers
      Section 10.2
      Tree
      Representations

    3. Draw a complete binary tree with exactly six nodes. Put a different value in each node. Then draw an array with six components and show where each of the six node values would be placed in the array (using the usual array representation of a complete binary tree).

    4. Write the private member variables for a new node definition that could be used for a node in a tree where: (1) Each node contains int data, (2) Each node has up to four children, and (3) Each node also has a pointer to its parent. Store the pointers to the children in an array of four pointers.

      Short Answers
      Section 10.3
      A Toolkit for
      Binary Tree Nodes

    5. Draw a binary taxonomy tree that can be used for these four animals: Rabbit, Horse, Whale, Snake.

    6. Using the binary_tree_node from page 465, write a function to meet the following specification. Check as much of the precondition as possible. No recursion is needed.
      template <class Item>
      void subswap(binary_tree_node<Item>* root_ptr)
      // Precondition: root_ptr is the root pointer of a non-empty binary tree.
      // Postcondition: The original left subtree has been moved and is now the right
      // subtree, and the original right subtree is now the left subtree.
      // Example original tree:            Example new tree:
      //          1                                 1
      //         / \                               / \
      //        2   3                             3   2
      //       / \                                   / \
      //      4   5                                 4   5
      

    7. template <class Item> Using the binary_tree_node from page 465, write a recursive function to meet the following specification. Check as much of the precondition as possible.
      template <class Item>
      void flip(binary_tree_node<Item>* root_ptr)
      // Precondition: root_ptr is the root pointer of a non-empty binary tree.
      // Postcondition: The tree is now the mirror image of its original value.
      // Example original tree:            Example new tree:
      //          1                                 1
      //         / \                               / \
      //        2   3                             3   2
      //       / \                                   / \
      //      4   5                                 5   4
      

      Short Answers
      Section 10.4
      Tree
      Traversals

    8. Here is a small binary tree:
             14
            /  \
           2    11
          / \   / \
         1  3  10  30
               /  /            
              7  40
      
      Write the order of the nodes visited in:
      A. An in-order traversal:
      B. A pre-order traversal:
      C. A post-order traversal:

    9. Using the binary_tree_node from page 465, Write a recursive function to meet the following specification. You do not need to check the precondition.
      template <class Item>
      void increase(binary_tree_node<Item>* root_ptr)
      // Precondition: root_ptr is the root pointer of a binary tree.
      // Postcondition: Every node of the tree has had its data increased by one.
      

    10. Using the binary_tree_node from page 465, write a recursive function to meet the following specification. You do not need to check the precondition.
      template <class Item>
      size_t many_nodes(binary_tree_node<Item>* root_ptr)
      // Precondition: root_ptr is the root pointer of a binary tree.
      // Postcondition: The return value is the number of nodes in the tree.
      // NOTES: The empty tree has 0 nodes, and a tree with just a root has
      // 1 node.
      

    11. Using the binary_tree_node from page 465, write a recursive function to meet the following specification. You do not need to check the precondition.
      template <class Item>
      int tree_depth(binary_tree_node<Item>* root_ptr)
      // Precondition: root_ptr is the root pointer of a binary tree.
      // Postcondition: The return value is the depth of the binary tree.
      // NOTES: The empty tree has a depth of -1 and a tree with just a root
      // has a depth of 0.
      

    12. Using the binary_tree_node from page 465, write a function to meet the following specification. You do not need to check the precondition.
      template <class Item>
      size_t count42(binary_tree_node<Item>* root_ptr)
      // Precondition: root_ptr is the root pointer of a binary tree (but
      // NOT NECESSARILY a search tree).
      // Postcondition: The return value indicates how many times 42 appears
      // in the tree. NOTE: If the tree is empty, the function returns zero.
      

    13. Using the binary_tree_node from page 465, write a function to meet the following specification. You do not need to check the precondition.
      template <class Item>
      bool has_42(binary_tree_node<Item>* root_ptr)
      // Precondition: root_ptr is the root pointer of a binary tree (but
      // NOT NECESSARILY a search tree).
      // Postcondition: The return value indicates whether 42 appears somewhere
      // in the tree. NOTE: If the tree is empty, the function returns false.
      

    14. Using the binary_tree_node from page 465, write a function to meet the following specification. You do not need to check the precondition.
      template <class Item>
      bool all_42(binary_tree_node<Item>* root_ptr)
      // Precondition: root_ptr is the root pointer of a binary tree (but
      // NOT NECESSARILY a search tree).
      // Postcondition: The return value is true if every node in the tree
      // contains 42. NOTE: If the tree is empty, the function returns true.
      

    15. Using the binary_tree_node from page 465, write a recursive function to meet the following specification. You do not need to check the precondition.
      template <class Item>
      int sum_all(binary_tree_node<Item>* root_ptr)
      // Precondition: root_ptr is the root pointer of a binary tree.
      // Postcondition: The return value is the sum of all the data in all the nodes.
      // NOTES: The return value for the empty tree is zero.
      

      Short Answers
      Section 10.5
      Binary Search
      Trees

    16. Suppose that we want to create a binary search tree where each node contains information of some data type called Item (which has a default constructor and a correct value semantics). What additional factor is required for the Item data type?

    17. Suppose that a binary search tree contains the number 42 at a node with two children. Write two or three clear sentences to describe the process required to delete the 42 from the tree.

    18. Using the binary_tree_node from page 465, write a function to meet the following specification. You do not need to check the precondition. Make the function as efficient as possible (do not visit nodes unnecessarily):
      template <class Item>
      size_t count42(binary_tree_node<Item>* root_ptr)
      // Precondition: root_ptr is the root pointer of a binary SEARCH tree.
      // Postcondition: The return value indicates how many times 42 appears
      // in the tree.
      

    19. Using the binary_tree_node from page 465, write a function to meet the following specification. You do not need to check the precondition. Make the function as efficient as possible (do not visit nodes unnecessarily):
      template <class Item>
      int max(binary_tree_node<Item>* root_ptr)
      // Precondition: root_ptr is the root pointer of a nonempty binary SEARCH
      // tree.
      // Postcondition: The return value is the largest value in the tree.
      

    20. Using the binary_tree_node from page 465, write a function to meet the following specification. You do not need to check the precondition.
      template <class Item>
      void insert_one_42(binary_tree_node<Item>*& root_ptr)
      // Precondition: root_ptr is the root pointer of a binary SEARCH tree.
      // Postcondition: One copy of the number 42 has been added to the binary
      // search tree.
      

    Multiple Choice

      Multiple Choice
      Section 10.1
      Introduction
      to Trees
             14
            /  \
           2    11
          / \   / \
         1  3  10  30
               /  /            
              7  40
      
    1. There is a tree in the box at the top of this section. How many leaves does it have?
      • A. 2
      • B. 4
      • C. 6
      • D. 8
      • E. 9

    2. There is a tree in the box at the top of this section. How many of the nodes have at least one sibling?
      • A. 5
      • B. 6
      • C. 7
      • D. 8
      • E. 9

    3. There is a tree in the box at the top of this section. What is the value stored in the parent node of the node containing 30?
      • A. 10
      • B. 11
      • C. 14
      • D. 40
      • E. None of the above

    4. There is a tree in the box at the top of this section. How many descendants does the root have?
      • A. 0
      • B. 2
      • C. 4
      • D. 8

    5. There is a tree in the box at the top of this section. What is the depth of the tree?
      • A. 2
      • B. 3
      • C. 4
      • D. 8
      • E. 9

    6. There is a tree in the box at the top of this section. How many children does the root have?
      • A. 2
      • B. 4
      • C. 6
      • D. 8
      • E. 9

    7. Consider the binary tree in the box at the top of this section. Which statement is correct?
      • A. The tree is neither complete nor full.
      • B. The tree is complete but not full.
      • C. The tree is full but not complete.
      • D. The tree is both full and complete.

    8. What is the minimum number of nodes in a full binary tree with depth 3?
      • A. 3
      • B. 4
      • C. 8
      • D. 11
      • E. 15

    9. What is the minimum number of nodes in a complete binary tree with depth 3?
      • A. 3
      • B. 4
      • C. 8
      • D. 11
      • E. 15

    10. Select the one true statement.
      • A. Every binary tree is either complete or full.
      • B. Every complete binary tree is also a full binary tree.
      • C. Every full binary tree is also a complete binary tree.
      • D. No binary tree is both complete and full.

    11. Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T?
      • A. 0
      • B. 3
      • C. 4
      • D. 5

    12. Select the one FALSE statement about binary trees:
      • A. Every binary tree has at least one node.
      • B. Every non-empty tree has exactly one root node.
      • C. Every node has at most two children.
      • D. Every non-root node has exactly one parent.

      Multiple Choice
      Section 10.2
      Tree
      Representations

    13. Consider the binary_tree_node from page 465. Which expression indicates that t represents an empty tree?
      • A. (t == NULL)
      • B. (t->data( ) == 0)
      • C. (t->data( ) == NULL)
      • D. ((t->left( ) == NULL) && (t->right( ) == NULL))

    14. Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child's value be stored?
      • A. data[i+1]
      • B. data[i+2]
      • C. data[2*i + 1]
      • D. data[2*i + 2]

      Multiple Choice
      Section 10.3
      A Toolkit for
      Binary Tree Nodes

    15. How many recursive calls usually occur in the implementation of the tree_clear function for a binary tree?
      • A. 0
      • B. 1
      • C. 2

    16. Suppose that a binary taxonomy tree includes 8 animals. What is the minimum number of NONLEAF nodes in the tree?
      • A. 1
      • B. 3
      • C. 5
      • D. 7
      • E. 8

      Multiple Choice
      Section 10.4
      Tree
      Traversals
             14
            /  \
           2    11
          / \   / \
         1  3  10  30
               /  /            
              7  40
      

    17. There is a tree in the box at the top of this section. What is the order of nodes visited using a pre-order traversal?
      • A. 1 2 3 7 10 11 14 30 40
      • B. 1 2 3 14 7 10 11 40 30
      • C. 1 3 2 7 10 40 30 11 14
      • D. 14 2 1 3 11 10 7 30 40

    18. There is a tree in the box at the top of this section. What is the order of nodes visited using an in-order traversal?
      • A. 1 2 3 7 10 11 14 30 40
      • B. 1 2 3 14 7 10 11 40 30
      • C. 1 3 2 7 10 40 30 11 14
      • D. 14 2 1 3 11 10 7 30 40

    19. There is a tree in the box at the top of this section. What is the order of nodes visited using a post-order traversal?
      • A. 1 2 3 7 10 11 14 30 40
      • B. 1 2 3 14 7 10 11 40 30
      • C. 1 3 2 7 10 40 30 11 14
      • D. 14 2 1 3 11 10 7 30 40

      Multiple Choice
      Section 10.5
      Binary Search
      Trees

    20. Consider this binary search tree:
             14
            /  \
           2    16
          / \    
         1   5 
            /    
           4     
      
      Suppose we remove the root, replacing it with something from the left subtree. What will be the new root?
      • A. 1
      • B. 2
      • C. 4
      • D. 5
      • E. 16


    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/chap10q.html
    Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
    Sample Data Structures Questions - Chapter 11

    Sample Data Structures Questions
    Chapter 11
    Trees Projects

    Data Structures and Other Objects Using C++
    by Michael Main and Walter Savitch
    Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


    The Purpose of These Questions

    These are typical exam questions from Chapter 11 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 14 short answer questions and 12 multiple choice questions in this file.

    Short Answers

      Short Answers
      Section 11.1
      Heaps

    1. Suppose that we want to create a heap where each node contains information of some data type called Item (which has a default constructor and a correct value semantics). What additional factor is required for the Item data type?

    2. A heap is a binary tree where the entries can be compared using the usual six comparison operations (that form a total order semantics). Write the two rules that the binary tree must follow in order for the structure to actually be a heap.

    3. Give two different reasons to explain why the following binary tree is not a heap:
                 91
                /  \
              77    46
             /  \     \
           68    81    11
      

    4. Draw a new heap that is created by inserting 82 into the following heap:
                910
                /  \
              77     66
             /  \    /  \
           68    1  3    11
      
    5. Draw a new heap that is created by removing one item from the following heap:
                910
                /  \
              77     66
             /  \    /  \
           68    1  3    11
      

    6. Suppose that you are performing a reheapification downward. Write a precise condition that describes the situation that causes the reheapification to stop.

    7. Suppose that you are performing a reheapification upward. Write a precise condition that describes the situation that causes the reheapification to stop.

      Short Answers
      Section 11.2
      B-Trees

    8. Suppose that a non-leaf node in a B-tree contains 42 entries. How many children does the node have?

    9. Draw an example of a B-tree with four nodes and seven integer entries. The value of MINIMUM is 1 for this tree.

    10. Draw a new B-tree that is created by inserting 82 into the following B-tree. For this example, the minimum number of items in each node is 1. Note that the rightmost leaf starts with two entries, 71 and 93.
                 56
                /  \
              7      66
             /  \    /  \
            2    8  63    71 and 93
      
    11. Draw a new B-tree that is created by deleting 63 from the following B-tree. For this example, the minimum number of items in each node is 1. Note that the rightmost leaf starts with two entries, 71 and 93.
                 56
                /  \
              7      66
             /  \    /  \
            2    8  63    71 and 93
      
    12. Suppose that a B-tree is declared so that MAXIMUM (the maximum number of items in a node) is 84. What is the value of MINIMUM (the minimum number of items in a non-root node)?
    13. Suppose that a B-tree is declared so that MAXIMUM (the maximum number of items in a node) is 84. Write one clear sentence to describe why each node's data array is set up to hold up to 85 items (one more than MAXIMUM).
      Short Answers
      Section 11.3
      Trees, Logs, and
      Time Analysis

    14. Suppose that a and b are two positive integers and n is some non-negative number. Write an equation to show the relationship between log base a of n and log base b of n. Give a derivation to show that the relationship is valid.

    Multiple Choice

      Multiple Choice
      Section 11.1
      Heaps
    1. What feature of heaps allows them to be efficiently implemented using a partially filled array?
      • A. Heaps are binary search trees.
      • B. Heaps are complete binary trees.
      • C. Heaps are full binary trees.
      • D. Heaps contain only integer data.

    2. If a heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value?
      • A. data[0]
      • B. data[n-1]
      • C. data[n]
      • D. data[2*n + 1]
      • E. data[2*n + 2]

    3. Select the true statement about the worst-case time for operations on heaps.
      • A. Niether insertion nor removal is better than linear.
      • B. Insertion is better than linear, but removal is not.
      • C. Removal is better than linear, but insertion is not.
      • D. Both insertion and removal are better than linear.

    4. Suppose that we have implemented a priority queue by storing the items in a heap (using an array for the heap items). We are now executing a reheapification upward and the out-of-place node is at data[i] with priority given by data[i]. Which of the following boolean expressions is TRUE to indicate that the reheapification IS NOT YET DONE.
      • A. (i > 0)
      • B. (data[(i-1)/2] < data[i])
      • C. (i > 0) && (data[(i-1)/2] < data[i])
      • D. (i > 0) || (data[(i-1)/2] < data[i])

    5. Suppose that we have implemented a priority queue by storing the items in a heap. We are now executing a reheapification downward and the out-of-place node has priority of 42. The node's parent has a priority of 72, the left child has priority 52 and the node's right child has priority 62. Which statement best describes the status of the reheapification.
      • A. The reheapification is done.
      • B. The next step will interchange the two children of the out-of-place node.
      • C. The next step will swap the out-of-place node with its parent.
      • D. The next step will swap the out-of-place node with its left child.
      • E. The next step will swap the out-of-place node with its right child.

    6. Which formula is the best approximation for the depth of a heap with n nodes?
      • A. log (base 2) of n
      • B> The number of digits in n (base 10)
      • C. The square root of n
      • D. n
      • E. The square of n

      Multiple Choice
      Section 11.3
      B-trees

    7. Which statement is true for a B-tree?
      • A. All entries of a node are greater than or equal to the entries in the node's children.
      • B. All leaves are at the exact same depth.
      • C. All nodes contain the exact same number of entres.
      • D. All non-leaf nodes have the exact same number of children.

    8. Suppose that a non-leaf node in a B-tree has 41 entries. How many children will this node have?
      • A. 2
      • B. 40
      • C. 41
      • D. 42
      • e. 82

    9. Suppose that a B-tree has MAXIMUM of 10 and that a node already contains the integers 1 through 10. If a new value, 11, is added to this node, the node will split into two pieces. What values will be in these two pieces?
      • A. The first piece will have only 1 and the second piece will have the rest of the numbers.
      • B. The first piece will have 1 through 5 and the second piece will have 6 through 11.
      • C. The first piece will have 1 through 5 and the second piece will have 7 through 11.
      • D. The first piece will have 1 through 6 and the second piece will have 7 through 11.
      • E. The first piece will have 1 through 10 and the second piece will have only 11.

    10. Suppose that X is a B-tree leaf containing 41 entries and having at least one sibling. Which statement is true?
      • A. Any sibling of X is also a leaf.
      • B. Any sibling of X contains at least 41 entries.
      • C. The parent of X has exactly 42 entries.
      • D. X has at least 41 siblings.

      Multiple Choice
      Section 11.3
      Trees, Logs,
      and Time Analysis

    11. Suppose you run a O(log n) algorithm with an input size of 1000 and the algorithm requires 110 operations. When you double the input size to 2000, the algorithm now requires 120 operations. What is your best guess for the number of operations required when you again double the input size to 4000?
      • A. 130
      • B. 140
      • C. 150
      • D. 160
      • E. 170

    12. Tree algorithms typically run in time O(d) . What is d?
      • A. The depth of the tree.
      • B. The number of divisions at each level.
      • C. The number of entries in each node.
      • D. The number of nodes in the tree.
      • E. The total number of entries in all the nodes of the tree.


    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/chap11q.html
    Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
    Sample Data Structures Questions - Chapter 12

    Sample Data Structures Questions
    Chapter 12
    Searching

    Data Structures and Other Objects Using C++
    by Michael Main and Walter Savitch
    Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


    The Purpose of These Questions

    These are typical exam questions from Chapter 12 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 10 short answer questions and 10 multiple choice questions in this file.

    Short Answers

      Short Answers
      Section 12.1
      Serial Search and
      Binary Search

    1. Here is an array with exactly 15 elements:
       1   2   3   4   5   6   7   8   9   10   11   12   13   14   15
      
      Suppose that we are doing a serial search for an element. Circle any elements that will be found by examining two or fewer numbers from the array.

    2. Here is an array with exactly 15 elements:
       1   2   3   4   5   6   7   8   9   10   11   12   13   14   15
      
      Suppose that we are doing a binary search for an element. Circle any elements that will be found by examining two or fewer numbers from the array.

    3. Implement the body of the following function using a binary search of the array. You do not need to check the precondition. All your local variables must be size_t variables.
          bool has_42(const int data[ ], size_t n)
          // Precondition: The elements data[0]...data[n-1] are sorted from smallest
          // to largest. The value of n might be zero (indicating an empty
          // array).
          // Postcondition: A true return value indicates that the number 42 appears in
          // data[0]...data[n-1]. A false return value indicates that 42 doesn’t appear.
      

      Short Answers
      Section 12.2
      Open-Address
      Hashing

    4. Draw a hash table with open addressing and a size of 9. Use the hash function "k%9". Insert the keys: 5, 29, 20, 0, 27 and 18 into your table (in that order).

    5. Suppose you are building an open address hash table with double hashing. The hash table capacity is n, so that the valid hash table indexes range from 0 to n. Fill in the blanks:
      • In order to ensure that every array position is examined, the value returned by the second hash function must be ________________________ with respect to n.
      • One way to ensure this good behavior is to make n be _______________, and have the return value of the second hash function range from _________ to _________ (including the end points).

      Short Answers
      Section 12.3
      Chained
      Hashing

    6. You are writing code for the remove member function of a chained hash table. Fill in the blanks in this pseudocode with the two missing statements. You may use pseudocode yourself, or write actual C++ code:
          void Table::remove(int key)
          {
              Node cursor;
              size_t i;
      
              1. i = hash(key);
      
              2. Make cursor point to the node that contains an item with the given key
                 (or set it to NULL if there is no such node).
      
              3. if (cursor != NULL)
                 {
                 3a. _____________________________________________________________
                 
                 3b. _____________________________________________________________
                 }
      

    7. Draw a hash table with chaining and a size of 9. Use the hash function "k%9" to insert the keys 5, 29, 20, 0, and 18 into your table.

    8. Suppose that I have the following record_type definition for a record in a hash table:
          struct record_type
          {
              int key;
              ... other stuff may also appear here ...
          };
      
      The hash table uses open addressing with linear probing. The table size is a global constant called CAPACITY. Locations of the table that have NEVER been used will contain the key -1. Locations of the table that were once used but are now vacant will contain the key -2. All valid keys will be non-negative, and the hash function is:
          size_t hash(int key)
          {
              return (key % CAPACITY);
          }
      
      Complete the implementation of the following function. There is no need to check the precondition, but your code must be as efficient as possible.
      bool key_occurs(const record_type data[ ], int search_key)
      // Precondition: data[0]...data[CAPACITY-1] is an open address hash table
      // as described above.
      // Postcondition: If search_key occurs as a key of a record in the table, then
      // the function returns true; otherwise the function returns false.
      

      Short Answers
      Section 12.4
      Time Analysis
      of Hashing

    9. Suppose that an open-address hash table has a capacity of 811 and it contains 81 elements. What is the table's load factor? (An appoximation is fine.)

    10. I plan to put 1000 items in a hash table, and I want the average number of accesses in a successful search to be about 2.0.

      A. About how big should the array be if I use open addressing with linear probing? NOTE: For a load factor of A, the average number of accesses is generally ½(1+1/(1-A)).

      B. About how big should the array be if I use chained hashing? NOTE: For a load factor of A, the average number of accesses is generally (1+A/2).

    Multiple Choice

      Multiple Choice
      Section 12.1
      Serial Search and
      Binary Search

    1. What is the worst-case time for serial search finding a single item in an array?
      • A. Constant time
      • B. Logarithmic time
      • C. Linear time
      • D. Quadratic time

    2. What is the worst-case time for binary search finding a single item in an array?
      • A. Constant time
      • B. Logarithmic time
      • C. Linear time
      • D. Quadratic time

    3. What additional requirement is placed on an array, so that binary search may be used to locate an entry?
      • A. The array elements must form a heap.
      • B. The array must have at least 2 entries.
      • C. The array must be sorted.
      • D. The array's size must be a power of two.

      Multiple Choice
      Section 12.2
      Open-Address
      Hashing

    4. What is the best definition of a collision in a hash table?
      • A. Two entries are identical except for their keys.
      • B. Two entries with different data have the exact same key.
      • C. Two entries with different keys have the same exact hash value.
      • D. Two entries with the exact same key have different hash values.

    5. Which guideline is NOT suggested from from empirical or theoretical studies of hash tables:
      • A. Hash table size should be the product of two primes.
      • B. Hash table size should be the upper of a pair of twin primes.
      • C. Hash table size should have the form 4K+3 for some K.
      • D. Hash table size should not be too near a power of two.

    6. In an open-address hash table there is a difference between those spots which have never been used and those spots which have previously been used but no longer contain an item. Which function has a better implementation because of this difference?
      • A. insert
      • B. is_present
      • C. remove
      • D. size
      • E. Two or more of the above functions

    7. What kind of initialization needs to be done for an open-address hash table?
      • A. None.
      • B. The key at each array location must be initialized.
      • C. The head pointer of each chain must be set to NULL.
      • D. Both B and C must be carried out.

      Multiple Choice
      Section 12.3
      Chained
      Hashing

    8. What kind of initialization needs to be done for an chained hash table?
      • A. None.
      • B. The key at each array location must be initialized.
      • C. The head pointer of each chain must be set to NULL.
      • D. Both B and C must be carried out.

    9. A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?
      • A. 256
      • B. 511
      • C. 512
      • D. 1024
      • E. There is no maximum.

      Multiple Choice
      Section 12.4
      Time Analysis
      of Hashing

    10. Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?
      • A. s + m
      • B. s - m
      • C. m - s
      • D. m * s
      • E. m / s


    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/chap12q.html
    Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
    Sample Data Structures Questions - Chapter 13

    Sample Data Structures Questions
    Chapter 13
    Sorting

    Data Structures and Other Objects Using C++
    by Michael Main and Walter Savitch
    Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


    The Purpose of These Questions

    These are typical exam questions from Chapter 13 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 14 short answer questions and 12 multiple choice questions in this file.

    Short Answers

      Short Answers
      Section 13.1
      Quadratic Sorting
      Algorithms

    1. Here is an array of ten integers:
            5  3  8  9  1  7  0  2  6  4
      
      Draw this array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest).

    2. Here is an array of ten integers:
            5  3  8  9  1  7  0  2  6  4
      
      Draw this array after the FIRST iteration of the large loop in an insertion sort (sorting from smallest to largest). This iteration has shifted at least one item in the array!

    3. Suppose that you are writing a program that has the usual selectionsort function available:
          void selectionsort(int data[ ], size_t n);
      
      Your program also has an integer array called x, with 10 elements. Write two function calls: The first call uses selectionsort to sort all of x; the second call uses selectionsort to sort x[3]..x[9].

      Short Answers
      Section 13.2
      Recursive Sorting
      Algorithms

    4. Describe a case where quicksort will result in quadratic behavior.

    5. Here is an array which has just been partitioned by the first step of quicksort:
            3, 0, 2, 4, 5, 8, 7, 6, 9
      
      Which of these elements could be the pivot? (There may be more than one possibility!)

    6. Give a concise accurate description of a good way for quicksort to choose a pivot element. Your approach should be better than "use the entry at location [0]".

    7. Give a concise accurate description of a good way for quicksort to improve its performance by using insertionsort.

    8. Here is an array of ten integers:
            5  3  8  9  1  7  0  2  6  4
      
      Suppose we partition this array using quicksort's partition function and using 5 for the pivot. Draw the resulting array after the partition finishes.

    9. Here is an array of ten integers:
            5  3  8  9  1  7  0  2  6  4
      
      Draw this array after the TWO recursive calls of merge sort are completed, and before the final merge step has occured.

    10. Implement the following function:
          void merge(int data[ ], size_t n1, size_t n2);
          // Precondition: The first n1 elements of data are sorted, and the 
          // next n2 elements of data are sorted (from smallest to largest).
          // Postcondition: The n1+n2 elements of data are now completely
          // sorted.
      

      Short Answers
      Section 13.3
      An O(n log n) Algorithm
      Using a Heap

    11. Write two or three clear sentences to describe how a heapsort works.

    12. Fill in the following table for the times to sort an array of n items. Use only big-O notation, and do not have any extraneous constants in your expressions.
      Worst Case Average Case
      Binary search of a sorted array ..
      Insertion sort ..
      Merge sort ..
      Quick sort without "median of three" pivot selection ..
      Quick sort with "median of three" pivot selection ..
      Selection sort ..
      Heap sort ..

      Short Answers
      Beyond the Book

    13. Suppose that you are writing a program that has these two functions available:
          int compare_ints(const void* p1, const void* p2);
          // Precondition: p1 and p2 are really pointers to integers.
          // Postcondition: The return value is:
          //   (a) negative if *p1 < *p2
          //   (b) zero if *p1 == *p2
          //   (c) positive if *p1 > *p2
      
          void qsort(
              void* base,
              size_t n,
              size_t bytes,
              int compar(const void*, const void*)
          );
          // Same specification as the standard library qsort function. 
      
      Your program also has an integer array called x, with 10 elements. Write two function calls: The first call uses qsort to sort all of x; the second call uses qsort to sort x[3]..x[9].

    14. Suppose that you implement quicksort nonrecursively using a stack, as in your last programming assignment. You use your algorithm to sort an array of 100 items, and at the start of the final iteration of the while loop, the stack contains just two numbers: 10 (on top) and 90 (on bottom). Write one or two clear sentences to describe which parts of the array are sorted at this point, and which parts of the array remain to be sorted.

    Multiple Choice

      Multiple Choice
      Section 13.1
      Quadratic Sorting
      Algorithms

    1. In a selectionsort of n elements, how many times is the swap function called in the complete execution of the algorithm?
      • A. 1
      • B. n - 1
      • C. n log n
      • D. n²

    2. Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?
      • A. O(n log n) sorts
      • B. Divide-and-conquer sorts
      • C. Interchange sorts
      • D. Average time is quadratic.

    3. Suppose that a selectionsort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?
      • A. 21
      • B. 41
      • C. 42
      • D. 43

    4. Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:
          1  2  3  4  5  0  6  7  8  9
      
      Which statement is correct? (Note: Our selectionsort picks largest items first.)
      • A. The algorithm might be either selectionsort or insertionsort.
      • B. The algorithm might be selectionsort, but could not be insertionsort.
      • C. The algorithm might be insertionsort, but could not be selectionsort.
      • D. The algorithm is neither selectionsort nor insertionsort.

    5. Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:
          2  4  5  7  8  1  3  6
      
      Which statement is correct? (Note: Our selectionsort picks largest items first.)
      • A. The algorithm might be either selectionsort or insertionsort.
      • B. The algorithm might be selectionsort, but it is not insertionsort.
      • C. The algorithm is not selectionsort, but it might be insertionsort.
      • D. The algorithm is neither selectionsort nor insertionsort.

    6. When is insertionsort a good choice for sorting an array?
      • A. Each component of the array requires a large amount of memory.
      • B. Each component of the array requires a small amount of memory.
      • C. The array has only a few items out of place.
      • D. The processor speed is fast.

      Multiple Choice
      Section 13.2
      Recursive Sorting
      Algorithms

    7. What is the worst-case time for mergesort to sort an array of n elements?
      • A. O(log n)
      • B. O(n)
      • C. O(n log n)
      • D. O(n²)

    8. What is the worst-case time for quicksort to sort an array of n elements?
      • A. O(log n)
      • B. O(n)
      • C. O(n log n)
      • D. O(n²)

    9. Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
      • A. The array elements form a heap.
      • B. Elements in each half of the array are sorted amongst themselves.
      • C. Elements in the first half of the array are less than or equal to elements in the second half of the array.
      • D. None of the above.

    10. Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:
          2  5  1  7  9  12  11  10
      
      Which statement is correct?
      • A. The pivot could be either the 7 or the 9.
      • B. The pivot could be the 7, but it is not the 9.
      • C. The pivot is not the 7, but it could be the 9.
      • D. Neither the 7 nor the 9 is the pivot.

    11. What is the worst-case time for heapsort to sort an array of n elements?
      • A. O(log n)
      • B. O(n)
      • C. O(n log n)
      • D. O(n²)

      Multiple Choice
      Section 13.3
      An O(n log n) Algorithm
      Using a Heap

    12. Suppose we are sorting an array of eight integers using heapsort, and we have just finished one of the reheapifications downward. The array now looks like this:
          6  4  5  1  2  7  8
      
      How many reheapifications downward have been performed so far?
      • A. 1
      • B. 2
      • C. 3 or 4
      • D. 5 or 6


    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/chap13q.html
    Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
    Sample Data Structures Questions - Chapter 14

    Sample Data Structures Questions
    Chapter 14
    Software Reuse with Derived Classes

    Data Structures and Other Objects Using C++
    by Michael Main and Walter Savitch
    Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


    The Purpose of These Questions

    These are typical exam questions from Chapter 14 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 8 short answer questions and 10 multiple choice questions in this file.

    Short Answers

      Short Answers
      Section 14.1
      Derived Classes

    1. Write one or two sentences to describe the primary advantage of implementing a derived class. Your answer should use the word "inherited" at least once.

    2. If the programmer doesn't declare any constructors for a derived class, an automatic default constructor will be provided by the compiler. What steps will this default constructor carry out?

    3. If the programmer doesn't declare a destructor for a derived class, an automatic destructor will be provided by the compiler. What steps will this destructor carry out?

      Short Answers
      Section 14.2
      An Ecosystem Simulation

    4. Describe one purpose of a member initialization list for a derived class.

    5. When is it appropriate to use a container class of pointers to objects (rather than a container class of actual objects)?

    6. In the pond life simulation program, the weeds in the pond were represented by a variable weeds with the declaration:
      Bag weeds;
      The constructor for the Plant class has two arguments: the initial size of the plant (in ounces) and the growth rate of the plant (in ounces/week). Write a for-loop that will put pointers to 100 new plants in the weeds bag. Each plant should have an initial size of 15 ounces, and a growth rate of 2.5 ounces/week.

      Short Answers
      Section 14.3
      Using Derived Classes
      for ADTs

    7. Describe the difference between a public base class and a private base class.

    8. Suppose that a derived class has a private base class. How is it possible to to make some of the inherited members become public?

    Multiple Choice

      Multiple Choice
      Section 14.1
      Derived Classes
      Throughout this section,
      A is a class and B is
      a new class derived from A.
      Also, we have these variables:
      A a;
      B b;
      B b1;
      B b2;

    1. What C++ syntax is used to declare that a class B is derived from class A?
      • A. class A derives B { ... };
      • B. class B from A { ... };
      • C. class B : public A { ... };
      • D. class B subclass of A { ... };

    2. If a class B is derived from A, then which of the following terms describes A?
      • A. ancestor class.
      • B. base class.
      • C. parent class.
      • D. superclass.
      • E. All of the above.

    3. Using the variable declarations at the top of this section, which of the following assignment statements are legal?
      • A. a = b;
      • B. b = a;
      • C. b1 = b2;
      • D. Both (A) and (B) are legal, but not (C).
      • E. Both (A) and (C) are legal, but not (B).
      • F. Both (B) and (C) are legal, but not (A).

    4. Consider the assignment statement a=b; (with the variable declarations at the top of this section). Which answer is true?
      • A. The assignment statement is illegal.
      • B. The assignment statement activates the A assignment operator.
      • C. The assignment statement activates the B assignment operator.
      • D. The assignment statement activates both A and B assignment operators.

    5. Consider the assignment statement b=a; (with the variable declarations at the top of this section). Which answer is true?
      • A. The assignment statement is illegal.
      • B. The assignment statement activates the A assignment operator.
      • C. The assignment statement activates the B assignment operator.
      • D. The assignment statement activates both A and B assignment operators.

    6. What is the term used to describe the situation when a derived class provides a function already provided in the base class?
      • A. Inheriting.
      • B. Overriding.

    7. Consider the declarations at the top of this section. Suppose there are two functions: f has an argument of type A and g has an argument of type B. Which statement is correct?
      • A. Both f(b) and g(b) are legal function calls.
      • B. f(b) is legal, but g(b) is not legal.
      • C. f(b) is not legal, but g(b) is legal.
      • D. Neither f(b) nor g(b) is a legal function function call.

    8. Consider the declarations at the top of this section. Suppose there are two functions: f has an argument of type A and g has an argument of type B. Which statement is correct?
      • A. Both f(a) and g(a) are legal function calls.
      • B. f(a) is legal, but g(a) is not legal.
      • C. f(a) is not legal, but g(a) is legal.
      • D. Neither f(a) nor g(a) is a legal function function call.

      Multiple Choice
      Section 14.3
      Using Derived Classes
      for ADTs

    9. Suppose you were going to quickly implement a Stack class. What class would be the best base class?
      • A. Bag.
      • B. List.
      • C. Queue.
      • D. Table.

    10. Suppose you were going to quickly implement a Stack class as a derived class. Why would it be likely that the base class would be a private base class?
      • A. You would not want to have all of the base classes private member functions be private member functions of the stack.
      • B. You would not want to have all of the base classes private member functions be public member functions of the stack.
      • C. You would not want to have all of the base classes public member functions be private member functions of the stack.
      • D. You would not want to have all of the base classes public member functions be public member functions of the stack.


    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/chap14q.html
    Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group
    Sample Data Structures Questions - Chapter 15

    Sample Data Structures Questions
    Chapter 15
    Graphs

    Data Structures and Other Objects Using C++
    by Michael Main and Walter Savitch
    Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000


    The Purpose of These Questions

    These are typical exam questions from Chapter 15 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 8 short answer questions and 10 multiple choice questions in this file.

    Short Answers

      Short Answers
      Section 15.1
      Graph Definitions

    1. Draw a directed graph with five vertices and seven edges. Exactly one of the edges should be a loop, and do not have any multiple edges.

    2. Draw an undirected graph with five edges and four vertices. The vertices should be called v1, v2, v3 and v4--and there must be a path of length three from v1 to v4. Draw a squiggly line along this path from v1 to v4.

      Short Answers
      Section 15.2
      Graph Implementations

    3. Draw the directed graph that corresponds to this adjacency matrix:
                0       1       2       3
          0  |  true    false   true    false  |
          1  |  true    false   false   false  |
          2  |  false   false   false   true   |
          3  |  true    false   true    false  |
      

    4. Draw the edge lists that correspond to the graph from the previous question.

    5. What are the benefits of using an external iterator as opposed to an internal iterator?

      Short Answers
      Section 15.3-15.4
      Graph Traversals
      and Path Algorithms

    6. How may Djikstra's algorithm be modified to determine if it is possible to get from a given vertex to all other vertices in the graph?

    7. In Djikstra's shortest path algorithm, what technique is used to choose the next vertex to process?

    8. Consider this graph:
                          v0 <------- v2
                         / \
                        /   \
               -> v1 <-/     \-> v4
              /    \     
             /      \
            /        \->v3 -------> v5
           /            /
          /            /
         v6 <---------/
      
      In what order are the vertices visited for a depth-first search that starts at v0? In what order are the vertices visited for a breadth-first search that starts at v0?

    Multiple Choice

      Multiple Choice
      Section 15.1
      Graph Definitions

    1. Which of the following statements is true?
      • A. A graph can drawn on paper in only one way.
      • B. Graph vertices may be linked in any manner.
      • C. A graph must have at least one vertex.
      • D. A graph must have at least one edge.

    2. Suppose you have a game with 5 coins in a row and each coin can be heads or tails. What number of vertices might you expect to find in the state graph?
      • A. 7
      • B. 10
      • C. 25
      • D. 32

    3. Why is the state graph for tic-tac-toe a directed graph rather than an undirected graph?
      • A. Once a move is made, it cannot be unmade.
      • B. There is an odd number of vertices.
      • C. There is an odd number of edges.
      • D. There is more than one player in the game.

    4. A simple graph has no loops. What other property must a simple graph have?
      • A. It must be directed.
      • B. It must be undirected.
      • C. It must have at least one vertex.
      • D. It must have no multiple edges.

    5. Suppose you have a directed graph representing all the flights that an airline flies. What algorithm might be used to find the best sequence of connections from one city to another?
      • A. Breadth first search.
      • B. Depth first search.
      • C. A cycle-finding algorithm.
      • D. A shortest-path algorithm.

      Multiple Choice
      Section 15.2
      Graph Implementations

    6. If G is an directed graph with 20 vertices, how many boolean values will be needed to represent G using an adjacency matrix?
      • A. 20
      • B. 40
      • C. 200
      • D. 400

    7. How many linked lists are used to represent a graph with n nodes and m edges, when using an edge list representation,
      • A. m
      • B. n
      • C. m + n
      • D. m*n

    8. How are loops represented in an edge-list representation of a graph?
      • A. A vertex will be on its own edge-list.
      • B. The edge-list will be a circular linked list.
      • C. The edge-list will be empty for that particular vertex.
      • D. The edge-list will be full for that particular vertex.

      Which graph representation allows the most efficient determination of the existence of a particular edge in a graph?

      • A. An adjacency matrix.
      • B. Edge lists.

    9. What is the expected number of operations needed to loop through all the edges terminating at a particular vertex given an adjacency matrix representation of the graph? (Assume n vertices are in the graph and m edges terminate at the desired node.)
      • A. O(m)
      • B. O(n)
      • C. O(m²)
      • D. O(n²)

      Multiple Choice
      Section 15.3-15.4
      Graph Traversals
      and Path Algorithms

    10. What graph traversal algorithm uses a queue to keep track of vertices which need to be processed?
      • A. Breadth-first search.
      • B. Depth-first search.


    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/chap15q.html
    Copyright © 2000 Addison-Wesley Computer and Engineering Publishing Group