软件技术基础第二章课后习题答案.doc

习题2.1什么是数据结构？它对算法有什么影响？答：数据结构是指同一数据对象中各数据元素间存在的关系。数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。习题2.2何谓算法？它与程序有何区别？答：广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。和程序的区别：一个程序包括两个方面的内容：（1）对数据的描述，即数据结构。（2）对操作的描述，即算法。所以算法是程序的一个要素。习题2.3何谓频度，时间复杂度，空间复杂度？说明其含义。答：频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。习题2.4算法：A=(a0,a1an)mul1/sum=a0fori=1tonmulmul*xsum=Ai*mul+sum/求和end(i)程序代码：#include#include#define N 10double polynomail(int a,int i,double x,int n);int main() double x;int n,i;int aN;printf(输入变量的值x:);cinx;coutn;if(nN-1) exit(0);cout输入多项式的系数a0-an:;for(i=0;iai;coutThe polynomail value is polynomail(a,n,x,n)0) return an-i+polynomail(a,i-1,x,n)*x;else return an; 本算法的时间复杂度为O(n)。 习题2.9bool IsSubSequence(String a , int n, String b , int m) int i=0; int j=0; while (i n) if (ai = bj) /* 相等时，下标同时向后移动一个位置. */ i+;j+; else j+; /* 不等时,只将b数组下标向后移动一个位置. */ if (j = m) /* 当b数组找完时，指向了第m+1个不存在的元素，则不符合。 */ return false; /a不是b的子序列 return true; /a 是b 的子序列 上机需要定义main函数 别偷懒哦习题2.10void mgsl(int n,int a ,int m, int b , int c )int k=0,i=0,j=0; while(in)&(jm) if(ai=bj) /复制有序表a中的元素 ck=ai;i=i+1; else ck=bj;j=j+1;k=k+1; if(i=n) /复制有序表b中剩余元素 for(i=j;im;i+) ck=bi;k=k+1; else /复制有序表a中剩余元素 for(j=i;jn;j+) ck=aj;k=k+1; return; 习题2.11void invsl(int n,int a )int k;int t;for(k=1;k=n/2;k+)t=ak-1; ak-1=an-k; an-k=t;return;int main() int a10=1,2,.; invsl(10,a); for(int i=0;inext;i+;return i;习题2.13 int DeleteElem_L(LinkList &L,int x,int k)int i=1;LinkList p=L;while(p&i!=k-1)p=p-next;i+;p=p-next-next; 习题2.14设待插入的结点值为x，则至少需要考虑下面三种情况：1.prev-val x current-val: 插入到prev和current之间。2. x是链表中最小或者最大的值： 插入x到链表头部的前面。3.回到起始点： 插入到起始点前面。第1和2种情况还比较容易考虑到，但是第3种情况往往会被忽略，先给出代码，再根据代码来分析这些情况为什么都需要考虑到。1. voidinsert(Node*&aNode,intx)2. /链表为空，创建节点返回 3. if(!aNode)4. aNode=newNode(x);5. aNode-next=aNode;6. return;7. 8. 9. Node*p=aNode;10. Node*prev=NULL;11. do12. prev=p;13. p=p-next;14. if(xdata&x=prev-data)break;/情况1，找到正常位置返回，如例子中插入4到链表中 15. if(prev-datap-data)&(xdata|xprev-data)break;/情况2，x最小或者最大，插入到链表最前面 16. while(p!=aNode);/情况3，回到起始结点，停止. 17. 18. Node*newNode=newNode(x);19. newNode-next=p;20. prev-next=newNode;21. 1）链表只有一个结点 如果x等于该结点值，则直接在情况1处理。否则情况3处理。2）链表包含重复值 如果链表为1-*1-1，起始结点为第二个1，则在其中插入2时，由情况3处理，即最终插入到初始结点前面。会变成1-2-1-1.循环链表从第二个1开始，照样是有序的。习题2.15/ 将合并后的结果放在C表中，并删除B表Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C)LinkList pa,pb,qa,qb;pa=A-next;pb=B-next;C=A;while(pa&pb)qa=pa;qb=pb;pa=pa-next;pb=pb-next;qb-next=qa-next;qa-next=qb;if(!pa)qb-next=pb;pb=B;free(pb);return OK;习题2.18/ 在单循环链表S中删除S的前驱结点Status ListDelete_CL(LinkList &S)LinkList p,q;if(S=S-next)return ERROR;q=S;p=S-next;while(p-next!=S)q=p;p=p-next;q-next=p-next;free(p);return OK;习题2.19/ 带头结点的单链表的逆置Status ListOppose_L(LinkList &L)LinkList p,q;p=L;p=p-next;L-next=NULL;while(p)q=p;p=p-next;q-next=L-next;L-next=q;return OK;习题2.21 有一铁路交换站如题图（栈），火车从右边开进交换站，然后再开到左边，每节车厢均有编号如1，2，3，n。请问： （1）当n=3和n=4时有哪几种排序方式？哪几种排序方式不可能发生？（2）当n=6时，325641这样的排列是否能发生？154623的排列是否能发生？解：N=3时可能的出栈序列：1231S1X2S2X3S3X 1321S1X2S3S3X2X2131S2S2X1X3S3X2311S2S2X3S3X1X312CAB 3211S2S3S3X2X1XN=4，不可能的排列：4312421342314123413231243142341214232413N=6时，325641可能154623不可能 习题2.24双向栈（a ,m,top1,top2,x） top1=m; top2=1; if(top1= =top2)thenprintf(“上溢”),return ERROR while(top1!=top2) if(x%2= =0) atop2=x;top2+;else atop1=x; top1- -; 习题2.26用三元组和带行辅助向量形式表示下列稀疏矩阵： （1）： （2）： （1）：三元组 带行辅助向量行列值1115142216651916328 (2): 三元组 带行辅助向量i123456POS146778NUM321011 行列值11815-131926211524628532-334436344248453 -1262274481791129429669930i123456789POS147101213141516NUM333211114习题2.27 试说明树与二叉树有何不同？为何要将一般树转换为二叉树？解：树与二叉树区别：树是由n个（n=0）结点组成的有限集合T，其中有且仅有一个结点称为根结点，在此类元素结点之间存在明显的分支和层次关系。二叉树是一种特殊的树结构，每一个结点最多只有两个孩子，即最多只有两个分支。为何要转换：一般树，树中结点次序没有要求，分支庞杂。而二叉树，元素之间存在严谨的前后代关系，在对数据元素进行删除、查找、插入等运算时更加有效率。习题2.28DEFIJKGLABC 习题2.29 解：在一般的二叉树中，叶子结点总是比度为2的结点多1个。而在完全二叉树中，度为1的结点最多有1个。综合以上两点，如果完全二叉树的结点数为奇数，设为2n+1,则没有度为1的结点，在所有结点中有n个是度为2的结点，n+1个是叶子结点；如果完全二叉树的结点数为偶数，设为2n,则其中有1个是度为1的结点，剩下的结点中有n-1个是度为2的结点，n个是叶子结点。 本题中，如果完全二叉树公有1000个结点，则有500个叶子结点，499个度为2的结点，有1个度为1的结点。习题2.30 设一棵二叉树其中序和后序遍历为中序：BDCEAFHG 后序：DECBHGFA画出这棵二叉树的逻辑结构，并写出先序遍历结果。 先序遍历：ABCDEFGH其逻辑结构如下：ABFCDEGH习题2.31 (1) / 复制一棵二叉树Status CopyBiTree(BiTree& T,BiTree& T1)BiTree p;if(T)p=new BiTNode;if(!p) return ERROR;p-data=T-data;T1=p;CopyBiTree(T-lchild,T1-lchild);CopyBiTree(T-rchild,T1-rchild);elseT1=T;return OK;(2) / 判断两棵二叉树是否相等/* T1,T2分别指向两个二叉树的根结点.若T1与T2相等,则返回1;否则返回0 */int BiTreeEqual(BiTree &T1, BiTree &T2)if (T1 = NULL & T2 = NULL) return 1;if (T1 != NULL & T2 != NULL & T1 - data = T2 - data & BiTreeEqual(T1 - leftChild, T2 - leftChild) & BiTreeEqual(T1 - rightChild, T2 - rightChild) return 1;return 0;(3) / 计算二叉树的树叶 Status POLeafNodeNum(int& i,BiTree& T)if(T)if(!T-lchild & !T-rchild) i+;POLeafNodeNum(i,T-lchild);POLeafNodeNum(i,T-rchild);return OK;(4) / 求二叉树的深度int BiTDepth(BiTree& T)int ldep,rdep;if(!T) return 0;elseldep=BiTDepth(T-lchild)+1;rdep=BiTDepth(T-rchild)+1;ret