CSCI 2610
Answers to practice questions for quiz 4

  1. Write a function that has a single null-terminated string parameter. It should return 1 if the string contains an 'a', and 0 if it has no occurrences of the letter 'a'. Call it anyAs. For example, anyAs("cat") = 1, but anyAs("dog") = 0.

    Here are two solutions. 

      bool anyAs(char s[])
  {
    int i,len;
    len = strlen(s);
    for(i = 0; i < len; i++) {
      if(s[i] == 'a') return 1;
    }
    return 0;
  }

      bool anyAs(char s[])
  {
    int i;
    for(i = 0; s[i] != '\0'; i++) {
      if(s[i] == 'a') return 1;
    }
    return 0;
  }

  2. To within a constant factor (that is, in terms of proportionality) how much time does it take to sort an array of n integers using insertion sort?

    n2

  3. To within a constant factor, how long does it take to do a linear search of an array of n integers?

    n

  4. To within a constant factor, how long does it take to do a binary search of a sorted array of n integers?

    log2 n

  5. With an error of no more than 1, what is log base 2 of 2000?

    11. (Repeatedly divide by two, and count how many steps it takes to reach 1. When a fractional result occurs, round up to the next integer.)

  6. Given a 20x20 two-dimensional array T of integers, you would like to compute a single-dimensional array S of 20 integers, where for i = 0,1,...,19, S[i] is the sum T[i][0] + T[i][1] + T[i][2] + ... + T[i][19]. That is S[i] is the sum of all numbers in row i of of T. Write a function called rowSums that has T and S as parameters. It should assume that T already has values in it, and should compute the values of S as described. 
       void rowSums(int T[20][20], S[20])
   {
     int i,k,sum;
     for(i = 0; i < 20; i++) {
       sum = 0;
       for(k = 0; k < 20; k++) sum = sum + T[i][k];
       S[i] = sum;
     }
   }

  7. What would a function call to function rowSums of the preceding exercise, if it were being used to put the row sums of two-dimensional array Table into array Sums?

    rowSums(Table,Sums);

  8. When passing an array as a parameter to a function, you usually also pass the size of an array. That is not necessary when the array is a null-terminated string? Why not?

    You can get the length of a null-terminated string using strlen. So it is not necessary to be told the length. (Strlen does not work for all arrays. It only works for null-terminated strings.)