《数据结构作业题.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;