没有合适的资源?快使用搜索试试~ 我知道了~
全国计算机等级考试二级VF.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 70 浏览量
2022-05-03
22:43:20
上传
评论
收藏 263KB DOC 举报
温馨提示
试读
19页
全国计算机等级考试二级VF.doc
资源推荐
资源详情
资源评论
第 1 章 基本数据结构与算法
1. 算法的基本概念
算法的指解题方案的准确而完整的描述。作为一个算法,一般应具有的特征为:
1) 可行性,针对实际问题设计的算法, 考虑其可行性,应该能够得到满意的结果;
2) 确定性,算法中的每一个步骤都必须是明确定义的,不允许有模掕两可的解释,也不允许有多义性;
3) 有穷性,算法必须能在执行有限个步骤之后终止;
4) 有零个或多个输入;
5) 有一个或多个输入;
综上所述,算法是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的 .明确的;这个运算顺序将在有限的次数下终
止。
2. 算法复杂度
算法的复杂度主要包括时间复杂度和空间复杂度。
(1)算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法在所执行的基本运算次数来度量,而算法
所执行的基本运算次数是问题规模的函数,即算法的工作量=f(n)
其中 N 是问题的规模。例如,两个 N 阶矩阵相乘需要的基本算法次数为 n
3
,即计算工作量为 n
3
, 也就是时间复杂度为 n
3
, 即
F(n)=O( n
3
)
(2) 算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的存空间。
[例 1.1] 算法的时间复杂度是指( ) A)执行算法程序所需要的时间 B)算法程序的长度 C)算法执行过程中所需要的基
本运算次数 D)算法程序中的指令条数答案:C
提示:2005 年 9 月真题填空题第 2 题。2006 年 9 月真题选择题第 7 题。2007 年 4 月真题选择题第 1 题属该题的类似题目
2007 年 4 月真题选择题第 11 题考察算法的特征。
1.2 数据结构的基本概念
1. 数据结构的定义 数据结构是指反映数据元素之间关系的数据元素集合的表示。 通俗地说,数据结构是指带有结构的
数据元素的集合。
(1)数据的逻辑结构
数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。
一个数据结构应包含以下两方面的信息: 1) 表示数据元素的信息; 2) 表示各数据元素之间的前后件关系。
(2) 数据的存储结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构 (也称数据的物理结构)。
一般来说,一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序。。索引等。而采用不同的
存储结构,其数据处理的效率是不同的,因此,在进行数据处理时, 选择适宜的存储结构是很重要的。
[例 1.2 ] 与所使用的计算机系统无关的数据结构是( ) A)存储 B)物理 C)逻辑 D)线性表 答案:
C
解析: 线性表是一种具体逻辑结构,存储结构也称物理结构,只是逻辑结构是不依赖于计算机系统的。所以选项 C 为正确答
案。
[例 1.3 ] 数据的存储结构是指( )
A) 存储在外存中的数据 B) 数据所占的存储空间量 C) 数据在计算机中的顺序存储方式 D) 数据的逻辑结构在计算
机中的表示 答案: D
解析:数据的存储结构,也称为数据的物理结构,它指的是数据的逻辑结构在计算机存储空间的中的存放形式。只有选项 D
符合其定义,为此题的答案。
提示:2007 年 4 月真题选择题第 1 题与该题相关。 2007 年 9 月真题选择题第 5 题考察程序的执行效率也数据结构的关系。
2. 数据结构的图形表示
[例 1.4] 以下表达中,正确的是( )
A)一个逻辑数据结构只能有一种存储结构 B)数据的逻辑结构属于线性结构,存储结构属于非线性结构
C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率 D)一个逻辑数据结构可以有多种存
储结构,且各种存储结构影响数据处理的效答案:D
解析:数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。一般来说,一种数据的逻辑结构根据需要
可以表示成多种存储结构,而采用不同的存储结构,其数据处理的效率是不同的。
提示: 2007 年 9 月真题选择题第 6 题属该题的类似题目。
数据结构除了可用二元关系表示外,还可以用直观的图形表示。在数据结构的图形表示中,对于数据集合中的
每一个数据元素用中间标有元素指的方框表示,一般称之为数据结点(简称为结点)。为了进一步表示各数
据元素之间的前后件关系,对于关系中的每一个元组,用一条有向线段从前件结点指向后件结点。
3. 线性结构与非线性结构
根据数据结构中个数据元素之间前后件关系的复杂程度,一般将数据结构分成两大类:线性结构和非线性结构。
如果一个非空的数据结构满足以下两个条件: 1)有且只有一个根结点 2)每一个结点最多有一个前件,也最多有
有一个后件。
则称该数据结构为线性结构。线性结构又称为线性表。如果一个数据结构不是线性结构。就称为非线性结构。
1.3 线性表与其顺序存储结构
1. 线性表的基本概念
线性表是有 n(n≥0)个数据元素 a
1
,a
2
,...,a
n
组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个
前件,除了最后一个外,有且只有一个后件,即线性表或是一个空表。或者可以表示为: ( a
1
,a
2
,...a
i
,..a
n
)其中 a
i
(i=1,2,...n)是数据元素,通常也称其为线性表中的一个结点。
2. 线性表的顺序存储结构
线性表的顺序存储结构具有以下两个基本特点:
1)线性表中所有元素所占的存储空间是连续的; 2)线性表中个数据元素在存储空间中是逻辑顺序依次存放的。
由此可以看出,在线性表的存储结构中,其前后件两个元素在存储空间中的紧邻的, 且前后元素一定存储在后件元素的
前面。
3. 线性表的插入、删除运算
下面讨论线性表在顺序存储结构下的插入与删除的问题。
(1)线性表的插入运算
设长度为 n 的线性表为 ( a
1
,a
2
,… ,a
i
,…,a
n
)
现要在线性表的第 j 个元素 之前插入一个新元素 b,插入后得到长度为 n+1 的线性表为 (a′
1,
a′
2,
…,a
′
j
,a′
j+1
,…,a′
n
,a′
n+1
)
则插入前后两个线性表中的元素满足如下关系:
a
j
1≤j≤i-1
a′
j=
b j = i
a
j-1
i+1≤j≤n+1
一般情况下,要在第 i(1≤i≤n)个元素之前插入一个新元素时,首先要从最后一个(即第 n)元素开始,知道第 i 个元素之
间共 n-i+1 个元素依次向后移动一个位置,移动完毕后,第 i 个就被空出,然后将新元素插入到第 i 个位置,插入完毕后,
线性表的长度增加了 1.(2)线性表的删除运算
设长度为 n 的线性表为 ( a
1
,a
2
,… ,a
i
,…,a
n
)
现要删除第 j 个元素,删除后得到长度为 n-1 的线性表 ( a′
1,
a′
2,
…,a′
j
,…,a′
n-1
)
则删除前后两个线性表中的元素满足如下关系:
a
j
1≤j≤i-1
a′
j=
a
j+1
i+1≤j≤n+1
一般情况下,要删除第 i (1≤i≤n )个元素时,从第 i+1 个元素开始,直到第 n 个元素之间共 n-1 个元素依次向前移动一个
位置,删除完毕后,线性表的长度减少了 1。
1 / 19
退队←a
1
a
2
a
3
a
n
←入队
1.4 栈和队列
栈与其基本运算
队列与其基本运算
1. 与其基本运算
栈(stack)是限定在一端进行插入和删除运算的线性表。
在栈中,允许插入与删除的一端称为栈顶(top),另一端称为栈低(bottom)。栈顶元素总是最后被插入的元素;栈
底元素总是最先被插入的元素,栈顶元素总是最先被删除的元素;栈底元素总是最后被删除的元素。即栈是按照“先进后出”
(First In Last “Out, FILO”)的原则组织数据的,因此,栈也被称为“先进后出”表。
栈的基本运算有三种: 入栈、出栈、和读栈顶元素。
[例 1.5] 以下关于栈的描述中错误的是( )
A)栈的先进后出的线性表 B)栈只能顺序存储
C)栈具有记忆作用 D)对栈的插入于删除中,不需要改变栈底指针。
答案: B .
解析:栈是限定在一端进行插入和删除的线性表,允许插入和删除的一端称为栈顶,另一端称为栈底;栈是按照“先进后出”
或“后进先出”的原则就、组织数据的;栈既可以顺序存储又可以链式存储;栈具有记忆功能。
提示:2008 年 4 月真题选择题第 7 题属该题的类似题目。
(1) 队列的基本概念
队列是指允许在一端进行插入,而在另一端进行删除的线性表。允许插入的一段称为队尾,通常用一个称为队尾
指针(rear)的指针指向队尾元素,即尾指针总是指向最后被插入的元素;允许删除的一端称为排头(也称为队头),通常也
用一个排头指针(front)指向排头元素的前一个位置。因此,队列又称为“先进先出”(First In First Out FIFO)的线性表。
队列的基本结构如图 1-1 所示。
图 1-1 队列的基本结构
向队列的队尾插入一个元素称为入队运算,从队列的排头删除一个元素称为退队运算。(2)循环队列与其运算
在实际应用中,队列的顺序存储结构一般采用循环队列的形式。
所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。
在循环队列中,用队尾指针 rear 指向队列中的队尾元素,用排头指针 front 指向排头元素的前一个位置,因此,从
排头指针 front 指向最后一个位置直到队尾指针 rear 指向的位置之间,所有的元素均为队列中的元素。
循环队列的初始状态唯恐,即 rear=front[例 1-6] 以下关于队列的表达正确的是( )。A)队列是非线性结构
B)队列是一种树状结构 C)队列具有“先进先出”的特征 D)队列具有“后进后出”的特征
答案:C。提示:2007 年 4 月真题选择题第 5 题属该题的类似题目。
[例 1-7] 以下说法中,正确的是( )。A)栈是在两端操作、“先进先出”的线性表 B)栈是在一端操作、“先进先出”的线
性表 C)队列是在一端操作、“先进先出”的线 D)队列是在两端操作、“先进先出”的线性表 答案:D。
解析:栈是只允许在一端进行插入和删除操作的线性表,又称“先进后出”或“后进先出”表;队列是在一段进行插入,而在另
一端进行删除的线性表,又称“先进先出”或“后进后出”表。所以只有选项 D 正确。
提示:2007 年 9 月真题填空题第 3 题考察循环队列的存储结构。
1.5 线性链表
1.线性链表的基本概念
线性表的链式存储结构称为线性链表,线性链表分为单链表,双向链表和循环链表三种类型。
为了适应线性表的链式存储结构,计算机存储空间被划为一个一个小块,每一小块占若干字节,通常称这些小块为存储节点。
为了存储线性表中的每一个元素,一方面要存出数据元素的值,另一方面要存储各数据元素之间的前后件关系。为此目的,
将存储空间中的每一个存储节点分为两部分:一部分用于存储数据元素的值,称之为数据域;另一部分用于存放下一个数据
元素的存储序号(即存储节点的地址),即指向后件节点,称为指针域。
2. 线性链表的基本运算
线性链表的运算主要有以下几个:
1) 在线性链表中包含指定元素的结点之前插入一个新元素。
2) 在线性链表中删除包含指定元素的结点。
3) 将两个线性链表按要求合并成一个线性链表。
4) 将一个线性链表按要求进行分解。
5) 逆转线性链表。
6) 复制线性链表。
7) 线性链表的排序。
8) 线性链表的查找。
3.循环链表与其基本运算
循环链表与线性链表相比,具有以下两个特点:
1) 在循环链表中增加了一个表头结点,其数据域为任意或者根据需要来设置,指针域指向线性表的第一个元素
的结点。循环链表的头指针指向表头结点。
2) 循环链表中最后一个结点的指针域不为空,而是指向表头结点。即循环链表中,所有结点的指针构成了一个
环状链。
图 1-2 是一个非空循环链表,图 1-3 是一个空循环链表。
HEAD …
图 1-2 非空循环链表
HEAD
表头结点 图 1-3 空循环链表
循环链表的插入和删除运算的方法与线性单链表基本相同。但由循环链表的特点可以看出,在对循环链表进行插入和删除过程中,实现了空表和非空表的运算统一。
[例 1-8] 以下对于线性链表的描述中正确的是( )。 A)存储空间不一定是连续,且各元素的存储顺序是任意的 B)存储空间不一定是连续,且前件元素一定存储在后件元素的前面
C)存储空间必须有连续,且前件元素一定存储在后件元素前面 D)存储空间必须有连续,且各元素的存储顺序是任意的 答案:A。
解析:采用链式存储结构的线性表称为线性链表。其存储的结构的存储空间可以不连续,换句话说,逻辑上相邻的数据元素,其储存位置(又称物理位置)不一定相邻,数据元素之间的逻辑关系是由指针域确定的。
2 / 19
a
1
a
2
a
n
1.6 树和二叉树 树的基本概念 树是一种简单的非线性结构。在树这种数据结构中,所有元素之间的关系具有明显的层次特性,图 1-4 表示一棵一般的树。
图 1-4 一般的树
2.二叉树与其基本性质
(1)什么是二叉树
二叉树是一种很有用的非线性结构,它具有以下两个特点:非空二叉树只有一个根结点;每一个结点最多有两棵子树,
且分别称为该节点的左子树和右子树。
(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)满二叉树与完全二叉树 满二叉树:除最后一层外,每一层上的所有结点都有两个子结点,换句话说,每一
层上的节点数都达到最大值,即在满二叉树的第 k 层上有 2
k-1
个结点,且深度为 m 的满二叉树中有 2
m
-1 个结点。
完全二叉树:除最后一层外,每一层上的节点数都达到最大值;在最后一层上只缺少右边的若干结点。
满二叉树与完全二叉树的关系:满二叉树也是完全二叉树,但完全二叉树不一定是满二叉树。
完全二叉树还具有如下两个特性:
性质 5 具有 n 个结点的完全二叉树的深度为[log
2
n]+1。
性质 6 设完全二叉树共有 n 个结点。如果从根节点开始,按层序(每一层从左到右)用自然数 1,2,…,n 给
结点编号,则对于编号为 k(k=1,2,…,n)的结点有以下结论:1、若 k=1,则该结点为根节点,他没有父节点,若 k
>1,则该结点的父节点编号为[k/2]。2、若 2k≤n,则编号为 k 的左节点的左子结点编号为 2k;否则该结点无左子结点
(显然也没有右子结点)。3、若 2k+1≤n,则编号为 k 的结点的右子结点编号为 2k+1;否则该结点无右子结点。
[例 1-9] 设一棵完全二叉树共有 700 个结点,则在该二叉树中有个叶结点。 答案:350 个。
解析:根据完全二叉树的定义可以得出:度为 1 的结点的个数为 0 或 1;又由性质 3 可知,度为 0 的结点的个数比度为
2 的结点的个数多 1 个;设度为 0 的结点个数为 k,则度为 2 的结点个数为 k-1,设度为 1 的结点个数为 n,则有 k+k-
1+n=700,由于 k 和 n 都是自然数,n 的值为 0 或 1,所以只有当 n=1 是,k 有整数解,此时 k=350.
提示:2007 年 9 月真题选择题第 8 题属该题的类似题目。
[例 1-10] 深度为 5 的满二叉树中,结点的个数为。 答案:31。
解析:满二叉树是相同深度的二叉树中结点最多的一棵,所以由性质 2 可知,深度为 5 的二叉树最多有 2
5
-1=31 个结点。
即深度为 5 的满二叉树的结点为 31 个。
提示:2007 年 4 月真题选择题第 7 题、填空题第 1 题、2008 年 4 月真题填空题第 2 题属该题的类似题目。
3.二叉树的存储结构
在计算机中,二叉树通常采用链式存储结构。
与线性链表类似,用于存储二叉树中各元素的存储结点也由两部分组成;数据域和指针域。但在二叉树中,由于每一个
元素可以有两个后件(即两个子结点),一次,用于存储二叉树的存储节点的指针域有两个,一个用于指向该结点的左子结
点的存储地址,称为左指针域;另一个用于指向该结点的右子结点的存储地址,称为右指针域。
4.二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为三种:前序遍历、中序遍历和后序遍历。各个
遍历过程描述如下:
(1) 前序遍历(DLR)若二叉树为空,则完毕返回,否则:访问根节点;前序遍历左子树;前序遍历右
子树。
(2) 中序遍历(LDR)若二叉树为空,则完毕返回,否则:中序遍历左子树;访问根节点;中序遍历右
子树。
(3) 后序遍历(LRD)若二叉树为空,则完毕返回,否则:后序遍历左子树;访问根节点后
(4) 序遍历右子树。
[例 1-11] 已知二叉树(见图 1-5),其后序遍历序列是( )。
A)ABCDEF B) DBAECFC) BCDEFA D) DBEFCA
答案:D。
解析:采用后序遍历方式遍历二叉树的具体过程为:
1)先后序遍历左子树(以 B 为根节点的左子树,
包括两个结点 B 和 D),在左子树中仍按后序遍历,
所以先访问左节点 D,其右子树为空,所以第二个
访问的结点是该子树的根节点 B。
图 1-5 二叉树
2)接着按后序遍历右子树(以 C 为根节点,包括 C、E、F 三个结点),右子树中也按后序遍历访问左子树 E,再访问右子树
F,最后访问根节点 C,右子树访问完毕。
3)最后访问的是二叉树的根节点 A。故访问顺序为:D→B→E→F→C→A。
查找技术所谓查找是指在一个给定的数据结构中查找某个指定的元素。通常,对不同的数据结构应采用不同的查找
3 / 19
A
B C D E
F G H I J
K
A
B C
E F
D
方法。
1.顺序查找 顺序查找是指在现行表中查找指定的元素,基本方法为:从线性表的第一个元素开始,依次将线性表中的元素
与被查元素进行比较,若相等则表示找到(即查找成功);若现行表中所有的元素都与被查元素进行了比较但都不相等,则
表示线性表中没有要找的元素(即查找失败)。
【例1-12】 对长度为 n 的线性表进行顺序查找,在最坏的情况下所需要的比较次数是( )。
A)n+1 B)n C)(n+1)/2 D)n/2 答案:B。
解析:在进行顺序查找过程中,如果现行表中的第一个元素就是被查找元素,则只需做一次比较就查找成功,查找效率
最高;但如果被查的元素是线性表中的最后一个元素,或者被查找元素根本不在线性表中,则为了查找这个元素需要与线性
表中所有的元素进行比较,这是顺行查找的最坏情况。在平均情况下,利用顺序查找法在线性表中一半的元素进行比较。
题目中的线性表的长度为 n,则在最坏情况下,需要比较 n 次。
2.二分查找
二分查找只适用于顺序存储的有序表。设有序线性表的长度为 n,被查元素为 x,则二分查找的方法如下:将 x 与线性表的
中间项进行比较。
若中间项的值等于 x,则说明查到,查找完毕;若 x 小于中间项的值,则在线性表的前半部分(即中间项以前的部分)以相
同的方法进行查找;若 x 大于中间项的值,则在线性表的后半部分(即中间项以后的部分)以相同的方法进行查找。
这个过程一直进行到查找成功或子表长度为 0(说明现行表中没有这个元素)为止。
显然,当有序线性表为顺序存储时才能采用二分查找,并且二分查找的效率要比顺序查找高得多。对于长度为 n 的有序线
性表,在最坏的情况下,二分查找只需要比较 log
2
n 次,而顺序查找需要比较 n 次。
排序技术 所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)的次序排列起来。
重要知识点
交换类排序法
1. 交换类排序法
(1) 冒泡排序法
冒泡排序法是一种最简单的交换类排序方法,它是通过相邻数据元素的交换逐步将线性表变成有序。
冒泡排序法的基本过程如下:
首先,从表头开始往后扫描线性表,在扫描过程中主次比较两个相邻元素的大小。若两个相邻元素中,前面的元素大于后面
的元素,则将它们交换,称之为消去了一个逆序。
然后从后往前扫描剩下的线性表,同样,在扫描过程中主次比较两个相邻元素的大小。若两个相邻元素中,后面的元素小于
前面的元素,则将他们交换,这样就又消去了一个逆序。一次排序完毕后,表中最大元素为与线性表末尾。
对剩下的线性表重复上述过程,直到剩下的线性表变空位置,此时的线性表已经变为有序。
(2) 快速排序法
快速排序法也会死一种交换类排序方法,但由于它的排序速度比较快,因此称为快速排序法。
快速排序法的基本思想如下:
从线性表中选取一个元素,设为 T,将线性表后面小于 T 的元素移到前面,而前面大于 T 的元素移到后面,结果就将线
性表分成了两部分(称为两个子表),T 插入到其分界线的位置处,这个过程称为线性表的分割。通过对线性表的一次分割 ,
就以 T 为分界线,将线性表分成了前后连个子表,且前面子表中的所有元素均不大于 T,二后面子表中的所有元素均不小于
T。
如果对分割后的各子表再按上述原则进行分割,并且这种分割过程一直做下去,知道所有子表为空为止,则此时的线性
表就变成了有序表。
[1-13] 在最坏情况下,冒泡排序法需要的比较次数为。 答案:n(n-1)/2.
解析:假设线性表的长度为 n,则在最坏情况下,冒泡排序需要经过 n/2 遍从前往后的扫描和 n/2 遍的从后往前的扫描,
同时需要进行 n-1 躺排序所以比较次数为 n(n-1)/2。但这个工作量不是必需的,一般情况下要小于这个工作量。
2. 插入类排序法
(1) 简单插入排序法 所谓插入排序,是指将无序序列中的各元素依次插入到已经有序的线性列
表中。
(2) 希尔排序法 希尔排序法属于插入类排序,其基本思想为:将整个无序序列分割成若干小
的子序列分别进行插入排序。
子序列分割方法 如下:将相隔某个增量 h 的元素构成一个子序列,在排序过程中,逐次减少这个铮亮,最后
当 h 减到 1 时,进行一次插入排序,排序即完成
3. 选择类排序法
(1) 简单项选择择排序法
选择排序法的基本思想如下:扫描整个线性表,从中选出最小的元素,将它交换到表的最前面;然后对剩下的子表
采用同样的方法,直到子表空为止。
(2) 建堆排序法
堆排序的方法如下:1、首先将一个无序序列建成堆;2、然后将堆顶元素与堆中最后一个元素交换。不考虑已经交
换到最后的那个元素,只考虑前 n-1 个元素构成的子序列,显然,该子序列已不是堆,但左、右子树仍为堆,可以
将该子树调整为堆。反复做第二部,知道剩下的子序列为空为止。
1.10 仿真练习与参考答案
一.选择题
1.下面的表达正确的是( )。A)算法的执行效率与数据的存储结构无关 B)算法的空间复杂度是指算法程序中指令(或语
句)的条数
C)算法的有穷性是指算法必须能在执行有限个步骤之后终止。D)以上三种描述都不对。
2.以下数据结构中不属于现行数据结构的是( )。A)队列 B)线性表 C)二叉树 D)栈
3.一个栈的入栈序列是 A,B,C,D,E,则不可能的输出序列是( )。A) E D C B A B) D E C B A C) D C E A B
D) A B C D E
4.快速排序法属于( )排序法。A) 交换类 B)插入类 C)选择类 D) 建堆
5.以下关于队列的表达正确的是( )。
A)在队列中只能插入数据 B)在队列中只能删除数据 C)队列是“先进先出”的线性表 D)队列
是“先进后出”的线性表
6.在深度为 5 的满二叉树中,叶结点的个数为( )。A)32 B)31 C)16 D)15
7.算法的空间复杂度是指( )。
A)算法程序的长度 B)算法程序中的指令条数 C)执行算法过程中所需要的存储空间 D)算法程序所
占的存储空间
8.对一个长度为 10 的排好序的表用二分法查找,若查找不成功,至少需要比较的次数为( ) A)3 B )4
C)5 D)6
9. 假定根节点的层次是 0, 含有 15 个结 点的二叉树的最小树深是( )。 A) 3 B )4 C ) 5
D)6
10.深度为 h 的二叉树上只有度为 0 和度为 2 的结点,则此二叉树中所包含的结点数至少为( )。 A)2h-1 B)2h
C)2h+1 D)h+1
11.对于长度为 n 的线性表,在最坏情况下,以下各排序法所对应的比较次数中正确的是( )。
A)冒泡排序为 n/2 B)冒泡排序为 n C)快速排序为 n D)快速排序为 n(n-1)/2
二.填空题
1.数据结构包括数据的结构和数据的存储结构与各种数据结构间的运算。
2.只允许在一端进行插入和删除的线性表称为。
3.在长度为 n 的有序线性表中进行二分查找,其时间复杂度为 。
4.设一棵二叉树的中序遍历结果为 DBEAFC,前序遍历结果为 ABDECF,则后序遍历结果为
5.线性表中 称为线性表的长度。
参考答案一、选择题 1.C 2.C 3.C 4.A 5.C 6.C 7.C 8.A 9.A 10.A 11.D
二、填空题 1.逻辑 2.栈 3.O(log
2
n) 4.DEBFCA 5.数据元素的个数
4 / 19
剩余18页未读,继续阅读
资源评论
智慧安全方案
- 粉丝: 0
- 资源: 59万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功