清华大学《数据结构与算法》(4)

a c b e f d

yxh：都不可能

13、栈的存储方式有哪两种？ yxh：顺序表、链

14、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。其中： 单链表和单循环链表的结点结构为

data next prior data next

双向链表的结点结构为

YXH:单链表不行，单循环链表和双向链表可以； 单循环链表： q=p

while(q->next!=p) q=q->next; temp=q->data; q->data=p->data; p->data=temp;

双向链表：

temp=p->data;

p->data=p->prior->data;

p->prior->data=temp;

15、假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。

(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；

(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。

16、试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过2.0。并请验证你造的哈希表的实际平均查找长度是否满足要求。（CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,WANG,CAO,YUN,CHANG,YANG）

设用线性探测再散列解决冲突，根据公式Snl≈（1+1/（1-α））/2 。可求出负载因子为α=0.67。再根据数据个数和装载因子，可求出表长m=15/0.67，取m=23。设哈希函数H（key）=（关键字首尾字母在字母表中序号之和）MOD 23。

从上表求出查找成功时的平均查找长度为ASLsucc=19/15<2.0，满足要求。

17、用链表表示的数据的简单选择排序，结点的域为数据域data ，指针域 next ；链表首指针为head ，链表无头结点。 selectsort(head) p=head;

while (p(1)_______) {q=p; r=(2)_______ while((3)______ )

{if ((4)_______ ) q=r;

r=(5)_______ ;

}

tmp=q->data; q->data=p->data; p->data=tmp; p= (6)_______ ; }

题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。(1)!=null (2)p->next (3)r!=null (4)r->datadata (5)r->next (6)p->next

18、设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。

19、 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。

20、下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，?,依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。 void sort(SqList &r,int n) { i=1;

while((1)__) {

min=max=1;// min=max=i

for (j=i+1;(2)____ ;++j)

{if((3)____) min=j; else if(r[j].key>r[max].key) max=j; } if((4)_____) r[min] < ---- >r[j];// r[i]

if(max!=n-i+1){if ((5)___) r[min] < ---- > r[n-i+1]; else ((6)__); } i++;

} }//sort

(1)ir[n-i+1]

21、 堆是一种有用的数据结构. 堆排序是一种_(1)_排序，堆实质上是一棵_(2)_结点的层次

序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是_(3)_，所需的附加存储结点是_(4)_。关键码序列05，23，16，68，94，72，71，73是否满足堆的性质_(5)_。

(1) 选择 (2)完全二叉树 (3)O(Nlog2N) (4)O(1) (5)满足堆的性质

22、在堆排序、快速排序和合并排序中：

(1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？

(2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？

(3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？

(4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？

(1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序

23、

算法模拟

设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。

(1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。

(2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。

(3) 直接插入排序算法和直接选择排序算法的稳定性如何？

(1)直接插入排序 第一趟 第四趟

(3)[8,3],2,5,9,1,6 第二趟 (2)[8,3,2],5,9,1,6 (5)[8,5,3,2],9,1,6

(9)[9,8,5,3,2],1,6 第五趟 (1)[9,8,5,3,2,1],6 (6)[9,8,6,5,3,2,1]

第第

三六

趟趟

(2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束） 第一趟 (9)[9],3,2,5,8,1,6 第二趟 (8)[9,8],2,5,3,1,6 第 第四趟

(6)[9,8,6],5,3,1,2

(5)[9,8,6,5],3,1,2 第五趟 (3)[9,8,6,5,3],1,2 (2)[9,8,6,5,3,2],1

第

三六

趟趟

(3)直接插入排序是稳定排序，直接选择排序是不稳定排序。

四 算法阅读

1、void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={1,5,8,12,15}; for(i=0;i<5;i++) Push(S,2*a[i]); while(!StackEmpty(S)) print(Pop(S)); }

该算法被调用后得到的输出结果为： YXH：30 24 16 10 2 10

2、 void ABC (BTNode *BT,int &c1,int &c2) { if (BT !=NULL )

{ ABC(BT->left,c1,c2); c1++; if (BT->left==NULL&&BT->right==NULL) c2++; ABC(BT->right,c1,c2); }//if }

该函数执行的功能是什么？

YXH：统计结点总数(c1)和叶子结点总数（c2）

3、在下面的每个程序段中，假定线性表La的类型为List，e的类型为ElemType,元素类型ElemType为int，并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。

（1）InitList(La);

Int a[]={100,26,57,34,79}; For (i=0;i<5;i++)

ListInsert(La,1,a[i]); YXH:79 34 57 26 100

（2）ListDelete(La,1,e);

ListInsert(La,ListLength(La)+1,e); YXH: 34 57 26 100 79

（3）ClearList(La); For (i=0;i<5;i++)

ListInsert(La,i+1,a[i]); YXH: 100 26 57 34 79

4、int Prime(int n) {

int i=1;

int x=(int) sqrt(n); while (++i<=x)

if (n%i==0) …… 此处隐藏：2386字，全部文档内容请下载后查看。喜欢就下载吧 ……