Sample Data Structures Questions

Sample Data Structures Questions
Chapter 4
Pointers and Dynamic Arrays

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

The Purpose of These Questions

These are typical exam questions from Chapter 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

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.

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

Draw a picture of memory after these statements:

    int i = 42;
    int k = 80;
    int* p1;
    int* p2;
    p1 = &i;
    p2 = &k;

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.

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

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.

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

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.

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.

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

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.

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?

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

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.

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

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.

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

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

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

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

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.

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

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.

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[ ]);

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

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

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.

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.

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.

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

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

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

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.

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

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];

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

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