跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 2016年8月実施 午前 問8

标签：
留学警示（商务部公告2026年第12号）

根据中华人民共和国商务部公告2026年第12号，东京科学大学（東京科学大学/Institute of Science Tokyo）已被列入关注名单。请中国留学申请者慎重考虑相关风险，在做出留学决定前充分了解相关政策及其可能带来的影响。

Author​

GPT-5

Description​

A nearly complete binary tree is filled on all levels except possibly the deepest, which is filled from the left. Indexing its nodes from 0 in level order gives an array representation . It is a heap when

for every non-root node .

Index 0123456789
15121011897632

The height of a node is the number of edges on its longest path to a leaf. The following properties may be used.

  • (P1) The root of an -element heap has height .
  • (P2) The number of nodes of height is at most .

The following code constructs a heap.

void heapify(int a[], int i, int n) {
    int k = 2*i+1;             /* node k is the left child of node i */
    while (k < n) {
        if (k+1 < n && a[k+1] > a[k]) k = k+1;
        if (a[i] >= a[k]) return;
        int tmp = a[i];
        a[i] = a[k];
        a[k] = tmp;
        i = k; k = 2*i+1;
    }
}

void build_heap(int a[], int n) {
    for (int i = n-1; i >= 0; i--) {
        heapify(a, i, n);
    }
}

(1) Find the number of different 7-element heaps containing all integers from 1 to 7.

(2) Run build_heap(a1,10) for and give the resulting array.

(3) Explain why heapify(a,i,n) takes time for a node of height .

(4) Show using (P1), (P2), and that build_heap(a,n) takes time.

Kai​

(1)​

根には最大値 7 を置く必要がある。残り 6 個から左の 3 頂点部分木に置く値を選ぶ方法は 通りである。各 3 頂点部分木では最大値が根に決まり、残り 2 値の左右への配置が 2 通りある。したがって

(2)​

値が変化する呼び出しを追うと次のようになる。

処理後配列
初期状態（ の処理後も同じ）

よって

(3)​

ループ 1 回の比較・交換は定数時間であり、交換後は注目節点が子へ 1 段下がる。高さ の節点から葉まで高々 段なので、反復回数は高々 、実行時間は である。

(4)​

とし、高さ の節点数を とする。葉を含む各呼び出しの定数時間を 、下向き処理を節点当たり 以下と評価すると、(P2) より

かつ なので

目录