アルゴリズムとプログラミング
基本情報技術者試験｜要素数nの単方向連結リストにおいて、先頭ノードへのポインタが分かっているとき、リストの先頭に新しい要素を1個挿入…
要素数nの単方向連結リストにおいて、先頭ノードへのポインタが分かっているとき、リストの先頭に新しい要素を1個挿入する処理の計算量はどれか。
アO(1)
イO(log n)になる
ウO(n)で線形時間
エO(n^2)に達する
正解
ア．O(1)
連結リストの先頭挿入は、新ノードのnextを現在の先頭に向け、リストの先頭ポインタを新ノードに更新するだけで完了する。要素数nに関係なく一定回数の操作で済むためO(1)で正しい。
?選択肢ごとの解説
ア ○連結リストの先頭挿入は、新ノードのnextを現在の先頭に向け、リストの先頭ポインタを新ノードに更新するだけで完了する。要素数nに関係なく一定回数の操作で済むためO(1)で正しい。
イ ×O(log n)は探索範囲を半減する二分探索などの量であり、ポインタ付け替えだけの先頭挿入には対数的な分割が存在しないため当てはまらない。
ウ ×O(n)は先頭が分からず先頭まで走査する場合や末尾挿入で末尾までたどる場合の量であり、先頭ポインタ既知の先頭挿入には不要な走査である。
エ ×O(n^2)は二重ループ相当の量で、単純な1要素の先頭挿入とはかけ離れており、過大な見積りである。
アルゴリズムとプログラミングの他の問題
平衡が保たれた2分探索木に約100万個の要素を格納したとき、根から葉までの高さ(段数)はおよそどの程度になるか。なおlog2…スロット数が500のハッシュ表に、現在350個のデータが格納されている。このハッシュ表の負荷率(占有率)はいくらか。次のデータ構造で目的の値を1個探索するときの平均計算量を比べる。最も速い(オーダが小さい)ものはどれか。ただし表引き方式は衝…単純選択ソートで要素数nの配列を昇順に整列するとき、要素の比較回数は最悪・平均ともにおよそどれで表されるか。挿入ソートの計算量について最も適切に述べたものはどれか。シェルソートの基本的な考え方を最も適切に説明したものはどれか。ヒープソートの最悪計算量と安定性の組合せとして正しいものはどれか。衝突がほとんど起きないよう設計されたハッシュ表を用いた探索の、平均的な計算量はどれか。
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0129