《数据结构与算法》期末练习题 - 2010-2011-1 - 带答案

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

单链表和单循环链表的结点结构为 双向链表的结点结构为

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。并请验证你造

设用线性探测再散列解决冲突,根据公式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,请标出各结点的值。

(CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,WANG,CAO,YUN,CHANG,YANG)

date next prior date next

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

void sort(SqList &r,int n) { i=1;

while((1)__) { min=max=1;

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];

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] (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

(2)直接选择排序(第六趟后仅剩一个元素,是最小的,直接选择排序结束)

(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)); }

该算法被调用后得到的输出结果为:

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 }

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

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]); (2)ListDelete(La,1,e);

ListInsert(La,ListLength(La)+1,e); (3)ClearList(La); For (i=0;i<5;i++)

ListInsert(La,i+1,a[i]);

4、int Prime(int n) {

int i=1;

int x=(int) sqrt(n);

while (++i<=x)

if (n%i==0) break; if (i>x) return 1; else return 0; }

(1)指出该算法的功能;

(2)该算法的时间复杂度是多少?

5. 写出下述算法A的功能: 其中BiTree定义如下: Typedef struct BiTNode{

TElemType data;

struct BiTNode *LChild, *RChild; }BiTNode, *BiTree;

Status A(BiTree T) {

Queue Q;

InitQueue(Q); ENQueue(Q,T);

While(not QueueEmpty(Q)) { DeQueue(Q,e);

If(e==NULL) break; Else

{ Print(e.data);

ENQueue(Q,e.LChild); ENQueue(Q.e.RChild); }

} }

6.阅读下列函数algo,并回答问题:

(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q; (2)简述算法algo的功能。 void algo(Queue *Q) {

Stack S; InitStack(&S);

while (!QueueEmpty(Q)) Push(&S, DeQueue(Q)); while (! StackEmpty(&S)) EnQueue(Q,Pop(&S)); }

yxh:(1)q中的元素为(8,7,5,4,2); (2)把队列q中的元素倒序。 五 算法填空

1、下面是在带表头结点的循环链表表示的队列上,进行出队操作,并将出队元素的值保留在x中的函数,其中rear是指向队尾结点的指针。请在横线空白处填上适当的语句。

typedef struct node { int data; struct node *next;

联系客服:779662525#qq.com(#替换为@)