会社の従業員の名前と電話番号を保存する必要がある電子電話帳を開発するタスクがあります。利用可能なデータ構造は、リンク リストと二分探索ツリー (BST) であり、プロジェクトに最適なサポートされているデータ構造を選択する必要があります。さらに、データ構造を選択する際には、挿入、削除、および検索操作も考慮する必要があります。これは、会社が新しい従業員を雇ったり、従業員の電話番号を検索したり、古い従業員が退職したりする可能性があるためです。上記のシナリオにより適していると思われるデータ構造を検討してください。また、他のデータ構造よりもこのデータ構造を好む理由についても説明してください。
質問する
251 次
1 に答える
1
BSTの方がいいでしょう。なぜなら...
電話帳で最も頻繁に使用される機能である検索は、リンクされたリストよりも BST の方が高速です。
平均的なケースでは、挿入には O(log n) の時間がかかります。リンクされたリストの場合、新しいノードが挿入される場合、正しい場所を見つけるのに O(n) 時間がかかり、BST よりも遅くなります。
削除：最悪の場合、木の高さに比例して時間がかかります。ただし、連結リストの場合は一定のオーダー時間がかかります。(これは、リンクされたリストが優れている唯一のケースです。)
したがって、平均的にリンクされたリストの方が優れています。
PS : 電話帳をソートして保存することを想定しています。
于 2012-06-26T11:46:13.550 に答える