数据结构各章课后作业答案第一章 绪论课后作业答案1. 简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。2分析下面各程序段的时间复杂度（每小题5分，共20分）（2）s=0; for（i=0; in; i+)for(j=0; jn; j+) s+=Bij;sum=s;答：O（n2）（1） for (i=0; in; i+)for (j=0; jm; j+)Aij=0;(3) x=0;for(i=1; in; i+) for (j=1; j=n-i; j+)x+;(4)i=1; while(inext; / 原链表 L-next = NULL; / 新表(空表) while ( p ) / 从原链表中取下结点s s = p; p = p-next; / 插入L新表表头 s-next = L-next; L-next = s; 第三章 栈和队列课后作业答案1、填空题。（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。（2） 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。（3）在具有n个单元的循环队列中，队满时共有 n-1 个元素。2计算题。设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？解：用队列长度计算公式：(Nrf)%N L=(401911)%40=8 L=(401119)%40=323.写出下列程序段的输出结果（栈的元素类型SElem Type为char）。void main( )Stack S;char x,y;InitStack(S);x=c; y=k;Push(S,x); Push(S,a); Push(S,y);Pop(S,x); Push(S,t); Push(S,x);Pop(S,x); Push(S,s);while(!StackEmpty(S) Pop(S,y); printf(y);printf(x); 答：输出结果为“stack”。第四章 串课后作业答案1算法填空题。本算法是在S中找子串t。若找到。则返回子串t第一次出现在主串s中的位置，否则返回-1。int index(char s,char t) int i=0,j=0; while( ) if(si+j=tj) j+; else ; ; if( ) retrun i;else return 1;解：可以参照课本上模式匹配算法中的BF算法思想。答案为：istrlen(s)&j=strlen(t)2写出子串t=”ABCABCACAB”的next值和nextval值。解：j12345678910模式串ABCABCACABnextj0111234512nextvalj0110110501第五章 数组和广义表课后作业答案1、选择题。（1）设数组a1.60, 1.70的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 8950 。解：不考虑0行0列，利用列优先公式： LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1*28950（2）一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 288 个字节。 （3）三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标 、 列下标 和 元素值 。（4）求下列广义表操作的结果：GetHead【(a,b),(c,d)】= (a,b) ; GetHead【GetTail【(a,b),(c,d)】= (c,d) ; /头元素不必加括号GetHead【GetTail【GetHead【(a,b),(c,d)】= b ;GetTail【GetHead【GetTail【(a,b),(c,d)】= (d) ;2、递归算法比非递归算法花费更多的时间，对吗？为什么？答：不一定。时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。第六章 树和二叉树课后作业答案1、填空题。（1）一棵完全二叉树有1000个结点，则它必有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。分析题意：已知n=1000,求n0和n2,还要判断末叶子是挂在左边还是右边？解1: 易求出总层数和末层叶子数。总层数k=1 =10;且前9层总结点数为29-1=511 (完全二叉树的前k-1层肯定是满的)，所以末层叶子数为1000-511=489个。由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。 请注意叶子结点总数末层叶子数！还应当加上第k-1层（靠右边）的0度结点个数。根据分析末层的489个叶子只占据了上层的245个结点（）上层（k=9）右边的0度结点数还有29-1-245=11个。所以，全部叶子数489(末层)11(k-1层)=500个。度为2的结点叶子总数1=499个。解2：可先求2度结点数,再由此得到叶子总数。首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉）。另外，末层叶子（刚才已求出为489）所对应的双亲也是度2，（共有244个）。所以，全部2度结点数为255(k-2层)244(k-1层)=499个；总叶子数2度结点数1=500个。（2）用二叉链表存储n个结点的二叉树(n0)，共有 n+1 个空指针域；采用三叉链表存储，共有 n+2 个空指针域。解2：当二叉树中采用二叉树链表存储时，共有2n个指针，其中只有n-1个指针指向左右孩子，所以空指针数=2n-(n-1)=n+1。当二叉树中采用三叉树链表存储时，共有3n指针，其中只有n-1个指针指向左右右孩子，又因为根结点没有父结点，所以根结点的父指针为空，其它结点的每个父指针不为空,共有n-1个。所以根据分析，得到如下等式：3n=n-1+n-1+空指针数，解得空指针数=n+2。（3）由3个结点所构成的二叉树有 5 种形态。解2：含有n个结点的不相似的二叉树的棵数为（即为Catalan数）去计算。当n=3时，=5。2、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。【解答】3、编写递归算法，计算二叉树中叶子结点的数目。【分析】输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。【解答】算法如下：int LeafCount_BiTree(Bitree T) /求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子 else if(!T-lchild&!T-rchild) return 1; /叶子结点 else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子树的叶子数加上右子树的叶子数 /LeafCount_BiTree 第七章 图课后作业答案1、填空题。（1） 图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先遍历 、 广度优先遍历 等方法。（2） 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。（3）如果n个顶点的图是一个环，则它有 n 棵生成树。（4） 图的逆邻接表存储结构只适用于 有向 图。（5）用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。（6）拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。2、求解下图的最小生成树，并计算出它的权值。解：图的最小