清华大学2001年“数据结构”试题

《清华大学2001年“数据结构”试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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)对于union(i,j)，以i作为j的

2、双亲；（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分)三、针对以下情况确定非递归的归并排序的运行时间(

3、数据比较次数与移动次数):(1)输入的n个数据全部有序;(5分)(2)输入的n个数据全部逆向有序;(5分)(3)随机地输入n个数据.(5分)四、简单回答有关AVL树的问题.(1)在有N个结点的AVL树中,为结点增加一个存放结点高度的数据成员,那么每一个结点需要增加多少个字位(bit)?(5分)(2)若每一个结点中的高度计数器有8bit,那么这样的AVL树可以有多少层?最少有多少个关键码?(5分)五、设一个散列表包含hashSize=13个表项,.其下标从0到12,采用线性探查法解决冲突.请按以下要求,将下列关键码散列到表中.101003

4、245581263292004000(1)散列函数采用除留余数法,用%hashSize(取余运算)将各关键码映像到表中.请指出每一个产生冲突的关键码可能产生多少次冲突.(7分)(2)散列函数采用先将关键码各位数字折叠相加,再用%hashSize将相加的结果映像到表中的办法.请指出每一个产生冲突的关键码可能产生多少次冲突.(8分)六、设一棵二叉树的结点定义为structBinTreeNode{ElemTypedata;BinTreeNode*leftChild,*rightChild;}现采用输入广义表表示建立二叉树.具体规定如下:(1)

5、树的根结点作为由子树构成的表的表名放在表的最前面;(2)每个结点的左子树和右子树用逗号隔开.若仅有右子树没有左子树,逗号不能省略.(3)在整个广义表表示输入的结尾加上一个特殊的符号(例如”#”)表示输入结果.例如,对于如右图所示的二叉树,其广义表表示为A(B(D,E(G,)),C(,F))A/BC/DEF/G此算法的基本思路是:依次从保存广义表的字符串ls中输入每个字符.若遇到的是字母(假定以字母作为结点的值),则表示是结点的值,应为它建立一个新的结点,并把该结点作为左子女(当k=1)或有子女(当k=2)链接到其双亲结点上.若遇到的是

6、左括号”(“,则表明子表的开始,将k置为1;若遇到的是右括号”)”,则表明子表结果.若遇到的是逗号”,”,则表示以左子女为根的子树处理完毕,应接着处理以右子女为根的子树,将k置为2.在算法中使用了一个栈s,在进入子表之前,将根结点指针进栈,以便括号内的子女链接之用.在子表处理结束时退栈.相关的栈操作如下:MakeEmpty(s)置空栈Push(s,p)元素p进栈Pop(s)进栈Top(s)存取栈顶元素的函数下面给出了建立二叉树的算法,其中有5个语句缺失.请阅读此算法并把缺失的语句补上.(每空3分)VoidCreateBinTree(Bi

7、nTreeNode*&BT,charls){Stacks;MakeEmpty(s);BT=NULL;//置二叉树BinTreeNode*p;intk;istreamins(ls);//把串ls定义为输入字符串流对象insCharch;ins>>ch;//从ins顺序读入一个字符While(ch!=”#”){//逐个字符处理,直到遇到'#'为止Switch(ch){case’(‘:_______(1)_______k=1;break;case’)’:pop(s);break;case’,‘:_______(2)_______break;d

8、efault:p=newBinTreeNode;_______(3)_______p->leftChild=NULL;p->rightChild=NULL;if(BT==NULL)_______(4)___