平成30年度秋季解答

問題6

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

ア	枝の個数がn ならば、葉を含む節点の個数もn である。
イ	木の深さがn ならば、葉の個数は2n -1である。
ウ	節点の個数がn ならば、深さはlog2n である。
エ	葉の個数がn ならば、葉以外の節点の個数はn -1である。

解答：エ

＜解説＞

完全二分木（葉以外の節点はすべて二つの子をもち、根から葉までの深さがすべて等しい木）は、次の図のようになる。

ア	×	枝の個数がnならば、葉を含む節点の個数はn+1である。
イ	×	木の深さが n ならば，葉の個数は 2n である。
ウ	×	節点の個数が n ならば，深さは (log2(n+1))-1 である。
エ	○	葉の個数がnならば、葉以外の節点の個数はn-1である。

問題へ

問題7

2次元配列A [i , j ](i 、j はいずれも0～99の値をとる)のi >j である要素A [i , j ]は全部で幾つか。

ア	4,851
イ	4,950
ウ	4,999
エ	5,050

解答：イ

＜解説＞

2次元配列A [i.j]において.i=0のときは i>jを満たすjは存在しない。

·i=1のとき:i>jを満たすjは0の1個

·i=2のとき:i>jを満たすjは0と1の2個

　　　：

　　　：

·i=98のとき:i>jを満たすjは0~97の98個

·i=99のとき:i>jを満たすjは0~98の99個

よって.1+2+3+ …… +98+99=100×99÷2=4,950になる。

したがって、イが正解である。

問題へ

問題8

探索表の構成法を例とともにa～cに示す。 最も適した探索手法の組合せはどれか。 ここで、探索表のコードの空欄は表の空きを示す。

解答：ア

＜解説＞

[a コード順に格納した探索表：2分探索]

2分探索は、予めソートされたデータ列を二つに分けて、そのどちらに検索対象が含まれているか判断するという手順を再帰的に繰り返していく検索方法。
⇒aは、 コード順に格納されているので、2分探索法が適している。

[b コードの使用頻度順に格納した探索表：線形探索]

線形探索は、対象データを検索範囲のデータと先頭から順に1つずつ比較し、一致するものを検索する方法。
⇒bは、使用頻度順にならんでいるので先頭から順番に検索すると早く見つけることができるので、線形探索が適している。

[c コードから一意に決まる場所に格納した探索表：ハッシュ探索]

ハッシュ探索は、キーの値を基に格納先（記録媒体上）のアドレスを算出し、そのアドレス位置にあるデータを検索する方法。
⇒cは、コードから格納場所を探索するのでハッシュ探索が適している。

したがって、アが正解である。

問題へ

問題9

メモリの誤り制御方式で、2ビットの誤り検出機能と、1ビットの誤り訂正機能を持たせるのに用いられるものはどれか。

ア	奇数パリティ
イ	水平パリティ
ウ	チェックサム
エ	ハミング符号

解答：エ

＜解説＞

ア	×	奇数パリティは、バイト単位のデータにパリティビットを付加し、データ+パリティビットの1の個数を奇数にすることで誤り検出をする手法である。1 ビットの誤り検出しかできない。
イ	×	水平パリティは、データに対して水平方向に付加されたパリティビットのことである。1ビットの誤り検出しかできない。
ウ	×	チェックサムは、データの合計などを計算し、その結果をデータに付加することでエラーを検出する方式である。誤り検出できるビット数は分割するサイズによって異なる。誤り訂正はできない。
エ	○	ハミング符号はメモリの誤り制御方式である。ハミング符号方式では2ビットの誤り検出機能と、1ビットの誤り訂正をおこなうことができる。

問題へ

問題10

相変化メモリの説明として、適切なものはどれか。

ア	一度だけ書き込みが可能な不揮発性メモリ
イ	結晶状態と非結晶状態のちがいを利用して情報を記憶する不揮発性メモリ
ウ	フリップフロップ経路で構成された揮発性メモリ
エ	リフレッシュ動作が必要な揮発性メモリ

解答：イ

＜解説＞

相変化とは,固体、液体,気体のそれぞれを相としてその相が変わることをいう。

相変化メモリは,カルコゲナイドを材料として電流を流して発熱させ,結晶状態と非晶質状態の間の抵抗の変化を使って記憶させる不撣発性メモ リですある

ア	×	PROM(Programmable ROM)の説明である。
イ	〇	相変化メモリの説明である。
ウ	×	SRAM(Static RAM)の説明である。
エ	×	DRAM(Dynamic RAM)の説明である。

問題へ