応用情報技術者　② アルゴリズムとプログラミング

データ構造とアルゴリズム、プログラミング言語の基礎を扱う分野です。配列・リスト・スタック・キュー・木構造といったデータ構造の特徴、探索・整列アルゴリズムの計算量、再帰やポインタの考え方が頻出です。計算量のオーダー評価や、アルゴリズムの動作をトレースする問題が多いのが特徴です。単に名称を覚えるのではなく、各データ構造がどんな処理に向くか、なぜその計算量になるかを図で理解しましょう。実装経験があると強い分野で、午後試験にもつながる重要テーマです。出題数56問。

この分野の問題56問を、選択肢・正解・解説つきで掲載しています。まず自分で解答を考えてから「正解と解説を見る」を開いて答え合わせをしてください。

クイズモードで挑戦 →

第63問リストの実現方法のうち、配列を用いる場合の特徴として、適切なものはどれか。

Aあらかじめ最大データ数に対応した領域を確保する必要がある
B要素の挿入や削除が容易である
C使用するデータ数に応じて動的に領域を確保できる
D要素への参照にポインタのたどりを必要とする

正解と解説を見る

正解：A．あらかじめ最大データ数に対応した領域を確保する必要がある

配列は要素位置が固定されており、最大データ数を見越した領域確保が必要となる。

応用情報技術者 ② アルゴリズムとプログラミング

第63問リストの実現方法のうち、配列を用いる場合の特徴として、適切なものはどれか。

第64問リストの実現方法のうち、連結リストの特徴として、適切なものはどれか。

第65問Head（先頭ポインタ）とTail（末尾ポインタ）をもつ連結リストにおいて、リストの末尾への要素追加の処理量について、適切な説明はどれか。

第66問2分木を各ノードが子へのポインタをもつリスト構造で表現する場合、ノードが通常もたないものはどれか。

第67問スタックの動作方式を指す用語はどれか。

第68問キューの動作方式を指す用語はどれか。

第69問グラフ探索において、深さ優先探索と幅優先探索で使用されるデータ構造の組み合わせとして、適切なものはどれか。

第70問再帰的処理を含む関数呼出しの実現に用いられる制御スタックにおいて、関数ごとに積まれるデータのまとまりを何というか。

第71問完全2分木において、木の深さがHであるとき、葉の個数はいくつになるか。

第72問完全2分木において、木の深さがHであるとき、葉以外の節の個数はいくつになるか。

第73問2分木の走査法において、先行順（行きがけ順）の順序はどれか。

第74問2分木の走査法において、中間順（通りがけ順）の順序はどれか。

第75問2分木の走査法において、後行順（帰りがけ順）の順序はどれか。

第76問探索アルゴリズムのうち、探索データのキー値により、格納場所を直接計算する方法はどれか。

第77問ハッシュ法において、異なるキー値から同一のハッシュ値が求められることを何というか。

第78問線形探索法における平均比較回数を表す式はどれか（データ数をnとする）。

第79問2分探索法を用いるための前提条件として、適切なものはどれか。

第80問ハッシュ法におけるシノニム発生時の対応策として、オープンアドレス法の説明として適切なものはどれか。

第81問ハッシュ法におけるシノニム発生時の対応策として、チェイン法の説明として適切なものはどれか。

第82問バブルソート（隣接交換法）の計算量のオーダはどれか。

第83問単純挿入法の最良計算量のオーダはどれか。

第84問分割統治法の考え方に基づいた整列アルゴリズムはどれか。

第85問安定な整列アルゴリズムはどれか。

第86問どんなデータ列に対しても計算量がO(n log n)となる整列法はどれか。

第87問マージソートの特徴として、適切なものはどれか。

第88問再帰関数における定義のうち、自分自身を呼び出さないものはどれか。

第89問再入可能（リエントラント）プログラムの性質として、適切なものはどれか。

第90問再使用可能（リユーザブル）プログラムの性質として、適切なものはどれか。

第91問再配置可能（リロケータブル）プログラムを実現するために用いられるものはどれか。

第92問値呼出し（call by value）の特徴はどれか。

第93問参照呼出し（call by reference）の特徴はどれか。

第94問ガーベジコレクションの説明として、適切なものはどれか。

第95問手続型言語の特徴として、適切なものはどれか。

第96問関数型言語の特徴として、適切なものはどれか。

第97問論理型言語の推論処理において、失敗した際にそれまでの効果を元に戻し、異なるパターンで試行することを何というか。

第98問JSONの特徴として、適切なものはどれか。

第99問Javaサーブレットの説明として、適切なものはどれか。

第100問連結リストで、追加先の直前要素を指すポインタが与えられているとき、その直後に要素を追加する計算量のオーダはどれか。

第101問2分探索木の探索における最悪計算量のオーダはどれか。

第102問ハッシュ表を用いた探索において、チェイン法を採用した場合の探索計算量のオーダ（n個のデータをm個の表に格納）はどれか。

第103問バブルソートにおいて、データが既に正しい順に並んでいる場合の比較回数のオーダはどれか。

第104問クイックソートにおいて、最小値あるいは最大値を基準値とした場合の最悪計算量のオーダはどれか。

第105問再帰プログラムの特徴として、適切なものはどれか。

第106問スタック領域の説明として、適切なものはどれか。

第107問B木における節の構造について、適切なものはどれか。

第108問単純挿入法の平均的な計算量のオーダはどれか。

第109問オブジェクト指向言語の特徴として、適切なものはどれか。

第110問XMLにおいて、文書構造を定義するための記述（スキーマ言語）を何というか。

第111問線形リストを用いた探索において、特定の要素を探すための計算量はどれに比例するか。

第112問単純選択法の比較回数のオーダはどれか。

第113問再帰関数の階乗定義において、n=0のとき返す値はどれか。

第114問ヒープソートにおいて、データを高速に整列できる理由として適切なものはどれか。

第115問XML Stylesheet Language Transformations（XSLT）の説明として、適切なものはどれか。

第116問ハッシュ法において、シノニムが発生しなかった場合の探索時間はどうなるか。

第117問プログラム言語の分類において、再帰処理向きの言語はどれか。

第118問スタック領域とヒープ領域の違いとして、適切なものはどれか。

応用情報技術者　② アルゴリズムとプログラミング