THE HONG KONG POLYTECHNIC UNIVERSITY Spring 2020 COMP1011: Programming Fundamentals
Quiz 2
Date and time: Monday, 20 April 2020, 10:00 a.m. – 11:30 a.m.
To submit your answers to the five questions below, put them in five separate files (one file for each question) named:
• “Q2-1-99999999Z.txt” or “Q2-1-99999999Z.pdf”, • “Q2-2-99999999Z.c”,
• “Q2-3-99999999Z.txt” or “Q2-3-99999999Z.pdf”, • “Q2-4-99999999Z.c”,
• “Q2-5-99999999Z.c”,
where “99999999Z” is your student ID number, and upload them to Blackboard before the deadline.
The maximum possible score is 10 marks. Late submissions will not be accepted. You are not allowed to discuss the quiz questions or your solutions with other people until after the deadline.
1. Suppose that a is a sorted array of 10, 000 elements and that we need to check whether or not an input search key is stored in a. Will the binary search technique be more efficient than the linear search technique for every possible search key? Justify your answer. (2 marks)
2. Write a C program that:
(a) Generates and prints a table with random integers between −10 and 10. The table should have five rows and five columns. At the start of your program, seed the random number generator with the current time and then call the rand()-function to obtain random numbers.
(b) Prints “YES” if the table has a column in which all entries are negative, and “NO” otherwise.
Two sample program outputs:
(2 marks)
3. Consider the following C function:
-5 -8
7 -5
-5 7
1 -1
7 -10
YES
4 -4 8 9 -7
-8 -5 -1 -9 -1
-2 -1 9 -8 8
-2 10 -4
5 5 0
-4 -2 -1
6 6 -7
-1 -7 -6
NO
6 2 4 3 9 -3 1 0
-6 5
void f(char *s1, const char *s2) {
while (*s1 != ’\0’) ++s1;
for (; *s1 = *s2; ++s1, ++s2) ;
}
(a) Describe what the function f does and how it works. When will the for-loop terminate? (b) f has a serious issue that can cause a program using it to crash. Explain what this issue is.
(2 marks)
(Continued −→)
4. A street magician places three identical, nontransparent cups upside down in a line on a table and puts a small ball under the leftmost cup (leftmost, from the audience’s point of view). He then shuffles the cups by performing a sequence of swaps, where each swap is one of the following operations:
• Type A: Swap the leftmost cup and the middle cup.
• Type B: Swap the middle cup and the rightmost cup. • Type C: Swap the leftmost cup and the rightmost cup.
Write a C program that asks the user to input a sequence of ’A’, ’B’, and ’C’ characters (ended by the newline character ’\n’), representing the sequence of swaps made by the magician, and then tells the user where the ball is located.
Two sample program outputs:
Input the sequence of swaps, where each swap is A, B, or C: ABCAB
The ball is under the rightmost cup.
Input the sequence of swaps, where each swap is A, B, or C: BBBB
The ball is under the leftmost cup.
(2 marks)
5. The dot product of two n-dimensional vectors x = (x0,x1,…,xn−1) and y = (y0,y1,…,yn−1) is n−1
defined as the sum xiyi = x0y0 +x1y1 +x2y2 +…+xn−1yn−1. i=0
(a) Write a C function named dot_product_A that returns the dot product of two n-dimensional vectors whose coordinates are stored in two arrays. Use array indexing. The function proto- type should be:
double dot_product_A(const double x[], const double y[], size_t n);
where x and y point to two arrays and n is the number of dimensions.
(b) Write a C function named dot_product_B that returns the same values as dot_product_A, but by using pointer/offset notation instead of array indexing. In other words, the program code of the function dot_product_B is not allowed to contain any square bracket characters (’[’ and ’]’). The function prototype should be:
double dot_product_B(const double * const x, const double * const y, size_t n);
where x and y point to two arrays and n is the number of dimensions.
For example, if we have defined:
double vector1[4] = {10, 0, -10, 0};
double vector2[4] = {1, 1.414, 0.88, 1011};
then both dot_product_A(vector1, vector2, 4) and dot_product_B(vector1, vector2, 4) should give the value 1.2. (2 marks)