# 情報基礎の教科書 解答

## 3章

### 1. OSが行う典型的な4つの動作を列挙せよ。

4つで足りんの？

### 2. バッチ処理とリアルタイム処理の違いを端的に述べよ。

バッチ処理は複数のジョブをひとまとまりにして処理する機能である。リアルタイム処理は決められた時間内にジョブを完了させる機能である。違いも何もむしろ類似点が見当たらない。

ユーザーが処理に介入できるかどうかかな

### 4. 組込みシステムとPCの違いは何か。

PCは単一ユーザが広い用途において必要に応じて使用することを想定して作られている。組込みシステムは特定の目的で使用される機器に組み込まれたOSで、消費電力を抑えつつリアルタイムに動くことが要求され、かつ人の介入なしに長時間にわたって動作し続けなければならない。

組込みシステムは一つの作業に焦点を合わせることが多いが、PCは汎用コンピュータである。組込みシステムは同時代のPCより多くの資源を持つことがあるが、ほとんど人間の介入なしで厳しい時間制約をもつ。

### 5. マルチタスキングオペレーティングシステムとは何か。

呪文？
1人のユーザが複数のタスクを同時に処理できるようなOS

### 6. PCにおいて、マルチタスキングが有効である状況を述べよ。

まぁ 普通にユーザアプリケーションが複数あるときは有効なのでは

### 7. 身近なコンピュータシステムにおいて、アプリケーションソフトウェアとユーティリティソフトウェアを2つずつ挙げよ。その上で、なぜそのように分類したか説明せよ。

そもそもマシンのソフトウェアは2つに分類できて、アプリケーションソフトウェアとシステムソフトウェアである。そのうちシステムソフトウェアを2つに分類すると、OSとユーティリティソフトウェアとなる。アプリケーションソフトウェアの例は、表計算ソフト、データベースシステム、プログラム開発用ソフトウェア、ゲームなど。ユーティリティソフトウェアはOSに搭載こそされていないものの、コンピュータにはほぼ必須な機能を搭載したソフトウェアであり、データの圧縮や解凍をするソフトウェア、マルチメディアを再生するソフトウェア、ネットワークコミュニケーションを司るソフトウェアなどがこれにあたる。これらの分類は、コンピュータの利用にどれだけその機能が必要であるかに依存する。

### 8. a. OSのユーザインターフェースの役割は何か。 b. OSのカーネルの役割は何か。

a. ユーザインターフェース：ユーザからの要求に応えるための側面のことであり、すなわち役割を答えるなら「ユーザからの要求に応えること」となる。
b. カーネル：OSの内部部分。内部データとアプリケーションを繋ぐ仲介の役割を担っており、コンピュータのリソースを管理しつつ必要に応じてユーザにリソースを割り振る。

### 9. ディレクトリパスX/Y/Zによって示されるディレクトリ構造を述べよ。

hoge

### 10. OSの文脈で使用されるときのプロセスという用語を定義せよ。

OSが処理する作業の最小単位。

### 11. OS中のプロセステーブルには、どのような情報が含まれるか。

プロセステーブルはメモリに格納されたプロセスそれぞれに関するデータを保持するものである。プログラムの実行が要求されるたびにプロセステーブル中に新たなプロセスのエントリを生成する。テーブル中にはプロセスに割り付けられたメモリ領域、プロセスの優先順位、プロセスが準備完了か準備中かといった情報が格納される。

### 12. プロセスが準備完了であるのと待機中であるのとでは、どのように違うのか。

実行可能な状態であるのが準備完了で、外部イベントの発生を待っているがゆえに実行できない状態が待機中である。

### 13. 仮想メモリとメインメモリの違いは何か。

実メモリはもちろん容量が一定であるのに対して、OSではページをうまくやりとりすることによって実際よりも大きな架空のメモリを構成することができる。これを仮想メモリと呼ぶ。

