COMP 2011 Midterm - Fall 2014 - HKUST
Date: October 25, 2014 (Saturday)
Time Allowed: 2 hours, 2–4pm
Instructions: 1. This is a closed-book, closed-notes examination.
2. There are 9 questions on 18 pages (including this cover page).
3. Write your answers in the space provided in black/blue ink. NO pencil please.
4. All programming codes in your answers must be written in ANSI C++.
5. You may use only the C++ language features and constructs learned in the class
so far. For example, no pointers, C++ classes, string class, etc..
6. For programming questions, you are NOT allowed to define additional helper
functions or structures, nor global variables unless otherwise stated. You also
cannot use any library functions not mentioned in the questions.
Student Name
Student ID
Email Address
Lecture & Lab Section
Problem Score
1 / 15
2 /6
3 /6
For T.A. 4 /8
Use Only 5 / 12
6 / 12
7 / 18
8 / 11
9 / 12
Total / 100
1
Problem 1 [15 points] True or false
Indicate whether the following statements are true or false by circling T or F. You get 1.5
point for each correct answer, −0.5 for each wrong answer, and 0.0 if you do not answer.
T F (a) The enum keyword is used to define a new data type that consists of a finite set of named
integer variables.
T F (b) Any switch statement may be re-written as an if-else-if statement.
T F (c) The following piece of code will cause an infinite loop to run forever in practice, regardless
of what statements we put within the loop or outside the loop.
// statements
// ..
while (true)
{
// statements
// ...
}
T F (d) What is the truth value of x after running the following code?
bool x = true;
int j = 1;
if (j >= 3)
if (j > 7)
x = true;
else
x = false;
T F (e) The index of the last element of an array with n elements is n.
T F (f) If function A wants to call function B, then function B must be defined before the
definition of function A.
T F (g) Overloaded functions are functions with the same name but different return types.
2
T F (h) Given the following two functions
void f(int num);
int g(int num);
the following statement is illegal.
g(f(10));
T F (i) The following recursive function can be used to compute the factorial of any non-negative
integer (that is, any integer that is greater than or equal to zero) correctly.
int factorial(int n)
{
if (n < 0)
return -1;
else
return n ∗ factorial(n-1);
}
T F (j) Even the main function can be recursive. That is, the main function may also call itself.
For example, the following program is syntactically correct and runs with no errors.
#include <iostream>
using namespace std;
int x = 3;
int main( )
{
if (x <= 0)
return -1;
cout --x endl;
main( );
return 0;
}
3
Problem 2 [6 points] Arithmetic and Boolean Operators
Determine the output for each of the following program codes.
(a) [2 points]
int a = 10;
int b = 20;
cout ++a+b-- endl;
Answer:
(b) [2 points]
int x = 10;
int y = 20;
int& z = x;
if (y = z)
cout x endl;
else
cout y endl;
Answer:
(c) [2 points] Determine the truth value of the following boolean expression:
false || true && false || true
i. [1 point] if the || operator has a higher precedence than the && operator.
Answer:
ii. [1 point] if both of the || operator and the && operator have the same precedence
and they are right-associative.
Answer:
4
Problem 3 [6 points] Switch and enum
What is the output of each of the following programs that make use of enum or switch?
(a) [3 points]
#include <iostream>
using namespace std;
enum test { A, B = 32, C };
int main( )
{
cout A " " B " " C endl;
return 0;
}
Answer:
(b) [3 points]
#include <iostream>
using namespace std;
int main( )
{
int choice = 1;
switch (choice)
{
case 1: cout "HKUST" endl;
case 2: cout "HKU" endl;
case 3: cout "CUHK" endl;
default: cout "Error" endl;
}
return 0;
}
Answer:
5
Problem 4 [8 points] Loops and Continue
(a) [4 points] What is the output of the following program?
#include <iostream>
using namespace std;
int main( )
{
int rows = 4, k = 1;
for (int i = 1; i <= rows; ++i)
{
for (int j = 1; j <= i; ++j, ++k)
cout k ’ ’; // Print one space after the value of k
cout endl;
}
return 0;
}
Answer:
(b) [4 points] Now we add a continue statement. What is the new output?
#include <iostream>
using namespace std;
int main( )
{
int rows = 4, k = 1;
for (int i = 1; i <= rows; ++i)
{
for (int j = 1; j <= i; ++j, ++k)
{
if (k%2)
cout k ’ ’; // Print one space after the value of k
else
continue;
}
cout endl;
}
return 0;
}
Answer:
6
Problem 5 [12 points] Check If An Array Is Sorted By An Iterative Method and A
Recursive Method
(a) [5 points] Given an array of integers, check if the array elements are sorted in ascending
order (i.e., from the smallest to the largest) using an iterative function.
/∗ Inputs:
∗ x: an array of const integers
∗ size: size of the const integer array x
∗/
bool iterative check ascending(const int x[ ], int size)
{
// ANSWER: ADD YOUR CODE HERE
(b) [7 points] Repeat part (a) but using a recursive function.
/∗ Inputs:
∗ x: an array of const integers
∗ size: size of the const integer array x
∗/
bool recursive check ascending(const int x[ ], int size)
{
// ANSWER: ADD YOUR CODE HERE
7
Problem 6 [12 points] Parameter Passing
Determine the output of the following program which calls various functions using different
parameter passing methods.
#include <iostream>
using namespace std;
int A(int a, int& b)
{
a += b;
b += a;
return a+b;
}
int B(int& a, int b)
{
a += b;
b += a;
return a+b;
}
int C(int& a, int& b)
{
a += b;
b += a;
return a+b;
}
int D(int& a, int b)
{
a += b;
b += a;
return A(a,b)+b;
}
8
int main( )
{
int x = 0, y = 1;
cout A(x,y) endl;
cout B(x,y) endl;
cout C(x,y) endl;
cout x ’ ’ y endl; // Print one space
x = 0, y = 1; // Reset the values of x and y
cout D(x,y) endl;
return 0;
}
Answer:
9
Problem 7 [18 points] Sub-string in a Sentence
#include <iostream>
using namespace std;
const int LENGTH = 100;
void to lower case(const char input[ ], char result[ ]);
void only letters(const char input[ ], char result[ ]);
bool is substring(const char s1[ ], const char s2[ ]);
int main(void)
{
char input sentence[LENGTH]; // May contain any keyboard char except ’\n’
char s[LENGTH]; // Contains only English letters in lower case
char input in lower case[LENGTH]; // input sentence in lower case
char input with only letters[LENGTH]; // input with no non-English letters
cout "Enter a sentence: ";
cin.getline(input sentence, LENGTH);
to lower case(input sentence, input in lower case);
only letters(input in lower case, input with only letters);
cout "Enter a substring: ";
cin s; // Assume: s contains only English letters in lower case
cout boolalpha is substring(input with only letters, s) endl;
return 0;
}
The program above first reads in a sentence using the function cin.getline until the user
types in the newline character. Thus, the string, input_sentence consists of any character
one may type, including capital letters, punctuations, whitespaces and other symbols.
Then a simple string s is read in using the << operator of cin which is assumed to contain
only some combination of the 26 English letters in lower case. Now we want to check if the
string s is a substring of input_sentence using the boolean function is_substring. But
before we do so, we will first
1. convert all alphabetical characters in the input_sentence to their lower case by calling
the function to_lower_case, and
2. remove all non-alphabetical characters in the sentence by calling the function only_letters.
For example, if the input sentence is
10
A man, a plan, a canal: Panama.
After the first step of calling the function to_lower_case, it becomes
a man, a plan, a canal: panama.
Then after the second step of calling the function only_letters, it is turned into
amanaplanacanalpanama
And if the second input s is “ana” then the boolean function is_substring should return
true; on the other hand, if s is “hkust”, then it should return false.
Complete the definition of the 3 required functions on the following pages.
Remarks:
• You may assume that all inputs are valid and they consist of at most (LENGTH-1)
characters.
• You are NOT allowed to use any string library function except the following:
int strlen(const char str[ ]);
which may be used to get the length of any string str.
• You may define additional helper function(s) if you find the need to do so. Make sure
you indicate clearly where the helper functions will be put.
11
/∗ Part (a) [5 points]
∗ Copy the input C-string to the result C-string but change any capital
∗ letter in the input string to its lower case. Non-alphabetical characters
∗ are copied with no modification.
∗/
void to lower case(const char input[ ], char result[ ])
{
// ANSWER: ADD YOUR CODE HERE
}
/∗ Part (b) [5 points]
∗ Copy the input C-string to the result C-string but remove all
∗ non-alphabetical characters in the input.
∗/
void only letters(const char input[ ], char result[ ])
{
// ANSWER: ADD YOUR CODE HERE
12
/∗ Part (c) [8 points]
∗ Check if s2 is a substring of s1.
∗ Assumption: Both s1 and s2 contain only alphabetical characters in lower case.
∗/
bool is substring(const char s1[ ], const char s2[ ])
{
// ANSWER: ADD YOUR CODE HERE
13
Problem 8 [11 points] About Recursive Function Calls
int fibonacci(int n)
{
cout "Call fibonacci(" n ")" endl;
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
The recursive function above finds the nth fibonacci number where n is a non-negative integer.
(a) [4 points] Write down the output of the above function, int fibonacci(int n), when
the function is called with n = 3.
Answer:
(b) [7 points] Write another recursive function,
int num_fibonacci_calls(int n);
which returns the total number of fibonacci function calls when it is called with the in-
put n. Table 1 give some examples of the returned values of num_fibonacci_calls(int)
for different values of n.
Note that (i) the function num_fibonacci_calls does not compute or print out the
fibonacci number(s) but only tells you how many times the fibonacci function is called
to produce the nth fibonacci number. (ii) Your answer must be a recursive function
that works with the main function on the next page to produce the above results.
14
n Returned Value
0 1
1 1
2 3
3 5
4 9
5 15
6 25
Table 1: Examples of values returned by num fibonacci calls(int).
#include <iostream>
using namespace std;
int num fibonacci calls(int n)
{
// ANSWER: ADD YOUR CODE HERE
int main( )
{
cout "Enter a non-negative integer: ";
int n;
cin n;
cout "no. of fibonacci calls = " num fibonacci calls(n) endl;
return 0;
}
15
Problem 9 [12 points] Tax Computation
Every Citizen in Loutacs (an imaginary country) needs to pay tax. The more you earn, the
more tax you will pay.
There are two ways to compute one’s tax in Loutacs.
First method: Progressive Rates
The rules for computing the tax using progressive rates are:
• No tax for the first $100 of the income
• 10% of the next $400 of the income
• 20% of the next $600 of the income
• 30% of the remaining income
Second method: Flat Rate
The Loutacs government will also calculate the tax according to the flat rate of 25% from
the income.
The actual tax you pay is the smaller among the results computed by the above two methods.
The table below give some examples.
Citizen Income First $100 Next $400 Next $600 Remainder Progressive Flat Rate Final
Tax Tax Tax
A 75 75 0 0 0 0 0 0
B 120 100 20 0 0 2 30 2
C 800 100 400 300 0 100 200 100
D 9100 100 400 600 8000 2560 2275 2275
16
(a) [6 points] Write a function that takes the income as the input parameter and returns the
tax amount computed using the Progressive Rates; truncate your result to an integer.
int progressive rate tax(int income)
{
// ANSWER: ADD YOUR CODE HERE
(b) [2 points] Write a function that takes the income as the input parameter and returns
the tax amount computed using the Flat Rate; truncate your result to an integer.
int flat rate tax(int income)
{
// ANSWER: ADD YOUR CODE HERE
17
(c) [4 points] Write a void function that takes the income as the input parameter, and prints
out the actual tax that is to be paid. It should print out which of the two methods is used
to compute the actual tax. This function is expected to call the two functions defined in
parts (a) and (b).
The output should look like this if the Flat Rate method gives the lower tax:
You have to pay $200 tax.
It is computed using the Flat Rate.
On the other hand, if Progressive Rates method gives the lower tax, the output should
look like:
You have to pay $80 tax.
It is computed using the Progressive Rates.
void tax payable(int income)
{
// ANSWER: ADD YOUR CODE HERE
18
/* Rough work — You may detach this page */
19
/* Rough work — You may detach this page */
20
