基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

タイトルの問題について解説を見るもわからなかったのでこちらで共有させていただきます。
設問1までは理解できたのですが、設問2からよくわかりません。
とくに設問2の8.9行で行っている動作がわからなくなってしまいました。
i,jには要素番号が入っていて、それをleft[], right[]にいれるのは分かるのですが、
[size]となっているため、要素番号を入れるのか、葉の節の個数を入れるのかわからなくなってしまいました。
また、そのほかの引数[nsize][node]等もなんとなくの理解になっているので、こちらの設問全体の解説をどなたかしていただけますでしょうか。
※できれば解答C→Dの順で解説いただけますと幸いです。

この投稿は投稿者により削除されました。(2021.03.17 18:22)

Huffmanの中でSortmodeが実行されているので、おそらくD→Cの方がわかりやすいと思います。
まず、簡単な配列を図３を参照して作ります。要素番号:freqの順で書きます。
[0]10,[1]2,[2]4,[3]3
とします。
では、Huffmanが受け取る引数を見ていきます。
sizeは、節の個数なので、4です。他の整数型であるparentからrightまでの配列は初期化されたままなので、ー1です。freqには先程例に出した配列データが入っています。
そして、4行目でそのままSortmodeにデータが引き渡されます。前後するので、注意してください。
プログラムSortmodeが呼び出されたので、Sortmodeを見ていきます。
Sortmodeが受け取る引数は、先程と同じです。整数型のnsizeがありますが、Sortmode内の18行目で0に初期化されているので、この時点で大して気にする必要はありません。
では、19行目から見ていきます。
■変数iを0から3まで増やしながらループさせています。要素番号は0から始まるので、問題ありません。
  ↑空欄dです
    node{nsize(一回目なので0)]←に0を入れています
  ↓nsize(一回目なので同じく0）←を１増やしています。
■
25行目のSortで、要素を昇順に並べ替えています。
Sortmodeが一体何をしているのかは、問題文に説明があります。何らかの方法によって親がいない節を抽出した後に、要素番号を配列nodeに格納しているそうです。親がいない節を抽出してそうな作業が明らかにアルゴリズム内にないので、空欄dでありそうだとなります。
親がいない節をどうやって割り出すのかといえば、要素番号0なら、そのparent[0]を見ればいいわけです。なぜなら問題文に、すべての要素は-1で初期化されているとあるので、根に辿り着かない限りは、parent[]の値が0より小さければ、その要素番号には親がいないということがわかるからです。0から3までiを増やしている事、sizeが節の個数を表していること(この場合は4)を見ると、要素番号0から3までを順に見て、それぞれ判断しているわけだとなります。ここまでわかれば、dにエが入ることがわかるはずです。
そして、忘れてはいけないのが、昇順に並べ替えられていること。一旦、配列を示してみます。
配列freq
0:2、1:3、2:4、3:10
配列node(親がいない節、この場合全ての要素番号)
0:0、1:1、2:2、3:3
この状態で、副プログラムHuffmanに戻ります。
よく覚えて置かなければならないのが、sizeは節の個数、つまり4であることです。
■空欄c
 i←node[0](この場合０)
 j←node[1](1)
  left[size=4]←2
  right[4]←3(この２つの作業で、要素番号4のleftとrightに値が設定されます)
  freq[4]←要素番号0と1の節の値を合計したものを代入します
  parent[0]に、親である要素番号の4を代入
  parent[1]に、同じく4を代入
  sizeがここで、＋1されます。
  再びSortmodeが呼び出されます
■
ざっと説明すると、Huffmanはこんな感じで、図３のような表を配列を作り出しています。
中で何をしているのかには気づいても、具体的な説明がないので戸惑いますが、ここ最初に読んだはずの問題文にヒントがあることに気づく必要があります。
「親が作成されていない節を二つ選択し，選択した順に左側の子，右側の子とする親の節を一つ作成する。この節の値を，配列中で値が格納されている最後の要素の次の要素に格納する。節の選択は節の値の小さい順に行い，同じ値をもつ節が二つ以上ある場合は，配列の先頭に近い要素に値が格納されている節を選択する。」
そして、「親が作成されていない節が一つになるまで③を繰り返す。」
とあるのです。
しかし、この条件を達成するためのコードがHuffmanの中にあるかと見ると、どう見てもありません。どう見ても空欄cでループ条件を設定しています。
では、親が作成されていない節というピンポイントな条件を、どうやって見つけるか。ここで、副プログラムSortmodeが渡してくる、配列nodeとnsizeを思い出します。配列nodeには、親が作成されていない要素番号が格納されています。そして、nsizeは、nodeに値を格納するたび、＋１されています。つまり、nsizeという変数は、親が作成されていない要素番号の数が格納されているんだと、遅いながらもここで以前私は気づきました。
一回しかトレースしていませんが、わからなければ聞いてください

アメフラさん  いつも解説いただきありがとうございます。
まだ空欄Dしか読んでないのですが二点質問があります。
①親がいない節→根がの値が入っている要素だと思うのですが、
昇順に整列された配列node(親がいない節、この場合全ての要素番号)では0.1.2.3を抽出しています。
図3の表の0.1.2.3の要素だとすべて親がいると思うのですが、なにか認識が違っているのでしょうか。

②配列freqがどのタイミングで昇順に整列されたのかわかりません。

この投稿は投稿者により削除されました。(2021.03.18 09:48)

書き間違えたので削除しました。
図３の表は、図１に示したハフマン木を完全に表現したものです。
副プログラムHuffmanに引き渡される情報である、(3)をよく読んでみてください。全て、初期化されています。唯一データとしてあるのは、「初期化された後，文字の出現回数が要素番号0から順に格納された配列 freq」です。つまり、データが最初に引き渡される時点においては、要素番号0,1,2.3のデータしかまだ作成されていないんです。
そして、配列freqが整列されるタイミングですが、(5)を読んでください。「副プログラム Sort (プログラムは省略)は・・・」の以下の文です。そして、副プログラムSortmodeを注意深く見てください。さらっと副プログラムSortが呼び出されていることに気づくはずです。

説明の（4）（5）の考え方って以下ではないですかね・・
わからなくなってしまったので、どこの考え方が違うか教えていただけますか。
（4）
①親が作成されていない節を抽出し→freq[0.10][1.2][2.4][3.3]の右部分
②節の値の昇順に整列し→配列の左の要素ではなく右部分の節の値の昇順→[1.2][3.3][2.4][0.10]
③節を表す要素組の要素番号を順に配列 node に格納し（この後（5）の副プログラムSortにいくんですよね？）
→node[0.1][1.3][2.2][3.0]
副プログラムsort
→node[0.1][1.3][2.2][3.0]（上記と一緒になってしまいます。）

度々すいません。さっき送ったの間違っている気がして明日朝早くて集中して解けなそうなので、また時間あるときに解いて質問させていただきます。何回もやり取りさせてしまいすいません。。