### 14. コンピュータが512MBのメインメモリを持ち、OSは2KBのページを使用して、その2倍の大きさの仮想メモリを生成すると仮定する。何ページ必要か。

512*10^3*2/2

### 15. 2つのプロセスが、同時に同じファイルにアクセスする必要があるとき、どのような問題がタイムシェアリングシステムやマルチタスキングシステムに起こるか。ファイルマネージャが、そのような要求を受け入れる場合があるか。ファイルマネージャが、そのような要求を拒否する場合があるか。

デ　ー　タ　こ　わ　れ　る
受　け　入　れ　る　な
拒　否　し　ろ

これをうまくやるのがセマフォちゃんです

### 16. アプリケーションソフトウェアとシステムソフトウェアの違いは何か。それぞれの例を述べよ。

何か似たような問題なかった？
必須か否か

### 17. マルチプロセッサアーキテクチャの文脈で、ロードバランシングとスケーリングを定義せよ。

ロードバランシング：複数のプロセッサにそれぞれ異なるプロセスを割り当てることができるような場合に、タスクの割り当てを最適化する問題
スケーリング：1つの作業を複数のプロセッサに割り当てられるように分割する問題

ロードバランシング：複数のプロセッサを効率的に使用する
スケーリング：プロセッサの数に合うように、一つの作業を分割する

### 18. ブートプロセスを要約せよ。

1. マシンの起動時に、ROM中に格納されているブートローダと呼ばれるプログラムが実行される。
2. ブートローダの命令に従って、CPUがOSをメインメモリに持ってくる。
3. OSが起動

### 19. なぜブートプロセスが必要なのか。

コンピュータのメインメモリは揮発性をもつ。すなわち、電源を落とすたびに記憶領域が消去される。これに対応するため、コンピュータのメインメモリの一部を不揮発性のROMに置き換えている。OSはメインメモリに格納されるので、電源投入時にメインメモリにOSを移す工程が必要であり、これがブートプロセスである。

ブートプロセスを用いない場合、不揮発性のROMにOSを搭載することになるが、OSはセキュリティ保持や最新のものにアップグレードされることが多いため不揮発性のストレージに保存するのは効率が悪い。そのためブートプロセスが必要となる。

### 20. 身近のPCで、起動したときに起きる一連の事象を述べよ。実際にブートプロセスが始まる前に、どのようなメッセージがコンピュータスクリーンに現れるか述べよ。これらのメッセージを書いているのは、どのソフトウェアか。

hoge
マシン名のロゴとか出るよね
メッセージ書いてるのは多分ブートローダ

### 21.22.計算問題

### 23. マルチプログラミングオペレーティングシステムが50msのタイムスライスを割り当てると仮定する。ディスクの読み書きヘッドを求めるトラック上に置くのに8ms、そして求めるデータが読み書きヘッドの下に回転してくるのに17msかかるとすると、ディスクからの読み取り演算が行われるのを待って、どれだけのプログラムのタイムスライスが費やされるか。マシンが1ナノ秒に10個の命令を実行できるなら、この待ち時間に幾つの命令を実行できるか。

wakarazu
25msが使われているので、残り25msで10命令/nsがいくつできるかという問題ですかね。

### 24. マルチタスキングオペレーティングシステムが、アクセスの調整をしなければならない5つの資源を列挙せよ

### 25.
I/Oバウンド。待っている間にCPUを使わない部分の動作を行えるため

### 26.
計算バウンドのプロセスで計算している間、I/Oバウンドの処理も行えるのでこちらの方がスループットが良い。

### 27.　プロセスのタイムスライスが終了したとき、OSのディスパッチャが何をするかを書き出せ。
プロセステーブル中の準備完了になっているプロセスの中で最も優先順位の高いプロセスを選択してタイマー回路を再起動し、選択したプロセスがそのタイムスライスを始められるようにする。

### 28. プロセス状態には、どのような情報が含まれているか。
プログラムカウンタの値、他のCPUレジスタや関連するメモリセルの値が含まれる。

