数据结构试题（含答案）

本文格式为Word版，下载可任意编辑——数据结构试题（含答案）

一．是非题

（正确的打“√〞，错误的打“×〞。）1.数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系，

P是对D的基本操作集。×

2.线性表的链式存储结构具有可直接存取表中任一元素的优点。×3.字符串是数据对象特定的线性表。

4.二叉树是一棵结点的度最大为二的树。×

5．邻接多重表可以用以表示无向图，也可用以表示有向图。×6．可从任意有向图中得到关于所有顶点的拓扑次序。×7．一棵无向连通图的生成树是其极大的连通子图。×8．二叉排序树的查找长度至多为log2ｎ。×

．对于一棵m阶的B-树.树中每个结点至多有m个关键字。除根之外的所有非终端结点

至少有┌m/2┐个关键字。×

10．对于目前所知的排序方法，快速排序具有最好的平均性能。

11.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。×12.二维数组是其数据元素为线性表的线性表。

13.连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。×14.折半查找不适用于有序链表的查找。15.完全二叉树必定是平衡二叉树。

16.中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。17.队列是与线性表完全不同的一种数据结构。×18.平均查找长度与记录的查找概率有关。

19.二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特别情形。×

20.算法的时间繁杂性越好，可读性就越差；反之，算法的可读性越好，则时间繁杂性就越差。×

二．选择题

1.若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到(e)的序列。a:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,1

2.递归程序可借助于(b)转化为非递归程序。

a:线性表b:栈c:队列d:数组

3.在以下数据结构中(c)具有先进先出（FIFO）特性，

(b)具有先进后出(FILO）特性。

a:线性表b:栈c:队列d:广义表

4.对字符串s=’data-structure’执行操作replace(s,substring(s,6,8),’bas’)

的结果是(d)。

a:‘database’b:‘data-base’c:‘bas’d:‘data-basucture’

5.设有二维数组A5x7,每一元素用相邻的4个字节存储，存储器按字节编址。

已知A的起始地址为100。则按行存储时，元素A06的第一个字节的地址是（d）按列存储时，元素A06的第一个字节的地址是（a）a:220b:200c:140d:124

6.对广义表A=（（a,(b)）,(c,()),d）执行操作gettail(gethead(gettail(A)))的结果是：（b）。a:（）b:（（））c:dd:(d)

7．假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7,19,22,6,32,14。若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右），则频率为7的字符编码是（g），频率为32的字符编码是（c）。

a:00b:01c:10d:11e:011f:110g:1110h:1111

8.对二叉排序树（b）可得到有序序列。

??a:按层遍历b:前序遍历c:中序遍历d:后序遍历

9．已知某树的先根遍历次序为abcdefg，后根遍历次序为cdebgfa。

若将该树转换为二叉树,其后序遍历次序为（d）。

a:abcdefgb:cdebgfac:cdegbfad:edcgfba

10．对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子,其位序是(d)。

编号为n的结点若存在双亲,其位置是(a)。

a:n/2b:2nc:2n-1d:2n+1e:nf:2(n+1)

11．关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点（c）的路径。

a:弧的数目最多b:弧的数目最少c:权值之和最大d:权值之和最小

12.哈希表的查找效率取决于（d）。

a:哈希函数b:处理冲突的方法。c:哈希表的装填因子。d:以上都是13．从规律上可以把数据结构分成(c)。

A.动态结构和静态结构B.顺序组织和链接组织

C.线性结构和非线性结构D.基本类型和组合类型

14．在计算递归函数时，如不用递归过程，应借助于(b)这种数据结构。

A.线性表B.栈C.队列D.双向队列

15．若已知某二叉树的中序和后序遍历序列分别BCAEFD和CBFEDA，则该二叉树的先序

序列为(a)。

A.ABCDEFB.ABDCEFC.ABDCFED.ACBDFE

16．当待排序序列的关键字次序为倒序时，若需为之进行正序排序，以下方案中(d)为佳。A.起泡排序B.快速排序

C.直接插入排序D.简单项选择择排序

17．若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，

则该二叉树是(c)。

A.二叉排序树B.赫夫曼树C.堆D.平衡二叉树

18．下图所有可能的拓扑序列有(b)种。

A.2B.3C.4D.5

19．以下排序算法中，(d)算法可能会出现：初始数据为正序时，花费的时间反而最多。

A.堆排序B.起泡排序C.归并排序D.快速排序

20．右图为一棵3阶B-树。20，25在该树上插入元素15

后的B-树是(c)。10,142135

A.15,25B.20,25

10,1420,213510,1415,2135

C.20D.14,25

142510,1520,2135

10152135

21．设森林F中有三棵树，第一、其次和第三棵树的结点个数分别为m1、m2和m3，则与

森林F对应的二叉树根结点的右子树上的结点个数是(d)。

A.m1B.m1+m2C.m3D.m2+m3

22.根据插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序树。

图（a）是最终变化的结果。

若仍以该插入次序建立平衡二叉树。图（c）是最终变化的结果。

8080

70907590

607585100607085100

7211072110a:b:

9090

7510080100

7080110757085110

6072856072c:d:

23.设输入序列为20,45,30,89,70,38,62，19依次插入到一棵2-3树中(初始状态为空)，该B-树为（b）。再删除38，该B-树为（f）。

（3062）（45）

（19，20）（3845）（70，89）（30）（70）

（1920）（38）（62）（89）

a:b:

（4570）（45）

（20）（62）（89）（20）（70）

（19）（30）（19）(30,38）（62）（89）

c:d:

（3070）（45）

（19，20）（4562）（89）（20）（70）

（19）（30）（62）（89）

e:f:

24．已知一组待排序的记录关键字初始排列如下：45,34,87,25,67,43,11,66,27,78。(g)是快速排序法一趟排序的结果；

(a)是希尔排序法（初始步长为4）一趟排序的结果；(b)是初始堆（大堆顶）；

(d)是基数排序法一趟排序的结果。

A．27,34,11,25,45,43,87,66,67,78B．87,78,45,66,67,43,11,25,27,34C．11,43,34,25,45,66,27,67,87,78D．11,43,34,45,25,66,87,67,27,78E．34,45,25,67,43,11,66,27,78,87F．87,45,11,25,34,78,27,66,67,43G．27,34,11,25,43,45,67,66,87,78H．34,11,27,25,43,78,45,67,66,87

25．若有序表中关键字序列为：14，20，25，32，34，45，57，69，77，83，92。对其进行

折半查找，则在等概率状况下，查找成功时的平均查找长度是(c)。查找32时需进行(c)次比较。

A.1B.2C.3D.426.设一棵二叉树BT的存储结构如下:

12345678lchild23006000dataAB