ボンカレー 〜凡人コミュ障の僕が華麗に生きていく術を考えるブログ〜

凡人コミュ障の僕が華麗に生きていく術を考えるブログ

基本情報技術者 ミスノート 20180916

過去問H16春問13

問題

16進数で表される9個のデータ1A,35,3B,54,8E,A1,AF,B2,B3を順にハッシュ表に入れる。ハッシュ値ハッシュ関数f(データ) = mod(データ, 8)で求めたとき、

最初に衝突が起こる(既に表にあるデータと等しいハッシュ値になる)のはどのデータか。

ここで、mod(a, b)はaをbで割った余りを表す。

 

解答

そのまま、十進数になおして計算をすると手間がかかりすぎる。

16進数は、?×2(7乗) + ?×2(6乗) + ?×2(5乗) + ?×2(4乗) + ?×2(3乗) + ?×2(2乗) + ?×2(1乗) + ?×2(0乗)で表される数字。

この数字を8つまり2(3乗)で割ると、2(3乗)のように指数3以上の指数の項に関しては、必ず割り切れる。

 

これは、54630という数=5×10(4乗) + 4×10(3乗) + 6×10(2乗) + 3×10(1乗) + 0×10(0乗)を、10(2乗)で割ったらその指数2以上の指数を持つ項は必ず割り切れるのと同じ理屈。

しかし、指数2未満の指数を持つ項はあまりとしてでてしまう。

 

さて、2(3乗)で割ると、3未満の指数である下位三桁の部分があまりとして出てくる。

よって、16進数の下位三桁にだけ注目すれば良い。

 

1Aの下位三桁は、Aが10進数で言う10, 2進数で言う1010なので、010が該当する。

35の下位三桁は、5が10進数で言う5, 2進数で言う0101なので、101が該当する。

3Bの下位三桁は、Bが10進数で言う11, 2進数で言う1011なので、011が該当する。

54の下位三桁は、4が10進数で言う4, 2進数で言う0100なので、100が該当する。

8Eの下位三桁は、Eが10進数で言う14, 2進数で言う1110なので、110が該当する。

A1の下位三桁は、1が10進数で言う1, 2進数で言う0001なので、001が該当する。

AFの下位三桁は、Fが10進数で言う15, 2進数で言う1111なので、111が該当する。

B2の下位三桁は、2が10進数で言う2, 2進数で言う0010なので、010が該当する。

→ここで初めてコリジョンが発生する。

B3の下位三桁は、Aが10進数で言う3, 2進数で言う0011なので、011が該当する。

 

 

 

スタック(stack)とは

 

stackの英単語としての意味は、積み重ね。

スタックは、積み重ねられた本のような構造をしている。

 

本は、新しいものが積み重ねられていき、新しいものから手に取られていく。

ITでいう、スタックは後入先出法とも言われ、

データ構造のひとつのリストの中で、挿入や削除がリストの先頭(最新の分)からしかできないものを指す。

基本情報技術者 ミスノート 20180916

  • 問題文読み落とし

問題文

次の規則に従って配列の要素A[0],A[1],…A[9]に正の整数kを格納する。

16, 43, 73, 24, 85を順に格納したとき、85が格納される場所はどれか。

ここで、x mod yはxをyで割った剰余を返す。

また、配列の要素は全て0に初期化されている。

→ここを見落とした。配列の要素はすべて0に初期化ということは、A[?]は最初はすべて0ということを示している。

 

[規則]

(1)A[k mod 10]=0ならば、k→A[k mod 10]とする。

→A[k mod 10]は数字を格納する箱のようなもの。

 それに対してkは数字そのもの。

 初見で勘違いしていたポイントは、A[k mod 10]=0という式の意味。

 自分は、kを10で割った余り(剰余)が0という意味かと思った。

 しかし、実際はkを10で割った剰余が要素番号の箱に格納されている数字が0という意味だった。

 大事なのは、箱の番号ではなく箱に格納されている数字を指している点。

 k→A[k mod 10]は数字kをA[k mod 10]という箱に格納する行為を指している。

 

(2)(1)で格納できないとき、A[(k+1) mod 10]=0ならば、

 k→A[(k+1) mod 10]とする。

→kを格納しようとした箱の中にすでに初期値の0以外が入っていたら、箱の番号を変更して入れる。

 

(3)(2)で格納できないとき、A[(k+4) mod 10]=0ならば、

 k→A[(k+4) mod 10]とする。

→同様に、kを格納しようとした箱の中にすでに初期値の0以外が入っていたら、箱の番号を変更して入れる。

 

