《数据结构》试题及答案（A卷）

《数据结构》考试试卷（A卷）

班级：姓名：学号：分数：

题号二三四五七八九十总分

得分

评卷

人

单项选择题（每题2分，共30分）

（1）一个栈的入栈序列为1234,以下出栈序列不可能得到的是（）

A.1324B.2341

C.4312D.3421

（2）若一个二叉树具有10个度为2的结点，则度为0的结点的个数为（）

A.9B.10C.11D.不确定

（3）链式结构线性表的特点是：（）

A.便于随机存取B.花费的存储空间比顺序结构少

C.便于插入和删除1）.元素的物理顺序与逻辑顺序一致

（4）一个二叉树的前序遍历序为ABCDEFG,则中序遍历序可能是：（）

A.CABDEFGB.ABCDEFGC.DACEFBGD.EABCDFG

（5）树最适合用来表示（）。

A.有序数据元素B.无序数据元素

C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

（6）下列有关图遍历的说法中不正确的是：（）

A.连通图的深度优先搜索是一个递归过程。

B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征。

C.非连通图不能用深度优先搜索法。

D.图的遍历要求每一顶点仅被访问一次。

（7）若已知待排序序列基本有序，则效率最高的排序方法是：（）

A.直接插入排序B.直接选择排序

C.快速排序D.归并排序

（8）对一棵完全二叉树按层次遍历序进行递增编号，根结点编号为1,那么编号为49的结点的

左子的编号是：（）

A.98B.99C.50D.48

（9）下列序列中不符合堆的定义的是：（）

A.acdghmpqrx

B.acmdhpxgor

C.adprcqxmhg

D.adcmpghxrq

do）下列排序方法中，相同关键字元素的顺序不会被改变的排序方法是：（）

A.希尔排序法B.堆排序法C.快速排序D.归并排序法

（11）在有n个叶结点的哈夫曼树上，结点总数为：（）

A.2nB.2n+lC.2nTD.不确定

（12）对于关键字值序列（12、13、11、18、60、15、7、18、25、100）建堆,调整的起点是:（）

A.100B.12C.60D.15

（13）下列关键字序列中，是执行完一趟快速排序后得到的序列的是：（）

A.[da,ax,eb,de,bb]ff[ha,gc]B.[cd,eb,ax,da]ff[ha,gc,bb]

C.[gc,ax,eb,cd,bb]ff[da,ha]D.[ax,bb,cd,da]ff[eb,gc,ha]

（14）若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树

是：（）

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

（15）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并己知A的左

孩子的平衡因子为0右孩子的平衡因子为1，则应采取的调整型是：（）

A.LLB.LRC.RLD.RR

填空题（每题2分，共20分）

（1）通常从四个方面评价算法的质量：、、和

（2）若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指

针。在这种存储结构中，n个结点的二叉树共有个指针域，其中有个指针域

是存放了地址，有个指针是空指针。

（3）A0V网是一种的图。

(4)在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有

向完全图中，包含有________条边。

三.判断题(每题2分，共30分)

(1)由二叉树的前序和后序遍历序可以推导出其中序遍历序。()

(2)线性表的逻辑顺序和物理顺序总是一致的。()

(3)有向图的邻接表结构比邻接矩阵结构要节省空间。()

(4)栈和队列都是限制了读写操作的线性表，只是所施加的限制不同。()

(5)大顶堆(降序堆)是根结点大于其他所有结点的完全二叉树。()

(6)连通图从任意顶点出发进行一趟深度优先遍历，可以访问到图中的所有顶点。()

(7)用二叉链结构存储的--棵n个结点的二叉树上，有n+1个空链。()

(8)二路归并排序的核心操作是将两个有序序列归并为一个有序序列。()

(9)设只有根结点的二叉树高度为1,则高度为h的二叉树，至多有2回个结点.()

(10)递归形式的代码一定可以用非递归的形式来实现。()

(11)稳定排序法可以保证排序的效率，不稳定排序法不能保证排序的效率。()

(12)邻接矩阵所需存储空间大小只与结点数有关，与弧的个数无关。()

(13)二叉树中，具有两个子结点的中序后继结点最多只可能有一个子结点。()

(14)若一棵二叉树的左右子树都是平衡二叉树，则该二叉树亦为平衡二叉树。()

(15)折半查找法只适用于顺序结构的线性表。()

四.(共10分)请画出下图的邻接矩阵(5分)和邻接表(5分)。

五.已知某工程包括多个子项目，某些子项目可能存在前期子项目，也就是说，只有当前期子

项目都完成后，该子项目才能开始。下面给出各子项目的工期，以及各子项目的前期子项目。

请计算总工期的下限，以及哪些子项目是影响总工期的关键子项目，写出计算过程，并简要说

明计算过程。（共10分）

子项目名称子项目工期前期子项目

A55

B90

C16B

D61A、C

E11B

F80B

G76F

H2D、E

《数据结构》考试参考答案（A卷）

题号—二三四五六七八九总分

得分3020301010100

一.单项选择题(每题2分，共30分)

(1)C(2)C(3)C(4)B(5)C

(6)C(7)A(8)A(9)C(10)D

(11)C(12)C(13)A(14)C(15)C

二.填空题(每空2分，共20分)

(1)正确性易读性强壮性高效率

(2)2nn_ln+1

(3)有向无回路

(4)n(n-l)/2n(n-l)

三.判断题(每题2分，共30分)

(1)N(2)N(3)N(4)Y(5)N

(6)Y(7)Y(8)Y(9)N(10)Y

(11)N(12)Y(13)Y(14)N(15)Y

四.请画出下图的邻接矩阵和邻接表（共10分）。

（1）（5分）邻接矩阵如下所示：

"01110"

10101

11011

10101

01110

（2）（5分）邻接表如下所示:

五、（共10分）

由表可知A0E网如下:

计算拓扑序、ve、vl如下:

拓扑序021345

ve0