一、单选题（共 38 道试题，共 95 分。）V 1. 下列那种排序需要的附加存储开销最大（）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 插入排序
满分：2.5 分
2. 如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。
A. 起泡排序
B. 快速排序
C. 简单选择排序
D. 堆排序
满分：2.5 分
3. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A. 空或只有一个结点高度等于其结点数
B. 任一结点无左孩子
C. 任一结点无右孩子
满分：2.5 分
4. 以下数据结构中不属于线性数据结构的是（ ）。
A. 线性表
B. 队列
C. 二叉树
D. 栈
满分：2.5 分
5. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。
A. edcba
B. decba
C. abcde
D. dceab
满分：2.5 分
6. 在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从前向后依次后移（ ）个元素。
A. n-i
B. n-i+1
C. n-i-1
D. i
满分：2.5 分
7. 算法的时间复杂度是指（ ）。
A. 执行算法程序所需要的时间
B. 算法程序的长度
C. 算法执行过程中所需要的基本运算次数
D. 算法程序中的指令条数
满分：2.5 分
8. 当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。
A. top++
B. top=0
C. top--
D. top=N
满分：2.5 分
9. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。
A. 8
B. 63.5
C. 64
D. 7
满分：2.5 分
10. 队列的插入操作是在（ ）进行。
A. 队首
B. 队尾
C. 队前
D. 队后
满分：2.5 分
11. 二叉树第i层上至多有（）结点。
A. 2i
B. 2的i次方
C. 2i-1
D. 2的i-1次方
满分：2.5 分
12. 若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用( )存储方式最节省时间。
A. 顺序表
B. 单链表
C. 双链表
D. 单循环链表
满分：2.5 分
13. 由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。
A. 23
B. 51
C. 53
D. 74
满分：2.5 分
14. 无向图的邻接矩阵是一个 ( )。
A. 对称矩阵
B. 零矩阵
C. 上三角矩阵
D. 对角矩阵
满分：2.5 分
15. 在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子a等于（）。
A. n/m
B. m/n
C. n/(n+m)
D. m/(n+m)
满分：2.5 分
16. 对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )。
A. O(log2n)
B. O(n*n)
C. O(ne)
D. O(elog2e)
满分：2.5 分
17. 下列数据组织形式中，（ ）的各个结点可以任意邻接。
A. 集合
B. 树形结构
C. 线性结构
D. 图状结构
满分：2.5 分
18. 某二叉树结点的前序序列为E、A、C、B、D、G、F，中序遍历为A、B、C、D、E、F、G。 该二叉树结点的后序序列为 ( )。
A. B,D,C,A,F,G,E
B. B,D,C,F,A,G,E
C. E,G,F,A,C,D,B
D. E,G,A,C,D,F,B
满分：2.5 分
19. 设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针操作为（）。
A. P一＞next＝p一＞next一＞next
B. p＝P一＞next
C. p＝P一＞next一＞next
D. p一＞next＝p
满分：2.5 分
20. 线性表是一个具有n个（）的有限序列。
A. 表元素
B. 字符
C. 数据元素
D. 数据项
满分：2.5 分
21. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 （）。
A. 根结点无右子树的二叉树
B. 根结点无左子树的二叉树
C. 根结点可能有左二叉树和右二叉树
D. 各结点只有一个儿子的二叉树
满分：2.5 分
22. 一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（ ）。
A. 128
B. 127
C. 126
D. 255
满分：2.5 分
23. 链表不具有的特点是（ ）。
A. 不必事先估计存储空间
B. 可随机访问任一元素
C. 插入删除不需要移动元素
D. 所需空间与线性表长度成正比
满分：2.5 分
24. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是()。
A. O(n)
B. O(e)
C. O(n+e)
D. O(n*e)
满分：2.5 分
25. 以下关于数据的存储结构的叙述哪一条是正确的（ ）。
A. 数据的存储结构是数据间关系的抽象描述
B. 数据的存储结构是逻辑结构在计算机存储器中的实现
C. 数据的存储结构分为线性结构和非线性结构
D. 数据的存储结构对数据运算的具体实现没有影响
满分：2.5 分
26. 计算机的算法必须具备输入，输出和（ ）五个特性。
A. 可行性，可移植性和可扩充性
B. 可行性，确定性和有穷性
C. 确定性，有穷性和稳定性
D. 易读性，稳定性和安全性
满分：2.5 分
27. 向二叉排序树中插入一个元素时，其时间复杂度大致为( )。
A. O(log以2为底的n)
B. O(n)
C. O(1)
D. O(n*log2n)
满分：2.5 分
28. 从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。
A. 原树高度加1
B. 原树高度减1
C. 原树高度
D. 不确定
满分：2.5 分
29. 设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（）。
A. 3，2，5，6，4，1
B. 1，5，4，6，2，3
C. 2，4，3，5，1，6
D. 4，5，3，6，2，1
满分：2.5 分
30. 线性链表不具有的特点是（）。
A. 随机访问
B. 不必事先估计所需存储空间大小
C. 插入与删除时不必移动元素
D. 所需空间与线性表长度成正比
满分：2.5 分
31. 由两个栈共享一个向量空间的好处是（ ）。
A. 减少存取时间，降低下溢发生的机率
B. 节省存储空间，降低上溢发生的机率
C. 减少存取时间，降低上溢发生的机率
D. 节省存储空间，降低下溢发生的机率
满分：2.5 分
32. 用某种排序方法队线性表（25，84，21，47，15，27，68，35，20）进行排序，元素序列变化如下：（1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 所采用的排序方法是（ ）。
A. 选择排序
B. Shell排序
C. 归并排序
D. 快速排序
满分：2.5 分
33. 对n个记录的文件进行堆排序，最坏情况下的执行时间为 ( )。
A. O(log2n)
B. O(nlogn)
C. O(n)
D. O(n*n)
满分：2.5 分
34. 一个队的入队序列是1，2，3，4 ，则队列的输出序列是（ ）。
A. 4，3，2，1
B. 1，2，3，4
C. 1，4，3，2
D. 3，2，1，4
满分：2.5 分
35. 具有2000个节点的二叉树，其高度至少为（）。
A. 9
B. 10
C. 11
D. 12
满分：2.5 分
36. 广义表（（a）,a）的表头是（）。
A. a
B. b
C. (a)
D. ((a))
满分：2.5 分
37. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。
A. n-1
B. n
C. n+1
D. n+2
满分：2.5 分
38. 算法分析的两个主要方面是（ ）。
A. 空间复杂度和时间复杂度
B. 正确性和简明性
C. 可读性和文档性
D. 数据复杂性和程序复杂性
满分：2.5 分