清华大学2001年硕士研究生考试数据结构试题

清华大学2001年硕士研究生考试数据结构试题

 

一、试给出下列有关并查集(mfsets)的操作序列的运算结果：

 

union(1,2) , union(3,4) , union(3,5) , union(1,7) , union(3,6) , union(8,9) , union(1,8) , union(3,10) , union(3,11) , union(3,12) , union(3,13) , union(14,15) , union(16,0) , union(14,16) , union(1,3) , union(1,14)。(union是合并运算，在以前的书中命名为merge)

 

要求

 

(1) 对于union(i,j)，以i作为j的双亲； (5分)

 

(2) 按i和j为根的树的高度实现union(i,j)，高度大者为高度小者的双亲； (5分)

 

(3) 按i和j为根的树的结点个数实现union(i,j)，结点个数大者为结点个数小者的双亲； (5分)

 

二、设在4地(A,B,C,D)之间架设有6座桥,如图所示:

 

要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地

 

(1) 试就以上图形说明:此问题有解的条件是什么? (5分)

 

(2) 设图中的顶点数为n,试用C或Pascal描述与求解此问题有关的数据结构并编写一个算法,找出满足要求的一条回路. (10分)

 

三、针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数):

 

(1) 输入的n个数据全部有序; (5分)

 

(2) 输入的n个数据全部逆向有序; (5分)

 

(3) 随机地输入n个数据. (5分)

 

四、简单回答有关AVL树的问题.

 

(1) 在有N个结点的AVL树中,为结点增加一个存放结点高度的数据成员,那么每一个结点需要增加多少个字位(bit)? (5分)

 

(2) 若每一个结点中的高度计数器有8bit,那么这样的AVL树可以有多少层?最少有多少个关键码? (5分)

 

五、设一个散列表包含hashSize=13个表项,.其下标从0到12,采用线性探查法解决冲突. 请按以下要求,将下列关键码散列到表中.

 

10 100 32 45 58 126 3 29 200 400 0

 

(1) 散列函数采用除留余数法,用%hashSize(取余运算)将各关键码映像到表中. 请指出每一个产生冲突的关键码可能产生多少次冲突. (7分)

 

(2) 散列函数采用先将关键码各位数字折叠相加, 再用%hashSize将相加的结果映像到表中的办法. 请指出每一个产生冲突的关键码可能产生多少次冲突. (8分)

 

六、设一棵二叉树的结点定义为
..............................