《软件技术基础第二章课后习题答案》由会员分享,可在线阅读,更多相关《软件技术基础第二章课后习题答案(25页珍藏版)》请在金锄头文库上搜索。
1、习题 2.1 什么是数据结构?它对算法有什么影响? 答:数据结构是指同一数据对象中各数据元素间存在的关系。 数据结构对算法的影响:算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关,因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分,它对程序的质量影响很大。 习题 2.2 何谓算法?它与程序有何区别? 答:广义地说,为解决一个问题而采取的方法和步骤,就称为“算法” 。计算机算法是通过计算机能执行的算法语言来表达的。 和程序的区别:一个程序包括两个方面的内容: (1)对数据的描述,即数据结构。 (2)对操作的描述,即算法
2、。 所以算法是程序的一个要素。 习题 2.3 何谓频度,时间复杂度,空间复杂度?说明其含义。 答:频度:在某个算法中某个语句被重复执行的次数就是此语句的频度。 时间复杂度:是用来估算一个算法的执行时间的量,以算法中频度最大的语句来度量。 空间复杂度:指在算法中所需的辅助空间的单元,而不包括问题的原始数据占用的空间。习题 2.4算法:A=(a0, a1 an) mul 1 / sum=a0 for i=1 to n mul mul * x sum = Ai*mul + sum /求和 end(i) 程序代码:#include#include#define N 10double polynomai
3、l(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);coutai;cout0) 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 next;i+;return i;习题
4、 2.13int 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 种情况往往会被忽略,先给出代码,再根据代码来分析这些情况为什么都需要考虑到
5、。1. void insert(Node *& aNode, int x) 2. /链表为空,创建节点返回 3. if (!aNode) 4. aNode = new Node(x); 5. aNode-next = aNode; 6. return; 7. 8. 9. Node *p = aNode; 10. Node *prev = NULL; 11. do 12. prev = p; 13. p = p-next; 14. if (x data & x = prev-data) break; / 情况 1,找到正常位置返回,如例子中插入 4 到链表中 15. if (prev-data
6、p-data) & (x data | x prev-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 处理,即最终插入到初始结
7、点前面。会变成 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/ 在单循环链表
8、 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
9、OK;习题 2.21 有一铁路交换站如题图(栈) ,火车从右边开进交换站,然后再开到左边,每节车厢均有编号如 1,2,3,n。请问: (1)当 n=3 和 n=4 时有哪几种排序方式?哪几种排序方式不可能发生? (2)当 n=6 时,325641 这样的排列是否能发生?154623 的排列是否能发生?解: N=3 时可能的出栈序列: 123 1S1X2S2X3S3X 132 1S1X2S3S3X2X 213 1S2S2X1X3S3X 231 1S2S2X3S3X1X 312 CAB 321 1S2S3S3X2X1X N=4,不可能的排列: 4312 4213 4231 4123 4132312
10、4 3142 3412 1423 2413 N=6 时, 325641 可能 154623 不可能习题 2.24双向栈(a ,m,top1,top2,x)top1=m;top2=1;if(top1= =top2)thenprintf(“上溢”),return ERRORwhile(top1!=top2)if(x%2= =0)atop2=x;top2+;elseatop1=x;top1- -;习题 2.26用三元组和带行辅助向量形式表示下列稀疏矩阵:(1): (2):028096315025 30602174004233560152618(1):三元组 带行辅助向量行 列 值1 1 151 4
11、221 6 -152 2 112 3 33 4 -65 1 916 3 28(2): 三元组 带行辅助向量行 列 值1 1 81 5 -131 9 262 1 152 4 6i 1 2 3 4 5 6POS 1 4 6 7 7 8NUM 3 2 1 0 1 12 8 53 2 -33 4 43 6 34 4 24 8 45 3 -126 2 27 4 48 1 79 1 129 4 29 6 69 9 30习题 2.27 试说明树与二叉树有何不同?为何要将一般树转换为二叉树?解:树与二叉树区别:树是由 n 个(n=0)结点组成的有限集合 T,其中有且仅有一个结点称为根结点,在此类元素结点之间存
12、在明显的分支和层次关系。二叉树是一种特殊的树结构,每一个结点最多只有两个孩子,即最多只有两个分支。为何要转换:一般树,树中结点次序没有要求,分支庞杂。而二叉树,元素之间存在严谨的前后代关系,在对数据元素进行删除、查找、插入等运算时更加有效率。习题 2.28DEFIJKGLABC习题 2.29解:在一般的二叉树中,叶子结点总是比度为 2 的结点多 1 个。而在完全二叉树中,i 1 2 3 4 5 6 7 8 9POS 1 4 7 10 12 13 14 15 16NUM 3 3 3 2 1 1 1 1 4度为 1 的结点最多有 1 个。综合以上两点,如果完全二叉树的结点数为奇数,设为2n+1,则
13、没有度为 1 的结点,在所有结点中有 n 个是度为 2 的结点,n+1 个是叶子结点;如果完全二叉树的结点数为偶数,设为 2n,则其中有 1 个是度为 1 的结点,剩下的结点中有 n-1 个是度为 2 的结点,n 个是叶子结点。本题中,如果完全二叉树公有 1000 个结点,则有 500 个叶子结点,499 个度为 2 的结点,有 1 个度为 1 的结点。习题 2.30设一棵二叉树其中序和后序遍历为中序:BDCEAFHG 后序:DECBHGFA画出这棵二叉树的逻辑结构,并写出先序遍历结果。先序遍历:ABCDEFGH其逻辑结构如下:AB FCD EGH习题 2.31(1) / 复制一棵二叉树Sta
14、tus 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 =
15、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;