《严飞_《软件技术基础》沈被娜习题解答》由会员分享，可在线阅读，更多相关《严飞_《软件技术基础》沈被娜习题解答（31页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章 2.1 什么是数据结构？它对算法有什么影响？什么是数据结构？它对算法有什么影响？数据结构是指同一数据对象中各数据元素间存在的关系。数据结构是指同一数据对象中各数据元素间存在的关系。数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据 类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结 构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的 基本部分，它对程
2、序的质量影响很大。基本部分，它对程序的质量影响很大。 2.2何谓算法？它与程序有何区别？何谓算法？它与程序有何区别？ 广义地说，为解决一个问题而采取的方法和步骤，就称为广义地说，为解决一个问题而采取的方法和步骤，就称为“算法算法”。计算机。计算机 算法是通过计算机能执行的算法语言来表达的。算法是通过计算机能执行的算法语言来表达的。 和程序的区别：一个程序包括两个方面的内容：和程序的区别：一个程序包括两个方面的内容： （1）对数据的描述，即数据结构。）对数据的描述，即数据结构。 （2）对操作的描述，即算法。）对操作的描述，即算法。 所以算法是程序的一个要素。所以算法是程序的一个要素。 2.3 何
3、谓频度，时间复杂度，空间复杂度？说明其含义。何谓频度，时间复杂度，空间复杂度？说明其含义。 频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。 时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的 语句来度量。语句来度量。 空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数 据占用的空间。据占用的空间。 2.4 试编写一个求多项式试编写一个求多项式 Pn =anxn +an
4、-1 xn-1+a1x+a0 的值的值 Pn(x 0)的算法，要的算法，要 求用乘法次数最少，并说明算法中主要语句的执行次数及整个算法的时间复杂求用乘法次数最少，并说明算法中主要语句的执行次数及整个算法的时间复杂 度。度。A=(a0, a1 an) mul 1 / sum=a0 for i=1 to n mul mul * x / x sum = Ai*mul + sum /求和求和 end(i) 进行了进行了 n 次次 时间复杂度为：时间复杂度为：2n 2.5 计算下列各片段程序中计算下列各片段程序中 XX+1 执行次数执行次数 (1) for i=1 to nfor j=1 to i fo
5、r k=1 to jxx+1end(k)end(j) end(i) 执行次数：执行次数：n*n*n(2)i1while i=c / 找到第找到第 1 个大于等于个大于等于 c 的元素的元素s = i if t = -1 and Li d / 找到第找到第 1 个大于个大于 d 的元素的元素t = i ; end (i)if s != -1 and t !=-1i = s while i n then return( A 字符串中第字符串中第 i 个字符开始的子串与个字符开始的子串与 B 匹配匹配 ) end(i) renturn (找不到匹配的子串找不到匹配的子串)设设 A，B 两个线性表的元
6、素个数为两个线性表的元素个数为 m，n If (mlchild) newlchild=CopyTree(T-lchild);/ else newlchild=NULL;/ if(T-rchild) newrchild=CopyTree(T-rchild);/ else newrchild=NULL;/ newnode=GetTreeNode(T-data,newlchild,newrchild); /return newnode; /CopyTreeBiTNode *GetTreeNode(TelemType item,BiTNode *lptr,BiTNode *rptr) / T=new
7、BiTNode; T-data=item;T-lchild=lptr;T-rchild=rptr; return T; /GetTreeNode(2)在这里要对一种情况进行说明在这里要对一种情况进行说明当当 root1 的左子树与的左子树与 root2 的左子树相同，的左子树相同，root1 的右子树与的右子树与 root2 的右子树相的右子树相同时，这两颗二叉树相同。同时，这两颗二叉树相同。当当 root1 的左子树与的左子树与 root2 的右子树相同，的右子树相同，root1 的右子树与的右子树与 root2 的左子树相的左子树相同时，这两颗二叉树同样相同。同时，这两颗二叉树同样相同。以
8、下是实现代码以下是实现代码bool IsBSTEqual(BNode* root1,BNode* root2) if (root1=NULL else if (root1=NULL | root2=NULL) return false; else if (root1-data != root2-data) return false; bool is_left = IsBSTEqual(root1-left,root2-left); bool is_right = IsBSTEqual(root1-right,root2-right); if (is_left else is_right = I
9、sBSTEqual(root1-right,root2-left); is_left = IsBSTEqual(root1-left,root2-right); if (is_left else return false; 3）4） 计算叶子数和树的深度。计算叶子：递归每个节点，当没有左孩子和右孩子时即为叶子。计算叶子数和树的深度。计算叶子：递归每个节点，当没有左孩子和右孩子时即为叶子。 计算深度：对每个节点计算左右子树的深度，节点的最终深度是其子树深度的最大值加计算深度：对每个节点计算左右子树的深度，节点的最终深度是其子树深度的最大值加1，空树返回，空树返回-1. struct Tree E
10、lementType Element;Tree *left;Tree *right; ; int CountLeaf(Tree *T) static int count = 0;if (T != NULL)CountLeaf(T-left);CountLeaf(T-right);if (T-left = NULL return count; int Depth(Tree *T) int depthLeft, depthRight, depth;if (T = NULL)return -1;elsedepthLeft = Depth(T-left);depthRight = Depth(T-ri
11、ght);depth = 1 + (depthLeft depthRight ? depthLeft:depthRight);return depth; 2.32.给定一组元素给定一组元素17,28,36,54,30,27,94,15,21,83,40,画出由此生成的二叉排序树。画出由此生成的二叉排序树。 解：解：171528543694213040832.33给定一组权值给定一组权值 W=8,2,5,3,2,17,4,画出由此生成的哈夫曼树。画出由此生成的哈夫曼树。2.34.有一图如题图有一图如题图 2.4 所示：所示： （1）写出此图的邻接表与邻接矩阵；）写出此图的邻接表与邻接矩阵； （2
12、）由给点）由给点 V1 作深度优先搜索和广度优先搜索；作深度优先搜索和广度优先搜索； （3）试说明上述搜索的用途。）试说明上述搜索的用途。27175438222解：（解：（1）(0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
13、 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0
14、 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0)18121110976
15、435131415161718 1920125823421243514514665715768171811715981018102911111012191310（2） V1 作深度优先搜索作深度优先搜索: 12345678910111213141516171819 20V1 作广度优先搜索作广度优先搜索: 12583104679121114151718131916 20(3)为了避免同一顶点被多次访问。为了避免同一顶点被多次访问。2.35.有一又向图如题图有一又向图如题图 2.5 所示：所示：（1）写出每一结点的入度和出度各为多少；）写出每一结点的入度和出度各为多少；1536421231113131214201441315156141616151720177161818917191911182020131619（2）写出上图的邻接矩阵和邻接表。）写出上图的邻接矩阵和邻接表。 解：解： V1:入度入度=3 出度出度=0 V2:入度入度=2 出度出度=2 V3:入度入度=1 出度出度=2 V4:入度入度=2 出度出度=2 V5:入度入度=2 出度
