2017年度「アルゴリズムとデータ構造」のページ

練習問題

2018年1月25日出題
  1. 連鎖法ハッシュ表を実装せよ。

    格納するデータは、以下のように定義されたCの構造体で表されるものとする。

    struct xyz {
    	int	x, y, z;
    };
    	      
    データの比較は以下の型の関数xyz_equalで行うものとする。 xyz_equal(p, q)*p*q と等しいときに0でない整数を返し、そうでないとき0を返す。
    int     xyz_equal(const struct xyz *p, const struct xyz *q);
    	      
    ハッシュ値には、以下の型の関数xyz_hashの返り値を配列の大きさで割った余りを用いる。
    size_t	xyz_hash(const struct xyz *);
    	      
    struct xyz の型定義と関数xyz_equalと関数xyz_hashのプロトタイプ宣言がヘッダファイル xyz.h に書かれている。関数xyz_equalの定義は xyz.c に書かれている。

    関数xyz_lessもプロトタイプ宣言がヘッダファイル xyz.h に書かれていて、定義が xyz.c に書かれているが、今回は使う必要はない。

    連鎖法ハッシュ表の実装のために、以下のように定義されたCの構造体を用いる。これらの定義は、xyz_hashtable.h に書かれている。

    struct xyz_hashtable {
    	struct xyz_hashtable_node **array;
    	size_t	size;
    };
    
    struct xyz_hashtable_node {
    	struct xyz_hashtable_node *next;
    	struct xyz      data;
    };
    	      

    連鎖法ハッシュ表の初期化を行う関数xyz_hashtable_initは、ソースファイルxyz_hashtable_init.cで定義されている。

    1. データを探索する関数。

      int     xyz_hashtable_search(const struct xyz_hashtable *table, const struct xyz *data);
      		  
      同じ値が連鎖法ハッシュ表に含まれていれば1を返し、含まれていなければ0を返す。

    2. データを1個挿入する関数。

      int     xyz_hashtable_insert(struct xyz_hashtable *table, const struct xyz *data);
      		  
      同じ値が連鎖法ハッシュ表に含まれていて挿入が行われなかったら0を返し、含まれていなくて挿入が行われたら1を返す。

    3. データを1個削除する関数。

      int     xyz_hashtable_remove(struct xyz_hashtable *table, const struct xyz *data);
      		  
      同じ値が連鎖法ハッシュ表に含まれていて削除が行われたら1を返し、含まれていなくて削除が行われなかったたら0を返す。

  2. AVL木を実装せよ。

    格納するデータは、以下のように定義されたCの構造体で表されるものとする。

    struct xyz {
    	int	x, y, z;
    };
    	      
    データの大小比較は以下の型の関数xyz_lessで行うものとする。 xyz_less(p, q)*p*q よりも小さいときに0でない整数を返し、そうでないとき0を返す。
    int     xyz_less(const struct xyz *p, const struct xyz *q);
    	      
    struct xyz の型定義と関数xyz_lessのプロトタイプ宣言がヘッダファイル xyz.h に書かれている。関数xyz_lessの定義は xyz.c に書かれている。

    AVL木の実装のために、以下のように定義されたCの構造体を用いる。これらの定義は、xyz_avltree.h に書かれている。

    struct xyz_avltree {
    	struct xyz_avltree_node *root;
    };
    
    struct xyz_avltree_node {
    	struct xyz_avltree_node *left, *right;
    	signed char     height_difference; /* height(left_subtree) - height(right_subtree) */
    	struct xyz      data;
    };
    	      

    AVL木の初期化を行う関数xyz_avltree_initは、ソースファイルxyz_avltree_init.cで定義されている。

    1. データを探索する関数。

      int     xyz_avltree_search(const struct xyz_avltree *tree, const struct xyz *data);
      		  
      同じ値がAVL木に含まれていれば1を返し、含まれていなければ0を返す。

    2. データを1個挿入する関数。

      int     xyz_avltree_insert(struct xyz_avltree *tree, const struct xyz *data);
      		  
      同じ値がAVL木に含まれていて挿入が行われなかったら0を返し、含まれていなくて挿入が行われたら1を返す。

    3. データを1個削除する関数。

      int     xyz_avltree_remove(struct xyz_avltree *tree, const struct xyz *data);
      		  
      同じ値がAVL木に含まれていて削除が行われたら1を返し、含まれていなくて削除が行われなかったたら0を返す。

  3. ACM-ICPC 2017年日本国内予選の問題を2問以上解け。

  4. ACM-ICPC 2017年アジア地区予選つくば大会の問題を1問以上解け。

  5. (おまけ)

    1. 情報科学の研究者10名以上(うち、女性3名以上)を調べて、氏名と研究分野を列挙せよ。ただし、本学の教員・学生は除く。情報科学の範囲は広く解釈する。


戻る