THE HONG KONG POLYTECHNIC UNIVERSITY Spring 2020 COMP1011: Programming Fundamentals
Quiz 2, solutions
Date and time: Monday, 20 April 2020, 10:00 a.m. – 11:30 a.m.
1. No. For example, in the special case where the input search key is the element stored at the very beginning of the array a, linear search will use fewer comparisons than binary search to find it.
2.
// COMP1011_2020_Quiz_2_2.c: #include
#include
#include
#define TABLE_SIZE 5
int main(void) {
int a[TABLE_SIZE][TABLE_SIZE]; size_t i, j;
// Part (a):
srand(time(0));
for (i = 0; i < TABLE_SIZE; i++) {
for (j = 0; j < TABLE_SIZE; j++) a[i][j] = -10 + rand() % 21; printf("%3d ", a[i][j]);
}
printf("\n"); }
// Part (b):
j = 0;
int all_negative; do {
all_negative = 1;
for (i = 0; i < TABLE_SIZE; i++)
all_negative = all_negative &&
}
j++;
} while ((j < TABLE_SIZE) && !(all_negative)); printf("%s\n", all_negative ? "YES" : "NO");
}
3.
(a) If s1 and s2 point to two strings then the function f concatenates them, putting the second string at the end of the first string. The resulting string is stored in the string pointed to by s1 when the function is called. The function works as follows. First, the while-loop increases s1 until it points to ’\0’-character marking the end the first string. Next, the for-loop copies the second string to this location by copying the characters in the second string one by one.
The for-loop terminates when the ’\0’-character marking the end of the second string has been copied to the first string. The reason is that at this point, the value of the assignment *s1 = *s2 is 0, so the loop-continuation test fails.
(b) The issue is that the function f does not do any bounds checking on the memory locations that it writes to. If the concatenated string is too long to fit in the memory area reserved for storing s1, some characters from s2 will copied to memory locations lying outside that area. This may cause the program to crash.
{
{
(a[i][j] < 0);
1
4. // COMP1011_2020_Quiz_2_4.c: #include
#include
// Function from Fig. 7.15 in Chapter 7.6: void swap(int *element1Ptr , int *element2Ptr);
int main(void) {
int ballLeft = 1, ballMiddle = 0, ballRight = 0;
printf(“Input the sequence of swaps, where each swap is A, B, or C: “); char ch;
while ((ch = toupper(getchar())) != ’\n’) {
switch (ch) { case ’A’:
swap(&ballLeft, &ballMiddle); break;
case ’B’:
swap(&ballMiddle , &ballRight); break;
case ’C’:
swap(&ballLeft, &ballRight); break;
} }
printf(“The ball is under the “);
printf(“%s”, ballLeft ? “leftmost” : (ballMiddle ? “middle” : “rightmost”)); printf(” cup.\n”);
}
// Function from Fig. 7.15 in Chapter 7.6: void swap(int *element1Ptr , int *element2Ptr) {
int hold = *element1Ptr; *element1Ptr = *element2Ptr; *element2Ptr = hold;
}
5. // COMP1011_2020_Quiz_2_5.c:
double dot_product_A(const double x[], const double y[], size_t n) {
double result = 0;
size_t i;
for (i = 0; i < n; i++) {
result += x[i] * y[i]; }
return result; }
double dot_product_B(const double * const x, const double * const y, size_t n) {
double result = 0;
size_t i;
for (i = 0; i < n; i++) {
result += *(x + i) * *(y + i); }
return result; }
2