山东交通学院成人高考算法设计与分析复习题及参考答案

算法设计与分析A复习题一、单选题（每小题2分，共计20分。）1．与算法英文单词algorithm具有相同来源的单词是（D）。AlogarithmBalgirosCarithmosDalgebra2．从排序过程是否完全在内存中显示，排序问题可以分为（B）。A稳定排序与不稳定排序B内排序与外排序C直接排序与间接排序D主排序与辅助排序3．下列（D）不是衡量算法的标准。A时间效率B空间效率C问题难度D适应能力4．对于根树，出度为零的节点为（C）。A0节点B根节点C叶节点D分支节点5．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（C）。A0B2C4D6二、简答题（每空8分，共计24分。）1.1．是么是算法，算法与程序有什么区别？算法是一系列解决问题的清晰指令，也就是说，能够对一定符合规范的输入，在有限时间内获得所要求的输出。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性。2.2．贪婪技术的基本思想是什么？它有哪些应用（给出2种）？贪婪算法是在每一步中，“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择，能产生一个整个问题的最优解。比如找零问题中总是按面额从大到小的顺序找钱币；背包包问题中总是按价值/重量比从大到小的顺序装物品。三、算法设计题（每题14分，共计56分。）1.给出一个求两个数的最大公约数的算法。（1）如果n=0，返回m的值作为结果，同时过程结束；否则，转（2）（4分）（2）用n去除m,将余数赋给r。（5分）（3）将n的值赋给m，将r的值赋给n，返回（1）。（5分）说明：求最大公约数还有其他算法，可参照该方法评分。2.2．（1）用蛮力法求解下图的最短哈密顿回路。（10分）共有6条路径（2分），分别为：①a-b-d-c-a长度为：2+3+1+5=11最短哈密顿回路（2分）②a-b-c-d-a长度为：2+8+1+7=18（1分）③a-c-b-d-a长度为：5+8+3+7=23（1分）④a-c-d-b-a长度为：5+1+3+2=11最短哈密顿回路（2分）⑤a-d-b-c-a长度为：7+3+8+5=23（1分）⑥a-d-c-b-a长度为：7+1+8+2=18（1分）（2）为了减少线路条数，可对该算法作何改进？（4分）从（1）可以看到，6条线路可分成3对，每对只是方向不同。我们可以通过定义一条线路方向，使线路条数减半。3对数据表{26，99，20，45，15，29，65，35，20，72}用冒泡法进行排序，给出排序过程（写出每一趟的结果）。262045152965352072992026152945352065729920152629352045657299152026292035456572991520262029354565729915202026293545657299152020262935456572991520202629354565729915202026293545657299（1-8每步1分，第9步6分）4．对于下图，用Dijkstra算法求解以a为起点的单源最短路径。给出求解过程。①从a到b的距离最短，为3。即a-b的最短路径为a-b，长度为3。（2分）②剩下的路径中，从a到d的距离最短，为3+2=5。即a-d的最短路径为a-b-d，长度为5。（4分）③剩下的路径中，从a到c的距离最短，为3+4=7。即a-c的最短路径为a-b-c，长度为7。（4分）④剩下的路径中，从a到e的距离最短，为3+2+4=9。即a-e的最短路径为a-b-d-e，长度为9。（4分）《算法设计与分析》B复习题一、单选题（每小题2分，共计20分。）1.与算法英文单词algorithm具有相同来源的单词是（D）。A.logarithmB.algirosC.arithmosD.algebra2.根据执行算法的计算机指令体系结构，算法可以分为（B）。A.精确算法与近似算法B.串行算法语并行算法C.稳定算法与不稳定算法D.32位算法与64位算法3.具有10个节点的完全二叉树的高度是（C）。A.6B.5C.3D.24.下列函数关系随着输入量增大增加最快的是（D）。Ａ.log2nB.n2C.2nD.n!5.下列程序段的S执行的次数为(D)。fori←0ton-1do forj←0toi-1dos//某种基本操作n2B.n2/2C.n*(n+1)D.n(n+1)/2二、简答题（每空8分，共计24分。）1.1.分而治之的基本思想是什么？它有哪些应用（给出2种）？分治法的基本思想是：（1将问题的实例划分为同一个问题的几个较小的实例（2分）（2）对这些较小的实例求解（2分）（3）合并较小的问题，得到原问题的解（2分）应用：折半查找、合并排序、快速排序、大整数乘法、凸包问题等。（任给2种即可，每种1分）2.2.Prim算法和Kruskal算法的共同点和区别是什么？Prim算法和Kruskal算法都是利用贪心算法求最小生成树的算法。（4分，贪心和求最小生成树各2分）Prim算法是从还未加入的顶点中选择与生成树中的顶点构成边，并且边的权值最小的顶点。（2分）Kruskal算法是从未选择的边中选择不构成回路的边加入到生成树中。（2分）三、算法设计题（每题14分，共计56分。）1.1.给出一个求两个数的最大公约数的算法。（1）如果n=0，返回m的值作为结果，同时过程结束；否则，转（2）（4分）（2）用n去除m,将余数赋给r。（5分）（3）将n的值赋给m，将r的值赋给n，返回（1）。（5分）说明：求最大公约数还有其他算法，可参照该方法评分。2.2.用蛮力法求解下列背包问题。物品重量价值1742231234404525背包的承重量等于10子集总重量价值Φ00{1}742{2}312{3}440{4}525{1,2}1054{1,3}11不可行{1,4}12不可行{2,3}752{2,4}837{3,4}965{1,2,3}14不可行{1,2,4}15不可行{1,3,4}16不可行{2,3,4}12不可行{1,2,3,4}19不可行（每行0.5分）最优的选择是{3,4}，价值是65.（6分）33.对数据表{37，89，20，46，17，26，67，33，10，82}用插入排序进行排序，给出排序过程（写出每一趟的结果）26|9920451529653520722699|2045152965352072202699|4515296535207220264599|1529653520721520264599|2965352072152026294599|6535207215202629456599|3520721520262935456599|2072152020262935456599|7215202026293545657299|（1-9每步1分，第10步5分）4．4.对于下图，用Dijkstra算法求解以a为起点的单源最短路径。给出求解过程。