清华大学计算机系历年试题集

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) 设图中的顶点数为 n,试用 C 或 Pascal 描述与求解此问题有关的数据结构并编写一个算法,找出满足要

求的一条回路.!!!!(10 分)

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

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

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

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

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

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

字位(bit)?!!!!(5 分)

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

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

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

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

struct BinTreeNode{

ElemType data;

BinTreeNode *leftChild, *rightChild;

}

现采用输入广义表表示建立二叉树. 具体规定如下:

(2) 每个结点的左子树和右子树用逗号隔开. 若仅有右子树没有左子树, 逗号不能省略.

(3) 在整个广义表表示输入的结尾加上一个特殊的符号(例如”#”)表示输入结果.

例如,对于如右图所示的二叉树, 其广义表表示为 A(B(D,E(G,)),C(,F))

!!!!!!!! A

!!!!!! /!!\

点的值), 则表示是结点的值, 应为它建立一个新的结点, 并把该结点作为左子女(当 k=1)或有子女(当

k=2)链接到其双亲结点上. 若遇到的是左括号”(“, 则表明子表的开始,将 k 置为 1;若遇到的是右括号”)”,

则表明子表结果. 若遇到的是逗号”,”, 则表示以左子女为根的子树处理完毕,应接着处理以右子女为根的子

树, 将 k 置为 2.

在算法中使用了一个栈 s, 在进入子表之前,将根结点指针进栈, 以便括号内的子女链接之用. 在子表处理结

束时退栈. 相关的栈操作如下:

MakeEmpty(s) 置空栈

Push(s,p) 元素 p 进栈

Pop(s) 进栈

Top(s) 存取栈顶元素的函数

istream ins(ls);!!!!!!!!!!!!!!!!!!!!!!//把串 ls 定义为输入字符串流对象 ins

Char ch;

ins>>ch;!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!//从 ins 顺序读入一个字符