読者です 読者をやめる 読者になる 読者になる

【応用情報】アルゴリズム解けなかった問題メモ

平成28年春期 問6

流れ図に示す処理の動作の記述として,適切なものはどれか。ここで,二重線は並列処理の同期を表す。
f:id:yusuke_ujitoko:20160904212836p:plain

  • ABC又はACBを実行してデッドロックになる。
  • AB又はACを実行してデッドロックになる。
  • Aの後にBC又はCB,BC又はCB,…と繰り返して実行する。
  • Aの後にBの無限ループ又はCの無限ループになる。

平成26年春期 問19

ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで,複数のデータが同じハッシュ値になることはないものとする。
http://www.ap-siken.com/bunya.php?m=2&s=2&no=9

平成25年春期 問7

配列Aに対して次の手続を実行して,2≦k≦100である素数kだけを全て出力したい。a,b,cに入るループの初期値,終値,増分として,適切な組合せはどれか。
f:id:yusuke_ujitoko:20160904220632p:plain

平成24年秋期 問6

アルゴリズムの処理時間や問題の計算時間を比較するときに使用するオーダ記法の説明として,適切なものはどれか。

平成23年秋期 問7

n個の正の整数x1,x2,…,xn が並んだ線形リストを[x1,x2,…,Xn]で表し,空リストは[ ]で表す。次のように再帰的に定義される関数func(L)を,L=[1,3,2]を実引数として呼び出したとき, print文によって表示される数字はどれか。ここで,プログラム中の=は等号,:=は代入を表す。

〔関数の定義〕
first([x1,x2,…,xn])はx1を返す。
butfirst([x1,x2,…,xn])は[x2,…,xn]を返す。butfirst([x])は[ ]を返す。
max(x,y)は,X≧yであればxを返し,そうでなければyを返す。
func(L)
begin
 if L = [] then return 0;
 A := first(L);
 B := func(butfirst(L));
 C := max(A, B);
 print C;
 return C;
end

平成20年春期 問13

次の流れ図において,ステップS4でYesと判断したときまでの,ステップS1~S4の実行回数をそれぞれn1~n4とする。n1~n4の間に成立する式はどれか。
http://www.ap-siken.com/kakomon/20_haru/img//13.gif

  • n4=n1+n2+n3
  • n4=n1+n2-n3
  • n4=n1-n2+n3
  • n4=-n1+n2+n3

平成19年春期 問12

2整数X,Yをキーとするデータを,ハッシュ関数h(X,Y)を使って,要素数256の1次元配列に格納する。Xは値1~256を一様にとり,Yは値1~16を一様にとる。ハッシュ関数として最も不適切なものはどれか。ここで,N=256であり,A mod BはAをBで割った剰余を表す。

  • X mod N
  • Y mod N
  • (X+Y) mod N
  • (X×Y) mod N

平成18年春期 問13

キー値が1~1,000,000の範囲で一様にランダムであるレコード3件を,大きさ10のハッシュ表に登録する場合,衝突が起こらない確率は幾らか。ここで,ハッシュ値にはキー値をハッシュ表の大きさ10で割った余りを用いる。

  • 0.28
  • 0.7
  • 0.72
  • 0.8

平成18年春期 午前問15

条件1~4の検査する順序を変えても,動作が変化しない決定表はどれか。ここで,"-"は条件を判定しないことを表す。

平成18年春期 問28

ハッシュ法によるデータ編成法において,レコード値が図のような分布にしたがって発生する場合,シノニムの発生を最少とするハッシュアドレス(ハッシュした結果のアドレス値)の分布として適切なものはどれか。
f:id:yusuke_ujitoko:20160906235504p:plain

平成17年秋期 問12

キー値が等しい要素同士について,整列前の要素の順序(前後関係)を保つアルゴリズムを,安定な整列アルゴリズムという。次の二つの整列アルゴリズムに対して,安定にできるかどうかを考える。正しい組合せはどれか。

アルゴリズムとその特徴〕
選択ソート
未整列の並びに対して,最小のキー値をもつ要素と先頭の要素とを入れ換える。同様の操作を,未整列の並びの長さを一つずつ減らしながら繰り返す。
挿入ソート
未整列要素の並びの先頭の要素を取り出し,その要素を整列済みの要素の中の正しい位置に挿入する。

f:id:yusuke_ujitoko:20160907000401p:plain

平成17年春期 問11

昇順に整列されたn個のデータが格納されている配列Aがある。流れ図は,配列Aからデータxを2分探索法を用いて探し出す処理を表している。a,bに入る操作の正しい組合せはどれか。ここで,除算の結果は小数点以下が切り捨てられる。
f:id:yusuke_ujitoko:20160907000838p:plain
f:id:yusuke_ujitoko:20160907000851p:plain