Tut 4: Mid Term Revision

This tutorial is ungraded. No submission is required. Work through the questions in the first part during your tutorial, and use the second part for additional revision. Try each question before opening its solution.

The questions are selected from past CS1010 midterm and final assessments, with the latest source identified in each question heading. Assume the required headers and function declarations are available. Unless a question explicitly discusses overflow, wraparound, or undefined behaviour, assume the inputs are valid and the arithmetic does not overflow or underflow.

During the Tutorial

Question 1: Midterm AY25/26 Q10

What does f(12) print?

void f(int n) {
    if (n > 15) {
        printf("a");
    }
    if (n > 10) {
        printf("b");
    }
    if (n > 20) {
        printf("c");
    } else {
        printf("d");
    }
}

• A. ac

• B. b

• C. bc

• D. bd

• E. d

Solution

D: bd. The first condition is false, the second is true, and the third is false. The else belongs to the third if, so d is printed after b.

Question 2: Midterm AY25/26 Q20

Which return statement is equivalent to the function below?

bool check(bool a, bool b, bool c, bool d) {
    if (a) {
        if (b) {
            return true;
        }
    }
    if (c) {
        return true;
    }
    return false;
}

• A. return a && b && c;

• B. return a || b || c;

• C. return (a || b) && c;

• D. return (a && b) || c;

Solution

D. The function returns true when a && b is true or when c is true. The unused parameter d has no effect.

Question 3: Final AY21/22 Q14

What are the values of a.x at F and G?

typedef struct box {
    int x;
} box;
 
void modify_again(box b) {
    b.x = 3;
}
 
box modify_some_more(box b) {
    b.x = 4;
    return b;
}
 
int main(void) {
    box a;
    a.x = 1;
    modify_again(a);
    // F
    a = modify_some_more(a);
    // G
}

Solution

F: 1; G: 4. Both functions receive a copy of the struct. modify_again changes only its local copy. modify_some_more also changes a copy, but returns that copy; the assignment in main replaces a with the returned value.

Question 4: Midterm AY23/24 Q4

What does foo(1, 1) return?

long foo(long m, long n) {
    if (m == 0) {
        return n + 1;
    }
    if (n == 0) {
        return foo(m - 1, 1);
    }
    return foo(m - 1, foo(m, n - 1));
}

• A. 0

• B. 1

• C. 2

• D. 3

• E. 4

Solution

D: 3. Evaluate the inner call before using its result:

foo(1, 1)
= foo(0, foo(1, 0))
= foo(0, foo(0, 1))
= foo(0, 2)
= 3

Question 5: Final AY22/23 Q13(a–d)

For each independent function, express its return value in terms of n and k. State the input ranges covered by your expression and when the loop fails to terminate. As elsewhere on this page, exclude executions that overflow their integer types.

(a)

long foo(long n) {
    long i = 0;
    while (i <= n) {
        i += 1;
    }
    return i;
}

(b)

long foo(long n, long k) {
    long i;
    for (i = 0; i < n; i += k) {
    }
    return i;
}

(c)

long foo(long n, long k) {
    while (n > k) {
        n -= k;
    }
    return n;
}

(d)

long foo(long n, long k) {
    long i = 0;
    while (n > k) {
        n -= k;
        i += 1;
    }
    return i;
}

Solution

(a) Returns 0 when n < 0, and n + 1 when n >= 0. Thus the mathematical expression is $\max (0,n+1)$. The case n == LONG_MAX is excluded: incrementing beyond it would overflow.

(b) If n <= 0, the loop is skipped and returns 0, regardless of k. For n > 0 and k > 0, it returns $\lceil n/k\rceil k$, the smallest multiple of k at least n, provided that multiple is representable. For n > 0 and k == 0, it does not terminate. For n > 0 and k < 0, it moves away from the target and eventually incurs signed overflow.

(c) If n <= k, it returns n immediately. For k > 0 and n > 0, it returns $((n-1)\mathrm{mod}k)+1$, where the remainder is mathematical and lies between 0 and k - 1. In particular, a positive multiple of k produces k, not 0. For k > 0 and n <= 0, it returns n. If n > k and k == 0, it does not terminate; if n > k and k < 0, it increases n until signed overflow.

(d) If n <= k, it returns 0 immediately. For k > 0 and n > 0, it returns $\lfloor (n-1)/k\rfloor$. For k > 0 and n <= 0, it returns 0. If n > k and k == 0, the counter keeps increasing until signed overflow; if n > k and k < 0, n eventually overflows.

Question 6: Midterm AY25/26 Q12

In terms of n, how many times is a printed?

