数据结构作业题.docx

答案出错，本宝宝概不负责，应该没错作业题-填空题：(1) 一个有向图G中若有弧vvi,vj>'vvj,vk>和vvi,vk>,则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为i,j,k。队列是一种一线性的结构。(3)在单链表中，指针p所指结点为最后一个结点的条件是p->next=NULL。(4)二路归并排序的时间复杂度是_nlogn。(5)栈是一种线性的结构。(6)由树转换成二叉树时，其根结点的右子树总是空的。(7)直接选择排序是不稳定的，其时间复杂性为Mo(8)对无向图，其邻接矩阵是一个关于_对角线对称的矩阵。(9)由转换成二叉树时，其根结点的右子树总是空的。(10)归并排序要求待排序列由若干个有序的子序列组成。(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.顺序表但键值不一定有序。(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. rear->next->next和rear；D.rear和rear->nexto(7)堆是一个键值序列kl,k2,，kn,对i=l,2,，|_n/2_,满足(C)。.kik2ik2i+l;B.ki<k2i+l<k2i;C.kik2i且kik2i+l(2i+ln);D.kik2i或者kik2i+l(2i+ln)<,(8)已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是(D)。A.acbed；B.deabc；C.decab；D.cedba0(9)串是任意有限个(C)oA.符号构成的序列；B.符号构成的集合；字符构成的序列；D.字符构成的集合。(10)如果以链表作为栈的存储结构，则退栈操作时(C)。A.必须判别栈是否满；B.对栈不作任何判别；C.必须判别栈是否空；D.判别栈元素的类型。(U)用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值(D)。.一定都是同义词；B.一定都不是同义词；C.都相同；D.不一定都是同义词。(12)以下不稳定的排序方法是(A)。A.直接插入排序；B.冒泡排序；C.直接选择排序；D.二路归并排序。(13)在串的基本运算中，属于加工型运算的有(D)。.EQAL(S,T)；B.LENGTH(S);C.CONCAT(S,T)；D.REPLACE(S,T,R)。(14)对于线性表基本运算，以下结果是正确的是(A)。a.初始化Initiate(L),引用型运算，其作用是建立一个空表l=jB.求表长LENGTH(L),引用型运算，其结果是线性表L的长度；C读表元GET(L,i),引用型运算。若K=K=LENGTH(L),其结果是线性表L的第i个结点；否则，结果为0；D.定位LOCATE(L,X),引用型运算.若L中存在一个或者多个值与X相等的结点，运算结果为这些结点的序号的最大值；否则运算结果为Oo(15)在串的基本运算中，属于引用型运算的有(B)。A.ASSIGN(S,T);B.INSERT(SI,i,S2)；C.DELETE(S,i,j)；D.SUBSTR(S,i,j)。三、算法阅读填空：1 .以下为求单链表表长的运算，分析算法，请在处填上正确的语句。intlength_lklist(Iklisthead)/*求表head的长度*/p=haed;j=0;while(p->next!=NULL)p=p->next_;j+；)return(j);*回传表长*/2 .以下为单链表按序号查找的运算，分析算法，请在处填上正确的语句。pointerfindjklist(lklisthead,inti)p=head;j=O;while(p->next!=null&&j<=i)p=p->next;j+;if(i=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,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);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+)/*每次循环，选择出一个最小键值*/k=i;for(j=i+1;j<=n;j+)if(rk>rj)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.key<rj.key)fIag=O;p=rjjrj=rj+l;rj+l=p;if(flag)return;)四、简答题：1.对m个顶点的无向图G,采用邻接矩阵，如何判别下列有关问题：(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,58,62第六趟10,15,18,45,46,62,58,90第七趟10,15,18,45,46,58,62,90以上每趟数据都发生变化3 .下图所示为一无向连通网络，根据prim算法构造出它的最小生成树。（要求画出过程）<1,2X2,3X3,6X6,4X2,5X5,7>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;