This is a closed book test. You may use one 8.5x11 sheet of prepared notes, written on both sides. You have 90 minutes. Answer all of the questions.
Write a clearly legible T to the left of each of the following statements that is true, and a clearly legible F to the left of each that is false.
A null-terminated string of length 30 occupies 30 bytes. False (It occupies 31, one byte used for the null-terminator.)
If Node is a type, then expression new Node[15] returns a pointer of type Node*. True
The heap is an area of memory that can change size while a program runs. True
Most dynamic storage allocation is done in the static area of memory. False (It is done in the heap.)
Storing a value at a memory address that is a dangling pointer can cause some minor problems, but the program usually recovers from them quickly. False (It typically has catastrophic effects from which recovery is impossible.)
Normally, function implementations are not placed in a header file. True (Only a few function implementations, such as constructors for classes, are typically put into header files.)
A header file should always contain a prototype for every function contained in the corresponding implementation file, including prototypes for functions that are private to that module. False. The only private information that you put into a header file is information that you must put for some reason. You do not put a prototype for a static function, for example.
If a C++ program does not return memory to the free space pool when it is done with the memory, then the system will periodically sweep through memory and return unused memory to the free space pool automatically. False (If a program does not delete unused memory then the memory leaks away and can not be recovered by the program.)
A dangling pointer is pointer to memory that has been deleted. True
A hash table is an excellent tool to help to sort an array. False (Hash tables tend to mix up data, which has the opposite effect from sorting it.)
All data structures have a logical size that is determined when the program is compiled. False (Your modified hash tables, for example, can grow as more data is added to them.)
You are allowed to add an integer to a pointer in C++. True
An abstract data type hides the way in which it is implemented. True
Which of the following are part of an abstract data type specification? (Select all that apply.) (Selected ones are shown in blue.)
Suppose that the following structure definition is given.
struct Widget
{
int side;
char* front;
char bottom[22];
Widget(int s, char* f, char *b)
{
side = s;
front = f;
strcpy(bottom, b);
}
};
Show how to create a new widget called frodo with side = 4, front = "red" and bottom = "blue". Use the constructor.
How you do this depends on where you want to store this new Widget.
If you want it stored in the run-time stack, so that it will
automatically be deallocated when the current function returns,
use the following form.
Widget frodo(4, "red", "blue");
If you want it stored in the heap, so that it will only be
deallocated when you explicitly deallocate it, use the following form.
(This requires frodo to be a pointer to a Widget, of type Widget*.)
Widget* frodo = new Widget(4, "red", "blue");
Show how to create the same widget frodo without using
the constructor.
(Note: This implicitly uses a constructor without
a parameter. It can only be used if either no constructors are
defined or a constructor with no parameters is defined.)
To create frodo in the run-time stack, use the following form.
Widget frodo;
frodo.side = 4;
frodo.front = "red"
strcpy(frodo.bottom, "blue");
To create frodo in the heap, use the following form.
Widget* frodo;
frodo->side = 4;
frodo->front = "red"
strcpy(frodo->bottom, "blue");
The following C++ program is run. It causes a memory fault. Why? (Note: there was a problem with the html source of this question. It is fixed here.)
#include <iostream.h>
int main()
{
char* word;
cin >> word;
cout << word << endl;
return 0;
}
No memory is allocated for word. So the line cin >> word is using an uninitialized pointer, and tries to store a string at the memory address that the uninitialized pointer points to. You do not know where that will be.
What does the following function print when it is run?
void test()
{
int* s;
int* p = new int;
int* q = p;
int* r = new int;
*r = 17;
s = r;
*r = 41;
*q = *s;
p = s;
*r = 8;
r = q;
cout << "*p = " << *p << endl;
cout << "*q = " << *q << endl;
cout << "*r = " << *r << endl;
cout << "*s = " << *s << endl;
}
*p = 8
*q = 41
*r = 41
*s = 8
The key to getting this right is to do a careful hand simulation.
Do not cut corners. Show the pointers, and what they point to.
The following function is supposed to test whether two strings are the same, provided upper and lower case letters are treated as equal. That is, 'a' and 'A' should be considered the same letter. It is supposed to return 1 if the two strings are the same (when case is ignored) and 0 when they are not the same. For example, sameUpper("abc", "ABC") = 1, but sameUpper("abc", "AbD") = 0. This function works by copying each string, replacing lower case letters by upper case letters, and then using library function strcmp to tell whether the resulting strings are the same. (strcmp(s,t) returns 0 if strings s and t are equal, -1 if s comes before t in alphabetical order, and 1 if s comes after t in alphabetical order.) The function also uses function toupper, which converts a lower case letter to upper case, and returns all other characters unchanged. So toupper('a') = 'A' and toupper(':') = ':'. There is a serious mistake in this function. Explain what the mistake is, and rewrite the function to avoid the mistake. You might need to make more than one change, but try to keep the spirit of the method instead of choosing a completely different method. Make sure the external behavior of the function is correct.
bool sameUpper(char* x, char* y)
{
char *cpyx, *cpyy;
int xlen = strlen(x);
int ylen = strlen(y);
int i;
if(xlen != ylen) return 0;
for(i = 0; i <= xlen; i++) {
cpyx[i] = toupper(x[i]);
cpyy[i] = toupper(y[i]);
}
if(strcmp(cpyx, cpyy) == 0) return 1;
else return 0;
}
No memory is allocated for the copies. Just before the
for-loop, add
cpyx = new char[xlen + 1];
cpyy = new char[ylen + 1];
But now that these arrays have been allocated, we want to deallocate
them before returning. So replace the if-statement at the
end by
bool result;
if(strcmp(cpyx, cpyy) == 0) result = 1;
else result = 0;
delete [] cpyx;
delete [] cpyy;
return result;
Write a function called stutter that takes a null-terminated string s as a parameter and produces, in newly allocated memory, the string that results from repeating each character in s twice. For example, stutter("abaac") = "aabbaaaacc". It should return a pointer to the memory where the new string is stored.
There are many correct solutions. Here is one.
char* stutter(const char *s)
{
int slen = strlen(s);
char* result = new char[2*slen + 1];
for(int k = 0; k < slen; k++) {
result[2*k] = s[k];
result[2*k + 1] = s[k];
}
result[2*slen] = '\0';
return result;
}
When doing object-oriented programming, you typically find that functions have one less parameter than do corresponding functions that are used in procedural (non-object-oriented) computing. For example, a classical function to test whether a value x is present in a tree t has two parameters, x and t, but an object-oriented function has only one parameter, x. Explain why there is one less parameter.
In object-oriented programming, each function is part of an object. The function can refer to the object in which it resides implicitly, so that object is not an explicit parameter. It is an implicit parameter.
Suppose that structure Polynomial is defined as follows.
struct Polynomial {
int degree;
double* coef;
Polynomial(int n)
{
degree = n;
coef = new double[d+1];
}
};
Which of the following will create a polynomial with
degree 5?
Suppose that structure Polynomial and variable P are defined as in the preceding problem. Which of the following will set the coefficient of P at index 1 to hold 3.5?