跳到主要内容

電気通信大学 情報理工学研究科 情報・ネットワーク工学専攻 2024年8月実施 選択問題 アルゴリズムとデータ構造

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

二分木の再帰的な深さ優先走査について、中順走査の出力位置を答え、スタックを用いる非再帰版を書け。また、10,15,3,2,7,4,1210,15,3,2,7,4,12 を順に挿入した二分探索木を描き、最悪時の計算量を説明せよ。

最後に、キー 11,12,13,14,1511,12,13,14,15 の探索頻度がそれぞれ 4,2,1,3,34,2,1,3,3 のとき、探索コストが最小となる二分探索木を求めよ。

题目描述​

回答二叉树中序遍历的输出位置，写出基于栈的非递归中序遍历；构造指定插入序列的二叉搜索树并说明最坏复杂度；再按给定查找频率求最优二叉搜索树。

Kai​

(1)​

中順走査では左部分木を走査した直後に根を出力する。したがって、

（イ）\boxed{\text{（イ）}}

である。

(2)​

InOrder(root)
    S <- empty stack
    p <- root
    while p != NULL or S is not empty
        while p != NULL
            push(p, S)
            p <- left[p]
        p <- pop(S)
        output key[p]
        p <- right[p]

(3)​

挿入後の二分探索木 T2T2 は次のとおりである。

(4)​

昇順または降順に近い順序で挿入すると、木が片側だけに伸び、高さが n−1n-1 となり得る。このとき探索・挿入・削除には根から最大 nn 個の頂点を調べる必要がある。したがって、

最悪計算量は O(n)\boxed{\text{最悪計算量は }O(n)}

となり、平衡な場合の O(log⁡n)O(\log n) より悪化する。

(5)​

区間 i,…,ji,\ldots,j の最小コストを C(i,j)C(i,j)、頻度を qkq_k とすると、

C(i,j)=min⁡i≤r≤j{C(i,r−1)+C(r+1,j)+∑k=ijqk},C(i,i−1)=0.C(i,j)= \min_{i\le r\le j} \left\{ C(i,r-1)+C(r+1,j)+\sum_{k=i}^{j}q_k \right\}, \qquad C(i,i-1)=0.

この漸化式を計算すると最小値は 2727 で、根は 1414 となる。

実際、探索コストは

3⋅1+4⋅2+3⋅2+2⋅3+1⋅4=27.3\cdot1+4\cdot2+3\cdot2+2\cdot3+1\cdot4 =\boxed{27}.
本页目录