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

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) )po

2、p(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上的（关系）有限集合。6.下面程序段的时间复杂度是（0（m*n）for(i=0;i<m;i+)for(j=0;j

3、<n;j+)aij=i*j;选择题：b 判断题：错误 正确 错误单选题：a d b 多选题：acd acd cd第二次作业答案选择题：a d b b c b 判断题：错误 错误 主观题：3、广义表a=(a),a)的表头是（a）4、稀疏矩阵一般的压缩存储方法有(三元组)和（十字链表）两种。5、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组r1.n中，若结点r有右孩子，则其右孩子是r2i+1。6、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是连通图。7、n个顶点的连通图至少有n-1条边。8、已知一个有序表为（11，22，33，44，

4、55，66，77，88，99），则折半查找55需要比较（1）次9、对一棵二叉排序树按（中序）遍历，可得到结点值从小到大的排列序列。10、一个序列中有10000个元素，若只想得到其中前10个最小元素，则最好采用（堆排序）方法。第三次作业答案b c c论述题：1.答：共计14种，分别是：1234， 1243， 1324， 1342， 1432， 2134， 2143， 2341， 2314， 2431， 3214， 3241， 3421， 4321 。主观题答案：答：1、 全进之后再出情况，只有1种：4，3，2，1 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 进2

5、个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,32、先序遍历：befcgdh 中序遍历：febgchd 后序遍历:fehgdcb3、dlr(liuyu *root) /*中序遍历 递归函数*/if(root!=null) if(root->lchild=null)&&(root->rchild=null)sum+; printf("%dn",root->data); dlr

6、(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,48,64,5

7、0,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，89，90，3

8、4） 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，rear=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、一个循环