アルゴリズムとプログラミングの要点とまちがえやすい点（ITパスポート試験 論点テキスト）

このページの論点

テクノロジ系｜基礎理論｜13論点・要点75本・まちがえやすい点53本・式5本

• データ構造
  • スタックとキューの取り出し順序
  • 配列・連結リスト・木構造の特徴
• アルゴリズムとプログラミング
  • 制御構造・流れ図・再帰
  • 変数・定数・関数・注釈と擬似言語
  • 探索アルゴリズムと比較回数
  • 整列アルゴリズムの方式
  • 繰返しの回数と合計・積の計算
  • 条件分岐の境界と多分岐の判定
  • 配列の走査と最大値・位置・連結
  • 値の入替え・進数変換・関数呼出し
• プログラム言語
  • 言語処理方式とスクリプト言語
  • ライブラリ・ローコード開発・RPA
• その他の言語
  • マークアップ言語とデータ交換形式

データ構造

スタックとキューの取り出し順序

スタックとキューのデータの出し入れの規則と、各操作の名称を扱う。格納と取り出しを順に行ったときの取り出し順も問われる。

要点

• スタックは後入れ先出し(LIFO)の構造であり、直前に積んだデータから取り出す。
• キューは先入れ先出し(FIFO)の構造であり、先に入れたデータから順に取り出される。
• スタックからデータを取り出す操作はPOP、格納する操作はPUSHと呼ばれる。
• キューにデータを追加する操作はエンキュー(ENQUEUE)、取り出す操作はデキュー(DEQUEUE)と呼ばれる。
• スタックに1・2・3の順に格納すると、最後に格納した3が最上段になり、最初に取り出される。

まちがえやすい点

• キューは先入れ先出し(FIFO)であり、後入れ先出し(LIFO)のスタックとは、データを取り出す順序の扱いが逆である。
• PUSHとPOPはスタックの操作であり、キュー(待ち行列)の操作であるENQUEUEとDEQUEUEとは用語が異なる。
• キューを後入れ先出しの規則で説明した記述は誤りであり、後入れ先出しはスタックの規則である。

配列・連結リスト・木構造の特徴

配列、連結リスト、木構造それぞれの構造と得意な操作、および木構造で使う用語と二分木の走査順を扱う。

要点

• 配列は各要素がメモリ上に連続して確保され、添字を指定することで目的の要素へ直接アクセスできるデータ構造である。
• 連結リストは各要素がポインタで次を指すため、途中の挿入・削除は付け替えだけで済むが、n番目へは先頭からたどる必要がある。
• 木構造では、あるノードの直下に連なるノードを子(チャイルド)と呼び、根から葉へ枝分かれする階層構造をなす。
• 葉(リーフ)は子ノードを持たない末端のノードであり、根(ルート)は最上位に位置して親を持たないノードである。
• 二分木を左部分木、自分自身のノード、右部分木の順にたどる走査方法を、通りがけ順(中間順)と呼ぶ。
• 2分木は、木構造のうち、各ノード（節点）の子が最大で2つに限られるもの。

まちがえやすい点

• 配列は添字で即アクセスできる反面、途中への挿入では後続要素の移動が必要であり、挿入・削除が容易な連結リストとは異なる。
• 次の要素への参照をたどってアクセスする方式は連結リストの特徴であり、配列の基本的な特徴ではない。
• 根は木構造の最上位のノード、葉は子を持たない末端のノードであり、直下に連なる子とは位置関係が異なる。

アルゴリズムとプログラミング

制御構造・流れ図・再帰

処理の流れを表す基本の制御構造、流れ図の記号の意味と分岐の読み方、自分自身を呼び出す再帰を扱う。

要点

• フローチャート(流れ図)は、処理・判断・端子などの標準化された記号を用いてプログラムの処理手順を図式化したものである。
• 流れ図ではひし形が条件による分岐(判断)を表し、長方形が通常の処理、平行四辺形がデータの入出力、だ円(端子)が開始・終了を表す。
• 構造化プログラミングは、処理の流れを順次、選択(分岐)、反復(繰り返し)という3つの基本的な制御構造の組合せだけで記述できるとする考え方である。
• 再帰は、関数や処理が自分自身を呼び出す形で定義される方式であり、階乗の計算や木構造の探索などを簡潔に記述できる。
• 流れ図の判断条件がx≧60のように等号を含む場合、境界の60はその条件に当てはまり、「はい」の側へ進む。
• ネストの深さは、条件分岐や繰返しが入れ子になっている重なりの程度。深くなるほどプログラムが読みにくくなる。
• メインルーチンは、プログラムの実行の起点となり、必要に応じてサブルーチンなどを呼び出して全体の流れを進める部分。

