《C语言课程课件 二级C语言等级考试 公共基础知识 part1》由会员分享，可在线阅读，更多相关《C语言课程课件 二级C语言等级考试 公共基础知识 part1（43页珍藏版）》请在金锄头文库上搜索。
1、计算机等级考试 公共基础知识 第2页计算机二级考试公共基础知识大纲 q 数据结构与算法q 程序设计基础q 软件工程基础q 数据库设计基础这四个方面在试卷中出现的情况是：选择题 10个（10分），总分值占 到了试卷卷面分的10，是一个不小的比例。 第3页算法算法 算法的基本概念2.算法复杂度的概念和 意义 一、基本数据结构与算法一、基本数据结构与算法数据结构数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术 对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概 念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。第4页对解题方案准确而完整的描述称为算法。
2、算法是程序设计的核心 算法的基本概念2 . 算法的基本特征一个算法应该具有以下五个重要的特征：有穷性、 确定性、 可行性 有零个或多个输入、 有一个或多个输出拥有足够的情报第5页3. 算法的两个基本要素：基本运算和操作基本运算和操作n 算术运算n 关系运算n 逻辑运算n 数据传输控制结构控制结构 n 顺序n 选择n 循环u一是对数据对象的运算和操作； u二是算法的控制结构。u算法基本设计方法：列举法、归纳法、递推、 递归、减斗递推技术、回溯法 第6页4. 算法的复杂度评价一个算法优劣的主要标准是算法的执行效率和存储需求：n 时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所
3、需基本运算的执行次数来度量计算工作量n 空间复杂度：执行这个算法所需要的内存空间算法在执执行过过程中临时临时 占用的存储储空间间第7页(1) 在计计算机中，算法是指_。A. 查询查询 方法 B. 加工方法C. 解题题方案的准确而完整的描述 D. 排序方法 (2)下列叙述中正确的是 （07年4月） A)算法的效率只与问题问题 的规规模有关，而与数据的存储结储结 构无关 B)算法的时间时间 复杂杂度是指执执行算法所需要的计计算工作量 C)数据的逻辑结逻辑结 构与存储结储结 构是一一对应对应 的 D)算法的时间时间 复杂杂度与空间间复杂杂度一定相关 (3)算法的有穷穷性是指 (08年4月) A）算法
4、程序的运行时间时间 是有限的 B）算法程序所处处理的数据量是有限的 C）算法程序的长长度是有限的 D）算法只能被有限的用户户使用(c)(B)算法习题:(A)(4) 下列叙述中正确的是 (06年9月)A）一个算法的空间间复杂杂度大，则则其时间时间 复杂杂度也必定大 B）一个算法的空间间复杂杂度大，则则其时间时间 复杂杂度必定小 C）一个算法的时间时间 复杂杂度大，则则其空间间复杂杂度必定小 D）上述三种说说法都不对对(5)算法分析的目的是 A) 找出数据结结构的合理性 B) 找出算法中输输入和输输出之间间的关系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改进进(D)(D)1数据的逻
5、辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构A 顺序存储B 链式存储 线性表、数组栈、广义表 队列、串树形结构图形结构数据结构的三个方面 数据结构可描述为 Group=（D，R）第10页二. 数据结构数据结构是指相互有关联的数据元素的集合。 数据结构是研究数据和数据之间关系的一门学科，它 包括三个方面。 （1）数据集合中各数据元素之间所固有的逻辑关系 ，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中 的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。第11页u 1. 逻辑结构 数据的逻辑结构是指反映数据
6、元素之间逻辑关系的数据结构 。数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 例：1. 一年四季的数据结构B=(D,R)D=春，夏，秋，冬R=(春，夏) ,(夏，秋),(秋，冬)2. 家庭成员的数据结构B=(D,R)D=父亲，儿子，女儿R=(父亲，儿子) ,(父亲，女儿)春夏秋冬数据结构的图形表示父亲儿子女儿B表示数据结构 D是数据元素的有限集 R是D上关系的有限集第12页u常见的逻辑结构有：线性结构、树形结构和图形结构。线性结构树形结构图形结构u 线性结构 结构中的每个元素之间存在一个对一个的关系； u 树形结构 结构中的每个元素之间存在一个对多个的
7、关系； u 图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。 其中，树形结构和图形结构统称为非线形结构。第13页u 2. 存储结构（物理结构）存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：n 顺序存储结构n 链式存储结构n 索引存储结构一种数据结构可以根据需要表示成一种或 多种存储结构。第14|92页常见的数据结构u 数据结构分类： 线性结构与非线性结构两 大类型线性结构：一个非空的数据结构若满足下面的两个条件，则 这种数据结构即为线性结构线性结构。 有且仅有一个根结点； 除第一个结点外，每一个结点最多有一个前件；除最后一个结点外，每一个结点最多有一个后件。常
8、见的线性结构有：线性表、栈、队列、线性链表等线性表、栈、队列、线性链表等常见的非线性结构有:树、二叉树、图等二叉树、图等非线性结构：一个数据结构不是线性结构。第15页栈栈和队列和队列栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。uu 栈（栈（StackStack）及其基本运算）及其基本运算uu 队列（队列（QueueQueue）及其基本运算）及其基本运算uu 循环队列及其基本运算循环队列及其基本运算第16页1 .栈栈是限定仅在表尾进行插入或删除操作的线性表。栈顶表尾。栈底表头。空栈不含元素的空表。a1a2an栈底栈顶进栈出栈栈s=(a1,a2,an)
9、后进先出或先 进后出（LIFO ）第17页2、队列定义：一种特殊的线性结构，限定只能在表的一端进行插入 ，在 表的另一端进行删除的线性表 。此种结构称为先进先 出（FIFO）表。a1 , a2 , a3 , a4 , an-1 , an队 列 示 意 图队头队尾先进先出 后进后出 （LIFO）队列中进行插入的一端称做队尾(rear),进行删除的一端 称做队首(front)。 第18页数据存储结构方面的考题 1：数据的存储结储结 构是指 （2005年4月）A) 存储储在外存中的数据 B) 数据所占的存储储空间间量C) 数据在计计算机中的顺顺序存储储方式 D) 数据的逻辑结逻辑结 构在计计算机中的
10、表示2. 下列叙述中正确的是 （2009年3月） A）栈栈是“先进进先出”的线线性表B）队队列是“先进进后出”的线线性表C）循环队环队 列是非线线性结结构D）有序线线性表既可以采用顺顺序存储结储结 构，也可以采用链链式存储结储结 构 3. 数据结构分为线性结构和非线性结构，带链的队列属于 。4. 下列数据结构中，属于非线性结构的是A）循环队列 B) 带链队列C) 二叉树 D）带链栈答案：D。答案：D。答案：线性结构 。答案：c第19页5.下列关于栈栈的叙述正确的是 （2008年4月） A）栈栈按“先进进先出”组织组织 数据 B)栈栈按“先进进后出”组织组织 数据 C）只能在栈栈底插入数据 D）
11、不能删删除数据 答案：B。6. 一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3 ，2，1依次入队，然后再依次退队，则元素退队的顺序为 【1】 。（ 2010年3月） 答案：A，B，C，D，E，F，5，4，3，2，1队列的特点：“先进先出”或“后进后出”。7.栈和队列的共同特点是A)都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点8.如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2D) 任意顺序9.栈底至栈顶依次存放元素A、B、C、D，在第五个
12、元素E入栈前， 栈中元素可以出栈，则出栈序列可能是A) ABCED B) DCBEA C) DBCEA D) CDABE 第21页树型结构是一种重要的非线性结构。u 树的概念u 二叉树的概念u 二叉树的存储u 二叉树的遍历树树与二叉树与二叉树第22页树的概念树的概念u 树的定义：是一种简单的非线性结构。 n个结点的有限集 。（n=0） ABDFECGHIJKMn n结点：结点：n n根结点：根结点：没有前件的结点， 只有一个称为根结点。 简称树 的根。n n父结点：父结点：结点的前件称该结 点的父结点。（相对而言） A只有一个 结点的树第23页树型结构的常用术语树型结构的常用术语ABDFECG
13、HIJKMn n子结点：子结点：结点的后件，称为该结 点的子结点。可以有多个。n n叶子结点叶子结点 没有后件的结点；Q：图中叶子结点有几个？n n结点的度结点的度 一个结点的子树的个数 ；(有几个分叉) Q：结点A、G的度数？Q：度数为0、1、2、3的结点分别有几个？n 树的度树的度 树中所有结点度的最大值 ；Q：右图中树的度？73,2 7,1,2,23第24页树型结构的常用术语树型结构的常用术语ABDFECGHIJKMn 结点的层次结点的层次 树中根结点的层次 为1，根结点子树的根为第2层，以 此类推；Q：图中结点F的层次？n 树的深度树的深度 树中所有结点层次的最大值；Q：图中树的深度？
14、第25页二叉树的概念二叉树的概念定义：定义：二叉树是一种有序的树形结构。它与一般树形结构的区别是：n 每个结点最多有两棵子树；n 子树有左右之分，次序不能任意颠倒。称左子树和右子树二叉树的5种基本形态第26页树与二叉树的区别A树和二叉树的结点个数最少都可为0。 B树中结点的最大度数没有限制，二叉树结点最大度数为2。 C树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。3个结点的树3个结点的二叉树第27页二叉树的性质二叉树的性质【性质1】 在二叉树的第i层上最多有2i-1个结点（i1）A BCDFEHG121314158910114567123第28页【性质2】深度为h的二叉树最多有2h
15、 -1个结点（h 1）ABCDFEHG121314158910114567123第29页【性质3】二叉树上叶子结点数比度为2的结点数多1ABCDFEHG度为2的结点叶子结点第30页满二叉树和完全二叉树满二叉树和完全二叉树n n满二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。最后一层的结点均为0度。n n完全二叉树完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。则称这棵二叉树为完全二叉树。完全二叉树中度数为1的结点的个数为0或1。第31页121314158910114567123满二叉树完全二叉树12138910114567123第32页1213891011456123非完全二叉树深度为4的 完全二叉树84567123第33页【性质4】具有n个结点的完全二叉树的深度为 log2 (n+1) 其中，log2n 的结果是不大于log2n的最大整数1213141589101