解答

16は10で割ると剰余が6。A[6]の箱には初期値の0が入っているので、

16はA[6]に入る。

 

43は10で割ると剰余が3。A[3]の箱には初期値の0が入っているので、

43はA[3]に入る。

 

73は10で割ると剰余が3。A[3]の箱には43が入っているので、

(2)を検討。

73+1=74を10で割ると剰余が4。A[4]の箱には初期値の0が入っているので、

73はA[4]に入る。

 

24は10で割ると剰余が4。A[4]の箱には73が入っているので、

(2)を検討。

24+1=25を10で割ると剰余が5。A[5]の箱には初期値の0が入っているので、

25はA[5]に入る。

 

85は10で割ると剰余が5。A[5]の箱には25が入っているので、(2)を検討。

85+1=86を10で割ると剰余が6。A[6]の箱には16が入っているので、(3)を検討。

85+4=89を10で割ると剰余が9。A[9]の箱には初期値の0が入っているので、85はA[9]に入る。

 

 

 

 

プログラム 挿入法 仕組み

 

基本情報技術者試験H19春午後問4

過去問

【プログラムの説明】

整列型の一次元配列の要素A[0],…A[N](N>0)を、挿入ソートで昇順に整列する副プログラムInsertSortである。

(1) 挿入ソートの手順は、次の通りである。

 ①まず、A[0]とA[1]を整列し、次にA[0]からA[2]までを整列し、その次にA[0]からA[3]までというように、整列する区間の要素をひとつずつ増やしていき、最終的にA[0]からA[N]までを整列する。

→左から一個ずつ整列していく

 ②整列する区間がA[0]からA[M](1≦M≦N)までのとき、A[M]を既に整列された列A[0],…A[M-1]中の適切な位置に挿入する。その手順は以下の通りである。

  (a) A[M]の値を、作業領域Tmpに格納する。

→格納された値は、挿入する目的を持っている。

  (b) A[M-1]からA[0]に向かってTmpと比較し、Tmpよりも大きな値を順次隣(要素番号の大きい方)に移動する。

→後で挿入するために別の場所Tmpにいったん避難させておき、

 Tmpを挿入する位置を空けるために、いままで入っていた値をずらしてあげる。

  (c) (b)で最後に移動した値の入っていた配列要素にTmpの内容を格納する。(b)で移動がなかった場合にはA[M]に格納する。

→場所をゆずってくれたので、避難していたTmpをその位置に挿入する。

 そもそもあらためて並び替える必要がない(挿入しなくて良い)場合は、

 同じ位置に格納する。

 

(2) 副プログラムInsertSortの引数の仕様を表に示す。

◯InsetSort (整数型:A[],整数型:N)

◯整数型:Idx1, Idx2, Tmp

◯論理型:Loop

■ Idx1:1, Idx1 ≦ N, 1 →Idx1は初期値が1、N以下のときにループし、1ずつ増加する

| ・Tmp ←A[Idx1] →A[Idx1]を後で挿入するために、一旦Tmpに格納(避難)する

| ・Idx2 ←?

→①A[Idx1]は現在一番右の数字であり、それを左側の既に整列されている部分に挿入したい。

そのためには、一番右の数字とそのひとつ左横の数字を比べる必要がある。

今、一番右の数字はA[Idx1]で、ひとつ左横はA[Idx1-1]にあたる。

→②Idx1は定義(初期化)されているのに対して、Idx2は初期化されていない。

 Idx1とひとつ左横のIdx1-1を比較するために変数Idx2が設定されていると考えられるので、変数Idx2にIdx1-1を代入するのが妥当。

| ・Loop ← true

→Loop変数に、trueを代入することで、下のループが実行される。

 Loop = trueにならないと、下の作業は実行されない。

| ■Idx2 ≧ 0 and Loop = true

→上で、Loop←trueが代入され、かつIdx2が0以上のときループが実行される。

| | ↑ A[Idx2] > Tmp

→比較対象のA[Idx2]が、Tmpより大きい場合。

| | | ・?

→A[Idx2]が現在存在する位置もしくはそれより左に、Tmpを挿入しなくてはならないので、A[Idx2]をひとつ右つまり、Idx2+1の位置にずらしてこなければならない。

 

| | | ・Idx2 ← Idx2 - 1

→Idx2よりひとつ左にあるIdx2-1の位置を、新たなIdx2の位置として再定義する。

 Idx2は、Tmp(A[Idx1])と数の大小関係を比較する対象の位置を示す変数であり、

 その位置の範囲は0からIdx1-1の間であり、最初Idx1-1とIdx1を比較し、

 Idx1の方が小さければ、順次より左の位置の数字とIdx1を比較する必要がある。

 ここで行われているのは、Tmpとの比較対象の位置をひとつ左にずらす行為。

