好老师在线ihaols【自考】自考算法设计分析复习题

《好老师在线ihaols【自考】自考算法设计分析复习题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、好老师在线资料中心查资料,比课程,找好老师!自考算法设计分析复习题第一章算法基础知识1.简单描述算法的定义以及算法的特性。答：算法是指解决那些适合于计算机实现的问题的方法或过程，即对特定问题求解步骤的一种描述。算法具有5个特性：输入性、输出性、确定性、有穷性和可行性。2.简述算法评估的方法与度量指标。答：算法评估的方法：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求

2、：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。度量指标算法的时间复杂度和空间复杂度。3.算法的三种基本结构是什么？答：4.举例说明什么是算法的空间复杂度？答：一个算法所占用的存储空间包括算法自身、算法的输入、算法的输出及实现算法的程序在运行时所占用空间的总和。对于一个算法空间复杂度的衡量主要考虑的是算法在运行过程中所需要的存储空间的大小。一般空间复杂度以最坏情况来分析。5.试列举算法复杂度分别为0(n2)和O(nlog2n)的算法。并解释由阶0(n2)改进

3、为O(nlog2n)W根本原因是什么？例冒泡排序算法中，其空间复杂度为S(n)=O(n)顺序结构、选择结构、循环结构。1答：如：快速排序的平均时间复杂度为O(nlog2n)；冒泡排序的时间复杂度为0(n2)一般情况下一个算法的时间复杂度考虑的只是对于问题规模n的增长率，此时只需计算出它关于n的增长率或阶即可。nlog2n的值比n2的值小，值越小效率越高，由阶0(n2)改进为O(nlog2n)提高了时间效率。6.给出下面算法的时间复杂度for(i=l;i<=n;++i)for(j=l;j<=n;++j){}答：1.

4、给出下面算法的时间复杂度intfact(intn){}答：2.利用伪码语言描述：求两个正整数m和n的最大公约数的算法。答：用辗转相除法求最大公约数，其算法描述为：输入两个正整数放入变量m和n中；将；进入循环，循环控制条件为r不等于0;若满足，则将n值送入m中，将r值送入n中，将m对n求余的结果放入变量『中；若不满足，则n为最大公约数，输出最大公约数n。2c[i][j]=0;for(k=l;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];时间复杂度为：O(n3)if(n

5、turn(n*fact(n-l));else时间复杂度为：O(n)3.利用伪码语言描述：将保存在数组中的若干元素从小到大进行排序的算法。答：4.利用伪码语言描述：将两个分别装有果汁和酒的杯子进行互换的算法。答：5.有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就有被吃掉的危险。试用伪码语言描述出一种安全的渡河方案。答：算法分析先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：初始状态：甲岸，3野人，3牧师；乙岸，0野人，0牧师；船停在甲岸，

6、船上有0个人；目标状态：甲岸，0野人，0牧师；乙岸，3野人，3牧师；船停在乙岸，船上有0个人；整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符(按照渡船方向的不同，也可以理解为10个算符人渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过一个FindNext(„)®数找出下一步可以进行的渡河操作中的最优操作，如果没

7、有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(„)3用冒泡排序法按升序排序，其算法描述为：输入10个相同类型的数放入一维数组a[10]中；进行n・l轮比较，用外循环控制：for(i=0;i<9;i++);每轮比较n・i・l次，用内循环控制：for(j=0;j<9-i;j++);每次用相邻两数比较，若前面的数大，则交换两个数：if(aU]>a[j+l]),排序结束后，输出排好序的10个数。则a[j]与a[j+l]交换；算法描述为：设果汁杯为a,酒杯为b,空杯为c；将果汁倒入空杯c,即a

8、->c;将酒倒入果汁杯，即b->a；将空杯c中的果汁倒入酒杯，即c-b。函数递规调用FindNext(„),一级一级的向后扩展。搜索中采用的一些规则如下：1、渡船优先规则：甲岸一次运走的人越多越好(即甲岸运多人优先)，同时野人优先运走；乙岸一次运走的人越少越好(即乙岸运少人优先)，同时牧师优先运走；2、不能重复上次渡船操作(通过链表中前一操作比较)，避免进入死循环；3、任