二、阅读程序（判断题每题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);
}

输入 9 2 7 4 1 8 3 6 并调用 solve(3)，输出是（ ）。

{{ select(1) }}

• 2 9 4 7 1 8 3 6
• 2 7 4 9 1 3 6 8
• 1 8 3 6 2 9 4 7
• 2 9 4 7 1 3 6 8