《数据结构》各章课后作业答案

1、数据结构各章课后作业答案第一章 绪论课后作业答案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

2、 = 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，

3、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

4、); 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

5、模式串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个字节存储，

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、递归算法比非递归算法花费更多的时间，对吗？为什么？答：不

7、一定。时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。第六章 树和二叉树课后作业答案1、填空题。（1）一棵完全二叉树有1000个结点，则它必有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。分析题意：已知n=1000,求n0和n2,还要判断末叶子是挂在左边还是右边？解1: 易求出总层数和末层叶子数。总层数k=1 =10;且前9层总结点数为29-1=51

8、1 (完全二叉树的前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度的（完全二叉）。另外

9、，末层叶子（刚才已求出为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个。所以根据分

10、析，得到如下等式：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;

11、/空树没有叶子 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） 图的逆邻接表存储结构只适用于 有向 图。（

12、5）用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。（6）拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。2、求解下图的最小生成树，并计算出它的权值。解：图的最小生成树如下： 最小生成树的权值为1+5+4+2+3=15。第九章 查找课后作业答案1、填空题。（1）具有11个元素的有序表进行折半查找，则平均查找长度为 3,3 。解：先看一个具体的情况，假设表长n=11。i为有序表中元素的位置，Ci为在折半查找过程中比较的次数。i1234567891011Ci34234134234ASLbs=(11+22+34+44)/11=3.3。

13、（2）在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。（3）在分块查找方法中，首先查找 索引表 ，然后再查找相应的 块表 。（4）在散列函数H(key)=key%m中，m应取 素数 。2、设散列表长为7，记录关键字组为：15,14,28,26,56,23，散列函数：H(key)=key MOD 7，冲突处理采用线性探测法，将它们填入表中。解：H(15)=15 MOD 7=1 H(14)=14 MOD 7=0 H(28)=28 MOD 7=0 冲突 H1(28)=1 又冲突 H2(28)=2 H(26)=26 MOD 7=5H(56)=56 MOD 7=0 冲突 H1(5

14、6)=1 又冲突 H2(56)=2 又冲突 H3(56)=3 H(23)=23 MOD 7=2 冲突 H1(23)=3 又冲突H3(23)=4各个关键字的存放的位置如下： 0 1 2 3 4 5 6141528562326第十章 内部排序课后作业答案1、填空题。（1）大多数排序算法都有两个基本的操作： 比较（两个关键字的大小） 和 移动（记录或改变指向记录的指针）。（2）对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2) 。若对其进行快速排序，在最坏的情况下所需要的时间是 O(n2) 。（3）对于n个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n) ，所需要的附加空间是 O(n) 。（4）对于n个记录的表进行2路归并排序，整个归并排序需进行 log2n 趟，共计移动 nlog2n 次记录。注：需要log2n趟，每趟都要移动n个元素，移动到新表中的总次数为nl