2011计算机2级公共基础知识

计算机等级考试 公共基础知识 张玲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分10分3算法算法 算法的基本概念2.算法复杂度的概念和意 义 一、基本数据结构与算法一、基本数据结构与算法数据结构数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术 对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概 念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。 4算法的定义uu对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法是程序设计的核心 算法的基本概念算法的基本概念算法是在有限步骤内求解某一问题所使用的一组 定义明确的规则。通俗点说，就是计算机解题的过 程(计算的方法)。在这个过程中，无论是形成解题 思路(推理实现的算法)还是编写程序(操作实现的算 法)，都是在实施某种算法。例： n个数从大到小进行排序。有多种排序方法 ，常用的有冒泡排序、选择排序等。 52 . 算法的基本特征一个算法应该具有以下五个重要的特征：n 有穷性n 确定性n 输入n 输出n 可行性一个算法必须保证执行有限步之后 结束； 算法的每一步骤必须有确切的定义 ； 一个算法有0个或多个输入，以刻画运算对象的初始 情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输 入数据加 工后的结果。没有输出的算法是毫无意义的； 算法原则上能够精确地运行，而且人 们用笔和纸做有限次运算后即可完成 6u算法与计算机程序算法_是一组逻辑步骤程序用计算机语言描述的算法3. 3. 算法的表示算法的表示INPUT rS=3.14 * r*rPTINT S开始输入RS=3.14 * R*R输出S结束问题：输入园的半径， 计算园的面积一个算法的表示需要使用一些语言形式。传统的算法-图形法，如“流程图”和N-S图目前常用的方法-使用伪码描述算法。7冒泡排序的方法：1.扫描整个线性表，逐次对 相邻的两个元素进行比较， 若为逆序，则交换；第一趟 扫描的结果使最大的元素排 到表的最后 ；2.除最后一个元素，对剩余 的元素重复上述过程，将次 大的数排到表的倒数第二个 位置；3.重复上述过程；对于长度为n的线性表，冒泡 排序需要对表扫描n-1遍。 算法举例：n个数排序84. 算法的两个基本要素：基本运算和操作基本运算和操作n 算术运算n 关系运算n 逻辑运算n 数据传输控制结构控制结构 n 顺序n 选择n 循环u一是对数据对象的运算和操作； u二是算法的控制结构。u算法基本设计 方法：列举法、归纳 法、递推、递归 、减半递推技术、回溯法 95.5.算法评价算法评价评价一个算法优劣的主要标准是算法的执行效率和存储需求：n 时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量n 空间复杂度：执行这个算法所需要的内存空间算法在执执行过过程中临时临时 占用的存储储空间间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临 时占用的存储空间这三个部分10一、算法一、算法uu对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为算法。算法不等于程序，也不等计算机方法，程序的编制不可算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。能优于算法的设计。uu算法评价算法评价：n 时间复杂度：执行这个算法所需要的计算工作量n 空间复杂度：执行这个算法所需要的内存空间11(1) 在计计算机中，算法是指_。A. 查询查询 方法 B. 加工方法C. 解题题方案的准确而完整的描述 D. 排序方法 (2)下列叙述中正确的是 （07年4月） A)算法的效率只与问题问题 的规规模有关，而与数据的存储结储结 构无关 B)算法的时间时间 复杂杂度是指执执行算法所需要的计计算工作量 C)数据的逻辑结逻辑结 构与存储结储结 构是一一对应对应 的 D)算法的时间时间 复杂杂度与空间间复杂杂度一定相关 (3)算法的有穷穷性是指 (08年4月) A）算法程序的运行时间时间 是有限的 B）算法程序所处处理的数据量是有限的 C）算法程序的长长度是有限的 D）算法只能被有限的用户户使用(c)(B)算法习题:(A)12(4) 算法的时问时问 复杂杂度是指 (2010年3月)A)算法的执执行时间时间B)算法所处处理的数据量C)算法程序中的语语句或指令条数D)算法在执执行过过程中所需要的基本运算次数 (5) 算法的空间间复杂杂度是指 (09年9月) A）算法在执执行过过程中所需要的计计算机存储储空间间 B）算法所处处理的数据量 C）算法程序中的语语句或指令条数 D）算法在执执行过过程中所需要的临时临时 工作单单元数 (6) 下列叙述中正确的是 (06年9月)A）一个算法的空间间复杂杂度大，则则其时间时间 复杂杂度也必定大B）一个算法的空间间复杂杂度大，则则其时间时间 复杂杂度必定小C）一个算法的时间时间 复杂杂度大，则则其空间间复杂杂度必定小D）上述三种说说法都不对对(D)计算工作量(A)(D)13计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数 据元素在计算机中如何组织，以便提高数据处理的效率，并且节省 计算机的存储空间，这是进行数据处理的关键问题。二、数据结构二、数据结构 程序=算法+数据结构数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系 的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据 元素之间存在有某种关系（即联系），这种关系反映了该集 合中的数据元素所固有的一种结构。 14二. 数据结构数据结构是指相互有关联的数据元素的集合。 数据结构是研究数据和数据之间关系的一门 学科，它包括三个方面。 （1）数据集合中各数据元素之间所固有的逻 辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计 算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。15u1. 逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 例： 1. 一年四季的数据结构B=(D,R)D=春，夏，秋，冬R=(春，夏) ,(夏，秋),(秋，冬) 2. 家庭成员的数据结构B=(D,R)D=父亲，儿子，女儿R=(父亲，儿子) ,(父亲，女儿)春夏秋冬数据结构的图形表示父亲儿子女儿16u常见的逻辑结构有：线性结构、树形结构和图形结构。线性结构树形结构图形结构u 线性结构 结构中的每个元素之间存在一个对一个的关系； u 树形结构 结构中的每个元素之间存在一个对多个的关系； u 图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。 其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可 以用二元关系表示，也可以直观地用图形来表示。 17u 2. 存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。如：一年四季 家庭成员 计算机存储空间怎样存放？存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：n 顺序存储结构n 链式存储结构n索引存储结构只抽象地反映数据元素之间的关系 的结构，而不管其存储方式的数据 结构称为逻辑结构。一种数据结构可以根据需要表示成 一种或多种存储结构。 18u3. 数据的运算n 检索n 插入n 删除n 更新n 排序 通常，一个数据结构中的元素结点可能是动态变化的。根 据需要或在处理过程中，可以在一个数据结构中增加一个新结 点（插入运算），也可以删除某个结点（删除运算），除此之 外，对数据结构的运算还有查找、分类、合并、分解、复制和 修改。在对数据结构的处理过程中，不仅数据结构中结点的个数 在动态变化，而且，各数据元素之间的关系也有可能在动态地 变化。如：无序表变有序表数据结构是研究数据和数据之间 关系的一门学科，研究以下三方面 内容：n 数据的逻辑结构n 数据的存储结构n 数据的运算19下一页上一页停止放映常见的数据结构1.线性表2.栈和队列3.树20 线性表（线性表（Linear ListLinear List）线性表是由n（n0）个数据元素a1，a2，ai，an组成的一个有限序列。简单的线性表简单的线性表春夏秋冬复杂的线性表复杂的线性表记录1 02011001 张三 男 记录2 02011003 李四 女 记录3记录421线性表的顺序存储结构线性表的顺序存储结构顺序存储结构把逻辑上相邻 的数据元素存储在物理上相邻的存 储单元里，顺序存储结构只存储结 点的值，不存储结点间的关系，结 点间的关系由存储单元的邻接关系 来体现。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为该类型数所占的字节线性表的存储结构线性表的存储结构线性表的存储结构有两种： u 顺序存储结构 u 链式存储结构22u 顺序表的插入运算u 顺序表的删除运算顺序表的插入和删除运算顺序表的插入和删除运算在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。线性表的顺序存储结构称为顺序表。23线性表的链式存储结构线性表的链式存储结构u 线性表的链式存储结构称为线性链表。u 链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。 各数据元素的先后关系是由各结点的指针域指示。u 链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：数据域指针域24应用举例应用举例线性链表的存储结构线性链表的存储结构设线性表为（a1，a2，a3，a4，a5）1a29 2 3a11 4 5a410 6 7 8 9a35 10a50HEAD 3a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的物理状态1 a 1 2 a 2 3 a 3 4 a 4 5 a 5 6 7线性表的线性表的顺顺 序存储序存储结构结构注意:1 2 3 此类编号不 代表所在的 地址单元的 地址编码25u 单链表的插入运算u