-
True or False. Write 'T' for True and 'F' for False for each of
the following statements:
- _T_ Searching an unordered array of n elements on average requires a number of comparisons proportional to n.
- _F_ Using binary search on an array of n elements requires a number of comparisons proportional to 2n.
- _F_ Bubble Sort on an array of n elements can require a number of comparisons proportional to log n.
- _F_ The Sieve of Eratosthenes is an efficient algorithm for sorting strings.
- _T_ After 10 iterations of the outer loop of Selection Sort, the first 10 elements of the array are in order.
- _T_ The 1000th Fibonacci number can be represented in the computer using arrays.
- _T_ The statement if ("hello") printf ("something"); will print something.
- _F_ The sequence of statements int a; a = 0; if (a = 0) printf ("something"); will print something.
- _F_ The first parameter to main is an array of characters.
- _T_ A string in C is represented by an array of characters where the last character is the value 0.
- _F_ The fgets function from the standard C library is considered unsafe.
- _T_ Each of the three expressions in a for statement is optional.
- _T_ A pointer can be thought of as the address of a variable together with the type of the variable.
- _T_ Pointers can point to array elements.
- _F_ A function that accepts a pointer parameter must return a value.
- Write a C function that accepts an integer parameter n
and returns the number of prime numbers between 2 and n.
solution:
int countprimes (int k) {
int n, i, found_a_factor, count = 0;
for (n=2; n<=k; n++) {
found_a_factor = 0;
for (i=2; i <= n-1; i++)
if (n % i == 0) found_a_factor = 1;
if (found_a_factor == 0)
count++;
}
return count;
}
- Write a C function that accepts two paramters: array, which
is an array of integers, and n, which is the size of the array.
The function should return the average of the numbers in the array as
a double.
solution:
double average (int array[], int n) {
double sum = 0.0;
int i;
for (i=0; i<n; i++)
sum += array[i];
return sum / n;
}
- Write a C function that accepts three parameters: array,
which is an array of double, n, which is the size of
the array, and val, which is a double. The function
should return the index of the array element that is closest to val
without exceeding val. If all of the elements exceed val,
then the function should return -1.
solution:
#include <stdio.h>
int find_closest (double array[], int n, double val) {
int i, mini = 0;
for (i=1; i<n; i++) {
if (array[i] <= val) {
double d = val - array[i];
double e = val - array[mini];
if (d < e || e < 0) mini = i;
}
}
if (array[mini] > val) return -1;
return mini;
}
- What is the output of the following program?
#include <stdio.h>
void m1 (int *p) {
*p = *p + 1;
}
void m2 (int p) {
p = p - 1;
}
int main () {
int x, *q;
x = 1;
printf ("%d\n", x);
m1 (&x);
printf ("%d\n", x);
q = &x;
m1 (q);
m2 (x);
printf ("%d\n", x);
return 0;
}
solution:
1
2
3
- Consider the following function. It is suppose to find the mean
squared error between two arrays v and w, where
each array contains n elements. That is, it should find the
average value of the square of the difference between corresponding array
elements in the two arrays. However, there are several errors that will
prevent the code from compiling and/or working properly. List at least five
errors. (You may list more than five errors, but for every wrong response
we will take off points.)
double mse (double v[], w[], int n) {
double d, sumsq;
for (i=0; i<=n; i++) {
d = v[i] - w[i];
sumsq += d * d;
}
return d / n;
}
solution:
- sumsq is not initialized
- '<=' should be just '<' in the for statement
- the function should return sumsq / n, not d / n
- the variable 'w' is not given a type (should be double w[])
- the variable 'i' is not declared (should be int i)
- there is the potential for a divide by zero error if n is zero