第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に格納し、表、グラフを作成し、分析せよ。