Computer Science 3510
Data Structures
Summer 1999
Exam 1

This is a closed book test. You may use one sheet of prepared notes. You have 90 minutes. Answer all of the questions.

1. 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.
   1. A null-terminated string of length 30 occupies 30 bytes.
   2. If Node is a type, then expression new Node[15] returns a pointer of type Node*.
   3. The heap is an area of memory that can change size while a program runs.
   4. Most dynamic storage allocation is done in the static area of memory.
   5. 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.
   6. Normally, function implementations are not placed in a header file.
   7. 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.
   8. 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
   9. A dangling pointer is pointer to memory that has been deleted.
   10. All data structures have a logical size that is determined when the program is compiled.
   11. You are allowed to add an integer to a pointer in C++.
   12. An abstract data type hides the way in which it is implemented.
2. 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.
3. The following C++ program is run. It causes a segmentation fault. Why?

   

4. What does the following function print when it is run?

   

5. 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;      
       }

6. 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.

       char* stutter(const char *s)

• About this document ...