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

かんたん合格  基本情報技術者予想問題集の問題について質問です。

下記設問について、解説を読んで解き方は分かったのですが、プログラムの「heapの末尾にdata[i]な値を追加する」のところが、解説をみると配列の先頭にデータを追加していたのが理解できませんでした。
プログラムで末尾に追加とあるのに配列の先頭にデータを追加するのは何故でしょうか。
初歩的な質問になってしまい申し訳ないのですが、よろしくお願いします。


【予想問題② 問15】
配列を用いてヒープを実現するプログラムである。ヒープとは二分木であり、本問では親は一つ又は二つの子をもち,親の値は子の値よりも常に大きいか等しいという性質を持つものとする。

プログラムは、整数型の配列dataに格納されているn個(n>0)のデータを、次の①～③の規則で整数型の配列heapに格納する。配列の要素番号は1から始まるものとする。

①配列要素heap[i](i=1,2,3,?)は、節に対応する。配列要素heap[i]には、節が保持する値を格納する。
②配列要素 heap[1]は、根に対応する。
③配列要素 heap[i](i=1,2,3,?）に対応する節の左側の子は配列要素heap[i×2]に対応し,右側の子は配列要素heap[i×2+1]に対応する。子が一つの場合,左側の子として扱う。

プログラムの実行後,配列heapの内容はXとなる。

整数型の配列:data(5,10,15,20,30]
整数型の配列:heap ]
整数型:i,parent,curr
for(iを1から dataの要素数まで1ずつ増やす)
 heapの末尾に data[i]の値 を追加する
 curr - i
while(currは1より大きい)
  parent - curr - 2 の商
  if (heap[curr] はheap[parent]より大きい)
   heap[parent]とheap[curr] の値を交換する
   curr - parent
  else
   break
  endif
 endwhile
endfor

解答群
ア[5, 10, 15, 20, 30]
イ[5, 10, 20, 15, 30]
ウ[20, 30, 10, 5, 15]
エ[20, 30, 10, 15, 5]
オ[30, 20, 10, 5, 15]
カ[30, 20, 10, 15, 5]
キ[30, 15, 20, 5, 15]

※解答はオになります。

プログラム途中の演算子がちょっと違うと思いますがなんとなく分かったので記載してみます。
> curr - i
curr = i
> parent - curr - 2 の商
parent = curr / 2 の商
> curr - parent
curr = parent

「末尾に」なのに先頭では？という所ですが、これは容量が固定の配列だから違和感が有ったのだと思います。

data{5,10,15,20,30}を1個ずつ、heap{空}の末尾に追加とすると
※要素０のheapの末尾は先頭
1回目( 5)を追加  →  heap{5}
※要素１のheapの末尾は２つ目
2回目(10)を追加  →  heap{5,10}
※要素２のheapの末尾は３つ目
3回目(15)を追加  →  heap{5,10,15}

とheapに「格納されている要素の末尾」という意味なので、この末尾にという部分だけであればイメージ的にはキューの様な扱いですね
※実際の処理はこの後インデックスで指定するのでキューでは処理できないので配列ですが

電タック様

ご返信ありがとうございます！
またプログラムの修正もありがとうございます。
ご修正いただいた内容が正しいプログラムでした。

疑問点解消できました。
まだまだ考え方が甘いので勉強頑張ります。

お忙しいところありがとうございました！

ちなみに賛否はあるかもしれませんが、実際の試験ではこの日本語で書いてくれてる部分は参考程度に斜め読みするのが良いと思います。

実際プログラムで問われている部分に①②③はほとんど関係なくheapはこういうものですの説明になっていて、使える情報は「配列の要素番号は1から始まるものとする」だけです。
プログラムを見ても「i×2」や「i×2＋１」で参照している箇所がありませんし
今回違和感があった「末尾に」というのも、質問者さんは先頭から入れているというのが分かっていたので無視して良い要素だったかもしれません。

あまりお行儀は良くないでしょうがプログラムをとりあえず読もうとして、何やってるかよくわからない、この変数で分岐してるけど何の意味？、設問で抜けている部分が現れた、みたいに足りない事態が発生した時に日本語説明を頼るのも１つの手です。
※この辺は旧午後試験にあった説明の長文を全て読んでからだと時間が間に合わない為、設問を先に見てから長文に戻るのテクニックに近いです

個人で色々やり方があると思いますので１つの考えとして思っていただけると幸いです。

>プログラムは、整数型の配列dataに格納されているn個(n>0)のデータを、次の①～③の規則で整数型の配列heapに格納する。配列の要素番号は1から始まるものとする。
>
>①配列要素heap[i](i=1,2,3,?)は、節に対応する。配列要素heap[i]には、節が>保持する値を格納する。
>②配列要素 heap[1]は、根に対応する。
>③配列要素 heap[i](i=1,2,3,?）に対応する節の左側の子は配列要素heap[i×2]に対応し,右側の子は配列要素heap[i×2+1]に対応する。子が一つの場合,左側の子として扱う。

連投すみません。

実務では説明をできるだけ読んでください（笑）
時間制限が有って、バグは無視していい試験問題故のテクニックでした・・・