NCRE二级公共基础知识讲义.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《NCRE二级公共基础知识讲义.ppt》由会员分享,可在线阅读,更多相关《NCRE二级公共基础知识讲义.ppt(86页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、全全国国计计算算机机等等级级考考试试National Computer Rank Examination二级 公共基础知识全国计算机等级考试1全国计算机等级考试National Computer Rank Examination二二级级公公共共基基础础知知识识考考试试内内容容 数数 据据 结结 构构 和和 算算 法法 程程 序序 设设 计计 基基 础础 软软件件工工程程 数数 据据 库库 设设 计计 基基 础础全国计算机等级考试2全国计算机等级考试National Computer Rank Examination1 1、二级公共基础的考试方式为笔、二级公共基础的考试方式为笔 试,与各科语言的
2、笔试部分合试,与各科语言的笔试部分合 为一张试卷。公共基础部分占为一张试卷。公共基础部分占 全卷的全卷的3030分。分。2 2、公共基础知识有、公共基础知识有1010道选择题和道选择题和 5 5道填空题。道填空题。二二级级公公共共基基础础知知识识考考试试方方式式全国计算机等级考试3全国计算机等级考试National Computer Rank Examination理解基本概念理解基本概念多做练习多做练习适当记忆一些名词适当记忆一些名词与所学程序设计语言结合起来理解与所学程序设计语言结合起来理解二二级级公公共共基基础础知知识识学学习习方方法法全国计算机等级考试4第第 一一 章章 数数据据结结构
3、构和和算算法法全国计算机等级考试5全国计算机等级考试National Computer Rank Examination本章知识要点本章知识要点算法算法算法的定义算法的特征算法复杂度数据结构数据结构数据结构的定义逻辑结构 和 物理结构线性结构 和 非线性结构顺序表、链表、堆栈队列、循环队列、树算法的基本要素全国计算机等级考试6全国计算机等级考试National Computer Rank Examination算法是对特定问题求解步骤的一种描述。一、算法一、算法算法的特性:(1)有穷性:算法必须在有限的次数内完成。有穷性:算法必须在有限的次数内完成。(2)确定性:算法的每一步必须是明确的。确定
4、性:算法的每一步必须是明确的。(3)可行性:算法的每一步必须是可以实现的。可行性:算法的每一步必须是可以实现的。(4)拥有足够的情报:算法必须有一定的输入拥有足够的情报:算法必须有一定的输入和输出。输出。全国计算机等级考试7全国计算机等级考试National Computer Rank Examination算法的基本要素:(1)对数据对象的运算和操作运算和操作:A.算术运算 B.逻辑运算 C.关系运算 D.数据传输 (2)算法的控制结构控制结构:A.顺序结构 B.选择结构 C.循环结构全国计算机等级考试8全国计算机等级考试National Computer Rank Examination算
5、法的复杂度:衡量算法优劣的量。(1)时间复杂度:算法的时间耗费。A.算法中基本操作重复执行次数和算法执行时间 同步增长,称作算法的时间复杂度。B.算法中基本操作重复执行次数和问题规模有关,是问题规模的函数。C.算法的时间复杂度是指执行算法所需要的计算工 作量。(2)空间复杂度:执行算法所需要的内存空间。全国计算机等级考试9全国计算机等级考试National Computer Rank Examination二、数据结构二、数据结构数据结构主要研究两方面的问题:(1)数据本身。(2)数据之间的前后件关系。数据数据 结构结构数据本身数据本身数据本身数据本身数据之间的数据之间的数据之间的数据之间的前
6、后件关系前后件关系前后件关系前后件关系数据结构表示为:DS=D,S例:D=春,夏,秋,冬 S=(春,夏),(夏,秋),(秋,冬),(冬,春)全国计算机等级考试10全国计算机等级考试National Computer Rank Examination数据的结构分为:数据的结构分为:(1 1)物理结构物理结构:数据在计算机存储介质中真正存储的结构,:数据在计算机存储介质中真正存储的结构,也被称为也被称为“存储结构存储结构”(2 2)逻辑结构逻辑结构:人们所理解的数据之间的结构,可以用图示:人们所理解的数据之间的结构,可以用图示 的方法绘画出来的数据之间的结构。的方法绘画出来的数据之间的结构。例:一
7、个班由35名同学,他们的座位牌号就是物理结构,一次考试的排名是逻辑结构。1注意:逻辑结构和物理结构没有必然的联系,也不一定是注意:逻辑结构和物理结构没有必然的联系,也不一定是 一一对应的。一一对应的。全国计算机等级考试11全国计算机等级考试National Computer Rank Examination数据的结构分为:数据的结构分为:(1 1)线性结构线性结构:非空数据结构同时满足以下两个条件就是线性结构:非空数据结构同时满足以下两个条件就是线性结构:A.A.有且仅有一个根结点;有且仅有一个根结点;B.B.除头结点和尾结点外,任何结点有且仅有一个前件除头结点和尾结点外,任何结点有且仅有一个
8、前件 和一个后件。和一个后件。(2 2)非线性结构非线性结构:除了线性结构都是非线性结构。:除了线性结构都是非线性结构。全国计算机等级考试12全国计算机等级考试National Computer Rank Examination全国计算机等级考试二级公共基础知识要求掌握的数据结构共有以下六种:线性表 堆栈 队列 循环队列 线性链表 树和二叉树线性结构物理结构和逻辑结构相同相同相同相同物理结构和逻辑结构相同相同相同相同物理结构和逻辑结构相同相同相同相同物理结构和逻辑结构相同相同相同相同物理结构和逻辑结构不相同不相同不相同不相同物理结构和逻辑结构不相同不相同不相同不相同非线性结构全国计算机等级考试
9、13全国计算机等级考试National Computer Rank Examination10102020303040405050606070708080三、顺序表:顺序表就是数组三、顺序表:顺序表就是数组1、顺序表也叫做线性表,属于线性结构。线性表的逻辑结构和物理结构相同。2、特点:(1)有且仅有一个头结点(根节点)和尾结点。(2)任意其他结点至多有一个前件,一个后件。(3)头结点没有前件,尾结点没有后件。全国计算机等级考试14全国计算机等级考试National Computer Rank Examination四、堆栈四、堆栈栈顶top栈底入栈入栈/压入压入出栈出栈/弹出弹出1、定义:只允
10、许在栈顶位置插 入数据和删除数据的线性结 构是堆栈,简称为“栈”。2、堆栈属于线性结构。3、堆栈的逻辑结构和物理结构 相同。4、特点:先进后出,后进先出 所以堆栈也叫做先进后出表 (FILO)5、堆栈具备存储功能:函数的 递归调用和表达式求解都用 到了堆栈。全国计算机等级考试15全国计算机等级考试National Computer Rank Examination入栈顺序:a、b、c、d、e、f栈空abacbabadba.入a入b入c出c入d模拟堆栈的数据出入过程:全国计算机等级考试16全国计算机等级考试National Computer Rank Examination【典型题型】假设一个堆
11、栈,入栈顺序为abcde,认为在任何时 刻均允许出栈,下列选项中不可能的出栈顺序为:A)abcde(可能)B)edcba(可能)C)cdeba(可能)D)cdeab(不可能)如果进栈序列为如果进栈序列为e1,e2,e3,e4e1,e2,e3,e4,则可能的出栈序列是(,则可能的出栈序列是()A)e3,e1,e4,e2 A)e3,e1,e4,e2 B)e2,e4,e3,e1 B)e2,e4,e3,e1 C)e3,e4,e1,e2 C)e3,e4,e1,e2D)D)任意顺序任意顺序栈底至栈顶依次存放元素栈底至栈顶依次存放元素A A、B B、C C、D D,在第五个元素,在第五个元素E E入栈前,栈
12、中元素入栈前,栈中元素可以出栈,则出栈序列可能是(可以出栈,则出栈序列可能是()A)ABCED A)ABCED B)DCBEA B)DCBEA C)DBCEA C)DBCEA D)CDABE D)CDABE全国计算机等级考试17全国计算机等级考试National Computer Rank Examination五、队列五、队列队头front队尾rear入队入队出队出队1、队列属于线性结构。2、队列的逻辑结构和物理结构相同。3、定义:入队操作发生在队尾,出队操作发生在队头。4、特点:先进先出,后进后出,所以队列也叫做先进先 出表(FIFO)。全国计算机等级考试18全国计算机等级考试Nation
13、al Computer Rank Examination六、循环队列六、循环队列rearfront全国计算机等级考试19全国计算机等级考试National Computer Rank Examination入队顺序:a、b、c、d、e、f模拟循环队列的数据出入过程:模拟循环队列的数据出入过程:循环队列空front=rearrearfrontafrontrear数据a入队afrontrearb数据b入队frontrearb数据a出队全国计算机等级考试20全国计算机等级考试National Computer Rank Examination七、线性链表七、线性链表1、链表属于线性结构。2、链表的逻
14、辑结构和物理结构不相同。3、线性链表由结点组成:每个结点有两个区域:数据域,指针域。A.数据域,用来存储数据。B.指针域,用来指向下一个结点的位置。3、绘画一个由5个节点组成的线性链表,数据为1、2、3、4、5。链表的结点链表的结点数据域数据域指针域指针域1 12 23 34 45 5单链表单链表全国计算机等级考试21全国计算机等级考试National Computer Rank Examination链表的种类:单链表、循环链表、双向链表。1234512345循环链表双向链表 12345 全国计算机等级考试22全国计算机等级考试National Computer Rank Examinati
15、on八、树与二叉树八、树与二叉树1、树属于非线性结构。2、树的逻辑结构和物理结构不相同。3、树有且仅有一个根节点。根节点xeoqkbg全国计算机等级考试23全国计算机等级考试National Computer Rank Examination二叉树:每个结点最多分两叉的有序树。二叉树:每个结点最多分两叉的有序树。二叉树二叉树的术语有序树与无序树二叉树的五种基本结构满二叉树 和 完全二叉树二叉树的计算二叉树的遍历全国计算机等级考试24全国计算机等级考试National Computer Rank Examination1 1、二叉树的术语:、二叉树的术语:根节点xeoqbg叶子节点A.结点、根节
16、点、叶子节点:(1)构成树的基本结构是结点。(2)没有父结点的结点是根节点。(3)没有子结点的结点是叶子节点(度为0的结点)。B.结点的度:结点子结点的个数。C.树的度:树中度数最大的结点的度就是树的度。D.树的高度/层数:树有多少层。E.父结点、子结点、双亲结点、孩子结点、左孩子、右孩子、兄弟结点、堂兄结点。全国计算机等级考试25全国计算机等级考试National Computer Rank Examination2 2、有序树与无序树:、有序树与无序树:eABeBA二叉树和度为二的树的区别:A.二叉树是有序树,度为二的树是普通树,属于无序树。B.二叉树允许为空,度为二的数至少有三个结点。【
17、普通树不允许为空,至少有一个结点】全国计算机等级考试26全国计算机等级考试National Computer Rank Examination3 3、二叉树的五种基本结构:、二叉树的五种基本结构:aaabcbab空二叉树只有一个结点的二叉树有两个结点的二叉树有三个结点的二叉树全国计算机等级考试27全国计算机等级考试National Computer Rank Examination4 4、满二叉树和完全二叉树:、满二叉树和完全二叉树:A.满二叉树:二叉树的每一层均具备该层最大结点个数。(即:不具备度为1的结点)B.完全二叉树:满二叉树是一个特殊的完全二叉树。将所有结点 自上向下、自左向右编号,
18、结点编号连续而不缺失。xeoqkbgxeoqkb满二叉树完全二叉树123456全国计算机等级考试28全国计算机等级考试National Computer Rank Examination5 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,其右孩子为2n+1。xeoqkbg1
19、 12 23 34 45 56 67 7全国计算机等级考试29全国计算机等级考试National Computer Rank Examination填空题:填空题:设一棵完全二叉树共有700个结点,则在该二叉树中有 个叶子结点二叉树的结点共有三种:度为二叉树的结点共有三种:度为0 0的叶子结点、度为的叶子结点、度为1 1的结点和度为的结点和度为2 2的结点。的结点。设度为设度为0 0的叶子结点个数为的叶子结点个数为n0n0,度为,度为1 1的结点个数为的结点个数为n1n1,度为,度为2 2的结点个数为的结点个数为n2n2,则:,则:n0+n1+n2=700n0+n1+n2=700(1 1)根据
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NCRE 二级 公共 基础知识 讲义
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内