アルゴリズムⅠ

単語カード

設定全面表示

• キューに関する記述として，最も適切なものはどれか。

  最初に格納されたデータが最初に取り出される
• 整列されたn個のデータの中から，求める要素を2分探索法で探索する。この処理の計算量のオーダを表す式はどれか。

  log n
• 関数ƒ(x)は，引数も戻り値も実数型である。この関数を使った，①～⑤から成る手続を考える。手続の実行を開始してから②～⑤を十分に繰り返した後に，③で表示されるyの値に変化がなくなった。このとき成立する関係式はどれか。

  ƒ(y)＝y
• ポインタを用いた線形リストの特徴のうち，適切なものはどれか

  ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。
• 配列Aが図2の状態のとき，図1の流れ図を実行すると，配列Bが図3の状態になった。図1のaに入れるべき操作はどれか。ここで，配列A，Bの要素をそれぞれ　A(i，j)，B(i，j)とする。

  A(i，j) → B(j，7－i)
• 整列アルゴリズムの一つであるクイックソートの記述として，適切なものはどれか。

  対象集合から基準となる要素を選び，これよりも大きい要素の集合と小さい要素の集合に分割する。この操作を繰り返すことで，整列を行う。
• 　ƒ(n)：if n≦1 then return 1 else return n＋ƒ(n－1)

  15
• 10個の節(ノード)からなる次の2分木の各節に，1から10までの値を一意に対応するように割り振ったとき，節a，bの値の組合せはどれになるか。ここで，各節に割り振る値は，左の子及びその子孫に割り振る値より大きく，右の子及びその子孫に割り振る値より小さくする。

  a＝6，b＝7
• 2次元の整数型配列 a の各要素 a(i，j) の値は，2i＋j である。このとき， a(a(1，1)×2，a(2，2)＋1) の値は幾つか。

  19
• xとyを自然数とするとき，流れ図で表される手続を実行した結果として，適切なものはどれか。

  x÷yの商、x÷yの余り
• 2分探索木になっている2分木はどれか。

  昇順になっているやつ
• 整数x，y(x＞y≧0)に対して，次のように定義された関数F(x，y)がある。F(231，15)の値は幾らか。ここで，x mod y はxをyで割った余りである。

  3
• データ構造の一つであるリストは，配列を用いて実現する場合と，ポインタを用いて実現する場合とがある。配列を用いて実現する場合の特徴はどれか。ここで，配列を用いたリストは，配列に要素を連続して格納することによって構成し，ポインタを用いたリストは，要素から次の要素へポインタで連結することによって構成するものとする。

  位置を指定して，任意のデータに直接アクセスすることができる。
• 流れ図は，シフト演算と加算の繰り返しによって，2進整数の乗算を行う手順を表したものである。この流れ図中のa，bの組合せとして，適切なものはどれか。ここで，乗数と被乗数は符号なしの16ビットで表される。X，Y，Zは32ビットのレジスタであり，けた送りは論理シフトを用いる。最下位ビットを第0ビットと記す。

  ０ビット、左、右
• 関数 ƒ(x，y)が次のように定義されているとき，ƒ(775，527)の値は幾らか。ここで，x mod yはxをyで割った余りを返す。 ƒ(x，y): if y = 0 then return x else return ƒ(y，x mod y)

  31
• 顧客番号をキーとして顧客データを検索する場合，2分探索を使用するのが適しているものはどれか。

  顧客番号の昇順に配置されているデータ構造
• A，B，C，Dの順に到着するデータに対して，一つのスタックだけを用いて出力可能なデータ列はどれか。

  C，B，D，A
• 次の二つのスタック操作を定義する。 　PUSH n：スタックにデータ(整数値n)をプッシュする。 　POP：スタックからデータをポップする。 空のスタックに対して，次の順序でスタック操作を行った結果はどれか。 　PUSH 1 → PUSH 5 → POP → PUSH 7 → PUSH 6 → PUSH 4 → POP → POP → PUSH 3

  1.7.3
• リストを二つの1次元配列で実現する。配列要素 box[i] と next[i] の対がリストの一つの要素に対応し，box[i] に要素の値が入り，next[i] に次の要素の番号が入る。配列が図の状態の場合，リストの3番目と4番目との間に値が H である要素を挿入したときの next[8] の値はどれか。ここで，next[0] がリストの先頭(1番目)の要素を指し，next[i] の値が0である要素はリストの最後を示し，next[i] の値が空白である要素はリストに連結されていない。

  7
