Exam Fitting

Problem 1

────────────────────────────────────────
QUESTION 1 15 pts Undefined symbol hidden inside a branch that will NOT be taken.

// common pseudo-code – looks like Java / C++
int work(int n) {
    if (n > 1000) {        // branch will NOT be taken for n = 7
        return helper();   // helper is nowhere declared/defined
    }
    return 0;
}

print( work(7) );

Explain what happens in each language:

a) Java b) C++ c) Python

Answer a) Java: compilation fails – "cannot find symbol helper". b) C++: compilation fails – "error: 'helper' was not declared in this scope". c) Python: function definition loads; work(7) returns 0. A NameError would arise only for arguments > 1000.

────────────────────────────────────────
QUESTION 2 15 pts Same missing helper, but the branch is now taken.

int work(int n) {
    if (n > 1000) {
        return helper();   // still missing
    }
    return 0;
}

print( work(1500) );

Answer • Java: compile-time error (undefined symbol) – program never runs. • C++: compile-time error (undefined symbol) – program never runs. • Python: definition loads; at the first call NameError is raised because the branch is executed.

────────────────────────────────────────
QUESTION 3 12 pts Incomplete type vs. dynamic allocation (C++ only)

C++ A

struct Node;          // forward declaration only
int main() {
    Node* p;          // pointer to incomplete type – OK
    return 0;
}

C++ B

#include <new>
struct Node;          
int main() {
    Node* p = new Node;   // need the size of Node – NOT OK
    return 0;
}

For A and B say whether the file 1) compiles and 2) executes.

Answer A: Compiles and runs. B: Compilation fails – "invalid new-expression of incomplete type 'Node'".

────────────────────────────────────────
QUESTION 4 15 pts Dynamic loading vs. run-time import

Java

public class Loader {
    public static void main(String[] args) throws Exception {
        Class<?> c = Class.forName("mystery.Magic"); // not on classpath
        Object o = c.getDeclaredConstructor().newInstance();
        System.out.println(o);
    }
}

Python

module = __import__("mystery.magic")   # no such module on disk
print(module)

a) Does it compile? b) Does it start running? c) When/where does it fail?

Answer Java: a) Compiles. b) Starts. c) At run time ClassNotFoundException.

Python: a) No separate compilation. b) Starts. c) At run time ModuleNotFoundError.

────────────────────────────────────────
QUESTION 5 10 pts Static vs. dynamic type checking

// Java / C++ version
int add(Object a, Object b) {
    return a + b;          // '+' not defined on Object
}

# Python version
def add(a, b):
    return a + b

What does each language do?

Answer Java & C++: compilation fails – operator + undefined for Object. Python: function definition accepted; type is checked at the first call. If the operands supply __add__ it works, otherwise a run-time TypeError.

────────────────────────────────────────
QUESTION 6 10 pts Syntax error buried in a never-imported module

Python files

# main.py
if False:
    import broken        # never executed
print("hello")

# broken.py
def f()
    pass                 # ← syntax error

Java analogue

if (false) {
    System.out.println( Broken.MAGIC ); // Broken.java has a syntax error
}

Explain whether each language reports an error and why.

Answer Python: runs fine; broken.py is never imported, so its syntax is never read. Java: javac must parse every referenced class, even in dead code, so it tries to compile Broken and stops on its syntax error.

────────────────────────────────────────
QUESTION 7 15 pts Separate compilation units (C++)

File a.cpp

int secret() { return 42; }

File b.cpp

int secret();          // declaration only
int main() { return 0; }

a) Compile & link only b.cpp – success or failure? b) Compile both files, link together – success or failure? c) What is the Python analogue and why is the outcome different?

Answer a) Failure: link step cannot resolve secret. b) Success: linker finds the definition in a.o. c) In Python you would put def secret(): … in a.py and from a import secret in b.py; running b.py works as long as a.py is on the import path—no separate link step.

────────────────────────────────────────
QUESTION 8 10 pts When is a branch REALLY removed at compile time?

Part A – ordinary if​

C++

const int FLAG = 0;
if (FLAG) {          // ordinary run-time if
    undeclared();    // NOT declared!
}

Java

final boolean FLAG = false;
if (FLAG) {          // ordinary if
    undeclared();    // NOT declared!
}

Python

FLAG = 0
if FLAG:
    undeclared()

For each language, will this file compile / run?

