データ構造｜基本情報技術者試験
この分野には 36問あります。くり返し出ているものから並べています。
この分野でくり返し出ている用語はハッシュ（2問）です。問題が多い回は平成31年度 春期（2問）・平成30年度 春期（2問）・平成28年度 春期（2問）です。
この分野で出た問題
- 令和元年度 秋期 問88回出題A, C, K, S, T の順に文字が入力される。スタックを利用して，S, T, A, C, K という順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。
- 平成26年度 春期 問75回出題空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合，変数 x に代入されるデータはどれか。ここで，手続で引用している関数は，次のとおりとする。
- 平成24年度 秋期 問54回出題四つのデータ A，B，C，D がこの順に入っているキューと空のスタックがある。手続 pop_enq，deq_push を使ってキューの中のデータを D，C，B，A の順に並べ替えるとき，deq_push の実行回数は最小で何回か。ここで，pop_enq はスタックから取り出したデータをキューに入れる操作であり，deq_push はキューから取り出したデータをスタックに入れる操作である。
- 平成29年度 秋期 問5A，B，C，D の順に到着するデータに対して，一つのスタックだけを用いて出力可能なデータ列はどれか。
- 令和5年度 科目A（公開問題） 問2双方向のポインタをもつリスト構造のデータを表に示す。この表において新たな社員 G を社員 A と社員 K の間に追加する。追加後の表のポインタ a ～ f の中で追加前と比べて値が変わるポインタだけを全て列記したものはどれか。
2回出題：令和5年度 科目A（公開問題）・平成22年度 春期
- 平成30年度 秋期 問5待ち行列に対する操作を，次のとおり定義する。
- 平成28年度 春期 問510 個の節（ノード）から成る次の 2 分木の各節に，1 から 10 までの値を一意に対応するように割り振ったとき，節 a，b の値の組合せはどれになるか。ここで，各節に割り振る値は，左の子及びその子孫に割り振る値よりも大きく，右の子及びその子孫に割り振る値よりも小さくするものとする。
- 平成26年度 春期 問62 分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n) の定義は，次のとおりである。このプログラムを，図の 2 分木の根（最上位のノード）に適用したときの出力はどれか。
- 平成28年度 春期 問62 次元の整数型配列 a の各要素 a(i, j) の値は，2i ＋ j である。このとき，a(a(1, 1)×2, a(2, 2)+1) の値は幾つか。
- 平成31年度 春期 問52分探索木として適切なものはどれか。ここで，数字1〜9は，各ノード（節）の値を表す。
- 平成28年度 秋期 問62分探索木になっている2分木はどれか。
- 平成27年度 春期 問5キューに関する記述として，最も適切なものはどれか。
- 平成23年度 秋期 問5スタック1，2があり，図の状態になっている。関数 f はスタック1からポップしたデータをそのままスタック2にプッシュする。関数 g はスタック2からポップしたデータを出力する。b，c，d，a の順番に出力するためには，関数をどの順で実行すればよいか。
- 平成29年度 春期 問4データ構造の一つであるリストは，配列を用いて実現する場合と，ポインタを用いて実現する場合とがある。配列を用いて実現する場合の特徴はどれか。ここで，配列を用いたリストは，配列に要素を連続して格納することによって構成し，ポインタを用いたリストは，要素から次の要素へポインタで連結することによって構成するものとする。
- 平成27年度 秋期 問5ポインタを用いた線形リストの特徴のうち，適切なものはどれか。
- 平成25年度 秋期 問6リストは，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。
- 平成30年度 春期 問6リストを二つの1次元配列で実現する。配列要素 box[ i ] と next[ i ] の対がリストの一つの要素に対応し，box[ i ] に要素の値が入り，next[ i ] に次の要素の番号が入る。配列が図の状態の場合，リストの3番目と4番目との間に値が H である要素を挿入したときの next[ 8 ] の値はどれか。ここで，next[ 0 ] がリストの先頭（1番目）の要素を指し，next[ i ] の値が0である要素はリストの最後を示し，next[ i ] の値が空白である要素はリストに連結されていない。
- 平成31年度 春期 問6三つのスタック A，B，C のいずれの初期状態も [1, 2, 3] であるとき，再帰的に定義された関数 f( ) を呼び出して終了した後の B の状態はどれか。ここで，スタックが [a₁, a₂, …, aₙ₋₁] の状態のときに aₙ を push した後のスタックの状態は [a₁, a₂, …, aₙ₋₁, aₙ] で表す。
- 平成26年度 秋期 問5加減乗除を組み合わせた計算式の処理において，スタックを利用するのが適している処理はどれか。
- 平成24年度 春期 問6十分な大きさの配列 A と初期値が0の変数 p に対して，関数 f(x) と g() が次のとおり定義されている。配列 A と変数 p は，関数 f(x) と g() だけでアクセス可能である。これらの関数が操作するデータ構造はどれか。
- 令和7年度 科目A（公開問題） 問3図の木構造は 2 分探索木である。a～g の値の大小関係として，適切なものはどれか。ここで，a～g の値は重複しないものとする。
- 平成24年度 春期 問7多数のデータが単方向リスト構造で格納されている。このリスト構造には，先頭ポインタとは別に，末尾のデータを指し示す末尾ポインタがある。次の操作のうち，ポインタを参照する回数が最も多いものはどれか。
- 平成25年度 春期 問5次の 2 分探索木から要素 12 を削除したとき，その位置に別の要素を移動するだけで 2 分探索木を再構成するには，削除された要素の位置にどの要素を移動すればよいか。
- 令和8年度 科目B（公開問題） 問4科目B次のプログラム中の［a］と［b］に入れる正しい答えの組合せを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。
- 令和7年度 科目B（公開問題） 問3科目B次のプログラム中の［a］と［b］に入れる正しい答えの組合せを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。
- 令和6年度 科目B（公開問題） 問3科目B次のプログラム中の［ ］に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。
- 平成30年度 春期 問5次の二つのスタック操作を定義する。
- 令和5年度 科目B（公開問題） 問4科目B次の記述中の［ ］に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。
- 平成23年度 特別 問5空の2分探索木に，8，12，5，3，10，7，6 の順にデータを与えたときにできる2分探索木はどれか。
- 平成21年度 秋期 問5空のスタックに対して次の操作を行った場合，スタックに残っているデータはどれか。ここで，“push x”はスタックへデータ x を格納し，“pop”はスタックからデータを取り出す操作を表す。
- 平成22年度 秋期 問6節点 1，2，…，n をもつ木を表現するために，大きさ n の整数型配列 A[1]，A[2]，…，A[n] を用意して，節点 i の親の番号を A[i] に格納する。節点 k が根の場合は A[k]＝0 とする。表に示す配列が表す木の葉の数は，幾つか。
- 平成21年度 春期 問6配列と比較した場合の連結リストの特徴に関する記述として，適切なものはどれか。
- 平成21年度 春期 問5関数や手続を呼び出す際に，戻り番地や処理途中のデータを一時的に保存するのに適したデータ構造はどれか。
正解と解説は、答え合わせのあとに出ます。
年度から解く
この分野の問題は 28年度ぶんの試験から出ています。いちばん新しいのは令和8年度 科目B（公開問題）です。年度別に解くと、回ごとにまとめて解けます。