まちがえやすい点

• データフロー図はデータの流れと処理の関係、UML状態遷移図は状態とその変化を表す図であり、処理手順を記号で追うフローチャートとは表現対象が異なる。
• 反復処理はループによる繰り返し、例外処理はエラー発生時の処理であり、自分自身を呼び出す再帰とは別である。
• 「より大きい」と「以上」は別の条件であり、取り違えると境の値である60で答えが変わる。
• オブジェクト指向設計はデータと手続きをまとめる考え方であり、3つの基本制御構造を主眼とする構造化プログラミングとは異なる。

変数・定数・関数・注釈と擬似言語

変数の有効範囲、定数、関数の引数と戻り値、注釈、擬似言語といった、アルゴリズムを記述するときの基本用語を扱う。

要点

• スコープ(有効範囲)は変数が参照・更新できるコード上の範囲であり、関数内だけで有効なローカル変数と全体で有効なグローバル変数がある。
• 関数を呼び出す際に渡す入力値を引数といい、その関数の処理結果として呼び出し元に返される値を戻り値という。
• 定数はプログラム中で一度値を設定すると実行中に変更できないものであり、変更してはいけない値を明示する目的で使われる。
• コメント(注釈)はソースコード中に書かれる説明文で、実行の対象とはならず、人が読むことを目的として記述される。
• 疑似言語(擬似コード)は特定のプログラム言語の文法にとらわれず、アルゴリズムの処理手順を人が読みやすい形式で表現する記述方法である。
• プログラムの式は、定数や変数、関数の呼出しなどを演算子でつなぎ、評価すると一つの値になるもの。
• 演算子は、加算や大小比較など、式の中で値に対して行う演算の種類を表す記号。
• 代入は、変数に値や式の計算結果を格納し、以降の処理で使えるようにする操作のこと。
• 字下げは、行頭に空白を入れて文の位置をずらし、条件分岐や繰返しの範囲を見やすくする書き方。

まちがえやすい点

• 変数は実行中に値を変更できるものであり、一度設定すると変更できない定数とは異なる。
• リテラルはソースコードに直接書かれた値、識別子は変数や関数に付ける名前であり、いずれも説明文であるコメントとは異なる。
• データ型は変数が扱う値の種類、ポインタはメモリ上の番地を保持する変数であり、変数の有効範囲を表すスコープではない。
• 入力として渡す引数と、処理結果として返す戻り値の役割を入れ替えて説明した記述は、関数の説明として誤りである。
• 機械語はCPUが直接実行する命令、バイトコードや中間言語は変換された中間的な表現であり、人が読みやすい擬似コードとは異なる。

探索アルゴリズムと比較回数

線形探索、2分探索、ハッシュ法の仕組みと前提条件、データ件数に応じた比較回数の見積もり、ハッシュ法の衝突を扱う。

要点

• 線形探索は先頭から順に1件ずつ照合していく最も基本的な探索方法であり、整列の有無にかかわらず利用できる。
• 2分探索は探索範囲を中央値と比較しながら半分ずつ絞り込む方式であり、対象データがあらかじめ整列されていることが前提となる。
• ハッシュ法はキーをハッシュ関数で計算した結果を格納場所として直接利用するため、データ量が増えてもほぼ一定時間で検索できる。
• 異なるキーが同じ格納位置に対応する現象を衝突(コリジョン)といい、同じ位置に複数データをつなぐチェイン法などで対処する。
• 1024件の整列済みデータを2分探索すると、探索範囲を毎回半分にするため、最悪でも10回程度の比較で目的のデータに到達できる。
• 目的のデータが確実に存在する100件を線形探索すると、平均比較回数はデータ件数の約半分である約50回になる。

まちがえやすい点

