网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311.
专业： 班级： 学号： 姓名： 日期： 2014年 11月 10日
48476Λn n 111+++=。 2、q(n ，m)=q(n ，n)，m>=n 。 最大加数n1实际上不能大于n ，因此，q(1，m)=1。 3、q(n ，n)=1+q(n ，n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ，m)= q(n ，m-1)+q(n-m ，m)，n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 （2）、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n 数据挖掘分类算法比较 分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。通过对当前数据挖掘中具有代表性的优秀分类算法进行分析和比较，总结出了各种算法的特性，为使用者选择算法或研究者改进算法提供了依据。 一、决策树（Decision Trees） 决策树的优点： 1、决策树易于理解和解释.人们在通过解释后都有能力去理解决策树所表达的意义。 2、对于决策树，数据的准备往往是简单或者是不必要的.其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。 3、能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。 4、决策树是一个白盒模型。如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。 5、易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。 6、在相对短的时间内能够对大型数据源做出可行且效果良好的结果。 7、可以对有许多属性的数据集构造决策树。 8、决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小。 决策树的缺点： 1、对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。 2、决策树处理缺失数据时的困难。 3、过度拟合问题的出现。 4、忽略数据集中属性之间的相关性。 二、人工神经网络 人工神经网络的优点：分类的准确度高,并行分布处理能力强,分布存储及学习能力强，对噪声神经有较强的鲁棒性和容错能力，能充分逼近复杂的非线性关系，具备联想记忆的功能等。 人工神经网络的缺点：神经网络需要大量的参数，如网络拓扑结构、权值和阈值的初始值；不能观察之间的学习过程，输出结果难以解释，会影响到结果的可信度和可接受程度；学习时间过长,甚至可能达不到学习的目的。 仿真一：在100*100的区域内随机生成100个节点 （matlab仿真代码： clear; xm=100;%x轴范围 ym=100;%y轴范围 sink.x=0.5*xm;%基站x轴 50 sink.y=0.5*ym;%基站y轴 50 n=100; E0=0.02; for i=1:1:n S(i).xd=rand(1,1)*xm; S(i).yd=rand(1,1)*ym; S(i).G=0;%每一周期结束此变量为0 S(i).E=E0;%设置初始能量为E0 S(i).type='N';%节点类型为普通 plot(S(i).xd,S(i).yd,'o'); hold on; end %设置SINK节点的坐标 S(n+1).xd=sink.x; S(n+1).yd=sink.y; plot(S(n+1).xd,S(n+1).yd,'*');%绘制基站节点仿真结果图片：（‘O’代表随机散布的节点，‘*’代表SINK节点） 仿真二：LEACH 分簇效果图（matlab 代码见附件） 仿真结果：(p=0.1) 1、簇头个数14. 0102030405060708090100 2、簇头个数：11 3、簇头个数：12 0102030405060708090100 4、簇头个数：10 10 20 30 40 50 60 70 80 90 100 (p=0.05) 1、簇头=6 10 20 30 40 50 60 70 80 90 100 2、簇头=7 3、簇头=12 4、簇头=8 10 20 30 40 50 60 70 80 90 100 5 、 010203040 5060708090 100 102030405060708090100x y LEACH 分簇算法成簇效果图 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） 算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i 《算法分析与设计》实验指导. 实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3） 图1 2个、4个和8个选手的比赛日程表 图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这 样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。 LEACH算法的学习摘要 一、LEACH的定义 LEACH:低功耗自适应路由算法 二、LEACH算法的工作流程 1.总述 LEACH路由协议主要分为两个阶段：即簇建立阶段(setup phase)和稳定运行阶段(ready phase)。簇建立阶段和稳定运行阶段所持续的时间总和为一轮(round)。为减少协议开销，稳定运行阶段的持续时间要长于簇建立阶段。 2.簇建立阶段 在簇建立阶段，传感器节点随机生成一个0，1之间的随机数，并且与阈值T(n)做比较，如果小于该阈值，则该节点就会当选为簇头。T(n)按照下列公式计算： 式中：P为节点成为簇头节点的百分数，r为当前轮数，G为在最近的1/p 轮中未当选簇头的节点集合。簇头节点选定后，广播自己成为簇头的消息，节点根据接收到的消息的强度决定加入哪个簇，并告知相应的簇头，完成簇的建立过程。然后，簇头节点采用TDMA的方式，为簇内成员分配传送数据的时隙。 3.稳定阶段 在稳定阶段，传感器节点将采集的数据传送到簇头节点。簇头节点对采集的数据进行数据融合后再将信息传送给汇聚节点，汇聚节点将数据传送给监控中心来进行数据的处理。稳定阶段持续一段时间后，网络重新进入簇的建立阶段，进行下一轮的簇重建，不断循环。 三、LEACH算法的优点 1.LEACH算法属于分层路由协议，节点之间反应速度快，簇头进行轮转性选举，能够保证无线传感器网络中各个节点能量均衡的消耗，从而有效地延长无线传感网络的生命周期，低功耗的目的。 2.各个节点之间不再是无序的建立通信路由，数据信息的传递具有一定的规则，普通节点只能向上一级簇头传送数据信息，一级粗托只能向二级簇头传送数据信息。很大程度上节省了能量，减少了能量的浪费。 3.相近的节点之间接收到的数据信息有可能相同或相近，这就需要簇头进行必要的数据融合。更好的提升了能量的利用率。 4.每个簇头都要进行数据融合，因为每个簇头接收到的都是局部数据信息，所以数据信息都是比较相关，给数据的融合带来了较快的速度。 5.LEACH路由算法采用TDMA和CDMA的MAC层机制进行各个节点间的数据信息的传递，保证了簇内各个节点有序的跟簇头节点的传递数据，也保证了簇头Sink节点进行有序的信息传递，从而避免了簇内和簇间的相互通信冲突。 6.LEACH路由协议感应外界的环境信息，是周期性的进行检测，各个周期之间不间断地进行。LEACH协议非常适合长期、连续性的进行环境的检测。为野外长时间、不间断地检测提供了保证。 7.有些检测不需要随时获取检测的数据信息，只是当环境中有意外、异常情况发生时，才进行必要的检测盒数据信息的传递。这种不需要周期性的信息传递，减少了无线传感器网络的能量消耗，提高了网络的生命周期。 8.每进行完一轮数据信息的传送，网络进行重新的簇头选举，保证了各个节点之间能量的均衡消耗，提高了能量的利用率。 四、LEACH算法的缺点 1.LEACH路由协议算法中没有说明簇头节点如何进行选举分配，才能保证网络数 聚类分析算法解析 一、不相似矩阵计算 1.加载数据 data(iris) str(iris) 分类分析是无指导的分类，所以删除数据中的原分类变量。 iris$Species<-NULL 2. 不相似矩阵计算 不相似矩阵计算，也就是距离矩阵计算，在R中采用dist()函数，或者cluster包中的daisy()函数。dist()函数的基本形式是 dist(x, method = "euclidean", diag = FALSE, upper = FALSE, p = 2) 其中x是数据框（数据集），而方法可以指定为欧式距离"euclidean", 最大距离"maximum", 绝对值距离"manhattan", "canberra", 二进制距离非对称"binary" 和明氏距离"minkowski"。默认是计算欧式距离，所有的属性必须是相同的类型。比如都是连续类型，或者都是二值类型。 dd<-dist(iris) str(dd) 距离矩阵可以使用as.matrix()函数转化了矩阵的形式，方便显示。Iris数据共150例样本间距离矩阵为150行列的方阵。下面显示了1~5号样本间的欧式距离。 dd<-as.matrix(dd) 二、用hclust()进行谱系聚类法（层次聚类） 1.聚类函数 R中自带的聚类函数是hclust()，为谱系聚类法。基本的函数指令是 结果对象<- hclust（距离对象, method=方法） hclust()可以使用的类间距离计算方法包含离差法"ward"，最短距离法"single"，最大距离法"complete"，平均距离法"average"，"mcquitty"，中位数法"median" 和重心法"centroid"。下面采用平均距离法聚类。 hc <- hclust(dist(iris), method="ave") 2.聚类函数的结果 聚类结果对象包含很多聚类分析的结果，可以使用数据分量的方法列出相应的计算结果。 str(hc) 下面列出了聚类结果对象hc包含的merge和height结果值的前6个。其行编号表示聚类过程的步骤，X1，X2表示在该步合并的两类，该编号为负代表原始的样本序号，编号为正代表新合成的类；变量height表示合并时两类类间距离。比如第1步，合并的是样本102和143，其样本间距离是0.0，合并后的类则使用该步的步数编号代表，即样本-102和-143合并为1类。再如第6行表示样本11和49合并，该两个样本的类间距离是0.1，合并后的类称为6类。 head (hc$merge,hc$height) 第一部分数据结构概论及算法分析 一、选择题 1．数据结构是一门研究计算机中__ __对象及其关系的学科。 （1）数值运算（2）非数值运算（3）集合（4）非集合 2．数据结构的定义为(K，R)，其中K是__ __的集合。 （1）算法（2）数据元素（3）数据操作（4）逻辑结构 3．算法分析的目的是____。 （1）找出数据结构的合理性（2）研究算法中输入和输出的关系 （3）分析算法的效率以求改进（4）分析算法的易懂性和文档性 4. 数据的不可分割的基本单位是_ ___。 A.元素 B.结点 C.数据类型 D.数据项 5．下列算法suanfa2的时间复杂度为____。 int suanfa2(int n) { int t=1； while(t<=n) t=t*2； return t； } A.O(log2n) B.O(2n) C.O(n2) D.O(n) 6.（）是具有相同特性数据元素的集合，是数据的子集。 A 数据符号 B 数据对象 C 数据 D 数据结构 7．与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )。 A. 存储结构 B. 逻辑结构 C. 算法 D. 操作 8．数据结构是研究数据的（）及它们之间的相互联系。 A、理想结构，物理结构b、理想结构，逻辑结构 C、物理结构，逻辑结构d、抽象结构，逻辑结构 9．组成数据的基本单位是（）。 a、数据项 b、数据类型 c、数据元素 d、数据变量 10．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构11．算法指的是（） A．计算机程序B．解决问题的计算方法 C．排序算法D．解决问题的有限运算序列 12．下列算法suanfa1中语句"x=x*2；"的执行次数是（）。 void suanfa1(int n) { int i,j,x=1； for(i=1；i<=n；i++) for(j=i；j<=n；j++) x=x*2； printf("%d",x)； } A.n(n-1)/2 B.n(n+1)/2 C.n2 D.?nlog2n? 13. 由____组成的集合是一个数据对象。 A.不同类型的数据项 B.不同类型的数据元素 C.相同类型的数据项 D.相同类型的数据元素 14．在下列选项中，哪个不是一个算法一般应该具有的基本特征_____。 A. 确定性 B. 可行性 C. 无穷性 D. 拥有足够的情报15．在计算机中，算法是指______。 A. 查询方法 B. 加工方法 C. 解题方案准确而完整的描述 D. 排序方法16．算法的时间复杂度是指________。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数17．算法的空间复杂度是指________。 A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间18．下面叙述正确的是_______。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（或语句）的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对 19．数据的存储结构是指______。 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; ---------------------------------------------------------------最新资料推荐------------------------------------------------------ 1算法分析的目的是( 1. 算法分析的目的是( ) A. 找出数据结构的合理性 B. 找出算法中输入和输出之间的关系 C. 分析算法的易懂性和 可靠性 D. 分析算法的效率以求改进【参考答案】 D 2. 在 单链表中，增加头结点的目的是( ) A. 方便运算的 B. 使单链表至少有一个结点 C. 标识表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现【参考答案】 A 3. 软件 开发离不开系统环境资源的支持，其中必要的测试数据属于( ) A. 硬件资源 B. 通信资源 C. 支持软件 D. 辅助资源【参考 答案】 D 4. 分布式数据库系统不具有的特点是( ) A. 数 据分布性和逻辑整体性 B. 位置透明性和复制透明性 C. 分布性 D. 数据冗余【参考答案】 D 5. 下列数据模型中，具有坚实 理论基础的是( ) A. 层次模型 B. 网状模型 C. 关系模 型 D. 以上 3 个都是【参考答案】 C 6. 栈底到栈顶依次 存放元素 A、 B、 C、 D，在第五个元素 E 入栈前，栈中元素可 以出栈，则出栈序列可能是( ) A. ABCED B. DCBEA C. DBCEA D. CDABE 【参考答案】 B 7. 在结构化程序设计思想提 出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的( ) A. 安全性 B. 一致性 C. 可 理解性 D. 合理性【参考答案】 C 8. 软件开发的结构化生命 周期方法将软件生命周期划分成( ) A. 定义、开发、运行 1 / 14 算法是，对特定问题求解方法和步骤的一种描述，它是有限指令的有限序列，其中每个指令表示一个或多个操作。 算法与程序的比较 ?算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。 ?程序是用某种程序设计语言对算法的具体实现。 ?程序 = 数据结构 + 算法 算法的特性 一个算法必须具备以下五个重要特性： ?有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ?确定性算法中每一条指令必须有确切的含义，没有二义性，在任何条件下只有唯一的一条执行路径，即对相同的输入只能得到相同的输出。 ?可行性算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 ?输入一个算法有零个或多个输入 ?输出一个算法有一个或对个输出 算法设计有正确性（Correctness）、可读性（Readability）、健壮性（Robustness）、高效性（Efficiency）的基本要求。 一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。 算法效率分析 算法效率主要从一下两个方面来考虑： 1.时间效率：指的是算法所耗费的时间； 2.空间效率：指的是算法执行过程中所耗费的存储空间。 时间效率和空间效率有时候是矛盾的。 时间效率分析 一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作（如赋值、比较、移动等）所需的时间与算法中进行简单操作次数的乘积。 算法运行时间 = 一个简单操作所需的时间 x 简单操作次数， 也就是算法中每条语句的执行时间之和 每条语句执行一次所需的时间，一般是随机器而异的，取决于机器的指令性能、速度以及编译的代码质量，是由机器本身软硬件环境决定的，它与算法无关。所以，可以假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可以转化为讨论改算法中所有语句的执行次数了。 例如：两个n x n矩阵相乘的算法课描述为： for(i=1;i<=n;i++) //n+1次 for(j=1;j<=n;j++) //n(n+1)次 { c[i][j]=0; //n*n次 for(k=0;k 《算法分析与设计》课程教学大纲 【课程编号】：14314025 【英文译名】：Analysis and Design of Computer Algorithms 【适用专业】：软件工程、计算机科学与技术、信息安全 【学分数】：3 【总学时】：48学时 【实践学时】：0 一、本课程教学目的和课程性质 本课程是软件工程、计算机科学与技术、信息安全等专业的选修课程，也可作为其它计算机相关专业的选修课程。课程属于专业教育课。 课程主要介绍计算机算法分析、算法设计及复杂性理论的基本概念、基本的算法分析方法和常用的算法设计方法。通过本课程的教学，强化学生算法分析与设计的基础理论知识，使学生掌握计算机算法分析的基本方法及常见的算法设计方法（如：分治法、回溯法、贪心法、动态规划法、分枝限界法等）。通过学习，学生能够用利用常见的算法设计方法来解决软件开发中的实际问题。培养扎实的专业知识和基本技能和从事应用软件开发和测试的能力。 二、本课程的基本要求 本课程的基本要求是让学生理解计算机算法效率分析与设计所涉及的基本概念和基础知识，掌握基本的算法分析方法和常见的算法设计方法，能熟练应用课程介绍的算法设计方法来解决软件开发中的实际问题。通过对算法实例的分析，进一步加深学生对算法设计方法的认识和理解。 1、理解算法的基本概念和算法的效率分析方法。 2、理解分治策略的原理、效率分析，掌握分支策略在常见问题（如：二分检索、归并分类、快速排序、选择问题等）问题中的应用。了解分治策略的变形（减治策略、变治策略）的思想和简单应用。 3、理解动态规划的原理、适用条件，了解算法的效率，掌握该算法在常见问题（如：多段图、最优二分检索树、0/1背包问题、货郎担问题、可靠性设计等）问题中的应用。 4、理解贪心方法的原理、效率分析方法，掌握在常见问题（如：背包问题、带有期限的作业排序、最小生成树、单源点最短路径等）问题中的应用。 5、理解回溯法的原理，掌握在常见问题（如：8-皇后、子集和数、图的着色、哈密顿环等）问题中的简单应用。 6、了解分支-限界方法的基本思想和简单应用。 7、了解基本的检索和周游方法的基本思想。 8、了解NP-难度和NP-完全问题基本思想和简单应用。 9、了解概率算法的基本思想及简单应用。 三、本课程与其他课程的关系 Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) 第一章 什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的 输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。 算法的三个要素 1）.数据：运算序列中作为运算对象和结果的数据?2）.运算：运算序列中的各种运算：赋值,算术和逻辑运算 3）.控制和转移：运算序列中的控制和转移. 算法分类 从解法上：数值型算法：算法中的基本运算为算术运算；非数值型算法：算法中的基本运算为逻辑运算. 从处理方式上：串行算法：串行计算机上执行的算法；并行算法：并行计算机上执行的算法 算法的五个重要的特性 （1）有穷性: 在有穷步之后结束。 （2）确定性: 无二义性。 （3）可行性: 可通过基本运算有限次执行来实现。 （4）有输入 f表示存在数据处理 （5） 伪代码 有输出A 程序设计语言（PDL），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言 （例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。 特点：1）使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2）以自然语言的自由语法描述了处理过程；3）数据声明应该既包括简单的也包括复杂的数据 结构；4）使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n阶方阵的相加C=A+B的算法如下，分析其时间复杂度。 #define MAX 20 //定义最大的方阶 void matrixadd (int n,int A[MAX][MAX], int B[MAX][MAX],i nt C[MAX][MAX]) { int i,j; for (i=0;i －、选择题 1.算法分析的目的是( ) A.找出数据结构的合理性 B.找出算法中输入和输出之间的关系 C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改进 【参考答案】D 2.在单链表中，增加头结点的目的是( ) A.方便运算的 B.使单链表至少有一个结点 C.标识表结点中首结点的位置 D.说明单链表是线性表的链式存储实现 【参考答案】A 3.软件开发离不开系统环境资源的支持，其中必要的测试数据属于( ) A.硬件资源 B.通信资源 C.支持软件 D.辅助资源 【参考答案】D 4.分布式数据库系统不具有的特点是( ) A.数据分布性和逻辑整体性 B.位置透明性和复制透明性 C.分布性 D.数据冗余 【参考答案】D 5.下列数据模型中，具有坚实理论基础的是( ) A.层次模型 B.网状模型 C.关系模型 D.以上3个都是 【参考答案】C 6.栈底到栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是( ) A.ABCED B.DCBEA C.DBCEA D.CDABE 【参考答案】B 7.在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的( ) A.安全性 B.一致性 C.可理解性 D.合理性 【参考答案】C 8.软件开发的结构化生命周期方法将软件生命周期划分成( ) A.定义、开发、运行维护 B.设计阶段、编程阶段、测试阶段 C.总体设计、详细设计、编程调试 D.需求分析、功能定义、系统设计 【参考答案】A 9.在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有( ) A.特定的数据模型 B.数据无冗余 C.数据可共享 D.专门的数据管理软件 【参考答案】A 10.实体是信息世界中广泛使用的一个术语，它用于表示( ) A.有生命的事物 B.无生命的事物 C.实际存在的事物 D.一切事物 【参考答案】C 11.下面叙述中正确的是（） A.C语言编译时不检查语法 算法分析与设计 学习总结 题目:算法分析与设计学习总结 学院信息科学与工程学院专业2013级计算机应用技术 届次 学生姓名 学号2０１31１0６57 二○一三年一月十五日 算法分析与设计学习总结 本学期通过学习算法分析与设计课程，了解到:算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。 设计的算法要具有以下的特征才能有效的完成设计要求，算法的特征有：（1）有穷性。算法在执行有限步后必须终止。(2)确定性。算法的每一个步骤必须有确切的定义。(3)输入。一个算法有0个或多个输入,作为算法开始执行前的初始值，或初始状态。(4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 (5)可行性。在有限时间内完成计算过程。 算法设计的整个过程,可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法和并行算法。 经典的算法主要有: 1、穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，bing从中找出那些符合要求的候选解作为问题的解。 穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举书来的情况数目会大得惊人，就是用高速计算机运行,其等待运行结果的时间也将使人无法忍受。我们在用穷举算法解决问题是，应尽可能将明显不符合条件的情况排除在外，以尽快取得问题的解。 2、迭代算法 迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或方程组)的过程，为实现这一过程所使用的方法统称为迭代法。迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为ｆ(ｘ)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0。 (2)将ｘ0的值保存于变量x1，然后计算g(x1),并将结果存于变量x0。 (3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（２）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。 3、递推算法 递推算法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系,从而达到目的。 4、递归算法 递归算法是一种直接或间接的调用自身的算法。 能采用递归描述的算法通常有这样的特征：为求解规模为ｎ的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模数据挖掘分类算法比较
LEACH算法仿真结果
算法设计与分析复习题目及答案
算法分析与设计习题集整理
《算法设计与分析》实验指导
LEACH算法的学习摘要
聚类分析算法解析
第一部分数据结构概论及算法分析答案
数据结构与算法分析习题与参考答案
1算法分析的目的是(
算法与算法分析
《算法设计与分析》教学大纲
算法设计与分析基础课后习题答案
算法分析与设计
1算法分析的目的是(
算法设计与分析学习总结
相关主题
文本预览