### 29.マルチプログラミングシステムにおいてプロセスが割り当てられたタイムスライス全体を消費しない状況を特定せよ

### 30.プロセスに割り込みが発生したときに実行される主要イベントを列挙
CPUが割り込みシグナルを受け取ると、現在マシンサイクルを完了し、現在プロセス中の位置を保存してから割り込みハンドラと呼ばれるプログラムを実行。
ディスパッチャが割り込みしたプロセスに資源の割り当てを行う

### 31.以下の場合、OSにどう指示すべきか
#### a.ファイルをある場所から別の場所へ複写するとき
#### b.ディスクのディレクトリを見たいとき
#### c.プログラムを実行したいとき

### 32.以下の問いに答えよ。
#### a.OSはどのようにしてユーザだけがアクセスするように制限しているか
#### b.現在どのようなプロセスがプロセステーブルにあるかを知りたいとき、OSにどう指示すべきか。
#### c.マシンの他のユーザがあなたのファイルにアクセスしないようにするため、OSにどう指示するか。

### 33.テストアンドセット命令の重要性について述べよ。
一つの命令として実装されていることで、CPUにフラグの値を取り出し、受け取った値を調べてからフラグをセットするという一連の動作が分割されなくなる。これにより、現在のプロセスが使用している資源を他のプロセスが使用できないことが担保される

### 34.
デッドロックの3条件：
1. 共有不能な資源を巡って競合がある
2. 各プロセスが資源を部分的に要求できる。つまりある資源を先に受け取ったプロセスは、後に追加の要求を出せる
3. いったん資源を割り当てられたならば、強制的に取り上げることはできない

### 35.
a. 1か2かなぁ
b. 3
c. 3
d. 1

### 36.
3?

### 37.

### 38.

### 39.プリンタの出力にスプールするプロセスでキューがどのように使用されるか。

### 40. タイムスライスを待っているプロセスが、タイムスライスをいつまでも得られないことをスタベーションにあるという。

### 41. デッドロックとスタベーションはどこが類似しているか。違いは何か。

### 42. マルチプログラミングシステムにおいて、タイムスライスの長さをどんどん短くするとどのような問題が生じるか。どんどん長くするとどうか。

短くすると、プロセス間の切り替えのオーバーヘッドが大きくなる。長くすると時分割の意味がない。

### 43.

### 44.

割込み不能　割込み可能　TS

### 45.

権限まわりの話

### 46.
セマフォ

### 47.
(38^8)*1

### 48.

## 5章

### 5
停止しない

### 6
平行なので交わらない

### 7,8
repeat
(Countの値を印字する
Count <- Count + 1)
until (Count = 7)

### 9
条件文をひっくり返す

### 10
1桁目から順番に数字を見ていく。1～n桁目までの数字が降順ソートになっていればn+1桁目を見る。降順ソートになっていない最初のn+1桁目において、「n+1桁目の数字より大きく1～n桁目に含まれる数字のうち最小のもの」とn+1桁目の数字をswapする。その後、1～n桁目の数字を逆順にする。

### 11
i <- 0
in は約数列挙したい数字
while(i <=in) do
i <- i + 1
if(in % i == 0)then(iを出力)

### 12

### 13
計算機が読むか人間が読むかの違い

### 14
マクロとミクロ

### 17
全探索

### 22
1 1 2 3 5 8 13 21 34 55 89

### 23
1 1 2 3 5 8 13 21 34 55 89

### 26
(1+...+6000)/6000=3000.5

### 27
Count >= 5
Count = 1
Count >= 5 OR Total >= 56

### 28
2回
6->無限ループ

### 29
0.1は正確に表現できないので、よほど運が良くない限りCountとlは等しくならず、無限ループする

### 30
procedure Euc(x,y)
if(x>0 and y>0)
then(
if(y>x)
then 手続きEuc(y,x)を呼び出す
else (
手続きEuc(y/x, y%x)を呼び出す
)
)
else("最大公約数はx"と出力する)

