数据结构试题和答案

A卷

一、填空题 （共 8 小题，每空 1 分，共计 20 分）

1． 栈和队列都是_线性_结构；对于栈只能在_栈顶_插入和删除元素；对于队列只能在_队尾_插入元素和在_队头_删除元素。

2．一个广义表中的元素分为 单 元素和 表 元素两类。

3．对于一个长度为n的顺序存储的线形表，在表头插入元素的时间复杂度为__ O(n)_______，在表尾插入元素的时间复杂度为____ O(1)_______。

5．在一棵具有n个结点的二叉树中，所有结点的空子树个数等于 n+1 。 6．若一个图的顶点集为{a,b,c,d,e,f},边集为{（a,b）,(a,c),(b,c),(d,e)},则该图含有___3____个连通分量。

7．在进行直接插入排序时，其数据比较次数与数据的初始排列__有___关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__无___关。

8．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为（15，02，21，24，26，57，43，66，80，48，73）。 9. 在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为__2___。

10.在线形表的散列存储中，处理冲突有 开放定址法 和 链地址法 两种方法。

11. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有______12______ 个叶子的结点。

12. 设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二叉树中叶子结点是_ E,F,H ___。

13．若由3，6，8，12，10作为叶子结点的值生成一棵哈夫曼树，则该树的高度为 4 ,带权路径长度为 87 。

二、选择题 （共 15小题，每题 1 分，共计 15 分） 1．算法指的是（ D ）

A．计算机程序 B．解决问题的计算方法

C．排序算法 D．解决问题的有限运算序列 2．如下陈述中正确的是（A ）

A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串

3．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ B ）

A．3，2，6，1，4，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( B ) A． s->next=p；p->next=s B． s->next=p->next；p->next=s C． s->next=p->next；p=s D． p->next=s；s->next=p 5．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ A ） A．队列 B．栈 C．线性表 D．有序表 6．图的邻接矩阵表示法适用于表示（ C ）

A．无向图 B．有向图 C．稠密图 D．稀疏图 7．深度为5的二叉树其结点数最多为 C 。 A、16； B、30； C、31； D、32。

8．设单循环链表中结点的结构为（data,next）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（ D ）

A． s=rear； rear=rear->next； delete s； B． rear=rear->next； delete rear； C． rear=rear->next->next； delete rear；

D．s=rear->next->next； rear->next->next=s->next； delete s； 9．线性表采用链式存储时，结点的存储地址（ B ） A．必须是不连续的 B．连续与否均可

C．必须是连续的 D．和头结点的存储地址相连续 10．线性链表不具有的特点是（A ）。

A．随机访问 B．不必事先估计所需存储空间大小

C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 11. 含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )

A．e B．2e C．n2－e D．n2－2e

12. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：

20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ D ）

A．选择排序 B．希尔排序 C．归并排序 D．快速排序

13. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的 D 。 A．先序遍历； B．中序遍历； C．后序遍历； D．按层遍历。

14. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为 C 。 A．1，2，5，4，3； B．1，2，3，4，5； C．1，2，5，3，4； D．1，4，3，2，5。

15.假定对元素序列（7，3，5，9，1，12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为 B 。

A．1，3，5，7，9，12； B．1，3，5，9，7，12； C．1，5，3，7，9，12； D．1，5，3，9，12，7。

三、 判断题 （对的打√，错的打× 共 15 小题，每题 1 分，共计 15 分） 1、在线性结构中，每个结点都有一个直接前驱和一个直接后继。（×）. 2、在堆中，以任何结点为根的子树仍然为堆。（√ ） 3、完全二叉树就是满二叉树。（ × ）

4、若将一棵树转换成二叉树，则该二叉树的根结点一定没有右子树（√ ）。 5、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存

储。（× ）

6、在AOE网中，关键路径是唯一的。(×)

7、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 (√ ) 8、连通分量是无向图中的极小连通子图。（ × ）

