プログラミング技法 定期テスト対策（全範囲・過去問全問解説）

試験情報

• 前期定期試験。100点満点・合格ライン60点。配点は小問ごとに問題用紙に明記される。

• 参照物件は電卓のみ（直近2回）。教科書・ノートは持ち込めない。二分法・ニュートン法・数値積分の手計算があるので電卓は必ず持って行く。

• 試験時間は90分。大問6題。問題用紙とは別に解答用紙（表形式）が配られ、空欄記号ごとに「語句」「式」「C言語の1行」を書き込む形式。

• 出題テーマは3回分を並べるとほぼ固定されている。下の地図で3回とも出ているテーマから手をつける。

• このプリントが解説している過去問は3回分・全55問。 令和4年度 前期期末試験（100点満点・合格60点・参照物件なし）、 令和6年度 前期定期試験（電卓可）、 令和7年度 前期定期試験（100点満点・合格60点・電卓可）。 どの問題がどの過去問かは、次ページの「過去問対応表」と各問題箱の先頭の「出題：」に書いてある。

• プログラムは問題用紙に印刷されて配られる。暗記する必要はないが、空欄1行を自分で書けることが要求される。

出題テーマの地図

出題テーマ	出題された年度	解説する節
ビルドの4工程とファイルの種類	令和4・6・7	第I部
#include の " " と < >、ヘッダに書く内容	令和4・6・7	第I部
変数の有効範囲（大域・局所・static・extern）	令和4・6・7	第II部
構造体・typedef・動的メモリ確保（calloc／free）	令和4	第III部
スタック（トレース＋配列実装）	令和4・6・7	第IV部
キュー（トレース＋配列実装）	令和7	第V部
連結リスト（挿入・削除・降順ソート挿入）	令和4	第VI部
浮動小数点数の誤差（== で比較すると止まらない）	令和7	第VII部
二分法	令和7	第VIII部
ニュートン・ラプソン法	令和6	第VIII部
数値積分（台形則）	令和6・7	第IX部

3回とも出ているテーマ（第I部・第II部・第IV部）は必ず出ると考えてよい。 1回だけのテーマも、テーマ自体は3回で一巡している（データ構造はスタック→連結リスト→キュー、 数値計算はニュートン法→二分法と入れ替わっている）ので、どれが来ても書けるようにしておく。

答案の型は4つだけ

• 型A：語句を答える／選ぶ ビルド用語、#include の動作、スコープの範囲、static の利点。1行で言い切る。

• 型B：手で追って表・図を埋める スタック／キューの状態、二分法・ニュートン法の反復表、台形則の区間面積。電卓で検算する。

• 型C：プログラムの空欄に1行書く セミコロンまで含めて書く。ここが最大の配点（1問6〜15点）。

• 型D：誤りを見つけて直す 手順の順序の誤り、右上がり限定の条件判定。「どちらが誤り」＋「正しい手順」の2点セットで書く。

過去問対応表（3回分・全55問）

令和4年度 前期期末試験（100点満点・合格ライン60点・参照物件なし）

問題番号	問われている内容	配点	解説する節
問1	ビルド過程の文章穴埋め（語群13個から7つ選ぶ）	各2点	第I部
問2(1)	スタックの pop で取り出される順番	3点	第IV部
問2(2)	配列で表した連結リストに入っている文字列	3点	第VI部
問3(1)	#include"data.h" の動作	3点	第I部
問3(2)	data.h に入るべき内容	5点	第I部
問3(3)	ポインタ p が受け取る値	3点	第III部
問3(4)	calloc の返り値	3点	第III部
問3(5)	make の空欄 (A)(B)(C)	6点	第III部
問3(6)	del の内容	2点	第III部
問4(1)	大域変数 x,y の有効範囲	3点	第II部
問4(2)	実行例の (A)(B)	4点	第II部
問4(3)	// y = 0; のコメントを外した場合の (A)(B)	4点	第II部
問4(4)	修正後の func の x の有効範囲	3点	第II部
問4(5)	func の空欄 (a)(b)	6点	第II部
問5(1)	struct cell と別名 CELL の定義	4点	第VI部
問5(2)	空のリストの図	4点	第VI部
問5(3)	add_cell／del_cell の空欄 (A)〜(G)	14点	第VI部
問6(1)	23 と 1 を降順に挿入した後のリストの図	4点	第VI部
問6(2)	sort_list の空欄 (A)〜(D)	12点	第VI部

令和6年度 前期定期試験（参照物件は電卓）

問題番号	問われている内容	配点	解説する節
問1	ビルド用語5つと説明（ア）〜（オ）の対応づけ	10点	第I部
問2(1)	#include"problem.h" の動作（" " の意味も含める）	4点	第I部
問2(2)	problem.h に入る内容をコードで示す	6点	第I部
問2(3)	構造体 A・B のスコープ	6点	第II部
問2(4)	プログラムの実行結果（8行）	4点	第II部
問3(1)	スタックの変化の様子	6点	第IV部
問3(2)	pop で取り出される順番	4点	第IV部
問4(1)	プログラム開始時点の top	3点	第IV部
問4(2)	push(20) 直後の top と配列 stack	4点	第IV部
問4(3)	2回目の pop() 直後の top と配列 stack	4点	第IV部
問4(4)	実行結果の (A)	4点	第IV部
問5(1)	ニュートン法の図の空欄 (a)〜(c)	3点	第VIII部
問5(2)	$x_n$ と $x_{n+1}$ の関係式	4点	第VIII部
問5(3)	$f(x)=x^2+2x-8$ をニュートン法で2回反復	4点	第VIII部
問5(4)	プログラム3の空欄 (A)〜(E)	15点	第VIII部
問6(1)	長方形の平均で台形則を導く文章の空欄 (a)〜(d)	8点	第IX部
問6(2)	プログラム4の空欄 (A)(B)(C)	9点	第IX部

令和7年度 前期定期試験（100点満点・合格ライン60点・参照物件は電卓）

問題番号	問われている内容	配点	解説する節
問1	ビルド過程の文章穴埋め（令和4年度 問1と同一問題）	各2点	第I部
問2(1)	x += 0.1 のループがどのような動作をするか	4点	第VII部
問2(2)	なぜそのような動作をするのか	4点	第VII部
問3(1)	スタックの pop で取り出される順番	4点	第IV部
問3(2)	キューの get で取り出される順番	4点	第V部
問4(1)	$f(x)=x^2+x-6$ を二分法で2回反復し表を埋める	4点	第VIII部
問4(2)	プログラム4の空欄 (a)〜(f)	12点	第VIII部
問4(3)	右下がりでも動くように条件判定を修正	4点	第VIII部
問5(1)	台形の面積で書く文章の空欄 〜	8点	第IX部
問5(2)	$f(x)=-x^2+1$、区間 $[0,0.2]$、分割数2の積分値	4点	第IX部
問5(3)	$x_3$ を $x_1$ と $\Delta x$ で表す	4点	第IX部
問5(4)	プログラム5の空欄 (a)〜(d)	8点	第IX部
問6(1)	#include"queue.h" の動作	4点	第I部
問6(2)	queue.h に入るべき内容	4点	第I部
問6(3)	queue・tail のスコープ	4点	第II部
問6(4)	static を用いることのメリット	4点	第II部
問6(5)	誤った手順で put(10)／get した後のキュー	4点	第V部
問6(6)	put・get のどちらが誤りか・正しい手順	4点	第V部
問6(7)	関数 put と get を完成させる	6点	第V部

• 配点は問題用紙に印刷されている数字をそのまま写した。年度によってはヘッダの満点表記と各問の配点の合計が一致しないので、当日は問題用紙の配点を見て解く順番を決める。

• 配点が10点を超える小問は必ず「プログラムの空欄埋め」（令和4 問5(3) 14点・問6(2) 12点、令和6 問5(4) 15点、令和7 問4(2) 12点）。ここを落とすと合格ラインに届かないので、コードを1行書く練習を最優先にする。

• 令和4年度と令和7年度の問1は文章・語群・図まで完全に同じ。ビルド用語は確実に14点取れるので最初に固める。

直前チェック：用語・公式チートシート

プリプロセス	#include・#define を展開する。機械語へ翻訳する前の事前処理。
コンパイル	ソースコードを CPU が理解できる言語に変換する操作。→ オブジェクトファイル
アセンブル	アセンブリ言語を機械語に変換する操作（試験の文章ではコンパイルにまとめられている）。
リンク	変換済みのファイル同士や、ライブラリの関数を接続する操作。→ 実行ファイル
ソースファイル	C言語のプログラムが記述されているファイル（.c）
ヘッダファイル	複数のソースで共有する宣言を書くファイル（.h）。#include で読み込む
オブジェクトファイル	CPU が理解できる言語に変換したファイル（.o／.obj）。ファイル間の関数の連結がまだなので実行できない
ライブラリ	あらかじめ用意された関数の集まり（printf など）。リンクで結合される
実行ファイル	全ての処理を終え、PC が実行できる形式のファイル（.exe）

書き方	有効範囲（スコープ）	寿命
関数の中で int x;	その関数の中だけ（局所変数）	関数を抜けると消える
関数の中で static int x;	その関数の中だけ	プログラム終了まで残る（値が次の呼び出しに持ち越される）
関数の外で int x;	プログラム全体（他ファイルからも extern で使える）	プログラム終了まで
関数の外で static int x;	宣言したファイルの中だけ	プログラム終了まで
extern int x;	「他のファイルにある大域変数を使う」という宣言（実体は作らない）	—

	スタック（LIFO）	キュー（FIFO）
追加・取出の名前	push／pop	put（enqueue）／get（dequeue）
出る順番	後から入れたものが先に出る	先に入れたものが先に出る
位置を覚える変数	top（今の一番上）	tail（次に入れる空き位置）
空の目印	top = -1	tail = 0
追加の手順	top++; → stack[top] = dat;	queue[tail] = dat; → tail++;
取出の手順	ret = stack[top]; → top–;	ret = queue[0]; → 全体を前へずらす → tail–;
イメージ	積み重ねた本	レジの待ち行列

