数据结构习题集(答案).docx

该【数据结构习题集(答案) 】是由【森林书屋】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【数据结构习题集(答案) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构****题
第一章
绪论
数据结构是一门研究非数值计算的程序设计问题中计算机的
___①__以及它们之间的__②_
和运算等的
学科。
①



②



算法分析的目的是
___①__,算法分析的两个主要方面是
__②___
。
①



以求该进

②




计算机算法指的是
__①__,它必须具备输入、输出和
__②_等5
个重要特性。
①




②
、可移植性和可扩展性
、可移植性和有穷性
、有穷性和可行性
、稳定性
和安全性
数据元素是数据处理的
基本单位;数据项是数据处理的
_最小单位。
数据结构是研究数据的
逻辑结构___和__物理结构__,并对这种结构定义相适应的运算,设计出相应的算
法,分析算法的效率。算法的效率包括时间和空间两个方面,分别称为
_空间复杂度和时间复杂度。数据
的逻辑结构是指_数据元素之间的关系
__;包括线性结构、
树形结构和图形结构
三种类型,其中树形结
构和图状结构合称为
__非线性结构__。
线性结构中元素之间存在
_一对一___
关系,树形结构中元素之间存在
_一对多___
关系,图状结构中元
素之间存在__多对多__关系。
数据结构
在计算机中的表示称为数据的物理(或存储)结构,数据的物理结构可以采用
_顺序存储和_
链式存储__两种存储方法。
顺序存储方法是把逻辑上
相邻的元素
存储在物理位置
相邻的内存单元中
;链式存储方法中元素间的关
系是由__指针来表示_的。
第二章
线性表
链表不具备的特点是
____。




不带头结点的单链表
head为空的判定条件是____。
==null
->next==null
->next==head
!=null
带头结点的单链表
head为空的判定条件是____。
==null
->next==null
->next==head
!=null
非空的循环单链表
head
的尾结点(由
p所指向)满足____。
->next==null
==null
->next==head
==head
在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是
____。
(1)
(n)
2
2
(n)
(nlogn)
线性链表中各个结点之间的地址
不一定
连续。
线性表中数据元素之间具有
__一对一__,除第一个和最后一个元素外,其他数据元素有且只有
_一个后继
和前趋。
若频繁地对线性表进行插入和删除操作,该线性表采用 链式

存储结构比较合适。
在一个单链表中 p所指结点之后插入一个 s所指结点时,应执行

s->next=_p->next_和

p->next=_s_的操作。
已知具有

n个元素的一维数组采用顺序存储结构,

每个元素占

k个存储单元,第一个元素的地址为

LOC(a1),
那么,

LOC(ai)=__LOC(a1)+(i-1)

*k_。
若线性表采用顺序存储结构,

每个数据元素占用

3个存储单元,第

11个数据元素的存储地址为

130,则
第1个数据元素的存储地址是

100 。
若线性表采用顺序存储结构,线性表的最大长度为

1000,每个数据元素占

3个存储单元,则要分配给该
线性表

_3000__存储单元,若第一个数据元素的存储地址是

2000,则第

11个元素的存储地址是

__2030__。
以head为头结点循环双链表为空时,应满足

head->llink=head

,head->rlink=head

。
在单链表中,指针

p指向元素为

x的结点,实现“删除x的后继”的语句是

。
=p->next;

>next=p->next->next;
>next=p;

=p->next->next;
在单链表中,已知q指的结点是

p指的结点的直接前驱结点,

若在q和p指的结点之间插入一个由

s指的结点,
则需执行

________。
->next=p->next;p->next=->next=s->next;s->next=p

->next=s;s->next=p
>next=s;s->next=q
用链表表示线性表的优点是()





下面关于线性表的叙述中,错误的是()
线性表采用顺序存储必须占用一片连续的存储单元
线性表采用顺序存储便于进行插入和删除操作
线性表采用链式存储不必占用一片连续的存储单元
线性表采用链式存储便于进行插入和删除操作线性表是具有n个()的有限序列
A. 数据项 C. 表元素
长度为n的线性表采用链式存储结构,访问其第 i个元素的算法时间复杂度为()
A. O(1) (n) C. O(n2) (log2n)
在长度为 n的顺序表删除第 i(1≤i≤n)个元素,则需要向前移动元素的次数为()
A. i

-i

C. n-i+1
在长度为

n的顺序表中第

i(1≤i≤n)个位置上插入一个元素时,

为留出插入位置所需要移动元素的次数
为()
A. n-i

B. i

