Chapter 4
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;
Here is a function prototype:
void exam(const double
data[]);
Regarding the parameter; what is the effect
of the 'const'? what is the effect of the []s?
Consider the following declaration and prototype:
typedef int* IntPtr;
function foo (const
IntPtr p1, const int * p2);
Explain the differences between the types
of p1 and p2.
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. I.E. given Bag b1, b2; What is wrong with b1 = b2;?
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(
)
// Precondition: None
// 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 resize 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.
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 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.
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 foo(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 foo(a)?
A. 0
B. 1
C. address of
a
D. address of
x
E. None of the
above
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 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
{ typedef double Item;
Item 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 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 function as a new function 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.
Implement the following function as a new function for the linked list class. (Use the above Node definition with member variables called data and link.)
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.
Implement the following function as a new function for the linked list class. (Use the above Node definition with member variables called data and link.)
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.
Implement the following function as a new function for the linked list class. (Use the above Node definition with member variables called data and link. The data field is an int.)
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.
Implement the following function as a new function for the linked list class. (Use the above Node definition with member variables called data and link. The data field is an int.)
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.
Implement the following function as a new function for the linked list class. (Use the above Node definition with member variables called data and link.)
void list_tail_insert(const Node::Item& 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.Implement the following function as a new function for the linked list class. (Use the above Node definition with member variables called data and link.)
bool data_is_on(Node::Item entry);
// Precondition: head_ptr is the head pointer of a linked list (which might be empty, or might be non-empty). The Node:Item 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.Implement the following function as a new function for the linked list class. Do not call any of the other class functions from within your implementation. (Use the above Node definition with member variables called data and link.)
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 #6)
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.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 List that is implemented using a linked list.
Compare the worst-case big-O time analysis for these two functions: The remove function for the Bag that is implemented using a fixed-sized array, and the remove function for the List that is implemented using a linked list.
Compare the worst-case big-O time analysis for these two functions: The insert function for a List that is implemented using a fixed-sized array, and the insert function for a List that is implemented using a linked list.Compare the worst-case big-O time analysis for these two functions: The remove function for the List that is implemented using a fixed-sized array, and the remove function for the List that is implemented using a linked list.
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.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. occurrences
C. remove
D. None of the 1st 3.
E. TWO of the 1st 3.
F. ALL of the 1st 3.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
Suppose that the List is implemented with a linked list. Which of these operations are likely to have a constant worst-case time?
A. insert
B. occurrences
C. remove
D. None of the 1st 3
E. TWO of the 1st 3
F. ALL of the 1st 3What 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
Write one or two short sentences to clearly explain the advantage
of template functions.
Consider the code below which is supposed to shift the values from data[0] through data[n-1] rightward on position (so these values now reside in data[1] through data[n]).
size_t i;Complete the body of this template function. Check the precondition as much as possible, and don't cause a heap leak.
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.
template <typename Item>What is the primary purpose of template functions?
void list_head_remove()
// Precondition: head_ptr is the head pointer of a doubly 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.
Consider this prototype for a template function:
template <typename
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 );
Consider the following definition:
template <typename
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.
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.
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.)
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;
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 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.
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 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:
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|
|
|_______|
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
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
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:
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:_______ __________________________________
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 WITH HEAPS ON NOV. 13.
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.
Programming Questions
Be prepared to write InsertHead, InsertTail, InsertBefore, RemoveHead,
RemoveTail, Find or GetCurrent from homework program #7.