2010公共基础知识-1

《2010公共基础知识-1》由会员分享，可在线阅读，更多相关《2010公共基础知识-1（65页珍藏版）》请在金锄头文库上搜索。

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

2、0分2分8分10分2009年3月10分2分8分10分3算法算法 算法的基本概念2.算法的基本特征3. 算法的表示4. 算法的要素5. 算法的评价 一、基本数据结构与算法一、基本数据结构与算法数据结构数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术 对于等级考试，这个部分的考核重点主要在算法的基本概念和特征、 二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。 4算法的定义uu对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法是程序设计的核心 算法的基本概念算法的基本概念算法是在有限步骤内求解某一问题所使用的一组 定义明确的规则。通俗点

3、说，就是计算机解题的过 程(计算的方法)。在这个过程中，无论是形成解题 思路(推理实现的算法)还是编写程序(操作实现的算 法)，都是在实施某种算法。例： 解方程：f(x)=0在区间a,b 上有实根且 f(a)与f(b) 异号，求该方 程在区间a,b 上的实根。有多种解法 ，常用的是用二分法求方程实根。52 . 算法的基本特征一个算法应该具有以下五个重要的特征：n 有穷性n 确定性n 输入n 输出n 可行性一个算法必须保证执行有限步之后 结束； 算法的每一步骤必须有确切的定义 ； 一个算法有0个或多个输入，以刻画运算对象的初始 情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输

4、出，以反映对输 入数据加 工后的结果。没有输出的算法是毫无意义的； 算法原则上能够精确地运行，而且人 们用笔和纸做有限次运算后即可完成 算法的特征：有穷性、 确定性、可行性、拥有足够的情报。 6u算法与计算机程序算法_是一组逻辑步骤程序用计算机语言描述的算法3. 3. 算法的表示算法的表示INPUT rS=3.14 * r*rPTINT S开始输入RS=3.14 * R*R输出S结束问题：输入园的半径， 计算园的面积一个算法的表示需要使用一些语言形式。传统的算法-图形法，如“流程图”和N-S图目前常用的方法-使用伪码描述算法。7冒泡排序的方法：1.扫描整个线性表，逐次对 相邻的两个元素进行比较

5、， 若为逆序，则交换；第一趟 扫描的结果使最大的元素排 到表的最后 ；2.除最后一个元素，对剩余 的元素重复上述过程，将次 大的数排到表的倒数第二个 位置；3.重复上述过程；对于长度为n的线性表，冒泡 排序需要对表扫描n-1遍。 算法举例：n个数排序84. 算法的两个基本要素：基本运算和操作基本运算和操作n 算术运算n 关系运算n 逻辑运算n 数据传输控制结构控制结构 n 顺序n 选择n 循环u一是对数据对象的运算和操作； u二是算法的控制结构。u算法基本设计 方法：列举法、归纳 法、递推、递归 、减斗递推技术、回溯法 95.5.算法评价算法评价评价一个算法优劣的主要标准是算法的执行效率和存储

6、需求：n 时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量n 空间复杂度：执行这个算法所需要的内存空间算法在执执行过过程中临时临时 占用的存储储空间间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临 时占用的存储空间这三个部分 10一、算法一、算法uu对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法不等于程序，也不等计算机方法，程序的编

7、制不算法不等于程序，也不等计算机方法，程序的编制不 可能优于算法的设计。可能优于算法的设计。 u算法的两个要素：一是对数据对象的运算和操作；二是算法的控制结构 。 uu算法的特征算法的特征：有穷性有穷性 、确定性、确定性 、可行性、可行性、 输入、输入、 输出输出 uu算法评价算法评价： n 时间复杂度：执行这个算法所需要的计算工作量n 空间复杂度：执行这个算法所需要的内存空间11(1) 算法一般都可以用哪几种控制结结构组组合而成_。A. 循环环、分支、递归递归B. 顺顺序、循环环、嵌套C. 循环环、递归递归 、选择选择D. 顺顺序、选择选择 、循环环 (2)算法中，对对需要执执行的每一步操作