二分法（中点）	$c=\frac{a+b}{2}$
二分法（区間更新）	$f(a)\cdot f(c)<0$ なら $b\leftarrow c$、$f(b)\cdot f(c)<0$ なら $a\leftarrow c$
ニュートン法	$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$
終了条件（両方共通）	$\left
刻み幅と分点	$\Delta x=\frac{x_e-x_s}{n}$、$x_k=x_s+(k-1)\Delta x$（だから $x_3=x_1+2\Delta x$）
長方形近似	$S_{a1}=f(x_1)\Delta x$（左端）、$S_{b1}=f(x_2)\Delta x$（右端）
台形則（1区間）	$S_1=\frac{S_{a1}+S_{b1}}{2}=\frac{f(x_1)+f(x_2)}{2}\Delta x$
台形則（全体）	$S=S_1+S_2+\cdots +S_n=\sum _{k=1}^n{S}_k$

関数	書き方	返り値	初期化
malloc	(CELL*)malloc(sizeof(CELL))	確保したメモリの先頭アドレス（失敗なら NULL）	しない
calloc	(int*)calloc(n, sizeof(int))	同じ（$n$ 個ぶんまとめて確保）	0 で埋める
free	free(A.dat)	なし（確保した領域を返す）	—

第I部 ビルドと分割コンパイル

ビルドの流れ

ビルド： 人間が書いたソースファイルを、PC がそのまま動かせる実行ファイルに変える一連の作業。 1つの操作ではなくプリプロセス → コンパイル → リンクという段階を踏む。
分割コンパイル： プログラムを複数の .c ファイルに分けて書き、ファイルごとにオブジェクトファイルを作ってから最後にリンクでつなぐやり方。 1か所直したときにそのファイルだけコンパイルし直せば済むのが利点。共有したい宣言はヘッダファイル（.h）に書き、各 .c が #include する。

ビルドの過程を説明した文章の穴埋め（語群から選ぶ）

出題：令和4年度 問1／令和7年度 問1（各空欄2点＝14点）。2年とも文章・語群・図まで完全に同一。

以下の文章の空欄に入る語句を、下の語句一覧から選んで示せ。

プログラムが記述されている を実行可能な形式に変換するには、いくつかの処理が必要となる。図に示したように、 は、まず と呼ばれる処理を行なう。この処理は を機械語へ翻訳する前の事前処理を行う。

次に と呼ばれる処理を行なう。この時点でプログラムは機械語へ変換され が生成される。図のように が複数ある場合は、それぞれについて が生成される。この は機械語に変換されたものではあるが、ファイル間の関数の連結などが行われていないため、実行はできない。最後に と呼ばれる処理を行なう。ファイル間の関数の結合や の関数の結合が行われる。このような行程を経て、プログラムは となる。

語句一覧： A.オブジェクトファイルB.ライブラリC.データファイルD.コンパイルE.ニーモニックF.アセンブルG.データベースH.実行ファイルI.リファクタリングJ.オペレートK.ソースファイルL.プリプロセスM.リンク

方針： 文章を読む順ではなく、定義が言い切られている空欄から先に埋める。 「機械語へ翻訳する前の事前処理」＝プリプロセス、「実行はできない」＝オブジェクトファイル、「ファイル間の関数の結合」＝リンク、と決まり文句が対応している。 最後に残った は「このような行程を経て」＝ゴールなので実行ファイル。

空欄	答え	根拠になる語
		「プログラムが記述されている」
		「機械語に変換されたが実行はできない」
		「…や〈 〉の関数の結合」＝外部の関数の集まり
		「このような行程を経て」＝最終成果物
		「機械語へ翻訳する前の事前処理」
		「機械語へ変換され が生成される」
		「ファイル間の関数の結合」

• F.アセンブル は使わない。実際のビルドは「コンパイル → アセンブル」だが、この文章はコンパイルで機械語まで行くことになっているので、アセンブルを入れる空欄はない。「習った工程を全部使うはず」と考えて埋めると外す。

• C.データファイル・G.データベース・E.ニーモニック・I.リファクタリング・J.オペレートはすべてダミー。ニーモニックはアセンブリの命令の記号名、リファクタリングは動作を変えずにコードを整える作業で、どちらもビルドの工程名ではない。

• の空欄は3か所に同じ語が入る。1か所だけ違う語を入れないよう、埋め終わったら通して読み直す。

ビルド用語と説明の対応づけ

出題：令和6年度 問1（10点）。

プログラムのビルドに関連する以下の用語の説明で、適切なものを選択肢より選べ。

用語： A コンパイルB リンクC 実行ファイルD オブジェクトファイルE ソースファイル

選択肢：

• 変換済みのファイル同士や、ライブラリの関数を接続する操作

• ソースコードを CPU が理解できる言語に変換する操作

• CPU が理解できる言語に変換したファイル

• C言語のプログラムが記述されているファイル

• 全ての処理を終え、PC が実行できる形式のファイル

方針： 選択肢の末尾が「操作」か「ファイル」かで2グループに分かれる。 操作は（ア）（イ）の2つだけなので、まず操作の2つ（コンパイル・リンク）を決めてから残りのファイル3つを割り振る。

用語	答え	決め手
A コンパイル		「ソースコードを変換する」＝入口がソース
B リンク		「変換済みのファイル同士を接続」＝入口がオブジェクト
C 実行ファイル		「全ての処理を終え」＝一番最後
D オブジェクトファイル		「変換したファイル」＝コンパイルの出口
E ソースファイル		「C言語のプログラムが記述されている」

A（コンパイル）と B（リンク）を逆に書くのが最頻出の失点。見分け方は「何を入れるか」で覚える。 コンパイルに入れるのはソースコード、リンクに入れるのはもう変換が済んだファイル。 「接続する」という語が出てきたらリンク、「変換する」ならコンパイル、と1語で決めてよい。
（ウ）と（オ）も紛らわしい。（ウ）は変換しただけ＝まだつながっていない＝オブジェクト、（オ）は全部終わった＝実行ファイル。 「実行できるかどうか」が境目。

#include の2つの書き方とヘッダファイルの中身

#include はプリプロセスの命令で、動作は「指定したファイルの内容を読み込み、その行の場所にそのまま挿入する」。 コピー&ペーストを機械にやらせているだけで、それ以上のことはしない。

#include"data.h"	まずソースファイルと同じフォルダを探し、無ければ標準の場所を探す。自分で作ったヘッダに使う。
#include<stdio.h>	処理系（コンパイラ）が用意した標準のフォルダだけを探す。標準ライブラリのヘッダに使う。

書く（複数ファイルで共有したい宣言）	書かない（実体）
構造体の定義 struct Dat { …};	関数の本体（{ } の中身）
typedef による型の別名	変数の定義（int x;）
関数のプロトタイプ宣言 struct Dat make(int n, int *p);
#define によるマクロ

理由：ヘッダは#include した全ファイルに丸ごとコピーされる。実体をヘッダに書くと同じ関数・同じ変数が複数のオブジェクトファイルにでき、リンクのときに「二重定義」で失敗する。

#include の動作と、ヘッダファイルに入るべき内容

出題：令和4年度 問3(1)(2)（3点・5点）／令和6年度 問2(1)(2)（4点・6点）／令和7年度 問6(1)(2)（4点・4点）。3年連続で出題。

次の3つのプログラムについて、#include の行の動作を説明し、ヘッダファイルに入るべき内容を示せ。

1. main.c の3行目 #include"data.h" の動作を説明せよ。また "data.h" に入るべき内容を示せ。
   （data.h を使うプログラムでは、構造体 struct Dat（メンバは int n; int *dat; double ave;）と、関数 make・del を2つの .c ファイルで共有している）

2. #include"problem.h" の動作を、" "（二重引用符）の意味も含めて説明せよ。また problem.h に入るべき内容をコードで示せ。
   （構造体 struct data は整数型のメンバ a,b を持つ構造体、Data は struct data の別名。関数 func は int を1つ受け取り値を返さない）

3. #include"queue.h" がどのような動作をするか説明せよ。また queue.h に入るべき内容を示せ。
   （main 側からはキューの関数 put（int を1つ受け取り値を返さない）と get（引数なしで int を返す）だけを使う）

方針： 動作の説明は「読み込んで、その場に挿入する」の一文で足りる。 入るべき内容は「その .h を読み込む側が知らないと書けない情報」を数え上げる。 すなわち①使っている構造体の定義 ②typedef の別名 ③呼んでいる関数のプロトタイプ宣言の3種類だけ。

1. 動作：

1. data.h の内容：

struct Dat {
    int n;
    int *dat;
    double ave;
};
struct Dat make(int n, int *p);
void del(struct Dat A);

（main.c は struct Dat Math; を宣言し make・del を呼ぶので、構造体の定義とプロトタイプ宣言の両方が必要。片方だけでは足りない。）

2. 動作： 二重引用符 " " はまず自分（ソースファイル）と同じフォルダを探すという指定で、自作のヘッダに使う。 < > なら処理系が用意した標準のフォルダを探し、stdio.h のような標準ライブラリのヘッダに使う。

2. problem.h の内容：

struct data {
    int a;
    int b;
};
typedef struct data Data;
void func(int);

3. 動作：

3. queue.h の内容：

void put(int dat);
int get(void);

（キューの実体である queue[] と tail は static で実装側のファイルに閉じてあるので、ヘッダには書かない。書いてしまうと main 側から中身をいじれてしまい、static にした意味が消える。）

• 「動作を説明せよ」に対して「ヘッダファイルを使うため」「宣言を読み込むため」だけでは点にならない。「その場に挿入する（貼り付ける）」という機械的な動作を書く。

• typedef の行を忘れるのが定番の落とし穴。Data A = {0,0}; と書いてあるなら Data という名前が必要なので、struct data の定義だけでは足りない。

• ヘッダに int queue[10]; のような変数の定義を書かない。読み込んだファイルごとに実体ができて二重定義になる。

第II部 変数の有効範囲（スコープ）と記憶クラス

4種類の変数の使い分け

スコープ（有効範囲）： その変数の名前が通じる範囲。範囲外から名前で呼ぶことはできない。
寿命（記憶域期間）： その変数の値が生き残っている期間。スコープとは別の話で、「見えないが生きている」状態がありうる（static 局所変数がそれ）。
大域変数（グローバル変数）： 関数の外で宣言した変数。どの関数からでも読み書きできる。便利だがどこで値が壊れたか追えなくなるので、あまり使用を推奨されていない。引数と返り値で渡すのが基本。
static の2つの顔： 同じキーワードだが書く場所で意味が変わる。関数の中なら寿命が延び、初期化 static int y = 0; は最初の1回だけ実行されて以降は前回の値を持ち越す。関数の外ならスコープがそのファイルの中だけに狭まる。
extern の意味： 「この名前の大域変数は他のファイルにあるので、実体は作らずに借りて使う」という宣言。実体は1つのファイルだけが持つ。 （詳しい対応はチートシートの「変数の有効範囲（スコープ）と寿命」の表を見る。）

