リスト構造のポイント【プログラミングの午後問題・出る順14位・応用情報技術者試験】

 

■出る順14位のリスト構造

 

情報処理教科書 出るとこだけ!応用情報技術者[午後]』によると、

選択分野:プログラミング
の中では、
配列に次ぐ出題頻度で、
図や処理を理解する読解力、トレース力が必要となる分野のようです。

 

■出る順14位のリスト構造のポイント

情報処理教科書 出るとこだけ!応用情報技術者[午後]

の出る順14位「リスト構造」

 の内容を参考に、覚えるべきポイントを以下に記載します。

① リスト構造、ノード、参照、nullとは。

▼リスト構造
 データの個数が増減する場合に適したデータ構造で、
ノードの中にデータと次ノードの参照を示すポイントが含まれる。

▼ノード
ノードとは、節点などの意味を持つ英単語。ITの分野では網状構造の構成要素をこのように呼ぶ。点と線で構成図を書いたときの点の部分を意味する。

▼参照
ノード自体でなく、ノードの存在する場所を示す情報である。

▼null
値が格納されてないことを意味する値


② 配列とリスト構造の違いは。

 配列とリスト構造も、プログラムで利用されるデータの格納方法であるが、
配列は、目的のデータにすぐに到達できるのが特徴で、リスト構造は、データを追加、削除しやすいのが特徴である。

▼配列は、目的のデータにすぐに到達できるという点の解説
 配列は、例えば「array[5]」と記述できる。この場合、添字を使って、目的のデータへとすぐ到達できる。 リスト構造は、先頭や末尾からノードを1つずつたどらないと目的のデータに到達できない。


▼リスト構造は、データを追加、削除しやすいという点の解説
 配列はデータが満杯で、新しいデータを追加する場合、元の配列より、新しい大きな配列を作成して、元の配列のデータを新しい配列にコピーする手順が必要である。

 データの追加、削除について、配列とリスト構造の違いは、以下の通りです。
 配列は、新しくデータを追加する場合、時間と負荷がかかるので、配列はデータの追加、削除には適さない。
 リスト構造は、新しくデータと追加、削除する場合、参照を変更するだけでよい。
つまり、リスト構造は、データの追加、削除に適したデータ構造である。

 

③ 先頭に新しいノードを追加する場合の処理を図で示せ。

先頭に新しいノードを追加する場合の処理

先頭に新しいノードを追加する場合の処理

④ 末尾の次に、新しいノードを追加する場合の処理を図で示せ。

末尾の次に、新しいノードを追加する場合の処理

末尾の次に、新しいノードを追加する場合の処理

⑤ 先頭から末尾へ先頭ノードを削除する場合の処理を図で示せ。

先頭から末尾へ先頭ノードを削除する場合の処理

先頭から末尾へ先頭ノードを削除する場合の処理

⑥ 先頭から末尾へ先頭ノード以外を削除する場合の処理を図で示せ。

先頭から末尾へ先頭ノードを削除する場合の処理

先頭から末尾へ先頭ノードを削除する場合の処理

⑦ 末尾から先頭へ末尾ノードを削除する場合の処理を図で示せ。

末尾から先頭へ末尾ノードを削除する場合の処理

末尾から先頭へ末尾ノードを削除する場合の処理

⑧ 末尾から先頭へ、末尾ノード以外を削除する図を示せ。

末尾から先頭へ、末尾ノード以外を削除する図

末尾から先頭へ、末尾ノード以外を削除する図

⑨ O記法と計算量について説明せよ。

 O記法とは計算量を表すための表記法で、計算量とはアルゴリズムの評価指標の一つで、「処理対象のデータ量の増加に伴って、処理の回数がどれだけ増加するか」を示す指標です。

 計算量は、プログラムの処理回数そのものでなく、データの量が増加した場合、
何に比例して、処理の回数が増加するかを示す。
例えば、データが増加しても処理の回数が一定であれば、0記法ではO(1)と表し、
処理の回数などデータ量nに正比例であれば、0記法では0(n)と表す。

 

代表的な0記法の例と説明は、次の通りです。

▼0(1)
データ量が増加しても、処理の回数は一定である。例えば、偶数奇数を判別する場合、
1で割った余りが0なら偶数、そうでないなら奇数のため、
データ量が増加しても1回の処理で結果が得られる。

▼0(n)
 データの量の増加に正比例して、処理の回数などが増加する。例えば、線形探索法で
n個のデータを探索した場合、データ量(要素数)が10(n=10)なら平均10回、要素数が20(n=20)なら平均20回の処理により探索できる。

▼0(n2)
 データ量の2乗に比例して、処理の回数が増加する。
例えば、挿入ソートで、n個のデータを並び替えする場合、データ量(要素数)が10なら平均100回(102)、要素数20なら平均400回(202)の処理で整理できる。
 データ量が増えると、計算量は加速度的に増える。

0記法は、計算量を表すため、値が変動しない定数を無視して表記する。

0(n+2)の場合は +2は無視して、O(n)を表記するし、0(0.5n)のうち、定数0.5は無視して0(n)と表記する。

■参考書の紹介

午後問題を出る順に効果的な試験対策ができる良書かなと思っています。

基本情報技術者試験も、同じシリーズの参考書で勉強して、苦手な午後問題を克服して合格しました。

 

情報処理教科書 出るとこだけ!応用情報技術者[午後]

情報処理教科書 出るとこだけ!応用情報技術者[午後]

  • 作者:橋本 祐史
  • 発売日: 2019/01/16
  • 「『応用情報の午後』は試験範囲が幅広く、どの分野・テーマを学習したらよいかわからない」と困っている方も多くいることと思います。応用情報の午後は、11問中5問に解答する形式ですが、多くの選択肢があるようで、受験生を惑わせることにもなります。

    そこで、本書では、徹底した分析と対策授業の経験などをもとに「出る順」で「出るところだけ」を厳選して掲載しました。本書で学ぶことにより、効率よく午後試験に合格する力が身に付けることができます。

     

  • 【本書の特徴】
    ・「出る順」に「出るところだけ」掲載。効率よく学習できる
    ・午後問題に合格するために「17のテーマ」に厳選して収録
    ・1つのテーマは、前提知識+解き方+過去問の順で丁寧に解説
    ・ベテランの現役講師による鋭い分析とわかりやすい説明で合格力養成

    【対象読者】
    応用情報技術者の午前試験の学習が一通り終わった人
    ・午後試験の学習の仕方が分からない人
    ・短期間で午後試験の対策をしたい人

 

■関連ブログ

chanmabo.hatenablog.com

 

 以上です。