没有合适的资源?快使用搜索试试~ 我知道了~
全国计算机二级C语言(完整复习资料) .doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 113 浏览量
2021-10-11
11:59:40
上传
评论
收藏 160KB DOC 举报
温馨提示
试读
22页
全国计算机二级C语言(完整复习资料) .doc
资源推荐
资源详情
资源评论
计算机二级 C 复习资料
公共基础知识资料
第一章 数据结构与算法
【考点 1】算法的基本概念
算法:是指一组有穷的指令集,是解题方案的准确而完整的描述。算法不等于程序,也不
等于计算方法。
算法的基本特征:
确定性,算法中每一步骤都必须有明确定义,不允许有多义性;
有穷性 ,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止;
可行性,算法原则上能够精确地执行;
拥有足够的情报。
算法的组成要素:一个算法由数据对象的运算和操作以及其控制结构这两部分组成。
算法的基本运算和操作:算术运算,逻辑运算,关系运算,数据传输。
算法的基本控制结构:顺序,选择,循环。
算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术。
【考点 2】算法的复杂度
算法效率的度量——算法的复杂度:时间复杂度和空间复杂度。
算法时间复杂度: 指执行算法所需要的计算工作量 。通常,一个算法所用的时间包括 编译
时间和运行时间。
算法空间复杂度: 指执行这个算法所需要的内存空间 。包括算法程序所占的空间,输入的
初始数据所占的空间,算法执行过程中所需的额外空间。
空间复杂度和时间复杂度 并不相关。
【考点 3】数据结构的基本概念
数据:数据是客观事物的符号表示,是能输入到计算机中并被计算程序识别和处理的符号
的总称,如文档,声音,视频等。
数据元素:数据元素是数据的基本单位。
数据对象:数据对象是性质相同的数据元素的集合。
数据结构:是指由某一数据对象中所有数据成员之间的关系组成的集合。
【考点 4】逻辑结构和存储结构
数据结构可分为数据的逻辑结构和存储结构。
数据的逻辑结构是对数据元素之间的逻辑关系的描述,与数据的存储无关,是面向问题的,
是独立于计算机的。它包括数据对象和数据对象之间的关系。
数据的存储结构也称为数据的物理结构,是数据在计算机中的存放的方式,是面向计算机
的,它包括数据元素的存储方式和关系的存储方式。
数据结构和逻辑结构的关系:一种数据的逻辑结构可以表示成多种存储结构即数据的逻辑
结构和存储结构不一定一一对应。
常见的存储结构有:顺序,链接,索引等。采用不同的存储结构其数据处理的效率是不同
的。
【考点 5】线性结构和非线性结构
1
线性结构的条件(一个非空数据结构):( 1)有且只有一个根结点;(2)每一个结点最
多有一个前件,也最多有一个后件。
非线性结构:不满足线性结构条件的数据结构。
栈、队列、双向链表是线性结构,树、二叉树为非线性结构。
【考点 6】线性表及其顺序存储结构
线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位
置是线性的。
在复杂线性表中,由若干项数据元素组成的数据元素称为记录;由多个记录构成的线性表
称为文件。
非空线性表的结构特征:
(1)有且只有一个根结点 a1,它无前件;
(2)有且只有一个终端结点 an,它无后件;
(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。
结点个数 n 称为线性表的长度,当 n=0 时,称为空表。
线性表的顺序存储结构具有以下两个基本特点:
( 1 ) 线性表中所有元素所占的存储空间是连续的;
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
元素 ai 的存储地址为:ADR(ai)=ADR(a1)+(i-1)*k,ADR(a1)为第一个元素的地址,k 代表
每个元素占的字节数。
顺序表的运算:
查找、插入、删除。
【考点 7】线性链表
线性链表是线性表的链式存储结构,数据结构中的每一个结点对应于一个存储单元,这种
存储单元称为存储结点,简称结点。结点由两部分组成:(1) 用于存储数据元素值,称为数
据域;(2) 用于存放指针,称为指针域,用于指向前一个或后一个结点。
在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据
元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式既可用于表示线性结构,也可用于表示非线性结构。
线性单链表中,HEAD 称为头指针,HEAD=NULL(或 0)称为空表。
双向链表有两个指针:左指针(Llink)指向前件结点,右指针(Rlink)指向后件结点。
循环链表:循环链表与单链表的不同的是它的最后一个结点的指针域存放的事指向第一个
结点的指针而单链表存放的是空指针。
图 1 单链表的结构
单链表的结构(图 1 )
……
数据域 指针域 数据域 指针域 数据域 指针域
……
L D R
……
图 2 双链表的结构
L D R L D R
……
图 3 循环链表的结构
2
线性链表的基本运算:查找、插入、删除。
【考点 8】栈
1、栈的基本概念
栈是一种特殊的线性表,只允许在表的一端进行插入和删除的线性表;插入,删除的一端
为栈顶,另一端为栈底;当表中没有元素时为空栈。
栈是一种后进先出(或先进后出
Last In First Out )的线性表。 栈具有记忆功能。栈的实例:
火车调度,子弹夹。
2、栈的存储结构
顺序存储结构:用一组地址连续的存储单元即一维数组来存储;
链式存储:用线性链表来存储;
3、栈的基本运算
(1) 入栈运算,在栈顶位置插入元素;
(2) 退栈运算,删除元素(取出栈顶元素并赋给一个指定的变量);
(3) 读栈顶元素,将栈顶元素赋给一个指定的变量,此时指针无变化。
【考点 9】队列
1.队列的基本概念
队列是一种特殊的线性表,只允许在表的一端插入,在另一端删除,允许插入的一端是队
尾(rear),允许删除的一端为队头( front);当表中没有元素是空队列; 队列是一种先
进先出的线性表。 (FIFO)
2、队列的存储结构
顺序存储:一维数组。
链式存储:线性链表。
3、队列的运算:
(1) 入队运算:从队尾插入一个元素; (2) 退队运算:从队头删除一个元素。
队列的顺序存储结构一般采用循环队列的形式。循环队列
s=0
表示队列为空; s=1
且
front=rear
表示队满。
计算循环队列的元素个数:“尾指针减头指针”,若为负数,再加其容量即可。
【考点 10】树的基本概念
树是一种非线性结构,是 n 个结点的有限集。当 n=0 时为空树,n>0 时为非空树。结点的
度:结点所拥有的子树的个数。
叶子结点:度为 0 的结点。
分支结点:除叶子结点以外的结点。
结点的层次:根结点在第一层,同一层上左右结点的子结点在下一层。
树的深度:所处层次最大的那个结点的层次。
树的度:树中所有结点的度的最大值。
【考点 11】二叉树及其基本性质
1、二叉树的概念
二叉树是一种特殊的树形结构,每个结点最多只有两棵子树,且有左右之分不能互换,因
此,二叉树有五种不同的形态,见教材 12 页。
2、二叉树的性质
性质
1 在二叉树的第
k
层上,最多有
2
k-1
(k ≥ 1 )个结点。
性质
2 深度为
m
的二叉树最多有
2
m
-1
个结点。
性质
3 在任意一棵二叉树中,度为
0
的结点(叶子结点)总是比度为
2
的结点多一个。
性质 4 具有 n 个结点的二叉树,其深度不小于[log
2
n]+1,其中[log
2
n]表示为 log
2
n 的整数部分。
3
3、二叉树的存储结构:详见教材第 13-14 页。
【考点 12】满二叉树与完全二叉树
满二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层
上的结点数都达到最大值,即在满二叉树的第 k 层上有 2
k-1
个结点,且深度为 m 的满二叉
树有 2
m
-1 个结点。
完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后
一层上只缺少右边的若干结点。
满二叉树是完全二叉树,而完全二叉树一般不是满二叉树。
【考点 13】完全二叉树的性质
性质 1 具有 n 个结点的完全二叉树的深度为[log
2
n]+1
。
性质 2 完全二叉树中度为 1 的结点数为 0 或 1。
【考点 14】二叉树的遍历
前序遍历:先访问根结点、然后遍历左子树,最后遍
历右子树;并且,在遍历左、右子树时,仍然先访问
根结点,然后遍历左子树,最后遍历右子树。
前序遍历图 5 可得:ABCDFHEG。
中序遍历:先遍历左子树、然后访问根结点,最后遍
历右子树;并且,在遍历左、右子树时,仍然先遍历
左子树,然后访问根结点,最后遍历右子树。
中序遍历图 5 可得:BAFHDCGE。
后序遍历:先遍历左子树、然后遍历右子树,最后访
问根结点;并且,在遍历左、右子树时,仍然先遍历
左子树,然后遍历右子树,最后访问根结点。
后序遍历图 5 可得:BHFDGECA。
【考点 15】顺序查找
顺序查找是从表的一端开始,依次扫描表中的各个元素,并与所要查找的数进行比较。
在下列两种情况下也只能采用顺序查找:
(1)如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,只能用顺序查找。
(2)即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。
【考点 16】二分查找
二分查找的条件:( 1 )用顺序存储结构 (2) 线性表是有序表。
查找的步骤:详见教材第 16 页。
对于长度为
n
的有序线性表,在最坏情况下,二分法查找只需比较
log
2
n
次,而顺序查找需
要比较
n
次。
【考点 17】排序
1 、交换排序
( 1 )冒泡排序法,在最坏的情况下,冒泡排序需要比较次数为
n(n - 1)/2 。
( 2 )快速排序法 ,在最坏的情况下,快速排序需要比较次数为
n(n - 1)/2 。
2 、插入类排序法:
( 1 )简单插入排序法,最坏情况需要
n(n-1)/2
次比较;
( 2 )希尔排序法,最坏情况需要
O(n
1.5
) 次比较。(大写
O
是算法复杂度的表示方法)
3 、选择类排序法:
4
A
B C
E
D
GF
H
图 4 二叉树的遍历
( 1 )简单选择排序法,最坏情况需要
n(n-1)/2
次比较;
( 2 )堆排序法,最坏情况需要
O(nlog
2
n) 次比较。
相比以上几种 ( 除希尔排序法外 ) ,堆排序法的时间复杂度最小。
第二章 程序设计基础
【考点 1】程序设计方法与风格
形成良好的程序设计风格需注意: ( 详见教材第
19
页 ) 。
1 、源程序文档化; 2 、数据说明的方法; 3 、语句的结构; 4 、输入和输出。
注释分序言性注释和功能性注释。
语句结构清晰第一、效率第二。
【考点 2】结构化程序设计方法的四条原则
1 、自顶向下; 2 、逐步求精; 3 、模块化; 4 、限制使用
goto
语句。
【考点 3】结构化程序的基本结构
顺序结构:是最基本、最普通的结构形式,按照程序中的语句行的先后顺序逐条执行。
选择结构:又称为分支结构,它包括简单选择和多分支选择结构。
循环结构:根据给定的条件,判断是否要重复执行某一相同的或类似的程序段。循环结构
对应两类循环语句:先判断后执行的循环体称为当型循环结构;先执行循环体后判断的称
为直到型循环结构。
【考点 4】面向对象的程序设计及面向对象方法的优点
面向对象的程序设计以对象为核心,强调对象的抽象性,封装性,继承性和多态性。
面向对象方法的优点
(1)人类习惯的思维方法一致; (2)稳定性好; (3)可重用性好;
(4)易于开发大型软件产品; (5)可维护性好。
【考点 5】对象及其特点
对象(object):面向对象方法中最基本的概念,可以用来表示客观世界中的任何实体,对
象是实体的抽象。
对象的基本特点:
( 1 )标识惟一性; ( 2 )分类性; ( 3 )多态性; ( 4 )封装性; ( 5 )模块独立性好。
【考点 6】属性,类和实例
属性:即对象所包含的信息,它在设计对象时确定,一般只能通过执行对象的操作来改变。
类:是具有相似属性与操作的一组对象。类是关于对象性质的描述。类是对象的抽象,对
象是其对应类的一个实例。
【考点 7】消息及其组成
消息:是一个实例与另一个实例之间传递的信息。对象间的通信靠消息传递。它请求对象
执行某一处理或回答某一要求的信息,它统一了数据流和控制流。
消息的组成包括:
(1)接收消息的对象的名称; (2)消息标识符,也称消息名; (3)零个或多个参数。
【考点 8】继承和多态
继承:是使用已有的类定义作为基础建立新类的定义技术,广义指能够直接获得已有的性
质和特征,而不必重复定义他们。
继承具有传递性,一个类实际上继承了它上层的全部基类的特性。
继承分单继承和多重继承。单继承指一个类只允许有一个父类,即类等级为树形结构;多
重继承指一个类允许有多个父类。
多态性:是指同样的消息被不同的对象接受时可导致完全不同的行动的现象
5
剩余21页未读,继续阅读
资源评论
hualuodiewu
- 粉丝: 0
- 资源: 5万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功