大域変数を extern で共有するプログラムの追跡と、static を使った書き換え

出題：令和4年度 問4(1)〜(5)（3点・4点・4点・3点・6点＝20点）。

以下のプログラム2について問に答えよ。

プログラム2 main.c

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int func(void);
int x = 0, y = 0;

int main(void)
{
    while (1) { // 無限ループ
        printf("x=?");
        scanf("%d", &x);
        if (x == -1) { break; }
        // y = 0;
        printf("y=%d\n",func());
    }
    return 0;
}

プログラム2 sub.c

extern int x, y;

int func(void)
{
    y += x;
    return y;
}

実行例（数字はキーボードからの入力）

x=?10
y=  (A)
x=?20
y=  (B)
x=?-1

1. 変数 x,y の有効範囲を述べよ。

2. 上記の実行例の空欄 (A), (B) を示せ。

3. main.c の13行目のコメント（// y = 0;）を外した場合、実行例の空欄 (A), (B) はどのようになるか示せ。

4. 大域変数の使用は推奨されないため、関数が引数をとるように修正した（下のプログラム2–2）。修正後の関数 func の変数 x の有効範囲を述べよ。

5. 関数 func を埋め、修正前と同じ動作をするプログラムを完成せよ。

プログラム2–2 main.c

#include<stdio.h>

int func(int x);

int main(void)
{
    int x;
    while (1) { // 無限ループ
        printf("x=?");
        scanf("%d", &x);
        if (x == -1) { break; }
        printf("y=%d\n", func(x));
    }
    return 0;
}

プログラム2–2 sub.c

int func(int x)
{
    ___(a)___;
    ___(b)___;
    return y;
}

方針： y += x; は「$y$ に $x$ を足し込む」＝$y$ が前の値を覚えているかどうかがすべて。 大域変数なのでループを回っても $y$ はリセットされない。ここを表にして追う。

解法（1回目・2回目の追跡）：

	入力 x	func 前の y	y += x の結果	表示
1回目	10	0（初期値）	$0+10=10$	y=10
2回目	20	10（前回の値）	$10+20=30$	y=30

問	答え
1	すべての関数内（プログラム全体）。main.c で定義され、sub.c が extern で参照しているので、2つのファイルのどの関数からでも使える
2	(A) 10 (B) 30
3	(A) 10 (B) 20
4	関数 func 内（引数として受け取った局所変数なので、func の中だけ）
5	(a) static int y = 0; (b) y += x;

3 の理由： y = 0; が毎回のループで実行されるので、func を呼ぶ直前に必ず $y=0$ に戻る。 よって $y=0+10=10$、次も $y=0+20=20$。$x$ の値がそのまま出る形になる。

5 の理由： 修正後は y が大域変数ではなくなったので、func の中に用意しなければならない。 ただしただの int y = 0; では毎回0に戻ってしまい、答えが 10, 20 になって修正前（10, 30）と違う動作になる。 static を付ければ初期化は最初の1回だけで、以降は前回の値を持ち越すので 10, 30 が再現できる。

• 問5でstatic を落として int y = 0; と書くのが最頻出の失点。設問が「修正前と同じ動作をする」と指定しているのは、まさにここを見ている。

• 問1で「main 関数内」と答えない。extern が付いているのは「他のファイルにある」という意味なので、範囲はファイルをまたいでプログラム全体になる。

• 問4は「main の x と func の x は別物」が要点。同じ名前でも別の変数で、値は呼び出しのときにコピーされる。

大域構造体と static 大域構造体のスコープ・実行結果

出題：令和6年度 問2(3)(4)（6点・4点）。同じ問2の(1)(2)（#include とヘッダの中身）は第I部で解説。

別紙に提示した以下のプログラム1–1、1–2 について問に答えよ。 構造体 struct data は整数型のメンバ a,b を持つ構造体であり、Data は struct data の別名である。

プログラム1–1

#include <stdio.h>
#include"problem.h"

Data A = { 0,0 };
static Data B = { 0,0 };
int main(void)
{
    int i;
    for (i = 1; i < 3; i++) {
        A.a += i; A.b += i * 2;
        B.a += i; B.b += i * 2;
        printf("%d %d\n", A.a, A.b);
        printf("%d %d\n", B.a, B.b);
        func(i);
    }
    return 0;
}

プログラム1–2

#include<stdio.h>
#include"problem.h"
extern Data A;
static Data B = { 0,0 };
void func(int i)
{
    A.a += i; A.b += i * 2;
    B.a += i; B.b += i * 2;
    printf("%d %d\n", A.a, A.b);
    printf("%d %d\n", B.a, B.b);
}

1. プログラム中の #include"problem.h" はどのような動作をするか説明せよ。（第I部で解説済み）

2. ヘッダファイル problem.h に入る内容をコードで示せ。（第I部で解説済み）

3. プログラム中の構造体 A、B の、それぞれのスコープ（有効範囲）を述べよ。

4. プログラムの実行結果がどのようになるか示せ。

方針： 問3が問4の鍵になる。 A は実体が1つ（1–1 が定義し、1–2 が extern で借りている）。 一方 B はstatic なのでファイルごとに別の実体があり、同じ名前でも中身は別々に増える。 これを取り違えると実行結果が全部ずれる。

解法： A は共有なので足し込みが累積、B は 1–1 用と 1–2 用が別々に累積する。

i	実行される場所	A（共有）	B(1–1)	B(1–2)	表示
1	1–1 の for の中	1  2	1  2	—	1 2 / 1 2
1	func(1)（1–2）	2  4	—	1  2	2 4 / 1 2
2	1–1 の for の中	4  8	3  6	—	4 8 / 3 6
2	func(2)（1–2）	6  12	—	3  6	6 12 / 3 6

問	答え
3	A：プログラム全体（1–1 で定義し 1–2 が extern で参照しているので両ファイルから使える）B：宣言されているファイル内（static なので 1–1 の B と 1–2 の B は別の変数）

4. 実行結果（8行。左が A、右が B）

行	$i=1$ の4行	行	$i=2$ の4行
1行目	1  2	5行目	4  8
2行目	1  2	6行目	3  6
3行目	2  4	7行目	6  12
4行目	1  2	8行目	3  6

• B を1つの変数だと思って足し続けるのが最大のひっかけ。そうすると 4行目が 2 4、8行目が 6 12 になってしまう。 static 大域変数は「ファイルごとに別の箱」。

• ループが i = 1; i < 3; i++ なので$i$ は 1 と 2 の2回だけ。$i=0$ から数えると4行足りなくなる。

• 問3で「1–1 と 1–2 の両方」と答えない。static を付ける目的はまさに他ファイルから見えなくすること。

実装側に static 変数を置くメリット

出題：令和7年度 問6(3)(4)（各4点）。

キューを実装したファイルで、変数 queue（配列）および tail が static で宣言されている。

1. 変数 queue および tail のスコープ（有効範囲）を述べよ。

2. 変数 queue および tail に static 変数を用いることのメリットを、問1を踏まえて述べよ。

問	答え
1	キューを実装したファイルの中だけ（static を付けた大域変数なので、宣言したファイル内のみ有効）
2	main 関数から、キューのデータを変更することができない

補足（なぜそれが「メリット」なのか）： キューはput と get という決められた出入口だけを通して使うのが正しい使い方。 static を付けずに大域変数にすると、main 側で queue[2] = 99; や tail = 0; と直接書き換えられてしまい、 キューの整合性（tail が本当に末尾を指しているか）が壊れる。 中身を隠して関数経由に限定することで、壊れ方を put／get の中だけに閉じ込められる。

「メリット」を「プログラム終了まで値が残るから」と答えると点にならないことがある。 設問が「問1（スコープ）を踏まえて」と指定しているので、答えるべきは寿命の話ではなくスコープの話＝ 外から触れなくなること。値が残る性質は「関数の外で宣言した」ことで既に得られていて、static が新しく加えた効果ではない。

第III部 構造体と動的メモリ確保

構造体の基本と、関数との受け渡し

構造体： 型の違う値をまとめて1つの型として扱う仕組み。中の変数をメンバと呼ぶ。
アクセス： 実体ならドット A.n、ポインタ経由なら矢印 p->n（(*p).n と同じ意味）。
typedef： 型に別名を付ける。typedef struct cell CELL; と書くと以降 struct cell を CELL と書ける。
関数との受け渡し： 構造体は値渡し（コピーが渡る）で、返り値としても返せる。 ただし配列は値渡しにならず、先頭アドレス（ポインタ）が渡る。

配列を関数に渡すと何が渡るか
int data[100]; を make(n, data) と渡すと、関数側が受け取るのは配列 data の先頭アドレス（&data[0] と同じ）。 だから受け取る側は int *p と書き、中では p[i] と配列のように使える。 配列の要素数は伝わらないので、個数 n を別の引数で渡す必要がある。

構造体を返す関数と、動的に確保したメモリの解放

出題：令和4年度 問3(3)〜(6)（3点・3点・6点・2点＝14点）。同じ問3の(1)(2)（#include とヘッダの中身）は第I部で解説。

プログラム1中、構造体 struct Dat はデータの数、データの内容、平均値を保持するためのものである。 関数 make はデータの個数とデータの入った配列を渡すと、メンバに値の入った（平均値などが計算された）構造体を返す関数である。 make は動的なメモリ確保を行っているため、確保したメモリを解放する関数 del を用意する。以下の問に答えよ。

プログラム1 main.c

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include"data.h"

#define N 100

int main(void)
{
    int i, n, data[N];
    struct Dat Math;

    printf("データの個数：");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
      printf("データ[%d]:", i);
      scanf("%d", &data[i]);
    }
    Math = make(n, data);

    for (i = 0; i < Math.n; i++) {
      printf("%d ", Math.dat[i]);
    }
    printf("平均値: %f", Math.ave);
    del(Math);
    return 0;
}

プログラム1 sub.c

#include <stdlib.h>
#include"data.h"

struct Dat make(int n, int *p)
{
    int i;
    double ave = 0;
    struct Dat A;
    A.n = n;
    A.dat = (int *)calloc(n, sizeof(int));
    for (i = 0; i < n; i++) {
        ___(A)___;
        ___(B)___;
    }
    ___(C)___;
    return A;
}

void del(struct Dat A)
{
    ___(a)___;
}

構造体の定義

