コンピュータ科学基礎（1-7から）１．下記のアルゴリズムについての記述の（）内を埋めよ．良いアルゴリズムを構築するためには以下の条件に合致させると良い．（①信頼性）が高い：正しい結果が得られる，精度の高い結果を得られる．（②一般性）がある：あらゆる状況に対応する．（③拡張性）がある：修正が容易である．（④効率）がよい：処理が早い，無駄な資源を使わない．（⑤理解）し易い：誰にでもわかりやすい，保守がし易い．２．下記の流れ図についての記述の（）内を埋め，例題に答えよ．アルゴリズムを，（①日本工業規格（JIS））によって定められた記号を用いて視覚的に理解しやすく表記する方法が流れ図（フローチャート）である．記号意味記号意味入出力：データの入出力を行う機能を表す判断：ある条件に応じた次の処理の方向を判断する書類：書類を出力する機能を表す表示：表示出力する機能を表す処理：あらゆる処理を表す線：処理の流れを表すループ端：ループの開始と終了の位置を表し，ループ名と終了の条件を記述する結合子：制御の流れにおける入り口や出口を表す端子：処理の開始，終了，中断，再開などを表す与えられた手続きを連続して直線的に処理する（②直線型），処理に伴う判定の結果によって，複数存在する処理の中から実行する処理を選択する（③分岐型）がある．その中でも，一般に条件を満たすか否かという真偽判定を行うものを（④二分岐型）， 1つの判定で複数の異なる処理を選択する（⑤多分岐型）がある．また，ある条件が満たされている間，あるいは満たされるまで，一定の処理を繰り返し実行する（⑥反復型）がある．その中でも処理を行う前に処理を継続するか否かを判定する（⑦事前判定型（DO WHILE型））と，処理を実行した後に繰り返し処理を実行するか否かを判定する（⑧事後判定型（REPEAT UNTIL型））がある．例題1 要素番号が0からはじまる配列TANGOがある．ｎ個の単語がTANGO（1）からTANGO（ｎ）に入っている．下図は，ｎ番目の単語をTANGO（1）に入れるために， TANGO（1）からTANGO（ｎ－1）の単語を順に1つずつ後ろにずらして単語表を構成する流れ図である．に入る処理として正しいものはどれか．開始 TANGO (n)→TANGO (0) ループ i ： n-1 ,-1, 0 ループ終了最初のTANGO（ｎ）→TANGO（0）の処理で， TANGO（ｎ）をTANGO（0）へ待避している． TANGO（1）からTANGO（ｎ－1）の単語を順に1ずつ後ろにずらすには，ループ内の処理でTANGO（ｎ－１）→TANGO（ｎ）， TANGO（ｎ－2）→TANGO（ｎ－1），･･････，TANGO（0）→TANGO（1）と順に移動させればよい． iの初期値がｎ－1で， 0になるまで1つずつ減少させていくので，内の処理はTANGO（i）→TANGO（i＋1）となる．〔答〕ア３．下記のリストについての記述の（）内を埋めよ．リストとは，データが（①直線的）に並んでいる状態のデータ構造を指し，以下のようなものがある．（②線形リスト）：データが順番に並んでいる構造で（③配列）とも呼ばれる．（④連結リスト）：リストに含まれる（⑤ポインタ）と呼ばれる情報で，個々のデータの関連付けを行うデータ構造である．単リストポインタデータポインタデータポインタデータ次のデータがない双リスト連結リストには下図のような３種類の形状がある．・・ 10 ・ 10 ・／ 10 ・ 20 ・ 20 ・・ 20 ・ 30 ・ 30 ・・ 30 ・ 40 ・ 40 ／片方向リスト（　）・ 40 ・双方向リスト（　）環状リスト（　）リストのデータに対する操作は以下のようなものがある．（⑥探索）：線形リストの場合，探索データが現われるまで先頭データから順に調べられる．結合リストの場合，最初の要素から順次ポインタで示された要素を順番に探索する．（⑦更新）：更新すべきデータを探索操作によって探し出し，該当データを読み出した後，新たなデータを書き込む．（⑧削除）：線形リストの場合，削除の方法は物理的にデータを消し去り，空いたところを次のデータから順に埋めていく方法と，「削除された」という情報を付記しておき読み出すときその配列は無いものとして扱う論理的方法の2つがある．連結リストの場合，削除する配列を連結から切り離し，読み飛ばす方法が取られる．（⑨挿入）：線形リストの場合，配列のサイズを挿入すべきデータ分だけ大きくし，挿入する位置を空けて挿入データを記録する．連結リストの場合は，削除操作と同様にポインタを入れ替える．４．下記のスタックと待ち行列についての記述の（）内を埋めよ．スタックとは，最初に取り出される（ポップ）データが最後に格納した（プッシュ）データであるデータ構造である．スタックはコンピュータの中でサブルーチンなどが呼び出されたときの（①戻りアドレス）を記録するときに使われる．配列を用いる際，データが格納されている位置を表す添字を（②スタックポインタ）と呼び，全ての添字はプッシュの際＋1，ポップの際－1する． PUSH POP データ３データ２データ１後入れ先出し待ち行列とは，最初に列に加わった（エンキュー）データが最初に処理される（デキュー）データ構造である．１ポインタ１２３先入れ先出しポインタ２ (先頭と末尾のデータを指す二つのポインタが必要) ５．下記の２分木についての記述の（）内を埋めよ．要素どうしの階層構造を表現したデータ構造を，（①木）という．木構造において○は節（②ノード）と呼び，最上位の節を（③“根”又は“ルート”），最下位の節を（④“葉”）又は“リーフ”）という．各節の上下関係（上が親，下が子という）を結んだ線を枝（⑤ブランチ）と呼ぶ． 2分木の節の部分に探索する要素を与えて探索するものに（⑥2分探索木）がある．下図のように2分木は，左部分木と右部分木の中間に位置する節には，両者の間に位置する要素が入る．これを利用し探索データと節のデータを比較することで左部分木か右部分木を絞り込むことができる．完全2分木は最も比較回数が少ないため効率がよい． 6 3 1 1 0 4 8 7 1 2 ６．下記のハッシュ法についての記述の（）内を埋め，例題に答えよ．ハッシュ法とは，データのキーの値から，データの格納場所を計算で求めて探索する方法である．この計算を（①ハッシュ関数）といい，これにより得られる値を（②ハッシュ値）という．したがってデータの並び順に関係なく探索ができる．データが表に格納されているとすると，キー値からハッシュ関数でそのデータが格納されている場所を添字値に変換して，その要素を求めるようにする．データの格納場所を即求めることができるので，速度が速い探索方法である．異なるキー値を変換しても，ハッシュ関数によって同じ値になることがある．これを（③衝突）という．衝突が起きたとき，既に格納されているデータを（④ホーム），これから格納しようとするデータを（⑤シノニム）という．衝突を回避する方法として，主に衝突が起きたデータをリストとして格納し，これをつなぐ（⑥チェーン法）と，全てのデータをハッシュ表に格納する（⑦オープンアドレス法）がある．例題2 次のハッシュ法探索に関する記述のうち，誤っているものはどれか．ア通常は計算によってデータの格納場所を求める．イ探索対象となるデータは，整列されていなければならない．ウ格納場所を計算する関数を，ハッシュ関数という．エハッシュ関数で計算したハッシュ値が，同じ値になることがある．〔答〕イ７．下記の処理についての記述の（）内を埋めよ．キー項目の大小関係により，記憶装置内で並べ替えを行うことを（①“内部整列”又は“内部ソート”）といい，複数のファイル内で並べ替えを（②“外部整列”又は“外部ソート”）という．・隣接交換法とは，全ての要素が整列されるまで，隣り合う２つの項目を比較して交換する方法．データ数がｎ個のとき，比較回数は（③ n(n-1)/2 ）回である．・選択法とは，配列の中から（④最小のもの）を選択して先頭にし，残りの配列から（ ④ ）を選択し，これを2番目にする．この動作を最後まで繰り返す方法．データ数がｎ個の時，比較回数は（⑤ n(n-1)/2 ）回である．隣接交換法元データ配列X [1] [2] [3] [4] 40 30 10 20 40 30 10 20 30 40 10 20 30 10 40 20 結果 30 10 20 40 10 30 20 40 10 20 30 40 交換しない 10 20 30 40 選択法元データ配列X [1] [2] [3] [4] 40 30 10 20 40 30 10 20 30 40 10 20 10 40 30 20 交換しない結果 10 40 30 20 10 30 40 20 10 20 40 30 10 20 30 40 探索とは,（⑥データ）の中からあたえられた（⑦条件）に合致するデータを探しだす処理である．（⑧線形探索）法や（⑨2分探索）法などがある．（ ⑧ ）法は，（⑩探索キー）が出現するまで一つ一つ調べる方法．要素数nのデータの中から検索データを見つける最大比較回数は（⑪n）回になり，平均比較回数は，（⑫n/2）となる．検索データの最後に配置したキーと同様のデータを（⑬番兵）という．（ ⑨ ）法は，まず配列の（⑭中心位置）の値を照合し，検索する要素が上半分にあたるか，下半分にあるかを確かめる．例えば，上半分にあるとしたら，次の上半分の( ⑭ )と照合し，以下同様に配列を二等分し照合することを繰り返しして探し出す方法．データ数がｎ個のとき，最大比較回数は（⑮[log2n]+1）回，平均比較回数は（⑯[log2n]）回である．線形探索法元データ配列X [1] [2] [3] [4] 40 30 10 20 1 2 3 目的データ 10 (比較) 目的データと配列の要素を先頭から順番に比較していく方法．配列の要素は，事前に整列する必要はない．平均比較回数は，配列の要素数に比例する．データ数が少ないと有効．２分探索法３：目的データ元データ [1] [2] [3] [4] [5] 配列X １３５６８１０１１１３比較３ ① ３ ② ③ ④ ３３ [6] [7] [8] 目的データが含まれる範囲配列を２等分しながら，目的データが含まれる範囲を絞って探索する方法．配列の要素は事前に整列済みでなければならない．データ数が多い場合，有効．小テスト解説問題１ PUSH1 PUSH5 5 １１ 5 POP PUSH7 5 7 １１ PUSH6 PUSH4 4 6 6 7 7 １１ 4 POP 6 POP 4 6 6 7 7 １１ PUSH3 3 7 １〔答〕ウ問題２テキストｐ.60 〔答〕イ問題３テキストｐ.63~65 〔答〕ウ問題４テキストｐ.71~72 〔答〕ア問題５テキストｐ.66 〔答〕ウ