CMSC--202 Computer Science II for Majors
Fall 1997 23 September 1997 Exam 1 Review

Exam 1 will be a full-period exam. The exam will be taken entirely from the following questions, although some of the questions may be changed in minor ways. One purpose of these review questions is to guide your studying for the exam. You could work every single problem in the review -- that should guarantee an excellent exam grade (and help you understand the material very well). Alternatively, you could notice that the problems fall into various categories -- be sure you can work representative problems in each category.

Another purpose of these review questions is to eliminate any possibility of ``trick'' questions on the exam. There are no tricks. No question on the exam should be a surprise to you. Every question on the exam will be substantially (or exactly) the same as one of these review questions.

Modules, Makefiles, etc.

Given the following code in the indicated files:

foo.c:

  


                  

                  
int main()        
{                 
  double x = 4.0; 
  ProcA(x);       
  ProcB();        
}

m1.h:

extern void ProcA(double);

m2.h:

extern void ProcB(void);

m1.c:

                              
                              
                              
                              
void ProcA(double y)          
{                             
  printf("%f\n", sqrt(y));    
}

m2.c:

void ProcB(void);
{
  int y;
  scanf("%d",&y);
}

Write any additional compiler directives such as #include, #ifndef, etc. needed in any file.
Write a simple makefile to compile the above code into an executable named foo. Each module ( i.e., foo.c, m1.c, and m2.c) must be separately compiled before linking into the executable.

Strings

Suppose you have the following function:

/* localMatch
 * Returns TRUE if, starting at word index word_i, each character of
 * pattern matches the corresponding character in word.  Example:
 * the pattern "abc" does match the word "qrsabcdef" at word index 3.
 * Returns FALSE otherwise.
 */
int localMatch(char * word, char * pattern, int word_i);

Show how to use localMatch to test for the occurrence of pattern at a given index in word.
Show how to use localMatch to test for the occurrence of pattern string at the end of word.
Show how to use localMatch to test for the occurrence of pattern anywhere in word.

Write a C function stringLength(char * s) that returns the length of the string s. Do not use strlen anywhere in the function. You may assume that s is a null-terminated array of char.

Recursion

