基本情報技術者(科目A)過去問集 - データ構造

葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。

配列と比較した場合の連結リストの特徴に関する記述として，適切なものはどれか。

十分な大きさの配列Aと初期値が0の変数pに対して，関数 f(x) と g() が次のとおり定義されている。配列Aと変数pは，関数 f(x) と g() だけでアクセスが可能である。これらの関数が操作するデータ構造はどれか。

function f(x) {
　p = p+1;
　A[p] = x;
　return None;
}
function g() {
　x=A[p];
　p = p-1;
　return x;
}

A，B，C，Dの順に到着するデータに対して，一つのスタックだけを用いて出力可能なデータ列はどれか。

スタック操作の特徴を表す用語はどれか。

空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合，変数xに代入されるデータはどれか。ここで，手続で引用している関数は，次のとおりとする。

〔関数の定義〕
　push(y)：データyをスタックに積む。
　pop()：データをスタックから取り出して，その値を返す。
　enq(y)：データyをキューに挿入する。
　deq()：データをキューから取り出して，その値を返す。

〔手続〕
　push(a)
　push(b)
　eng(pop())
　enq(c)
　push(d)
　push(deq())
　x ← pop()

双方向のポインタをもつリスト構造のデータを表に示す。この表において新たな社員Gを社員Aと社員Kの間に追加する。追加後の表のポインタ a～f の中で追加前と比べて値が変わるポインタだけを全て列記したものはどれか。

表

アドレス	社員名	次ポインタ	前ポインタ
100	社員A	300	0
200	社員T	0	300
300	社員K	200	100

追加後の表

アドレス	社員名	次ポインタ	前ポインタ
100	社員A	a	b
200	社員T	c	d
300	社員K	e	f
400	社員G	x	y

2分木を入力するためのテキスト表現を，次のように規定した。図のように節に番号をつけたとき，テキスト表現として適切なものはどれか。

〔テキスト表現〕
（1）（左部分木の節番号又はテキスト表現，節番号，右部分木の節番号又はテキスト表現）と表す。
（2）部分木が空のときはxを書く。

ノード1～5をもつグラフを隣接行列で表したもののうち，木となるものはどれか。ここで，隣接行列のi行j列目の成分は，ノードiとノードjを結ぶエッジがある場合は1，ない場合は0とする。

10進法で5桁の数 a₁a₂a₃a₄a₅ を，ハッシュ法を用いて配列に格納したい。ハッシュ関数を mod（a₁+a₂+a₃+a₄+a₅，13） とし，求めたハッシュ値に対応する位置の配列要素に格納する場合，54321 は配列のどの位置に入るか。ここで，mod（x，13） は，xを13で割った余りとする。

リストを二つの1次元配列で実現する。配列要素 box[i] と next[i] の対がリストの一つの要素に対応し，box[i] に要素の値が入り，next[i] に次の要素の番号が入る。配列が図の状態の場合，リストの3番目と4番目との間に値がHである要素を挿入したときの next[8] の値はどれか。ここで，next[0] がリストの先頭（1番目）の要素を指し，next[i] の値が0である要素はリストの最後を示し，next[i] の値が空白である要素はリストに連結されていない。

2分探索木になっている2分木はどれか。

三つのスタックA，B，Cのいずれの初期状態も [1，2，3] であるとき，再帰的に定義された関数 f() を呼び出して終了した後のBの状態はどれか。ここで，スタックが [a₁，a₂，…，a_n-1] の状態のときに a_n をpushした後のスタックの状態は [a₁，a₂，…，a_n-1，a_n] で表す。

f(){
　Aが空ならば{
　　何もしない。
　}
　そうでない場合{
　　Aからpopした値をCにpushする。
　　f() を呼び出す。
　　Cからpopした値をBにpushする。
　}
}

次の規則に従って配列の要素 A[0]，A[1]，…，A[9] に正の整数kを格納する。kとして 16，43，73，24，85 を順に格納したとき，85が格納される場所はどこか。ここで，x mod yは，xをyで割った剰余を返す。また，配列の要素は全て0に初期化されている。

〔規則〕
（1）A[k mod 10] = 0 ならば，k を A[k mod 10] に格納する。
（2）（1）で格納できないとき，A[(k+1) mod 10] = 0 ならば，k を A[(k+1) mod 10] に格納する。
（3）（2）で格納できないとき，A[(k+4) mod 10] = 0 ならば，k を A[(k+4) mod 10] に格納する。

キューに関する記述として，最も適切なものはどれか。

加減乗除を組み合わせた計算式の処理において，スタックを利用するのが適している処理はどれか。

2分探索木として適切なものはどれか。ここで，数字1～9は，各ノード（節）の値を表す。

待ち行列に対する操作を，次のとおり定義する。
　ENQ n：待ち行列にデータnを挿入する。
　DEQ　：待ち行列からデータを取り出す。
空の待ち行列に対し，ENQ 1，ENQ 2，ENQ 3，DEQ，ENQ 4，ENQ 5，DEQ，ENQ 6，DEQ，DEQの操作を行った。次にDEQ操作を行ったとき，取り出されるデータはどれか。