### 31
逆順になる

### 32
停止条件：Countが5になる

### 33
N not 5

### 34
3124

### 35
201-1

### 36
1から順に、素因数が2か3のみである数かどうか確かめていく

### 37
a.二分探索
b.逐次探索
c.逐次探索
d.二分探索
e.5回/１回

### 38
手続きfact(n)を用意し、nが1以上ならfact(n-1)を呼び出す。nが0なら1を代入する

### 39
a.4つソートして、5つ目を二分探索して挿入
b.手続きmerge(list)を用意する
* listのサイズが4より大きいなら、listをほぼ半分に分割し、それぞれのリストについてmergeを呼び出す
* 4以下なら、listをソートしておわり
* 一つ目のアレで得られた2つのリストをマージする。すなわち、先頭同士を比較してソートされた列にする

### 40
手続きhanoi(n)は、
* nが1のとき、円盤を3番目の杭に移す
* それ以外のとき、hanoi(n-1)を呼び出し、n-1枚の円盤を別の杭に移す。残った1枚の円盤を空いている杭に移し、hanoi(n-1)を呼び出す

### 41
円盤iについて、
* i=1
* iが奇数かつ時計回りに動かすことが出来るなら動かす。
* iが偶数かつ反時計回りに動かすことが出来るなら動かす。
* そのいずれでもない場合、i+1について調べる。

### 42
tmp <- 1
while(i<=30) do(
tmpの値を印字する;
tmp <- tmp*2
i <- i+1
)

手続きsal(n)を用意し、
* nが1なら1を印字し返す
* nが2以上なら、sal(n-1)*2を印字し返す

tmpを1として
procedure sal(n)
if(n not 30)
then (tmpの値を印字する
tmp <- tmp*2
salをn+1の値に適用する;)
sal(1)を呼ぶ

### 43
* 近そうな数字を思い浮かべ、tmpに代入する
* tmpと(元の数をtmpで割った数)の平均をtmpに代入し、その二乗と求めたい数を比較する。誤差が一定値以下ならループをやめる

### 44
abcde
手続きrekkyo(list)を用意して、
* listのサイズが2なら、それらの2つの組み合わせを返す
* それ以外のとき、listの要素それぞれについて、rekkyo(リストのサイズ-1)の先頭に残った1文字を付加したものを出力する

### 45
文字列を頭から減らしていって、サイズが0になった文字列はリストから消す。リストのサイズが1になったらそれを出力。同時に0になった場合、最後まで残っていた文字列を1つ出力する。

### 46
最小の5個および最大の5個を保持するリストを用意しておいて、順に見ていく。更新する余地がある要素を見つけたら弾き出す。

### 47
辞書順の逆順

### 48
12
4000

### 49
加算：$O(n)$
乗算：$O(n^2)$

### 50
ソートして左右に分ける　nlogn
全探索 $2^n$

### 51
DP

### 52
Yが0になるからループは停止しない

### 53
正しいです　正しいと思います

### 54
等しい場合を考えていない

### 55
最後の要素が最大のときにこまる

### 56
ループ不変表明：testentryがリストの要素
ループ停止条件：testentry>=testvalue

### 57
Z=X-J
これとループ停止条件J=YからZ=X-Yが示される

## 6章

### 1 プログラミング言語がマシン独立であるとは、どういう意味か。

特定のマシンの性質に依存しない言語であること。なお、第三世代のプログラミング言語はそれ以前の世代の言語と、基本命令が高レベルであること、言語がマシン独立であることの2点において異なっている。

### 2
次の疑似コードプログラムを、マシン語に翻訳せよ。

x <- 0;
while(x<3) do
(x <- x+1)

2100
2003
2201
B10B
5112
C000

### 3, 4 省略
### 5 問題4で文を翻訳するのに、なぜ変数のデータ型を指定する必要があったのか。多くの高レベルプログラミング言語で、なぜプログラマがプログラムの初めに変数の型を指定する必要があるのか。

