UMBC CMSC202, Computer Science II, Fall 1998, Sections 0101, 0102, 0103, 0104

Sample Exam

Warning: Do not study from this sample exam

Instructions:

• This is a 75-minute, closed-book, closed-notes exam.
• Calculators are not allowed --- you won't need them.
• Print your name, fill in your student identification number, and check the discussion section where you would like to receive the graded exam.

True-False Questions: 1 point each

Circle one of TRUE or FALSE after each question.

1. Mergesort is much faster when the input is already sorted than when the input is in random order.

   TRUE       FALSE

2. The binary search algorithm is best described as an O(n) algorithm.

   TRUE       FALSE

3. The function 7 n² + 10 n log(n) is O(n log(n)).

   TRUE       FALSE

4. If p is a pointer to int then the statement p = (int *) malloc(152) ; allocates enough memory for an array of 152 int's.

   TRUE       FALSE

5. The function free() is used to determine the largest block of memory that malloc() can currently reserve.

   TRUE       FALSE

6. In C, a pointer to void always points to NULL.

   TRUE       FALSE

7. The "list" abstract data type must be implemented using singly- or doubly-linked lists.

   TRUE       FALSE

8. In a circular linked list, the "next" field of the last node points to the "header" node.

   TRUE       FALSE

9. When a call to malloc() returns NULL because the system does not have enough memory, the situation is called a "memory leak".

   TRUE       FALSE

10. C uses a "garbage collector" to recover dynamically allocated memory that is not used any more.

    TRUE       FALSE

Multiple Choice Questions: 2 points each

1. Suppose that the C expression p[i] has type int. Then the type of p can be:
   1. int
   2. pointer to int
   3. pointer to an array of int
   4. none of the above
    

2. Suppose that sizeof(int) is 4 and that the address value stored in the int pointer ptr is 4294946208. Then after the statement ptr++ ; the address value stored in ptr is:
   1. 4294946209
   2. 4294946212
   3. 4294946224
   4. any of the above
    

3. For programs running under UNIX, a "segmentation fault" occurs when
   1. A program tries to access memory reserved for the operating system
   2. A program tries to access memory reserved for another user
   3. A program tries to dereference a NULL pointer
   4. all of the above.
    

4. When we call realloc() to increase the amount of memory allocated for an array, we follow a strategy that doubles the size of the array instead of increasing the size of the array by 1 because:
   1. this strategy reduces the amount of time that the system might spend copying.
   2. this strategy reduces the amount of memory used by the program.
   3. this strategy reduces the probability of a segmentation fault.
   4. all of the above
    

5. In a C file, after the type declaration typedef struct tag { struct tag * foo ; double r ; } bar ;
   1. the field foo is a record of type bar.
   2. the field foo is a type.
   3. the field foo is a pointer to a record of type bar.
   4. the field foo is a pointer to a linked list.
    

6. Consider the following declarations: typedef struct node_tag { char *item ; struct node_tag *next ; } node ; typedef struct { node header ; int count ; node *last ; } *list ; list L ; Which of the following expressions has type char, assuming that all the necessary memory has been allocated?
   1. L.header.item[3]
   2. L.header->item[3]
   3. L->header.item[3]
   4. L->header->item[3]
    

7. The purpose of the "header" node in a singly-linked list is:
   1. to keep track of the last node in the linked list
   2. to keep track of the first node in the linked list
   3. to keep track of the number of elements in the linked list
   4. to simplify the C code for inserting new nodes into the linked list
    

8. Each node of a doubly-linked list contains one more pointer than a singly-linked list. This extra pointer is used to:
   1. point to the previous node in the linked list
   2. point to the "header" node
   3. point to the last node in the list
   4. none of the above
    

9. An advantage of linked lists over dynamically allocated arrays is:
   1. linked lists generally use less memory
   2. the size of a dynamically allocated array must be known when the program is compiled
   3. inserting at the beginning of a linked list is faster than inserting at the beginning of an array
   4. all of the above
    

10. An advantage of dynamically allocated arrays over linked lists is:
    1. arrays generally use less memory
    2. C code for arrays is somewhat simpler than C code for linked lists
    3. binary search can be used with a sorted array, but not with a sorted linked list
    4. all of the above
     

Short Answer Questions: 4 points each

In the following questions, no syntax errors have been put in deliberately. (So, "there is a syntax error" is not the right answer and will receive no credit.) Please mark your final answer clearly. In order to receive partial credit, you must show your work.

1. Consider the following recursive function: int foobar (int n) { if (n == 0) return 0 ; if (n < 0) return foobar(-n) ; return foobar(n-1) + 2*n - 1 ; }

   • What value is returned by foobar(-3) ?

   • What value is returned by foobar(4) ?

   • What value is returned by foobar(5) ?

   • Describe in less than 10 words the mathematical function that the function foobar() computes.
    

2. Write a recursive function with the function prototype int IsSorted(int A[], int low, int high) ;

   Your function must determine whether the array A is sorted in increasing order between indices low and high inclusively. If the array is so sorted, your function must return the value 1; otherwise the return value must be 0. Your function must be recursive and must implement the following recursive strategy:

   An array is sorted in increasing order if and only if the first element is less than or equal to the second element and the array without the first element is sorted in increasing order.

   Note: the statement above does not cover any base cases.

3. Write a function MakeFloatArray() which takes an integer parameter n and returns a pointer to float. This pointer must point to the first element of an array of n elements, each of which has type float. Memory for the array must be dynamically allocated. If memory allocation fails, your function should return a NULL pointer. Finally, each element of the array must be initialized to the value 1.0.

4. Two-dimensional arrays. Write down the output of the following program. Note: this program has been compiled and runs without causing a segmentation fault or bus error. Answers that say "segmentation fault" or "bus error" will receive zero credit. #include <stdio.h>: typedef int array[4] ; main () { array SA[4], *aptr ; int i, j, *iptr ; for (i = 0 ; i < 4 ; i++) { for (j = 0 ; j < 4 ; j++) { SA[i][j] = 10 * i + j ; } } aptr = &(SA[2]) ; iptr = &((*aptr)[0]) ; for (i = 0 ; i < 4 ; i++) { printf("%d ", *(iptr + i) ) ; } printf("\n") ; }  

5. Write the type definitions, variable declarations, memory allocation statements and assignment statements that will construct the following data structure. All boxes that contain numbers have type int. All boxes that have arrows coming out of them are pointers. Except for memory for the variable ptr, memory for all boxes must be dynamically allocated. Thus, ptr is a pointer to a record whose second element is a pointer to int which points into an array of 4 elements, each of which is an int. If you have doubts about the type of a particular box, you may ask a proctor for a brief explanation.