基本情報技術者試験
こちらより
内容がまとまったので
まとめて投稿しなおします。
①変数と配列
データの格納方法を【データ構造】といいます。
データ型
データの種類のこと
- 整数型
- 少数型
- 文字型
- 論理型: 偽が真を表す
変数
数学で扱うものと一緒
変数にはデータを一つだけ格納することができます。
レコード型の変数
構造体変数ともいいます。
複数の項目をもつ情報カードのような変数です。
例として
⚪️学生型の形式 ⇦ 〜型の形式と呼称する
| 項目名 | 型 | 内容 |
|---|---|---|
| id | 整数型 | 1000 |
| name | 文字型 | tanaka |
| sex | 文字型 | otoko |
このように
形式を呼称して
格項目に情報を入れて行きます。
変数aに会員番号を格納するには
a.id ⇦ 10001
と表記します。
配列
棚や靴箱と行ったイメージ
一つの配列に同系統のデータが複数入っている訳です。
先頭要素を0か1とする場合があるので注意が必要です。
()などの括弧で要素番号を指定します。
例えば配列aの6番目の要素を指定する時
最初が1の時
a(6)
最初が0のとき
a(5)
とします。
二次元配列
基盤の目のようにマス目をもつ配列です。
例えば
配列名: 学生
行番号: 学生の名前
列番号: 数学の成績(他にも国語の成績など)
という風に取り出します。
②リスト,スタック,キュー
リスト: データとデータをリンクで接続して、順番にデータを取れるようにしたものです。
スタック: 直近から古い順にデータを遡ってデータを取り出したい時に使用します。
のデータ構造ともいいます。後入れ先出し(LIFO)
キュー: データを格納した順に取り出したい時に使用
リスト(線形リスト)
リストの構成データをリストの要素といいます。
特徴として
- レコード型の変数
- データをいれる項目
- 次の要素のアドレスをいれる項目
- 末尾の.nextにはNULLや-1がが入れられます。
スタック
データを積み重ねて管理するイメージです。
用語として
- プッシュ(PUSH): データをいれる。
- ポップ(POP): データを取り出します。
後入れ先出しの法則です。
キュー
データを行列入れて管理するイメージです。
- エンキュー(ENQUEUE またはENQ): データを格納する
- デキュー(DEQUEUEm またはDEQ): データ取り出し
③木
木構造では、データを格納する部分を接点(ノード)といいます。
構造的にデフォルトされた木を逆さまにした構造になっています。
親: 上位階層にある節点
子: 下位階層にある節点
根: 最上位の節点
葉: 子を持たない節点
二分木と多分木
二分木
一番最初の根で、分かれているのは二つまでの構造
ヒープ
データを並べ替える用途
二分探索木
データを検索する用途
多分木
根の部分で3っ以上に分かれている構造
B木
データを検索する用途に使用
全ての葉が同じ階層にある構造です。
完全二分木とヒープ
上位から順に、かつ、同じ階層で左から詰まっている
構造を完全二分木をいいます。
ヒープは更に完全二分木に置いて
親>子 または 子<親
の条件が全て成立している木です。
ヒープの条件
- 完全二分木であること
- 親子間に一定の大小関係が成立していること
二分探索木の条件
下記の条件を満たしていることが条件です。
- 節点の値< (節点の右についている全ての子の値)
- (節点の左についている全ての子の値)< 節点の値
木の巡回
データを順番に見ていくことを巡回するといいます。
幅優先探索
同じ階層の節点を優先して巡回します。
上から順 かつ 左から順です。
深さ優先探索
下位層の節点を優先して巡回します。
根からすぐ下に下に潜って行って、突き当たったら
一つ上に戻り下に、全て見終わっってたら上に戻って同じく・・・
という方法です。
先行順
行きがけ順に行います。
中間順
一旦一番下を処理してから途中の節点を処理していく
後行順
一番下を優先
④探索
アルゴリズム: 処理の手順
データを探すアルゴリズム: 線形探索、二分探索、ハッシュ法
時間計算量(オーダ)
データ数の増加に対する、処理時間の増加指標
オーダ記法(O記法)
O(n)などと記述して、効率の良さを表します。
(n)は処理するデータの数を表します。
O(1)
データ数にかかわらず、処理時間が一定
O(log n)
データ数が２倍に増えても、手間が一回増えるだけ
O(n)
データ数が10倍だと処理時間も10倍になります。
O(nlog n)
データ数が10倍だと処理時間も30倍になります。
O(nc) (cは小文字)
データ数が10倍だと
処理時間は二乗で100倍になります。
探索アルゴリズム
左のオーダ記法は時間計算量を表します。
線形探索 O(n)
順番に一つずつ、値の比較をしていく
二分探索 O(logn)
データの整列が前提条件
データを前半と後半に分けて行います。
小さい順に並んていれば
中央値>目的値 であれば前半を
中央値<目的値 であれば後半を探します。
ハッシュ法 O(1)
事前にハッシュ表に登録しておく必要がある。
ハッシュ関数を用いて
格納場所のアドレスを計算して、目的の値を探します。
線形探索
先頭要素から順に探します。
二分探索
データを昇順に整列させておく必要があります。
最小値と最大値の平均から中央値を算出する。
そこから前半と後半を分けて探索
仮に後半にあれば同様に分けて再探索
要は、中央値を求めて半分削って行って探索する方法です。
ハッシュ法
データの格納場所を計算によって決める方法です。
ハッシュ関数
データの格納場所を求める計算式
ハッシュ法により衝突(コリジョン)
異なったキーに大して、同じハッシュが計算されること
シノニム
後から、同じハッシュとして計算されたハッシュのこと
下記の方法で処理がされます。
- オープンアドレス法: 空き領域に格納
- チェーン法: 同じハッシュの値をリストで管理する方法
⑤整列
データを並べ替えるアルゴリズムについてです。
整列アルゴリズム
下記のようなものがあります。
交換法 O(n2)
隣同士を比較して
順序が逆であれば入れ替えます。
選択法 O(n2)
最大値、最小値を順じ取り出す。
挿入法 O(n2)
整列済み要素の適切な位置に
未整列要素を挿入する処理を繰り返します。
クイックソート O(nlog n)
基準値よりも大きなグループと
小さいグループに分ける。
その後同様の処理を繰り返します。
二分法に近い形です。
マージソート O(nlog n)
整列済みの二つの配列を併合することを
繰り返します。
配列データの2分の1を格納する作業領域が必要です。
シェルソート O(n 1.25)
挿入法の改良版
一定間隔ごとに整列し、感覚を徐々に狭めながら再度整列を繰り返します。
ヒープソート O(nlog n)
ヒープの根を取り出して、ヒープを再構築することを繰り返します。