计算机等考试公共基础知识

《计算机等考试公共基础知识》由会员分享，可在线阅读，更多相关《计算机等考试公共基础知识（191页珍藏版）》请在金锄头文库上搜索。

1、计算机等级考试 公共基础知识,温俊香,第2页,计算机二级考试公共基础知识大纲,数据结构与算法程序设计基础软件工程基础数据库设计基础,这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30，是一个不小的比例。,第3页,计算机二级考试公共基础知识试卷分析,第4页,算法 算法的基本概念2.算法复杂度的概念和意义,一、基本数据结构与算法,数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术,对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。,第5页,算法的定

2、义 对解题方案准确而完整的描述称为算法。,算法是程序设计的核心, 算法的基本概念,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。,例： n个数从大到小进行排序。有多种排序方法 ，常用的有冒泡排序、选择排序等。,算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。,讲课 说课,第6页,2 . 算法的基本特征 一个算法应该具有以下五个重要的特征：,有穷性确定性输入输出可行性,拥有足够的情报,第7页,算法与计算机程序算法_是一组

3、逻辑步骤程序用计算机语言描述的算法,3. 算法的表示,INPUT r S=3.14 * r*r PTINT S,问题： 输入园的半径，计算园的面积,一个算法的表示需要使用一些语言形式。 传统的算法-图形法，如“流程图”和N-S图 目前常用的方法-使用伪码描述算法。,第8页,冒泡排序的方法： 1.扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后 ； 2.除最后一个元素，对剩余的元素重复上述过程，将次大的数排到表的倒数第二个位置； 3.重复上述过程； 对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。,算法举例：n个数排序,第9页,4. 算

4、法的两个基本要素：,基本运算和操作算术运算关系运算逻辑运算数据传输,控制结构 顺序选择循环,一是对数据对象的运算和操作； 二是算法的控制结构。,算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法,第10页,5. 算法的复杂度评价一个算法优劣的主要标准是算法的执行效率和存储需求：时间复杂度：执行这个算法所需要的计算工作量 一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度：执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。 一个算法在计算机存储器上所占用的

5、存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分,第11页,(1) 在计算机中，算法是指_。 A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法 (2)下列叙述中正确的是 （07年4月） A)算法的效率只与问题的规模有关，而与数据的存储结构无关 B)算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的 D)算法的时间复杂度与空间复杂度一定相关 (3)算法的有穷性是指 (08年4月) A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C

6、）算法程序的长度是有限的 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）一个

7、算法的时间复杂度大，则其空间复杂度必定小D）上述三种说法都不对,(D) 计算工作量,(A),(D),算法的时间复杂度是指 A) 执行算法程序所需要的时间 B) 算法程序的长度 C) 算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数算法的基本特征是可行性、确定性、 【1】 和拥有足够的情报。算法的空间复杂度是指A) 算法程序的长度 B) 算法程序中的指令条数C) 算法程序所占的存储空间 D) 执行过程中所需要的存储空间在计算机中，算法是指A) 加工方法 B) 解题方案的准确而完整的描述 C) 排序方法 D) 查询方法,例题讲解,有穷性,算法分析的目的是A) 找出数据结构的合理性 B

8、) 找出算法中输入和输出之间的关系C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改进算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 【1】 。,时间复杂度和空间复杂度,第15页,计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。,二、数据结构,程序=算法+数据结构,数据结构是指相互有关联的数据元素的集合。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总

9、是分别进行处理。 一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。,第16页,二. 数据结构,数据结构是指相互有关联的数据元素的集合。 数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。 （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。,第17页,1. 逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含： （1）表示数据元素的信息； （2

10、）表示各数据元素之间的前后件关系。 例： 1. 一年四季的数据结构B=(D,R)D=春，夏，秋，冬R=(春，夏) ,(夏，秋),(秋，冬) 2. 家庭成员的数据结构B=(D,R)D=父亲，儿子，女儿R=(父亲，儿子) ,(父亲，女儿),春,夏,秋,冬,数据结构的图形表示,第18页,常见的逻辑结构有： 线性结构、树形结构和图形结构。, 线性结构 结构中的每个元素之间存在一个对一个的关系； 树形结构 结构中的每个元素之间存在一个对多个的关系； 图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。 其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示，也可以直观地用图

11、形来表示。,第19页,2. 存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。 如：一年四季 家庭成员 计算机存储空间怎样存放？存储结构指数据结构在计算机存储空间中的具体实现。 常见的存储结构有：顺序存储结构链式存储结构索引存储结构,只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结构。一种数据结构可以根据需要表示成一种或多种存储结构。,第20页,3. 数据的运算检索插入删除更新排序,通常，一个数据结构中的元素结点可能是动态变化的

12、。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。如：无序表变有序表,数据结构是研究数据和数据之间关系的一门学科，研究以下三方面内容：数据的逻辑结构数据的存储结构数据的运算,第21|92页,常见的数据结构,数据结构分类线性结构与非线性结构两大类型,线性结构：一个非空的数据结构若满足下面的两个条件，则这种数据结构即为线性结构。 有且仅有一个根结点； 除第一个结点外，每

13、一个结点最多有一个前件；除最后一个结点外，每一个结点最多有一个后件。,常见的线性结构有：线性表、栈、队列、线性链表等,第22|92页,常见的非线性结构有树、二叉树、图等,非线性结构：一个数据结构不是线性结构。,第23页, 线性表（Linear List）,线性表是由n（n0）个数据元素a1，a2，ai，an组成的一个有限序列。,简单的线性表,复杂的线性表,记录1 02011001 张三 男 ,记录2 02011003 李四 女 ,记录3,记录4,第24页,线性表的顺序存储结构,特点： 顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，顺序存储结构只存储结点的值，不存储结点间的关系

14、，结点间的关系由存储单元的邻接关系来体现。,存储地址,2000,2004,2000+4*(i-1),2000+4*(n-1),占4个字节,Loa（ai）=Loa（a1）+L*（i-1）,第i个数的地址,第一个数的地址,L为该类型数所占的字节,线性表的存储结构,线性表的存储结构有两种：顺序存储结构链式存储结构,第25页,顺序表的插入运算顺序表的删除运算,顺序表的插入和删除运算,在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。,线性表的顺序存储结构称为顺序表。,第26页,插入运算,插入算

15、法的分析:假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：,第27页,删除运算,删除算法的分析:在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：,总结:顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,第28页,线性表的链式存储结构,线性表的链式存储结构称为线性链表。链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系： 链式存储结构分为单链表、双向链表、循环链表 线性链表不能随机存取,第29页,设线性表为（a1，a2，a3，a4，a5）,HEAD,3,线性链表的物理状态,线性表的顺序存储结构,注意:1 2 3 此类编号不代表所在的地址单元的地址编码,线性表的链式存储结构 及其插入与删除操作,第30页,单链表,第31页,单链表的插入运算,在P所指向的结点之后插入新的结点,单链表删除运算,要求:删除结点ai。,第32页,循环链表: 首尾相接的链表。将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。,