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

好老师在线，省钱好教育 找资料，查课程，好老师！ 好老师在线 资料中心 查资料，比课程，找好老师！ 自考算法设计分析复习题 第一章 算法基础知识 1．简单描述算法的定义以及算法的特性。 答： 算法是指解决那些适合于计算机实现的问题的方法或过程，即对特定问题求解步骤的一 种描述。 算法具有5 个特性：输入性、输出性、确定性、有穷性和可行性。 2．简述算法评估的方法与度量指标。 答： 算法评估的方法： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生 莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的 最大存储空间。一般这两者与问题的规模有关。 度量指标 算法的时间复杂度和空间复杂度。 3．算法的三种基本结构是什么？ 答： 4 ．举例说明什么是算法的空间复杂度？ 答： 一个算法所占用的存储空间包括算法自身、算法的输入、算法的输出及实现算法的程序在 运行时所占用空间的总和。对于一个算法空间复杂度的衡量主要考虑的是算法在运行过程 中所需要的存储空间的大小。一般空间复杂度以最坏情况来分析。 5．试列举算法复杂度分别为O(n2)和O(nlog2n)的算法。并解释由阶O(n2)改进为 O(nlog2n)的根本原因是什么？ 例冒泡排序算法中，其空间复杂度为S(n)=O(n) 顺序结构、 选择结构、循环结构。 1 答： 如：快速排序的平均时间复杂度为O(nlog2n)；冒泡排序的时间复杂度为 O(n2 ） 一般情况下一个算法的时间复杂度考虑的只是对于问题规模n 的增长 率，此时只需计算出它关于n 的增长率或阶即可。nlog2n 的值比 n2 的值小，值越小效率越高，由阶O(n2)改进为O(nlog2n)提高了时间效率。 6．给出下面算法的时间复杂度 好老师在线，省钱好教育 找资料，查课程，好老师！ for(i=1;i=n;++i) for(j=1;j=n;++j){ } 答： 7．给出下面算法的时间复杂度 int fact(int n){ } 答： 8 ．利用伪码语言描述：求两个正整数m 和n 的最大公约数的算法。 答： 用辗转相除法求最大公约数，其算法描述为: 输入两个正整数放入变量m 和n 中； 将； 进入循环,循环控制条件为r 不等于0; 若满足，则将n 值送入 m 中,将r 值送入 n 中，将m 对n 求余的结果放入变量 r 中； 若不满足，则 n 为最大公约数，输出最大公约数n。 2 c[i][j]=0; for(k=1;k=n;++k) c[i][j]+=a[i][k]*b[k][j]; 时间复杂度为：O(n3) if(n1) return 1; return(n*fact(n-1)); else 时间复杂度为：O(n) 9 ．利用伪码语言描述：将保存在数组中的若干元素从小到大进行排序的算法。 答： 10．利用伪码语言描述：将两个分别装有果汁和酒的杯子进行互换的算法。 答： 11．有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上， 如果野人的人数大于牧师的人数，那么牧师就有被吃掉的危险。试用伪码语言描述出一种 安全的渡河方案。 答： 算法分析 先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸： 初始状态：甲岸，3 野人，3 牧师； 乙岸，0 野人，0 牧师； 船停在甲岸，船上有0 个人； 目标状态：甲岸，0 野人，0 牧师； 乙岸，3 野人，3 牧师； 船停在乙岸，船上有0 个人； 整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变 是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求， 可以得出以下5 个算符（按照渡船方向的不同，也可以理解为10 个算符）： 渡1 野人、渡1 牧师、渡1 野人1 牧师、渡2 野人、渡2 牧师 算符知道以后，剩下的核心问题就是有哪些信誉好的足球投注网站方法了，本文采用深度优先有哪些信誉好的足球投注网站，通过一个 FindNext(„)函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节 点，看看是否有其它兄弟节点可以扩展，然后用Process(„) 3 用冒泡排序法按升序