C语言二级公共基础知识讲义.ppt
《C语言二级公共基础知识讲义.ppt》由会员分享,可在线阅读,更多相关《C语言二级公共基础知识讲义.ppt(86页珍藏版)》请在课桌文档上搜索。
1、全国计算机等级考试,National Computer Rank Examination,二级 公共基础知识,全国计算机等级考试,2,考试内容,数据结构和算法 程序设计基础 软件工程 数据库设计基础,全国计算机等级考试,3,1、二级公共基础的考试方式为笔 试,与各科语言的笔试部分合 为一张试卷。公共基础部分占 全卷的30分。2、公共基础知识有10道选择题和 5道填空题。,考试方式,全国计算机等级考试,4,理解基本概念多做练习适当记忆一些名词与所学程序设计语言结合起来理解,学习方法,第一章 数据结构和算法,全国计算机等级考试,6,本章知识要点,算法,算法的定义,算法的特征,算法复杂度,数据结构,
2、数据结构的定义,逻辑结构 和 物理结构,线性结构 和 非线性结构,顺序表、链表、堆栈队列、循环队列、树,算法的基本要素,全国计算机等级考试,7,算法是对特定问题求解步骤的一种描述。,一、算法,算法的特性:(1)有穷性:算法必须在有限的次数内完成。(2)确定性:算法的每一步必须是明确的。(3)可行性:算法的每一步必须是可以实现的。(4)拥有足够的情报:算法必须有一定的输入和输出。,全国计算机等级考试,8,算法的基本要素:(1)对数据对象的运算和操作:A.算术运算 B.逻辑运算 C.关系运算 D.数据传输(2)算法的控制结构:A.顺序结构 B.选择结构 C.循环结构,全国计算机等级考试,9,算法的
3、复杂度:衡量算法优劣的量。(1)时间复杂度:算法的时间耗费。A.算法中基本操作重复执行次数和算法执行时间 同步增长,称作算法的时间复杂度。B.算法中基本操作重复执行次数和问题规模有关,是问题规模的函数。C.算法的时间复杂度是指执行算法所需要的计算工 作量。(2)空间复杂度:执行算法所需要的内存空间。,全国计算机等级考试,10,二、数据结构,数据结构主要研究两方面的问题:(1)数据本身。(2)数据之间的前后件关系。,数据结构表示为:DS=D,S例:D=春,夏,秋,冬 S=(春,夏),(夏,秋),(秋,冬),(冬,春),全国计算机等级考试,11,数据的结构分为:(1)物理结构:数据在计算机存储介质
4、中真正存储的结构,也被称为“存储结构”(2)逻辑结构:人们所理解的数据之间的结构,可以用图示 的方法绘画出来的数据之间的结构。,例:一个班由35名同学,他们的座位牌号就是物理结构,一次考试的排名是逻辑结构。1,注意:逻辑结构和物理结构没有必然的联系,也不一定是 一一对应的。,全国计算机等级考试,12,数据的结构分为:(1)线性结构:非空数据结构同时满足以下两个条件就是线性结构:A.有且仅有一个根结点;B.除头结点和尾结点外,任何结点有且仅有一个前件 和一个后件。(2)非线性结构:除了线性结构都是非线性结构。,全国计算机等级考试,13,全国计算机等级考试要求掌握的数据结构共有以下六种:,线性表
5、堆栈 队列 循环队列 线性链表 树和二叉树,线性结构,物理结构和逻辑结构相同,物理结构和逻辑结构相同,物理结构和逻辑结构相同,物理结构和逻辑结构相同,物理结构和逻辑结构不相同,物理结构和逻辑结构不相同,非线性结构,全国计算机等级考试,14,10,20,30,40,50,60,70,80,三、顺序表:顺序表就是数组,1、顺序表也叫做线性表,属于线性结构。线性表的逻辑结构和物理结构相同。2、特点:(1)有且仅有一个头结点(根节点)和尾结点。(2)任意其他结点至多有一个前件,一个后件。(3)头结点没有前件,尾结点没有后件。,全国计算机等级考试,15,四、堆栈,1、定义:只允许在栈顶位置插 入数据和删
6、除数据的线性结 构是堆栈,简称为“栈”。2、堆栈属于线性结构。3、堆栈的逻辑结构和物理结构 相同。4、特点:先进后出,后进先出 所以堆栈也叫做先进后出表(FILO)5、堆栈具备存储功能:函数的 递归调用和表达式求解都用 到了堆栈。,全国计算机等级考试,16,入栈顺序:a、b、c、d、e、f,栈空,a,b,a,c,b,a,b,a,d,b,a,.,入a,入b,入c,出c,入d,模拟堆栈的数据出入过程:,全国计算机等级考试,17,【典型题型】假设一个堆栈,入栈顺序为abcde,认为在任何时 刻均允许出栈,下列选项中不可能的出栈顺序为:A)abcde(可能)B)edcba(可能)C)cdeba(可能)
7、D)cdeab(不可能),如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是()A)e3,e1,e4,e2 B)e2,e4,e3,e1 C)e3,e4,e1,e2D)任意顺序,栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是()A)ABCED B)DCBEA C)DBCEA D)CDABE,全国计算机等级考试,18,五、队列,1、队列属于线性结构。2、队列的逻辑结构和物理结构相同。3、定义:入队操作发生在队尾,出队操作发生在队头。4、特点:先进先出,后进后出,所以队列也叫做先进先 出表(FIFO)。,全国计算机等级考试,19,六、循环队列,r
8、ear,front,全国计算机等级考试,20,入队顺序:a、b、c、d、e、f,模拟循环队列的数据出入过程:,循环队列空front=rear,rear,front,a,front,rear,数据a入队,a,front,rear,b,数据b入队,front,rear,b,数据a出队,全国计算机等级考试,21,七、线性链表,1、链表属于线性结构。2、链表的逻辑结构和物理结构不相同。3、线性链表由结点组成:每个结点有两个区域:数据域,指针域。A.数据域,用来存储数据。B.指针域,用来指向下一个结点的位置。3、绘画一个由5个节点组成的线性链表,数据为1、2、3、4、5。,全国计算机等级考试,22,链表
9、的种类:单链表、循环链表、双向链表。,1,2,3,4,5,1,2,3,4,5,循环链表,双向链表,1,2,3,4,5,全国计算机等级考试,23,八、树与二叉树,1、树属于非线性结构。2、树的逻辑结构和物理结构不相同。3、树有且仅有一个根节点。,根节点,x,e,o,q,k,b,g,全国计算机等级考试,24,二叉树:每个结点最多分两叉的有序树。,二叉树,二叉树的术语,有序树与无序树,二叉树的五种基本结构,满二叉树 和 完全二叉树,二叉树的计算,二叉树的遍历,全国计算机等级考试,25,1、二叉树的术语:,A.结点、根节点、叶子节点:(1)构成树的基本结构是结点。(2)没有父结点的结点是根节点。(3)
10、没有子结点的结点是叶子节点(度为0的结点)。B.结点的度:结点子结点的个数。C.树的度:树中度数最大的结点的度就是树的度。D.树的高度/层数:树有多少层。E.父结点、子结点、双亲结点、孩子结点、左孩子、右孩子、兄弟结点、堂兄结点。,全国计算机等级考试,26,2、有序树与无序树:,e,A,B,e,B,A,二叉树和度为二的树的区别:A.二叉树是有序树,度为二的树是普通树,属于无序树。B.二叉树允许为空,度为二的数至少有三个结点。【普通树不允许为空,至少有一个结点】,全国计算机等级考试,27,3、二叉树的五种基本结构:,全国计算机等级考试,28,4、满二叉树和完全二叉树:,A.满二叉树:二叉树的每一
11、层均具备该层最大结点个数。(即:不具备度为1的结点)B.完全二叉树:满二叉树是一个特殊的完全二叉树。将所有结点 自上向下、自左向右编号,结点编号连续而不缺失。,满二叉树,完全二叉树,1,2,3,4,5,6,全国计算机等级考试,29,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,其右孩子
12、为2n+1。,全国计算机等级考试,30,填空题:设一棵完全二叉树共有700个结点,则在该二叉树中有 个叶子结点,二叉树的结点共有三种:度为0的叶子结点、度为1的结点和度为2的结点。设度为0的叶子结点个数为n0,度为1的结点个数为n1,度为2的结点个数为n2,则:n0+n1+n2=700(1)根据二叉树性质:叶子结点个数比度为2的结点个数多1,即:n0=n2+1(2)将(2)式带入(1)式,所以:n0+n1+n0-1=700 2n0=701-n1 完全二叉树总结点个数为偶数,则度为1的结点个数为1;完全二叉树的总结点个数为奇数,则度为1的结点个数为0。所以:2n0=701-1,即 n0=350。
13、,全国计算机等级考试,31,6、二叉树的遍历:,A.前/先(根)序遍历,GLR。【根节点为序列开头】B.中(根)序遍历,LGR。【没有左子树,根节点为开头;没有右子树,根节点为结尾】【左右子树均有,根节点的位置位于左子树结点个数之和+1】C.后(根)序遍历,LRG。【根节点为序列结尾】,先序序列:xeqbog,中序序列:qebxog,后序序列:qbegox,第二章 程序设计基础,全国计算机等级考试,33,本章知识要点,面向过程的程序设计,结构化程序设计,模块化程序设计,面向对象的程序设计,对象的定义,对象的属性和方法,类和实例的派生与继承,消息与多态性,全国计算机等级考试,34,一、程序设计方
14、法,1、面向过程的程序设计:C语言、BASIC语言等。(1)结构化程序设计:顺序、选择、循环。三大结构(顺序、选择、循环)可以解决所有的问题,和 问题的规模没有关系。(2)模块化程序设计:利用将程序分解的方法,将复杂的问题 简单化,将单一的问题分成多个模块独立解决。C语言:模块就是函数。VB语言:模块就是模块、子例程、子程序。VFP数据库:模块就是子程序。Access数据库:模块就是宏、事件代码。2、面向对象的程序设计:VB、VFP、Java、Delphi等。,全国计算机等级考试,35,二、程序设计风格,1.源程序文档化 选择标示符的名字 注释(序言性和功能性注释)程序的视觉组织2.数据说明的
15、方法 显式地说明一切变量 数据说明的次序应该规范化 说明语句中变量安排有序化 对复杂数据结构应注释说明,3.语句的结构 每条语句简单明了 尽量不用或少用GOTO语句 尽量只采用3种基本控制结构编程4.输入和输出 对输入数据进行校验和合理性检查 输入输出格式保持一致 设计良好的输出报表,全国计算机等级考试,36,三、结构化程序设计,20世纪70年代提出了结构化程序设计(Structured Programming),结构化程序设计的原则:(1)自顶向下。(2)逐步求精。(3)模块化。(4)限制使用goto语句。,结构化程序设计的基本结构:(1)顺序结构。(2)选择结构。(3)重复结构。,结构化程
16、序设计主要强调程序的易读性。,全国计算机等级考试,37,利用图示表示顺序结构,程序流程图,N-S图,全国计算机等级考试,38,利用图示表示选择结构,程序流程图,N-S图,全国计算机等级考试,39,利用图示表示重复结构(1),程序流程图当型循环,程序流程图直到型循环,全国计算机等级考试,40,利用图示表示重复结构(2),S,UNTIL 条件,N-S图当型循环,N-S图直到型循环,全国计算机等级考试,41,三、面向对象的程序设计,面向对象(Object Oriented)的程序设计方法已经发展成为主流的软件开发方法,起源于对面向对象语言的研究。20世纪60年代后期首次被提出,80年代开始走向实用。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 二级 公共 基础知识 讲义
链接地址:https://www.desk33.com/p-263972.html