加算演算ができる型とできない型があるから。プログラムの初めに型を指定することで、実際に計算する前に演算ができない場合をえらーとして報告することができる。

### 6 4つのプログラミングパラダイムを列挙して説明せよ。

「命令型パラダイム」プログラミングのプロセスを、一連の命令を作成するものと位置づけ、命令列に従うことで求める結果が作成されるようにデータを加工していくもの。
「宣言型パラダイム」問題を解くようなアルゴリズムを記述するのではなく、解くべき問題を記述するもの。命令型パラダイムとは真逆の性質を持つと言える。
「関数型パラダイム」プログラムを、入力を受け取り出力を返すものとして考える。
「オブジェクト指向パラダイム」特定の値にメソッドを付加したオブジェクトと呼ばれる単位を用いて、オブジェクト同士が総合作用することによって問題が解決される。

### 7
4つの値の最小値。

### 8
dcbaabcd

### 9
預金の残高、支出と日時と概要の組の配列

### 10 マシン語とアセンブリ言語の違いを要約せよ。
アセンブリ言語はマシン語を1対1対応で多少分かりやすい形に翻訳したものであるので、本質的には同じである。異なるのはそれらを表現する構文そのものだけである。

### 11 省略

### 12
定数化を行わないことで、プログラム中でAirportAltの値が書き換わり、意図しないバグが起こり得るから。

### 13 宣言文と命令文の違いを要約せよ。
宣言文はデータを参照するのに使用される名前のような、プログラム中で使用される用語を定義するものである。命令文は宣言文で宣言したデータなどを適宜用いつつ、アルゴリズムのステップを記述する。ちなみにプログラム中の文は3種類あり、宣言文、命令文とあとひとつはコメント文である。

### 14 リテラル、定数、変数の違いを説明せよ。
明示的に出現する値をリテラルと呼ぶ。リテラルが代入されているため本質的には用途に違いがないが、可読性や保守性の向上のために名前の付けられているものを定数、定数と異なりプログラム中で書き換えることができる名前付きの値を変数と呼ぶ。

### 15 a. 演算子優先順位とは何か。　b. 演算子優先順位によって、式6+2×3の値はどのようになるか。
ある演算子と他の演算子が並列されているとき、どちらを先に評価するかを定めた順位。12になる。

### 16 構造化プログラミングとは何か。
言語の制御文を適切にしようとすることを組み込んだ設計方法論。制御文とは、プログラムの実行順序を上から逐次的に行うような状態を崩して、プログラムの実行順序を変えるものである。

### 17 if文中の=と代入文の=の違い
比較と代入(比較に=を使うなよ)

### 18 フローチャートを書け
条件分はひし形で記述する。分岐先の矢印は2つあり、それぞれの矢印の横に「真」「偽」と書く。

### 19
xに2を代入
while(xが8より小さい) do(xに1を加える)

### 20
楽譜に親しくないので無回答でAC

### 21
ifでごちゃごちゃやる

### 22
CASE W IS
WHEN 5 => Z<-7;
WHEN 6 => Y<-7;
WHEN 7 => X<-7;
WHEN OTHERS => ;
END CASE

### 23
if (X>5)
then (X=X+2)
else (X=X+1)

### 24 次の動作を実行する、命令型とオブジェクト指向型のプログラミング言語の基本制御構造を要約せよ。 a. 次に実行する命令を決定する　b. 一群の命令を繰り返す　c. 変数の値を変える
？

### 25 コンパイラとインタプリタの違いを要約せよ。
コンパイラはプログラミング言語によって記述されたコードを一度機械語に翻訳し、それを実行することでコードの実行を行うもの。インタプリタは命令を逐一変換しながら実行する。

### 26
型エラー

### 27 プログラミング言語が強く型付けされるとは、何を意味しているか。
プログラムが実行する全ての動作が型の合致するデータ同士でのみ行われるように設計されていること。