C. n-i-1

-i+1
以下对单链表的叙述错误的是()
单链表中的每一个结点都由存放结点值的数据域和存放直接后继结点地址信息的指针域两部分组
成
,

以下记叙中正确的是 ()
线性表的链式存储结构优先于顺序存储结构
线性表的存储结构不影响其各种运算的实现
选择线性表的存储结构就是要保证存储其各个元素的值
,链式存储属于动态结构
第三章

栈与队列
一、选择题
栈的特点是___B_


,队列的特点是 ___A_


。
栈和队列的共同点时

____。




一个栈的进栈序列是 a,b,c,d,e,则栈的不可能的输出序列是

____

。







判定一个栈

ST(最多元素

MaxSize)为空的条件是

____

。
>top!=-1

->top==-1
>top!=MaxSize

->top==MaxSize-1
判定一个栈

ST(最多元素

MaxSize)为栈满的条件是

____

。
>top!=-1

->top==-1
>top!=MaxSize

->top==MaxSize-1
循环队列用数组 A[0,m-1]存放其元素值,已知其头尾指针分别是

front

和

rear,则
当前队列中的元素个数是 ____。
A.(rear-front+m)%m

-front+1
-front-1

-front
在一个链队中,假设

f和

r

分别是队头和队尾指针,则插入一个

s结点的运算时

____。
->next=s;f=s;

->next=s;r=s;
->next=r;r=s;

->next=f;f=s;
在一个链队中,假设

f和

r

分别是队头和队尾指针,则删除一个结点的运算时

____。
=f->next;

=r->next;

=f->next;

=r->next;
若进栈序列为

a,b,c,进栈过程中允许出栈,则以下

_____是不可能得到的出栈序列。
,b,c

,a,c

,a,b

,b,a
一个最多能容纳 m个元素的顺序存储的循环队列
的条件是__________

Q,其头尾指针分别为

front

和rear,则判定该队列为满
A.+1)%m==

B.==
C.+1==

D.+1)%m==
一个最多能容纳 m个元素的顺序存储的循环队列
的条件是__________

Q,其头尾指针分别为

front

和rear,则判定该队列为空
A.+1)%m==

B. ==
C.+1==

D.+1)%m==
若进栈序列为 1,2,3,4,,进栈过程中可以出栈,则以下不可能的出栈序列是()
,4,3,2 ,3,4,1 ,1,4,2 ,4,2,1
一个队列的入队序列是 1,2,3,4,则队列的输出序列是 _____。
,3,2,1

,2,3,4

,4,3,2

,2,4,1
若用一个可容纳 6个元素的数组来实现循环队列,且当前
队和1次入队操作后 ,rear和front 的值分别为()
和0 和2 和5

rear

和

front

的值分别是

0和

4,当执行

2次出
第四章

串和数组
串是一种特殊的线形表,其特殊性体现在 ____


串的两种最基本的存储方式是 _顺序和链式___。
两个串相等的充分必要条件是 :长度相等_且_对应位置上的字符相等

__。
如下陈述中正确的是______。



不含任何字符的串称为 __空串_,其长度为_长度等于零__。
设有字符串 S=“ABC123XYZ”,问该串的长度为()
.10

C
已知二维数组 A[m][n]采用行序为主方式存储,每个元素占 k个存储单元,并且第一个元素的存储地址是
LOC(A[0][0]),则A[i][j]的地址是__loc(a[0][0])+(n*i+j)*k 。
二维数组有两种存储方式,第一种是以 _行为主序的存储方式,第二种是以 _列_为主序的存储方式。设有
二维数组 A[10][20],其中每个元素占 2个字节,数组按行优先顺序存储,第一个元素的存储地址为 100,
那么元素 A[8][12]的存储地址为 __100+(20*8+12)*2
对于稀疏矩阵的压缩存储, 通常用一个三元组表示非零元素的信息, 其中包括非零元素的 值、行、列 。
这些信息可用一个 三元组 数组表示,也称此为 三元组顺序表 。
设有一个10阶的对称矩阵 A,采用压缩存储方式,以行序为主序存储, a0,0为第一个元素,其存储地址为
1,每个元素占

1个字节,则

a8,5的地址为

__________。