• 2分探索は整列済みデータが前提となる点で、整列の有無にかかわらず使える線形探索とは異なる。
• 線形探索の100回は最悪の場合の比較回数であり、目的のデータが存在する場合の平均である50回ではない。
• 線形探索と2分探索はいずれもハッシュ関数による直接計算を行わず、格納場所を直接求めるハッシュ法とは別である。
• オーバーフローは桁あふれ、デッドロックは資源待ちの膠着状態であり、異なるキーが同じ位置に対応する衝突とは別の概念である。

式

• 線形探索の平均比較回数データ件数÷2目的のデータが存在する場合
• 2分探索の最悪の比較回数比較回数＝log2(データ件数)1024件なら10回程度

整列アルゴリズムの方式

バブルソート、選択ソート、クイックソート、マージソートの整列の進め方と、併合の考え方の違いを扱う。

要点

• バブルソートは隣り合う2つの要素を比較し、大小関係が逆であれば交換する処理を繰り返してデータを整列させる。
• クイックソートは基準値(ピボット)を選び、それより小さい値のグループと大きい値のグループに分割する操作を再帰的に繰り返して整列する。
• マージソートはデータを分割できない単位まで分割し、整列を保ちながら2つずつ統合(マージ)していく分割統治法に基づくアルゴリズムである。
• 選択ソートは未整列の範囲から最小値(または最大値)を探し、整列済み範囲の末尾の要素と入れ替える操作を繰り返す。
• 併合(マージ)は、すでに整列済みの複数のデータ列を、順序を崩さずに1つのデータ列へまとめる処理である。
• 4, 2, 5, 1の並びに対し、隣り合う2つを先頭から1回ずつ比べて逆順なら入れ替える処理を1周行うと、2, 4, 1, 5になる。

まちがえやすい点

• 基準値で振り分けるのはクイックソート、最小値を選んで交換するのは選択ソート、分割してから併合するのはマージソートであり、隣り合う要素を交換するバブルソートとは別である。
• 挿入ソートは整列済みの列に1つずつ要素を適切な位置へ挿入する方式であり、最小値を末尾と入れ替える選択ソートとは異なる。
• 二分探索・深さ優先探索・幅優先探索はいずれも探索アルゴリズムであり、整列を目的とするバブルソートとは目的が異なる。
• 基準値で2組に振り分けるのはクイックソートの分割、目的の値の位置を見つけるのは探索であり、整列済みの列をまとめる併合とは目的が異なる。
• 1, 2, 4, 5は何周も繰り返して整列が完了した場合の並びであり、1周しか行わない手続きの結果ではない。

繰返しの回数と合計・積の計算

繰返しの範囲と回数、初期値の置き方、入れ子の繰返しの回数、合計や積を求める処理の追い方を扱う。

要点

• 入れ子になった繰返しの回数は、外側の繰返しの回数と内側の繰返しの回数の積になる。
• 掛け算を積み上げる処理では初期値を1にする必要があり、0にすると結果が常に0になる。
• 合計を求める処理では、初期値を0にすることと、要素番号の範囲を配列の大きさと一致させることが必要である。
• 平均を求める処理では合計を要素数で割り、割る数が配列の要素数と一致していることを確かめる必要がある。
• while文は条件が成り立つ間だけ繰り返すため、繰返しを抜ける条件の境界によって処理の回数が決まる。
• 直前の2つの値を足していく並びはフィボナッチ数列と呼ばれ、繰返しの回数を1回でも取り違えると答えがずれる。

まちがえやすい点

• 積を求める処理の初期値を0にすると結果が常に0になってしまい、初期値を0とする合計の処理とは異なる。
• どちらか一方の繰返し回数だけを数えても、入れ子の繰返しの総回数にはならない。
• 繰返しの上限を読み違えると結果がずれ、iが4までなら20になるところ、5までと読み違えると30となり、答えが異なる。
• 4回繰り返したときのbの値は8であり、3回めの5や5回めの13ではない。

式

• 入れ子の繰返しの総回数外側の回数×内側の回数3回と4回なら12回
• 平均合計÷配列の要素数合計300を要素数4で割ると75

条件分岐の境界と多分岐の判定

条件式の境界、多分岐で上から順に調べる規則、条件を満たす個数の数え方、フラグによる判定を扱う。

要点