• 表探索におけるハッシュ法の特徴はどれか。

  キーの関数値によって格納場所を決める。
• 待ち行列に対する操作を，次のとおり定義する。 ENQ n: 待ち行列にデータnを挿入する。 DEQ : 待ち行列からデータを取り出す。 　空の待ち行列に対し，ENQ1，ENQ2，ENQ3，DEQ，ENQ4，ENQ5，DEQ，ENQ6，DEQ，DEQの操作を行った。次にDEQ操作を行ったとき，取り出されるデータはどれか。

  5
• クイックソートの処理方法を説明したものはどれか。

  適当な基準値を選び，それより小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
• 2分探索木として適切なものはどれか。ここで，1～9の数字は，各ノード(節)の値を表す

  昇順になっているやつ
• 三つのスタックA，B，Cのいずれの初期状態も[1，2，3]であるとき，再帰的に定義された関数ƒ()を呼び出して終了した後のBの状態はどれか。ここで，スタックが，[a1 a2，…，an-1]の状態のときにanをpushした後のスタックの状態は[a1 a2，…，an-1，an]で表す。

  [1，2，3，1，2，3]
• 次の流れ図は，2数 A，B の最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。Aが876，Bが204のとき，何回の比較で処理は終了するか。

  11
• 次の流れ図は，10進整数 j(0＜j＜100) を8桁の2進数に変換する処理を表している。2進数は下位桁から順に，配列の要素 NISHIN(1) から NISHIN(8) に格納される。流れ図のa及びbに入る処理はどれか。ここで，j div 2 はjを2で割った商の整数部分を，j mod 2 はjを2で割った余りを表す。

  nishin,div
• A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。

  3
• 配列Aが図2の状態のとき，図1の流れ図を実行すると，配列Bが図3の状態になった。図1のaに入れる操作はどれか。ここで，配列A，Bの要素をそれぞれ A(i，j)，B(i，j) とする。

  B(i，7－j) ← A(i，j)
• 10進法で5桁の数 a1a2a3a4a5 をハッシュ法を用いて配列に格納したい。ハッシュ関数を mod(a1＋a2＋a3＋a4＋a5，13) とし，求めたハッシュ値に対応する位置の配列要素に格納する場合，54321は配列のどの位置に入るか。ここで，mod(x，13) は，xを13で割った余りとする。

  2
• 　ƒ(n)：if n≦1 then return 1 else return n＋ƒ(n－1)

  15
• 0≦x≦1の範囲で単調に増加する連続関数ƒ(x)が ƒ(0)≦0≦ƒ(1) を満たすときに，区間内で ƒ(x)＝0 であるxの値を近似的に求めるアルゴリズムにおいて，(2)は何回実行されるか。 〔アルゴリズム〕 x0←0，x1←1とする。 x← x0＋x1 2とする。 x1－x＜0.001ならばxの値を近似値として終了する。 ƒ(x)≧0ならばx1←xとして，そうでなければx0←xとする。 (2)に戻る。

  10
• キューに関する記述として，最も適切なものはどれか。

  最初に格納されたデータが最初に取り出される。
• 加減乗除を組み合わせた計算式の処理において，スタックを利用するのが適している処理はどれか。

  計算の途中結果を格納し，別の計算を行った後で，その計算結果と途中結果との計算を行う処理
• 要素番号が0から始まる配列 TANGO がある。n個の単語が TANGO[1] から TANGO[n] に入っている。図は，n番目の単語を TANGO[1] に移動するために，TANGO[1] から TANGO[n－1] の単語を順に一つずつ後ろにずらして単語表を再構成する流れ図である。aに入れる処理として，適切なものはどれか。

  TANGO[i＋1] ← TANGO[i]
• 顧客番号をキーとして顧客データを検索する場合，2分探索を使用するのが適しているものはどれか。

  顧客番号の昇順に配置されているデータ構造
• 十分な大きさの配列Aと初期値が0の変数pに対して，関数ƒ(x)とg()が次のとおり定義されている。配列Aと変数pは，関数ƒ(x)とg()だけでアクセス可能である。これらの関数が操作するデータ構造はどれか。

  スタック
• 自然数をキーとするデータを，ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を 　　h(x) = x mod n とすると，任意のキーaとbが衝突する条件はどれか。ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。

  a－bがnの倍数
• 再帰的に定義された手続きprocで，proc(5)を実行したとき，印字される数字を順番に並べたものはどれか。

  5432112345

広告

コメント