《数据结构第一次至第四次作业答案.docx》由会员分享，可在线阅读，更多相关《数据结构第一次至第四次作业答案.docx（5页珍藏版）》请在三一办公上搜索。
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( !St
2、ackEmpty(S) ) Pop(S,&e); printf(%d”,e); /conversion 2.设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为(615)。 3.在一个单链表中删除p所指结点的后继结点时，应执行以下操作： q=p-next; p-next=(q-next) 4.一个算法的效率可分为(时间 )效率和效率。 5.数据结构被形式地定义为，其中D是的有限集合，R是D上的有限集合。 6.下面程序段的时间复杂度是） for(i=0;im;i+) for(j=0;jlchild=NULL)&(root-rchild=N
3、ULL)sum+; printf(%dn,root-data); DLR(root-lchild); DLR(root-rchild); return(0); 4、(1)s-next=p-next (2)p-next=s 5、ACBDACDB ADCB (4)BCDA (5)BCAD (6)BDCA (7) CABD (8)CADB (9)CDAB (10)DCBA 6、 7、：(1)广度优先遍历序列：1; 2, 3, 4; 5; 6 (2)最小生成树 1 1 1 1 1 1 1 1 2 3 3 3 3 5 4 4 4 6 4 2 6 4 2 6 1 1 2 3 5 3 5 4 4 2 6 第
4、四次作业答案 1、写出用直接插入排序将关键字序列54,23,89,48,64,50,25,90,34排序过程的每 一趟结果。 答案：初始： 54，23，89，48，64，50，25，90，34 1： ，89，48，64，50，25，90，34 2： ，48，64，50，25，90，34 3： ，64，50，25，90，34 4： ，50，25，90，34 5： ，25，90，34 6： ，90，34 7： ，34 8： 2设待排序序列为10,18,4,3,6,12,1,9,15,8请写出希尔排序每一趟的结果。增量序列为 5，3，2，1。 答案：初始： 10，18，4，3，6，12，1，9，15
5、，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，18 3. m*n 4. n*n 5. 设循环队列的容量为40，现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？ 答：用队列长度计算公式：(N+r-f)%N (1)L=(40+19-11)%40=8 (2)L=(40+11-19)%40=32 6、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用存储方式最节省时间. 7.在一个长度为n的顺序表中删除第i个元素，需要向前移动个元素 8、带头结点的单链表head为空的判定条件是(head-next=NULL) 9、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为%m 10、设串长为n，模式串长为m，则KMP算法所需的附加空间为(O(m) A：唯一的 B：31 C：是一棵树也是一棵二叉树 C：28 D：可行性、确定性和有穷性
