《算法设计与分析》练习题库答案

《《算法设计与分析》练习题库答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》练习题库参考答案一、概念题：请解释下列术语。1.数据元索的集合。2.队列是一个线性表，限制为只能在I古I定的一端进行插入，在I占I定的另一端进行删除。3.对于算法a,如果存在一多项式p(),使得对a的每个大小为n的输入，a的计算时间为o(p(n)),则称a具有多项式复杂度4.二叉树的层数i与该层上的结点数n的关系为：n(i)=25.如果可满足性约化为一个问题L,则称该问题为NP■难度的。6.算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。。7.多数据单指令流8.若图的任意两个节点间均存在路径可达，则称该图为连通图。9.是指一个数学模型以及定

2、义在该模型上的一组操作。1.算法的复杂度只能用指数函数对其限界。11・函数或过程宜接或间接调用它自己。12.和高度相同的满二叉树的每个对应的顶点编号相同的树13.由所有可行状态所构成的树。14.如果L时NP难度的且LWNP,则称问题L是NP•完全的。15.算法是一个步骤的序列，满足：有穷性、可行性、确定性、输入、输岀;过程不需要满足由穷性。16.有向图的每条边有起点与终点之分，且用箭头指向边的终点。无向图的边无起点和终点之分，边无箭头。17.树(tree)是一个或多个结点的有限集合，，它使得：①有一个特别指定的称作根(roof)的结点；②剩下的结点被分成个不相交的集合tl,…,

3、tm,这些集合的每一个都是一棵树，并称tl,…，tm为这根的了树(subtree)o18.P是所有可在多项式时间内用确定算法求解的判定问题的集合。19.运算结果是唯一确定的算法20.nP是所有叮在多项式时间内用不确定算法求解的判定问题的集合21・在一给定的无向图G=(V,E)中，(u,v)代表连接顶点u与顶点v的边(即)，而w(u,v)代表此边的权重，若存在T为E的子集(即)且为无循环图，使得T中所有边的权重之和w(T)最小，则此T为G的最小生成树。22.动态规划是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。23.数据结构

4、是相互之间存在一种或多种特定关系的数据元索的集合。24.排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来的操作。二、填空题1.n2.0(n)3.最优化问题4.宽度优先搜索5.结点的最大级数6.互异7.内结点和外结点&方形9.内部路径长度、外部路径长度10.一次11.归并分类算法12.贪心选择性质13.最优子结构14.二元归并15.最小成木生成树16.最优性17.最优决策18.可容许最大成本c19.最小成本20.确定性有穷性可行性0个或多个输入一个或多个输出是的21.时间复杂性空间复杂性时间复杂度高低地方9.该问题具有最优子结构性质23.｛BABCD｝或｛CA

5、BCD｝或｛CADCD｝三、程序填空题。1.callPREORDER(LCHILD(T))callPREORDER(RCHILD(T))2.callMAXMIN(i,mid,gmax,gmin)callMAXMIN(mid+l,j,hmax,hmin)3.collSUMOFSUB(S+v(K),K+l,r-W(k))callSUMOFSUB(s,k+1,r—W(k))4.X(k)+X(k)+1k〈-k+1；X(k)〈-0k《k-l5.(1)n+1(2)high-1(3)high<-mid(4)low<-mid6.(1)a(i,j)(2)a(i,k)+a(k,j)1.(1)Pa

6、rent(i)>0(2)j<--Parent(j)2.(1)2(2)j-13.仃)mergesort(low,mid)(2)mergesort(mid+1,high)(3)merge(low,mid,high)4.(1)i^O(2)j/0(3)link(k)^j;k^j;j^link(j)⑷llnk(k)Gj5.(1)i《2(2)j^jUi}6.(1)weight(lchild(t))^weight(rchild(t))(2)return(least(1))(2)mincost+cost(u,v)14.(1)cost(n)<一一015.(1)a(j)

7、w(k)⑵k-1(2)a(i)<-a(k~i+l)(2)y(k)《O17.(l)x[k]-x[k]+l;(2)k-k-118.(1)A[i]>max⑵min=A[i]19.(1)min:=n[j](2)n[i]:=n[k]!1!问答题1.答:1)・确定性算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。在算法小不允许有诸如“计算5/0”或“将6或7与x相加”之类的运算，因为前者的结果是什么不清楚，而后者对于两种可能的运算应做哪一种也不知道。2)・能