C语言二级公共基础知识讲义.ppt
全国计算机等级考试全国计算机等级考试National Computer Rank Examination二级 公共基础知识全国计算机等级考试National Computer Rank Examination全国计算机等级考试2考试内容考试内容 数 据 结 构 和 算 法数 据 结 构 和 算 法 程 序 设 计 基 础程 序 设 计 基 础 软件工程软件工程 数 据 库 设 计 基 础数 据 库 设 计 基 础全国计算机等级考试National Computer Rank Examination全国计算机等级考试31 1、二级公共基础的考试方式为笔、二级公共基础的考试方式为笔 试，与各科语言的笔试部分合试，与各科语言的笔试部分合 为一张试卷。公共基础部分占为一张试卷。公共基础部分占 全卷的全卷的3030分。分。2 2、公共基础知识有、公共基础知识有1010道选择题和道选择题和 5 5道填空题。道填空题。 考试方式考试方式全国计算机等级考试National Computer Rank Examination全国计算机等级考试4 理解基本概念理解基本概念 多做练习多做练习 适当记忆一些名词适当记忆一些名词 与所学程序设计语言结合起来理解与所学程序设计语言结合起来理解学习方法学习方法第一章第一章 数据结构和算法数据结构和算法全国计算机等级考试National Computer Rank Examination全国计算机等级考试6本章知识要点本章知识要点算法算法算法的定义算法的特征算法复杂度数据结构数据结构数据结构的定义逻辑结构 和 物理结构线性结构 和 非线性结构顺序表、链表、堆栈队列、循环队列、树算法的基本要素全国计算机等级考试National Computer Rank Examination全国计算机等级考试7算法是对特定问题求解步骤的一种描述。一、算法一、算法算法的特性： （1）有穷性：算法必须在有限的次数内完成。有穷性：算法必须在有限的次数内完成。 （2）确定性：算法的每一步必须是明确的。确定性：算法的每一步必须是明确的。 （3）可行性：算法的每一步必须是可以实现的。可行性：算法的每一步必须是可以实现的。 （4）拥有足够的情报：算法必须有一定的输入拥有足够的情报：算法必须有一定的输入和输出。输出。全国计算机等级考试National Computer Rank Examination全国计算机等级考试8算法的基本要素： （1）对数据对象的运算和操作运算和操作： A .算术运算 B .逻辑运算 C .关系运算 D .数据传输 （2）算法的控制结构控制结构： A .顺序结构 B .选择结构 C .循环结构全国计算机等级考试National Computer Rank Examination全国计算机等级考试9算法的复杂度：衡量算法优劣的量。 （1）时间复杂度：算法的时间耗费。 A .算法中基本操作重复执行次数和算法执行时间 同步增长，称作算法的时间复杂度。 B .算法中基本操作重复执行次数和问题规模有关， 是问题规模的函数。 C .算法的时间复杂度是指执行算法所需要的计算工 作量。 （2）空间复杂度：执行算法所需要的内存空间。全国计算机等级考试National Computer Rank Examination全国计算机等级考试10二、数据结构二、数据结构数据结构主要研究两方面的问题： （1）数据本身。 （2）数据之间的前后件关系。数据数据 结构结构数据结构表示为：DS=D，S例：D=春，夏，秋，冬 S=(春,夏)，(夏,秋)，(秋,冬)，(冬,春)全国计算机等级考试National Computer Rank Examination全国计算机等级考试11数据的结构分为：数据的结构分为： （1 1）物理结构物理结构：数据在计算机存储介质中真正存储的结构，：数据在计算机存储介质中真正存储的结构， 也被称为也被称为“存储结构存储结构” （2 2）逻辑结构逻辑结构：人们所理解的数据之间的结构，可以用图示：人们所理解的数据之间的结构，可以用图示 的方法绘画出来的数据之间的结构。的方法绘画出来的数据之间的结构。例：一个班由35名同学，他们的座位牌号就是物理结构， 一次考试的排名是逻辑结构。1注意：逻辑结构和物理结构没有必然的联系，也不一定是注意：逻辑结构和物理结构没有必然的联系，也不一定是 一一对应的。一一对应的。全国计算机等级考试National Computer Rank Examination全国计算机等级考试12数据的结构分为：数据的结构分为： （1 1）线性结构线性结构： 非空数据结构同时满足以下两个条件就是线性结构：非空数据结构同时满足以下两个条件就是线性结构： A .A .有且仅有一个根结点；有且仅有一个根结点； B .B .除头结点和尾结点外，任何结点有且仅有一个前件除头结点和尾结点外，任何结点有且仅有一个前件 和一个后件。和一个后件。 （2 2）非线性结构非线性结构：除了线性结构都是非线性结构。：除了线性结构都是非线性结构。全国计算机等级考试National Computer Rank Examination全国计算机等级考试13全国计算机等级考试要求掌握的数据结构共有以下六种： 线性表 堆栈 队列 循环队列 线性链表 树和二叉树线性结构物理结构和逻辑结构物理结构和逻辑结构物理结构和逻辑结构物理结构和逻辑结构物理结构和逻辑结构物理结构和逻辑结构非线性结构全国计算机等级考试National Computer Rank Examination全国计算机等级考试1410102020303040405050606070708080三、顺序表：顺序表就是数组三、顺序表：顺序表就是数组1、顺序表也叫做线性表，属于线性结构。 线性表的逻辑结构和物理结构相同。2、特点： （1）有且仅有一个头结点（根节点）和尾结点。 （2）任意其他结点至多有一个前件，一个后件。 （3）头结点没有前件，尾结点没有后件。全国计算机等级考试National Computer Rank Examination全国计算机等级考试15四、堆栈四、堆栈栈顶top栈底入栈入栈 / 压入压入出栈出栈 / 弹出弹出1、定义：只允许在栈顶位置插 入数据和删除数据的线性结 构是堆栈，简称为“栈”。2、堆栈属于线性结构。3、堆栈的逻辑结构和物理结构 相同。4、特点：先进后出，后进先出 所以堆栈也叫做先进后出表 （FILO）5、堆栈具备存储功能：函数的 递归调用和表达式求解都用 到了堆栈。全国计算机等级考试National Computer Rank Examination全国计算机等级考试16入栈顺序：a、b、c、d、e、f栈空abacbabadba.入a入b入c出c入d模拟堆栈的数据出入过程：全国计算机等级考试National Computer Rank Examination全国计算机等级考试17【典型题型】假设一个堆栈，入栈顺序为abcde，认为在任何时 刻均允许出栈，下列选项中不可能的出栈顺序为： A）abcde（可能） B）edcba（可能） C）cdeba（可能） D）cdeab（不可能）全国计算机等级考试National Computer Rank Examination全国计算机等级考试18五、队列五、队列队头front队尾rear入队入队出队出队1、队列属于线性结构。2、队列的逻辑结构和物理结构相同。3、定义：入队操作发生在队尾，出队操作发生在队头。4、特点：先进先出，后进后出，所以队列也叫做先进先 出表（FIFO）。全国计算机等级考试National Computer Rank Examination全国计算机等级考试19六、循环队列六、循环队列rearfront全国计算机等级考试National Computer Rank Examination全国计算机等级考试20入队顺序：a、b、c、d、e、f模拟循环队列的数据出入过程：模拟循环队列的数据出入过程：循环队列空front=rearrearfrontafrontrear数据a入队afrontrearb数据b入队frontrearb数据a出队全国计算机等级考试National Computer Rank Examination全国计算机等级考试21七、线性链表七、线性链表1、链表属于线性结构。2、链表的逻辑结构和物理结构不相同。3、线性链表由结点组成： 每个结点有两个区域：数据域，指针域。 A .数据域，用来存储数据。 B .指针域，用来指向下一个结点的位置。3、绘画一个由5个节点组成的线性链表，数据为1、2、3、4、5。链表的结点链表的结点数据域数据域指针域指针域1 12 23 34 45 5单链表单链表全国计算机等级考试National Computer Rank Examination全国计算机等级考试22链表的种类：单链表、循环链表、双向链表。 1234512345循环链表双向链表 12345 全国计算机等级考试National Computer Rank Examination全国计算机等级考试23八、树与二叉树八、树与二叉树1、树属于非线性结构。2、树的逻辑结构和物理结构不相同。3、树有且仅有一个根节点。根节点xeoqkbg全国计算机等级考试National Computer Rank Examination全国计算机等级考试24二叉树：每个结点最多分两叉的有序树。二叉树：每个结点最多分两叉的有序树。二叉树二叉树的术语有序树与无序树二叉树的五种基本结构满二叉树 和 完全二叉树二叉树的计算二叉树的遍历全国计算机等级考试National Computer Rank Examination全国计算机等级考试251 1、二叉树的术语：、二叉树的术语：根节点xeoqbg叶子节点A .结点、根节点、叶子节点： （1）构成树的基本结构是结点。 （2）没有父结点的结点是根节点。 （3）没有子结点的结点是叶子节点（度为0的结点）。B .结点的度：结点子结点的个数。C .树的度：树中度数最大的结点的度就是树的度。D .树的高度/层数：树有多少层。E .父结点、子结点、双亲结点、孩子结点、 左孩子、右孩子、兄弟结点、堂兄结点。全国计算机等级考试National Computer Rank Examination全国计算机等级考试262 2、有序树与无序树：、有序树与无序树：eABeBA二叉树和度为二的树的区别： A .二叉树是有序树，度为二的树是普通树，属于无序树。 B .二叉树允许为空，度为二的数至少有三个结点。 【普通树不允许为空，至少有一个结点】全国计算机等级考试National Computer Rank Examination全国计算机等级考试273 3、二叉树的五种基本结构：、二叉树的五种基本结构： aaabcbab空二叉树只有一个结点的二叉树有两个结点的二叉树有三个结点的二叉树全国计算机等级考试National Computer Rank Examination全国计算机等级考试284 4、满二叉树和完全二叉树：、满二叉树和完全二叉树： A .满二叉树：二叉树的每一层均具备该层最大结点个数。 （即：不具备度为1的结点）B .完全二叉树：满二叉树是一个特殊的完全二叉树。将所有结点 自上向下、自左向右编号，结点编号连续而不缺失。xeoqkbgxeoqkb满二叉树完全二叉树123456全国计算机等级考试National Computer Rank Examination全国计算机等级考试295 5、二叉树的计算：、二叉树的计算： A .二叉树第n层的最大结点个数：2n-1。B .n层满二叉树的结点个数：2n-1。C .n层完全二叉树的最小结点个数：2n-1。 n层完全二叉树的最大结点个数：2n-1。D .度为0的结点个数表示为n0，同理，n1表示度为1的结点个数， n2表示度为2的结点个数。 则，对于任意二叉树都有：n0=n2+1。E .结点编号：任意结点编号n，其左孩子为2n，其右孩子为2