### 28 大きな配列を、なぜ値渡しで手続きに渡さないのか。
配列中の全ての値を値渡しすると配列の大きさ分の時間がかかる。参照渡しをすることで先頭のアドレスを渡すだけで済む。

### 29
値渡し：7 5 手続きが呼び出されると、データの複製が手続きに渡される。手続き中でx=7が出力されたのち、x=7のデータが破棄され、xは5のまま。
参照渡し：7 7 手続きが呼び出されるとき、仮引数は実引数の参照である。手続きが適用されると、xは7に変更され、それが出力される。

### 30
値渡し：5 7 5
参照渡し：7 7 7 グローバル変数は手続きが呼び出された時点で7に変更される

### 31
手続きが終了した時点でグローバル変数xに7が代入されるので、5 7 7となる

### 32 a.参照渡しと比較して、引数の値渡しの利点は何か。　b.値渡しと比較して、引数の参照渡しの利点は何か。
a. 元の値は変更されないので、データを変えたくないときに用いることができる
b. 手続き側でデータの変更ができる。リストのソートやスワップに対して有用　大きな値を引数にとるとき、値渡しはオーバーヘッドになる

### 33
代入のタイミングが曖昧

### 34
NumEmplを5に変更するだけでよい。元のコードは、従業員の数である5と平日の数である5の区別がつきにくい。

### 35
a. 形式言語は厳密な文法で定義されるものであるのに対し、自然言語は形式的な文法解析なしに長い時を経て進化してきたものである

### 36
hoge

### 37
hoge

### 38
hoge

### 39
hoge

### 40
yes 文 noとyes noで分岐

### 41
これパンピングレンマで示せるんだっけ？

### 42
xx...xyxx...x 前半と後半に登場するxの数は同じ

### 43
hogeっとるな

### 44
うん

### 45
条件節内でxをレジスタにロードしているので、そのxをそのまま使えばいい

### 46
y <- 5
z <- 9
ワロタ　鳥頭か？

### 47
x <- 5

### 48
類似点：特定の値を保持し、メソッドにより何らかの値を取り出したりできる
異なっている点はそんなに多くないが、型はもともと用意されているもので、クラスはユーザが実装するものである、とか、「変数」「インスタンス」という呼び名の違い

### 49
建物のクラスは例えば「階数」みたいなデータを保持している。継承により作られる新規クラス「一軒家」を考えてみると、「階数」はそのまま継承したうえで、例えば「表札」みたいなデータを新たに保持するようなクラスを作ることが出来る。

### 50
公開部は他のいずれのプログラムもアクセスできる部分であるのに対し、非公開部はアクセスが制限される。

### 51
a. 例えば建物のクラスを考えたとき、「階数」などのデータが外部から参照されてしまうと、それを自由に書き換えることができてしまう。現実問題として建物の階数が突然変化することはないので、このような場合は「階数はデータとして保持し、パブリックなメソッドとして階数を取得する」のような形態をとるべきである。
b. そのような心配がないときは公開してもよい。例えば2次元座標クラスを考えると、それらの値はいつでも参照し変更できるようにしておくのが吉である。
c. クラスの中でのみ用いるメソッド。あるクラスについて、メソッドA,B,Cがあり、パブリックメソッドDはA,Bを、EはB,Cを利用しているとする。A,B,Cはいずれも外部から参照されることを意図していないメソッドであるとき、いずれもプライベートにすべきである。原理的にはD,E中に直接A,BおよびB,Cの中身を書いても良いのだが、Bを2回書くのは無駄であるので、このように分割したメソッドを参照するような形式をとっている。保守の観点からすれば、これらの小さいメソッドA,B,Cを再利用する機会を得ることにもなる。
d. 非公開変数や非公開メソッドは公開メソッドにより参照したりする。

