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