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.)
- 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.)
- If variables A and B each have type char*, then
test A == B will have value 1 whenever the strings
pointed to by A and B have exactly the same characters
in them
False (A == B compares the pointers, to see if
the pointers are the same memory address. To compare strings,
use strcmp.)
- 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 (A stack, for example, can grow
as more data is added to it.)
- 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.)
- A type.
- Prototypes for functions in the abstract data type.
- A description of how the type is represented.
- Implementations of the functions.
- Conceptual meanings of the functions.
- 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.
Widget frodo(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.)
Widget frodo;
frodo.side = 4;
frodo.front = "red"
strcpy(frodo.bottom, "blue");
- 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.
Each function that belongs to an object can access the
object to which it belongs implicitly. So there is always
one implicit parameter, the object in which the function resides.
The implicit parameter is the one that occurs in front
of the dot when the function is used. For example, if you
write t.member(x), the implicit parameter is t. This compares
with member(t,x) for the non-object-oriented function.
- The following C++ program is run. It causes a segmentation
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.
- 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 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;
}