清华大学2001�q�硕士研�I�生考试数据�l�构试题_跨考网

复习(f��n)紧张�Q�焦头烂额？逆风轻袭�Q�来跨考秋季集训营�Q�帮你寻�Ҏ(gu��)���Q�定�Ҏ(gu��)���Q?/span> 了解一�?>

　　一、试�l�出下列有关�q�查�?mfsets)的操作序列的�q�算�l�果�Q?/p>

　　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是合�q�运���，在以前的书中命名为merge)

　　要求

　　(1) 对于union(i,j)�Q�以i作�ؓ(f��)j的双�Ԍ�� (5�?

　　(2) 按i和j为根的树(w��i)的高度实现union(i,j)�Q�高度大者�ؓ(f��)高度���者的双亲�Q?(5�?

　　(3) 按i和j为根的树(w��i)的结点个数实现union(i,j)�Q�结点个数大者�ؓ(f��)�l�点个数���者的双亲�Q?(5�?

　　二、设�?�?A,B,C,D)之间架设�?座桥,如图所�C?

　　要求从某一地出�?�l�过每��桥恰巧一��?最后仍回到原地

　　(1) 试就以上囑�Ş说明:此问题有解的条�g是什�? (5�?

　　(2) 讑֛�中的��点��Cؓ(f��)n,试用C或Pascal描述与求解此问题有关的数据结构�ƈ�~�写一个算�?扑և�满��要求的一条回�? (10�?

　　三、针对以下情�늡�定非递归的归�q�排序的�q�行旉���(数据比较�ơ数与移动次�?:

　　(1) 输入的n个数据全部有�? (5�?

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

　　(3) 随机地输入n个数�? (5�?

　　四、简单回�{�有关AVL�?w��i)的问�?

　　(1) 在有N个结点的AVL�?w��i)�?为结点增加一个存攄���炚w��度的数据成员,那么每一个结炚w��要增加多���个字位(bit)? (5�?

　　(2) 若每一个结点中的高度计数器�?bit,那么�q�样的AVL�?w��i)可以有多少�?最���有多少个关键码? (5�?

　　五、设一个散列表包含hashSize=13个表��?.其下标从0�?2,采用�U�性探查法解决冲突. ��h��以下要求,���下列关键码散列到表�?

　　10 100 32 45 58 126 3 29 200 400 0

　　(1) 散列函数采用除留余数�?�?hashSize(取余�q�算)���各关键码映像到表中. ��h��出每一个��生冲�H�的关键码可能��生多���次冲突. (7�?

　　(2) 散列函数采用先将关键码各位数字折叠相�? 再用%hashSize���相加的�l�果映像到表中的办法. ��h��出每一个��生冲�H�的关键码可能��生多���次冲突. (8�?

　　六、设一���二叉树(w��i)的结点定义�ؓ(f��)

　　struct BinTreeNode{

　　ElemType data;

　　BinTreeNode *leftChild, *rightChild;

　　}

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

　　(1) �?w��i)的根结点作为由子�?w��i)构成的表的表名放在表的最前面;

　　(2) 每个�l�点的左子树(w��i)和右子树(w��i)用逗号隔开. 若仅有右子树(w��i)没有左子�? 逗号不能省略.

　　(3) 在整个广义表表示输入的结���֊�上一个特�D�的�W�号(例如�?�?表示输入�l�果.

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

　　A

　　/ \

　　B C

　　/ \ \

　　D E F

　　/

　　G

　　此算法的基本思�\�?依次从保存广义表的字�W�串ls中输入每个字�W? 若遇到的是字�?假定以字母作为结点的�?, 则表�C�是�l�点的�? 应�ؓ(f��)它徏立一个新的结�? �q�把该结点作为左子女(当k=1)或有子女(当k=2)链接到其双亲�l�点�? 若遇到的是左括号�?�? 则表明子表的开�?���k�|��ؓ(f��)1;若遇到的是右括号�?�? 则表明子表结�? 若遇到的是逗号�?�? 则表�C�Z��左子女�ؓ(f��)根的子树(w��i)处理完毕,应接着处理以右子女为根的子�? ���k�|��ؓ(f��)2.

　　在算法中使用了一个栈s, 在进入子表之�?���根�l�点指针�q�栈, 以便括号内的子女链接之用. 在子表处理结束时退�? 相关的栈操作如下:

　　MakeEmpty(s) �|�空�?/p>

　　Push(s,p) 元素p�q�栈

　　Pop(s) �q�栈

　　Top(s) 存取栈顶元素的函�?/p>

　　下面�l�出了徏立二叉树(w��i)的算�? 其中�?个语句缺�? 请阅��L�����法�q�把�~�失的语句补�? (每空3�?

　　Void CreateBinTree(BinTreeNode *&BT, char ls){

　　Stacks; MakeEmpty(s);

　　BT=NULL; //�|�二叉树(w��i)

　　BinTreeNode *p;

　　int k;

　　istream ins(ls); //把串ls定义�����入字�W�串���对象ins

　　Char ch;

　　ins>>ch; //从ins��序��d��一个字�W?/p>

　　While(ch!=�?�?{ //逐个字符处理,直到遇到''#''为止

　　Switch(ch){

　　case�?�? _______(1)_______

　　k=1;

　　break;

　　case�?�? pop(s);

　　break;

　　case�?�? _______(2)_______

　　break;

　　default: p=new BinTreeNode;

　　_______(3)_______

　　p->leftChild=NULL;

　　p->rightChild=NULL;

　　if(BT==NULL)

　　_______(4)_______

　　else if (k==1) top(s)->leftChild=p;

　　else top(s)->rightChild=p;

　　}

　　_______(5)_______

　　}

　　}

　　七、下面是一个用C�~�写的快速排序算�? ��Z��避免最坏情�?取基准记录pivot采用从left,right和mid=[(left+right)/2]中取中间�? �q�交换到right位置的办�? 数组a存放待排序的一�l�记�? 数据�c�d��为Type, left和right是呆排序子区间的最左端点和最右端�?

　　Void quicksort(Type a,int left,int right){

　　Type temp;

　　If(leftType pivot=median3(a,left,right);

　　Int I=left, j=right-1;

　　For( ; ; ){

　　While(iWhile(iif(itemp=a[i]; a[j]=a[i]; a[i]=temp;

　　I++; j--;

　　}

　　else break;

　　}

　　if(a[i]>pivot)

　　{temp=a[i]: a[i]=a[right]; a[right]=temp;}

　　quicksort(a,left,i-1); //递归排序左子区间

　　quicksort(a,i+1,right); //递归排序叛_��区间

　　}

　　}

　　(1) 用C或Pascal实现三者取中子�E�序 median3(a,left,right); (5�?

　　(2) 改写 quicksort ���法, 不用栈消�ȝ��二个递归调用 quicksort(a,i+1,right); (5�?

　　(3) �l�箋改写 quicksort ���法, 用栈消去剩下的递归调用. (5�?