struct Dat {
    int n;       // データの個数
    int *dat;    // データ保存用ポインタ
    double ave;  // 平均値
};

実行例（数字はキーボードからの入力）

データの個数：3
データ[0]:10
データ[1]:20
データ[2]:30
10 20 30 平均値: 20.000000

1. main.c の3行目 #include"data.h" の動作を説明せよ。（第I部で解説済み）

2. "data.h" に入るべき内容を示せ。（第I部で解説済み）

3. ポインタ p が受け取る値は、どのような値か述べよ。

4. calloc の返り値は、何の値か述べよ。

5. 空欄を埋め、返り値の構造体 A にデータの中身と、平均値が代入されるよう完成せよ。

6. 関数 del の内容を示せ。

方針： 空欄が3つ（(A)(B)(C)）あり、ループの中に2つ・ループの外に1つという配置がヒント。 「データの中身を写す」と「合計を足し込む」はデータ1個ごとなのでループの中、 「平均を出す」は合計が出そろってから1回だけなのでループの外。 ここで平均をループの中で計算すると毎回上書きになり、最後の1回だけ正しく見えて途中は無意味な値になる。

問	答え
3	配列 data の先頭アドレス
4	確保したメモリの先頭アドレス
6	free(A.dat);

5. プログラムの空欄

空欄	答え
(A)	A.dat[i] = p[i];
(B)	ave += p[i];
(C)	A.ave = ave / n;

確認（実行例の再現）： $n=3$、データ $10,20,30$。 A.dat には $10,20,30$ が写り、ave は $10\to 30\to 60$ と積み上がる。 ループを抜けて A.ave = 60 / 3 = 20.0。表示は 10 20 30 平均値: 20.000000 で実行例と一致する。

• A.dat = p; と書いてはいけない。それは「同じ配列を指させる」だけで、中身のコピーになっていない。 main 側の data[] が書き換わったら Math.dat も変わってしまうし、calloc で確保した領域が使われないまま迷子になる。

• (C) でA.ave = ave / A.n; と書いてもよい（A.n には n が入っている）。ただしave は double なので、ave / n は実数の割り算になる。 もし合計を int で持っていたら、たとえばデータが $10,20,31$（合計 $61$）のとき 61 / 3 は整数除算になって 20 が入り、正しい $20.333\cdots$ が切り捨てられる。合計を double で持っているのはこのため。

• del でfree(A); と書かない。A は構造体そのもの（自動変数のコピー）で、calloc が確保したのは A.dat が指す領域。解放すべきは A.dat。

第IV部 スタック

スタックの考え方と配列での実装

スタック（stack）： イメージは積み重ねた本。次の本は上に乗せ、本は上から取り出す。 つまり後から入れたものが先に出る（LIFO：Last In First Out）。
用語： 積む操作＝push、取り出す操作＝pop、一番上＝頂上（top）、一番下＝底（bottom）。
使われ方： 関数の呼び出し履歴、ブラウザの「戻る」、エディタのアンドゥ。

配列による実装（top は今の一番上の添字を覚える）

#define N 10
int stack[N] = { 0 };
int top = -1;          // 空の状態は top = -1（要素が1つも無い）
void push(int dat)
{
    if (top < N - 1) { // 満杯でなければ
        top++;             // 先に1つ上へ進めて
        stack[top] = dat;  // そこへ書き込む
    }
}
int pop(void)
{
    int ret = 0;
    if (top >= 0) {        // 空でなければ
        ret = stack[top];  // 今の一番上を読んで
        top--;             // 1つ下げる
    }
    return ret;            // 空なら初期値 0 が返る
}

pop は配列の値を消さない（top を下げるだけなので取り出した値がそのまま残る）。 空で pop すると ret の初期値 0 が返る（if に入らないため）。この2点がそのまま試験で問われる。

スタック操作のトレース（取り出される順番）

出題：令和4年度 問2(1)（3点）／令和7年度 問3(1)（4点）。データ列まで同一。

以下のデータを用い、スタック操作をした場合、pop で取り出されるデータの順番を示せ。 なお、文字は push される文字を、$\uparrow$ は pop を意味する。

$$\text{A},\text{J},\text{C},\uparrow ,\text{P},\text{Q},\uparrow ,\uparrow ,\text{G},\text{Z},\uparrow ,\text{L},\uparrow$$

方針： 表を横に伸ばして1操作1列で書く。$\uparrow$ の列にそのとき出た文字を書けば、下段を左から読むだけで答えになる。

解法：

c 操作 & A & J & C & $\uparrow$ & P & Q & $\uparrow$ & $\uparrow$ & G & Z & $\uparrow$ & L & $\uparrow$
4段目 & & & & & & Q & & & & Z & & L &
3段目 & & & C & & P & P & P & & G & G & G & G & G
2段目 & & J & J & J & J & J & J & J & J & J & J & J & J
1段目 & A & A & A & A & A & A & A & A & A & A & A & A & A
取り出し & & & & & & & & & & & & &

（$\uparrow$ の列では、取り出された文字が消えて段が1つ下がる。3列目で積んだ C を取り出してもその下の J は動かないので、8列目で P を出した後はA と J が残っている。）

pop で取り出される順番は 。

スタックの変化の様子と取り出される順番

出題：令和6年度 問3(1)(2)（6点・4点）。

以下のデータを用い、スタック操作をした。文字はスタックへの push 操作、$\uparrow$ は pop 操作を意味する。

$$\text{A},\text{B},\uparrow ,\text{C},\uparrow ,\text{D},\text{E},\uparrow ,\uparrow ,\uparrow$$

1. スタックの変化の様子を順を追って示せ。

2. pop で取り出されるデータの順番を示せ。

方針： 「変化の様子を示せ」は1操作ごとの箱の絵を10個並べるのが求められている形。 下から積み上げる向き（1段目が底）で書き、$\uparrow$ の列では出て行く文字を箱の上に書き出すと採点者に伝わる。

解法：

c 操作 & A & B & $\uparrow$ & C & $\uparrow$ & D & E & $\uparrow$ & $\uparrow$ & $\uparrow$
3段目 & & & & & & & E & & &
2段目 & & B & & C & & D & D & D & &
1段目 & A & A & A & A & A & A & A & A & A &
取り出し & & & & & & & & & &

pop で取り出される順番は 。

E と D の順番を逆に書く（B, C, D, E, A としてしまう）のが最大の失点。 $\uparrow$ が2つ続く場面では、後から積んだ E が先に出る（LIFO）。 D は E の下にあるので、E を取り除いてから初めて取り出せる。

配布された解答例でもこの箇所が 「B, C, D, E, A」と書き間違えられているが、 同じ解答例の「変化の様子」の図（上の表と同じ形）ではE が D の上に積まれているので、 図と出力順が矛盾している。図を先に書いて、そこから出力順を読み取る手順にすれば必ず正しくなる。 $\uparrow$ が続いたら「上から順に」と口に出して確認する。

配列で実装したスタックの top と配列の中身

出題：令和6年度 問4(1)〜(4)（3点・4点・4点・4点＝15点）。

以下のプログラムはスタックの機能を実装したプログラムである。

1. プログラム開始時点で top 値はいくつか述べよ。

2. プログラム中 push(20) まで実行した直後の top の値と配列 stack の内容を示せ。

3. プログラム中 pop() を2回目に実行した（//(*) のコメントのある行）直後の top の値と列 stack の状態を示せ。

4. 実行結果の (A) に入る値を示せ。

#include<stdio.h>
#define N 10

int stack[N] = { 0 };
int top = -1;
void push(int dat);
int pop(void);

int main(void)
{
    push(10);
    push(20);
    printf("%d\n", pop());
    printf("%d\n", pop());  //(*)
    printf("%d\n", pop());
    return 0;
}

void push(int dat)
{
    if (top < N - 1) {
        top++;
        stack[top] = dat;
    }
}
int pop(void)
{
    int ret = 0;
    if (top >= 0) {
        ret = stack[top];
        top--;
    }
    return ret;
}

実行結果

20
10
(A)

方針： pop が配列を書き換えないことに気づけば全問解ける。 top だけが上下し、配列の値は上書きされるまで残り続ける。

解法：

時点	top	[0]	[1]	[2]	[3]	返り値
開始時点	$-1$	0	0	0	0	—
push(10) 直後	0	10	0	0	0	—
push(20) 直後	1	10	20	0	0	—
1回目の pop 直後	0	10	20	0	0	20
2回目の pop 直後	$-1$	10	20	0	0	10
3回目の pop 直後	$-1$	10	20	0	0	0

問	答え
1	$-1$
2	top は 1、配列は stack[] = {10, 20, 0, 0, …}
3	top は $-1$、配列は stack[] = {10, 20, 0, 0, …}（値は消えずに残る）
4	0

4 の理由： 3回目の pop では top が $-1$ なので if (top >= 0) が成立せず、if の中は1回も実行されない。 よって ret は宣言時の初期値 0 のまま返る。

• 問3で配列を {0,0,0,0} と書くのが典型的な誤り。pop は top– しかしないので、10 と 20 は配列に残っている。 「取り出したら消える」というイメージで答えると外す。

• 問4で「エラー」「不定値」と答えない。この pop は空のときも 0 を返すように書かれている（int ret = 0; が保険）。 プログラムを読んで答えるのであって、一般論で答えるのではない。

• top の初期値を 0 と答えない。top が 0 だと「stack[0] に有効な値がある」＝要素1個の意味になってしまう。

第V部 キュー

キューの考え方と配列での実装

キュー（queue）： イメージはレジの待ち行列。一番後ろに並び、並んだ順に対応される。 つまり先に入れたものが先に出る（FIFO：First In First Out）。
用語： 追加＝put（enqueue）、取り出し＝get（dequeue）、末尾＝tail、先頭＝head。
使われ方： プリンタの印刷待ち、キーボードの入力バッファ、通信の受信バッファ。

配列による実装（ずらし方式）tail は次に入れる空き位置の添字を覚える。先頭は常に queue[0]。

#define N 10
void shift(void);
static int tail = 0;    // 空の状態は tail = 0
static int queue[N];
void put(int dat)
{
    queue[tail] = dat;  // (1) 末尾に代入してから
    tail++;             // (2) 末尾の位置を +1 する
}
int get(void)
{
    int ret = 0;
    ret = queue[0];     // (1) 先頭の値を取り出す
    shift();            // (2) 2番目以降を前に一つずらす
    tail--;             // (3) 末尾の位置を -1 する
    return ret;
}
void shift(void)        // queue の内容を1つずらす関数
{
    int i;
    for (i = 1; i < N; i++) {
        queue[i - 1] = queue[i];
    }
}

	スタックの top	キューの tail
