基本情報技術者 2013年 秋期 午後 問11
次のJavaプログラムの説明及びプログラムを読んで、設問1～3に答えよ。
〔プログラムの説明〕
ディレクトリパス（以下、パスという）から木構造を生成するプログラムである。
パスは、木構造をもつファイルシステムにおいてディレクトリを特定するために利用される文字列であり、ディレクトリの名前を“/”で区切って並べて表す。“/”で始まるパスを絶対パスという。絶対パスはルートディレクトリを起点として表したパスである。“/”で始まらないパスを相対パスという。相対パスは任意のノードを起点として表したパスである。
このプログラムが生成する木構造中の各ノードは、それぞれが一つのディレクトリを表し、ルートノードはルートディレクトリを表す。
図1に木構造の例を示す。図1中の楕円一つはノード一つに対応し、“ と ”で囲まれた文字列はノードの名前を表す。ルートノードの名前は空文字列とする。例えば、ノードusrを特定する絶対パスは“/usr”であり、ノードusrを起点とする相対パス“local/lib”が特定するノードは、絶対パス“/usr/local/lib”が特定するノードと同じノードlibである。
クラスDirectoryNodeは木構造を構成するノードを表すクラスであり、一つのインスタンスが一つのノードを表す。フィールドnameはノードの名前を、フィールドparentは親ノードへの参照を、フィールドchildrenは子ノードのリストを保持する。引数を取らないコンストラクタはルートノードを生成する。
クラスDirectoryNodeは次のメソッドをもつ。
(1) public DirectoryNode add(String path)
引数pathで与えられたパスが、このノードを起点に一つのノードを特定できるように木構造を拡張し、パスが特定するノードを返す。引数pathが空文字列又は絶対パスを表すなら、IllegalArgumentExceptionを投げる。
パス中の連続する“/”は一つの“/”として扱い、末尾の“/”は無視する。つまり、パス“local//lib/”は“local/lib”とみなす。
(2) public String path()
このノードを特定する絶対パスを表す文字列（末尾は常に“/”）を返す。
例えば、図1の最下段のノードlibでこのメソッドを呼ぶと、“/usr/local/lib/”を返す。
(3) public List<DirectoryNode> find(String name)
このノードが保持する各子ノードを頂点とする全ての部分木から、引数nameで与えられた名前をもつノードを全て探し、見つかったノードをリストで返す。
クラスDirectoryNodeTesterはテスト用のプログラムである。実行結果を図2に示す。
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：""
イ："", null
ウ：null
エ：null, ""
bに関する解答群
ア：!path.startsWith("/") && !"".equals(path)
イ：!path.startsWith("/") || !"".equals(path)
ウ：path.startsWith("/") && "".equals(path)
エ：path.startsWith("/") || "".equals(path)
cに関する解答群
ア：parent != ""
イ：parent != null
ウ：parent == ""
エ：parent == null
d, eに関する解答群
ア：child
イ：name
ウ：node
エ：null
オ：parent
カ：root
模範解答
a：イ、b：エ、c：エ、d：ウ、e：イ
解説
解答の導き方
空欄は、ルートノードの作り方、パスの入力チェック、ルートノードの判定、検索結果への追加と再帰検索をそれぞれ完成させるものです。順に確認します。
a：ルートノードの名前と親
引数を取らないコンストラクタでは、ルートノードを生成します。問題文では「ルートノードの名前は空文字列」とされています。また、ルートノードには親がないので、親への参照はnullです。
このクラスのもう一つのコンストラクタは、名前と親ノードを受け取ります。そのため、ルートノードを作るにはthis("", null) として、空文字列とnullを渡します。よって、aはイです。
b：不正なパスを判定する条件
add(String path) は、「引数pathが空文字列又は絶対パスを表すなら、IllegalArgumentExceptionを投げる」と説明されています。
つまり、不正と判断する条件は次のどちらかです。
- パスが「/」で始まる
- パスが空文字列である
どちらか一方でも当てはまれば例外を投げるため、条件は OR（または）でつなぎます。空文字列かどうかは、"".equals(path) で判定できます。したがって、bはエです。
ここで、!path.startsWith("/") は「絶対パスではない」という意味です。これは有効な相対パスの条件なので、例外を投げる条件には使いません。
c：ルートノードかどうかの判定
path() は、ルートノードなら「/」を返し、それ以外のノードなら親ノードのパスに自分の名前をつなげます。
ルートノードには親がないため、parentはnullです。したがって、ルートノードかどうかはparent == nullで判定します。よって、cはエです。
例えば、usrの親はルートノードなので、usrのpath() は親のパス「/」に名前usrと「/」をつないだ「/usr/」になります。
d：見つけたノードを検索結果に追加する
find(String name) では、まずfindChild(name) で、このノードの子の中から名前が一致するノードを探します。その結果は変数nodeに入ります。
nodeがnullでなければ、名前が一致する子ノードが見つかったということです。そのノードを検索結果のリストretに追加する必要があります。追加する値はnodeなので、dはウです。
e：子ノードの下も同じ名前で検索する
このメソッドの説明には、「各子ノードを頂点とする全ての部分木から」名前を探すとあります。つまり、子ノード一つ一つについて、その下にあるノードも調べます。
そのため、各子ノードに対してchild.find(...) を呼びます。探す名前は、元のメソッドに渡されたnameと同じです。よって、eはイです。
この流れは、テスト用プログラムの結果でも確認できます。root.find("local") は、usrの下とoptの下にある「local」を探します。見つかった各ノードのpath() が表示され、その後usr.add("") で空文字列が渡されるため、例外が発生して「IllegalArgument」が表示されます。
誤りやすいポイント
- bは「有効なパス」の条件ではなく、「例外を投げるパス」の条件です。絶対パスと空文字列のどちらか一方でも不正なので、OR でつなぎます。
- cは文字列との比較ではありません。parentは親ノードへの参照なので、親がないことを示すnullと比較します。
- dでは、検索で見つかったノードを追加します。名前の文字列ではなく、ノードを表す変数nodeを追加します。
- eでは、子ノードの下も検索するために再帰呼出しをします。再帰呼出しにも、探す名前nameを渡します。
- find(String name) は、このノード自身ではなく、子ノードから始まる部分木を検索します。
FAQ
Q: 「/」が続くパスは、どのように扱われますか？
A: split("/+") の「/+」は、「/」が1回以上続く部分を区切りとして扱います。そのため、連続する「/」は一つの区切りとして扱われます。また、Javaのsplitは既定では末尾の空要素を取り除くので、末尾の「/」も無視されます。
A: split("/+") の「/+」は、「/」が1回以上続く部分を区切りとして扱います。そのため、連続する「/」は一つの区切りとして扱われます。また、Javaのsplitは既定では末尾の空要素を取り除くので、末尾の「/」も無視されます。
Q: find(String name) が自分自身を検索しないのはなぜですか？
A: メソッドの説明では、このノードが保持する各子ノードを頂点とする部分木を探すとされています。そのため、検索対象は子ノードとその子孫であり、このノード自身は含まれません。
A: メソッドの説明では、このノードが保持する各子ノードを頂点とする部分木を探すとされています。そのため、検索対象は子ノードとその子孫であり、このノード自身は含まれません。
Q: ルートノードのpath() で、親のpath() を呼び出さないのはなぜですか？
A: ルートノードには親がなく、parentはnullです。そのまま親のpath() を呼び出すことはできないため、ルートノードの場合は「/」を直接返す処理が必要です。
A: ルートノードには親がなく、parentはnullです。そのまま親のpath() を呼び出すことはできないため、ルートノードの場合は「/」を直接返す処理が必要です。
関連キーワード: 木構造、再帰、オブジェクト参照、例外処理、文字列分割、リスト
設問2：
問題文を見る クラスDirectoryNodeTesterを実行したときに生成される、クラスDirectoryNodeのインスタンスの個数として正しい答えを、解答群から選べ。
解答群
ア：6
イ：7
ウ：8
エ：9
オ：10
模範解答
ウ
解説
解答の導き方
この設問では、クラスDirectoryNodeのインスタンス、つまりクラスを基に作られた実体が何個できるかを数えます。問題文には「一つのインスタンスが一つのノードを表す」とあるため、木構造のノードを一つずつ数えればよいです。
最初に、引数なしのコンストラクタでルートノードが一つ作られます。ここまでで1個です。
次に、プログラムの処理を順番に追います。addメソッドは、パスの各部分に対応する子ノードがなければ作ります。すでに同じ親の下にあるノードは、作り直さずに使います。
ここで、同じ名前のノードがあっても、親が違えば別のノードです。たとえば、usrの下のlocalとoptの下のlocalは、それぞれ別に作られます。一方、usr.add("local/lib")では、usrの下にlocalがすでにあるため、localは増えません。
その後のroot.childrenを表示する処理とroot.find("local")は、すでにあるノードを調べたり、ノードへの参照をリストに入れたりする処理です。DirectoryNodeのインスタンスは増えません。
最後のusr.add("")では、引数が空文字列です。問題文には「引数pathが空文字列又は絶対パスを表すなら、IllegalArgumentExceptionを投げる」とあります。このため例外が発生し、新しいノードは作られません。
以上から、作られるDirectoryNodeのインスタンスは8個です。
誤りやすいポイント
- usrの下のbinと、usrの下のlocalの下のbinは別のノードです。名前だけでまとめず、親の違いも見て数えます。
- usr.add("local/lib")では、localはすでに存在します。パスにlocalが含まれていても、新しく作られるのはlibだけです。
- root.find("local")はノードを探してリストに入れますが、ノードを作る処理ではありません。
- usr.add("")は空文字列を確認した時点で例外になります。例外が発生した後にノードが追加されることはありません。
- 問われているのはDirectoryNodeの個数です。検索結果を入れるリストなど、別の種類のオブジェクトは数えません。
FAQ
Q: 同じ名前のノードがあれば、必ず同じノードとして数えますか？
A: いいえ。親が同じ場合は既存の子ノードを使いますが、親が違う場合は別のノードです。usrの下のlocalとoptの下のlocalは別々に数えます。
A: いいえ。親が同じ場合は既存の子ノードを使いますが、親が違う場合は別のノードです。usrの下のlocalとoptの下のlocalは別々に数えます。
Q: root.find("local")で見つかったノードは、新しく作られたものですか？
A: いいえ。findメソッドは、すでにあるノードを探して返します。探しただけではDirectoryNodeのインスタンスは増えません。
A: いいえ。findメソッドは、すでにあるノードを探して返します。探しただけではDirectoryNodeのインスタンスは増えません。
Q: usr.add("")の後に、ノードが作られる可能性はありますか？
A: ありません。空文字列は例外の対象なので、パスを処理してノードを追加する前に処理が中断します。
A: ありません。空文字列は例外の対象なので、パスを処理してノードを追加する前に処理が中断します。
関連キーワード: クラスとインスタンス、木構造、ノード、再帰処理、例外処理
設問3：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
クラスDirectoryNodeのメソッドpathが返す文字列の末尾は常に“/”である。これを、このメソッドが呼ばれたインスタンスがルートノードであるか、子ノードをもつときにだけ末尾が“/”になるように、メソッドpathの最後のreturn文の直前に次の3行を挿入した。クラスDirectoryNodeTesterの実行結果は図3となる。
if (f) {
return parent.path() + name;
}
fに関する解答群
ア：!children.isEmpty()
イ：children != null
ウ：children == null
エ：children.isEmpty()
模範解答
f：エ
解説
解答の導き方
この設問では、path()が「/」を付けずに返すのはどのようなノードかを考えます。
木構造は、親と子の関係でつながったデータ構造です。ノードは、その中の一つ一つの要素を指します。このプログラムでは、ノード一つがディレクトリ一つを表します。
もとのpath()は、ルートノードなら「/」を返し、それ以外なら親のパス、ノード名、「/」をつなげて返します。そのため、どのノードでも返す文字列の末尾に「/」が付きます。
変更後の処理では、最後のreturn文の直前で条件を調べます。条件が真なら、親のパスとノード名だけを返します。条件が偽なら、もとのreturn文に進むため、末尾に「/」が付きます。
設問の条件は、「ルートノードであるか、子ノードをもつときにだけ末尾が“/”になる」というものです。ルートノードは、その前にある処理で「/」を返して終了します。したがって、ここで条件を調べるのはルート以外のノードです。条件が真になるべきなのは、子ノードをもたないノードです。その場合に「/」なしの文字列を返せばよいからです。
子ノードのリストが空かどうかを調べるのがchildren.isEmpty()です。子ノードがないときに真になるので、fにはエのchildren.isEmpty()が入ります。
図3の結果でも確認できます。usrの下にあるlocalにはbinとlibがあるので、子ノードをもちます。そのため条件は偽となり、末尾に「/」が付きます。一方、optの下にあるlocalには子ノードがありません。条件が真となり、親のパス「/opt/」と名前「local」をつなげた「/opt/local」が返ります。
誤りやすいポイント
- children.isEmpty()は、名前のとおり「子ノードが空か」を調べます。子ノードがあるかどうかを調べる条件と取り違えないようにします。
- アの!children.isEmpty()は、子ノードがあるときに真になります。しかし、その場合は末尾に「/」を付けたいので、条件を逆にすると誤りです。
- children != nullは、子ノードがないかどうかを表しません。このプログラムではchildrenにリストが設定されているため、リストが空かどうかを調べる必要があります。
- ルートノードは、条件を調べる前に「/」を返します。そのため、fではルートかどうかではなく、子ノードがあるかどうかを判定します。
FAQ
Q: children.isEmpty()が真のとき、なぜ「/」を付けないのですか？
A: 真になるのは子ノードがないときです。設問では、末尾に「/」を付けるのはルートノードか子ノードをもつノードに限るため、子ノードがないノードでは付けません。
A: 真になるのは子ノードがないときです。設問では、末尾に「/」を付けるのはルートノードか子ノードをもつノードに限るため、子ノードがないノードでは付けません。
Q: 子ノードがないノードのパスで、親のパスの末尾に「/」が残っていてもよいのですか？
A: はい。親のパスの末尾の「/」は、親の名前と子の名前を区切る役割をします。たとえば「/opt/」に「local」をつなげると「/opt/local」になります。
A: はい。親のパスの末尾の「/」は、親の名前と子の名前を区切る役割をします。たとえば「/opt/」に「local」をつなげると「/opt/local」になります。
Q: childrenがnullかどうかを調べるのではだめですか？
A: childrenはリストとして用意されています。子ノードがない場合もリスト自体は存在し、中身が空になります。そのため、空かどうかを調べるchildren.isEmpty()を使います。
A: childrenはリストとして用意されています。子ノードがない場合もリスト自体は存在し、中身が空になります。そのため、空かどうかを調べるchildren.isEmpty()を使います。
関連キーワード: 木構造、ノード、リスト、条件分岐、戻り値
