第 8 9 章：数据结构与算法.pdf

您现在的位置：希赛网 云阅读 软件设计师考试试题分类精解（第3版）例题1第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题1本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题21.2 试题精解例题1（2004年5月试题4）的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。A.树形存储结构 B.链式存储结构C.索引存储结构 D.散列存储结构试题分析很显然，这是散列存储结构。散列存储结构将节点按其关键字的散列地址存储到散列表中。常用的散列函数有除余法、基数转换法、平方取中法、折叠法、移位法和随机数法等。试题答案D版权方授权希赛网发布，侵权必究例题2（2004年5月试题5）若循环队列以数组Q0,，m-1作为其存储结构，变量rear表示循环队列中队尾元素的实际位置，其移动按rear=（rear+1）mod m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是_。A.rear-length B.（rear-length+m）mod mC.（1+rear+m-length）mod m D.m-length试题分析其实这种题目在考场上最好的解题方法是找一个实际的例子，往里面一套便知道了。下面解释一下原理。因为rear表示的是队列尾元素的实际位置（注意：不是队尾指针）。而且题中有移动按rear=（rear+1）mod m进行,这说明：队列存放元素的顺序为：Q1,Q2,，Qm-1,Q0.所以在理想情况下rear-length+1能算出队首元素的位置，即当m=8,rear=5,length=2时，rear-length+1=4,4就是正确的队首元素实际位置。但rear-length+1有一种情况无法处理，即当m=8,rear=1,length=5时，无法算出。所以我们在rear+1-length的基础上加上m再与m求模，以此方法来计算。试题答案C上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题3上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题4版权方授权希赛网发布，侵权必究例题3（2004年5月试题6）一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有_个零元素。A.e B.2e C.n2-e D.n2-2e试题分析邻接矩阵反映顶点间邻接关系，设G=（V,E）是具有n（n?1）个顶点的图，G的邻接矩阵M是一个n行n列的矩阵，并有若（i,j）或E,则Mij=1;否则，Mij=0.由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，即图中的一条边对应邻接矩阵中的两个非零元素。因此，在一个含有n个顶点和e条边的简单无向图的邻接矩阵中共有n2-2e个零元素。试题答案D版权方授权希赛网发布，侵权必究例题4（2004年5月试题7）若一棵哈夫曼树共有9个顶点，则其叶子节点的个数为_。A.4 B.5 C.6 D.7试题分析哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。具体过程如下所述。假设有n个权值，则构造出的哈夫曼树有n个叶子节点。n个权值分别设为w1,w2,，wn,则哈夫曼树的构造规则为：（1）将w1,w2,，wn看成是有n棵树的森林（每棵树仅有一个节点）。（2）在森林中选出两个根节点的权值最小的树，作为一棵新树的左、右子树，且新树的根节点权值为其左、右子树根节点权值之和。（3）从森林中删除选取的两棵树，并将新树加入森林。（4）重复第（2）步和第（3）步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。从以上构造过程可知，哈夫曼树是严格的二叉树，没有度数为1的分支节点。设二叉树的0度节点（即叶子节点）个数为n0,2度节点个数为n2,则树的总节点数n=n0+n2.又因为二叉树有性质：对上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题5上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题6任何一棵二叉树，如果其叶子节点数为n0,度为2的节点数为n2,则n0=n2+1.所以n=n2+1+n2.即9=n2+1+n2,n2=4,n0=5.试题答案B版权方授权希赛网发布，侵权必究例题5（2004年5月试题8）若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵_。A.第i行中值为1的元素个数 B.所有值为1的元素总数C.第i行及第i列中为1的元素总个数 D.第i列中值为1的元素个数试题分析由邻接矩阵的定义可知，对于无向图，其邻接矩阵第i行元素的和，即顶点i的度。对于有向图，其邻接矩阵的第i行元素之和为顶点i的出度，而邻接矩阵的第j列元素之和为顶点j的入度。试题答案D版权方授权希赛网发布，侵权必究例题6（2004年5月试题9）在一棵度为3的树中，有2个度为3的节点，有1个度为2的节点，则有_个度为0的节点。A.4 B.5 C.6 D.7试题分析对于任一棵树，它的总度数等于节点数减1.所以我们可以设此树的节点个数为n,其中度为3的节点有n3个，度为2的节点有n2个，度为1的节点有n1个，度为0的节点有n0个，并设总度数为k.此时我们可以得到两个等量关系，一个关于节点数量，另一个关于总度数：n=n0+n1+n2+n3=n=n0+n1+1+2 k=n0 x0+n1x1+n2x2+n3x3=n-1=n1x1+n2x2+n3x3=n-1=n1+2+6 把上面两式相减得：n0=6试题答案上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题7上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题8C版权方授权希赛网发布，侵权必究例题7（2004年5月试题10）设节点x和y是二叉树中任意的两个节点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是_。A.x是y的左兄弟 B.x是y的右兄弟C.x是y的祖先 D.x是y的后裔试题分析二叉树的遍历方法主要有3种。（1）前序遍历（先根遍历，先序遍历）：首先访问根节点，然后按前序遍历根节点的左子树，再按前序遍历根节点的右子树。（2）中序遍历（中根遍历）：首先按中序遍历根节点的左子树，然后访问根节点，再按中序遍历根节点的右子树。（3）后序遍历（后根遍历，后序遍历）：首先按后序遍历根节点的左子树，然后按后序遍历根节点的右子树，再访问根节点。已知在该二叉树的先根遍历序列中，x在y之前，则说明x可能是y的父节点（祖先）或是y的父节点的左子树里的某个节点。又知在其后根遍历序列中，x在y之后，则说明x可能是y的父节点或是y的父节点的右子树里的某个节点。因此，x只能是y的父节点。试题答案C版权方授权希赛网发布，侵权必究例题8（2004年5月试题11）设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找的平均查找长度为_。A.21 B.23 C.41 D.62上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题9试题分析分块查找又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。二分查找表由分块有序的线性表和索引表组成。表R1,，n均分为b块，前b1块中节点个数为sn/b,第b块的节点数允许小于等于s;每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是分块有序的。抽取各块中的最大关键字及其起始位置构成一个索引表IDl,，b,IDi（1ib）中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。分块查找的基本思想是：索引表是有序表，可采用二分查找或顺序查找，以确定待查的节点在哪一块。由于块内无序，只能用顺序查找。分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。如果以二分查找来确定块，则分块查找成功时的平均查找长度为ASL1 log2（b1）1（s1）/2log2（n/s1）s/2;如果以顺序查找确定块，分块查找成功时的平均查找长度为ASL2 （b1）/2（s1）/2 （s22sn）/（2s）。在本题中，n123,b3,s41,因此平均查找长度为（4141241123）/（241）23。试题答案B版权方授权希赛网发布，侵权必究例题9（2004年5月试题14）已知有一维数组A0,，mn-1,若要对应为m行、n列的矩阵，则下面的对应关系_可将元素Ak（0kmn）表示成矩阵的第i行、第j列的元素（0im,0jn）。A.i=k/n,j=k%m B.i=k/m,j=k%mC.i=k/n,j=k%n D.i=k/m,j=k%n试题分析本题其实就是求一个一维数组Am?n向二维数组Bmn的转化问题，最原始的方法就是把A数组的前n个元素放到B数组的第一行中，A数组的第n个元素放到B数组的第二行中，依次类推，A数组的最后n个元素放到B数组的最后一行中。要求Ak在B数组中的位置，首先确定Ak处在哪一行，根据上面的存放方法，显然，应该是k/n行。然后再确定处在k/n行的哪一列，显然是k%n（%表示模运算）。试题答案C版权方授权希赛网发布，侵权必究上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题10上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题11例题10（2004年5月试题64,65）类比二分搜索算法，设计k分搜索（k为大于2的整数）如下：首先检查n/k处（n为被搜索集合的元素个数）的元素是否等于要搜索的值，然后检查2n/k处的元素，依次类推，或者找到要搜索的元素，或者把集合缩小到原来的1/k;如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直至找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为（64）,在最好情况下搜索失败的时间复杂度为（65）。（64）A.O（logn）B.O（nlogn）C.O（logkn）D.O（nlogkn）（65）A.O（logn）B.O（nlogn）C.O（logkn）D.O（nlogkn）试题分析与二分法查找类似，k分查找法可用k叉树来描述。k分查找法在查找成功时进行比较的关键字个数最多不超过树的深度，而具有n个节点的k叉树的深度为，所以，k分查找法在查找成功时和给定值进行比较的关键字个数至多为，即时间复杂度为O（logkn）。同时，k分查找法在查找不成功时，和给定值进行比较的关键字个数也至多为，即时间复杂度为O（logkn）。试题答案（64）C（65）C版权方授权希赛网发布，侵权必究例题11（2004年11月试题33）在一棵完全二叉树中，其根的序号为1,_可判定序号为p和q的两个节点是否在同一层。A.B.C.D.试题分析完全二叉树的性质是，具有n个节点的完全二叉树的深度为.判定序号为p和q的两个接点是否在同一层，即求是否成立。所以A为所求的结果。试题答案A上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题12上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题13版权方授权希赛网发布，侵权必究例题12（2004年11月试题34）堆是一种数据结构，_是堆。A.（10,50,80,30,60,20,15,18）B.（10,18,15,20,50,80,30,60）C.（10,15,18,50,80,30,60,20）D.（10,30,60,20,15,18,50,80）试题分析堆排序定义如下：n个元素的序列k1,k2,，kn当且仅当满足以下关系时，称之为堆。在本题中，我们可以将对应的一维数组看作一棵完全二叉树，如（10,18,15,20,50,80,30,60）转换为二叉树，如图1-1所示。图1-1 序列转换后的二叉树我们发现该序列满足堆的含义，即完全二叉树中所有非终端节点的值均不大于（或者不小于）其左、右孩子节点的值。其他序列不满足此定义。试题答案B版权方授权希赛网发布，侵权必究例题13（2004年11月试题35）从二叉树的任一节点出发到根的路径上，所经过的节点序列必须按其关键字降序排列。A.二叉排序树B.大顶堆C.小顶堆D.平衡二叉树试题分析上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题14上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题15上一节本书简介下一节当为小顶堆时，任意一棵子树的根点比其左、右子节点要小，所以从任一节点出发到根的路径上，所经过的节点序列必须按其关键字降序排列。试题答案C版权方授权希赛网发布，侵权必究例题14（2004年11月试题36）若广义表L=（1,2,3），则L的长度和深度分别为_.A.1和1 B.1和2 C.1和3 D.2和2试题分析广义表记做LS=（a1,a2,，an）其中LS是广义表名，n是它的长度。在广义表中，嵌套括号的层数为其深度，所以L深度为2.试题答案B版权方授权希赛网发布，侵权必究例题15（2004年11月试题37）若对27个元素只进行三趟多路归并排序，则选取的归并路数为_。A.2 B.3 C.4 D.5试题分析归并就是将两个或两个以上的有序表组合成一个新的有序表。本题有三趟归并，每次归并x个有序表，第一趟27个元素归并后，剩余27/x个表，归并2次后剩余27/（x2）个表，归并3次后剩余27/（x3）个表。这时候27/（x3）=1,求得x=3。试题答案B版权方授权希赛网发布，侵权必究第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题16上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题16（2004年11月试题52）采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是_。A.当前所出的决策不会影响后面的决策B.原问题的最优解包含其子问题的最优解C.问题可以找到最优解，但利用贪心法不能找到最优解D.每次决策必须是当前看来的最优决策才可以找到最优解试题分析动态规划（Dynamic Programming）：运筹学的一个分支，是求解决策过程（DecisionProcess）最优化的数学方法。美国数学家R.E.Bellman等人在研究多阶段决策过程（MultistepDecision Process）的优化问题时，提出了著名的最优化原理（Principle of Optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法-动态规划。最优性原理：动态规划的理论基础是最优性原理，它认为整个过程的最优策略有这样的特点，即无论过去的状态和决策如何。对于前面的决策所形成的状态而言，余下的诸决策必定构成最优策略。这就是说，任何一个完整的最优策略的子策略总是最优的。设计动态规划法的步骤：（1）找出最优解的性质，并刻画其结构特征。（2）递归地定义最优值（写出动态规划方程）。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造一个最优解。步骤（1）（3）是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省略，步骤（3）中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤（4），步骤（3）中记录的信息必须足够多，以便构造最优解。动态规划算法的有效性依赖于问题本身所具有的两个重要性质。最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，以后尽可能多地利用这些子问题的解。试题答案B版权方授权希赛网发布，侵权必究例题17上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题18例题17（2004年11月试题54）下面的程序段违反了算法的_原则。void sam（）int n=2while（！odd（n）n+=2;printf（n）；A.有穷性 B.确定性C.可行性D.健壮性试题分析由于n的初始值为2,语句while（！odd（n）n+=2;无论循环多少步，n都不能为奇数，所以循环无法终止，违背了算法的有穷性。试题答案A版权方授权希赛网发布，侵权必究例题18（2004年11月试题55）拉斯维加斯（Las Vegas）算法是一种常用的_算法。A.确定性 B.近似 C.概率 D.加密试题分析此题主要考查基本概率算法，我们来了解一下到底什么样的算法是概率算法。概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。（因此特征，我们就可以排除哈夫曼编码算法，因为哈夫曼编码是一种确定的方法。）一般情况下，可将概率算法大致分为4类：数值概率算法、蒙特卡罗（Monte Carlo）算法、拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解，而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到相当满意的解。蒙特卡罗算法用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为是或否,二者必居其一，不存在任何近似解答。又如，我们要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因子没有任何意义。用蒙特卡罗算法能求得问题的一个上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题19上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题20解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点就在于此。一般情况下，无法有效判断得到的解是否肯定正确。拉斯维加斯算法不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。试题答案C版权方授权希赛网发布，侵权必究例题19（2004年11月试题56）在分支-界限算法设计策略中，通常采用_搜索问题的解空间。A.深度优先B.广度优先C.自底向上D.拓扑排序试题分析在分支-界限算法设计策略中，通常采用广度优先搜索问题的解空间。试题答案B版权方授权希赛网发布，侵权必究例题20（2004年11月试题57,58）在下列算法设计方法中，（57）在求解问题的过程中并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。利用该设计方法可以解决（58）问题。（57）A.分治法 B.贪心法 C.动态规划法 D.回溯法上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题21上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日（58）A.排序 B.检索 C.背包_D.0/1背包试题分析贪心法是这样的一种解题方法：逐步给出解的各部分，在每一步贪婪地选择最好的部分解，但不顾及这样选择对整体的影响，因此一般地得到的不是最好的解。解决背包问题：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。较高效率地解决背包问题一般用递归和贪心算法，而背包问题规模不是很大时，也可采用穷举法。试题答案（57）B（58）C版权方授权希赛网发布，侵权必究例题21（2004年11月试题59,60）以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O（nlog2n）。在下面的排序算法中，最坏情况下计算时间可以达到O（nlog2n）的是（59）,该算法采用的设计方法是（60）。（59）A.归并算法 B.插入算法 C.选择算法 D.冒泡算法（60）A.分治法 B.贪心法 C.动态规划法 D.回溯法试题分析对照表1-3,我们可知归并算法在最坏情况下的计算时间可达到O（nlog2n）。设归并排序的当前区间是Rlow,，high,分治法的三个步骤是：（1）分解。将当前区间一分为二，即求分裂点。（2）求解。递归地对两个子区间Rlow,，mid和Rmid+1,，high进行归并排序。（3）组合。将已排序的两个子区间Rlow,，mid和Rmid+1,，high归并为一个有序的区间Rlow,，high。递归的终结条件：子区间长度为1（一个记录自然有序）。试题答案（59）A（60）A版权方授权希赛网发布，侵权必究例题22上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题23例题22（2005年5月试题38）循环链表的主要优点是_。A.不再需要头指针了B.已知某个节点的位置后，能很容易找到它的直接前驱节点C.在进行删除操作后，能保证链表不断开D.从表中任一节点出发都能遍历整个链表试题分析此题考查循环链表的基础知识，所以我们来了解一下什么是循环链表，一个带头节点的线性链表如图1-2所示。图1-2 带头节点的线性链表若将此链表的最后一个节点d的next域指向头，则产生了循环链表，如图1-3所示。图1-3 循环链表实现循环链表的类型定义与线性链表完全相同，它的所有操作也都与线性链表类似。只是判断链表结束的条件有所不同。对照图1-6,我们现在来分析题目的备选答案。选项A不再需要头指针了,言下之意就是线性链表一定需要头指针，但实际上不管是线性链表还是循环链表，头指针都是可要可不要的，所以选项A错误。再来看B选项，已知某个节点的位置后，能很容易找到它的直接前驱节点,题目中只说是循环链表，没有说是双向的循环链表。在单向循环链表中，已知某个节点的位置很难得到它的直接前驱节点，所以不对。接着看C选项，在进行删除操作后，能保证链表不断开,在线性链表中也能满足这个要求，所以不能算作循环链表的主要优点，也不正确。其实到这里我们已经可以知道答案为D了，但我们还是看看D到底对不对。D选项是这样的：从表中任一节点出发都能遍历整个链表.我们首先看看在线性链表中，是否能满足这个要求。以线性链表中c为例，c只能往向走到d,然后d的next域为空，无路可走，所以线性链表无法满足这个要求。再看循环链表，无论从哪一点出发，都可以到达任一节点，因为所有的节点围成了一个圈。所以此题的正确答案为D.试题答案D版权方授权希赛网发布，侵权必究例题23（2005年5月试题39）表达式a*（b+c）-d的后缀表达式为_.A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题24试题分析题目要求根据已知的表达式写对应的后缀表达式。解这种题，如果你知道前缀、中缀、后缀表达式有何关联，有什么特点，解题就非常轻松。其实前缀、中缀、后缀的得名是从二叉树来的，也就是把一个表达式转化为一棵二叉树后，对二叉树进行前序遍历得到前缀表达式，对二叉树进行中序遍历得到中序表达式（也就是一般形式的表达式），对二叉树进行后序遍历得到后缀表达式。所以这里我们只要把表达式转成树的形式，再对二叉树进行后序遍历，即可得到正确答案。但现在最主要的问题是如何构造这棵树。构造的规则是这样的：所有的操作数只能在叶子节点上，操作符是它们的根节点，括号不构造到二叉树当中去，构造树的顺序要遵循运算的顺序。在表达式a*（b+c）-d中最先计算b+c,所以先构造图1-4的部分。然后把b+c的结果与a进行运算，有如图1-5所示的结果。图1-4 第一步 图1-5 第二步接着把运算结果和d相减，最终得到的二叉树如图1-6所示。图1-6 最终得到的二叉树对此树进行后序遍历得到序列：abc+*d-,所以正确答案是B.试题答案B版权方授权希赛网发布，侵权必究例题24（2005年5月试题40）若二叉树的先序遍历序列为ABDECF,中序遍历序列为DBEAFC,则其后序遍历序列为_.A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA试题分析此题要求根据二叉树的先序遍历和中序遍历求后序遍历。我们可以根据这棵二叉树的先序和中序遍历画出这棵二叉树。根据先序和中序来构造二叉树的规则是这样的：首先看先序，先序遍历中第一个访问的节点是A,这说明A是二叉树的根节点（因为先序遍历顺序是：根、左、右）。然后看中序，中序中A前面有节点D,B,E,后面有节点F,C.这说明D,B,E是A的左子树，F,C是A的右子树。我们再回到先序遍历中看上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题25D,B,E的排列顺序（此时可以不看其他节点），我们发现在先序中B排在最前，所以B是A左子树的根节点。接下来又回到了中序，中序中D在B前面，E在B后面，所以D是B的左子树，E是B的右子树。依此规则可构造二叉树，如图1-7所示。然后对这棵二叉树进行后序遍历得到DEBFCA。图1-7试题答案D版权方授权希赛网发布，侵权必究例题25（2005年5月试题41）无向图中一个顶点的度是指图中_。A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻的顶点数 D.与该顶点连通的顶点数试题分析此题是纯概念题。（1）无向图中顶点V的度（Degree）。无向图中顶点V的度是关联于该顶点的边的数目，也可以说是直接与该顶点相邻的顶点个数，记为D（V）。例如，在图1-8中，V1的度为1,V2的度为2,V3的度为3,V4的度为2.（2）有向图顶点V的入度（InDegree）。有向图中，以顶点V为终点的边的数目称为V的入度，记为ID（V）。图1-8 无向图示例 图1-9 有向图示例1例如，在图1-9中，V1的入度为1,V2的入度为2,V3的入度为1,V4的入度为0.（3）有向图顶点V的出度（OutDegree）有向图中，以顶点V为始点的边的数目，称为V的出度，记为OD（V）。上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题26上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题27图1-10 有向图示例2例如，在图1-10中，V1的出度为0,V2的出度为0,V3的出度为2,V4的出度也_为2.试题答案C版权方授权希赛网发布，侵权必究例题26（2005年5月试题42）利用逐点插入法建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树以后，查找元素30要进行 次元素间的比较。A.4 B.5 C.6 D.7试题分析首先，我们对给出的节点建立排序二叉树，如图1-11所示。图1-11 排序二叉树图1-11中我们可以看出，30首先要与50比较，3050,所以进入节点50的左子树；接着与43比较，结果3020,所以进入节点20的右子树；再和35比较，300）个顶点的连通无向图至少有_条边。A.n+1 B.n C.D.n-1试题分析在无向图中如果任意两点是可达的，则我们称其为连通无向图。要把这n个顶点连通，我们可以让一个顶点向其他所有顶点连一条边，这样需要n-1条边，如图1-14所示。图1-14 一个顶点向其他所有顶点连一条边此外，我们还可以让这n个顶点首尾相接，这样也需要n-1条边，如图1-15所示。图1-15 n个顶点首尾相接所以至少需要n-1条边。试题答案D上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题29上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题30版权方授权希赛网发布，侵权必究例题29（2005年5月试题50）由权值为9,2,5,7的4个叶子节点构造一棵哈夫曼树，该树的带权路径长度为_.A.23 B.37 C.44 D.46试题分析首先构造这棵哈夫曼树，如图1-16所示。图1-16 哈夫曼树带权路径长度为：9+7x2+（2+5）x3=44.试题答案C版权方授权希赛网发布，侵权必究例题30（2005年5月试题51）在最好和最坏情况下的时间复杂度均为O（nlog2n）且稳定的排序方法是_。A.基数排序 B.快速排序 C.堆排序 D.归并排序试题分析此题考查对排序算法时间复杂度的掌握程度，以及对稳定排序概念的理解。排序算法的时间复杂度要靠理解和记忆，稳定排序算法是指在排序过程中两个排序关键字相同的元素，在排序的过程中位置不发生变化，即对数列62,42,12,36,4,12,67进行排序时，第一个12在排序完毕以后要排在第二个12的前面，这就是稳定的排序。有些人可能会发出疑问：既然都是12,为什么一定要保证它的顺序呢？举一个简单的例子：如果组织一次有奖答题活动，选手在电脑上答完题后直接提交数据，最后按答题得分奖励前100名参赛选手。这样会出现一个问题，即如果同时有10个人并列第100名，而我们只能给一个人发奖，到底给谁发呢？最合理的判断标准是给先提交答案的人发奖，这样稳定排上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题31序就可以用上了。下面用排除法来解答此题。题目给出的4个选项中快速排序和堆排序都是不稳定的排序算法，所以排除。再看基数排序，我们知道基数排序的最坏时间复杂度为O（d（n+rd）所以正确答案应是答案D,归并排序。试题答案D版权方授权希赛网发布，侵权必究例题31（2005年5月试题50）已知一个线性表（38,25,74,63,52,48），假定采用散列函数h（key）=key%7计算散列地址，并散列存储在散列表A0,，6中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为_.A.1.5 B.1.7 C.2.0 D.2.3试题分析要计算散列表上的平均查找长度，我们首先必须知道在建立这个散列表时，每个数据存储时进行了几次散列。这样就知道哪一个元素的查找长度是多少。散列表的填表过程如下：首先存入第1个元素38,由于h（38）=38%7=3,又因为3号单元现在没有数据，所以把38存入3号单元，如图1-17所示。图1-17 第1步接着存入第2个元素25,由于h（25）=25%7=4,又因为4号单元现在没有数据，所以把25存入4号单元，如图1-18所示。图1-18 第2步接着存入第3个元素74,由于h（74）=74%7=4,此时的4号单元已经被25占据，所以进行线性再散列，线性再散列的公式为：Hi=（H（key）+di）%m,其中的di=1,2,3,4,所以H1=（4+1）%7=5,此时的单元5没有存数据，所以把74存入到5号单元。如图1-19所示。图1-19 第3步接着存入第4个元素63,由于h（63）=63%7=0,此时的0号单元没有数据，所以把63存入0号单元，如图1-20所示。图1-20 第4步上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题32接着存入第5个元素52,由于h（52）=52%7=3,此时的3号单元已被38占据，所以进行线性再散列：H1=（3+1）%7=4,但4号单元也被占据了，所以再次散列：H2=（3+2）%7=5,但5号单元也被占据了，所以再次散列：H3=（3+3）%7=6,6号单元为空，所以把52存入6号单元，如图1-21所示。图1-21 第5步最后存入第6个元素48,由于h（48）=48%7=6,此时的6号单元已被占据，所以进行线性再散列：H1=（6+1）%7=0,但0号单元也被占据了，所以再次散列：H2=（6+2）%7=1,1号单元为空，所以把48存入1号单元，如图1-22所示。图1-22 第6步如果一个元素存入时，进行了N次散列，相应的查找次数也是N,所以38,25,63这三个元素的查找长度为1,74的查找长度为2,48的查找长度为3,52的查找长度为4.平均查找长度为：（1+1+1+2+3+4）/6=2。试题答案C版权方授权希赛网发布，侵权必究例题32（2005年5月试题53,54）为在状态空间树中（53）,可以利用LC-检索（Least Cost Search）快速找到一个答案节点。在进行LC-检索时，为避免算法过分偏向于纵深检查，应该（54）.（53）A.找出任一个答案节点B.找出所有的答案节点C.找出最优的答案节点D.进行遍历（54）A.使用精确的成本函数c（）来做LC-检索B.使用广度优先检索C.使用深度优先检索D.在成本估计函数（）中考虑根节点到当前节点的成本（距离）试题分析LC-检索是分支限界法中的一种检索方法。分支限界法类似于回溯法，是在问题的解空间树上搜索问题解的算法。一般情况下分支限界法和回溯法的求解目标不同。回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。所以（53）应是C找出最优的答案节点。上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题33上一节本书简介下一节第 1 章：数据结构与算法作者：希赛教育软考学院 来源：希赛网 2014年02月07日例题34分支限界法中，对问题空间树检索的方法有两种：广度优先和最小耗费优先。在LC-检索中为了避免算法过分偏向于纵深检查，提出了改进成本估计函数c（），使其不只是考虑节点X到一个答案节点的估计成本，还应考虑由根节点到节点X的成本h（X）。试题答案（53）C（54）D版权方授权希赛网发布，侵权必究例题33（2005年5月试题55）以比较为基础的排序算法在最坏情况下的计算时间下界为_.A.O（n）B.O（n2）C.O（log2n）D.O（nlog2n）试题分析此题求基础的排序算法在最坏情况下的计算时间下界。由于下界的含义是最小值，而时间复杂度的值最小，表1-3是常用排序算法的时间复杂度比较表，从表中可以看出，最坏情况下的最好时间复杂度为：O（nlog2n）。试题答案D版权方授权希赛网发布，侵权必究例题34（2005年5月试题56）利用动态规划方法求解每对节点之间的最短路径问题（all pairs s