何を指しているか	今の一番上（データがある場所）	次に入れる空き（データがない場所）
だから追加は	先に進めてから書く	書いてから進める

つまり「tail を先に +1 してから代入」は誤り。1つ飛ばした場所に書き込むことになり、飛ばされた場所に不定値（?）が残る。

キュー操作のトレース（取り出される順番）

出題：令和7年度 問3(2)（4点）。データ列はスタックの問3(1)と同じ。

以下のデータについて、キュー操作をした場合、get で取り出されるデータの順番を示せ。 なお、文字は put される文字を、$\uparrow$ は get を意味する。

$$\text{A},\text{J},\text{C},\uparrow ,\text{P},\text{Q},\uparrow ,\uparrow ,\text{G},\text{Z},\uparrow ,\text{L},\uparrow$$

方針： 同じデータ列でも、取り出す向きが逆になるだけ。 キューは左端（先頭）から出るので、列の左端を消していく。

解法：

操作	入れる／出す	キューの中身（左が先頭）	出た値
A, J, C	put $\times 3$	A J C
$\uparrow$	get	J C
P, Q	put $\times 2$	J C P Q
$\uparrow$	get	C P Q
$\uparrow$	get	P Q
G, Z	put $\times 2$	P Q G Z
$\uparrow$	get	Q G Z
L	put	Q G Z L
$\uparrow$	get	G Z L

get で取り出される順番は 。 （スタックだと同じデータ列で C $\to$ Q $\to$ P $\to$ Z $\to$ L になる。入れる操作は同じで、出る向きだけが違う。）

キューの答えが「入れた順に並べただけ」に見えるのは正しい。 FIFO なので、出る順番＝入れた順番になる。取り出しの回数が5回なら、入れた順の先頭5個がそのまま答え。 「そんな簡単でいいのか」と疑って並べ替えると失点する。

キューの操作手順の誤りを見つけて直し、関数を完成させる

出題：令和7年度 問6(5)〜(7)（4点・4点・6点＝14点）。

以下はキューを扱うプログラムである。キューの保持データは整数型配列 queue[] に保持されているものとする。

プログラム（main 側）

#include<stdio.h>
#include "queue.h"

int main(void)
{
    int a, b;
    while (1) {
        printf("保存データ入力\n");
        printf("(-1でデータ取り出し):");
        scanf("%d", &a);
        if (a == -1) {
            b = get();
            printf("取り出したデータ: %d\n", b);
        }
        else {
            put(a);
        }
    }
    return 0;
}

プログラム（実装側）

#define N 10

void shift(void);

static int tail = 0;
static int queue[N];

void put(int dat)
{
    ___(A)___
}

int get(void)
{
    int ret = 0;
    ___(B)___
    return ret;
}

// queue の内容を1つずらす関数
void shift(void)
{
    int i;
    for (i = 1; i < N; i++) {
        queue[i - 1] = queue[i];
    }
}

キューの操作 put と get の手順は以下に示されている。しかし、示された手順は put, get のどちらかに誤りがある。

putput したい値を dat とする。

1. 末尾の位置を $+1$ する

2. キューの末尾に dat の値を代入

get

1. 先頭の値を取り出す（関数の返り値として保存）

2. 2番目以降の値を前に一つずらす

3. 末尾の位置を $-1$ する

1. 上記の誤りのある手順で、右の図の状態のキューに put(10) を行う。操作後のキューの状態を示せ。 また、同様に図の状態のキューに get を行い、操作後のキューの状態を示せ。取り出された値についても示すこと。

2. put, get のどちらに誤りがあるかを示せ。また、手順の誤りを修正し、キューが正しく動作する手順にせよ。

3. 修正した手順に従い、関数 put と get を完成せよ。

操作前のキューの状態

1-2 番号	データ
1-2 0	5
1-2 1	20
1-2 2	?	$\leftarrow$ tail = 2
1-2 3	?
1-2

方針： 問1は「わざと誤った手順のまま」動かすことを求めている。 書かれた手順をそのまま1行ずつ実行して、飛ばされた場所（? のまま残る場所）を図に描くのが答え。 自分で気づいた正しい手順で解いてしまうと問1が不正解になる。

解法（問1）： 誤った put は「tail++; → queue[tail] = dat;」なので、 $\text{tail}=2\to 3$ にしてから queue[3] = 10 に書き込む。queue[2] は ? のまま置き去りになる。 get は手順どおりで正しく、queue[0] の 5 を取り出し、全体を前へずらして tail を $2\to 1$ にする。

誤った手順で put(10) した後

1-2 番号	データ
1-2 0	5
1-2 1	20
1-2 2
1-2 3		$\leftarrow$
1-2

get した後

1-2 番号	データ
1-2 0
1-2 1		$\leftarrow$
1-2 2	?
1-2 3	?
1-2

取り出された値：

問	答え
2	誤りがあるのは put。正しい手順は(1) キューの末尾に dat の値を代入(2) 末尾の位置を $+1$ する

3. 関数の完成

空欄	答え
(A)	queue[tail] = dat;``tail++;
(B)	ret = queue[0];``shift();``tail–;

なぜ put が誤りなのか： tail は「次に入れる空き位置」を指している（空のとき tail = 0 で、最初のデータは queue[0] に入る）。 先に $+1$ してしまうと1つ飛ばした場所に書くことになり、飛ばした場所は不定値のまま。 その後 get でずらすと、入れていない値が取り出される。

• 問1で正しい手順で解いてしまうのがひっかけ。設問に「上記の誤りのある手順で」とわざわざ書いてあるので、queue[2] を ? のまま残すのが正解。

• get を誤りだと答えない。手順（取り出す → ずらす → $-1$）は正しい。順序を入れ替えて「ずらしてから取り出す」にすると2番目の値が出てしまうが、書かれている手順はそうなっていない。

• 問2の答えは「put」だけでは半分。正しい手順を2行書くところまでが答え。

第VI部 連結リスト

セルとポインタでつなぐデータ構造

連結リスト（linked list）： データ1個ぶんの箱（セル）に「次のセルのアドレス」を持たせて数珠つなぎにしたもの。 配列と違って途中への挿入・削除がポインタの付け替えだけで済むのが利点（配列だと後ろを全部ずらす必要がある）。
セルの中身： データ本体（data）＋次のセルを指すポインタ（next）。
終端： 最後のセルの next は NULL。「ここで終わり」の印。
head（ダミーセル）： 先頭を表すためだけのセル。data は使わない（図では $\times$ を書く）。 head を置いておくと「先頭への挿入」も「途中への挿入」と同じコードで書ける。

セルの定義

struct cell {
    int data;           // 整数型データ
    struct cell* next;  // 次のセルを指すためのポインタ
};
typedef struct cell CELL;   // struct cell の別名を CELL にする

メンバの型は struct cell* と書く。typedef で別名 CELL が作られるのはこの定義が終わった後なので、 中で CELL* next; と書くことはできない。

空のリスト（init_list が作る状態）

CELL* init_list(void)          // リストの初期化
{
    CELL* head = (CELL*)malloc(sizeof(CELL));
    if (head != NULL) {
        head->next = NULL;     // 「次は無い」= 空のリスト
    }
    return head;
}

挿入と削除は「順番」が命

• 挿入（p の後ろに入れる）： temp = (CELL*)malloc(sizeof(CELL)); → temp->data = n; → temp->next = p->next; → p->next = temp;

• 削除（p の次のセルを消す）： temp = p->next; → p->next = temp->next; → free(temp);

青で示した2手順を入れ替えると壊れる。挿入では「元の続き」を上書きしてから読むことになりリストの後半が全部行方不明、削除では解放済みメモリを読むことになる。

配列で表された連結リストから文字列を読む

出題：令和4年度 問2(2)（3点）。

以下の連結リスト構造に保持されている文字列を示せ。最初のセルは 0 番のものとする。

0	1	2	3	4
A	M	B	P	E
3	4	1	2	–

（上段＝セル番号、中段＝データ、下段＝次のセル番号。– は終端）

方針： 0 番から出発して、下段の番号をたどるだけ。表の左から順に読んではいけない。 たどった順にデータを書き並べる。

解法：

$$0(\text{A})\to 3(\text{P})\to 2(\text{B})\to 1(\text{M})\to 4(\text{E})\to \text{終端}$$

保持されている文字列は 。

表の並び順（A M B P E）をそのまま答えるのがひっかけ。 連結リストはメモリ上の並び順とリストの並び順が無関係なのが本質で、この問題はそこを確認している。 たどるときは訪れたセル番号をメモしながら進めると迷わない（0, 3, 2, 1, 4）。

セルの定義・空リストの図・挿入と削除の関数を完成させる

出題：令和4年度 問5(1)〜(3)（4点・4点・14点＝22点）。

整数の値（data）を保持する連結リストを構築する。以下の問に答えよ。

1. セルを表す構造体 struct cell および、その別名 CELL を定義する文を示せ。以下のメンバが含まれているものとする。

   • 整数型データ：data

   • 次のセルを指すためのポインタ：next

2. 関数 init_list は空のリストを生成するためのものである。関数の動作より、空のリストはどのようなものか図で示せ。

3. 関数の空欄を埋め、挿入および削除の関数を完成せよ。

CELL* init_list(void) // リストの初期化
{
    CELL* head = (CELL*)malloc(sizeof(CELL));
    if (head != NULL) {
        head->next = NULL;
    }
    return head;
}
void add_cell(CELL* p, int n) // セルの追加
{
    CELL* temp;
    ___(A)___;
    ___(B)___;
    ___(C)___;
    ___(D)___;
}
void del_cell(CELL* p) // セルの削除
{
    CELL* temp;
    ___(E)___;
    ___(F)___;
    ___(G)___;
}

挿入の手順

1. 挿入用セルの準備

2. p の next の値を新しいセルの next へ代入

3. 新しいセルのアドレスを p の next へ代入

削除の手順

1. p の next の値を保存

2. p の次のセルの next の値を p の next へ代入

3. p の次のセルを消去

方針： 空欄が挿入は4つ・削除は3つなのに、示された手順はどちらも3段階。 つまり挿入の手順(1)「挿入用セルの準備」が2行に分かれる（領域の確保とデータの代入）と分かる。 空欄の数と手順の数を突き合わせるのが空欄問題の定石。

1. セルの定義

struct cell {
    int data;
    struct cell* next;
};
typedef struct cell CELL;