void g(size_t n) {
    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < n; j++) {
            printf("a");
            break;
        }
        continue;
        printf("a");
    }
}

Solution

n times. For positive n, each outer iteration prints once and breaks out of the inner loop. continue then skips the second printf and proceeds to the outer loop’s update. For n == 0, nothing is printed.

Question 7: Midterm AY25/26 Q33

Does reverse_arr correctly reverse every array with more than one element? If not, explain why.

void swap(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
}
 
void reverse_arr(int a[], size_t num_elems) {
    for (size_t idx = 0; idx < num_elems / 2; ++idx) {
        swap(a[idx], a[num_elems - 1 - idx]);
    }
}

Solution

No. swap exchanges its local copies of two integers. It never assigns to either array element, so the array remains unchanged. For example, {1, 2} remains {1, 2}.

A repair using only array indexing is to put the exchange inside the loop:

int temp = a[idx];
a[idx] = a[num_elems - 1 - idx];
a[num_elems - 1 - idx] = temp;

Question 8: Midterm AY25/26 Q34

Rewrite this function using only while loops, keeping its prototype and printed output. Assume n >= 0 and the counters can represent n + 1.

void i_dont_like_for_loops(int n) {
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = i; j <= n; j++) {
            printf("a");
        }
    }
}

Solution

void i_dont_like_for_loops(int n) {
    size_t i = 0;
    while (i < n) {
        size_t j = i;
        while (j <= n) {
            printf("a");
            j++;
        }
        ++i;
    }
}

Initialize each counter before its loop and perform its update at the end of the body. In particular, reset j to the current i on every outer iteration.

Other Questions for Revision

Question 9: Midterm AY25/26 Q22

Suppose we have the following variables:

long three = 3;
long five = 5;
double answer;

Which expression makes answer approximately 0.6?

• A. answer = three / five;

• B. answer = (long)(three / five);

• C. answer = (long)three / (long)five;

• D. answer = (double)(three / five);

• E. answer = (double)three / five;

Solution

E. Casting three before division makes the division floating-point division. In A–D, the division has two integer operands and produces 0. Converting that result to double afterwards produces 0.0, not 0.6.

Question 10: Midterm AY25/26 Q5

Which expression produces a negative result?

• A. -1 / 2

• B. 1 / -2

• C. -2 / 1

• D. All of A–C

• E. None of A–C

Solution

C. Integer division truncates towards zero. A and B produce 0; C produces -2.

Question 11: Midterm AY25/26 Q2

Given the same number of bits, the maximum value of an unsigned int is ______ compared with the maximum value of an int.

• A. Larger

• B. Smaller

• C. The same

• D. None of the above

Solution

A. The unsigned type uses its value bits for nonnegative values. For example, with 32 value/sign bits, the unsigned maximum is $2^{32}-1$, whereas the signed maximum is $2^{31}-1$.

Question 12: Midterm AY25/26 Q4

The mathematical result of 10000 * 7 must be stored in a variable. Using the minimum ranges guaranteed by C, which is the smallest of these types guaranteed to represent the result?

• A. char

• B. int

• C. long

• D. long long

• E. None of the above

Solution

C: long. The result is 70000. C guarantees that int can represent at least -32767 through 32767, and that long can represent at least -2147483647 through 2147483647. When computing this on a system with a small int, use 10000L * 7: a wider destination alone does not make the multiplication use a wider type.

Question 13: Midterm AY25/26 Q6

At one instant, the stack frames are arranged as follows, with the current call at the top:

foo
foo
quux
bar
main

All function bodies are omitted. Which statement is supported by this stack?

• A. foo calls quux

• B. quux calls foo

• C. quux calls bar

• D. All of A–C

• E. This stack layout is impossible

Solution

B. Starting at the bottom, main called bar, bar called quux, quux called foo, and that call of foo called foo again. Two active calls of the same function have separate stack frames.

Question 14: Midterm AY25/26 Q9

What is printed? The indentation is intentional.

int i = 0;
if (i == 0)
    i = 3;
else
    i = 5;
    printf("%d", i);

• A. Nothing

• B. 1

• C. 3

• D. 5

• E. All of the above are possible

Solution

C: 3. Without braces, each branch controls only the next statement. The printf is outside the if/else and executes after i becomes 3.

Question 15: Midterm AY25/26 Q13

How many times is the word true printed?

bool buzz(int n) {
    if (n > 0) {
        printf("false");
    } else if (n < 0) {
        printf("true");
    }
    return true;
}
 
int main(void) {
    bool ret = buzz(1000);
    if (!ret) {
        printf("true");
    } else {
        printf("false");
    }
}

