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

自分の勉強も含め、解説が載ってないものについては、
H29秋のものから5年分ぐらいは解説書こうと思います。
問題文については深く記述しないのであしからず。

------------以下解説---------------

H29秋  問9  C言語  回文の探索

注：プログラム中の「const char*」型は、読み取り専用のchar型です。
    ここでは例として「abc0cbe」の回文を探索することにします。

設問１
まず、各関数のプログラムの意味を簡単なものから理解しましょう。

・関数 find_char(const char* str, char ch)
この関数の説明に「文字列 str 中で,文字 ch が最初に現れる位置を求める」とあります。
if文で空欄 c が真ならば return 文によってその位置が返されるので、
空欄 c に入る論理式は str[i] と ch が同じ文字である、と言えればいいですが、
大文字と小文字を区別せず一致判定をさせる必要があります。
ライブラリ関数 tolower(ch) を使えば大文字を小文字に変換できますが、
str[i] も ch もどちらが大文字かわからないので、どちらも tolower(ch) に通す必要があります。
よって空欄 c は  ウ  です。

・関数 is_palindrome(const char* chars, int size)
この関数の説明には「文字の並び chars が回文かどうか判定する」とあります。
関数内で宣言されている l と r は for 文内で
l は chars の先頭から上がっていき、r は末尾から下がっていきます。
その後の while 文で空白・記号でないときに加算または減算しています。
このことから、先頭から l 番目と末尾から r 番目の文字がすべて同じであれば回文と言えます。
if文が死んで通った先には return 文で 0 が返されていますので、
論理式には先頭から l 番目と末尾から r 番目の文字が異なる、と言えればいいわけです。
この判定も大文字小文字を区別せず判定し、どちらが大文字かわかりません。
よって空欄 b は  カ  です。

・関数 find_palindome
12-14行目では、text[i] が空白・記号のとき continue ではねています。
そのあとの記述が重要です。

15行目においてポインタ ith に &text[i] を代入しています。
次に16行目では関数 find_char(ith + 1, *ith) の結果を代入しています。
関数 find_char の説明に「文字列 str 中で,文字 ch が最初に現れる位置を求める」とありました。

つまり16行目でやっていることは,
文字 taxt[i] 以降の文字列から最初に出てくる text[i] (同じ文字)を探してポインタ hit にその位置のポインタを渡している
ということになります。

==========続く

==========続き

例では,最初の文字「a」はそれ以降どこにも出てきませんので hit に代入されるのは NULL ポインタであり、直後の while 文は実行されません。
その後の文字「b」は 6 文字目にでてくるので、ここのポインタが hit に渡されます。

次に while 文に入ると空欄 a があります。
これは回文となる「かもしれない」文字の並びの長さ psize を求めています。
どういうことかというと、19行目で関数 is_palindrome によって回文かどうか判定していますが、
重要なのはその引数で、ポインタ ith にある位置から数えて psize 文だけのところで回文かどうか判定するのです。

例でいえば、2 文字目の b から 6 文字目の b までの 5 文字を判定するわけです。
2 文字目の b はポインタ ith によって、6 文字目の b はポインタ hit によって位置が格納されていますので、hit - ith + 1 で psize が求まります。
例を用いて感覚的に言えば、hit - ith + 1 = 6 - 2 + 1 = 5 というわけです。
よって空欄 a は  オ  です。

その後のプログラムも確認しましょう。
19行目で関数 is_palindrome によって回文かどうか判定して、真ならば印字して終了です。
重要なのが 27 行目です。
ここは回文か判定して回文でないときに実行されます。
ここでは、hit (text[i]と同じ文字の位置) を変更してますが、今 hit にある位置以降も、
text[i] と同じ文字がある可能性があるので、hit + 1 以降の文字列から *ith = text[i] を探しているんですね。

設問２
回文が2つ以上ある場合、長さが長いものを表示するようにプログラムを変更します。
関数 find_char(const char* str, char ch) を
find_last_char(const char* str, char ch, int count) と名称変更しています。
この関数で探すのは str 中、先頭から count の範囲で ch と一致する「最後の」文字です。

変更内容表を確認します。
表 3 行目では textlen として回文を探索する文字列の長さを渡します。
表 4 行目は 16 行目を
hit = find_char(ith + 1, *ith)
から
hit = find_last_char(ith + 1, *ith, textlen - i - 1)
としています。
探すのは ith 以降の文字列ですので、全体 textlen から ith の位置分 (i + 1) を引いているわけです。(i は 0 スタートなので i + 1 を引きます)

