第4回 演習問題 離散探索木
■ 共通
実行・測定環境
hardware: 貸与されたnotePC(3年生、任意のPC or WS、性能記載の必要がある)
OS: linux(時間的余裕があればwindowsXP)
測定時は、当該プログラム以外のプログラムはできるだけ削減する
作成済み4a 離散探索木(2進) 操作関数の作成 難易度: A
作成関数: 格納、探索、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
作成済み4b 離散探索木(26進) 操作関数の作成 難易度: A
作成関数: 格納、探索、削除、メイン関数
キー: 文字列
使用ファイル: wordE100KR.dat
4c 離散探索木(26進)と二分探索分法の比較(探索関数) 難易度: B
作成関数: 格納、探索、削除、メイン関数
キー: 文字列
使用ファイル: wordE100KS.dat、 U = 10000
上記ファイルを読み込み、 配列(文字列ポインター配列)に格納する(配列A: 探索値配列)。
(a) 配列(文字列ポインター配列)を生成し、配列Aから格納する(配列B: 探索値配列)。配列Aの全単語を配列Bに対して探索する(前探索)。この過程において、1u, 2u, ・・・, 10uで比較回数、処理時間を計測する。
(b) 配列Aから離散探索木を生成する。配列Aの全単語を配列Bに対して探索する(前探索) (a), (b)の計測結果を表、グラフで表わし、これらの数値を対比し、分析する。
作成済み4h 離散探索木(26進)と分離連鎖法の比較(探索関数) 難易度: B
キー: 文字列
使用ファイル: wordE100KR.dat
上記ファイルを読み込み、通常の配列に格納する。この配列から要素を読み込み、分離連鎖法および離散探索木(26進)を生成する。格納された要素と同一の要素集合すなわち、配列に格納された用語集合に対して、1万語毎に探索を行い、照合回数、および探索時間を測定する。
結果として、それぞれの手法について照合回数について20個のデータ(2×10)、同様に探索時間について20個のデータ(2×10)が得られる。これらのデータをExcelに格納し、表、グラフを作成し、分析せよ。
4i 離散探索木(26進)と外部ハッシュ法の比較(探索関数) 難易度: B
キー: 文字列
使用ファイル: wordE100KR.dat
上記ファイルを読み込み、通常の配列(文字ポインター配列)に格納する。この配列から要素を読み込み、外部ハッシュ法および離散探索木(26進)を生成する。格納された要素と同一の要素集合すなわち、配列に格納された用語集合に対して、1万語毎に探索を行い、照合回数、および探索時間を測定する。
結果として、それぞれの手法について照合回数について10個のデータ(1万×10)、同様に探索時間について10個のデータ(1万×10)が得られる。これらのデータをExcelに格納し、表、グラフを作成し、分析せよ。
4j 離散探索木(26進)とAVL木の比較(探索関数) 難易度: B
キー: 文字列
使用ファイル: wordE100KR.dat
上記ファイルを読み込み、通常の配列に格納する。この配列から要素を読み込み、AVL木および離散探索木(26進)を生成する。格納された要素と同一の要素集合すなわち、配列に格納された用語集合に対して、1万語毎に探索を行い、照合回数、および探索時間を測定する。
結果として、それぞれの手法について照合回数について10個のデータ(1万×10)、同様に探索時間について10個のデータ(1万×10)が得られる。これらのデータをExcelに格納し、表、グラフを作成し、分析せよ。
作成済み4k 離散探索木(2進)とAVL木の比較(探索関数) 難易度: B
キー: 文字列
使用ファイル: wordJ1MR.dat
上記ファイルを読み込み、通常の配列に格納する。この配列から要素を読み込み、AVL木および離散探索木(2進)を生成する。格納された要素と同一の要素集合すなわち、配列に格納された用語集合に対して、10万語毎に探索を行い、照合回数、および探索時間を測定する。
結果として、それぞれの手法について照合回数について10個のデータ(10万×10)、同様に探索時間について10個のデータ(10万×10)が得られる。これらのデータをExcelに格納し、表、グラフを作成し、分析せよ。