Solution

Zero times. The complete output is falsefalse. Printing the word false does not determine a function’s return value: buzz still returns the boolean value true. Consequently, main takes its else branch.

Question 16: Midterm AY25/26 Q14

What does f(12) print?

void f(int n) {
    printf("%d", n + '0');
}

• A. 12

• B. A value greater than 12

• C. A value less than 12

• D. Undefined behaviour

• E. None of the above

Solution

B. '0' is the integer character code for the digit zero, not the integer 0. On an ASCII system, '0' is 48, so this prints 60. %d prints the resulting integer, not the character with that code.

Question 17: Midterm AY25/26 Q19

Assume n has more than two decimal digits. Which is the incorrect way to check whether the last two digits of n are the same?

• A. (n / 100) == (n / 10)

• B. ((n % 100) % 11) == 0

• C. ((n / 10) % 10) == (n % 10)

Solution

A. For example, n = 122 gives 1 != 12, despite its repeated final digits. B works because two equal final digits form 00, 11, …, 99, exactly the multiples of 11 in that range. The corresponding negative remainders are also divisible by 11. C compares the tens and units digits directly.

Question 18: Midterm AY21/22 Q5

bool kim(bool x) {
    printf("kim\n");
    return x;
}
 
bool gan(bool x) {
    printf("gan\n");
    return x;
}
 
bool mud(bool a, bool b) {
    if (kim(a)) {
        return false;
    }
    if (gan(b)) {
        return true;
    }
    return false;
}

Which replacements for the body of mud always return the same value and print the same strings in the same order? Select all correct options.

• A. return gan(b) || !kim(a);

• B. return !gan(b) || kim(a);

• C. return gan(b) && !kim(a);

• D. return kim(a) && !gan(b);

• E. return kim(a) || !gan(b);

• F. return !kim(a) && gan(b);

• G. None of the above

Solution

F only. kim(a) is called first. If a is true, !kim(a) is false, so && skips gan(b) and returns false. If a is false, gan(b) is called and its result determines the return value. C has the same truth value, but calls gan first and therefore changes the output.

Question 19: Midterm AY25/26 Q27

Describe what happens when rec(5) is called. Does it reach the printing statement?

void rec(int n) {
    rec(n - 1);
    if (n == 0) {
        printf("%d", n);
        return;
    }
}

Solution

It never reaches the printing statement or returns normally. Even rec(0) first calls rec(-1). Every call waits for another call before it can test the base case. On a typical unoptimised execution this exhausts the stack. If execution continued far enough, computing n - 1 at INT_MIN would also overflow; there is no defined successful output to predict.

Question 20: Final AY18/19 Q13

Complete the missing lines to generate all binary strings of length n, in order. Assume n >= 1, 0 <= k < n, and str has n + 1 elements with str[n] == '\0'. The positions before k have already been filled.

void generate(long n, char str[], long k) {
    if (k == n - 1) {
        str[k] = '0';
        printf("%s\n", str);
        str[k] = '1';
        printf("%s\n", str);
        return;
    }
    // Missing lines
}

For n == 2, the desired lines are 00, 01, 10, and 11.

Solution

str[k] = '0';
generate(n, str, k + 1);
str[k] = '1';
generate(n, str, k + 1);

Choose the digit at position k before generating the remaining positions. The first call generates every suffix beginning with the chosen 0; the second generates every suffix beginning with the chosen 1. Printing is already handled by the base case.

Question 21: Midterm AY22/23 Q8

Assume something() returns normally. Compare the number of calls for n <= 0 and n > 0.

void tutu(long n) {
    long x = n;
    do {
        something();
        x -= 1;
    } while (x > 0);
}
void tata(long n) {
    something();
    for (long x = n; x > 0; x -= 1) {
        something();
    }
}

Solution

For n <= 0, both call something() once. For n > 0, tutu calls it n times and tata calls it n + 1 times. In particular, at n == 1, tata makes one extra call. The do-while body runs before its first condition check.

Question 22: Midterm AY25/26 Q25–26

What does each snippet print, and does it terminate? Unsigned wraparound is allowed in this question.

// (a)
for (size_t i = 0; i <= 5; i++) {
    printf("i");
}
// (b), considered separately
for (size_t i = 0; i <= 5; i--) {
    printf("i");
}

Solution

(a) Prints iiiiii and terminates: the body runs for i from 0 through 5. (b) Prints i once and terminates. The first decrement wraps zero to the maximum size_t value, which is greater than 5. The quoted "i" is a literal character, so these statements do not print the counter’s value.

Question 23: Midterm AY25/26 Q29

