全国计算机等级考试二级公共基础考点Word文件下载.docx
《全国计算机等级考试二级公共基础考点Word文件下载.docx》由会员分享,可在线阅读,更多相关《全国计算机等级考试二级公共基础考点Word文件下载.docx(89页珍藏版)》请在冰点文库上搜索。
![全国计算机等级考试二级公共基础考点Word文件下载.docx](https://file1.bingdoc.com/fileroot1/2023-5/7/4b52a1f7-a918-4fcc-8016-4270b7d58458/4b52a1f7-a918-4fcc-8016-4270b7d584581.gif)
算法
考点2逻辑结构和存储结构
1.数据结构的基本概念
(1)数据结构:
是指相互有关联的数据元素的集合。
(2)数据结构主要研究3个方面的内容:
①数据集合中各数据元素之间的逻辑关系,即
数据的逻辑结构;
②在对资料进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
③对各种数据结构进行的运算。
2.逻辑结构
数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和
定义在此集合中的若干关系来表示。
数据的逻辑结构有两个要素:
一是数据元素的集合,通
常记为D;
二是D上的关系,它反映了数据元素之间的前后件关系,通常记为R。
所以一
个数据结构B可以表示成:
B=(D,R)
例如,如果把一年四季看作一个数据结构,则可表示成:
B=(D,R),其中D={春季,夏
季,秋季,冬季},R={(春季,夏季),(夏季,秋季),(秋季,冬季)}。
3.存储结构
数据的逻辑结构在计算机存储空间中的存放形式称数据的存储(物理)结构。
数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,一种数据的逻辑结构根
据需要可以表示成多种存储结构,常用的存储结构有顺序存储结构、链接存储结构。
顺序存储方式主要用于线性的数据结构,它把逻辑上相邻的数据元素存储在物理上相邻
的存储单元里,结点之间的关系由存储单元的邻接关系来体现。
链式存储结构就是在每个结点中至少包含一个指标域,用指标来体现数据元素之间逻辑
上的联系。
考点3线性结构和非线性结构
1.线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类:
线性结构和非线性结构。
如果一非空的数据结构满足:
①有且仅有一个根结点;
②每一个结点最多有一个前件,
也最多有一件后件。
则称该数据结构为线性结构或线性表。
在一个线性结构中插入或删除任何一个结点后还应是线性结构。
栈、队列、串等都是线性结构。
2.非线性结构
如果一个数据结构不满足线性结构的两个条件的一个或两个,则该结构称为非线性结构。
广义表、树和图等数据结构都是非线性结构。
3.线性表的顺序存储结构具有以下两个基本特点
(1)线性表中所有元素所占的存储空间是连续的;
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
例如,对于线性表(a1,a2,⋯,ai,⋯,an)元素ai的存储位址为:
ADR(ai)=ADR(a1)+(i-1)*k
其中,ADR(a1)是第一个元素的位址,
k代表每个元素所占的位元组数。
4.顺序表的运算
顺序表是指线性表的顺序存储结构,对顺序表的运算有:
查找、插入、删除等。
1.下列叙述中正确的是。
A)顺序结构存储的存储一定是连续的,链式存储结构的存储空间不一定是连续的
B)顺序存储结构只针对线性结构,链式存储结构只针对非线性结构
C)顺序存储结构能存储有序表,链式存储结构不能存储有序表
D)链式存储结构比顺序存储结构节省存储空间
2.下列数据结构中,属于非线性结构的是
A)循环队列B)带链队列
C)二叉树
D)带链栈
3.下列关于线性链表的叙述中,正确的是。
A)各数据结点的存储空间可以不连续,但它们的存储顺序与逻辑顺序必须一致
B)各数据结点的存储顺序与逻辑顺序可以不一致,但它们的存储空间必须连续
C)进行插入与删除时,不需要移动表中的元素
D)以上三种说法都不对
4.下列链表中,其逻辑结构属于非线性结构的是
A)双向链表B)带链的栈
5.下列叙述中正确的是。
C)二叉链表
D)循环链表
A)一个逻辑结构只能有一种存储结构
B)逻辑结构属于线性结构,存储结构属于非线性结构
C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理效率
D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理效率
6.链表不具备的特点是。
)可随机访问任一结点
B)插入和删除不需要移动任何元素
C)不必事行估计存储空间
D)所需空间与其长度成正比
考点4
栈
1.栈的基本概念
栈(stack)是一种特殊的线性表,是限定只在一端进行插入与删除的线性表。
在栈中,一端是封闭的,既不允许进行插入元素,也不允许删除元素;
另一端是开口的,允许插入和删除元素。
通常称插入、删除的一端为栈顶,另一端为栈底。
当表中没有元素时
称为空栈。
栈顶元素总是最后被插入的元素,从而也是最先被删除的元素。
栈底元素总是最先被插入的元素,因而也是最后才能被删除的元素。
栈是按照“先进后出”(FirstInLastOut,简称FILO)或“后进先出”的原则组织数据的。
例如,枪械的子弹匣就可以用来形象地表示栈结构。
子弹匣的一端是完全封闭的,最后被压入弹匣的子弹总是最先被弹出,而最先被压入的子弹最后才能被弹出。
2.栈的顺序存储及其运算
栈的基本运算有3种:
入栈、退栈与读栈顶元素。
①入栈运算:
在栈顶位置插入一个新元素;
②退栈运算:
取出栈顶元素并赋给一个指定的变数;
③读栈顶元素:
将栈顶元素赋给一个指定的变数。
1.下列关于栈的叙述正确的是
A)栈按“先进先出”组织数据
B)栈按“先进后出”组织数据
C)只能在栈底插入数据
D)不能删除数据
2.一个栈的初始状态为空。
现将元素
1、2、3、4、5、A、B、C、D、E依次入栈,然后再
依次出栈,则元素出栈的顺序是
A)12345ABCDE
C)ABCDE12345
D)54321EDCBA
BEDCBA54321
3.假设用一个长度为
50的数组(数组元素的下标从
0到49)作为栈的存储空间,栈底指
针bottom指向栈底元素,栈顶指针
top指向栈顶元素,如果
bottom=49,top=30(数组
下标),则栈中具有__【1】__个元素。
19
4.下列数据结果中,能够按照“先进后出”原则存取资料的是
A)循环队列B)栈C)队列
D)二叉树
5.下列关于栈的叙述中,正确的是
A)栈顶元素最先能被删除
C)栈底元素永远不能被删除
B)栈顶元素最后才能被删除
D)以上三种说法都不对
6.下列关于栈的叙述中,正确的是
A)栈底元素一定一定是最后入栈的元素C)栈顶元素一定是最先入栈的元素
B)栈操作遵循先进后出的原则
7.数据结构分为线性结构与非线性结构,带链的栈属于【1】。
线性结构
8.设栈的存储空间为S(1:
40),初始状态为bottom=0,top=0
算后,top=20,则当前栈中有【1】元素。
20
9.以下不是栈的基本运算的是。
A)判断栈是否为空B)将栈置为空栈
C)删除栈顶元素D)删除栈底元素
,现经过一系列入栈和出栈运
考点5队列
1.队列的基本概念
队列是只允许在一端进行删除,在另一端进行插入的线性表,通常将允许删除的一端称为队头,允许插入的一端称为队尾。
当表中没有元素时称为空队列。
队列是按照“先进先出”的原则来组织数据的,与栈相反,队列又称为“先进先出”(FirstInFirstOut,简称FIFO)或“后进后出”(LastInLastOut,简称LILO)的线性表。
例如:
火车进隧道,最先进遂道的是火车头,最后是火车尾。
而火车出遂道的时候也是火车头先出,最后出的是火车尾。
更一般地,若有队列:
Q=(q1,q2,⋯,qn)
那么,q1为队头元素,qn是队尾元素。
队列中的元素是按照
q1,q2,⋯,qn的顺序进入的,
退出队列也只能按照这个次序依次退出,即只有在
q1,q2,⋯,qn-1
都出队之后,qn才能出队。
队列体现了一种“先来先服务”的原则。
2.队列的运算
入队:
往队尾插入一个数据元素;
出队:
从队列的队头删除一个数据元素。
由于存在假“溢出”现象,队列的顺序存储结构一般采用循环队列的形式。
计算循环队列的元素个数:
“尾指针减头指针”,若为负数,再加其容量即可。
设某循环队列的容量为40(序号为0~39),现经过一系列的入队和出队运算后,有:
①front=11,rear=19
②front=19,rear=11
则该循环队列中的元素个数分别为:
8和32。
1.设某循环队列的容量为50,头指针front=5(指向队头元素的前一位置),尾指针rear=29(指向队尾元素),则该循环队列中共有【3】个元素。
24
2.下列叙述正确的是。
A)循环队列有队头和队尾两个指针,因此,循环队列是非线形结构
B)在循环队列中,只需要队头指针就能反映队列中元素的动态变化情况
C)在循环队列中,只需要队尾指针就能反映队列中元素的动态变化情况
D)循环队列中元素的个数由队头指标和队尾指标共同决定
3.对于循环队列,下列叙述中正确的是。
A)队头指针是固定不变的
B)队头指针一定大于队尾指针
C)队头指针一定小于队尾指针
D)队头指标可以大于队尾指标,也可以小于队尾指标
4.一个队列的初始状态为空,先将元素A,B,C,D,E,F,5,4,3,2,1依次入队,然后再依次退队,则元素退队的顺序为【1】。
ABCDEF54321
5.设某循环列队的容量为50,如果头指标front=45(指向队头元素的前一位置),尾指针rear=10(指向队尾元素),则该循环队列中共有【2】个元素。
15
6.设循环列队的存储空间为
Q(1:
30),初始状态为front=rear=30。
现经过一系列入队与
退队运算后,front=16,rear=15,则该循环队列中共有【2】个元素。
29
7.设循环队列的存储空间为
Q(1:
35),初始状态为front=rear=35。
退队运算后,front=15,rear=15,则循环队列中的元素个数为
A)20
或
35
C)15
D)16
B0
8.下列叙述中正确的是
A)栈是“先进先出”的线性表B)队列是“先进先出”的线性表
C)循环队列是非线性结构
D)有序线性表既可以采用顺序存储结构,也可以采用链式存储结构
9.支持子程序调用的数据结构是。
A)栈B)树C)队列D)二叉树
考点6链表
在链式存储方式中,要求每个结点至少由两部分组成:
一部分用于存放数据元素值,称为值域;
另一部分用于存放指针,称为指针域。
其中指标用于指向该结点的前一个或后一个
结点。
链式存储方式既可用于表示线性结构,也可用于表示非线性结构。
1.线性链表
线性表的链式存储结构称为线性链表。
在某些应用中,对线性链表中的每个结点设置两个指标,一个称为左指标,用于指向其
前件结点;
另一个称为右指标,用于指向其后件结点。
这样的链表称为双向链表。
在线性链表中,各数据元素结点的存储空间可以是不连续的,且各数据元素的存储顺序
与逻辑顺序可以不一致。
在线性链表中进行插入与删除,不需要移动链表中的元素。
线性单链表中,要设置一个头指针,一般用head来表示,当head=NULL(或0)时称
为空表。
如果是双向链表,则两个指针通常为:
左指标(Llink)指向前件结点,右指标(Rlink)指向
后件结点。
线性链表的基本运算有:
2.带链的栈
栈也是线性表,也可以采用链式存储结构。
带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为可利用栈。
1.下列关于线性链表的叙述中,正确的是。
A.各数据结点的存储空间可以不连续,但它们的存储顺序与逻辑顺序必须一致B.各数据结点的存储顺序与逻辑顺序可以不一致,但它们的存储空间必须连续
C.进行插入与删除时,不需要移动表中的元素
D.以上三种说法都不对
2.下列对于线性链表的描述中正确的是。
A)存储空间不一定是连续,且各元素的存储顺序是任意的
B)存储空间不一定是连续,且前件元素一定存储在后件元素的前面C)存储空间必须连续,且前件元素一定存储在后件元素的前面
D)存储空间必须连续,且各元素的存储顺序是任意的
3.下列叙述中正确的是。
A)线性链表是线性表的链式存储结构C)双向链表是非线性结构
B)栈与队列是非线性结构
D)只有根结点的二叉树是线性结构
4.数据结构分为线性结构和非线性结构,带链的队列属于
考点
7
二叉树及其基本性质
1.二叉树及其基本概念
二叉树是一种很有用的非线性结构,具有以下两个特点:
①非空二叉树只有一个根结点;
②每一个结点最多有两棵子树,且分别称为该结点的左子树和右子树。
在二叉树中,每一个结点的度最大为2,即所有子树(左子树或右子树)也均为二叉树。
另外,二叉树中的每个结点的子树被明显地分为左子树和右子树。
在二叉树中,一个结点可以只有左子树而没有左子树;
也可以只有右子树而没有左子树。
当一个结点既没有左子树也没有右子树时,该结点称为叶子结点。
如图1-1中的各结点说明
及有关二叉树的基本概念详见表1-1。
图1-1
二叉树示例图
表1-1
二叉树的基本概念
根(父)结点
在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只
有一个,称为树的根结点,简称树的根。
例如,在图
1-1中,结点A是树的根。
子结点和
在树结构中,每一个结点可以有多个后件,称为该结点的子结点。
没有后
叶子结点
件的结点称为叶子结点。
1-1中,结点D、E、F均为叶子结点。
在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中
度最大的度称为树的度。
例如,在图1-1中,根结点A和结点B的度为2,结
点C的度为1,叶子结点D,E,F的度为0。
所以,该树的度为2。
若一棵树的根结点所在的层次为1,其它结点所在的层次等于它的父结点
深度所在的层次加1。
树的最大层次称为树的深度。
例如,在图1-1中,根结点A
在第1层,结点B,C在第2层,结点D,E,F在第3层。
该树的深度为3。
子树
在树中,以某结点的一个子结点为根构成的树称为该结点的一棵子树。
2.二叉树基本性质
二叉树具有以下几个性质:
性质1:
在二叉树的第k层上,最多有2k-1(k≥1)个结点;
性质2:
深度为m的二叉树最多有
2m-1个结点;
性质3:
在任意一棵二叉树中,度为
0的结点(即叶子结点)总是比度为
2的结点多一
个,即n0=n2+1。
性质4:
具有n个结点的二叉树,其深度至少为[
log2n]+1,其中[log2n]表示取log2n
的整数部分。
3.满二叉树与完全二叉树
满二叉树是指这样的一种二叉树:
除最后一层外,每一层上的所有结点都有两个子结点。
在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第
k层上有2k-1个结点,
且深度为m的满二叉树有2m-1个结点。
完全二叉树是指这样的二叉树:
除了最后一层外,每一层上的结点数均达到最大值;
在最后一层上只缺少右边的若干个结点。
对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现。
对于任何一个结点,
若其右分支下的子孙结点的最大层数为p,则其左分支下的子孙结点的最大层数或为p,或
为p+1.
完全二叉树具有以下两个性质:
性质5:
具有n个结点的完全二叉树的深度为[log2n]+1。
性质6:
设完全二叉树共有n个结点。
如果从根结点开始,按层次(每一层从左到右)
用自然数1,2,⋯,n给结点进行编号,则对于编号为k(k=1,2,⋯,n)的结点有以下结论:
①若k=1,则该结点为根结点,它没有父结点;
若k>
1,则该结点的父结点编号为(int)(k/2)。
②若2k≤n,则编号为k的结点的左子结点编号为2k;
否则该结点无左子结点(显然也
没有右子结点)。
③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;
否则该结点无右子结点。
考点8二叉树的遍历
在遍历二叉树的过程中,一般先遍历左子树,再遍历右子树。
在先左后右的原则下,根
据访问根结点的次序,二叉树的遍历分为三类:
前序遍历、中序遍历和后序遍历。
(1)前序遍历
1-1
前序遍历的次序为:
访问根结点、前序遍历左子树、前序遍历右子树。
例如,对图
中的二叉树进行前序遍历的结果
(前序序列)为:
ABDECF。
(2)中序遍历
中序遍历的次序为:
中序遍历左子树、访问根结点、中序遍历右子树。
中的二叉树进行中序遍历的结果(中序序列)为:
DBEACF。
(3)后序遍历:
后序遍历的次序为:
后序遍历左子树、后序遍历右子树、访问根结点。
中的二叉树进行后序遍历的结果(后序序列)为:
DEBFCA。
1.深度为5的满二叉树有
个叶子结点。
16
2.某二叉树有5个度为2的结点,则该二叉树的叶子结点数是
A)10
B)8
C)6
D)4
3.某二叉树有5个度为2的结点以及3个度为1的结点,则该二叉树中共有
个结点。
14
4.某二叉树共有7个结点,其中叶子结点只有
1个,则该二叉树的深度为(假设根结点在
第1层)
A)3
B)4
D)7
5.对下列二叉树进行中序遍历的结果是
DBXEAYFZC
BC
DEF
X
Y
Z
6.一棵二叉树的中序遍历结果为
DBEAFC,前序遍历结果为
ABDECF,则后序遍历的结果
为
DEBFCA
7.已知某二叉树的后序遍历序列是
DACBE,中序遍历序列是
DEBAC,则它的前序遍历序
列是
A)ACBDE
B)DEABC
C)DECAB
D)EDBAC
8.下列关于二叉树的叙述中,正确的是
A.叶子结点总是比度为
2的结点少一个
B.叶子结点总是比度为2
的结点多一个
C.叶子结点数是度为
2的结点数的两倍
D.度为2的结点数是度为
1的结点数的两倍
9.某二叉树共有25个结点,其中5个是叶子结点,则度为
1的结点数是
A)16
B)10
C)6
10.设树T的度为4,其中度为
1、2、3和4的结点个数分别为4、2、1、1,则T中叶子
结点的个数为
8
11.设二叉数如下:
DF
EGH
对该二叉树进行后序遍历的结果为
12.一棵二叉树共有47个结点,其中有
二叉树的深度为。
6
EDBGHFCA
23个度为2的结点。
假设根结点在第
1层上,则该
9
顺序查找
查找是指在一个给定的数据结构中查找某指定元素。
可从线性表的第1个元素开始,依
次将线性表中的元素与被查找的元素相比较,若相等则表示查找成功;
若线性表中的所有元
素都与被查找元素进行了比较,但都不等,则表示查找失败。
在下列两种情况下,只能采用顺序查找:
(1)如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,只能用顺序查找;
(2)即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。
10
二分法查找
二分法查找,也称折半查找,这是一种高效的查找方法。
能使用