数据结构作业题.docx

《数据结构作业题.docx》由会员分享，可在线阅读，更多相关《数据结构作业题.docx（7页珍藏版）》请在优知文库上搜索。

1、答案出错，本宝宝概不负责，应该没错作业题-填空题：(1) 一个有向图G中若有弧vvi,vjvvj,vk和vvi,vk,则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为i,j,k。队列是一种一线性的结构。(3)在单链表中，指针p所指结点为最后一个结点的条件是p-next=NULL。(4)二路归并排序的时间复杂度是_nlogn。(5)栈是一种线性的结构。(6)由树转换成二叉树时，其根结点的右子树总是空的。(7)直接选择排序是不稳定的，其时间复杂性为Mo(8)对无向图，其邻接矩阵是一个关于_对角线对称的矩阵。(9)由转换成二叉树时，其根结点的右子树总是空的。(10)归并排序要求待排序列由若干个

2、有序的子序列组成。(11)已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有12个叶子的结点。二、单项选择题：(1)设有一个无向图G=(V,E)和G=(V,E)如果G为G的生成树，则下面不正确的说法是(B)。A.G,为G的子图；B.G,为G的边通分量；C.G,为G的极小连通子图且=V5D.G,为G的一个无环子图。(2)单链表的一个存储结点包含(D)。A.数据域或者指针域；B.指针域或者链域；C.指针域和链域；D.数据域和链域。(3)二分查找要求被查找的表是(C)。A.键值有序的链接表；B.链接表但键值不一定有序；C.键值有序的顺序表；D.顺序表但键值不一定有序

3、。(4)设指针P指向双链表的某一结点，则双链表结构的对称性可用(C)式来刻划。A. p-prior-next-=p-next-next;B. p-prior-prior-=p-next-prior;C. p-prior-next-=p-next-prior;D. p-next-next=p-prior-prior(5)顺序查找法适合于(D)存储结构的查找表。.压缩；B.散列；C.索引；1) .顺序或者链式。(6)在循环链表中，将头指针改设为尾指针(rear)后，其头结点和尾结点的存储位置分别是(B)。A. real和rear-next-next;B. rear-next和rear；C. rea

4、r-next-next和rear；D.rear和rear-nexto(7)堆是一个键值序列kl,k2,，kn,对i=l,2,，|_n/2_,满足(C)。.kik2ik2i+l;B.kik2i+lk2i;C.kik2i且kik2i+l(2i+ln);D.kik2i或者kik2i+l(2i+ln)next!=NULL)p=p-next_;j+；)return(j);*回传表长*/2 .以下为单链表按序号查找的运算，分析算法，请在处填上正确的语句。pointerfindjklist(lklisthead,inti)p=head;j=O;while(p-next!=null&jnext;j+;if(i

5、=j)return(p);elsereturn(NULL);)3 .以下为单链表的插入运算，分析算法，请在处填上正确的语句。voidinsertjklist(lklisthead,datatypex,inti)/*在表head的第i个位置上插入一个以X为值的新结点*/p=findjklist(head,i-1);if(p=NULL)error(不存在第i个位置”)；elses=mailloc(size);s-data=x;s-next=p-next；p-next=s;4 .程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈S2之中去,请完成程序。SeqStackS1,S2,

6、tmp;DataTypex;.J/假设栈tmp和S2已做过初始化while(!StackEmpty(&S1)x=Pop(&S1);while(!StackEmpty(&tmp)(x=Pop(&tmp);Push(&S1,x);Push(&S2,x);)5 .以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。VOidCoIJnHeaf(bitreptrt,int*count)/*根指针为t,假定叶子数COlJnt的初值为07if(t!=NULL)if(t-lchild=NULL)&(t-rchild=NULL)*count+;countleaf(t-lchild,&count

7、);CClmtIacf(t-rchild)6 .以下程序段的功能是利用栈T,将一个非空栈S中值等于m的元素全部删去，请在-处填上正确语句。voidDemo2(SeqStack*S,intm)/设DataType为int型SeqStackT;inti;InitStack(&T);while(!StackEmpty(S)if(i=Pop(&S)!=m)Push(&T,i);while(!StackEmpty(&T)i=Pop(&T);Push(SJ);)7 .以下是直接选择排序的算法。请分析算法，并在横线上填充适当的语句。voidselect(listr,intn)for(i=1;i=n-1;i+

8、)/*每次循环，选择出一个最小键值*/k=i;for(j=i+1;jrj)k=j;if(_k!=l)swap(rk,ri)/函数SWaP(IIkHiD交换rk和币的位置*/8 .以下为冒泡排序的算法。请分析算法，并在上填充适当的语句。voidbulbblesort(intn,listr)*flag为特征位，定义为布尔型*/for(i=l;i=n-1;i+)fIag=I;for(j=lj=n-i；j+)if(rj+l.keyrj.key)fIag=O;p=rjjrj=rj+l;rj+l=p;if(flag)return;)四、简答题：1.对m个顶点的无向图G,采用邻接矩阵，如何判别下列有关问题：

9、(1) 图中有多少条边？(2) 任意两个顶点i和j是否有边相连？答：(1)数邻接矩阵里对角线上或者下的不为零的数有多少个，就是边数。(2)从矩阵里找到(i,j)位置的数，如果不为零，则有边相连。2.对于下列一组关键字46,58,15,45,90,18,10,62,试写出快速排序每一趟的排序结果，并标出每一趟中各元素的挪移方向。第一趟10,58,15,45,90,18,46,62手机做的，自己标方向第二趟10,46,15,45,90,18,58,62第三趟10,18,15,45,90,46,58,62第四趟10,18,15,45,46,90,58,62第五趟10,15,18,45,46,90,5

10、8,62第六趟10,15,18,45,46,62,58,90第七趟10,15,18,45,46,58,62,90以上每趟数据都发生变化3 .下图所示为一无向连通网络，根据prim算法构造出它的最小生成树。（要求画出过程）4 .设某密码电文由8个字母组成，每一个字母在电文中的浮现频率分别是22,15,2,5,17,11,9,19,试为这8个字母设计相应的哈夫曼编码。19=0022=012=1100015=10111=1005=110019=110117=1115 .请用类C语言编写从单链表中删除表头元素的算法。EIemTypeDeleteFront(LNode*&HL)(EIemTypedata;MHL)(LNode*p=HL-next;Data=HL-data;free(HL);HL=P;returndata;