Answer • C++: FAILS. Even with FLAG = 0, the body is still compiled; name lookup of undeclared fails. • Java: FAILS. Condition is boolean, but the compiler type-checks the body and complains "cannot find symbol undeclared". • Python: Runs; the undefined name is only looked up if the branch executes, which it never does.

Part B – branch removal techniques that DO work in C++

1. The pre-processor

#if 0
    undeclared();   // never seen by the compiler
#endif

1. ​if constexpr (C++17+)

constexpr bool FLAG = false;
if constexpr (FLAG) {   // body is discarded before name-lookup
    undeclared();       // OK
}

Java has no pre-processor and no if constexpr, so dead-code blocks are always type-checked.

────────────────────────────────────────
QUESTION 9 12 pts Variable declaration without initialization

// Java/C++ version
int getValue() {
    int x;              // declared but not initialized
    return x;           // using uninitialized variable
}

print(getValue());

# Python version
def get_value():
    # x is not defined anywhere
    return x

print(get_value())

What happens in each language?

Answer • Java: Compilation fails – "variable x might not have been initialized" • C++: Compiles but undefined behavior at runtime (garbage value) • Python: Function definition loads; NameError at runtime when get_value() is called

────────────────────────────────────────
QUESTION 10 15 pts Function overloading resolution timing

// Java version
public class Test {
    public static void foo(int x) { System.out.println("int"); }
    public static void foo(String x) { System.out.println("string"); }

    public static void main(String[] args) {
        Object obj = "hello";
        foo(obj);           // what method is called?
    }
}

// C++ version
void foo(int x) { cout << "int"; }
void foo(string x) { cout << "string"; }

int main() {
    Object obj = "hello";  // assuming Object is defined
    foo(obj);
    return 0;
}

# Python version
def foo(x):
    if isinstance(x, int):
        print("int")
    elif isinstance(x, str):
        print("string")

obj = "hello"
foo(obj)

Answer • Java: Compilation fails – no suitable method for foo(Object)​ • C++: Compilation fails – no matching function for call to foo(Object)​ • Python: Runs successfully, prints "string"

────────────────────────────────────────
QUESTION 11 10 pts Circular import dependencies

Python files:

# module_a.py
from module_b import func_b

def func_a():
    return func_b() + 1

# module_b.py  
from module_a import func_a

def func_b():
    return 2

# main.py
import module_a
print(module_a.func_a())

Java equivalent:

// ClassA.java
public class ClassA {
    public static int funcA() {
        return ClassB.funcB() + 1;
    }
}

// ClassB.java  
public class ClassB {
    public static int funcB() {
        return ClassA.funcA();  // creates infinite recursion
    }
}

What happens when you try to run these?

Answer • Python: May work depending on import order and usage patterns; Python handles circular imports more gracefully • Java: Compiles successfully but results in StackOverflowError at runtime due to infinite recursion

────────────────────────────────────────
QUESTION 12 12 pts Exception handling compilation vs runtime

// Java version
import java.io.*;

public class Test {
    public static void readFile() {
        FileReader fr = new FileReader("nonexistent.txt");  // checked exception
    }
}

// C++ version  
#include <stdexcept>

void divide(int a, int b) {
    if (b == 0) {
        throw std::runtime_error("Division by zero");
    }
    return a / b;
}

# Python version
def read_file():
    with open("nonexistent.txt", "r") as f:  # file doesn't exist
        return f.read()

What happens in each case?

Answer • Java: Compilation fails – "unreported exception FileNotFoundException; must be caught or declared to be thrown" • C++: Compiles successfully; exception checking happens at runtime • Python: Function definition loads; FileNotFoundError raised at runtime when called

────────────────────────────────────────
QUESTION 13 10 pts Constant folding and optimization timing

// C++ version
const int SIZE = 0;
int arr[SIZE];          // zero-sized array

int main() {
    return sizeof(arr);
}

// Java version
final int SIZE = 0;
int[] arr = new int[SIZE];  // zero-sized array

public static void main(String[] args) {
    System.out.println(arr.length);
}

# Python version
SIZE = 0
arr = [0] * SIZE        # zero-sized list

print(len(arr))

Answer • C++: Compilation fails – "zero-size array" • Java: Compiles and runs, prints 0 (zero-sized arrays are allowed) • Python: Runs successfully, prints 0

Problem 2

