アルゴリズム、Ｃ言語に関する問題の解答が知りたい

アルゴリズム、Ｃ言語に関する過去問を解いたのですが、あまり自分の解答に自身がないです...
添付したPDFの問題3,4の解答を教えてくれる方がいたらお願いしたいです。
記述問題もあるので、それに関する説明もしていただけると嬉しいです。

<URL(PDF)>
https://www.dropbox.com/s/m39m6283nd8bsjg/H28%E9 …

以下、自分の解答を載せておきます。(合っているかは分かりません)

問題3
(1)
(a) end = middle - 1
(b) -1

(2)
時間計算量はO(logN)
(理由)二分探索による配列の探索では、プログラム中のwhileループが一回実行されるごとに探索対象の要素数が半分ずつに減っていくから。

(3)
(c) n -> next_char[numchar(key[i]) - 1]
(d) n -> value

(4)
時間計算量はO(k)
(理由)探索はkeyに含まれた文字を有向辺とするため、キーと値の組の数には影響を受けず、プログラム中のfor文のステップ数はkeyの長さ文だけ実行されるから。

(5)
文字種が多いと、キー同士が同じ文字種を含んでいる可能性が低くなり、rootノードからのポインタが極端に多く、それ以外のノードでは枝分かれがほぼないような木構造になってしまうから。

問題4
(1)
略

(2)
図1(a) : 3, 図1(b) : 1

(3)
O(mn^2)
二重forループの内側のfor文にある「rank++;」という処理の計算量はO(m)であり、それに二重forループの計算量であるO(n^2)をかければ良いから

No.1 回答者： nouble1 回答日時： 2019/06/22 03:59

URSの　先か、

現れませんよ。