第五章 树与二叉树
采用二叉链表存储结构,具有n个结点的二叉树中,一共有_2n_个指针域,其中有__n-1_个指针域指向孩子结点,有_n+1_个指针域为空.
一棵非空二叉树 ,其第i层上最多有_2i-1__结点。
满二叉树是一棵深度为 k且恰有_2k-1___结点的二叉树.
一棵哈夫曼树有个
m叶子结点,则其结点总数为_2m-1__.
三个结点的二叉树,最多有
_5__种形状。
将一棵完全二叉树按层次编号
,对任一编号为i的结点有:如有左孩子,则其编号为__2i_;如有右孩子,则其
编号为_2i+1.
深度为k的非空二叉树最多有2k-1个结点,最少有k个结点,其第i层最多有_2i-1
个结点。
树最适合用来表示____。




在下列存储形式中,不是树的存储形式的是
____。




一棵高度为h的满二叉树中结点的个数为
____。

-1
C.
2h-1
+1
已知一棵二叉树的先序遍历序列为
ABCDEFG,中序遍历序列为
:CBDAFEG,则该二叉树的后序遍历序列是
().




具有100个结点的完全二叉树,其中含有
__________个度为
1的结点。



已知一棵二叉树的先序遍历序列为
EFHIGJK,中序遍历序列为:HFIEJGK,则该二叉树的右子树的根是
().




如下左图所示二叉树的中序遍历序列是
____



一棵二叉树如上右图所示,其中序遍历的序列为


____

在非空二叉树的中序遍历序列中,二叉树的根结点的左边应该

(

)




在一非空二叉树的中序遍历序列中,根结点的右边应该 ____。


有一棵树如下左图所示,回答下列问题:
⑴这棵树的根结点是 _k1___;
⑶结点k3的度为_2___;
⑸这棵树的深度为 _4__;

⑵这棵树的叶子结点是
⑷这棵树的度为 _3___
⑺结点k3的孩子结点是

_k2,k4,k5,k7___
_k5,k6_
⑻结点

k3的双亲结点是
由上右图所示的二叉树,回答以下问题。
⑴其中序遍历序列为 ____ ⑵其先序遍历序列为 ____
⑶其后序遍历序列为 ____ (4)该二叉树对应得森林是 ____
某二叉树的先序遍历序列为 abdgcefh,中序遍历序列是 dgbaechf,请画出该二叉树并给出其后序遍历序列。
gdbehfca
如下左图所示 ,以数据集
路径长度为_165___。

{4,5,6,7,10,12,18}为结点权值所构成的二叉树为

_哈夫曼树

___,其带权
对如上右图所示的树,该树的高度为
__________,该树的度为__________,结点E的层次为__________,
结点H的双亲为__________,结点H的兄弟为__________,结点B的度为__________。
若二叉树中度为2的结点有
15个,该二叉树则有
16个叶结点。
若深度为6的完全二叉树的第
6层有3个叶结点,则该二叉树一共有
34个结点。
二叉树的前序遍历序列为A,B,C,E,F,D,G,H,中序遍历序列为
A,E,C,F,B,G,D,H,其后序
遍历序列为
。
一个深度为k的二叉树,当具有
2k-1个结点时称之为_满二叉树。
下面关于哈夫曼树的说法,不正确的是()



1的结点

1的结点外,还有度为
2的结点和叶结点
在如图所示的表达式二叉树中,按中序遍历得到的序列为
__________。
第六章
图
一个具有n个顶点的无向连通图至少有
_n-1___条边,所有顶点的度数之和等于所有边数的2_倍。

在有向图的邻接矩阵中,第
i行中1的个数为第i个顶点的_出度__。第i列中1
的个数为第i个顶点
的_入度__。

一个无向图有n个顶点和e条边,则所有顶点的度的和为
_2e。具有n个顶点的无向完全图的边数为
__n(n-1)/2__。具有n个顶点的有向完全图的弧个数为
__n(n-1)_。

设连通图G的顶点数为n,则G的生成树的边数为__n-1
。

若无向图中有e条边,则表示该无向图的邻接表中就有
_2e个结点。

Dijkstra算法是按_路径长序依次递增
__的次序产生一点到其余各顶点最短路径的算法。