2. 空のリストの図： head のセルが1つだけ確保され、next が NULL。data は使わない。

3. プログラムの空欄

空欄	答え	意味
(A)	temp = (CELL*)malloc(sizeof(CELL));	セル1個ぶんの領域を確保
(B)	temp->data = n;	新しいセルにデータを入れる
(C)	temp->next = p->next;	元の「続き」を新セルに引き継ぐ
(D)	p->next = temp;	p の次を新セルに差し替える
(E)	temp = p->next;	消す相手のアドレスを保存
(F)	p->next = temp->next;	p の次を「消す相手の次」に飛ばす
(G)	free(temp);	領域を解放

• (C) と (D) を入れ替えると致命的。先に p->next = temp; をすると、元の p->next（後続リストの先頭）が上書きされて、temp->next に入れるべき値が読めなくなる。以降のセルは全部たどれなくなる（メモリリーク）。

• (E) と (F) を入れ替えても壊れる。p->next を先に書き換えると、消す相手のアドレスが分からなくなる。

• (G) を先に書かない。free した後の temp->next を読むのは解放済み領域へのアクセス。

降順にソートされたリストを作る（sort_list）

降順ソート挿入の図と sort_list の完成

出題：令和4年度 問6(1)(2)（4点・12点）。

連結リストの関数群を用いて、挿入するデータが、降順（大きい値から小さくなる順）にソートされたリストを生成するリストを作る。 そのための関数を sort_list とする。目的の挿入データが降順になるようにするために、以下の手順で行われる。

ポインタ p は最初リストの先頭のアドレス（Add1）を指しているものとする。挿入する値を n とする。

1. 以下のことを p の next の値が NULL となるまで、以下の手順 A), B) を繰り返す。

   • p の次のセルの data の値が n よりも小さければ、繰り返しを終了

   • A) が成立しなければ、p を次のセルを指すようにする

2. 繰り返しが終了したら p の後にセルを挿入する

void sort_list(CELL *p, int n)
{
    CELL *q;
    while (___(A)___) {
        q = p->next;
        if (___(B)___) {break;}
        ___(C)___;
    }
    ___(D)___;
}

実行例（数字はキーボードからの入力）

追加データ：10
リストの内容:10
追加データ：5
リストの内容:10 5
追加データ：30
リストの内容:30 10 5
追加データ：20
リストの内容:30 20 10 5

1. 下図に示したリスト構造の例に対して、23 と 1 をデータが降順になるように挿入する。挿入されたリストが最終的にどのような状態になるか示せ。新しいセルのアドレスは Add5, Add6 とする。

2. 上記の手順を参考に関数 sort_list の空欄を埋め、関数を完成せよ。

方針： 手順の文をそのままコードに1対1で写す。 「p の next が NULL となるまで繰り返す」＝NULL でない間ループ＝while (p->next != NULL)。 A) の「p の次のセルの data」は直前の行で q = p->next; と取ってあるので q->data。 「n よりも小さければ」は q->data < n。 B) の「p を次のセルを指すようにする」は p = q;。 最後の「p の後にセルを挿入」は既にある add_cell を呼ぶ。

解法（問1のトレース）： 挿入位置は「自分より小さい値が現れる直前」。

挿入する値	p の動き（比較する相手）	結果
23	Add1 → 次は 30。$30<23$ でない → p=Add2。次は 15。$15<23$ なので break	Add2 の後に Add5(23) を挿入
1	Add1 → 30 で継続、Add2 → 23 で継続、Add5 → 15 で継続、Add3 → 3 で継続、Add4 の次は NULL なのでループ終了	Add4 の後（末尾）に Add6(1) を挿入

1. 最終的なリストの状態Add1 $\to$ Add2(30) $\to$ Add5(23) $\to$ Add3(15) $\to$ Add4(3) $\to$ Add6(1) $\to$ NULL

（変わったのは Add2 の next（Add3 $\to$ Add5）と Add4 の next（NULL $\to$ Add6）の2か所だけ。他のセルは動かない。）

2. プログラムの空欄

空欄	答え	対応する手順
(A)	p->next != NULL	「p の next が NULL となるまで」
(B)	q->data < n	A)「p の次のセルの data が n より小さければ」
(C)	p = q;	B)「p を次のセルを指すようにする」
(D)	add_cell(p, n);	2.「p の後にセルを挿入する」

• (A) をp->next == NULL と書くと逆。「…となるまで繰り返す」は「…でない間繰り返す」。日本語の「まで」を while に直すときは必ず否定に変える。

• (B) の不等号の向きを間違えると昇順になる。降順（大きい値から）なので、挿入したい n より小さい値に出会ったらそこで止まる＝q->data < n。

• (D) を自分で malloc から書き始めない。設問が「関数群を用いて」と言っているので、既にある add_cell を呼ぶのが正解。

第VII部 浮動小数点数の誤差

なぜ 0.1 を10回足しても 1 にならないのか

丸め誤差： 実数を有限桁の2進数で表すときに切り捨て・切り上げが起こる誤差。
打ち切り誤差： 無限に続く計算（級数・反復）を途中で止めることで生じる誤差。
桁落ち： 近い値どうしの引き算で有効桁数が激減すること。
情報落ち： 大きく違う大きさの値の足し算で、小さい方が無視されること。

10進の 0.1 は2進数では循環小数になる

$$0.1_{(10)}=0.0001100110011001100{\cdots }_{(2)}$$

double は仮数部が有限桁（52ビット）なので、この循環はどこかで打ち切られる。 実際に double に入る値は 0.1 ではなく

$$0.1000000000000000055511151231257827\cdots$$

という別の数になる。だからこれを10回足しても

$$0.99999999999999988897\cdots \ne 1.0$$

であり、x == 1 は成立しない。

対策： 実数の比較に == を使わない。

if (fabs(x - 1.0) < 1.0e-9) { break; }   // 差が十分小さいかで判定する

意図どおりに動かないループの動作と、その理由

出題：令和7年度 問2(1)(2)（各4点）。

以下のプログラムは x を 1.0 まで 0.1 ずつ加算し、表示するプログラムである。 しかし、意図した通りに動作しない。以下の問に答えよ。

#include<stdio.h>

int main(void)
{
  double x = 0;

  while (1) {
    x += 0.1;
    printf("%f\n", x);
    if (x == 1) { break; }
  }
  return 0;
}

1. このままのプログラムでは、どのような動作をするか述べよ。

2. 問1について、なぜそのような動作をするのか説明せよ。

方針： 「画面に何が出るか」と「内部の値がどうなっているか」を分けて考える。 printf("%f") は小数点以下6桁に丸めて表示するので、画面には 1.000000 と出る。 しかし if (x == 1) が見ているのは内部の値で、それは 1 より少しだけ小さい。

解法（実際の値）：

足した回数	画面の表示	内部の値
9 回	0.900000	0.89999999999999991118
10 回	1.000000	0.99999999999999988898（$\ne 1$）
11 回	1.100000	1.09999999999999986677

問	答え
1	0.1, 0.2, …, 1.0, 1.1, …のように、1.0 で止まらずに加算と表示を続ける無限ループになる
2	2進数で 0.1 は循環小数となることから、プログラムでは有限桁で表現される。このことから、0.1 を10回足しても正確に 1.0 とならないから

答案での書き方： 問1は「無限ループになる」という語を必ず入れる。 問2は①2進数では循環小数になる ②有限桁で打ち切られる ③だから正確に 1.0 にならないの3段で書く。 「誤差があるから」だけでは何の誤差かが示せていないので部分点になる。

• 「1.0 を超えたところで止まる」と答えない。止める条件は x == 1 だけなので、1 をまたいでも止まらない。

• 画面には 1.000000 と表示されるのがこの問題の意地の悪いところ。「表示は 1 なのに止まらない」ことを説明できるかが問われている。

• 直し方を聞かれたら回数で回す（for (i = 0; i < 10; i++)）か差の絶対値で判定する（fabs(x - 1.0) < EPS）の2通りを書く。

第VIII部 方程式の数値解法（二分法・ニュートン法）

2つの方法の使い分け

	二分法	ニュートン・ラプソン法
考え方	解を挟んだ区間を半分ずつ狭める	接線を引いて$x$ 軸との交点へ飛ぶ
必要なもの	解を挟む2点 $a,b$	導関数 $f^{\prime }(x)$ と初期値 $x_1$
長所・短所	必ず収束するが遅い	収束が速いが $f^{\prime }(x)=0$ で破綻・初期値が悪いと発散

二分法

アルゴリズム

1. 最初に解を挟む適当な初期値 $a,b$ を選ぶ（ただし $a<b$）

2. $a$ と $b$ の中点 $c=(a+b)/2$ を求める

3. $f(c)$ の符号を調べる

   • $f(c)>0$ ならば、$b$ に $c$ の値を代入

   • $f(c)<0$ ならば、$a$ に $c$ の値を代入

4. $\left|f(c)\right|<\epsilon$ になったら終了。そうでなければ (1) へ戻る

(2) の書き方は「右上がりの関数」専用。一般の関数でも動くようにするには符号の積で判定する（後述）。

二分法の反復計算・プログラムの完成・条件判定の一般化

出題：令和7年度 問4(1)〜(3)（4点・12点・4点＝20点）。

$f(x)=0$ の方程式を求める方法として、二分法と呼ばれる方法がある。二分法について問に答えよ。

1. 以下の方程式について、初期値 $a=1$, $b=4$ として、二分法の計算を2回行い、表を埋めよ（小数点以下2桁示すこと）。 $f(x)=x^2+x-6=0$

2. 上記の手順に従って問1の方程式を解くプログラムを作成する。以下のプログラムの空欄を埋め、二分法のプログラムを完成せよ。

3. 上記の計算手順は、関数が右上がりの場合についてのみ計算可能である。右上がり、右下がり両方の場合どちらでも計算可能になるように修正せよ。

#include<stdio.h>
#include<math.h>
#define EPS 1.0e-6

double f(double x);

int main(void)
{
    double a, b, c;
    a = 1; b = 4;
    while (1) {
        ___(a)___;
        ___(b)___ {
            ___(c)___;
        }
        ___(d)___ {
            ___(e)___;
        }
        if (fabs(f(c)) < EPS) {
          break;
        }
    }
    printf("解は x=%f", c);

    return 0;
}

double f(double x)
{
    ___(f)___;
}

問1の表

$a$	$b$	$c$	$f(c)$
1.00	4.00

