二、阅读程序（判断题每题1分，选择题每题3分，共计40分；判断题正确填 T，错误填 F）

第3题

int A[1024];
int cache[1024];

int build(int begin, int end, int node)
{
    if (begin + 1 == end) {
        std::cin >> A[begin];
        return A[begin];
    }
    else {
        auto mid = (begin + end) / 2;
        auto lson = node * 2 + 1;
        auto rson = lson + 1;
        auto left = build(begin, mid, lson);
        auto right = build(mid, end, rson);
        if (left <= right) {
            cache[node] = true;
            return left;
        }
        else {
            cache[node] = false;
            return right;
        }
    }
}

void print(int begin, int end, int node) {
    if (begin + 1 == end) {
        std::cout << A[begin] << " ";
    }
    else {
        auto mid = (begin + end) / 2;
        auto lson = node * 2 + 1;
        auto rson = lson + 1;
        if (cache[node]) {
            print(begin, mid, lson);
            print(mid, end, rson);
        }
        else {
            print(mid, end, rson);
            print(begin, mid, lson);
        }
    }
}

void solve(int n)
{
    build(0, 1 << n, 0);
    print(0, 1 << n, 0);
}

输入是 $1$ 到 $8$ 的任意一个排列时，调用 solve(3) 总会输出升序排列 1 2 3 4 5 6 7 8（ ）。

{{ select(1) }}

• 正确
• 错误