全国计算机等级考试二级教程公共基础知识第一章 数据结构与算法

《全国计算机等级考试二级教程公共基础知识第一章 数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国计算机等级考试二级教程公共基础知识2021/8/72第一章数据结构与算法2021/8/731.1算法1.1.1算法的基本概念算法是指解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法。一般说来，程序的编制不可能优于算法的设计。2021/8/741.1算法1.算法的基本特征可行性（effectiveness）确定性（definiteness）有穷性（finiteness）拥有足够的情报2021/8/751.1算法算法的定义：是一组严禁地定义的运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下

2、中止。2021/8/761.1算法2.算法的基本要素(1)算法中对数据的运算和操作算术运算逻辑运算关系运算数据传输2021/8/771.1算法(2)算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。描述算法的工具有传统流程图、N-S结构化流程图、算法描述语言等。算法的基本控制结构：顺序、选择、循环2021/8/781.1算法3.算法设计基本方法列举法归纳法递推递归减半递推技术回溯法2021/8/791.1算法例题1设方程f(x)=0在[a,b]上有实根，且f(a)与f(b)异号，利用二分法来该方程在区间[a,b]上的一个实

3、根。abcbc2021/8/7101.1算法1.1.2算法复杂度算法的复杂度包括时间复杂度和空间复杂度。1.算法的时间复杂度算法的时间复杂度是指算法所需要的计算工作量。与问题有关与问题的规模有关与输入有关2021/8/711课后习题选择1算法的时间复杂度是指执行算法程序所需要的时间算法程序的长度算法执行过程中所需要的基本运算次数算法程序中的指令条数2021/8/7122005年9月试题填空２算法复杂度主要包括时间复杂度和【2】复杂度。2021/8/7131.1算法算法工作量＝f（n）n是问题的规模2021/8/7141.1算法分析算

4、法的工作量平均性态最坏情况复杂性2021/8/7151.1算法例题2采用顺序搜索法，在长度为n的一维数组中查找值为x的元素。即从数组的第一个元素开始，逐个与被查值x进行比较，基本运算为x与数组元素的比较。2021/8/7161.1算法平均性态分析设被查项x在数组中出现的概率为q，则查找次数titi=i1≤i≤n时ti=n,i=n+1时假设x在每个位置上出现的概率一样，则在每个位置上出现的概率为q/n，不出现的概率为1-q，则平均查找次数为A(n)=1×q/n+2×q/n+3×q/n+……+n×q/n+n×(1-q)最坏情况为n202

5、1/8/7171.1算法2.算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。算法程序所占用的空间输入的初始数据所占的空间算法执行过程中所需的额外空间压缩存储技术2021/8/718课后习题选择２算法的空间复杂度是指算法程序的长度算法程序中的指令条数算法程序所占的存储空间算法执行过程中所需要的存储空间2021/8/7192006年9月试题选择７下列叙述中正确的是________。A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间可复杂

6、度必定小D）上述三种说法都不对2021/8/7201.2数据结构的基本概念数据结构所研究的问题数据的逻辑结构－－数据集合中各数据元素之间所固有的逻辑关系数据的存储结构－－在对数据进行处理时，各数据元素在计算机中存储关系对各种数据结构进行的运算2021/8/7211.2数据结构的基本概念1.2.1什么是数据结构数据结构是指相互有关联的数据元素的集合。数据元素：现实世界中客观存在的一切个体都可以是数据元素。2021/8/7221.2数据结构的基本概念例题3无序表的顺序查找与有序表的对分查找351678854329332154461621

7、29333543465478852021/8/7231.2数据结构的基本概念例题4查看学生情况登记表中的学生成绩总表分类表分等次表2021/8/7241.2数据结构的基本概念数据的逻辑结构数据元素的集合，记为DD上关系的集合，记为R数据结构表示为B=(D,R)数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构2021/8/7251.2数据结构的基本概念例题5一年四季的数据结构可以表示为B=(D,R)D=｛春，夏，秋，冬｝R=｛(春，夏)，(夏，秋)，(秋，冬)｝2021/8/7261.2数据结构的基本概念例题6家庭成员数据结构表示

8、为B=(D,R)D=｛父亲，儿子，女儿｝R=｛(父亲，儿子)，(父亲，女儿)｝2021/8/7271.2数据结构的基本概念例题7n维向量的数据结构X=(X1,X2,X3,…,Xn)D=｛X1,X2,X3,…,Xn｝R=｛(X1,X2)