🗒️
３０日後に基本情報技術者試験を受ける人によるまとめノート（１日目）
この記事について
３０日後（２０２４年２月２９日時点）に基本情報技術者試験を受ける自分が、学習のために記すまとめノート的なものです。
記事一覧はこちら
本文
①データ構造
-
スタックとは最後に格納したデータを最初に取り出すデータ構造
- イメージとしては「積み上げられた本」
- データを格納することをpush、取り出すことをpopという。
- 後入れ先出しアルゴリズム（LIFO） という
-
キューとは最初に格納したデータを最初に取り出すデータ構造
- イメージとしては「待ち行列」
- データを格納することをenqueue、取り出すことをdequeueという。
- 先入れ先出しアルゴリズム（FIFO） という。
-
配列とはデータを表の形に並べたデータ構造
- 添え字に要素が関連付けられて保存されている。
- １次元配列と２次元配列がある。
- ２次元配列の値は
配列名(行,列)で表す - 参照と更新が早い
-
連結リストとはデータを数珠つなぎで並べたデータ構造
-
ポインタに要素が関連付けられて保存されている。
- アドレスが０のデータに３というポインタがつけられていたら、次のデータのアドレスは３。
- 単方向リスト、双方向リスト、線形リスト、環状リストの４種類がある
- 挿入と削除が早い
-
ポインタに要素が関連付けられて保存されている。
-
木構造とは階層構造を持つデータ構造
- 最上位を根、分岐を節、末端を葉という。
- 二分木のうち、
左の子孫＜親＜右の子孫となっているものを二分探索木という。
②アルゴリズムの基本
③アルゴリズムの分類
- 整列アルゴリズム（データを並べる）
- バブルソート
- 配列の先頭から隣り合ったデータを比較して順序が誤っているものの交換を繰り返す
- 選択ソート
- 配列の先頭から順にデータを比較して最小値を選択し、先頭とのデータ交換を繰り返す
- 挿入ソート
- 整列してある配列に追加要素を適切な場所に挿入することを繰り返す
- クイックソート （頻出）
- 基準値を最初に決め、データ全体を基準値より大きいか小さいかに分けることを繰り返す
- もっとも高速なアルゴリズム
- バブルソート
- 探索アルゴリズム（データを見つける）
- 線形探索法
- 先頭からひとつづつ照合を繰り返す
- ハッシュ法 （頻出）
- ハッシュ関数を使ってデータをハッシュ値に変換し、ハッシュ値を添え字として持つハッシュ表から目的のデータを見つける
- ハッシュ値が被る衝突が起こる可能性がある
- 二分探索法 （頻出）
- 列の中央の要素を見つけ、目的のデータと比較し、それよりも大きいか小さいか比べることを繰り返す
- データを前もって整列させておく必要がある
- 効率の良いアルゴリズム
- 線形探索法
- 再帰的アルゴリズム
- 処理の途中で自分自身を呼び出すアルゴリズム
- 再帰呼び出しする関数を再帰関数という
- 総和、剰余、階乗を求めるアルゴリズム
④アルゴリズムの計算量
- 二分探索法
-
O(\log_2n) -
logとは、定数（下付き数字）を何度欠けたら数xになるか、を表す
-
- ハッシュ法
-
O(1)
-
- 線形探索法
-
O(n)
-
- クイックソート
-
O(n \log n) - 二分探索法の計算量をさらに
n倍する
-
⑤プログラムの性質
- 再帰（リカーシブ） （頻出）
- 先述。プログラムの実行中に自分自身を呼び出せる
- 再入可能（リエントラント） （頻出）
- 複数のプログラムから同時に呼び出されても正しく動作する
- 再配置可能（リロケータブル）
- どこにプログラムを配置しても正しく動作できる
- 再使用可能（リユーザブル）
- リロードしなくても動作できる
⑥言語の種類
内容まとめ
- データ構造
- アルゴリズムの基本
- アルゴリズムの分類
- アルゴリズムの計算量
- プログラムの性質
- 言語の種類
Discussion