トップ過去問一覧応用情報技術者 平成21年・秋 > 問5
問5

n個の要素x1,x2,・・・,xnから成る連結リストに対して、新たな要素xn+1の末尾への追加に要する時間をf(n)とし、末尾の要素xnの削除に要する時間をg(n)とする。nが非常に大きいとき、実装方法1と実装方法2におけるg(n)/f(n)の挙動として、適切なものはどれか。

 

 

 

実装方法1

実装方法2

○正解
×不正解

ほぼ1になる

ほぼ1になる

ほぼ1になる

ほぼnに比例する

ほぼnに比例する

ほぼ1になる

ほぼnに比例する

ほぼnに比例する

解説

実装方法1では新たな要素を追加する際にはfrontから最後のセルまで順に辿らなくてはならず、処理時間f(n) はn が増えるほど増加するのでn に比例することになります。同じように削除処理時間g(n)もnが増えれば同様にn に比例するのでg(n)/f(n)はほぼ1になります。

実装方法2では追加の場合はrearのアドレス指定に従い1つ追加するだけなので処理時間はほぼ1になります。しかし削除する場合はrearからは1つ前のアドレスがわからないためfrontから順に辿ることになり作業時間g(n)はn に比例します。よってg(n)/f(n)はnに比例します。

無料学習システムはこちら
→間違えた問題を繰り返し学習
→分野別学習
→模擬試験モード
デモサイト
無料ユーザ登録

問題文や解説文の内容の正確性については、できるかぎりチェックをしていますが、間違いがある可能性があります。 十分ご注意の上、参考までにご利用ください。