公共基础知识ppt培训课件

《公共基础知识ppt培训课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国计算机等级考试二级教程－－公共基础知识数据结构与算法程序设计基础软件工程基础数据库设计基础√√1考试方式公共基础知识有10道选择题和5道填空题共三十分。数据结构部分和软件工程部分是考核的重点，二叉树的遍历和求结点数需理解掌握，其它部分以识记为主。2第1部分数据结构与算法3算法算法的概念算法的时间复杂度算法的空间复杂度4什么是算法？所谓算法（Algorithm)是描述计算机解决给定问题的操作过程（解题方法），可以用汉语描述，也可以用英语等描述，即为解决某一特定问题而由若干条指令组成的有穷序列。5例：求给定半径的圆的面积输入半径，赋给变量r（判断r是否大于等于0）如果r>

2、=0面积=3.14*r*r否则提示输入错误，半径不能为负数输出面积的值6算法必须满足以下五个特性：（1）有穷性---执行了有限条指令后一定要终止。（2）确定性（无二义）---算法的每一步操作都必须有确切定义，不得有任何歧义性。（3）可行性---算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。（4）输入数据（5）输出数据思考：算法与程序有何区别？7算法的描述和实现描述---可采用自然语言、数学语言或约定的符号语言。实现---必须借助程序设计语言提供的数据类型及其运算。程序=算法+数据结构软件=程序+文档（软件工程的观点）8算法效率的度量之--------时间复杂

3、度1.时间复杂度（不考虑机器软硬件环境时算法的时间耗费）一个用高级语言编写的程序在计算机执行时耗费的时间或称为算法中基本操作运算次数。决定因素：算法所选用的策略问题的规模（求100以内还是1000以内的数的和）书写程序所采用的语言（语言级别越高，执行效率越低）编译程序所产生的机器代码的质量机器执行指令的速度撇开这些与计算机硬件、软件有关的因素，可以认为一个特定的算法“运行工作量”的大小，只依赖于问题的规模（通常用整数n表示）。9算法效率的度量：采用时间复杂度例：分析以下程序段的时间复杂度（先看执行次数）（1）{s=0，x=x+1}（2）fori=1ton{s=s+i，i=i+

4、1}（3）fori=1tonforj=1ton{c[i][j]=0;}基本操作一般是最深层循环内的语句10算法效率的度量：采用时间复杂度（1）{s=0，x=x+1}O(1)（2）fori=1ton{s=s+i，i=i+1}O(n)（3）fori=1tonforj=1ton{c[i][j]=0;}O(n2)它表示随着问题规模n的增大，算法执行时间的增长率和括号内函数的增长率相同，称作渐进时间复杂度，简称时间复杂度。11算法效率的度量之--------空间复杂度2.空间复杂度一般是指执行这个算法时所需要的辅助内存空间。算法的时间复杂度和空间复杂度没有必然的联系，它们没有相关性。一

5、般考虑算法效率时，主要考虑时间复杂度。12历年真题(2)算法的时间复杂度是指（2010年3月）A)算法的执行时间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数(4)算法的空间复杂度是指()（2009年9月）A)算法在执行过程中所需要的计算机存储空间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的临时工作单元数答案:(2)D(4)A13历年真题(1)下列叙述中正确的是（）（2007年4月）A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是执行算法所需要的计算工作量C)数据的

6、逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关5.算法的有穷性是指（）（2008年4月）A)算法程序的运行时间是有限的B)算法程序处理的数据量是有限的C)算法程序的长度是有限的D)算法只能被有限的用户使用答案：(1)B5.A14数据结构（定义P144）包括逻辑结构和物理结构什么是逻辑结构？（P144）什么是物理结构？（P145）逻辑结构和物理结构的关系？各数据元素在计算机存储空间中位置关系与他们的逻辑关系不一定相同。012345678910111213141516171819202122232425262728293031夏春冬秋01234567891

7、01112131415161718192021222324252627冬夏春秋2829303115春夏秋冬一年四季数据结构的图形表示父亲儿子女儿家庭成员间辈分关系数据结构的图形表示线性结构非线性结构两类逻辑结构：P145定义16两类物理结构：定义P145顺序存储链式存储A1A2An-1An…………HEAD数据1数据2数据nNULL…数据域指针域01234567891011121314151617181920212223242526272829303111016null25HEAD16125NULL101