応用情報技術者 試験情報＆徹底解説

午後問3の皆様の解答を教えていただけませんでしょうか。

1.???
2.?????
3.??
4.??

文字化けしてたらすみません

試験お疲れさまでした。
今回のプログラミングは難しかったですね。。。

僭越ながら、私の解答を。

平成30年度  秋  午後 問３  プログラミング
設問１
  ア  …  １０００１
  イ  …  ＴＧＧＧＴ
設問２
  ウ  …  ３
設問３
  エ  …  ＤＥＰＴＨ－ｄ
  オ  …  ｒ
  カ  …  ０
  キ  …  ｃｏｕｎｔ
設問４  ※わからなくて適当に解答しました。
  ク  …  σ
  ケ  …  Ｎ
  コ  …  Ｎ×σ

皆さま試験お疲れ様でした。
出て来るなと思っていたオーダー記法が見事に出てきてしまいました。

終わったことは置いといて私の回答を 組込ソフト屋のケロさん と異なる部分だけ載せます。

設問2
ウ…5
設問4
コ…N×(logσ+1)
です。
ウに関しては根の0の個数なので5になります。
またコに関してもN×logσのlogσは深さを表しており、このままでは根のキー数が抜けてしまうので+1が必要になるはずです。

ちなみに設問4の他の回答に関しましては調べたところケロさんが書かれているのが正解になると思います。

コは「ビット列の長さの総和」なので
コ…N×DEPTH×(logσ+1)
ではないかと思いますが、どうでしょう？

コですが、私は  N×logσ  にしました。
図１の例を見ると、４種類（２の２乗）で１０文字の場合は、キー値のビット数は２０ビットです。
N×logσ = 10×2 = 20 で一致します。

根を忘れていますよ。
30ビットです。
正解はNo.4さんの式ですね。

本文にはウェーブレット木の構築には「ノードの深さに応じて決まるビット位置の値を取り出してキー値として登録する」と書かれています。
ビット位置は（深さ＋１）番目なので、図１の例だと根は1番目、深さ1のノードは２番目のビットになります。
このルールだと、深さ2のノードにはキー値が登録されないので、ウェーブレット木には深さ２のノードは生成されないものだと思ってました。
なので、根が10ビット、深さ１が10ビットで計20ビット。

コはNo.6さんと同じくN*logσにしました。
文字の出現回数を数える操作から、特定の文字の符号に注目すると左から1ビットずつ順に経路のキーの値になっているので、各キーの長さ(logσ)*文字数(N)が全体のキーの長さの総和になると思います。

補足ですが、
[ウェーブレット木の構築]の(3)の記述には取り出した文字列が１種類の場合は新たなノードは生成しないと書かれていますので、
やはり深さ２のノードは生成されないと思います。
図１の右側の図に深さ２まで書かれているので紛らわしいですが、実際に生成されるウェーブレット木は図１左側の深さ１の木になると思います。

私もN *logσにしました。
深さ0（根）が10ビット。深さ1（葉）が5ビット×2＝10ビット。
計:20ビットで一致すると思いました。
明日の解答速報を待つしかないですね。。

問題見直しましたが、たしかにNo10さんが言われてる通りに書かれてますね。
というより、このアルゴリズムではそもそもlogσ分のbitで1文字を表すため、この問題の例では2回までしかキーを取り出せない…
つまりウは N×logσ でしたね。
完全に勘違いしてました。