孙夫雄数据结构习题剖析.docx
《孙夫雄数据结构习题剖析.docx》由会员分享，可在线阅读，更多相关《孙夫雄数据结构习题剖析.docx（130页珍藏版）》请在冰点文库上搜索。
孙夫雄数据结构习题剖析
数据构造习题
一、单项选择题
研究数据构造就是研究
数据的逻辑构造
数据的逻辑构造和储存构造
数据的储存构造
数据的逻辑构造、储存构造及其数据在运算上的实现
2.下边关于算法的说法，错误的选项是。
A）算法最后一定由计算机程序实现×
为解决某问题的算法与为该问题编写的程序含义是相同的程序=算法+数据构造
算法的可行性（确立性）是指指令不可以有二义性
以上几个都是错误的
计算机中的算法指的是解决某一个问题的有限运算序列，它一定具备
5个特征输入、输出、。
可履行性、可移植性和可扩大性
可履行性、有穷性和确立性
确立性、有穷性和稳固性
易读性、稳固性和确立性
4.以手下于逻辑构造的看法是。
次序表
哈希表
有序表
单链表
5.拥有线性构造的数据构造是。
图
树
广义表
栈
6.数据的储存构造包含次序、链接、散列和种基本种类。
向量
数组
会集
索引
7.根椐数据元素之间关系的不一样特征，以下4类基本逻辑构造反响了4
类基本数据组织形式。
以下解说错误的选项是。
会集中任何两个结点之间都有逻辑关系，但组织形式松懈
线性构造中结点按逻辑关系挨次储存成一行
树型构造拥有分支、层次特征，其形态有点像自然界中的树
图状构造中各个结点按逻辑关系相互环绕，任何两个结点都可以
毗邻
8.在数据构造中，从逻辑上可以把数据构造分红。
动向构造和静态构造
紧凑构造和非紧凑构造
线性构造和非线性构造
内部构造和外面构造
与数据元素自己的形式、内容、相对地点、个数没关的是数据
的。
储存构造
储存实现
逻辑构造
运算实现
10.以下说法错误的选项是。
程序设计的实质是算法设计
数据的逻辑构造是数据的组织形式，基本运算规定了数据的基本
操作方式
运算实现是完成运算功能的算法或这些算法的设计
算法设计思想老是与数据的某种相应储存形式相联系
某线性表中最常用的操作是在最后一个元素以后插入一个元素和删除
第一个元素，则采纳储存方式最节约运算时间。
单链表
仅有头指针的单循环链表
双链表
仅有尾指针的单循环链表
12.单链表的主要优点是。
便于随机盘问
储存密度高
逻辑上相邻的元素在物理上也是相邻的
插入和删除比较方便
13.线性表采纳链式储存时，其地址。
一定连续
必定不连续
部分连续
连续与否均可
关于一个线性表，既要求可以较快地进行插入和删除，又要求储存结
构可以反响数据元素之间的逻辑关系，则应当。
以次序方式储存
以链接方式储存
以散列方式储存
以上均可
15.若线性表中最常用的操作是取第i个的前趋元素，采用储存方式最节约时间。
次序表
单链表
双链表
单循环链表
16.若用单链表来表示队列，则应当采纳。
带尾指针的非循环链表
带尾指针的循环链表
带头指针的非循环链表
带头指针的循环链表
17.
若用一个大小为
6的数组来实现循环队列，且当rear
和front
的值分
别为0和3。
从队列中出队一个元素，再进队两个元素后，
rear
和front
的值分别为
A）
1和5
B）
2和4
C）
4和2
D）
5和1
18.设栈的输入序列是（1、2、3，4），则不行能输出的序列。
1243
2134
1432
4312
19.一个栈的输入序列为12345，则以下序列中不行能是栈的输出序列的
是。
23415
54132
23145
15432
20.
设栈S和队列Q的初始状态为空，元素
e1、e2、e3、e4、e5和e6依
次经过栈S，一个元素出栈后即进入队列
Q，若6个元素出队的序列是
e2、
e4、e3、e6、e5、e1，则栈S的容量最少应当是
。
A）
6
B）
4
C）
3
D）
2
一般状况下，将递归算法变换成等价的非递加归算法应当设
置。
货仓
队列
货仓或队列
数组
22.设栈的输入序列是
i个输出元素
A）不确立
1、2、,、
。
n，若输出序列的第一个元素是
n，则第
B）
n-i+l
c
n-i
23.假设一个次序循环队列的队首和队尾指针分别用front和rear表示，
则判队空的条件是。
front+1==rear
front==rear+1
front==O
front==rear
假设一个次序循环队列储存于数组a[n]中，其队首和队尾指针分别用
front和rear表示，则判断队满的条件是。
（rear-1）％n==front
B）rear==（front-1）％／n
（rear+1）％n==front
D）
rear==（front+1）
％／n
25.采纳
数据构造设计一个鉴别表达式中左、
右括号
能否配的算法最正确。
线性表的次序储存构造
队列
线性表的链式储存构造
栈
26.在以下算法描述中，涉及到队运算的算法是。
表达式求值算法
深度优先搜寻
二叉树前中后序遍历
广度优先搜寻
当利用大小为N的数组储存次序循环队列时，该队列的最大长度
为。
N-2
N-1
N
N+l
28.链栈与次序栈对比有一个显然的优点，即。
A）插入操作更为方便
B）平时不会出现栈满的状况
C）不会出现栈空的状况
D）删除操作更为方便
一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二
叉树必定满足。
A）所有的结点均无左孩子
B）所有的结点均无右孩子
C）只有一个叶子结点
D）是随意一棵二叉树
30.一棵完整二叉树上有1001个结点，此中叶子结点的个数是。
250
500
505
501
31.以下说法正确的选项是。
若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必
是该子树后序遍历序列中的最后一个结点
若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必
是该子树中序遍历序列中的最后一个结点
在二叉树中，拥有两个儿女的父结点，在中序遍历序列中，它的后继结点最多只好有一个儿女结点
在二叉树中，拥有一个儿女的父结点，在中序遍历序列中，它没有后继儿女结点
32.以下说法错误的选项是。
哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根
较近
若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点
C）己知二叉树的前序遍历和后序遍历其实不可以唯一地确立这棵树，因为不知道树的根结点是哪一个
在前序遍历二叉树的序列中，任何结点其子树的所有结点都是直接跟在该结点以后的
33.二叉树在线索化后，仍不可以有效求解的问题是。
前序线索二叉树中求前序后继
中序线索二叉树中求中序后继
中序线索二叉树中求中序前趋
后序线索二叉树中求后序后继
若二叉树采纳链式储存构造，要交换其所有分支结点左、右子树的位
置，利用遍历方法最适合。
前序
中序
后序
层次
35.一棵有124个叶结点的完整叉树，最多有个结点。
247
248
249
250
36.设a、b为一棵二叉树上的两个结点。
在中序遍历时，a在b前面的条件是
a在b的右方
a在b的左方
a是b的先人
a是b的后辈
在一棵具有n个结点的完全二叉树中，分枝结点的最大编号
为。
（（n+1）／2）下限取整
（（n-1）／2）下限取整
（n／2）下限取整
（n／2）上限取整
38.在N个结点的线索二叉树中，线索的数目为。
N-1
N
N+1
2N
39.
设深度为K的二叉树上只有度为
0和2的结点，则这种二叉树上所含
的结点总数最少为
。
A）
K+1
B）
2K
C）
2K-1
D）
2K+1
40.设有13个值，用它们构成一棵哈夫曼树，则该哈夫曼树共有个
结点。
13
12
26
25
41.以下说法错误的选项是。
存在这样的二叉树，对它采纳任何次序遍历其结点接见序列均相
同
二叉树是树的特别情况
由树变换成二叉树，其根结点的右子树老是空的
在二叉树只有一棵子树的状况下也要明确指出该子树是左子树还是右子树
42.若二叉树是则从二叉树的任一结点出发到根的路径上所经过的结点序列按其重点字有序。
二叉排序树
哈夫曼树
堆
退化二叉树
一棵有n个结点的二叉树，按层次从上到下，同一层从左到右的次序
储存在一维数组A[1．．n）中，则二叉树中第i个结点（i从1开始用上述方
法编号）的右孩子在数组A中的地点是。
A）A[2i]
（2i
≤n
B）A[2i+1）（2i+1
≤n）
A[i/2]
条件不充分，没法确立
44.
将有关二叉树的看法推行到三叉树，则一棵有
244个结点的完整三叉
树的高度是
。
A）
4
B）
5
C）
6
D）
7
45.
以下有关二叉树的说法正确的选项是
。
A）
二叉树的度为
2
B）
一棵二叉树度可以小于2
C）
二叉树中最少有一个结点的度为
2
D）
二叉树中任一个结点的度都为
2
46.
某二叉树中序序列为
ABCDEFG，后序序列为
BDCAFGE，则前序序列
是
。
，
EGFACDB
EACBDGF
EAGCFBD
上边的都不对
47.对二叉排序树进行遍历，可以获得该二叉树所有结点构成的排序序列
前序
中序
后序
按层次
48.的遍历仍需要栈的支持。
前序线索树
中序线索树
后序线索树
层次遍历
在一棵深度为h的完全二叉树中，所含结点的个数不小
于。
2h
h+1
2
2h-1
h-1
2
50.在一棵拥有n个结点的二叉树第i层上，最多拥有个结点。
i
2
2i+1
2i-1
n
2
51.树最适合用来表示。
有序数据元素
无序数据元素
元素之间拥有分支层次关系的数据
元素之间无联系的数据
52.以下说法错误的选项是。
一般在哈夫曼树中，权值越大的叶子离根结点越近
B）哈大曼树中没有度数为1的分支结点
C）若初始丛林中共有n棵二叉树，最后求得的哈夫曼树中共有
2n-1
个结
点
若初始丛林中共有n棵二叉树，进行2n-1次合并后才能剩下最后的哈夫曼树
53.以下说法错误的选项是。
二叉树可以是空集
二叉树的任一结点都可以有两棵子树
二叉树与树拥有相同的树形构造
二叉树中任一结点的两棵子树有次序之分
某二叉树的前序序列和后序序列正好相反，则该二叉树必定是的二叉树。
A）
空或只有一个结点
B）
任一结点无左子树
C）
高度等于其结点数
D）
任一结点无右子树
55.
设无向图的极点个数为
n，则该无向图最多有
条边。
A）
n-1
B）
n（n-1）/2
C）
n（n+1）/2
D）
0
E）
2
n
56.
采纳毗邻表储存的图，其深度优先遍历近似于二叉树的
。
A）
中序遍历
B）
先序遍历
C）
后序遍历
D）
按层次遍历
57.
采纳毗邻表储存的图，其广度优先遍历近似于二叉树的
。
A）
按层次遍历
B）
中序遍历
C）
后序遍历
D）
先序遍历
，
58.
一个图中包含有七个连通重量，若按深度优先
（DFS）遍历,一定调用
次深度优先遍历算法。
k
1
k-1
k+1
以下说法中不正确的选项是
A）
无向图中的极大连通子图称为连通重量
B）
连通图的广度优先搜寻中一般要采纳队列来暂存刚接见过
的极点
C）
图的深度优先搜寻中一般要采纳栈来暂存刚接见过的极点
D）
有向图的遍历不行采纳广度优先搜寻方法
60.
拥有n个极点的有向图最多有
条边。
n
n（n-1）
n（n+1）
n2
在有向图G的拓扑序列中，若极点Vi在极点Vj从前，则以下状况下
不行能出现的是
。
A）
G中有弧
B）
G中有一条从Vi到Vj的路径
C）
G中没有弧
D）
G中有一条从Vj到Vi的路径
62.
一个n个极点的连通无向图，其边的个数最少为
。
A）
n-1
B）
n
C）
n+l
D）
nlog2n
63.
以下说法中，正确的有
。
最小生成树也是哈夫曼树。
最小生成树唯一
C）
普里姆（Prim）最小生成树算法时间复杂度为
2
O（n）
克鲁斯卡尔（Kruskal）最小生成树算法比普里姆算法更适合于边
浓密的网
判断一个有向图能否存在回路，除了可以利用拓扑排序的方法外，还
可以利用。
A）求重点路径的方法
B）求最短路径的Dijkstra方法
C）深度优先遍历算法
D）广度优先遍历算法
65.在一个拥有n个极点的有向图中，若所有极点的出度之和为s，则所
有极点的入度之和为。
A）s
B）s-1
C）
s+l
D）
n
66.在一个无向图中，若两个极点之间的路径长度为的极点数为。
k条边，则该路径上
k
k+l
k+2
2k
一个有n个顶点的无向连通图，它所包含的连通分量个数
为。
0
1
n
n+1
关于一个有向图，若一个极点的入度为k1、出度为k2，则对应毗邻表
中该极点单链表中的结点数为。
kl
k2
k1-k2
k1+k2
关于一个有向图，若一个极点的入度为k1、出度为k2，则对应逆毗邻
表中该极点单链表中的结点数为。
kl
k2
k1-k2
k1+k2
70.关于一个无向图，下边的说法是正确的。
每个极点的入度等于出度
每个极点的度等于其入度与出度之和
每个极点的入度为0
每个极点的出度为0
为了方便地对图状构造的数据进行存取操作，则此中数据储存构造宜
采纳。
次序储存
链式储存
索引储存
散列储存
72.设有一个按各元素的值排好序的线性表且长度大于2，对给定的值
分别用次序查找法和二分查找法查找一个与K相等的元素，比较次数分别
是s和b：
在查找不行功的状况下，正确的s和b的数目关系是。
A）总有s=b
B）总有s>b
X，
C）总有sD）与K值大小有关
73.若在线性表中采纳折半查找法查找元素，该线性表应当
。
元素按值有序
采纳次序储存构造
元素按值有序，且采纳次序储存构造
元素按值有序，且采纳链式储存构造
74.假设有k个重点字互为同义词，若用线性探测法把这
散列表中，最少要进行次探测。
k个重点字存入
k-1次
k次
k+1次
k（k+1）／2次
75.
设散列地址空间
0～m-1，k为重点字，用
p去除k，将余数作为
k的
散列地址（h（k）=k%p）
，为了减少发生矛盾的可能性，
一般取P为
。
A）
小于m的最大奇数
B）
小于m的最大素数
C）
小于m的最大偶数
D）
小于m的最大合数
设散列表的长m=14，散列函数为h（k）=k%11，表中已有4个记录（如图
所示）假如用二次探测再散列来办理矛盾，则重点字为49的记录其储存地址是。
0
123
4
56
789
101112
13
15386184
图散列表
8
3
5
9
从拥有n个结点的二叉排序树中查找一个元素时，最坏状况下的时间
复杂性。
A）
O（n）
B）
O
（1）
C）
O（log2n）
D）
2
O（n）
78.
下边关于二叉排序树论述中，错误的选项是
。
当所有结点的权值都相等时，用这些结点构造的二叉排序树除根结点外只有右子树
中序遍历二叉排序树的结点便可以获得排好序的结点序列
任一二叉排序树的均匀查找时间都小于用次序查找法查找相同结点的线性表的均匀查找时间
对两棵拥有相同重点字会集而形状不一样的二叉排序树，按中序遍历获得的序列是相同的
79.以下说法错误的选项是。
散列法储存的基本思想是由重点码值决定数据的储存地址
散列表的结点中只包含数据元素自己的信息，不包含任何指针
装填因子是散列法的一个重要参数，它反响了散列表的装填程度
散列表的查找效率主要取决于散列表造表时采纳的散列函数和
办理矛盾的方法
设有一个用线性探测法解决矛盾获得的散列表以以下图
0
1
2
3
4
5
6
7
8
9
10
13
25
80
16
17
6
14
图
散列表
散列函数为
H=％11，若要查找元素
14，探测的次数是
。
8
9
3
6
假如要求一个线性表既能较快地查找，又能适应动向变化的要求，则
可采纳的查找方法是。
分块查找
次序查找
折半查找
基于属性查找
有数据{53，30，37，12，45，24，96}，从空二叉树开始逐一插入数
据来形成二叉排序树，若希望高度最小，则应选择下边哪个序列输入。
45,24,53，12,37,96,30
37,24,12,30,53,45,96
12,24,30,37,45,53,96
30,24,12,37,45,96,53
83.建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排
序树此后，查找元素35要进行元素间的比较
4次
5次
7次
10次
在次序表（n足够大）中进行次序查找，其查找不行功的均匀长度
是。
（n+1）／2
n／2+l
n
n+l
85.对线性表进行二分检索时，要求线性表一定。
以次序储存方式储存
以链式储存方式储存
以次序储存方式储存且数占有序
以链式储存方式储存且数占有序
在一棵深度为h的拥有n个元素的二叉排序树中，查找所有元素的最长查找长度
n
log2n
（h+1）／2
h
87.在散列查找中，均匀查找长度主要与有关。
散列表长度
散列元素个数
装填因子
办理矛盾方法
若依据查找表建立长度为m的散列表并采纳二次探测办理矛盾，假设
对—个元素第一次计算的散列地址为d，则第四次计算的散列地址
为。
（d+1）％m
（d-1）％m
（d+4）％m
（d-4）％m
89.以下说法正确的选项是。
数字解析法需早先知道所有可能出现的键值及所有键值的每一位上各数字分布状况，并且键值的位数比散列地址的位数多
除余法要求早先知道所有键值
平方取中法需要早先掌握键值的分布状况
随机数法合用于键值不相等的场合
90.分块查找的时间效率。
低于二分查找
高于次序查找而低于二分查找
高于次序查找
低于次序查找而高于二分查找
91.在一个拥有n个结点的单链表中查找值为m的某结点，若查找成功，
则均匀比较个结点。
n
n／2
（n-1）／2
（n+1）／2
92.以下序列不是堆的是。
（100,85,98,77,80,60,82,40,20,10,66）
（100,98,85,82,80,77,66,60,40,20,10,）
（10,20,40,60,66,77,80,82,85,98,100）
（100,85,40,77,80,60,66,98,82,10,20,）
在文件“局部有序”或文件长度较小的状况下，最正确内部排序方法是
直接插入排序
冒泡排序
简单项选择择排序
合并排序
94.在以下算法中，算法可能出现以下状况：
在最后一趟开始从前，所有的元素都不在其最后的地点上。
堆排序
冒泡排序
插入排序
快速排序
从未排序的序列中挨次拿出一个元素与已排序序列中的元素挨次进行
比较，而后将其放在排序序列的适合地点，该排序方法称为排序法。
插入
选择
希尔
二路合并
96.下边给出的四种排序法中，排序是不稳固排序法。
插入
冒泡
二路合并
堆
97.快速排序在最坏状况下时间复杂度是O（n2），比的性能差。
堆排序
冒泡排序
选择排序
二路合并
对给出的一组重点字{14，5，19，20，11，19}。
若按重点字非递减排
序，第一趟排序结果为{14，5，19，20，11，19}，问采纳的排序算法是。
简单项选择择排序
快速排序
希尔排序
二路合并排序
就排序算法所用的辅助空间而言，堆排序、快速排序、合并排序的关
系是。
堆排序<快速排序<合并排序
堆排序<合并排序<快速排序
堆排序>合并排序>快速排序
堆排序>快速排序>合并排序
巳以上答案都不对
100.假设某文件经过内部排序获得27个初始合并段，若要使多路合并3
趟完成，则应取合并的路数为。
2
3
4
5
101.下边排序方法中，重点字比较次数与记录的初始摆列没关的是。
希尔（Shell）排序
冒泡排序
直接插入排序
直
升级会员 