公共基础知识无基础

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

1、计算机等级考试公共基础知识数计学院卫春芳计算机二级考试公共基础知识大纲q数据结构与算法q程序设计基础q软件工程基础q数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30％，是一个不小的比例。第2页计算机二级考试公共基础知识试卷分析章节数据结构程序设软件工数据库设考试时间与算法计基础程基础计基础2007年4月10分2分10分8分2007年9月12分4分8分6分2008年4月10分2分8分10分2008年9月10分2分8分10分2009年3月10分2分8分10分2009年9月10分2分8分10分2010年3月10分0分10分

2、10分第3页对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。第4页算法是程序设计的核心算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。例：解方程：f(x)=0在区间[a,b]上有实根且f(a)与f(b)异号，求该方程在区间[a,b]上的实根。有多种解法，常用的是用二分法求方程实根。第5页2.算法的基本特征一个算法应该具有以下五个重要的特征：n有穷性一个算法必须

3、保证执行有限步之后结束；n确定性算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始n输入情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加n输出工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和n可行性纸做有限次运算后即可完成第6页一个算法的表示需要使用一些语言形式。传统的算法-------图形法，如“流程图”和N-S图目前常用的方法-------使用伪码描述算法。开始u算法与计算机程序算法____是一组逻辑步骤输入R程序——用计算机语言描述的算法S=3.14*R*RINPUTr输出S问题：

4、S=3.14*r*r输入园的半径，结束计算园的面积PTINTS第7页算法举例：n个数排序冒泡排序的方法：1.扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后；2.除最后一个元素，对剩余的元素重复上述过程，将次大的数排到表的倒数第二个位置；3.重复上述过程；对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。第8页4.算法的两个基本要素：u一是对数据对象的运算和操作；u二是算法的控制结构。u算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法第9页第10页第11页算法习题:(1)在计算机中，算法是指______。A.查询

5、方法B.加工方法(c)C.解题方案的准确而完整的描述D.排序方法(2)下列叙述中正确的是（07年4月）A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的(B)D)算法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指(08年4月)A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的(A)C）算法程序的长度是有限的D）算法只能被有限的用户使用第12页(4)算法的时问复杂度是指(2010年3月)A)算法的执行时间(D)B)算法所处理的数据量计算工作量C)算法程序中的语句或指令条数D

6、)算法在执行过程中所需要的基本运算次数(5)算法的空间复杂度是指(09年9月)(A)A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数(D)(6)下列叙述中正确的是(06年9月)A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小D）上述三种说法都不对第13页程序=算法+数据结构计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何

7、组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。第14页二.数据结构数据结构是指相互有关联的数据元素的集