• 1から5までの繰返しの中で偶数のときだけ加算すると、足されるのは2と4だけで、合計は6になる。
• 多分岐では条件が上から順に調べられ、最初に成り立ったものだけが実行される。
• 金額が20000以上か10000以上かで割引率を変える処理では、最初に当てはまる条件の割引額を金額から引いて支払額を求める。
• 配列から条件を満たす要素の個数を数える処理では、条件が成り立つたびに常に1を加算する。
• 条件を満たす要素が一つもなければフラグは初期値のまま変わらず、最後の分岐でelse側に進む。

まちがえやすい点

• 75は60以上という三つ目の条件にも当てはまるが、二つ目の条件で分岐が確定するため、三つ目へは進まない。
• 2は10未満の要素の個数、5は配列の要素数そのものであり、10以上の要素の個数である3ではない。
• 10200は15%の割引を当てはめた値、1200は割引額そのものであり、支払額の10800とは別である。
• 出力は繰返しの外で1回だけ行われるため、3回出力されることはなく、else側があるため何も出力されないこともない。
• 15は1から5までを全て足した値であり、条件分岐を無視した場合の答えで、偶数だけを足した6とは異なる。

式

• 割引後の支払額支払額＝金額－金額×割引率12000円に割引率0.1なら10800

配列の走査と最大値・位置・連結

配列の要素番号と走査の向き、最大値を求める処理、位置の記録、文字列の連結順を扱う。

要点

• 最大値を求める処理では、先頭の要素を仮の最大値として置き、2番目以降の要素と順に比べて大きければ入れ替える。
• 繰返しの変数が4から1まで1ずつ減る場合、配列の要素はA[4]、A[3]、A[2]、A[1]の順に、後ろから前へ向かって取り出される。
• 配列から条件に合う値の位置を記録する処理で、見つかっても繰返しを抜けない場合は、あとから見つかった位置で上書きされて残る。
• 文字列の連結では、どの順にまわるかと、前と後ろのどちらにつなぐかの二つで結果が決まる。

まちがえやすい点

• 2は最初に見つかった位置であり、見つけた時点で繰返しを抜ける書き方にした場合の結果で、あとから見つかった位置を残す4とは別である。
• 一度も見つからなかった場合の値は0であり、3は位置ではなく探している値そのものである。
• 増やす向きと読み違えると1, 2, 3, 4になり、最後の1を含めないと読み違えると4, 3, 2になり、正しい出力順とは異なる。
• 3は一度も入れ替えが起きないと読み違えた値、8は9と比べる前で繰返しが終わると読み違えた値であり、最大値の9ではない。
• ITPは元の並びそのものであり、増やす向きと読み違えた場合の結果で、減らす向きの結果であるPTIとは別である。

値の入替え・進数変換・関数呼出し

作業用変数による値の入替え、余りと商を使う変換や最大公約数の手続き、関数の呼出しの追い方を扱う。

要点

• 2つの変数の値を入れ替えるには、作業用の変数に一方の値をいったん退避してから、もう一方の値を代入する。
• 10進数を2進数に変換する手続きでは、2で割った余りを求めた順に前へ付け足していくと、変換結果が得られる。
• bが0になるまで余りを使って値を更新していく手続きは最大公約数を求めるもので、48と18では6になる。
• 関数は呼び出すたびに引数の値で計算され、returnで返した値がその呼出しの場所に置き換わる。

まちがえやすい点

• 退避を行わずにxにyを、yにxを代入すると、先に上書きされた値が失われ、2つの値は入れ替わらない。
• 1011は余りを求めた順に後ろへつないだ値であり、前へ付け足した結果である1101とは異なる。
• 2と3は48と18に共通する約数ではあるが最大ではなく、最大公約数である6ではない。
• 60は2つの呼出し結果を足さずに掛けた値であり、足した結果である22とは別である。

プログラム言語

言語処理方式とスクリプト言語

ソースコードを機械語にして実行する方式の違い、低水準言語、コンパイルの手間を要さないスクリプト言語の位置づけを扱う。

要点

