【 基本情報技術者 】平成24年 春期 午前 問7 単方向リスト

多数のデータが単方向リスト構造で格納されている。
このリスト構造には，先頭ポインタとは別に、末尾のデータを指し示す末尾ポインタがある。
次の操作のうち，ポインタを参照する回数が最も多いものはどれか。

　　　ア リストの先頭にデータを挿入する。 

　　　イ リストの先頭のデータを削除する。 

　　　ウ リストの末尾にデータを挿入する。

　　　エ リストの末尾のデータを削除する。

【解説】

リスト構造とは、

ポインタ型（アドレス指定型）のデータをつないで、全体を操作できるようにしたデータ構造です。

この構造で表現されるデータの並びをリスト（連結リスト）といいます。

リスト構造には、

単方向リスト（ポインタが順方向にだけ付けられたリスト最後のセルのポインタ部にNULL値が格納）と

双方向リスト（ポインタ部を二つ持ち、ポインタ部に順方向（次のセル）と逆方向（1つ前のセル）のアドレスをもつリスト）

があります。

　

※リストは、データの物理的順序と論理的順序が同じでなくてもよいため、配列に比べて、データの挿入や削除が容易（ポインタを付け替えるだけでよい）にできます。

問題文は、単方向リスト　について述べています。

求めるのは　「ポインタを参照する回数」　です。

選択肢を順に見ていきましょう。

ア リストの先頭にデータを追加する場合、先頭ポインタ（ｈｅａｄ（root））を書換えるだけですむので　1回です。

イ リストの先頭のデータを削除する場合、アと同様なので　1回です。

ウ リストの末尾のデータを追加する場合、末尾ポインタ（tail）より、現最後尾のデータの次データに追加データのアドレスを書き込むので　1回です。

エ リストの末尾のデータを削除する場合、末尾より一つ前のデータを参照しなければいけないのですが、単方向の場合、先頭からたどっていくしかないので、　ほぼリストの長さと同じだけ　ポインタの参照が発生することが必要となります。

【解答】エ

【 基本情報技術者 】平成23年 秋期 午前 問6 配列への格納

次の規則に従って配列の要素A[0]，A[1]，… ，A[9]に正の整数kを格納する。kとして16，43，73，24，85を順に格納したとき， 85が格納される場所はどこか。ここで，x mod yはxをyで割った剰余を返す。また，配列の要素は全て0に初期化されている

〔規則〕

（１）A[k mod 10] = 0ならば，k→A[k mod 10] とする。

（２）(1)で格納できないとき，A[(k＋1) mod 10]＝0ならば，k→ A[(k＋1) mod 10] とする。

（３）(2)で格納できないとき，A[(k＋4) mod 10]＝0ならば，k→A[(k＋4) mod 10] とする

ア　A[3]

イ　A[5]

ウ　A[6]

エ　A[9]

【解説】

配列の添え字は　１桁になります。　

（１）の規則に従うと、　85は　A[5]に格納されるとなりますが、格納されるデータの順番があります。

ダブっていた場合（今回は43と73がダブるのがわかっています）、格納位置がずれるので、順番にやっていくのが妥当です。

問題文の通りに　配列に格納していきます。

初期値

●手順１
16の格納位置を　求めると　添え字6となる。

●手順2
43の格納位置を　求めると　添え字3となる。

●手順3
73の格納位置を　求めると　添え字3となるが、すでにデータが存在しているため、（２）の規則により添え字4に格納する。

●手順4
24の格納位置を　求めると　添え字4となるが、すでにデータが存在しているため、（２）の規則により添え字5に格納する。

●手順5
85の格納位置を　求めると　添え字5となるが、すでにデータが存在しているため、（２）の規則により添え字6を求めた。

しかし、添え字6の位置にもすでにデータが存在するため、（３）の規則により、添え字9の位置に格納する

【解答】エ

【基本情報技術者試験】平成21年 秋期 午前 問35 分散データベース

分散データベースの透過性の説明として、適切なものはどれか。

　ア  　クライアントのアプリケーションプログラムは、複数のサーバ上のデータベースをアクセスする。
　　　　アプリケーションプログラムは、データベースがあたかも一つのサーバ上で稼動しているようにアクセスできる。

　イ  　クライアントのアプリケーションプログラムは、複数のサーバ上のデータベースをアクセスする。
　　　　アプリケーションプログラムはどのサーバ上のデータベースをアクセスするか知っている。

　ウ  　複数のクライアントのアプリケーションプログラムが、一つのサーバ上のデータベースを共有してアクセスする。

　エ  　複数のクライアントのアプリケーションプログラムは、一つのサーバ上のデータベースを、サーバ上のアプリケーションを介してアクセスする


【解説】
分散データベースとは、
物理的に離れているネットワーク上の複数のデータベースを、一つのデータベースとして使用する技術
のことです。

「分散データベースの透過性」とは、
実際のクライアントアプリケーションプログラムは、複数のサーバー上のデータベースに対しアクセスしているが、
アクセス利用者が分散されていることを意識せずに扱うことができる性質のことです。

選択肢別に　見ていきます。

　ア 　〇⇒「クライアントのアプリケーションプログラムは、複数のサーバ上のデータベースをアクセスする。
　　　　アプリケーションプログラムは、データベースがあたかも一つのサーバ上で稼動しているようにアクセスできる。」

　イ 　×⇒「クライアントのアプリケーションプログラムは、複数のサーバ上のデータベースをアクセスする。
　　　　アプリケーションプログラムはどのサーバ上のデータベースをアクセスするか知っている。」
　　　　　利用者（アプリケーションプログラム）が、意識してアクセスしているのは、透過性をもっていない。

　ウ 　×⇒「複数のクライアントのアプリケーションプログラムが、一つのサーバ上のデータベースを共有してアクセスする。」
　　　　　分散データベースは、ひとつのサーバー上に存在しているとは限らない。

　エ 　×⇒「複数のクライアントのアプリケーションプログラムは、一つのサーバ上のデータベースを、サーバ上のアプリケーションを介してアクセスする」
　　　　　分散データベースは、ひとつのサーバー上に存在しているとは限らない。

【解答】　ア