9、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（ × ） 10、在散列法中，一个可用散列函数必须保证绝对不产生冲突。（╳） 11、完全二叉树的某结点若无左孩子，则它必是叶结点。 (√ )

12、在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。（×） 13、栈和队列逻辑上都是线性表。 (√) 14、快速排序是一种稳定的排序方法。(× )

15、基数分类只适用于以数字为关键字的情形，不适用以字符串为关键字的情形（× ）。 四、算法填空题： 将折半查找的非递归算法中的空白处进行正确填写。

（每空2分，共计 10分）

int Search_Bin(SSTable ST,KeyType key)

{ int low=1； high=_ST.length_________； （1） While (__low<=high _____________) { (2) mid=_(low+high)/2________________； (3) if (EQ(key,ST.elem[mid].key ) return mid；

else if (LT(key,ST. elem[mid].key)) _ high=mid-1___________； (4) else __low=mid+1________________； (5) }

return 0； }// Search_Bin

五、 综合应用题 （每题10分，共计 40 分）

１．已知一个连通图的边集为｛（１，２）３，（１，３）６，（１，４）８，（２，３）４， （２，５）１０，（３，５）１２，（４，５）２｝，若从顶点V1出发, 求出此图的深度和广度优先遍历序列，按照普里姆算法求最小生成树并画出，写出依次得到的各条边．

1. 深度优先:1 2 3 5 4 2分 广度优先: 1 2 3 4 5 2分

普里姆算法依次得到的各边(1,2)3, (2,3)4, (1,4)8, (4,5)2 2分 最小生成树如图所示：

4分

２．一个待散列存储的数据集合为｛３２，７５，２９，６３，４８，９４，２５，４６，１８，７０，５６｝，散列地址空间为ＨＴ［１３］，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到得到的散列表，求平均查找长度．

0 1 2 3 4 5 6 7 8 9 1011 12 ＾ ＾ ＾ ＾ 94 6分 29 56 70 32 46 48 75 63 25 ＾ 18 ＾ ＾ ＾ ＾ ＾ ＾ ＾ ＾ 32 mod 13=6 75 mod 13=10 29 mod 13=3 63 mod 13=11 48 mod 13=9 94 mod 13=3 25 mod 13=12 46 mod 13=7 18 mod 13=5 70 mod 13=5 56 mod 13=4 2分 平均查找长度为：

ASL=(9*1+2*2)/10=13/11 2分

３．在一个空AVL树内，依次插入关键字(46,15,20,35,28,58,18,50,54) ，分别画出46，15，20，35插入完和所有关键字都插入完的AVL树。，并求出查找成功状态下的平均查找长度 （10分）

6 分

2分

平均查找长度：(1×1+2×2+4×3+2×4)/9=25/9 2分

4. 欲将无序序列（24, 79, 13, 36, 70, 96, 12, 10, 36*, 49, 100, 27）中的关键码按升序重新排列，请写出快速排序第一趟排序的结果序列。另外请画出堆排序（小根堆）的初始堆和结束堆。

①快速排序第一趟排序的结果序列为：

10， 12， 13， [24]， 70， 96, 36, 79, 36*, 49, 100, 27 （注意要按振荡式逼近算法实现） 5分

② 堆排序的初始堆如下，注意要从排无序堆开始，从最后一个非终端结点开始，自下而上调整,而且要排成小根堆！ 初始堆序列为：

10，24，12，79，49，27，13，36，36*, 70, 100, 96

24 79 13 36 70 96 12 10 36*49 100 27 无序堆 有序初始堆

4分

结束堆 1分

10 12 13 24 27 36 36* 49 70 79 96 100 10 24 12 79 49 27 13 36 36*70 100 96 B卷

一、填空题 （共 8 小题，每空 1 分，共计 20 分） 和 图状结构 4种。

2．链表最后一个结点的指针指向链表的头节点，这样的链表称为_循环_链表；链表的每个结点都有两个指针域，一个指针指向前一结点，另一个指针指向后一结点，这样的链表称为_双向_链表。

3．某二叉树结点的中序遍历序列为A，B，C，D，E，F，G，后序遍历序列为B，D，C， A，F，G，E，则该二叉树结点的前序遍历序列为__ E; A;C;B;D; G; F ___，该二叉树对应的树林包括___ 2 _____棵树。

5．按照锦标赛排序的思想，决出8个选手的名次排列，共需要进行___11___场比赛（考虑最坏的情况）。

6．Hanoi塔、求一个数的阶乘、二叉树遍历等类似问题的解决一般通过使用_递归_来解决。

1．数据的逻辑结构被分为 集合 、 线性结构 、 树形结构

7．在进行直接插入排序时，其数据比较次数与数据的初始排列__有___关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__无___关。

8．设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语

句是__ R->next =s ______；r=s; r->next=null;。

9. 在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为__2___。

10.在线形表的散列存储中，处理冲突有 开放定址法 和 链地址法 两种方法。 11. 在一棵二叉树中，第五层的结点数最多为 16 个。

12. 用冒泡法对n 个关键码排序，在最好情况下，只需做_____n-1________次比较和_______0_____ 次移动；在最坏的情况下要做______ n(n-1)/2 ___________次比较。

二、选择题 （共 15小题，每题 1 分，共计 15 分）

1．在数据结构的讨论中把数据结构从逻辑上分为 （ C）

A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构

2．算法分析的两个主要方面是（ A）。

A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性

3．一个非空广义表的表头（

D ）

A．不可能是子表 B．只能是子表

C．只能是原子 D．可以是子表或原子

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( B )

A． s->next=p；p->next=s B． s->next=p->next；p->next=s

C． s->next=p->next；p=s D． p->next=s；s->next=p 5．将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。

A． 栈

B． 队列

C． 循环队列 D． 优先队列

6．图的邻接矩阵表示法适用于表示（ C ）

A．无向图 B．有向图 C．稠密图 D．稀疏图 7．深度为5的二叉树其结点数最多为 C 。

A、16； B、30； C、31； D、32。

8．设单循环链表中结点的结构为（data,next）,且rear是指向

非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（D ） A． s=rear； rear=rear->next； delete s； B． rear=rear->next； delete rear； C． rear=rear->next->next； delete rear；

D．s=rear->next->next； rear->next->next=s->next； delete s；

9．线性表采用链式存储时，结点的存储地址（

B ）

A．必须是不连续的 B．连续与否均可

C．必须是连续的 D．和头结点的存储地址相连续

10．根据集合{25，30，16，48}，按照依次插入结点的方法生成一棵二叉搜索树，在等概率情况

下成功查找一个元素的平均查找长度为（ A ）

A． 2 B． 2.5 C．3 D． 4

11. 含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )

