よってマークNo.09の答えは0、マークNo.10の答えは6となる。中から中央値を選び、返す関数でした。応用ソートの1つであるクイックソートのピボットを決める問題でした。ちなみにクイックソートは、ピボットの決め方によって計算時間が結構変化します。クイックソートなどの応用ソートの復習はこちらから。番兵とはつぎの探索アルゴリズムの中で、番兵が有効なものはどれか。解答:2番兵は、線形探索においてあらかじめ目的のデータを配列の末尾につけておくことで探索の効率を上げるテクニックの1つです。番兵とはなにかを聞く問題でした。それぞれのテクニックがどのアルゴリズムに使われているかはセットで頭に入れておきましょう。データ構造の総まとめデータ構造に関する記述のうち、適切なものはどれか。問題13][選択肢]2分木は、データ間の関係を階層的に表現する木構造の一種であり、すべての節が二つの子をもつデータ構造である。スタックは、最初に格納したデータを最初に取り出す先入れ先出しのデータ構造である。線形リストは、データ部と次のデータの格納先を指すポインタ部から構成されるデータ構造である。配列は、ポインタの付替えだけでデータの挿入・削除ができるデータ構造である。解答:3一つずつ選択肢を見ていきましょう。飛びついて1番を選ばないように注意してください。正しそうに見えるが、2分木はすべての節が2つ以下の子を持つデータ構造です。スタックは最後に格納したデータを最初に取り出すデータ構造です。(選択肢の説明はキューの説明)大正解!連結リストの説明。★コメント★データ構造の総復習問題でした。正しそうに見えるひっかけ選択肢を選ばないように選択肢をよく読んでから答えを選びましょう。次の(1)〜(3)の問いに答えなさい。それぞれの問いにある図のスタック・キューは下から順番にデータが入る。空の状態のスタックとキューから、次の手続を順に実行していく。入っているデータの値を解答欄にマークしなさい。空欄の(何も入っていない)場合は0をマークすること。ここで、手続きに引用している関数は、次のとおりとする。※(2)以降も用いるpush(x):データxをスタックに積む。pop():データをスタックから取り出して,その値を返す。enqueue(x):データxをキューに挿入する。dequeue():データをキューから取り出して,その値を返す。7点]No.13:0No.14:6No.15:2No.16:5No.17:3No.18:1No.19:4それぞれの手続きごとのスタック、キューの変化を書くと、下の表のようになる。★コメント★スタック、キューの操作の過程を答える問題でした。基本情報にも出てくるタイプの問題です。頭でやるのではなく、落ち着いて1ステップずつ書き出していくことを強くおすすめします。スタック、キューの復習はこちらから。ある状態(空ではない)から次の手続きを順に実行すると、スタック・キューの中身は下の図のようになった。当てはまるデータの値をマークしなさい。データの値が確定しないときは0をマークすること。6点]No.20:2No.21:7(1)と同じように手続きによるスタック、キューの変化を書いていく。逆順なので(1)よりも慎重に変化の流れを書いていこう。★コメント★(1)とは異なり、逆順にさかのぼっていく必要があるため、より慎重に1ステップずつ書き出していきましょう。(ii)で入力されるデータがある。各データについて1回ずつスタックの挿入(push)と取り出し(pop)を行うことができる場合、データの出力順序は何通りあるかをそれぞれマークしなさい。pop(1)の2通り。pop(1)の5通り。思った人もいるかもしれません。3を順番に一旦スタックに入れる必要があります。3の順にスタックに入れてしまうと、どうがんばっても2よりも先に1を出力することができません。順に出力することはできません。★コメント★スタック、キューの応用問題でした。この問題が初見で解ければスタック、キューは理解したと思っていただいてOKです。次の(1)〜(2)の問いに答えなさい。(2)ともに同じデータ値のノードは考えないものとする。下図のような2分木の走査順を考える。このとき、つぎの[i]〜[iv]の走査方法で、4番目と7番目に走査されるデータの値をそれぞれマークしなさい。7」の順に走査するため、4番目は1、7番目は9となる。行きがけ順(先行順)ノード→左側→右側の順に見ていく。ノードを反時計回りに一筆書きしたとき(緑色の線)のノードの左側を通る順番がそのまま行きがけ順となる。9」の順に走査するため、4番目は3、7番目は5となる。通りがけ順(中間順)左側→ノード→右側の順に見ていく。ノードを反時計回りに一筆書きしたとき(緑色の線)のノードの下側を通る順番がそのまま通りがけ順となる。9」の順に走査するため、4番目は4、7番目は7となる。(なお、通りがけ順による2分探索木の走査順は、ノードの値を昇順に並べたものと必ず一致します。)帰りがけ順(後行順)ノード→左側→右側の順に見ていく。ノードを反時計回りに一筆書きしたとき(緑色の線)のノードの右側を通る順番がそのまま帰りがけ順となる。4」の順に走査するため、4番目は5、7番目は9となる。★コメント★2分探索の走査に関する問題でした。行きがけ順、通りがけ順、帰りがけ順は、解答例のように反時計周りにノードを囲うように一筆書きしてから解いていくことをおすすめします。(1)とは別の下図のような2分探索木(順序木となる2分木)を考える。(a)と(b)に入れられる自然数(1以上の整数)は全部で何通りあるかをマークしなさい。無限に存在する場合は0をマークすること。6点]No.24:6No.25:2(a)には、左子ノードと右子ノードの2つがある。<(右子ノード)」となる必要がある。30」を満たす必要がある。(b)」を満たす必要である。子ノードを持つ親ノードを削除することを考える。このとき、自身以下の部分木から新しく親となるノードを移動させることで順序木を崩さずに2分探索木を構成することができる。(b)で表されるノードを削除するとき、それぞれどのノードを新しく親にすれば(削除した場所にノードを移動させれば)順序木を崩さずに2分探索木を構成することができるかを下の選択肢の中からすべて選び、該当する番号をマークしなさい。45のノードには、子が1つなので移動できる候補は1つしか存在しない。5のノードの部分木には「2のノード」しかないため、2を移動させるしか方法がない。20のノードには子が2つあるため、移動できる候補が2つ存在する。左部分木で一番大きいノードは12、右部分木で一番小さいノードは23なのでこの2つのノードを移動させればよい。★コメント★2分探索木の追加、削除に関する問題でした。2つ子ノードがあるノードを削除するときが少しややこしいのであやふやな人は復習しましょう。某Y音楽能力検定の指導グレードの成績を処理するプログラムを作りたい。(1)〜(3)の問いに答えなさい。ここで、指導グレードの成績はソルフェージュ(solf)・鍵盤実技(key)・調音(choon)・楽典(gakuten)・コード(chord)の5つで評価される(成績は0点〜100点の1点刻み)。下の表は、指導グレードの成績の例である。受験番号をid、名前をname、英語の得点をeng、ソルフェージュの成績をsolf、鍵盤実技の成績をkey、調音の成績をchoon、楽典の成績をgakuten、コードの成績をchordを管理する構造体RESULTを解答欄に記入しなさい。20桁以内の英数字で管理される。・受験番号は必ず数字となり、小数、英字は入らない。・各5科目はそれぞれ100点満点で、0〜100点の1点刻みで採点される。半角20文字だけでなく、NULL文字分1文字を入れて合計21文字分の領域が必要なので注意。RESULT;と書いてもOK*1。構造体を作成する基本問題でした。何度も言いますが、最後のセミコロンを忘れないようにしましょう。[ii]の処理を行う関数を作りなさい。引数としてとり、rに格納されている5科目の合計点数を出力する関数sum_score。(ある受験者rの5科目の合計点を出す関数を作ればよい。(ソルフェージュの点数)の値を取得できます。合格条件は下の2つの条件を両方満たした場合である。(ある受験者rの合否を判定する関数を作ればよい。・5つの項目のうち、60点未満の項目が1つも存在しないこと前のページにある表の受験者のうち、合格しているのは受験番号が1番、2番、5番、3番の人である。それ以外は平均75点未満なので不合格}★採点基準★おかしい箇所1箇所ごとに:-2条件分岐に注意しましょう。基準点以下であれば不合格あとは平均75点(合計375点)以上あるかの判定と書くのがおすすめです。★コメント★ほぼプログラミングができるかどうかの問題でした。「平均点75点以上=合計点375点以上」と置き換えると、キャストを考えなくていいので楽です。配列で格納されている。データは全くのランダムな順に並んでいる。(受験番号順でもなく、成績順でもない。受験者が合格しているかどうかを調べたい。探索したい場合、線形探索・2分探索のどちらで行うのが効率的か。理由とともに答えなさい。[2点]理由:受験番号順の昇順に並んでいないため、2分探索は行えない。2分探索ができるようにソートするにも時間がかかるため、最初から線形探索を行ったほうが早くデータの探索ができるから。降順に並んでいる必要があります。今回探索する受験番号は、順番には並んでいないため、ソートを行う必要があります。程度)ので、「ソート」と「2分探索」の両方をする時間よりも「線形探索」だけをする時間のほうが短くなりますよね。線形探索のほうが効率がよいといえます。