8、，必须给须给 出清楚、严严格的规规定 ，这这属于算法的 （07年4月）A）正当性 B）可行性 C）确定性 D）有穷穷性 (3) 在计计算机中，算法是指_。A. 查询查询 方法 B. 加工方法C. 解题题方案的准确而完整的描述 D. 排序方法 (4)下列叙述中正确的是 （07年4月） A)算法的效率只与问题问题 的规规模有关，而与数据的存储结储结 构无关 B)算法的时间时间 复杂杂度是指执执行算法所需要的计计算工作量 C)数据的逻辑结逻辑结 构与存储结储结 构是一一对应对应 的 D)算法的时间时间 复杂杂度与空间间复杂杂度一定相关(D)(c)(c)(B)算法习题:12(5)算法的有穷穷性是指 (

9、08年4月)A）算法程序的运行时间时间 是有限的 B）算法程序所处处理的数据量是有限的 C）算法程序的长长度是有限的 D）算法只能被有限的用户户使用 (6) 算法的时间时间 复杂杂度是指_。A. 执执行算法程序所需要的时间时间B. 算法程序的长长度C. 算法执执行过过程中所需要的基本运算次数D. 算法程序中的指令条数(7)下列叙述中正确的是 (06年9月)A）一个算法的空间间复杂杂度大，则则其时间时间 复杂杂度也必定大B）一个算法的空间间复杂杂度大，则则其时间时间 复杂杂度必定小C）一个算法的时间时间 复杂杂度大，则则其空间间复杂杂度必定小D）上述三种说说法都不对对(A)(C)计算工作量(d)

10、13计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数 据元素在计算机中如何组织，以便提高数据处理的效率，并且节省 计算机的存储空间，这是进行数据处理的关键问题。二、数据结构二、数据结构 程序=算法+数据结构数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系 的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据 元素之间存在有某种关系（即联系），这种关系反映了该集 合中的数据元素所固有的一种结构。 14二. 数据结构数据结

11、构是指相互有关联的数据元素的集合。 数据结构是研究数据和数据之间关系的一门 学科，它包括三个方面。 （1）数据集合中各数据元素之间所固有的逻 辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计 算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。15u1. 逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 例： 1. 一年四季的数据结构B=(D,R)D=春，夏，秋，冬R=(春，夏) ,(夏，秋),(秋，冬) 2. 家庭成员的数据结构B=(D,R)D=父亲，

12、儿子，女儿R=(父亲，儿子) ,(父亲，女儿)春夏秋冬数据结构的图形表示父亲儿子女儿16u常见的逻辑结构有：线性结构、树形结构和图形结构。线性结构树形结构图形结 构u 线性结构 结构中的每个元素之间存在一个对一个的关系； u 树形结构 结构中的每个元素之间存在一个对多个的关系； u 图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。 其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可 以用二元关系表示，也可以直观地用图形来表示。 17u存储结构（物理结构）是指数据结构在计算机存储器中的具体实现。数据结结构（包括数据及其数据之间间的关系） 在计计算机存储储器上的存储储表示称为

13、为数据的物 理结结构或存储结储结 构，由于存储储表示的方法有 多种，诸诸如顺顺序、链链接、索引等，所以一种 数据结结构可以根据需要表示成一种或多种存 储结储结 构。 18u 2. 存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。如：一年四季 家庭成员 计算机存储空间怎样存放？存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：n 顺序存储结构n 链式存储结构n索引存储结构19u数据处理n 检索n 插入n 删除n 更新n 排序 数据处理（数

14、据的运 算）是指对数据集合中各 个元素以各种方式进行运 算，包括：插入、删除、 查找、更改、排序等，还 包括对数据元素进行分析 。u数据的逻辑结构表示数据元素之间的关系， 有一对一、一对多、多对多的关系； u数据的存储结构有顺序、链接、索引等。20数据结构是研究数据和数据之间关系 的一门学科，研究以下三方面内容：n 数据的逻辑结构n 数据的存储结构n 数据的运算21下一页上一页停止放映常见的数据结构1.线性表2.栈和队列3.树22 线性表（线性表（Linear ListLinear List）线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元 素之间的相对位置是线性的。在复杂线性表

15、中，由若干项数据元素组成 的数据元素称为记录，而由多个记录构成的线性表又称为文件。简单的线性表简单的线性表春夏秋冬复杂的线性表复杂的线性表记录1 02011001 张三 男 记录2 02011003 李四 女 记录3记录423线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点 ： （1）线性表中所有元素的所占的存储空间是连 续的； （2）线性表中各数据元素在存储空间中是按逻 辑顺序依次存放的。 ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,， ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。 24线性表的顺序存储结构线性表的顺序存储结构顺序存储结构把逻辑 上相邻的数据元素存储在 物理上相邻的存储单元里 ，顺序存储结构只存储结 点的值，不存储结点间的 关系，结点间的关系由存 储单元的邻接关系来体现 。a1a2aian存储地址200020042000+4*(i- 1)2000+4*(n- 1)占4个字节LoaLoa（a ai i）=Loa=Loa（a a1 1）+L*+L*（i-1i-1）第i个数的地址第一个数的地址L为该类型数所占的字节25u 顺序表的插入运算u 顺序表的删除运算顺序表的插入和删除运算顺序表的插入和删除运算在线性表顺序存储情况下