• コンパイラ方式は、ソースコード全体を事前に機械語などに一括翻訳してから実行する方式で、実行速度に優れる。
• インタプリタ方式はソースコードを一命令ずつ解釈しながら逐次実行する方式で、一般にコンパイラ方式より実行速度は遅いが、修正と実行を手軽に繰り返せる。
• スクリプト言語は、あらかじめコンパイルする手間を必要とせず、比較的簡易な記述で処理を実行できるプログラム言語の総称である。
• 低水準言語は機械語やアセンブリ言語のように機械の動作に近い言語であり、人間の言葉に近いのは高水準言語である。
• C言語は、ハードウェアに近い処理を記述でき、OSの開発にも使われてきた手続型のプログラム言語。
• Fortranは、数値計算や科学技術計算の分野で古くから使われてきたプログラム言語。
• C++は、C言語にオブジェクト指向の機能などを加えて拡張した、システム開発などに使われるプログラム言語。
• R言語は、統計解析やグラフ作成のための機能が充実した、データ分析の分野で広く使われるプログラム言語。

まちがえやすい点

• アセンブラ方式はアセンブリ言語を機械語に変換する処理、リンカは複数の目的プログラムを結合する処理であり、インタプリタ方式ではない。
• アセンブラはアセンブリ言語を機械語に変換するプログラムであり、1文ずつ解釈しながら実行する方式を指す語ではない。
• アセンブリ言語は機械語と対応した低水準言語、機械語はCPUが直接実行できる命令の集合であり、スクリプト言語とは別である。
• インタプリタ方式は1行ずつ解釈しながら実行する方式であり、翻訳の単位とタイミングがコンパイラ方式とは異なる。

ライブラリ・ローコード開発・RPA

処理を再利用する部品集であるライブラリ、コード記述を抑える開発手法、事務作業を自動化するRPAの役割を扱う。

要点

• ライブラリは、よく使う処理をあらかじめプログラム部品として用意し、複数のプログラムから呼び出して再利用できるようにしたものである。
• ローコード・ノーコード開発は、部品の組合せなど視覚的操作を中心に、コード記述を最小限にして開発する手法である。
• RPAは、データの転記や集計といった人手で行っていたパソコン上の定型的な事務作業を、ソフトウェアロボットに代行させて自動化する技術である。

まちがえやすい点

• コンパイラは機械語に翻訳するソフトウェア、デバッガは誤りを見つける開発支援ツールであり、再利用できる処理の部品集であるライブラリとは別である。
• アジャイル開発は反復的な開発手法、ペアプログラミングは2人一組の開発であり、視覚的操作を中心とするローコード・ノーコード開発とは異なる。
• IoTは「モノ」をインターネットに接続する技術であり、人手の事務作業を自動化するRPAとは自動化の対象が異なる。

その他の言語

マークアップ言語とデータ交換形式

HTML、XML、CSS、JSON、JavaScriptそれぞれの役割と表記の特徴、および文書の構造と見た目の分離を扱う。

要点

• HTMLは、見出しや段落などの文書構造をタグで記述するマークアップ言語で、Webページの作成に用いられる。
• JSONは、キーと値の組を波括弧や角括弧で表す軽量なデータ交換形式で、Web APIなどで広く使われる。
• XMLは、利用者が目的に応じて独自にタグを定義でき、データの構造や意味を表現できる汎用のマークアップ言語である。
• CSSは、HTMLで表した文書構造とは別に、文字色やレイアウトなどの見た目をまとめて指定する仕組みである。
• HTMLが文書の構造、CSSが見た目、JavaScriptが動きを担う役割分担により、内容を変えずに見た目だけを差し替える保守がしやすくなる。
• SGMLは、文書の構造をタグで記述するための国際規格で、HTMLやXMLの元になったマークアップ言語。

まちがえやすい点

• XMLもタグでデータを表現できるが記述量が多くなりやすく、軽量なデータ交換形式であるJSONとは特徴が異なる。
• HTMLはあらかじめ定義されたタグでWebページの構造を表す言語であり、利用者が独自にタグを定義できるXMLとは異なる。
• PythonやC言語はプログラム言語、SQLはデータベース操作言語であり、文書構造を記述するマークアップ言語とは分類が異なる。
• JSONはデータ交換形式、XMLはデータ記述用のマークアップ言語、URLはリソースの所在表記であり、見た目を指定するCSSではない。

ほかのページ

出典と作り方

この読み物は、IPA「ITパスポート試験 シラバス Ver.6.5」の中分類の順に、アプリ「ITウカール」の収録問題の解説をもとにアプリ製薬が作成したものです。公式の文章の転載ではありません。問題文・選択肢は載せていません。

• ITパスポート試験 シラバス Ver.6.5（IPA）