What does foo(31) return?

int foo(int a) {
    int b = 1;
    while (2 * b < a) {
        b *= 2;
    }
    return b;
}

Solution

16. The values of b are 1, 2, 4, 8, and 16. At 16, the condition is 32 < 31, which is false.

Question 24: Midterm AY25/26 Q21

Assume m >= 0 and n > 0. When execution reaches Line A, what do we know about i % n? Must the original m be divisible by n?

void corge(long m, long n) {
    long i = m;
    while ((i % n) != 0) {
        i -= 1;
    }
    // Line A
}

Solution

i % n == 0, because the loop stops when its condition becomes false. The original m need not be divisible by n. For example, m == 5 and n == 2 cause i to decrease to 4, then the loop stops.

Question 25: Midterm AY25/26 Q28

What does this program print?

int main(void) {
    int arr[5] = {0};
    if (arr[2] == 0) {
        printf("zero");
    } else {
        printf("non-zero");
    }
}

Solution

zero. The explicit initializer initializes arr[0] to zero. The remaining elements are also initialized to zero, so arr[2] == 0 is true.

Question 26: Midterm AY25/26 Q8

Does this snippet have a guaranteed output? Explain.

int arr[5] = {0};
arr[5] = 100;
printf("%d", arr[5]);

Solution

No. It has undefined behaviour. The five valid indices are 0 through 4. Both uses of arr[5] access outside those bounds. Writing there first does not make the subsequent read valid or guarantee that 100 is printed.

Question 27: Midterm AY25/26 Q31

What does print_foo("baba") print?

void print_foo(char s[]) {
    for (size_t i = 0; s[i] != 'a'; i++) {
        printf("%c", s[i]);
    }
}

Solution

b. At index zero, the character is b, so it is printed. At index one, the character is a, so the loop stops before printing it.

Question 28: Midterm AY25/26 Q18

Given int x[20][20] = {0};, which pair is adjacent in memory?

• A. x[5][19] and x[19][5]

• B. x[2][19] and x[3][0]

• C. x[0][0] and x[1][0]

Solution

B. The elements of each row are consecutive, and the rows are consecutive. The last element of row 2 is immediately followed by the first element of row 3. The first elements of successive rows are 20 elements apart.

Question 29: Final AY22/23 Q15(a–b)

Given an integer q and an array a of n integers, find whether a nonempty combination of its elements sums to q. Each array position may be used at most once. For {3, 11, -1, 9}, a combination sums to 20, but none sums to 6.

Assume n > 0 and 0 <= i < n. The function searches the elements from a[i] through a[n - 1]. Complete the two conditions and the single recursive return statement. Use short-circuiting to avoid an unnecessary second recursive call.

bool can_sum_to(long a[], size_t i, size_t n, long q) {
    if (/* condition 1 */) {
        return true;
    }
    if (/* condition 2 */) {
        return false;
    }
    return /* recursive expression */;
}

Solution

bool can_sum_to(long a[], size_t i, size_t n, long q) {
    if (a[i] == q) {
        return true;
    }
    if (i == n - 1) {
        return false;
    }
    return can_sum_to(a, i + 1, n, q - a[i]) ||
           can_sum_to(a, i + 1, n, q);
}

The first test checks the one-element combination {a[i]}. Otherwise, either include a[i] and find the remaining sum in the suffix, or skip it and search for the original sum in that suffix. The second call is skipped when the first succeeds.

Do not use q == 0 alone as the successful base case: that would accept the empty combination, contrary to this question’s contract. For example, {1, 2} has no nonempty combination summing to 0. The precondition ensures that reading a[i] is valid.

Question 30: Final AY20/21 Q13(a–b)

For long a[] = {9, 8, 7};, give i and the full array at Line Z on each of its first six visits. What is the array after moo(3, a) finishes? Also give the final array when the initial array is {3, 1, 2}.

void swap(long a[], long i, long j) {
    long temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
void moo(long len, long a[]) {
    long i = 0;
    while (i < len) {
        if (i == 0 || a[i] >= a[i - 1]) {
            i += 1;
        } else {
            swap(a, i, i - 1);
            i -= 1;
        }
        // Line Z
    }
}

Solution

Visit	i	Array
1	1	{9, 8, 7}
2	0	{8, 9, 7}
3	1	{8, 9, 7}
4	2	{8, 9, 7}
5	1	{8, 7, 9}
6	0	{7, 8, 9}

The final arrays are {7, 8, 9} and {1, 2, 3}, respectively. When adjacent elements are out of order, the function swaps them and steps back. At i == 0, short-circuit evaluation prevents evaluating a[i - 1].