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

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.

Here is a small function that uses the dynamic Bag class from Chapter 4:
         void quiz( )
         {
             size_t 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( )
         {
             size_t 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

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

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 NULL terminated 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.

struct Node
{int data;
      Node * link; };

Suppose we are using the above Node struct definition (with member variables 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 (with cout) all the numbers on the list.

Suppose we are using the above Node struct definition (with member variables called data and link), and that locate_ptr is pointing to a node in a linked list. Write an assignment 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 assignment statement should set locate_ptr to NULL.

Implement the following functions as new functions for the linked list class. (Use the above Node definition with member variables called data and link.)
 

size_t count_42s();
// 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.

bool has_42();
// 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.

bool all_42s();
// 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.

int sum();
// 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.

int product();
// 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.

void list_tail_insert(const int& 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.

bool data_is_on(int entry);
// Precondition: head_ptr is the head pointer of a linked list (which might be empty, or might be non-empty). The entry is an object that might be in the linked list.
// Postcondition: The return value is true if the data in entry 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.

void list_insert_zero();
// 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.

Suppose that p, q, and r are all pointers to nodes of type Node in a linked list with 5 nodes. The pointer p points to the first node, q points to the 3rd node, and r points to the last node. Write a few lines of code that will make a new copy of the list. Your 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 3rd node of the copy, and z points to the last node of the copy. Your code may NOT contain any loops.
 

For the Bag ADT vs. List ADT with a Doubly Linked List (like your program #5)
  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.

Suppose cursor points to a node in a linked list using the Node definition . What statement changes cursor so that it points to the next node?
          A. cursor++;
          B. cursor = link;
          C. cursor += link;
          D. cursor = cursor->link;

Suppose cursor points to a node in a linked list using the Node definition . 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.

What is the fundamental difference between a struct and a class?
          A. By default the members of structs are private.
          B. By default the members of structs are public.
          C. Structs can only contain data members.
          D. Structs must contain a pointer member variable.

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.

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.

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.

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;

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

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

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.

Why are external iterators sometimes needed instead of internal iterators?
          A. An internal iterator cannot have one traversal of the container's items followed by a second traversal.
          B. An internal iterator cannot have two simultaneous traversals of the container's items.
          C. An iternal iterator cannot easily be invalidated when the container's items change.
          D. All of the above.

Complete the body of this function. You do not need to check the precondition. You may use the CStack 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.

When answering these questions concerning stack behavior, assume that the CStack member functions work with integers. (You don't have to concern yourself with Node * or SuperNode * issues)

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

I am going to execute this code with THREE pushes and ONE pop:
        CStack 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|       |
                   |_______|

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:

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

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

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

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.

Consider the following pseudocode:
        declare a stack of characters
        while ( there are more characters in the word to read )
        {
           read a character
           push the character on the stack
        }
        while ( the stack is not empty )
        {
           pop a character off the stack
           write the character to the screen
        }
     What is written to the screen for the input "carpets"?
          A. serc
          B. carpets
          C. steprac
          D. ccaarrppeettss

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

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

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]

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.

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.

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.

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.

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

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

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.

I am going to execute this code with THREE inserts and ONE get_front ( DeQ() ):

        CQueue 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:

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

YOU MAY SKIP THE SECTION OF THE TEXT HERE THAT DISCUSSES PRIORITY QUEUES.
THAT MATERIAL WILL BE COVERED LATER WHEN WE COVER HEAPS.

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.

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

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 insert member function place the new entry in the array?
          A. data[1]
          B. data[2]
          C. data[11]
          D. data[12]

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.

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

In the linked-list version of the Queue class, which operations require linear time for their worst-case behavior?
          A. get_front
          B. insert
          C. is_empty
          D. None of these operations require linear time.

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

I have implemented the queue with a circular array, keeping track of front, rear, and count (the number of items in the array). Suppose front is zero, and rear 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.

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.

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.

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

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

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;

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 : class A { ... };
D. class B subclass of A { ... };
E. None of these.

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. All of the above.
E. None of these.

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.
E. None of these.

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.
E. None of these.

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.
C. Overloading.
D. Instantiating.
E. None of these.

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.
E. None of these.

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.
E. None of these.

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.
E. None of these.

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.
E. None of these.
 

Programming Questions

Be prepared to write any of the member functions that were a part of the Project #5 assignment

Be prepared to write any of the member functions that were a part of the Project #7 assignment

You may assume that you have CBag and Node classes defined as follows:
class CBag
{public:

void InsertHead(Node *);
void InsertTail(Node *);
Node * RemoveHead(Node *);
Node * RemoveTail(Node *);
bool isFull();
bool isEmpty();
bool Find(Node *);

private

Node * Head;
Node * Tail;
Node * Current;

};

class Node
{public:

Node * next;
Node * prev;

};