表 5 行目は、行番号 27 を変更します。
ここも find_last_char の引数 count を考えますが、
find_last_char が末尾から一致文字を探索していることに注意です。
ですので、hit にある位置よりも前で再度一致文字を探索する必要があります。
よって行番号 27 の変更結果は
hit = find_last_char(ith + 1, *ith, psize - 2)
ith + 1 から再度検索し、psize から 2 減らして(回文なので2減らした方が速い)、探索します。
よって空欄 d は  オ  です。

==========続く

==========続き

表 6 行目、関数 find_last_char の変更内容です。
末尾から探索していくのですが、当然配列は 0 から始まるので、
count - 1 から 0 までで探索します。
よって空欄 e は  エ  です。

設問３
実際の回文を探索する際、実行回数を回答する問題です。
「No!_Madam,_I'm_Adam_Graham._This_is_my_gym.」(ここでは空白を_で表示)
プログラムを追いながら数えていきましょう。

先頭「N」→ 関数 find_last_char が呼びだされるが返されるのはNULL、やり直し
2文字目「o」→上に同じ。
3-4文字目「!_」→空白・記号なので関数 find_last_char は呼び出されない。
5文字目「M」→関数 find_last_char が呼び出され末尾から 2 文字目「m」(gym の m)へのポインタが返される。
while文に入り、当然回文ではないので変更内容表 5 行目の内容が実行される。
そこでは末尾から 7 文字目「m」(my の m)が返され、以下同様。
次に末尾から 18 文字目「m」(Graham の m)が返され、以下同様。←ーーα
次に末尾から 25 文字目「m」(Adam の m)が返され、回文となり終了。

上記より関数 find_last_char の呼び出し回数は 6 回。
よって空欄 f は  オ  です。

空欄 g については、上記のαの直後、 while 文の先頭に戻り、psize が求められますが、ここでの psize を考えれば空欄 g がわかります。
αの直後で ith は先頭から 5 文字目、hit は先頭から 26 文字目です。
なのでこの後に求まる psize は hit - ith + 1 = 26 - 5 + 1 = 22 です。
psize が求まったら、回文ではないので再度 hit を求めます。
ここでの引数 psize - 2 = 22 - 2 = 20 が最後の呼び出しにおける引数 count の値となります。
よって空欄 g は  イ  です。

【総評】
例年よりかなり難しいと感じました。(実際私も半分しか取れませんでした)
ポインタをよく理解していないと最初からつまずくので、設問１は c,b,a と逆順で解いた方が点が取れたかもしれません。

この投稿は投稿者により削除されました。(2018.04.01 20:37)

ご投稿くださり誠に感謝いたします。
内容をこちらで確認し、問題がないようでしたら解説文としてアップロードさせていただきたく存じます。

管理人様
ありがとうございます。以降のものも掲載していただいて構いません。

------------以下解説---------------

H29春  問9  C言語  マーク式試験の答案の採点

注：ここでの unsigned char の定義は「16 ビットのビット列で表し、連続する 8 ビットが全て0のときは 0...0 全て 1 のときは 1...1 と表す」と書かれています。

設問１
プログラムを埋める問題です。

関数の中身を見ていきましょう。
最初の if 文 type[i] == 1 は、type[i] が 1 である、
つまり答えを一つだけマークする問題のとき、
ansE[i] == ansC[i] (正解) であるならば、1 を格納します。

次の else if 文 (2 <= type[i]) && (type[i] <= 8) は、
同様に答えを type[i] = n 個マークする問題のときです。
次の if 文の空欄ですが、採点方法の表によると
「ansE[i] 中の 1 のビットの個数が n + 1 個以上 (必要以上にマークしている) なら 0、
n 個以下なら ansC[i] と ansE[i] の対応するビットがともに 1 である個数 (正解したマーク数)」
と書かれていますので、
関数 countMarkBits によって ansE[i] の 1 のビットの個数を調べ、それが n = type[i] 個以下ならいいわけですね。
よって空欄 a は  カ
空欄 b は キ  です。

「n 個以下なら ansC[i] と ansE[i] の対応するビットがともに 1 である個数 (正解したマーク数)」
とありますので、
countMarkBits によって ansC[i] と ansE[i] の論理積 (AND) の 1 のビットの個数を調べればよいわけです。
論理積を表す演算子は「&」ですので、
空欄 c は  エ  です。

設問２
countMarkBits のプログラムを追う・読み解く問題です。

