スキップリストに関する記述として，最も適切なものはどれか。
ア リストの要素を一定間隔でスキップしながら線形探索を行うことで，O(n/k)の探索時間を実現するデータ構造である
イ ハッシュ関数を用いてリストの要素を分散配置し，O(1)の探索時間を実現するデータ構造である
ウ リストの要素を二分木状に再配置することで，最悪O(log n)の探索時間を保証するデータ構造である
エ 整列済み連結リストに複数レベルのリンクを追加し，平均O(log n)の探索を実現する確率的データ構造である
正解: エ
要点: スキップリストは複数レベルのリンクをもつ確率的データ構造で，平均O(log n)で検索・挿入・削除ができる。
この問題に出てくる用語
同じ回の前後の問題
- 令和7年度範囲 練習問題3: 文字列の集合を格納し，入力された文字列のプレフィックス（接頭辞）に一致するすべての文字列を高速に検索
- 令和7年度範囲 練習問題5: 有向非巡回グラフ（DAG）の全てのノードを，どの辺(u, v)についてもuがvより先に並ぶように一列
テクノロジ系の他の問題
- 令和7年度範囲 練習問題5: 有向非巡回グラフ（DAG）の全てのノードを，どの辺(u, v)についてもuがvより先に並ぶように一列
- 令和7年度範囲 練習問題6: 有向グラフにおいて，互いに到達可能な頂点の最大集合を何というか。
- 令和7年度範囲 練習問題7: CPUのパイプラインにおいて、条件分岐命令の分岐先を、過去の分岐履歴などに基づいて分岐結果の確定前に
- 令和7年度範囲 練習問題8: 投機的実行（スペキュレイティブエグゼキューション）に関する記述として，最も適切なものはどれか。
- 令和7年度範囲 練習問題9: メモリマップドI/Oの説明として，最も適切なものはどれか。
アプリで弱点分析つきの演習ができます