全国计算机级别考试—公共基本知识某些复习简纲
在二级考试中公共基本知识占30%,考察题型选取填空,下面我就结合几年考试原题,小结一下这一某些考点。
第一章 数据构造与算法
本章应考重点:本章内容在二级笔试中会浮现5—6题,是公共基本知识某些出题量比较多一章,所占分值也比较大,约10分
1.1 算法
算法是指解题方案精确而完整描述。
算法基本特性
a可行性b拟定性c有穷性d拥有足够情报
算法复杂度
a算法时间复杂度:是指执行算法所需要计算工作量,可以用执行算法过程中所需基本运算执行次数来度量
b 算法空间复杂度是指执行这个算法所需要内存空间。
1.2 数据构造基本概念
1 数据构造是指互有关于联数据元素集合
2 数据构造 a 数据逻辑构造 1表达数据元素信息 2 表达各数据元素之间先后件关系
b 数据存储构造 顺序存储
链接存储
索引存储
c 对各种数据构造进行运算
3数据构造图形表达
一种数据构造除了用二元关系外,还可以直观地用图形表达。在数据构造图形表达中,对于数据集合点D中每一种数据元素用中间标有元素值方框表达,普通称之为数据结点,并简称结点:为了进以步表达数据元素之间先后件关系,对于关系R中每一种二元组,用一条有向线段从前件结点指向后件结点。
4 数据构造分为二大类 线性构造 a有且只有一种根结点b 每个结点最多有一种前件,也最多有一种后件
常用线性构造有线性表,队列,线性链表,栈
非线性构造 不满足线性构造条件数据构造
常用非线性构造有树,二叉树,和图等
1.3线性表及其顺序存储构造
1线性表由一组数据元素构成,数据元素位置只取决于自己序号,元素之间相对位置是线性。表中每个数据元素,除了第一种外,由且只有一种前件,除了最后一种外,有且只有一种后件。线性表中数据元素个数称为线性表长度。线性表可以是空表
2线性表是一种存储构造 顺序构造 a线性表中所有元素所占存储空间是持续
b线性表中个数据元素在存储空间中是按逻辑顺序依次存储
链式构造
3顺序表插入,删除运算
a 顺序表插入运算,插入结束后,线性表长度增长了1,顺序表插入运算时需要移动元素,在等概率状况下,平均需要移动n/2个元素。
b 顺序表删除运算,删除结束后,线性表长度减少了1,顺序表删除运算时需要移动元素,在等概率状况下,平均需要移动(n-1)/2个元素。插入删除运算不以便
1.4栈和队列
1栈及其基本运算
栈是限定在一端进行插入与删除运算线性表。栈是按照“先进后出”或“后进先出”原则来组织数据。
栈具备记忆作用
栈基本运算 a入栈运算 b出栈运算 c读栈顶元素是将栈顶元素赋给一种指定变量,此时指针无变化
2队列及其基本运算
队列是指容许在一端(队尾)进行插入,一端(队头)进行删除线性表
队列是“先进先出”或“后进后出”线性表
队列运算涉及 a入队运算 b出队运算
3循环队列及其运算
循环队列初始状态为空,即rear=front=m
循环队列基本运算分为入队运算和退队运算
队列空条件:s=0
队列满条件:s=1 front=rear
1.5线性链表
1线性表顺序存储缺陷
Data next左指针 数据域 右指针A
Data next
左指针 数据域 右指针
B线性表顺序存储构造下,线性表存储空间不便扩充
C线性表顺序存储构造不便于对存储空间动态分派
2线性链表:线性表链式存储构造称为线性链表,是一种物理存储单元上非持续,非顺序存储构造,数据元素逻辑顺序是通过链表中指针链接来实现。在链式存储方式中每个结点由二某些构成:数据域,指针域
线性链表分为单链表,双向链表和循环链表三种类型
3线性链表基本运算
a在线性链表中包括指定元素结点之前插入一种新元素
b在线性链表中删除包括指定元素结点
c将二个线性链表按规定合并成一种线性链表
d将一种线性链表按规定进行分解
e逆转线性链表 f 复制线性链表 g线性链表排序 h线性链表查找
4循环链表及其基本运算
循环链表是另一种形式链式存储构造,与线性链表相比,具备如下二个特点
a在循环链表中增长了一种表头结点,其数据域为任意或者依照需要来设立,指针域指向线性表第一种元素结点,循环链表头指向表头结点。
b 循环链表中最后一种结点指针域不为空,而是指向表头结点,即在循环表中,所有结点指针构成一种环状链
在对循环链表进行插入与删除过程中,实现了空表与非空表运算