《数据结构第一次至第四次作业答案》由会员分享，可在线阅读，更多相关《数据结构第一次至第四次作业答案（6页珍藏版）》请在装配图网上搜索。
1、第一次作业答案填空题：1、已知栈的基本操作函数： int InitStack(SqStack *S); /构造空栈int StackEmpty(SqStack *S);/判断栈空int Push(SqStack*S,ElemType e);/入栈int Pop(SqStack *S,ElemType *e);/出栈函数conversion实现十进制数转换为八进制数，请将函数补充完整。void conversion()InitStack(S);scanf(%d”,&N);while(N) Push(S,N%8) ;N=N/8;while( !StackEmpty(S) )Pop(S,&e);pr
2、intf(%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上的（关系）有限集合。6.下面程序段的时间复杂度是（0（m*n）for(i=0;im;i+)for(j=0;jlchild=NULL)&(root-rchild=NULL)sum+;
3、 printf(%dn,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 (8)CADB (9)CDAB (10)DCBA6、7、：(1)广度优先遍历序列：1; 2, 3, 4; 5; 6 (2)最小生成树（prim算法）16311314613144261314422561314422553第四次作业答案1、写出用直接插入排序将关键字序列54,23,89,
4、48,64,50,25,90,34排序过程的每一趟结果。答案：初始： 54，23，89，48，64，50，25，90，34 1：（23，54），89，48，64，50，25，90，34 2：（23，54，89），48，64，50，25，90，34 3：（23，48，54，89），64，50，25，90，34 4：（23，48，54，64，89），50，25，90，34 5：（23，48，50，54，64，89），25，90，34 6：（23，25，48，50，54，64，89），90，34 7：（23，25，48，50，54，64，89，90），34 8：（23，25，48，50，54，64，
5、89，90，34） 2设待排序序列为10,18,4,3,6,12,1,9,15,8请写出希尔排序每一趟的结果。增量序列为 5，3，2，1。 答案：初始： 10，18，4，3，6，12，1，9，15，8 d=5： 10，1，4，3，6，12，18，9，15，8 d=3： 3，1，4，8，6，12，10，9，15，18 d=2： 3，1，4，8，6，9，10，12，15，18 d=1： 1，3，4，6，8，9，10，12，15，183. m*n4. n*n5. 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rea
6、r=11；问在这两种情况下，循环队列中各有元素多少个？答：用队列长度计算公式：(N+r-f)%N(1)L=(40+19-11)%40=8(2)L=(40+11-19)%40=326、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（顺序表）存储方式最节省时间.7.在一个长度为n的顺序表中删除第i个元素，需要向前移动（ N-i）个元素8、带头结点的单链表head为空的判定条件是(head-next=NULL)9、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为（rear-front+m）%m10、设串长为n，模式串长为m，则KMP算法所需的附加空间为(O(m)A：唯一的B：31C：是一棵树也是一棵二叉树C：28D：可行性、确定性和有穷性
数据结构第一次至第四次作业答案