PUSH命令でスタックにデータを入れ，POP命令でスタックからデータを取り出す。動作中のプログラムにおいて，ある状態から次の順で10個の命令を実行したとき，スタックの中のデータは図のようになった。1番目のPUSH命令でスタックに入れたデータはどれか。

16進数で表される9個のデータ1A，35，3B，54，8E，A1，AF，B2，B3を順にハッシュ表に入れる。ハッシュ値をハッシュ関数 f(データ) = mod(データ，8) で求めたとき，最初に衝突が起こるのはどのデータか。ここで，mod(a，b) はaをbで割った余りを表す。

A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。

データ構造の一つであるリストは，配列を用いて実現する場合と，ポインタを用いて実現する場合とがある。配列を用いて実現する場合の特徴はどれか。ここで，配列を用いたリストは，配列に要素を連続して格納することによって構成し，ポインタを用いたリストは，要素から次の要素へポインタで連結することによって構成するものとする。

プログラムの実行に関する次の記述の下線部 a～d のうち，いずれかに誤りがある。誤りの箇所と正しい字旬の適切な組合せはどれか。

　自分自身を呼び出すことができるプログラムは，_a再帰的であるという。このようなプログラムを実行するときは，_bスタックに局所変数，_c仮引数及び戻り番地を格納して呼び出し，復帰するときは_dFIFO（First In First Out）方式で格納したデータを取り出して復元する必要がある。

	誤りの箇所	正しい字句
ア	a	再入可能
イ	b	待ち行列
ウ	c	実引数
エ	d	LIFO（Last In First Out）

次の二つのスタック操作を定義する。
　PUSH n：スタックにデータ（整数値n）をプッシュする。
　POP：スタックからデータをポップする。
空のスタックに対して，次の順序でスタック操作を行った結果はどれか。
　PUSH 1 → PUSH 5 → POP → PUSH 7 → PUSH 6 → PUSH 4 → POP → POP → PUSH 3

次の2分探索木から要素12を削除したとき，その位置に別の要素を移動するだけで2分探索木を再構成するには，削除された要素の位置にどの要素を移動すればよいか。

プログラムの実行時に利用される記憶領域にスタック領域とヒープ領域がある。それらの領域に関する記述のうち，適切なものはどれか。

FIFO（First-In First-Out）の処理に適したデータ構造はどれか。

親の節の値が子の節の値より小さいヒープがある。このヒープへの挿入は，要素を最後部に追加し，その要素が親よりも小さい間，親と子を交換することを繰り返せばよい。次のヒープの＊の位置に要素7を追加したとき，Aの位置に来る要素はどれか。

10個の節（ノード）から成る次の2分木の各節に，1から10までの値を一意に対応するように割り振ったとき，節a，bの値の組合せはどれになるか。ここで，各節に割り振る値は，左の子及びその子孫に割り振る値よりも大きく，右の子及びその子孫に割り振る値よりも小さくするものとする。

2次元の整数型配列aの各要素 a（i，j）の値は，2i+j である。このとき，a（a（1，1）×2，a（2，2）+1）の値は幾つか。

ポインタを用いた線形リストの特徴のうち，適切なものはどれか。

次の2分探索木に12を追加したとき，追加された節12の位置を正しく表している図はどれか。

節点1，2，…，nをもつ木を表現するために，大きさnの整数型配列 A[1]，A[2]，…，A[n] を用意して，節点iの親の番号を A[i] に格納する。節点kが根の場合は A[k]=0 とする。表に示す配列が表す木の葉の数は，幾つか。

i	1	2	3	4	5	6	7	8
A[i]	0	1	1	3	3	5	5	5

データ構造の一つである木構造の特徴はどれか。

リストは，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。

四つのデータA，B，C，Dがこの順に入っているキューと空のスタックがある。手続pop_enq，deq_pushを使ってキューの中のデータをD，C，B，Aの順に並べ替えるとき，deq_pushの実行回数は最小で何回か。ここで，pop_enqはスタックから取り出したデータをキューに入れる操作であり，deq_pushはキューから取り出したデータをスタックに入れる操作である。

多数のデータが単方向リスト構造で格納されている。このリスト構造には，先頭ポインタとは別に，末尾のデータを指し示す末尾ポインタがある。次の操作のうち，ポインタを参照する回数が最も多いものはどれか。

スタック1，2があり，図の状態になっている。関数fはスタック1からポップしたデータをそのままスタック2にプッシュする。関数gはスタック2からポップしたデータを出力する。b，c，d，aの順番に出力するためには，関数をどの順で実行すればよいか。

データ構造に関する記述のうち，適切なものはどれか。

空の2分探索木に，8，12，5，3，10，7，6の順にデータを与えたときにできる2分探索木はどれか。

すべての葉が同じ深さをもち，葉以外のすべての節点が二つの子をもつ2分木に関して，節点数と深さの関係を表す式はどれか。ここで，nは節点数，kは根から葉までの深さを表す。例に示す2分木の深さkは2である。

B木に関する記述として，適切なものはどれか。

データ構造の特徴のうち，適切なものはどれか。

関数や手続を呼び出す際に，戻り番地や処理途中のデータを一時的に保存するのに適したデータ構造はどれか。