スライドモード

アルゴリズムとデータ構造 ITパスポート対策テクノロジ系基礎理論編⑥

8 views

2023-10-222023-10-21

アルゴリズム

アルゴリズムとは、特定の目的を達成するための処理手順のことです。ただこれでは非常に範囲が広いため、通常アルゴリズムの授業等では、様々な問題で共通に使用される処理手順(探索、並べ替えなど)が解説されます。

最終的な結果が同じでも、アルゴリズムは複数存在する場合が多く、処理にかかる時間やメモリ使用量でアルゴリズム間の優劣が判断されます。

アルゴリズムの表現方法

アルゴリズムは実際のプログラミング言語やこれを模した疑似言語で書かれる他、以下のような流れ図(フローチャート)で表現されることもあります。

記号機能
フローチャート-端子処理の開始、終了を表す。
フローチャート処理様々な具体的処理を表す。
フローチャート-判断条件を判断して処理を分岐する。
フローチャート-ループループの始まり、終わりを表す。この記号の代わりに条件と矢印で表現される場合もあります。

アルゴリズムの基本構造

アルゴリズムの基本構造には順次,選択,繰返しの3つがあります。

順次構造

上から下に書かれた順番に従って処理を行っていきます。

順次構造

選択構造

分岐点の選択条件に従って処理の流れを枝分かれさせます。

選択構造

繰返し構造

条件を満たしている間、同じ処理を繰り返します。ループの最初で条件判定を行う方式と最後で行う方式があります。永遠に条件を満たし続ける場合は無限ループに陥ります。

ループ構造

代表的なアルゴリズム

整列のアルゴリズム

バブルソート隣のデータと比較し、大小の順が逆であれば入れ替えるという動作を繰り返すことで整列を行う。
選択ソート最小値を探して、未整列部分の先頭と交換するという動作を繰り返すことで整列する。
クイックソート基準値をもとに大小2グループに分けるという動作を繰り返すことで整列する。
マージソートその中で整列するまでデータを2等分した後、分割したデータを併合するで整列する

この中で一番早い(計算量が小さい)ソート方法はマージソートです。

探索のアルゴリズム

線形探索法先頭から順に1つずつ探索値と比較していく方法。
2分探索法中央の値と比較し、大きければ後半、小さければ前半のデータの大して同じことを繰り返す(データが事前に整列されていることが条件)。
線形探索法と2分探索法の違い

データ構造

変数

もっとも基本的なデータの格納方法で、変数と呼ばれるデータの入れ物にデータを代入することで使用します。

型付きの変数と型なしの変数

変数にはどんなデータでも入れることができる型なしの変数と入れることのできるデータの種類(文字、整数、真理値など)が決まっている付きの整数があります。

配列

配列は同じ型のデータを集めて順序付けたデータ構造です。個々の要素にはその配列の中の位置であるインデックスを利用してアクセスすることができます。

配列の構造

リスト

リストは配列と似ていますが、次のデータ位置をポインタと呼ばれる情報によって示すことでより柔軟性を高めたデータ構造です。

リストのデータ構造

キュー

先に入れたものから先に取り出すことのできる先入れ先出し(FIFO)方式のデータ構造です。

キューのデータ構造

スタック

後に入れたものから先に取り出すことのできる後入れ先出し(LIFO)方式のデータ構造です。

スタックのデータ構造

木構造

木のように上部から下部に行くにしたがって枝分かれしていくデータ構造です。各節をノードといい、ノードの数が最大でも2個になるツリーを2分木(バイナリツリー)といいます。

木構造のイメージ

確認問題(過去問)

ITパスポート試験令和5年問69

配列に格納されているデータを探索するときの, 探索アルゴリズムに関する記述のうち、 適切なものはどれか。

ITパスポート試験令和3年問74

流れ図 X で示す処理では,変数 i の値が, 1 → 3 → 7 → 13 と変化し,流れ図 Y で示す処理では,変数 i の値が, 1 → 5 → 13 → 25 と変化した。図中の a, b に入れる字句の適切な組合せはどれか。

流れ図

ITパスポート試験平成30年春問96

先入れ先出し(First-In First-Out, FIFO)処理を行うのに適したキューと呼ばれるデータ構造に対して“8","1","6","3" の順に値を格納してから、取出し を続けて2回行った。2回目の取出しで得られる値はどれか。

ITパスポート試験平成30年問76

複数のデータが格納されているスタックからのデータの取出し方として、 適切なものはどれか。

ITパスポート試験平成28年秋問92

後に入れたデータが先に取り出されるデータ構造 (以下, スタックという)がある。これを用いて, 図に示すような, 右側から入力されたデータの順番を変化させて, 左側に出力する装置を考える。 この装置に対する操作は次の3通りである。

  1. 右側から入力されたデータをそのまま左側に出力する。
  2. 右側から入力されたデータをスタックの1番上に積み上げる。
  3. スタックの1番上にあるデータを取り出して左側に出力する。

この装置の右側から順番にデータ A, B, C, D を入力した場合に,この1~3の操作を組み合わせても, 左側に出力できない順番はどれか。

ITパスポート平成28年秋問92

これだけで受かるITパスポート

https://ja.mondder.com

link-image

IT・ICT

ユーザーアイコン

Official

このアカウントで公開されている過去問に解説をつけたいという方がおられましたら問題差し上げますのでご連絡下さい。。

TwitterLINEHatenaURL