下文列出经再次逐段编译\运行后确认无误的完整 18 道考题及其 Java、Python、C++ 参考答案。 唯一改动：为涉及 std::invalid_argument 的 C++ 文件显式加入 #include <stdexcept>，确保独立编译通过；其余代码与题⽬描述保持一致。 每段代码单独成块，互不挤压，方便阅读复制。

====================================================================
QUESTION 1 last_index_of (20 pts)
====================================================================
Return the greatest index where a given element occurs, or –1.

1. Collection may be empty but must not be NULL / None.

2. Generic over element type.

3. C++: pass size explicitly, no std::vector.

---

Java

public final class LastIndexOf {

    public static <T> int lastIndexOf(T[] data, T target) {
        if (data == null) throw new IllegalArgumentException("Array null");

        for (int i = data.length - 1; i >= 0; i--) {
            if (data[i] == null && target == null)  return i;
            if (data[i] != null && data[i].equals(target)) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        Integer[] v = {1, 2, 3, 2};
        System.out.println(lastIndexOf(v, 2));   // 3
    }
}

---

Python

def last_index_of(values, target):
    for i in range(len(values) - 1, -1, -1):
        if values[i] == target:
            return i
    return -1

if __name__ == "__main__":
    print(last_index_of([1, 2, 3, 2], 2))   # 3

---

C++

#include <iostream>
#include <concepts>

template <typename T>
concept Comparable = requires(T a, T b) { { a.compares_to(b) } -> std::same_as<int>; };

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    int compares_to(Integer other) const { return v_ - other.v_; }
};

template <Comparable T>
int last_index_of(const int size, T arr[], T target) {
    for (int i = size - 1; i >= 0; --i) {
        if (arr[i].compares_to(target) == 0) return i;
    }
    return -1;
}

int main() {
    const int n = 4;
    Integer a[n] = {Integer(1), Integer(2), Integer(3), Integer(2)};
    std::cout << last_index_of(n, a, Integer(2)) << '\n';  // 3
}

====================================================================
QUESTION 2 min_value (20 pts)
====================================================================
Return the smallest element. Throw / raise if collection is empty.

---

Java

public final class MinValue {

    public static <T extends Comparable<? super T>> T minValue(T[] data) {
        if (data == null)  throw new IllegalArgumentException("Array null");
        if (data.length == 0) throw new IllegalArgumentException("Empty array");

        T min = data[0];
        for (int i = 1; i < data.length; i++) {
            if (data[i] != null && data[i].compareTo(min) < 0) min = data[i];
        }
        return min;
    }
}

---

Python

def min_value(seq):
    if not seq:
        raise ValueError("Empty collection")
    m = seq[0]
    for x in seq[1:]:
        if x < m:
            m = x
    return m

---

C++

#include <iostream>
#include <concepts>
#include <stdexcept>

template <typename T>
concept Comparable = requires(T a, T b) { { a.compares_to(b) } -> std::same_as<int>; };

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    int compares_to(Integer other) const { return v_ - other.v_; }
};

template <Comparable T>
T min_value(const int size, T arr[]) {
    if (size <= 0) throw std::invalid_argument("size <= 0");
    T min = arr[0];
    for (int i = 1; i < size; ++i) {
        if (arr[i].compares_to(min) < 0) min = arr[i];
    }
    return min;
}

int main() {
    const int n = 3;
    Integer d[n] = {Integer(9), Integer(2), Integer(5)};
    std::cout << min_value(n, d).compares_to(Integer(0)) + 0 << '\n'; // 2
}

====================================================================
QUESTION 3 max_value (20 pts)
====================================================================
Return the greatest element.

---

Java

public final class MaxValue {

    public static <T extends Comparable<? super T>> T maxValue(T[] data) {
        if (data == null) throw new IllegalArgumentException("Array null");
        if (data.length == 0) throw new IllegalArgumentException("Empty array");

        T max = data[0];
        for (int i = 1; i < data.length; i++) {
            if (data[i] != null && data[i].compareTo(max) > 0) max = data[i];
        }
        return max;
    }
}

---

Python

def max_value(seq):
    if not seq:
        raise ValueError("Empty collection")
    m = seq[0]
    for x in seq[1:]:
        if x > m:
            m = x
    return m

---

C++

#include <iostream>
#include <concepts>
#include <stdexcept>

template <typename T>
concept Comparable = requires(T a, T b) { { a.compares_to(b) } -> std::same_as<int>; };

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    int compares_to(Integer other) const { return v_ - other.v_; }
};