問3の参考図（右上がりなら $f(c)>0$ で $b\leftarrow c$ が正しいが、右下がりでは逆になる）

方針（問1）： $f(x)=x^2+x-6=(x+3)(x-2)$ なので真の解は $x=2$。 これを知っておくと計算が合っているかの検算になる（$c$ が 2 に近づいていくはず）。 $f(1)=-4<0$、$f(4)=14>0$ なので区間 $[1,4]$ は確かに解を挟んでいる。

解法（問1）：

1回目： 中点は $c=\frac{1+4}{2}=2.5$。これを $f$ に代入して

$$f(2.5)=2.5^2+2.5-6=6.25+2.5-6=2.75$$

$f(c)>0$ なので $b\leftarrow c=2.5$（区間は $[1,2.5]$ に狭まる）。

2回目： 中点は $c=\frac{1+2.5}{2}=1.75$。同じように代入して

$$f(1.75)=1.75^2+1.75-6=3.0625+1.75-6=-1.1875$$

$f(c)<0$ なので $a\leftarrow c=1.75$（区間は $[1.75,2.5]$ に狭まる）。

1. 表

回	$a$	$b$	$c$	$f(c)$
1回目	1.00	4.00	2.50	2.75
2回目	1.00	2.50	1.75	$-1.1875$

（$f(c)$ は $-1.1875$ が正確な値。「小数点以下2桁」に従うなら $-1.19$ と書く。）

2. プログラムの空欄

空欄	答え	手順との対応
(a)	c = (a + b) / 2	(1) 中点を求める
(b)	if (f(c) > 0)	(2)(A) の判定
(c)	b = c	(2)(A) の代入
(d)	else if (f(c) < 0)	(2)(B) の判定
(e)	a = c	(2)(B) の代入
(f)	return x * x + x - 6	$f(x)=x^2+x-6$

3. 条件判定の修正

もとの手順	修正後
$f(c)>0$ ならば、$b$ に $c$ の値を代入	$f(a)\times f(c)<0$ ならば、$b$ に $c$ の値を代入
$f(c)<0$ ならば、$a$ に $c$ の値を代入	$f(b)\times f(c)<0$ ならば、$a$ に $c$ の値を代入

（プログラムなら if (f(a) * f(c) < 0) { b = c; } else if (f(b) * f(c) < 0) { a = c; }）

• 2回目の $a$ を $1.75$ と書かない。2回目の行に書く $a,b$ はその回の計算に使った値なので $a=1.00$, $b=2.50$。$a\leftarrow 1.75$ は2回目の結果であり、3回目の行に載る値。

• 修正のポイントは「$f(c)$ 単独の符号」をやめて「両端との符号の積」にすること。$f(a)\cdot f(c)<0$ は「$a$ と $c$ の間に解がある」という意味で、関数が右上がりでも右下がりでも成立する。

• $f(a)\times f(c)>0$ で判定しない。符号が同じ＝その区間に解が無いという意味なので、残すべきなのは積が負の側。

ニュートン・ラプソン法

式の導出（覚えるより導けるようにする）： 点 ${\mathrm{P}}_1=(x_1,f(x_1))$ における接線の傾きは $f^{\prime }(x_1)$ なので、接線の方程式は $y=f^{\prime }(x_1)(x-x_1)+f(x_1)$。$x$ 軸との交点は $y=0$ を代入して

$$\begin{array}{rl}0& =f^{\prime }(x_1)(x-x_1)+f(x_1)⟹x-x_1=-\frac{f(x_1)}{f^{\prime }(x_1)}\\ & ⟹x_2=x_1-\frac{f(x_1)}{f^{\prime }(x_1)}⟹x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}\end{array}$$

点 ${\mathrm{P}}_1$ における接線の傾きが $f^{\prime }(x_1)$。その接線と $x$ 軸の交点が次の点 $x_2$ で、$x_1$ より解 $x_0$ に近い。

ニュートン法の図の読み取り・反復計算・プログラムの完成

出題：令和6年度 問5(1)〜(4)（3点・4点・4点・15点＝26点）。

方程式を求める方法として、ニュートン・ラプソン法（以下ニュートン法）と呼ばれる方法がある。下記の文を読み問に答えよ。

ニュートン法は方程式 $f(x)=0$ の解 $x_0$ を求めるためのアルゴリズムである。図に示すように、初期値 $x_1$ を定め、 その垂線と $y=f(x)$ の交点を とする。この を通る を引き、さらに $x$ 軸との交点を とする。 $x_1$ より が解 $x_0$ に近づいていることが図より分かる。同様な操作によって、$x_n$ から $x_{n+1}$ を求めていくことで、 最終的には解 $x_0$ に限りなく近づく。

実際には $\left|f(x_{n+1})\right|$ が一定の値 $\epsilon$ より小さくなったら計算を終了し $x_{n+1}$ を解の近似値として扱う。

1. 文中の空欄 (a)–(c) に入る式、語句を図中から選び、示せ。

2. $x_n$ と $x_{n+1}$ の関係式を示せ。

3. 上記の文章と問1, 2 の解答を用いて、下記の方程式について、ニュートン法のアルゴリズムを2回行え。初期値 $x_1$ は 5.0 とする。 $f(x)=x^2+2x-8$

4. 上記の計算を行うためのプログラム3について、プログラム中の空欄を埋め、プログラムを完成せよ。

プログラム3

#include<stdio.h>
#include<math.h>
#define EPS 1.0e-6

double f(double x);
double df(double x);

int main(void)
{
    double x1, x2;
    x1 = 5;

    while (1) { //無限ループ
        //ニュートン法による計算
        ___(A)___;
        ___(B)___;
        ___(C)___;
    }
    printf("解は x=%f", x2);
    return 0;
}

double f(double x)
{
    ___(D)___;
}

double df(double x)
{
    ___(E)___;
}

問3の表

$x_n$	$f(x)$	$f^{\prime }(x)$	$x_{n+1}$
5.0

図中に示されている式・語句：
${\mathrm{P}}_1$、$f^{\prime }(x_1)$（点 ${\mathrm{P}}_1$ における傾き）、接線、 接線の方程式 $y=f^{\prime }(x_1)(x-x_1)+f(x_1)$、 接線と $x$ 軸の交点 $x_2=x_1-f(x_1)/f^{\prime }(x_1)$、$x_0$、$x_1$、$x_2$

方針（問3）： $f(x)=x^2+2x-8=(x+4)(x-2)$ なので真の解は $x=2$（と $-4$）。 $x_1=5$ から始めれば $x=2$ に近づくはず、という検算の当てをつけてから計算する。 導関数は $f^{\prime }(x)=2x+2$。

解法（問3）：

$$\begin{array}{rl}\text{1回目：}& f(5.0)=25+10-8=27,f^{\prime }(5.0)=2\cdot 5+2=12\\ & x_2=5.0-\frac{27}{12}=5.0-2.25=2.75\\ \text{2回目：}& f(2.75)=7.5625+5.5-8=5.0625,f^{\prime }(2.75)=2\cdot 2.75+2=7.5\\ & x_3=2.75-\frac{5.0625}{7.5}=2.75-0.675=2.075\end{array}$$

問	答え
1	(a) ${\mathrm{P}}_1$ (b) 接線 (c) $x_2$
2	$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$

3. 表

回	$x_n$	$f(x)$	$f^{\prime }(x)$	$x_{n+1}$
1回目	5.0	27.0	12.0	2.75
2回目	2.75	5.0625	7.50	2.075

4. プログラムの空欄

空欄	答え	意味
(A)	x2 = x1 - f(x1) / df(x1);	反復の式
(B)	if (fabs(f(x2)) < EPS) { break; }	終了条件
(C)	x1 = x2;	次の回に備えて更新
(D)	return x * x + 2 * x - 8;	$f(x)=x^2+2x-8$
(E)	return 2 * x + 2;	$f^{\prime }(x)=2x+2$

• (C) の x1 = x2; を落とすと無限ループになる。同じ $x_1$ で同じ $x_2$ を計算し続けるだけになる。反復のプログラムは「更新の行」が必ずあると覚える。

• (B) の判定は$f(x_2)$（新しい方）で行う。$f(x_1)$ で判定すると1回ぶん遅れる。

• 導関数を自分で微分するのを忘れない。$f(x)=x^2+2x-8$ なら $f^{\prime }(x)=2x+2$。定数 $-8$ は消える。

第IX部 数値積分（台形則）

長方形近似から台形則へ

1区間を長方形で近似すると誤差が大きい。左端の高さ $S_{a1}=f(x_1)\Delta x$ と右端の高さ $S_{b1}=f(x_2)\Delta x$ は逆方向にずれるので、平均を取ると精度が上がる。

$$S_1=\frac{S_{a1}+S_{b1}}{2}=\frac{f(x_1)\Delta x+f(x_2)\Delta x}{2}=\frac{f(x_1)+f(x_2)}{2}\Delta x$$

これが台形の面積（上底＋下底）$\times$ 高さ $÷2$ そのもの。

$$S=S_1+S_2+\cdots +S_n=\sum _{k=1}^n{S}_k,\Delta x=\frac{x_e-x_s}{n},x_k=x_s+(k-1)\Delta x$$

分点の式から $x_2=x_1+\Delta x$、$x_3=x_1+2\Delta x$（$x_1=x_s$ が出発点）。

長方形の平均として台形則を導き、プログラムを完成させる

出題：令和6年度 問6(1)(2)（8点・9点）。

数値積分法に関する文章を読み、以下の問に答えよ。

数値積分法は、求める区間を細かく分割し、各区間の面積の和より積分の近似値を求める手法である。 図1に示されたような、長方形を用いた方法は、誤差が大きい。誤差を軽減する方法を以下のように考える。

図1より、面積 $S_{a1}$ は である。同様に図2より面積 $S_{b1}$ = となる。 この区間の面積の真値は $S_{a1}$ と $S_{b1}$ の間に存在するはずである。 このことを利用し、この区間の面積 $S_1$ を $S_{a1}$ と $S_{b1}$ の平均値として $S_1$ = と計算を行なうこととする。

$n$ 分割された、$x_{n+1}$ までの区間全体の面積 $S$ は、上記のような $S_k$ を用いて、$S$ = となる。

1. 文章に入る式を示せ。

2. 以下のプログラムは文章の考え方に従って、面積を計算するプログラムである。プログラムの空欄を埋め、プログラムを完成せよ。