可以进行拓扑排序的有向图一定是
_无环的_。在拓扑排序序列中第一个顶点一定是
__入度为零_的顶
点。
,画出该图的邻接表和邻接矩阵;写出从顶点A出发进行深度优先和广度优先搜索得到的顶点序列。
1
2
3
1
2
3
2
2
1
2
2
3
3
2
3
1
3
3
=(V,E),其中V={v1,v2,v3,v4 ,v5,v6,v7} ,E={(v1,v2),(v1,v3),(v2,v4),(v2,v5),
(v3,v6),(v3,v7),(v6,v7)},画出该无向图,画出其邻接表和邻接矩阵,写出从顶点v1出发进行深度优先和广度优先搜索得到的顶点序列。
=(V,E),其中V={v1,v2,v3,v4 ,v5,v6},其邻接矩阵如上右图所示:
画出该无向图;
画出其邻接表和邻接矩阵;
写出从顶点v1出发进行深度优先和广度优先搜索得到的顶点序列;
分别用Prim和Kruskal算法,从顶点v1顶点出发,写出求该网的最小生成树的产生过程。
=(V,E),其中V={a,b,c,d,e,f} ,
E={<a,b>,<a,d>,<a,e>,<d,e> ,<e,b>,<c,b>,<c,e>,<c,f>,<f,e>}
画出该图;
画出其邻接矩阵和邻接表;
写出从顶点a出发进行深度优先和广度优先搜索得到的顶点序列;
对如下无向图,分别用Prim和Kruskal算法,分别从顶点1和顶点a出发,写出求该网的最小生成树的产生过程。
11
6
②
4
④
3
21
2
①
6⑤
19
⑦
7
③
10
8
10
⑥
对下图,写出拓扑有序序列
B
E
2
5
A
D
1
4
a
C
F
6
3
1
算法求出从源点A到其余各顶点的最短路径及其长
对下图所示的带权有向图,利用Dijstra
度。
1
A
1
1

25
B
E
10
2
16
7
5
12
3
D
10
2
4
4
C
F
3
8
第七章 查找
用顺序查找法在具有n各结点的线性表中查找一个结点所需的平均查找时间为( )。
AO(n)
(nlog2n)
(n)
(log2n)
使用折半查找,线性表必须(
)。
A、一顺序方式存储
B、以链式方式存储,且元素已按值排好序
C、以链式方式存储
D、以顺序方式存储,且元素已按值排好序
采用顺序查找法查找长度为
n的线性表时,每个元素的平均查找长度为
____。

C.(n+1)/2
D.(n-1)/2
顺序查找法适合于存储结构为
____的线性表。




采用折半查找法查找长度为
n的线性表时,每个元素的平均查找长度为
____。
2
(nlogn)
(n)
(logn)
(n)
2
2
采用顺序查找法检索长度为
n的线性表,则检索每个元素的平均比较次数为
_n-i+1_。
有一个有序表为:
(1,3,9,12,32,41,45,62,75,77,82,95,100),当折半查找值
82的结点时,经过__________次比
较后查找成功。




折半查找有序表{6,15,30,37,65,70,72,89,99},若要查找元素37,需要依次与表中元素____进行比较。
,15,37
,30,37
,15,30
,15,30,37
已有序表为(
20,18,24,35,47,50,62,83,90,115,134),当用折半法查找
90时,需要进行_2_
次查找可确定成功。查找
47时需进行_4_
次查找可确定成功,查找
100时,需进行_4__次查找才能确定
不成功。
按序列{60,17,38,40,7,32,73,65,85}的输入顺序建立一颗二叉排序树.
1)画出该二叉排序树;
2)在(1)的基础上插入结点80后,画出对应的二叉排序树;
在(2)的基础上删除结点38后,画出对应的二叉排序树。
按序列(53,49,26,78,63,35,19,99)的输入顺序建立一颗二叉排序树.
1)画出该二叉排序树;
2)在(1)的基础上插入结点50后,画出对应的二叉排序树;
在(2)的基础上删除结点26后,画出对应的二叉排序树。
已知一组关键字序列为( 75,33,52,41,12,88,66,27),请按哈希函数 H(key)=keyMOD7,分别
用线性探测和二次探测处理冲突方法构造一个表长为 10的哈希表。
已知一组关键字为( 17,12,21,01,66,35,82,37),请按哈希函数
性探测和二次探测处理冲突方法构造一个表长为 14的哈希表。

H(key)=keyMOD13,分别用线
已知:哈希表长为 10,哈希函数 H(key)=keyMOD9,给出关键字序列为(

23,45,14,17,9,29,37,
,25,41,33),采用链地址法解决冲突,请画出哈希表。
第八章 排序
对于给定的12个整数:23,37,7,79,29,43,73,19,31,61,23,47,分别写出用直接插入序、冒泡和直接选择、快速、归并排序的各趟结果。
排序可分为

__________和_____________两类;衡量排序算法的两个主要性能指标分别是

:______________、
______________。
假设待排序数据元素序列为

[

4,6,3,2,5

],应用快速排序方法按递增序排序,得到第一次划分后
的结果为_[2_3_4_6_5_]。