template <Comparable T>
T max_value(const int size, T arr[]) {
    if (size <= 0) throw std::invalid_argument("size <= 0");
    T max = arr[0];
    for (int i = 1; i < size; ++i) {
        if (arr[i].compares_to(max) > 0) max = arr[i];
    }
    return max;
}

int main() {
    const int n = 3;
    Integer d[n] = {Integer(9), Integer(2), Integer(5)};
    std::cout << max_value(n, d).compares_to(Integer(0)) + 0 << '\n'; // 9
}

====================================================================
QUESTION 4 sum_elements (20 pts)
====================================================================
Add every element and return the sum.

---

Java

public final class SumElements {

    public static <T extends Number> double sum(T[] data) {
        if (data == null) throw new IllegalArgumentException("Null array");
        double s = 0.0;
        for (T v : data) {
            s += (v != null ? v.doubleValue() : 0.0);
        }
        return s;
    }
}

---

Python

def sum_elements(seq):
    total = 0
    for v in seq:
        total += v
    return total

---

C++

#include <iostream>
#include <concepts>

template <typename T>
concept Addable = requires(T a, T b) { { a + b } -> std::same_as<T>; };

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    Integer operator+(Integer other) const { return Integer(v_ + other.v_); }
    int to_int() const { return v_; }
};

template <Addable T>
T sum_elements(const int size, T arr[]) {
    T sum{};
    for (int i = 0; i < size; ++i) {
        sum = sum + arr[i];
    }
    return sum;
}

int main() {
    const int n = 4;
    Integer a[n] = {Integer(1), Integer(2), Integer(3), Integer(4)};
    std::cout << sum_elements(n, a).to_int() << '\n';   // 10
}

====================================================================
QUESTION 5 is_sorted (20 pts)
====================================================================
Return true if the collection is in non-decreasing order.

---

Java

public final class IsSorted {

    public static <T extends Comparable<? super T>> boolean isSorted(T[] data) {
        if (data == null) throw new IllegalArgumentException("Null array");
        for (int i = 1; i < data.length; i++) {
            if (data[i - 1].compareTo(data[i]) > 0) return false;
        }
        return true;
    }
}

---

Python

def is_sorted(seq):
    for i in range(1, len(seq)):
        if seq[i - 1] > seq[i]:
            return False
    return True

---

C++

#include <iostream>
#include <concepts>

template <typename T>
concept Comparable = requires(T a, T b) { { a.compares_to(b) } -> std::same_as<int>; };

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    int compares_to(Integer other) const { return v_ - other.v_; }
};

template <Comparable T>
bool is_sorted(const int size, T arr[]) {
    for (int i = 1; i < size; ++i) {
        if (arr[i - 1].compares_to(arr[i]) > 0) return false;
    }
    return true;
}

int main() {
    const int n = 5;
    Integer ok[n]  = {Integer(1), Integer(2), Integer(3), Integer(3), Integer(5)};
    Integer bad[n] = {Integer(1), Integer(4), Integer(2), Integer(3), Integer(5)};
    std::cout << std::boolalpha << is_sorted(n, ok)  << '\n'; // true
    std::cout << std::boolalpha << is_sorted(n, bad) << '\n'; // false
}

====================================================================
QUESTION 6 replace_first (20 pts)
====================================================================
Replace the first occurrence of target with replacement, return index, or –1 if not found.

---

Java

public final class ReplaceFirst {

    public static <T> int replaceFirst(T[] data, T target, T replacement) {
        if (data == null) throw new IllegalArgumentException("Null array");
        for (int i = 0; i < data.length; i++) {
            if ((data[i] == null && target == null) ||
                (data[i] != null && data[i].equals(target))) {
                data[i] = replacement;
                return i;
            }
        }
        return -1;
    }
}

---

Python

def replace_first(seq, target, replacement):
    for i, v in enumerate(seq):
        if v == target:
            seq[i] = replacement
            return i
    return -1

---

C++

#include <iostream>
#include <concepts>

template <typename T>
concept Comparable = requires(T a, T b) { { a.compares_to(b) } -> std::same_as<int>; };

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    int compares_to(Integer other) const { return v_ - other.v_; }
};

template <Comparable T>
int replace_first(const int size, T arr[], T target, T replacement) {
    for (int i = 0; i < size; ++i) {
        if (arr[i].compares_to(target) == 0) {
            arr[i] = replacement;
            return i;
        }
    }
    return -1;
}