A．e B．2e C．n2－e D．n2－2e

12. 对线性表进行折半搜索时，要求线性表必须（ C ）

A． 以链接方式存储且结点按关键码有序排列 B． 以数组方式存储

C． 以数组方式存储且结点按关键码有序排列 D．以链接方式存储

A．选择排序 B．希尔排序 C．归并排序 D．快速排序 13. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在 已排序序列的合适位置，该排序方法称为(D )排序法。 A．二路归并 B．选择 C．shell D．插入

14. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为(C)。 A、1，2，5，4，3； B、1，2，3，4，5； C、1，2，5，3，4； D、1，4，3，2，5。 15. 在以下的叙述中，正确的是(B)。

A．线性表的线性存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出

三、 判断题 （对的打√，错的打× 共 15 小题，每题 1 分，共计 15 分）

1、单链表从任何一个结点出发，都能访问到所有结点。(×) 2、将一棵树转换成二叉树后，根结点没有左子树。 (× )

3、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 (√ ) 4、在树结构里，有且仅有一个结点没有前驱；非根结点有且仅有一个双亲，且存在一条从根到

该结点的路径（√ ）。

5、线性的数据结构可以顺序存储，也可以链接存储。非线性的

数据结构只能链接存储。（× ） 6、在AOE网中，关键路径是唯一的。(×)

