基本情報者試験2006年秋期問13問について

質問

基本情報者試験2006年秋期問13問について質問があります。
http://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2006h18_2/2006h18a_fe_am_qs.pdf

この問題において
配列の2行目の中身の値は、
初期が上から順に
2、3、4、0、空欄
一回目の操作で
2、3、4、0、3
となり
二回目の操作で
5、3、4、0、3
になり、空欄と0とNULLは同意意義で考えてよろしいのでしょうか？

また、一回目の操作と二回目の操作を入れ替えるとなぜデータが壊れてしまうのでしょうか？

回答No.4

superside0 · ベストアンサー

自分がこれをプログラムしたときにイメージとしてNULLが出てきたということなのですね。

0またはNULLがリストの終端の意味というのは、よく使われる手法ですもんね。
（別にNULL以外でターミネートしても、ロジック的に矛盾がなければ使えるので、
　あくまでも作法の問題かとは、思いますが）

で、この表の見た目として空欄なのは、　
””の空文字のことなのか、0なのかNULLなのか、それとも不定なのか
分からないけど、どれのことなのか？　という質問だったのですね。
失礼しました。

これは、どこからも参照されていない場合は、なんでもよいということでしょう。
ただし、これを参照するように誤ったロジックとなった場合に、ここの値が
空文字（へのポインタ）/0/NULL/不定　のいずれかで　結果が変わってくることに
なりますね。
これは、この表の空欄の意味を　どうプログラムとして表現するかの
コーディング側の問題なので、出題内容とは直接関係はしてこないと思います。

誤った操作順でプログラムを実装することを想定した出題内容ではないでしょうから。

回答No.3

superside0

>また、一回目の操作と二回目の操作を入れ替えるとなぜデータが壊れてしまうのでしょうか？
あ、もしかして実際に、リスト型のプログラムを作って、
操作１、２のあとにそれぞれで、そのリスト型を順番にめくってみたってことなのですかね。

操作２を最初に行うと
１　東京　５
２　品川　３
３　名古屋４
４　新大阪０
５　新横浜　空欄
（空欄は、プログラム的に初期値代入か暗黙の初期化でNULLとなっているか、
初期化してなければ不定値か）
となり、
この状態でリストを順にめくっていくと
東京の次が、５行目の新横浜、
新横浜の次は、NULLないしは不定値。
よってここでリストが止まるか、別のとんでもないポインタに飛んでしまうか、
ってことでしょう。

回答No.2

superside0

初期の
1東京 2
2品川 3
3名古屋 4
4新大阪 0
5新横浜 空欄

という状態で、どうやって「東京→品川→名古屋→新大阪」という順番と 新横浜がないのを
表現しているかを、まず、見つける必要がありそうですね。

気になるのは、操作として、A(A1,2),2) の２列目の値を、さらに行番号に使うような処理があることです。
これを考えると、どうやら、２列目は　ソートキーではなく、
次の行き先を行番号で示しているのではないかと　推測できます。

つまり、東京=2ということは　東京の次は２行目(品川)、同じように→名古屋→新大阪ときて、
最後の新大阪０は終点を示す例外値になるのではとは。

これを踏まえて、ウの操作１を行うと
A(A(1,2),2)は、東京の次の次の行き先行番号となり、
まずは、品川の次の行き先を示す行番号を、新横浜の次の行き先にコピーしたことになりますね。

そして、操作２で、東京の次の行き先を新横浜の行番号５と代入することで
品川と新横浜の　リスト順を入れ替えたことになります。
（品川の行き先の行番号３はどこらかも参照されませんね）

＃と、多分こんな、感じではないでしょうか？
＃Cプログラムとかで、構造体にnextポインタのメンバーを使ったリスト型の記録領域を
＃作ることがありますが、
＃これのリスト要素の入れ替えのテクニックに似ていると思います。

> 空欄と0とNULLは同意意義で考えてよろしいのでしょうか？

新横浜の空欄は単にどこからも参照されなかっただけのようです。
新大阪の0は、終点の意味っぽいです。
NULLは出題中にはありませんが、どこかの解法かにあるのでしょうか？

> また、一回目の操作と二回目の操作を入れ替えるとなぜデータが壊れてしまうのでしょうか？

これも、出題中にありませんが、なにか模擬プログラムを作られてのことなのでしょうか？
それのロジック追いかけてみないと、よくわかりません。

お礼

回答ありがとうございます

＞新横浜の空欄は単にどこからも参照されなかっただけのようです。
＞新大阪の0は、終点の意味っぽいです。
＞NULLは出題中にはありませんが、どこかの解法かにあるのでしょうか？

0またはNULLを用いることによってリストを終了するということは知っているのですが、人間目線で”空欄”は何も値が入っていないと考えたためNULLと一緒なのでは!?と真意がわからなかったのですが、ポインタが別のどこかに飛んでしまうと次のポインタに移る事ができないと考えればいいと言うことで納得しました。これを踏まえるとDBのデータの追加削除の関係に近いとなんですね。

回答No.1

nabe3desu

これって、RDB（リレーショナルデータベース）の問題で、「2列目の”値”を検索して、該当するレコード（列）の1列目を出力する」と考えればいいのでは？と考えます。しかも、検索時は必ず、”RDBの1行目から最終行まで検索する”仕様と考えます。

ご質問の通り、回答ウの操作で、二回目の操作が終わった時点で、「5,3,4,0,3」になっていますね。これを、上記の前提条件で検索すると、

0->新大阪
1->NULL
2->NULL
3->新横浜
4->名古屋
5->東京
6->NULL
※0->　とは、2列を0で検索した場合の結果（1列目の値）

ということではないかと考えます。見つかった時点で検索をやめてしまうと、”3”で検索した時の結果が”品川”になってしまうので、題意から外れます。

とすると、最初のご質問は、”空欄＝NULL＝行の終わり”であり、”0”とは異なることになります。RDBの検索終了条件は、NULLが見つかった時点となります。
また、ウの操作を二回目の後に一回目を実施すると、「5,3,4,0,NULL（空欄）」となりますね。データは壊れないと思います。

補足

RDBで考えると、5行2列目に3を入力した時点で2列目の検索において一意に求めることができず、これを考慮すると単方向リストで考えるべきでは？ということ、RDBの正規において順に検索するとなるとRDBのメリットが薄いと思うのですが...