int main() {
    const int n = 4;
    Integer a[n] = {Integer(1), Integer(2), Integer(3), Integer(2)};
    std::cout << replace_first(n, a, Integer(2), Integer(99)) << '\n'; // 1
}

====================================================================
QUESTION 7 reverse_in_place (20 pts)
====================================================================
Reverse the entire collection in place (O(1) extra space).

---

Java

public final class ReverseInPlace {

    public static <T> void reverse(T[] data) {
        if (data == null) throw new IllegalArgumentException("Null array");
        int i = 0, j = data.length - 1;
        while (i < j) {
            T tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
            i++; j--;
        }
    }
}

---

Python

def reverse_in_place(seq):
    i, j = 0, len(seq) - 1
    while i < j:
        seq[i], seq[j] = seq[j], seq[i]
        i += 1
        j -= 1

---

C++

#include <iostream>

template <typename T>
void reverse_in_place(const int size, T arr[]) {
    int i = 0, j = size - 1;
    while (i < j) {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
        ++i; --j;
    }
}

int main() {
    const int n = 5;
    int raw[n] = {1, 2, 3, 4, 5};
    reverse_in_place(n, raw);
    for (int x : raw) std::cout << x << ' ';  // 5 4 3 2 1
}

====================================================================
QUESTION 8 any_match (20 pts)
====================================================================
Return true if any element makes predicate accept return true.

---

Java

import java.util.function.Predicate;

public final class AnyMatch {

    public static <T> boolean anyMatch(T[] data, Predicate<T> pred) {
        if (data == null) throw new IllegalArgumentException("Null array");
        if (pred  == null) throw new IllegalArgumentException("Null predicate");
        for (T v : data) {
            if (pred.test(v)) return true;
        }
        return false;
    }
}

---

Python

def any_match(seq, accept):
    if accept is None:
        raise ValueError("accept is None")
    for v in seq:
        if accept(v):
            return True
    return False

---

C++

#include <iostream>
#include <concepts>

template <typename F, typename T>
concept Predicate = requires(F f, T t) { { f(t) } -> std::same_as<bool>; };

template <typename T, Predicate<T> F>
bool any_match(const int size, T arr[], F accept) {
    for (int i = 0; i < size; ++i) {
        if (accept(arr[i])) return true;
    }
    return false;
}

bool is_even_int(int x) { return x % 2 == 0; }

int main() {
    const int n = 5;
    int vals[n] = {1, 3, 5, 8, 9};
    std::cout << std::boolalpha << any_match(n, vals, is_even_int) << '\n'; // true
}

====================================================================
QUESTION 9 count_if (20 pts)
====================================================================
Return how many elements make predicate accept return true.

---

Java

import java.util.function.Predicate;

public final class CountIf {

    public static <T> int countIf(T[] data, Predicate<T> accept) {
        if (data == null)   throw new IllegalArgumentException("Null array");
        if (accept == null) throw new IllegalArgumentException("Null predicate");

        int cnt = 0;
        for (T v : data) {
            if (accept.test(v)) cnt++;
        }
        return cnt;
    }
}

---

Python

def count_if(seq, accept):
    if accept is None:
        raise ValueError("accept is None")
    return sum(1 for v in seq if accept(v))

---

C++

#include <iostream>
#include <concepts>

template <typename F, typename T>
concept Predicate = requires(F f, T t) { { f(t) } -> std::same_as<bool>; };

template <typename T, Predicate<T> F>
int count_if(const int size, T arr[], F accept) {
    int cnt = 0;
    for (int i = 0; i < size; ++i) {
        if (accept(arr[i])) ++cnt;
    }
    return cnt;
}

bool is_even(int x) { return x % 2 == 0; }

int main() {
    const int n = 6;
    int vals[n] = {1, 2, 3, 4, 5, 6};
    std::cout << count_if(n, vals, is_even) << '\n';   // 3
}

====================================================================
QUESTION 10 all_match (20 pts)
====================================================================
Return true only if every element makes predicate accept return true.

---

Java

import java.util.function.Predicate;

public final class AllMatch {

    public static <T> boolean allMatch(T[] data, Predicate<T> accept) {
        if (data == null)   throw new IllegalArgumentException("Null array");
        if (accept == null) throw new IllegalArgumentException("Null predicate");

        for (T v : data) {
            if (!accept.test(v)) return false;
        }
        return true;
    }
}

---

Python

def all_match(seq, accept):
    if accept is None:
        raise ValueError("accept is None")
    return all(accept(v) for v in seq)

