《数据结构》各章课后作业答案
第一章 绪论课后作业答案
1. 简述线性结构与非线性结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。
2．分析下面各程序段的时间复杂度（每小题5分，共20分） （1） for (i=0; i A[i][j]=0; (3) x=0; for(i=1; i for (j=1; j<=n-i; j++) x++; （2）s=0; for（i=0; i for(j=0; j i=i*3; 答：O（n2） while(i<=n) 解：1.第一个for循环执行n+1次，第二个for循环执行n(m+1)次，A[i][j]=0;语句执行n*m次，此程序段总的执行次数为n+1+n*(m+1)+n*m=2nm+2n+1次。故时间复杂度为O(n*m)。 2.算法的时间复杂度是由嵌套最深层语句的执行次数决定的，本程序段嵌套最深层语句为： s+=B[i][j]; 22 它的执行次数为n，所以本程序段的时间复杂度是O(n)。 3. 该算法的基本操作是语句x++, 其语句频度为： ??1=?(n?i)= i?1j?12 n?1n?in?1i?0n(n?1) 2所以本程序段的时间复杂度是O(n)。 4.设语句执行m次，则有 m 3≤n 所以本程序段的时间复杂度为O(log3n)。 m≤log3n 第二章 线性表课后作业答案 1. 填空题。 （1）在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 （2）线性表中结点的集合是 有限 的，结点间的关系是 一对一的。 （3）向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移 动 n-i+1 个元素。 （4）顺序表中逻辑上相邻的元素的物理位置 必定相邻 。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。 2.试写一算法，对单链表实现就地逆置。 分析：将单链表就地逆置，即不另外开辟结点空间，而将链表元素翻转顺序。 解：从链上依次取下结点，按照逆序建表的方法重新建表。 void Reverse ( LinkList &L ){ p = L->next; // 原链表 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；问在这两种情况下，循环队列中各有元素多少个？ 解：用队列长度计算公式：(N＋r－f)%N ①L=(40＋19－11)@=8 ②L=(40＋11－19)@=32 3.写出下列程序段的输出结果（栈的元素类型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(s[i+j]==t[j]) j++; else { ② ; ③ ;} } if( ④ ) retrun i; else return –1; } 解：可以参照课本上模式匹配算法中的BF算法思想。 答案为：①i ②i++ ③j=0 ④j>=strlen(t) 2．写出子串t=”ABCABCACAB”的next值和nextval值。 解： j 模式串 next[j] nextval[j] 1 A 0 0 2 B 1 1 3 C 1 1 4 A 1 0 5 B 2 1 6 C 3 1 7 A 4 0 8 C 5 5 9 A 1 0 10 B 2 1 第五章 数组和广义表课后作业答案 1、选择题。 （1）设数组a[1..60, 1..70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,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]]*2＝8950 （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=??log2n??＋1 =10;且前9层总结点数为2-1=511 (完全二叉树的前k-1层肯定是满的)，所以末层叶子数为1000-511=489个。由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。 请注意叶子结点总数≠末层叶子数！还应当加上第k-1层（靠右边）的0度结点个数。 根据分析末层的489个叶子只占据了上层的245个结点（??498/2??）上层（k=9）右边的0度结点数还有2-1-245=11个。所以，全部叶子数＝489(末层)＋11(k-1层)=500个。度为2的结点＝叶子总数－1=499个。 解2：可先求2度结点数,再由此得到叶子总数。 8 首先，k-2层的2-1（255）个结点肯定都是2度的（完全二叉）。另外，末层叶子（刚才已求出为489）所对应的双亲也是度＝2，（共有??498/2??＝244个）。所以，全部2度结点数为255(k-2层)＋244(k-1层)=499个；总叶子数＝2度结点数＋1=500个。 （2）用二叉链表存储n个结点的二叉树(n>0)，共有 n+1 个空指针域；采用三叉链表存储，共有 n+2 个空指针域。 9 9 解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个结点的不相似的二叉树的棵数为当n=3时， 1nC2n（即为Catalan数）去计算。n?11nC2n=5。 n?12、假设一棵二叉树的层序序列为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） 图的逆邻接表存储结构只适用于 有向 图。