このプログラムは引数 unsigned int ans で与えられたビット列の 1 のビットの個数を調べる関数です。
γが実行される前に work = 0101 0000 0...0 ならば、その実行結果は
work = work & (work - 1)
= 0101 0000 0000 0000 & (0101 0000 0000 0000 - 0000 0000 0000 0001)
= 0101 0000 0000 0000 & 0100 1111 1111 1111
= 0100 0000 0000 0000
= 0100 0000 0...0
となるため、
空欄 d は  イ  です。

次の設問ですが、このγの記述中の「&」を「&&」に変更したらどうなるか聞かれています。
「&」はビットの論理積を施す演算子ですが、「&&」は true と false の論理積を扱う論理演算子ですので、その結果は true または false となります。
よって空欄 e は  イ  です。

==========続く

==========続き

設問３
プログラムを順不同形式に対応するよう書き換える問題です。
sumC = sumC | ansC[i]
では、正解となるビットを sumC に順次加算していき、複数回答の形式と同じようにしていきます。
sumE に関する記述も同じですが、この記述は ansE[i] の 1 のビットの個数が 1 であるときに限られます。
ですので、図 4 の例において ansE[20] 及び ansE[21] は if 文を通りますが、
ansE[22] については 1 のビットの個数が 2 ですので通りません。
よって空欄 g は  イ  です。

採点結果については、順不同形式の問題で type[i] = 13 のとき
つまり順不同の末尾のときに、その末尾の mark[i] に正解の個数が格納されますので、
図 4 の例では mark[20] 及び mark[21] には 0 が格納されたままになります。
mark[22] に正答数が格納されるので、この例での正答数は sumE の結果から 1 ですので
空欄 f は  ア  です。

【総評】
採点方法をしっかり把握してさえいれば、プログラムは比較的簡単なので追いやすいと思います。
演算子に関する知識がないと詰まってしまいますので、しっかりと演算子に関する知識も身に着けておきましょう。

・余談
問9 C言語の問題は、期ごとにかなり難易度のばらつきがありますので、本番では最初に内容を見てから時間配分を考えた方がいいと思います。
特に、構造体・ポインタ・ファイル入出力の知識に不安がある方なんかは…
先に C を解いてしまうのも手です。
C をやってると特に見直しの時間なんか20分あっていい方です。
時計は当日持っていきましょう。余裕ぶっこいてるとどえらいことになりますので…

ありがとうございます。
平成29年秋期午後問9（C言語）の解説をアップロードいたしました。
  http://www.fe-siken.com/kakomon/29_aki/pm09.html

平成29年春期午後問9（C言語）についても解説をアップロードいたしました。
  http://www.fe-siken.com/kakomon/29_haru/pm09.html

みなさん午前午後と、お疲れさまでした。
私も初めて受けましたが、午前が難しかった…。61問正解の76点でした。
資格の大原さんが問8の解答を出していらっしゃって、なんと全当だったので僭越ながら解説を。
（自慢ぽくてごめんなさい）

------------以下解説---------------

H30春  午後  問8  データ構造及びアルゴリズム  ヒープの性質を利用したデータの整列

ヒープの性質を利用した、データ整列アルゴリズムです。

プログラム1は,配列 data に格納されている無作為な数値を,法則に従ってヒープとなるように並び替えるプログラムです。
重要なのは〔プログラム1の説明〕の (2)③ の記述,
「配列要素 heap[i] (i = 0, 1, 2, ...) に対応する節の"左側の子は配列要素 heap[2×i + 1] に対応し,右側の子は配列要素 heap[2×i + 2] に対応する。」
にある""で囲った部分です。
つまり,親が 0 なら左の子は 0×2 + 1 = 1 で右の子は 0×2 + 2 = 2 となり,親が 2 なら左の子は 2×2 + 1 = 5 で右の子は 2×2 + 2 = 6 となります。

(4) で説明されている関数ですが,
lchild は左の子の配列要素の【要素番号】を返却
rchild は右の子の配列要素の【要素番号】を返却
parent は親の配列要素の【要素番号】を返却
というふうに,【要素番号】を返却することに注意です。

プログラム makeHeap の中身を見ると,
繰り返し処理の一行目で"heap にデータを追加"しています。
その後に空欄 a の処理をしていますが,空欄 a が真ならばプログラム swap によって,
"【要素番号】の引数 k と 空欄b の配列要素を入れ替えて"います。
元のデータ配列 data を事前に入れているわけですが, data はヒープの性質を満たすように整列されていないので,並べ替える必要があります。
並べ替える必要がある状況は,【自分の親の配列要素と比較して自分の方が大きいとき】です。

