応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。
カテゴリ:

2.プログラミング > 2.1 スタックとキュー

問1 リストに関する次の記述を読んで,設問1~3に答えよ。

リストの構造は図1のとおりとする。
17-FE問1-1
(1)ROOTは,リストの先頭を指す。
(2)リストの要素は連続する2語からなる。第1語には値が,第2語には次の要素へのポインタが格納されている。
(3)リストの各要素は値の昇順に連結されていて,値はすべて異なる。最後の要素の第2語にはポインタとして0000が格納されている。
(4)図1の構造をもつリストが,図2のとおりに主記憶の00FF番地から0117番地までに格納されている。00FF番地はROOTである。
(5)1語は16ビットからなり,語単位で番地が付いている。
17-FE問1-2


設問1 010C番地の内容として正しい答えを,解答群の中から選べ。

解答群
ア 0099  イ 00A1  ウ 00A3  エ 00A4  オ 00A5
正解は、イです。

設問2 次の記述中の[   ]に入れる正しい答えを,解答群の中から選べ。

 0110番地及び0111番地からなる要素をリストから削除するには,[ a ]番地の内容を[ b ]に変えればよい。

解答群
ア 0101  イ 0102  ウ 0103  エ 0104  オ 0105
カ 0113  キ 0114  ク 0115  ケ 0116  コ 0117
正解は、
a コ  
b イ です。

設問3 次の記述中の[   ]に入れる正しい答えを,解答群の中から選べ。

 0118番地から011D番地に格納されている3要素からなるサブリストと,設問2で要素を削除する前のリストを併合するには,[ c ]番地の内容を011Aに,[ d ]番地の内容を0102に,[ e ]番地の内容を011Cに,[ f ]番地の内容を0108にそれぞれ変えればよい。

解答群
ア 0109  イ 010B  ウ 010D  エ 010F  オ 0111
力 0113  キ 0115  ク 0117  ケ 0119  コ 011B
正解は、
c オ
d コ
e キ
f ケ です。

データ構造とは、データをどのように持つかという方法のことです。
配列やリスト、スタック、キュー、木構造などがあります。
応用情報技術者試験を勉強する成子 

なんでそんなに種類があるのですか?
それぞれ特徴があるからです。データがもし書き込んだらそれでおしまいであれば、データ構造をあまり気にする必要はありません。しかし、データというのは追加したり変更したり削除したりします。
また、データベースなどの検索が重要な場合に、高速に検索できる仕組みが求められます。
そういう観点で、データ構造は重要なのです。

基本情報技術者試験の過去問(H23春FE午後問11)の「出題趣旨」でも「プログラムの作成において,データ構造は実行時の特性に大きな影響を及ぼすので,適切なデータ構造を選択することは重要である。」とあります。

過去問を基に整理します。
スタック
「格納した順序とは逆の順序でデータを取り出すことができる構造である(H16春FE午前問43)」

キュー
「格納した順序でデータを取り出すことができる構造である(H16春FE午前問43)。」

リスト
「データ部と一つのポインタ部で構成されるセルをたどることによって,データを取り出すことができる構造である(H16春FE午前問43)」

木構造
「階層の上位から下位に節点をたどることによって,データを取り出すことができる構造である(H16春FE午前問43)」。

H17秋FE午前
問13 データ構造に関する記述のうち,適切なものはどれか。
ア 2分木は,データ間の関係を階層的に表現する木構造の一種であり,すべての節が二つの子をもつデータ構造である。
イ スタックは,最初に格納したデータを最初に取り出す先入れ先出しのデータ構造である。
ウ 線形リストは,データ部と次のデータの格納先を指すポインタ部から構成されるデータ構造である。
エ 配列は,ポインタの付替えだけでデータの挿入・削除ができるデータ構造である。

H19春AD午前問34
問34 データ構造の特徴のうち,適切なものはどれか。
ア 配列は,添字によってデータを任意の順序で読み出すことができる。
イ 配列を用いることによって,データ構造とアルゴリズムを独立させることができる。
ウ リストは,添字によってデータの検索や更新ができる。
エ リストは,データの挿入や削除のときに既存のデータを移動する必要がある。

H18SW春午前
問9 データ構造に関する記述のうち,B木の説明として適切なものはどれか。
ア ある特定のアルゴリズムに従って,レコードのキー値から物理的な格納アドレスを求めてレコードを格納する。
イ 索引部の各ノートのキー値を中心にして,小さい側のレコード数と大きい側のレコード数の比率が,ある範囲内に収まるように動的に再配置しながら格納する。
ウ レコードの物理的配置とは独立に,論理的にレコードをつなぐポインタによって,レコードを関係づけて格納する。
エ レコードをキー値の昇順にしてトラックなどのアクセス単位(ページ)ごとに格納し,各ページ内の最大キー値とそのページの番地をもつ索引を作る。

スタックは,最後の格納したデータを最初に取り出す後入れ先出し(LIFO:Last In First Out)のデータ構造です。
★あとでイメージ図を入れる

スタックにデータを挿入することをpush、スタックからデータを取り出すことをpopといいます。

応用情報技術者試験を勉強する成子

FIFOとかpushとかpopとか、複雑なことをしますね。
メリットはあるのですか?



プログラムを書く上で、便利なときがあります。
過去問(H25春AP午後問2)を例に考えます。
http://sm.seeeko.com/archives/65909425.html

これは、一般的な表記法の数式を逆ポーランド表記法に変換するプログラムのアルゴリズムです。
たとえば、1+2×3を,逆ポーランド表記法では123×+と表記します。
このとき、人間では柔軟に考えることができますが、プログラムには「柔軟に」という命令が出せません。
一つ一つの動作をロジカルに命令するしかないのです。
ここでは、変換前の配列(1+2×3)を変換後の配列(123×+)に入れる際に、一時的な領域としてスタックを使っています。
詳細な動きはこの問題文に解説されていますが、簡略化すると
(1)変換前配列から1つずつ読み取る
(3)数字ならスタックにPush
(2)四則演算子ならスタックのデータをPopして変換後配列に追加、四則演算子をスタックにPush
(4)変換前配列が空になったら全てをPopして変換後配列に追加
※(3)と(2)は、流れに合わせて逆にしました。



過去問(H21春FE午前問5 )
問5 関数や手続を呼び出す際に,戻り番地や処理途中のデータを一時的に保存するのに適したデータ構造はどれか。
ア 2分探索木
イ キュー
ウ スタック
エ 双方向連結リスト
正解は、ウ

H18春FE午前
問12 空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合,変数眉こ代入されるデータはどれか。ここで,
データyをスタックに挿入することをpush(y),
スタックからデータを取り出すことをpop(),
データyをキューに挿入することをenq(y),
キューからデータを取り出すことをdeq() ,
とそれぞれ表す。

push(a)
push(b)
enq(pop())
enq(c)
push(d)
push(deq())
x←pop()

ア a  イ b  ウ c  エ d
正解は、

このページのトップヘ