---

C++

#include <iostream>
#include <concepts>

template <typename F, typename T>
concept Predicate = requires(F f, T t) { { f(t) } -> std::same_as<bool>; };

template <typename T, Predicate<T> F>
bool all_match(const int size, T arr[], F accept) {
    for (int i = 0; i < size; ++i) {
        if (!accept(arr[i])) return false;
    }
    return true;
}

bool non_zero(int x) { return x != 0; }

int main() {
    const int n = 3;
    int a[n] = {7, 5, 9};
    std::cout << std::boolalpha << all_match(n, a, non_zero) << '\n'; // true
}

====================================================================
QUESTION 11 index_of_min (20 pts)
====================================================================
Return the index of the smallest element; –1 if the collection is empty.

---

Java

public final class IndexOfMin {

    public static <T extends Comparable<? super T>> int indexOfMin(T[] data) {
        if (data == null) throw new IllegalArgumentException("Null array");
        if (data.length == 0) return -1;

        int idx = 0;
        for (int i = 1; i < data.length; i++) {
            if (data[i].compareTo(data[idx]) < 0) idx = i;
        }
        return idx;
    }
}

---

Python

def index_of_min(seq):
    if not seq:
        return -1
    idx = 0
    for i in range(1, len(seq)):
        if seq[i] < seq[idx]:
            idx = i
    return idx

---

C++

#include <iostream>
#include <concepts>

template <typename T>
concept Comparable = requires(T a, T b) { { a.compares_to(b) } -> std::same_as<int>; };

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    int compares_to(Integer other) const { return v_ - other.v_; }
};

template <Comparable T>
int index_of_min(const int size, T arr[]) {
    if (size == 0) return -1;
    int idx = 0;
    for (int i = 1; i < size; ++i) {
        if (arr[i].compares_to(arr[idx]) < 0) idx = i;
    }
    return idx;
}

int main() {
    const int n = 4;
    Integer a[n] = {Integer(9), Integer(3), Integer(7), Integer(5)};
    std::cout << index_of_min(n, a) << '\n';  // 1
}

====================================================================
QUESTION 12 arrays_equal (20 pts)
====================================================================
Return true when two collections have the same length and every corresponding pair is equal.

---

Java

public final class ArraysEqual {

    public static <T> boolean arraysEqual(T[] a, T[] b) {
        if (a == null || b == null) throw new IllegalArgumentException("Null array");
        if (a.length != b.length) return false;

        for (int i = 0; i < a.length; i++) {
            if (a[i] == null && b[i] == null) continue;
            if (a[i] == null || b[i] == null)  return false;
            if (!a[i].equals(b[i]))            return false;
        }
        return true;
    }
}

---

Python

def arrays_equal(a, b):
    if len(a) != len(b):
        return False
    for x, y in zip(a, b):
        if x != y:
            return False
    return True

---

C++

#include <iostream>
#include <concepts>

template <typename T>
concept Comparable = requires(T a, T b) { { a.compares_to(b) } -> std::same_as<int>; };

template <Comparable T>
bool arrays_equal(const int sizeA, T a[], const int sizeB, T b[]) {
    if (sizeA != sizeB) return false;
    for (int i = 0; i < sizeA; ++i) {
        if (a[i].compares_to(b[i]) != 0) return false;
    }
    return true;
}

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    int compares_to(Integer other) const { return v_ - other.v_; }
};

int main() {
    const int n = 3;
    Integer x[n] = {Integer(1), Integer(2), Integer(3)};
    Integer y[n] = {Integer(1), Integer(2), Integer(3)};
    std::cout << std::boolalpha << arrays_equal(n, x, n, y) << '\n'; // true
}

====================================================================
QUESTION 13 rotate_left (20 pts)
====================================================================
Rotate the collection left by k positions in place.

---

Java

public final class RotateLeft {

    public static <T> void rotateLeft(T[] data, int k) {
        if (data == null) throw new IllegalArgumentException("Null array");
        if (data.length == 0) return;
        k = ((k % data.length) + data.length) % data.length;

        for (int r = 0; r < k; r++) {                 // k single-step shifts
            T first = data[0];
            for (int i = 1; i < data.length; i++) {
                data[i - 1] = data[i];
            }
            data[data.length - 1] = first;
        }
    }
}

---

Python

def rotate_left(seq, k):
    n = len(seq)
    if n == 0:
        return
    k %= n
    for _ in range(k):
        first = seq[0]
        for i in range(1, n):
            seq[i - 1] = seq[i]
        seq[-1] = first