例えばヒープの根である heap[0] は一番大きくなくてはいけないので,
deta が 30 60 45 15 5 10 20 と並んでいたら 30 と 60 を入れ替えなくてはなりません。

要素番号 3,4 の親は要素番号 1 であり,子の配列要素は親の配列要素よりも大きくてはダメなので,
dataが 60 15 45 30 5 10 20 と並んでいたら 15 と 45 を入れ替えなくてはなりません。

（ここに書いてある例を図2の配列に書き込むとわかりやすいです、ここではわかりにくいと思います）

つまり、"子の配列要素が親の配列要素よりも大きくなっている"とき,
swap プログラムによって子の配列番号と"親の配列番号"を引数にとって,その配列要素を入れ替える
という操作が必要です。
いま""でそれぞれ囲んだところが空欄 a, b の答えです。
親の配列番号を返却する関数は parent ですので,
空欄 a は  イ
空欄 b は  エ  です。

==========続く

野暮用で続きは数時間後に上げます

数日経ってしまいました。すいません。

管理人さんへ
更新された掲示板でも後ろの方だとトップページに上がらないので、もしお手すきでしたらそこの仕様を変更してもらえると助かります。
思い違いだったらすいません。

==========続き

プログラム2は、プログラム1でヒープとなるように並べた配列を用いて,データを降順に並べるプログラムです。
このプログラムの"降順に並べる"という仕組みは書かれてはいませんが,解く際はあまり関係ないと思います。分かっていた方がプログラムの内容は分かりやすいです。

〔プログラム2の動作〕中の空欄が問題ですが,
最初の記述が大事です。この記述の中では図 2 に示されている,
60 30 45 15 5 10 20 という順番でデータが格納されている状態でプログラム 2 を動かす,ということをしています。

空欄 c で聞かれていることは「副プログラム heapSort の行番号 5 の副プログラム swap の実行が終了した直後の配列要素 heap[0] の値」です。
行番号 5 は「・swap(heap, 0, last)」ですから,heap[0] と heap[last] の値を交換しています。
最初の last の値は繰り返しの記述にある通り hnum - 1 つまり最後の要素ですから,
60 と 20 を交換していることになります。
すなわちデータの並びは 20 30 45 15 5 10 60 となりますから直後の haep[0] の値は 20 です。
よって空欄 c は  エ  です。

空欄 d ですが、ここは文脈から「rchild(n) ≦ hlast」の次の行「heap[tmp] ≦ heap[rchild(n)]」の意味を聞いているということがわかります。
tmp は (2) の最初の記述から左側の子の要素番号ですので,不等号の向きを見れば
空欄 d は  イ  です。

空欄 e についてはプログラム downheap を追えばわかります。
データは 20 30 45 15 5 10 60 と並んでいて,最初の n は 0 ですから
tmp には heap[0] = 20 の左の子 heap[1] = 30 の要素番号 1 が入ります。
左の子 heap[1] = 30 と右の子 heap[2] = 45 では 45 の方が大きいですから
tmp は右の子 heap[2] = 45 の要素番号 2 に置き換わります。
heap[tmp] = heap[2] = 45 と heap[n] = heap[0] = 20 は heap[tmp] の方が大きいので
swap(heap, n, tmp) = swap(heap, 0, 2) が実行され 20 と 45 が入れ替わり
データは 45 30 20 15 5 10 60 と並びが変わります。
そして行番号 15 の「n ← tmp」には  tmp = 2 が入ります。
よって空欄 e は  2  です。

【総評】
僕個人ではですが、ここ最近で一番簡単だと感じました。
プログラムを埋める問題も少なかったので、点の取りどころだと思います。

ご投稿ありがとうございます。

>更新された掲示板でも後ろの方だとトップページに上がらないので、もしお手すきでしたらそこの仕様を変更してもらえると助かります。
掲示板の投稿がトップページでアナウンスされる基準ですが、以下の2つをともに共に満たしたときに設定しています。

・そのスレッドの新規立ち上げ（初投降）から7日以内のものあること
・投稿が現時点から72時間以内に行われたこと

本スレッドがトップページには掲載されないのは、スレッド作成日が4月1日だからです。春期試験の午後問題に関しては皆さんも知りたい情報だと思いますので、新規スレッドを立ち上げて、ご投稿内容をそのまま転機していただいてもよいと思いますよ。

失礼いたしました。誤字を訂正いたします。

×  初投降
○  初投稿

管理人様
そうですね、真スレッドを立ち上げるのも情報が散在してと思ったので一応聞かせていただきました。立ち上げておきます。