Write a tail-recursive version of the following function.
```
int foo(int start, int finish)
{
  if (start == finish)
    return 0;
  return (1 + foo(start+1, finish));
}
```
What are the values of the parameters with which your function is to be called?
Write a recursive function
```
float Power(float x, unsigned n)
```
that computes x^n. n is a nonnegative integer.
[Hint: x^n can be defined by the following two equations:
```
  x^0 = 1.0
  x^n = x * x^(n-1)  for n >= 1
```
Write a recursive version of float Power(float x,unsigned n) that works by breaking n down into halves, squaring Power(x,n/2), and multiplying by x again if n was odd. For example,
```
      x^11 = x^5 * x^5 * x
      x^10 = x^5 * x^5
```
Write a recursive function,
```
int Mult(unsigned m,unsigned n)
```
to multiply two positive integers, m and n, using only repeated addition.
Write a recursive function int Product(int m,int n) which gives the product of the integers in the range m:n (m <= n)
Write a recursive function
```
    int Min(int A[], int n)
```
to find the smallest integer in the integer array A. n is the number of elements in A. Hint: define an auxiliary function Min2(A,k,j) that finds the smallest integer in A[k:j] and let Min(A,n) = Min2(A,0,n-1)
1. The function PrintChars, below, prints the string S, character-by-character, and returns the sum of N and the number of characters printed. Write a recursive function
```
   int PrintEmBackwards(char S[], int N)
```
  which prints the characters in reverse order, returning the same sum.
```
   int PrintChars(char S[], int N)
    {
      if (*S == '\0')
         return N;
      printf("%c",*S);
      return PrintChars(S + 1, N + 1);
    }
```
2. Notice that PrintChars is of the form
```
   int F(X)
     {
         if (P(X))
           return G(X);
         K(X);
         return F(H(X));
      }
```
  Identify F, X, P(X), G(X), K(X), and H(X).
3. Using your identifications above, write an iterative version of PrintChars.

For each of the following functions, determine if it is tail-recursive. Also determine if it is a correct recursive function; if not, explain why not in terms of the ``conditions for correct recursion.''

int foo (int bar)  /* bar is greater than zero */
{
  if (bar > 0) bar = bar - 1;
  return foo(bar/2);
}

int foo (int bar, int bell)
{
  if (bar >= bell)
    return foo(bar - bell, bell);
  return bar;
}

int foo (int bar)
{
  int gak;
  gak = getchar();
  if (gak == EOF) return 0;
  if (gak == 'Q') return foo(bar) + bar;
  return foo(bar) - bar;
}

1. Write a recursive C function
```
   int change_char (char A[], char old, char new)
```
  that takes a char array named A, a char named old and a char named new. Each occurrence of old in A is to be replaced by new. change_char returns the number of replacements made. Assume that A is null-terminated ( i.e., the last character in A is the '\0' character.) All array manipulations are to be done by pointer arithmetic (do not use subscript notation).
2. Rewrite change_char to use tail-recursion.
Write a recursive C function
```
  void double_char(char S[], char C, char T[])
```
that copies one string of characters into another one, replacing every instance of a given character with two copies of that character as it proceeds. Double_char takes three arguments: a string S to copy from (a null-terminated array of characters); a character C to double; and a string T to copy to (another array of characters). You may assume that T is large enough. For example, if the source string is "xyzzy" and the character to double is 'y', the target string ( i.e., the third argument) should be set to the string "xyyzzyy". Don't forget to terminate the target string with the ASCII null character ( i.e., with '\0'). All looping must be accomplished with recursion---you may not use any of C's iteration constructs. You may use a helper function if you like, but none is necessary.
Write a recursive C function
```
 void remove_char(char S[], char C, char T[])
```
that copies string S into string T removing every instance of character C as it proceeds. You may assume that T is of the appropriate size. For example, if S is "xyzzy", and C is 'y', then T should be set to the string "xzz". Don't forget to terminate the target string with the ASCII null character ( i.e., with '\0'). All looping must be accomplished with recursion---you may not use any of C's iteration constructs. You may use a helper function if you like, but none is necessary.
Write a recursive C function
```
   int count_digit(int digit, int numb)
```
that returns the number of occurrences of digit in the decimal representation of numb. digit is an int between zero and nine inclusive. For example, the call count_digit(8, 18488) should return 3, because there are three eights in the decimal representation of 18488. Recall that if num is an integer, then num/10 is the integer part of num divided by ten, while num%10 is the remainder of num divided by ten. These provide a way to split the problem into smaller pieces. All looping in your function must be accomplished with recursion---you may not use any of C's iteration constructs. You may use a helper function if you like, but none is necessary.
Write a recursive function that will count the number of occurrences of a given integer in an integer array. Your function count_occurrences should take three arguments: an array of ints, the number of elements in the array, and the integer occurrences of which in the array are to be counted.
Write a recursive function called count_7s, which counts the number of occurrences of the digit 7 in the decimal representation of a given integer. For example, if the argument to count_7s is 3762797, count_7s should return 3 (because there are three occurrences of the digit 7 in 3762797). Hint: remember that n%10 will give the remainder of n divided by ten, while n/10 will give the integer part of n divided by ten.
Write an iterative version of the tail-recursive function isPalindrome. The function returns 1 if the string S is a palindrome (reads the same forward and backward). It returns 0 if S is not a palindrome. The function is intended to be called with the parameter left equal to zero and the parameter right equal to strlen(S) - 1.
```
 int isPalindrome(char * S, int left, int right)
 {
   if (left >= right)
     return 1;  // true, S is a palindrome
   if (S[left] != S[right])
     return 0;  // false, S is not a palindrome
   return isPalindrome(S, left + 1, right - 1);
 }
```
Write an iterative version of the tail-recursive function isPalindrome. The function returns 1 if the string S is a palindrome (reads the same forward and backward). It returns 0 if S is not a palindrome. The function is intended to be called with the parameter left equal to zero and the parameter right equal to strlen(S) - 1.
```
 int isPalindrome(char * S, int left, int right)
 {
   if (left >= right)
     return 1;  // true, S is a palindrome
   if (S[left] != S[right])
     return 0;  // false, S is not a palindrome
   return isPalindrome(S, left + 1, right - 1);
 }
```

Pointers

All exercises in pointers handout.
All homework 3 problems.