### 52
歩く速さは一定で、時間tが1経過するごとにいずれかの行動をとるようなクラスを考える。
グローバル変数 t：時刻　n：ロビーにいる人数　配列a：座標のペアを保持。保持されたデータはいずれも壁などの通行不可オブジェクトを指す。
インスタンス変数：座標x, y プライベート
メソッド：
コンストラクタ：n+1, x=0, y=0(入口の座標を原点とする)　(0,0)をaの末尾に追加
座標の取得：x,yをそのまま返す
右に一歩進む：aを走査し、(x+1,y)が配列中に含まれていなければx+1 t+1
左：x-1 t+1
上：y+1 t+1
下：y-1 t+1
立ち止まって時間の経過を待つ：t+1
デストラクタ：n-1　リストから(x,y)を削除

### 53
排他的で正しいデータへのアクセスを実現するため、アクセス制御の機能をもつように補強されたデータ項目のこと。クリティカルセクションを用いた排他的アクセスの実現は、欠点として排他制御がプログラムの様々な部分に散在してしまう。この問題を解決するため、データ側がアクセス制御に加担するような仕組みが開発された。

### 54
複数の動作が見せかけ並列的に行われているように見せることができる
データへのアクセス制御をうまく制限することで、データが矛盾しないようにできる

### 55
1,2よりQ or T(6とする)
6,5よりP or T(7とする)
7,4よりP(8)
3,8より空節

### 56
1,2よりT(6)
6,4よりQ(7)
3,7よりP(8)
5,8よりR(9)
9,1より空節。矛盾

### 57
練習問題3の解答を載せておく。

female(carol).
female(sue).
male(bill).
male(john).
parent(john,carol).
parent(sue,carol).
mother(X,Y) :- female(X), parent(X,Y).
father(X,Y) :- male(X), parent(X,Y).

無関係なのに駆り出されてるbill　ウケるな

家族関係増やすのめんどいので規則だけ
parents(X,Y,Z) :- parent(X,Z), parent(Y,Z), female(X), male(Y).

### 58
・デイビッドはスポーツが好きな人が好きだ
・アリスはデイビッドが好きな人が好きだ
アリスはスポーツと音楽が好き、4つ目の規則からデイビッドはアリスが好き。5つ目の規則からアリスはアリスのことが好きである。自己愛

### 59
コンピュータ内で0.01を正確に記述することは出来ず、Xは1.00に等しくならない。よって無限ループが起こる

## 8章

### 2
39 58 59

### 3
40

### 4
挿入・削除に時間がかかる

### 5

### 6

### 7
15 19 21 11 ...

### 8
39を40
33を36 ...

### 9
JANE

### 10
1

### 11
後半のリストを頭から順に前半のリスト以降のメモリに格納していく

### 12
リスト長のメモリを確保して、頭からマージソートの要領で比較していく
2つ目のリストを頭から見ていって、O(1)の挿入を繰り返す

### 13
全てのアドレスを記憶しつつ、最後まで到達したら逆順にポインタを繋ぐ

### 14
全てのアドレスを記憶する際にスタックを用いる
手続きf(list)
listが空なら何もしない
そうでなければ、listの先頭をとってtopとする
f(listからtopを除いたもの)
topを印字

### 15
63 null 66 69 ...

### 16
A

### 17
FCAD

### 18
スタックをもう一つ用意し、他はポップしつつ保持してプッシュ、最下部だけポップして消す

### 19
popして比較

### 20
完全に逆順にすることができる
好きな順番にできる

### 21

### 22
変更に時間がかかるから

### 23
頭から尾

### 24
一旦放置

### 25
13 18

### 26
DPFKLAGR
ヘッドであるところのUが消え、元の文字列とは異なってしまう

### 27
メモリを確保して循環キューを作る　ポインタ2つ分の領域も確保

### 28
aとbとする
aを別の方へ移動
a側のキューをヘッドにaが来るまで回す
bを同じキューのテールに移動
bの下にaを移動

### 29
W
J F
M X G

### 30
0 39 0 0 33 45 0 0 30 36 0 0

