数据结构第一次至第四次作业答案

《数据结构第一次至第四次作业答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一次作业答案填空题：1、已知栈的基本操作函数：intInitStack(SqStack*S);//构造空栈intStackEmpty(SqStack*S);//判断栈空intPush(SqStack*S,ElemTypee);//入栈intPop(SqStack*S,ElemType*e);//出栈函数conversion实现十进制数转换为八进制数，请将函数补充完整。voidconversion(){InitStack(S);scanf("%d”,&N);while(N){Push(S,N%8);N=N

2、/8;}while(!StackEmpty(S)){Pop(S,&e);printf("%d”,e);}}//conversion2.设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为(615)。3.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q=p->next;p->next=(q->next)4.一个算法的效率可分为(时间)效率和（空间）效率。5.数据结构被形式地定义为（D,R），其中D是（数据元素）的有限集合，R是D上的（关系

3、）有限集合。6.下面程序段的时间复杂度是（0（m*n））for(i=0;i

4、+1]。6、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是连通图。7、n个顶点的连通图至少有n-1条边。8、已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（1）次9、对一棵二叉排序树按（中序）遍历，可得到结点值从小到大的排列序列。10、一个序列中有10000个元素，若只想得到其中前10个最小元素，则最好采用（堆排序）方法。第三次作业答案BCC论述题：1.答：共计14种，分别是：1234，1243，1324，1342，1432，

5、2134，2143，2341，2314，2431，3214，3241，3421，4321。主观题答案：答：1、①全进之后再出情况，只有1种：4，3，2，1②进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况，有5种，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,32、先序遍历：BEFCGDH中序遍历：FEBGCHD后序遍历:FEHGDCB3

6、、DLR(liuyu*root)/*中序遍历递归函数*/{if(root!=NULL){if((root->lchild==NULL)&&(root->rchild==NULL)){sum++;printf("%d",root->data);}DLR(root->lchild);DLR(root->rchild);}return(0);}4、(1)s->next=p->next(2)p->next=s5、（1）ACBD（2）ACDB（3）ADCB(4)BCDA(5)BCAD(6)BDCA(7)CABD

7、(8)CADB(9)CDAB(10)DCBA6、7、：(1)广度优先遍历序列：1;2,3,4;5;6(2)最小生成树（prim算法）16311314613144261314422561314422553第四次作业答案1、写出用直接插入排序将关键字序列{54,23,89,48,64,50,25,90,34}排序过程的每一趟结果。答案：初始：54，23，89，48，64，50，25，90，341：（23，54），89，48，64，50，25，90，342：（23，54，89），48，64，50，25，90，3

8、43：（23，48，54，89），64，50，25，90，344：（23，48，54，64，89），50，25，90，345：（23，48，50，54，64，89），25，90，346：（23，25，48，50，54，64，89），90，347：（23，25，48，50，54，64，89，90），348：（23，25，48，50，54，64，89，90，34）2设待排序序列为{10,18,4,3,6,12,1,9,15,8}