---

C++

#include <iostream>

template <typename T>
void rotate_left(const int size, T arr[], int k) {
    if (size <= 0) return;
    k = ((k % size) + size) % size;
    for (int r = 0; r < k; ++r) {           // simple O(k·n) method
        T first = arr[0];
        for (int i = 1; i < size; ++i) {
            arr[i - 1] = arr[i];
        }
        arr[size - 1] = first;
    }
}

int main() {
    const int n = 5;
    int a[n] = {1, 2, 3, 4, 5};
    rotate_left(n, a, 2);
    for (int x : a) std::cout << x << ' ';  // 3 4 5 1 2
}

====================================================================
QUESTION 14 contains_duplicates (20 pts)
====================================================================
Return true if the collection contains duplicate elements.

---

Java

public final class ContainsDuplicates {

    public static <T> boolean containsDuplicates(T[] data) {
        if (data == null) throw new IllegalArgumentException("Null array");
        for (int i = 0; i < data.length; i++) {
            for (int j = i + 1; j < data.length; j++) {
                if (data[i] == null && data[j] == null) return true;
                if (data[i] != null && data[i].equals(data[j])) return true;
            }
        }
        return false;
    }
}

---

Python

def contains_duplicates(seq):
    for i in range(len(seq)):
        for j in range(i + 1, len(seq)):
            if seq[i] == seq[j]:
                return True
    return False

---

C++

#include <iostream>
#include <concepts>

template <typename T>
concept Comparable = requires(T a, T b) { { a.compares_to(b) } -> std::same_as<int>; };

template <Comparable T>
bool contains_duplicates(const int size, T arr[]) {
    for (int i = 0; i < size; ++i) {
        for (int j = i + 1; j < size; ++j) {
            if (arr[i].compares_to(arr[j]) == 0) return true;
        }
    }
    return false;
}

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    int compares_to(Integer other) const { return v_ - other.v_; }
};

int main() {
    const int n = 4;
    Integer a[n] = {Integer(1), Integer(2), Integer(3), Integer(2)};
    std::cout << std::boolalpha << contains_duplicates(n, a) << '\n'; // true
}

====================================================================
QUESTION 15 binary_search (20 pts)
====================================================================
Assume the collection is sorted in non-decreasing order. Return the index of target, or –1 if not present.

---

Java

public final class BinarySearch {

    public static <T extends Comparable<? super T>> int binarySearch(T[] data, T target) {
        if (data == null) throw new IllegalArgumentException("Null array");
        int lo = 0, hi = data.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;          // safe mid
            int cmp = data[mid].compareTo(target);
            if (cmp == 0) return mid;
            if (cmp < 0)  lo = mid + 1;
            else          hi = mid - 1;
        }
        return -1;
    }
}

---

Python

def binary_search(seq, target):
    lo, hi = 0, len(seq) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if seq[mid] == target:
            return mid
        if seq[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

---

C++

#include <iostream>
#include <concepts>

template <typename T>
concept Comparable = requires(T a, T b) { { a.compares_to(b) } -> std::same_as<int>; };

template <Comparable T>
int binary_search(const int size, T arr[], T target) {
    int lo = 0, hi = size - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int cmp = arr[mid].compares_to(target);
        if (cmp == 0) return mid;
        if (cmp < 0)  lo = mid + 1;
        else          hi = mid - 1;
    }
    return -1;
}

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    int compares_to(Integer other) const { return v_ - other.v_; }
};

int main() {
    const int n = 6;
    Integer a[n] = {Integer(1), Integer(3), Integer(5), Integer(7), Integer(9), Integer(11)};
    std::cout << binary_search(n, a, Integer(7)) << '\n';   // 3
}

====================================================================
QUESTION 16 second_largest (20 pts)
====================================================================
Return the second largest distinct element; throw / raise if it does not exist.

---

Java

public final class SecondLargest {

    public static <T extends Comparable<? super T>> T secondLargest(T[] data) {
        if (data == null) throw new IllegalArgumentException("Null array");
        if (data.length < 2) throw new IllegalArgumentException("Too few elements");

        T max  = null, second = null;
        for (T v : data) {
            if (max == null || v.compareTo(max) > 0) {
                second = max;
                max = v;
            } else if (v.compareTo(max) < 0 &&
                       (second == null || v.compareTo(second) > 0)) {
                second = v;
            }
        }
        if (second == null) throw new IllegalArgumentException("Not enough distinct elements");
        return second;
    }
}