### 31
procedure Search(Tree, TargetValue)
ポインタの指す値 <- Treeの根
while(ポインタの指す値!=NIL)
if(ポインタの指す値=TargetValue) then(探索成功をreturn)
else if(ポインタの指す値<TargetValue) then(ポインタの指す値 <- 右の子)
else (ポインタの指す値 <- 左の子)
(探索失敗をreturn)

### 32

procedure PrintTree(Tree)
push(Treeの根)
while(スタックが空でない)
value <- スタックからpopした値
if(valueの子がいる)
then(valueの左の子をpush; 右の子をpush)
else(valueを印字; valueの親を印字;
if(valueの親の右の子に子がいる)then(valueの親の右の子をpush)
else(valueの親の右の子を印字))

### 33

### 34
W
J F
M X G
↓
J
G W
F M X

### 35
Z T W P NIL NIL R NIL NIL NIL NIL NIL NIL H J

### 36
A
B C
D E F G

### 37
辞書
元々木構造で、順番に意味がなく、挿入したいようなとき

### 38
木を走査して、4つ目のデータに親へのポインタを格納する
兄弟間は親に移動してからその親の持つポインタの先

### 39
8 $\times$ 8の配列でいい
コマと色の6*2、空きコマの計13の数で表現

### 40
全部では？

### 41
左右を変える

### 42
人を親にとって、両親を子に追加(両親へのポインタを保持)　親へのポインタも追加

### 43
探索した値について、
右に子がいる場合、右の子の左の子を掘っていって、左の子がいない左の子にぶち当たったらそれをもとの値に代入する　もしそのノードに右の子がいた場合、右の子以降の木をそのまま代入する
右に子がいない場合、左の子を根とする木をそのまま持ってくる

### 44
子のリストへのポインタを持たせる

### 45
define type EmployeeType to be
{char Name[25];
char Address[50];
char Occupation[25];
int Pay;
}

### 46
NameListを定義して、char型の配列の配列、ポインタを保持する

### 47
define type QueueType to be
{int QueueEntries[20]
int HeadPointer = 0;
int TailPointer = 0;
proceure push(value)
{QueueEntries[TailPointer] = value;
TailPointer = TailPointer + 1;
}
procedure pop(){
return QueueEntries[HeadPointer];
HeadPointer = HeadPointer + 1;
}
}

### 48
ユーザ定義のデータ型は基本データ型を集めたものである
抽象データ型はユーザ定義のデータ型に手続きを含めたもの

### 49
住所とその人の名前の配列に、手続きとして追加と削除、変更を加えたもの

### 50
名前、体力を保持して、攻撃手段などをメソッドにする

### 51
47でやった

### 52
クラスは抽象データ型に、継承システム、コンストラクタ、カプセル化システムを加えたもの。

### 53

## 9章　データベース

### 1
フラットファイルはある一つの視点からの情報を提供しているという点で一次元的であり、データベースはデータ項目が内部的に連結しているという点で多次元的である。

### 2
アプリを変更することなくデータベースの構成を変更できる性質のこと。

### 3
$(ユーザ→アプリ→DBMS→データベース$)
DBMSは実際のデータベースに変更を加えたり、該当するデータをデータベースからもってきたりする。

### 4
スキーマはデータベースの全体構造の記述であり、サブスキーマは利用者によって提示する情報を制限された記述のこと。

### 5
二分することで、抽象化ツールを構成して利用することができる。DBMSがいろいろやってくれるので、アプリケーションがデータがどこに格納されているかを考慮せずにデータベースにアクセスが可能となる。

データベースへのアクセスを制御する手段が生まれるから。スキーマを内部的に使用しつつ、ユーザにはサブスキーマを提示できるようになる。

データ独立性を達成できるから。

### 6
データベースモデルの目的
実際の構成よりもアプリケーションに近いデータベースの構成を表現する。DBモデルを定義するのはDBを抽象化ツールとして使用する第一歩。

### 7
a.DBMS
b.ユーザ
c.DBMS？
d.アプリケーション
e.