《软件技术基础第二章课后习题答案》由会员分享，可在线阅读，更多相关《软件技术基础第二章课后习题答案（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;
