基本情報の午後試験はプログラム問題です.
科目B問題を解けるようになるにはプログラムを元に自分でコードを書いてみるのが1番良いでしょう.
今回は科目B問9「木構造を走査するプログラム」の解説とそのコードを紹介します.
プログラムを元にPythonで書き直しました.
Pythonで書いてみたので是非手元で実行してみてください
サンプル問題 科目B 問9「木構造を走査するプログラム」
問題文は以下のとおりです.
木構造に関する問題ですね.


プログラムをPythonで書き直す
問9に掲載されているプログラムを元にPythonで書き直しました.
tree = [
[2,3],
[4,5],
[6,7],
[8,9],
[10,11],
[12,13],
[14],
[],
[],
[],
[],
[],
[],
[]
]
def order(n: int):
# 要素数が2と等しいとき
if (len(tree[n-1]) == 2):
order(tree[n-1][0])
print(n, end=', ') # 改行を「, 」に変換する
order(tree[n-1][1])
# 要素数が1と等しいとき
elif (len(tree[n-1]) == 1):
order(tree[n-1][0])
print(n, end=', ')
else:
print(n, end=', ')
order(1)

プログラムを実行すると「8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7」と表示されました.
この結果と一致する選択肢は「ウ」です.
答えも「ウ」なのでプログラムに誤りはなさそうですね.
ポイントを確認します.
ポイント1 木構造について
木構造について確認しましょう.
木構造は要素が親と子の関係を持つ階層的なデータ構造です.
各要素はノード(Node)と呼ばれます.

ノードはその特徴でそれぞれ呼び名が変わります.
- ルートノード(Root Node):木構造の1番上のノード.
- 親ノード(Parent Node):他のノードに対して上位に位置し,直接的にノードへのリンクを持つノード
- 子ノード(Child Node):親ノードから分岐するノード.親ノードとリンクしている.
- 葉ノード(Leaf Node):子ノードを持たないノード,最下位に位置する.
ポイント2 トレースする
order関数は再帰関数なので処理が複雑です.
頭の中で処理を追うと混乱してしまうので書き出すのが良いでしょう.
def order(n: int): # n=1
# 要素数が2と等しいとき
if (len(tree[n-1]) == 2): # tree[0] = [2, 3]
order(tree[n-1][0]) # tree[0][0] = 2
def order(n: int): # n=2
# 要素数が2と等しいとき
if (len(tree[n-1]) == 2): # tree[1] = [4, 5]
order(tree[n-1][0]) # tree[1][0] = 4
def order(n: int): # n=4
# 要素数が2と等しいとき
if (len(tree[n-1]) == 2): # tree[3] = [8, 9]
order(tree[n-1][0]) # tree[3][0] = 8
def order(n: int): # n=8 要素番号8は空のリストなので
# 要素数が2と等しいとき
if (len(tree[n-1]) == 2):
order(tree[n-1][0])
order(tree[n-1][1])
# 要素数が1と等しいとき
elif (len(tree[n-1]) == 1):
order(tree[n-1][0])
print(n, end=', ')
# 要素数が0のとき
else:
print(n, end=', ') # 8が出力される
以上から1番初めに出力される値は8です.
n=8のときに8が出力されると分かりました.
処理はn=4に戻ります.
def order(n: int): # n=4
# 要素数が2と等しいとき
if (len(tree[n-1]) == 2): # tree[3] = [8, 9]
order(tree[n-1][0]) # tree[3][0] = 8 が1番初めに出力される
print(n) # n=4 次に出力される数字
order(tree[n-1][0])の結果8が出力されたので処理は次に進みます.
後の処理でprint(n)をしているので4が出力されます.
よって答えは「8, 4…」と続く「ウ」になります.
まとめ
今回は科目B問9「木構造を走査するプログラム」について紹介しました.
木構造は要素が親と子の関係を持つ非線形なデータ構造です.
上位に位置すれば親,下位に位置すると子となり,それぞれリンクしています.
またこの問題は関数の中で自身を呼ぶ再帰関数でもありました.
そのため処理が少しややこしいです.
こんなときは落ち着いてトレースすると解けるでしょう!