7、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。 (√ ) 8、对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则

该图一定是完全图。（ × ）

9、在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧。（ × ）

10、在散列法中，一个可用散列函数必须保证绝对不产生冲突。（╳）

11、完全二叉树的某结点若无左孩子，则它必是叶结点。 (√ )

12、所谓平衡二叉树是指左右子树的高度差的绝对值不大于

1的二叉树。

（）

13、AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。 (×)

14、若一个栈的输入序列为

123…n，其输出序列的第一个元素为n，则

其输出序列的每个元素ai一定满足ai =n-i+1。(i=1,2,...,n)。(√ )

15、在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。（× ）。

四、算法填空题： 将折半查找的非递归算法中的空白处进行正确填写。

（每空2分，共计 10分）

int Search_Bin(SSTable ST,KeyType key)

{ int low=_______； high=ST.length； （1） While (low<=high) { (2) mid=_________________； (3) if (EQ(key,ST.elem[mid].key ) return __________；

else if (LT(key,ST. elem[mid].key)) __________________； (4) else __________________； (5) }

return 0； }// Search_Bin

五、 综合应用题 （每题10分，共计 40 分）

１．下图为某无向图的邻接表，分别写出从A出发深度优先搜索和广度优先搜索的结果，并画出该无向图的逻辑结构图。 1 2 3 4 5 6 7 8 9 10

深度优先搜索（DFS）结果为：AEBCFGDHIJ 广度优先搜索（BFS）结果为：AEBCGFDHIJ 这是有着4个连通分量的非连通图。

A E

B C F

G H I

D J

２．已知哈希表地址空间为0..14，哈希函数为H(k)=k mod 13，采用线性探测法处理冲突。将下面各数依次存入该散列表中，并求出在等概率下的平均查找长度和失败的查找长度。

A B C D E F G H I J ^ 5 3 2 1 3 2 9 8 8 ^ ^ ^ ^ ^ 7 6 3 ^ ^ 7 ^ 10 ^ 240, 29, 345, 1, 100, 20, 21, 35, 3, 208, 78, 99, 45, 350 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 208 78 350 29 3 240 mod 13=6 29 mod 13 =3

345 mod 13 =6 (冲突，地址7) 1 mod 13 =7 (冲突，地址8) 100 mod 13 =9

20 mod 13 = 7 (冲突，地址10) 21 mod 13 =8 (冲突，地址11) 35 mod 13 =12

3 mod 13 =3 (冲突，地址4) 208 mod 13 =0

78 mod 13 = 0 (冲突，地址1) 99 mod 13 = 8 (冲突，地址13) 45 mod 13 = 6 (冲突，地址14) 350 mod 13 =12 (冲突，地址2)

查找成功的ASL = 1/14*(1*5+2*4+4*2+6*2+9) = 3

查找失败的ASL = 1/14*(6+5+4+3+2+1+15+14+13+12+11+10+9) =7.5

240 345 1 100 20 21 35 99 45 ３．在一个空AVL树内，依次插入关键字(46,15,20,35,28,58,18,50,54) ，分别画出46，15，20，35插入完和所有关键字都插入完的AVL树。，并求出查找成功状态下的平均查找长度 （10分）

(1×1+2×2+4×3+2×4)/9=25/9

4. 判断以下序列是否为大根堆？若否，则按照教材中的算法将它们调整为大根堆，要求：画出调整后的堆结构图和相对应的序列(不要求过程)

1.(38,56,25,23,40,100,29,61,35,76,28,20) 2.(21,66,39,73,86,48,52,90,75,88) 3.(12,70,33,65,24,56,48,92,86,33,21)

(a) 否，100 76 38 61 56 25 29 23 35 40 28 20 (b) 否，90 88 52 75 86 48 39 73 66 21 (c) 否，92 86 56 70 33 33 48 65 12 24 21