| | | ーーーーーーーーーーーー

| | | ・Loop ← false

比較対象のA[Idx2]が、Tmpより小さい場合は、Loop関数にfalseを代入する。

 すると、Loop=trueではなくなるので、ループが実行されなくなる。

| | ↓

| ■

| ・?

→挿入するために作ったTmpを最終的にあるべき場所に挿入する。

 直前のループで、A[Idx2]がTmp以下になった時点でループは終了している。

 Tmpは大小関係によって挿入位置を決め、その順番は昇順である。

 A[Idx2]が初めてTmp以下になったということは、A[Idx2]の直後の位置にTmpが入るということなので、Tmpが入る位置はIdx2+1になる。

 よって、A[Idx2+1]←Tmp

ミスノート_基本情報技術者

ビットとバイトの単位をスルーしていた

変換してどちらかに単位を統一する。

 

奇数パリティと偶数パリティの違いが分からない

パリティビットをつけた後の1の個数が奇数になるのが、奇数パリティ

 パリティビットをつけた後の1の個数が偶数になるのが、偶数パリティ

 

リピータの意味

ネットワークの中継機器であり、減衰した信号を増幅させる機械。

 

スイッチングハブの意味

通信の中継機器であり、宛先によってデータの行き先を振り分けてくれる。

行き先を振り分ける際に、MACアドレスをみて宛先を判断している。

リピータハブと違うのは、リピータハブはデータを宛先と関係のない全てのコンピュータにもデータを送るという点(他のコンピュータは送られてきたデータを無視する)

 

ルータの意味

ネットワークの中継機器であり、IPアドレスを見てデータの交通整理をしている。

 

CSMA/CA(carrier sense multiple access with collision avoidance)の意味

通信方法のひとつで、他のコンピュータの通信状況を確認して、

他に通信しているデータがない時に、一定時間を空けてからデータを送る方法。

コリジョン(collision/衝突)を避けて通信するために、

他に通信しているデータがないことを確認した後に一定時間あけてから通信をする方法。

 

 CSMA/CD(carrier sense multiple access with collision detection)の意味

通信方法のひとつで、他のコンピュータの通信状況を確認して、

他に通信しているデータがない時に、即座にデータを送る方法。

コリジョンが起きたら、時間を置いてまたデータを再送する方法。

CAとの違いは、最初にデータを送るときに衝突を避けるために一定時間をあけることをしないという点。

 

IPv6の特徴

アドレス長が128ビット

アドレスには、IPv4のグローバルアドレスに対応するグローバルユニキャストアドレスや、プライベートアドレスに対応するユニークローカルユニキャストアドレスがある。

 

ゲートウェイOSIどこの層

 

 

 

ミスノート_OSI参照モデル

OSIとは、open systems interconnectionの略

 

通信機能の仕組みを整理した共通ルールの一つ

 

共通ルールを作れば、違うメーカーのコンピュータ同士でも通信ができる。

そこで作られたルールがOSI

 

7層あり、

第一層 物理層

ケーブルやコネクタ、電気信号などの物理的なものに関するルール

 

第二層 データリンク層

「パソコンとLANケーブルでつながったルータ」や、「パソコンと無線LANアクセスポイント」のように、

隣り合って直接つながっている機器とのやりとりについてのルール

 

第三層 ネットワーク層

目的の機器とのやりとりについてのルール

IPアドレスは、最終的な目的の機器のアドレスのことなので、

ネットワーク層に該当する。

 

第四層 トランスポート層

やり取りの正確性・信頼性についてのルール

TCP(transmission control protocol)やUDP(user datagram protocol)はトランスポート層に該当する。

TCPは信頼性は高いが、転送速度は遅い。

UDPは転送速度は速いが、信頼性は低い。

 

第五層 セッション層

通信の開始から終了までの一連の流れについてのルール

通信を開始する時の合図

通信を終了する時の合図

 

第六層 プレゼンテーション層

データ形式の変換についてのルール

コンピュータで分かるデータ形式とネットワークで共通のデータ形式の変換に関しての取り決め

日本人と中国人が、お互いの母国語(各コンピュータで分かるデータ形式)は分からないので、

世界共通語の英語(ネットワークで共通のデータ形式)で話すようなもの。

 

第七層 アプリケーション層

通信機能のソフトとの窓口になる部分