清华大学计算机考试数据结构与程序设计试题(1)-计算机等级考试试题.docx

清华大学计算机考试数据结构与程序设计试题(1)-计算机等级考试试题

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

试题内容:

一、试给出下列有关并查集(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) 试就以上图形说明:此问题有解的条件是什么? (5 分)

(2) 设图中的顶点数为 n,试用 C 或 Pascal 描述与求解此问题有关的数据结构并编写一个算法,

找出满

足要求的一条回路. (10 分)

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

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

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

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

码? (5 分)

五、设一个散列表包含 hashSize=13 个表项,.其下标从 0 到 12,采用线性探查法解决冲突. 请

按以下

要求,将下列关键码散列到表中.

10 100 32 45 58 126 3 29 200 400 0

(1) 散列函数采用除留余数法,用%hashSize(取余运算)将各关键码映像到表中. 请指出每一个

产生

冲突的关键码可能产生多少次冲突. (7 分)

(2) 散列函数采用先将关键码各位数字折叠相加, 再用%hashSize 将相加的结果映像到表中

的办