2分木へのデータの追加処理の説明を行う。 以下のようなコードを示しながら、ポインタの移動などを図を交えながらの解説とした。

struct Tree {
int  data ;
struct Tree* left ;
struct Tree* right ;
} ;
void main() {
struct Tree* top = NULL ;
int  key ;
while( scanf( "%d" , &key ) == 1 ) {
struct Tree** ppt = &top ;
while( (*ppt) != NULL ) {
if ( (*ppt)->data == key )
break ;
else if ( (*ppt)->data > key )
ppt = &( (*ppt)->left ) ;
else
ppt = &( (*ppt)->right ) ;
}
if ( (*ppt) == NULL ) {
(*ppt) = tcons( key , NULL , NULL ) ;
}
}
}

この動作確認の後、10,20,30,40,50,60… といったデータを順次与えた場合、 どのような木構造ができあがるのかを考えてもらい、 処理時間が、 であるべき所が、となってしまう欠点を説明する。 この改善策として、木の枝のつなぎかえを行って、右の枝・左の枝の大きさをそろえる AVL木などの紹介をする。

情報処理技術者試験の問題をみる

後半は、演習室に移動して、２分木の課題に取り組んでもらう。 演習中は暇だったので、先週末に実施された情報処理技術者試験の問題を 持っている人がいたので、問題を見てみる。

前半の試験問題でも、データベースやオブジェクト指向といった用語も多く、 自分の授業での説明の不足していそうな点の参考にする。 後半の試験問題を見ていると、なかなか面倒な問題も多い。 Javaでは、リスト構造や、スレッド起動を含む通信プログラムの出題もあり、 時代の違いを感じるとともに、ほかの出題と比べ難易度たかくねぇ？との感想。 問題を見せてくれた学生さんは、言語選択は表計算を選んだそうだ。

ちょうど、３年の授業では、構造体のネタを説明しているが、C言語の出題では、 typedef struct … が普通になっているみたい。自分の授業では、typedef せずに、 struct キーワード連発なんだが…. 例年、説明はしているけど、 改めて typedef の説明忘れないようにしないと…. しかしながら、構造体もリスト構造での出題でもないし、まだわかりやすい問題だったように思う。