文档介绍：《数据结构》考试试卷（A卷）
班级：姓名：学号：分数：
题号
一
二
三
四
五
六
七
八
九
十
总分
得分
评卷人
一. 单项选择题(每题2分，共30分)
(1) 一个栈的入栈序列为1 2 3 4，以下出栈序列不可能得到的是( )
A. 1 3 2 4 B. 2 3 4 1
C. 4 3 1 2 D. 3 4 2 1
(2) 若一个二叉树具有10个度为2的结点，则度为0的结点的个数为( )
A. 9 B. 10 C. 11 D. 不确定
(3) 链式结构线性表的特点是：( )
A. 便于随机存取 B. 花费的存储空间比顺序结构少
C. 便于插入和删除 D. 元素的物理顺序与逻辑顺序一致
(4) 一个二叉树的前序遍历序为ABCDEFG，则中序遍历序可能是：( )
A. CABDEFG B. ABCDEFG C. DACEFBG D. EABCDFG
（5）树最适合用来表示( )。

(6) 下列有关图遍历的说法中不正确的是：( )
A．连通图的深度优先搜索是一个递归过程。
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征。
C．非连通图不能用深度优先搜索法。
D．图的遍历要求每一顶点仅被访问一次。
(7) 若已知待排序序列基本有序，则效率最高的排序方法是：( )
A. 直接插入排序 B. 直接选择排序
C. 快速排序 D. 归并排序
(8) 对一棵完全二叉树按层次遍历序进行递增编号，根结点编号为1，那么编号为49的结点的左子的编号是：( )
A. 98 B. 99 C. 50 D. 48
(9) 下列序列中不符合堆的定义的是：( )
A. a c d g h m p q r x
B. a c m d h p x g o r
C. a d p r c q x m h g
D. a d c m p g h x r q
(10) 下列排序方法中，相同关键字元素的顺序不会被改变的排序方法是：( )
A. 希尔排序法 B. 堆排序法 C. 快速排序 D. 归并排序法
(11) 在有n个叶结点的哈夫曼树上，结点总数为：( )
A. 2n B. 2n+1 C. 2n-1 D. 不确定
(12) 对于关键字值序列(12、13、11、18、60、15、7、18、25、100)建堆，调整的起点是：( )
A. 100 B. 12 C. 60 D. 15
(13) 下列关键字序列中，是执行完一趟快速排序后得到的序列的是：( )
A. [da,ax,eb,de,bb]ff[ha,gc] B. [cd,eb,ax