---

Python

def second_largest(seq):
    if len(seq) < 2:
        raise ValueError("Too few elements")
    max_val = second = None
    for v in seq:
        if max_val is None or v > max_val:
            second, max_val = max_val, v
        elif v != max_val and (second is None or v > second):
            second = v
    if second is None:
        raise ValueError("Not enough distinct elements")
    return second

---

C++

#include <iostream>
#include <concepts>
#include <stdexcept>

template <typename T>
concept Comparable = requires(T a, T b) { { a.compares_to(b) } -> std::same_as<int>; };

template <Comparable T>
T second_largest(const int size, T arr[]) {
    if (size < 2) throw std::invalid_argument("Too few elements");
    T max = arr[0];
    T second = arr[0];
    bool second_init = false;

    for (int i = 1; i < size; ++i) {
        if (arr[i].compares_to(max) > 0) {
            second = max;
            second_init = true;
            max = arr[i];
        } else if (arr[i].compares_to(max) < 0 &&
                   (!second_init || arr[i].compares_to(second) > 0)) {
            second = arr[i];
            second_init = true;
        }
    }
    if (!second_init) throw std::invalid_argument("Not enough distinct elements");
    return second;
}

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    int compares_to(Integer other) const { return v_ - other.v_; }
    int to_int() const { return v_; }
};

int main() {
    const int n = 5;
    Integer a[n] = {Integer(7), Integer(2), Integer(9), Integer(9), Integer(5)};
    std::cout << second_largest(n, a).to_int() << '\n';  // 7
}

====================================================================
QUESTION 17 prefix_sum_in_place (20 pts)
====================================================================
Transform the collection so each element becomes the sum of all previous elements including itself.

---

Java

public final class PrefixSum {

    public static void prefixSum(double[] data) {
        if (data == null) throw new IllegalArgumentException("Null array");
        for (int i = 1; i < data.length; i++) {
            data[i] = data[i - 1] + data[i];
        }
    }
}

---

Python

def prefix_sum_in_place(seq):
    for i in range(1, len(seq)):
        seq[i] = seq[i - 1] + seq[i]

---

C++

#include <iostream>
#include <concepts>

template <typename T>
concept Addable = requires(T a, T b) { { a + b } -> std::same_as<T>; };

template <Addable T>
void prefix_sum_in_place(const int size, T arr[]) {
    for (int i = 1; i < size; ++i) {
        arr[i] = arr[i - 1] + arr[i];
    }
}

class Integer {
    int v_;
public:
    Integer(): v_(0) {}
    explicit Integer(int v): v_(v) {}
    Integer operator+(Integer other) const { return Integer(v_ + other.v_); }
    int to_int() const { return v_; }
};

int main() {
    const int n = 5;
    Integer a[n] = {Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)};
    prefix_sum_in_place(n, a);
    for (int i = 0; i < n; ++i) std::cout << a[i].to_int() << ' '; // 1 3 6 10 15
}

====================================================================
QUESTION 18 swap_pairs_in_place (20 pts)
====================================================================
Swap elements in successive pairs (0,1), (2,3) … If the length is odd, leave the final element unchanged.

---

Java

public final class SwapPairs {

    public static <T> void swapPairs(T[] data) {
        if (data == null) throw new IllegalArgumentException("Null array");
        for (int i = 0; i + 1 < data.length; i += 2) {
            T tmp = data[i];
            data[i] = data[i + 1];
            data[i + 1] = tmp;
        }
    }
}

---

Python

def swap_pairs_in_place(seq):
    for i in range(0, len(seq) - 1, 2):
        seq[i], seq[i + 1] = seq[i + 1], seq[i]

---

C++

#include <iostream>

template <typename T>
void swap_pairs_in_place(const int size, T arr[]) {
    for (int i = 0; i + 1 < size; i += 2) {
        T tmp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = tmp;
    }
}

int main() {
    const int n = 5;
    int a[n] = {1, 2, 3, 4, 5};
    swap_pairs_in_place(n, a);
    for (int x : a) std::cout << x << ' ';   // 2 1 4 3 5
}

====================================================================
End of Verified 18-Question Set
====================================================================
全部示例代码均可独立编译/运行，且严格遵守此前“使用基础方法、C++ 不用 vector、保持 concept/requires 与显式 size 参数”等要求。

‍