#include <stdio.h>
#include <math.h>
double f(double);
int main(void)
{
    double Sa = 0, Sb = 0, S = 0;
    double start = 0, end = 1;//区間の値は暫定値
    int i, n = 10; //分割数は暫定値
    double dx = (end - start) / n;
    for (i = 1; i <= n; i++) {
        ___(A)___;
        ___(B)___;
        ___(C)___;
    }
    printf("区間(%f,%f) の面積=%.5f\n", start, end, S);
    return 0;
}
double f(double x)
{
    //目的の関数が入る
}

方針： 変数名が Sa, Sb, S と3つあり、空欄も3つ。 つまり「左端の長方形」「右端の長方形」「平均を足し込む」の3行をそのまま書けばよい。 $i$ 番目の区間の左端は $x_i=\text{start}+(i-1)\Delta x$、右端は $x_{i+1}=\text{start}+i\Delta x$。 ループが i = 1 から始まっているので、この形になる。

1. 文章に入る式

空欄	答え	意味
(a)	$S_{a1}=f(x_1)\Delta x$	左端の高さ $\times$ 幅
(b)	$S_{b1}=f(x_2)\Delta x$	右端の高さ $\times$ 幅
(c)	$S_1=\frac{S_{a1}+S_{b1}}{2}$	2つの長方形の平均
(d)	$S=S_1+S_2+\cdots +S_n$	全区間の和

2. プログラムの空欄

空欄	答え
(A)	Sa = f(start + (i - 1) * dx) * dx;
(B)	Sb = f(start + i * dx) * dx;
(C)	S += (Sa + Sb) / 2.0;

台形の面積として書き、数値を計算し、プログラムを完成させる

出題：令和7年度 問5(1)〜(4)（8点・4点・4点・8点＝24点）。

数値積分法に関する文章を読み、以下の問に答えよ。

数値積分法は、求める区間を細かく分割し、各区間の面積の和より積分の近似値を求める手法である。 下図に示されたように、一区間の面積を台形の面積で近似する方法を考える。

下図内の (a), (b) はそれぞれ 、 であることから、区間 $[x_1,x_2]$ の台形の面積 $S_1$ は である。

積分区間を $n$ 分割された $x_{n+1}$ までの区間全体の面積 $S$ は、上記のような $S_k$（$S_1,S_2$ など）を用いて、$S$ = となる。

1. 文章に入る式を示せ。

2. 文章の考え方を用いて、$f(x)=-x^2+1$ について、区間 $[0,0.2]$、分割数 2（$\Delta x=0.1$）として積分値を求めよ。

3. 図において $x_3$ を、$x_1$ と $\Delta x$ を用いて表せ。

4. プログラム5は上記の文章の考え方に従って、問2の積分を計算するプログラムである。プログラムの空欄を埋め、プログラムを完成せよ。

問2の表

区間	区間面積（小数点以下3桁）
$0.0-0.1$
$0.1-0.2$
積分値 $\to$

プログラム5

#include <stdio.h>
#include <math.h>
double f(double);
int main(void)
{
    double S = 0;
    double xs = 0, xe = 0.2;
    int i, n = 2;
    double dx = ___(a)___;
    for (___(b)___) {
        S += ___(c)___;
    }
    printf("区間(%f,%f) の面積=%.5f\n",
           xs, xe, S);
    return 0;
}
double f(double x)
{
    ___(d)___;
}

図では、$x$ 軸上に $x_1,x_2,x_3$ が幅 $\Delta x$ 刻みで並び、(a) は $x_1$ での高さ、(b) は $x_2$ での高さを示している。$S_1$ が区間 $[x_1,x_2]$、$S_2$ が区間 $[x_2,x_3]$ の面積。

方針（問2）： $\Delta x=0.1$ なので分点は $x_1=0$, $x_2=0.1$, $x_3=0.2$。 まず3つの高さを先に全部計算してから台形の式に入れると計算間違いが減る。

$$f(0)=-0^2+1=1,f(0.1)=-0.01+1=0.99,f(0.2)=-0.04+1=0.96$$

解法（問2）：

$$\begin{array}{rl}{S}_1& =\frac{f(0)+f(0.1)}{2}\Delta x=\frac{1+0.99}{2}\times 0.1=\frac{1.99}{2}\times 0.1\\ & =0.995\times 0.1=0.0995\\ S_2& =\frac{f(0.1)+f(0.2)}{2}\Delta x=\frac{0.99+0.96}{2}\times 0.1=\frac{1.95}{2}\times 0.1\\ & =0.975\times 0.1=0.0975\\ S& =S_1+S_2=0.0995+0.0975=0.1970\end{array}$$

検算： 真の値は ${\int }_0^{0.2}(-x^2+1)\mathrm{d}x={\left[-\frac{x^3}{3}+x\right]}_0^{0.2}=-\frac{0.008}{3}+0.2=0.19733\cdots$。 上に凸な関数を台形で近似すると真の値より少し小さく出るので、$0.1970<0.19733$ は妥当。

1. 文章に入る式

空欄	答え	意味
	$f(x_1)$	(a) は $x_1$ での高さ
	$f(x_2)$	(b) は $x_2$ での高さ
	$S_1=\frac{f(x_1)+f(x_2)}{2}\Delta x$	台形の面積（上底＋下底）$\times$高さ$÷2$
	$S=S_1+S_2+\cdots +S_n$	全区間の和

3. $x_3=x_1+2\Delta x$

2. 表

区間	正確な値	小数点以下3桁
$0.0-0.1$	0.0995	0.100
$0.1-0.2$	0.0975	0.098
積分値 $\to$	0.1970	0.197

4. プログラムの空欄

空欄	答え
(a)	(xe - xs) / n
(b)	i = 1; i <= n; i++
(c)	(f(xs + (i - 1) * dx) + f(xs + i * dx)) * dx / 2
(d)	return -x * x + 1

• で$\Delta x$ を掛け忘れるのが最頻出。$\frac{f(x_1)+f(x_2)}{2}$ は平均の高さで、面積ではない。「面積 $S_1$ は」と問われているので$\times \Delta x$ まで書く。

• (a) を (xs + xe) / 2 と書かない。求めるのは刻み幅なので区間の長さ $÷$ 分割数。

• 途中で丸めてから足さない。$0.100+0.098=0.198$ になってしまう。正確な値で足してから最後に丸めると $0.197$。

暗記チェック（赤シート用）

(1) ビルドとファイル・ヘッダ

問い	答え
#include・#define を展開する工程	プリプロセス
ソースコードを CPU が理解できる言語に変換する操作	コンパイル
変換済みのファイル同士やライブラリの関数を接続する操作	リンク
CPU が理解できる言語に変換したが、実行はできないファイル	オブジェクトファイル
全ての処理を終え、PC が実行できる形式のファイル	実行ファイル
#include"a.h" の動作	a.h を読み込み、その場に挿入する
" " と < > の違い	" " はまず同じフォルダを探す／< > は標準フォルダだけ
ヘッダファイルに書くもの（3つ）	構造体の定義・typedef・プロトタイプ宣言
ヘッダファイルに書いてはいけないもの	関数の本体・変数の定義（二重定義になる）

(2) スコープと記憶クラス

問い	答え
関数の外で宣言した int x; のスコープ	プログラム全体（すべての関数内）
関数の外で宣言した static int x; のスコープ	宣言したファイルの中だけ
関数の中の static int y = 0; の効果	初期化は1回だけ・値をプログラム終了まで持ち越す
extern int x; の意味	他のファイルにある大域変数を借りて使う宣言（実体を作らない）
大域変数が推奨されない理由	どの関数からでも書き換えられ、どこで壊れたか追えない
実装用の変数を static にするメリット	main 側からデータを直接変更できなくなる
引数で受け取った変数のスコープ	その関数の中だけ

(3) データ構造

問い	答え
スタックの出入りの順序	LIFO（後から入れたものが先に出る）
キューの出入りの順序	FIFO（先に入れたものが先に出る）
スタックが空のときの top	$-1$
キューが空のときの tail	0
push の2行の順序	top++; → stack[top] = dat;
put の2行の順序	queue[tail] = dat; → tail++;
pop したあと配列の値は	消えずに残る（top を下げるだけ）
セル1個ぶんの領域を確保する式	temp = (CELL*)malloc(sizeof(CELL));
挿入の2行の順序	temp->next = p->next; → p->next = temp;
削除の3行の順序	temp = p->next; → p->next = temp->next; → free(temp);
空の連結リストの中身	head を1つ確保して head->next = NULL
malloc と calloc の違い	calloc は個数 $\times$ サイズで確保し、0 で初期化する
calloc の返り値	確保したメモリの先頭アドレス
配列を関数に渡すと渡る値	配列の先頭アドレス

(4) 数値計算法

問い	答え
0.1 を10回足しても 1 にならない理由	2進数で循環小数になり、有限桁で打ち切られるから
実数を比較するときの正しい書き方	fabs(x - a) < EPS（== を使わない）
二分法の中点	$c=\frac{a+b}{2}$
二分法の区間更新（一般形）	$f(a)f(c)<0$ なら $b\leftarrow c$、$f(b)f(c)<0$ なら $a\leftarrow c$
二分法の長所	必ず収束する
ニュートン法の反復式	$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$
その式が出てくる図形的な意味	接線と $x$ 軸の交点を次の点にする
ニュートン法に必要で二分法に不要なもの	導関数 $f^{\prime }(x)$
終了条件（両方共通）	$\left
刻み幅	$\Delta x=\frac{x_e-x_s}{n}$
$k$ 番目の分点	$x_k=x_s+(k-1)\Delta x$（だから $x_3=x_1+2\Delta x$）
左端の長方形の面積	$S_{a1}=f(x_1)\Delta x$
台形則（1区間）	$S_1=\frac{f(x_1)+f(x_2)}{2}\Delta x$
台形則（全体）	$S=S_1+S_2+\cdots +S_n$

1. プログラムの空欄に書いた行の末尾にセミコロンがあるか（if や for の条件だけを書く空欄には付けない）。

2. トレース問題の図と出力順が矛盾していないか。$\uparrow$ が連続する箇所を指でたどって確認する。

3. 反復計算の表の各行が「その回に使った値」になっているか（更新後の値を同じ行に書いていないか）。

4. 数値の丸めを途中でしていないか。最後にだけ丸める。

5. $\Delta x$（幅）を掛け忘れていないか（面積を聞かれているのに高さの平均を書いていないか）。

6. スコープを答える問題で「ファイル内」と「プログラム全体」を取り違えていないか（static が付いていたら必ず「ファイル内」）。