一、单项选择题
1. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储____。
A. 数据的处理方法
B. 数据元素的类型
C. 数据元素之间的关系
D. 数据的存储方法
2. 下述函数中对应的渐进时间复杂度（n为问题规模）最小是 。
A.
T
1
(
n
)
=
n
l
o
g
2
n
+
5000
n
T_1(n)=nlog_2^n+5000n
T1?(n)=nlog2n?+5000n
B.
T
2
(
n
)
=
n
2
?
8000
n
T_2(n)=n^2-8000n
T2?(n)=n2?8000n
C.
T
3
(
n
)
=
n
l
o
g
2
n
?
6000
n
T_3(n)= n^{log_2^n}-6000n
T3?(n)=nlog2n??6000n
D.
T
4
(
n
)
=
7000
l
o
g
2
n
T_4(n)=7000log_2^n
T4?(n)=7000log2n?
3. 设线性表有n个元素，以下操作中，____在顺序表上实现比在链表上实现效率更高。
A.输出第i（1≤i≤n）个元素值
B.交换第1个元素与第2个元素的值
C.顺序输出这n个元素的值
D.输出与给定值x相等的元素在线性表中的序号
4. 设n个元素进栈序列是p1，p2，p3，…，pn，其输出序列是1，2，3，…，n，若p3=3，则p1的值____。
A.可能是2
B.一定是2
C.不可能是1
D.一定是1
5. 以下各种存储结构中，最适合用作链队的链表是____。
A.带队首指针和队尾指针的循环单链表
B.带队首指针和队尾指针的非循环单链表
C.只带队首指针的非循环单链表
D.只带队首指针的循环单链表
6. 对于链串s（长度为n，每个结点存储一个字符），查找元素值为ch的算法的时间复杂度为____。
A.
O
(
1
)
O(1)
O(1)
B.
O
(
n
)
O(n)
O(n)
C.
O
(
n
2
)
O(n^2)
O(n2)
D.以上都不对
7. 设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素a[3][5]的存储地址为1000，则a[0][0]的存储地址是 。
A.872
B.860
C.868
D.864
8. 一个具有1025个结点的二叉树的高h为____。
A.11
B.10
C.11～1025
D.12～1024
9. 一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则先序遍历序列为____。
A.ACBED
B.DECAB
C.DEABC
D.CEDBA
10. 对图1所示的无向图，从顶点1开始进行深度优先遍历；可得到顶点访问序列____。
A.1 2 4 3 5 7 6
B.1 2 4 3 5 6 7
C.1 2 4 5 6 3 7
D.1 2 3 4 5 7 6
二、填空题
1. 顺序队和链队的区别仅在于存储方法或存储结构的不同。
2. 在有n个顶点的有向图中，每个顶点的度最大可达____。
3. 对有18个元素的有序表R[1…18]进行二分查找，则查找R[3]的比较序列的下标为____。
4. 对含有n元素的关键字序列进行直接选择排序时，所需进行的关键字之间的比较次数为____。
5. 已知关键字序列为{2,7,4,3,1,9,10,5,6,8}，采用堆排序法对该序列作升序排序时，构造的初始堆（大根堆）是____。
三、问答题
1. 一棵完全二叉树上有1001个结点，其中叶结点的个数是多少？
- 二叉树中度为1的结点个数只能是1或0。设 n 1 = 1 n_1=1 n1?=1， n = n 0 + n 1 + n 2 = n 0 + n 2 + 1 = 1001 n=n0+n1+n2=n0+n2+1=1001 n=n0+n1+n2=n0+n2+1=1001，由性质1可知 n 0 = n 2 + 1 n_0=n_2+1 n0?=n2?+1，由两式可求 n 0 = 500.5 n_0=500.5 n0?=500.5，不成立；设 n 1 = 0 n_1=0 n1?=0， n = n 0 + n 1 + n 2 = n 0 + n 2 = 1001 n=n_0+n_1+n_2=n_0+n_2=1001 n=n0?+n1?+n2?=n0?+n2?=1001，由性质1可知 n 0 = n 2 + 1 n_0=n_2+1 n0?=n2?+1，由两式可求 n 0 = 501 n_0=501 n0?=501。
2. 给出如下各种情况下求任意一个顶点的度的过程（只需文字描述）：
（1）含n个顶点的无向图采用邻接矩阵存储；
（2）含n个顶点的无向图采用邻接表存储；
（3）含n个顶点的有向图采用邻接矩阵存储；
（4）含n个顶点的有向图采用邻接表存储。
- (1)对于邻接矩阵表示的无向图，顶点i的度等于第i行或第i列中元素等于1的个数
- (2)对于邻接矩阵表示的无向图，顶点i的度等于g->adjlist[i]为头结点的单链表中结点的个数
- (3)对于邻接矩阵表示的有向图，顶点i的出度等于第i行中元素等于1的个数；入度等于第i列中元素等于1的个数；度数等于它们之和
- (4)对于邻接矩阵表示的有向图，顶点i的出度等于g->adjlist[i]为头结点的单链表中结点的个数；入度需要遍历各顶点的边表，若g->adjlist[k]为头结点的单链表中存在顶点编号为i的结点，则顶点i的入度增1；度数等于它们之和
- 将整数序列{4,5,7,2,1,3,6}中的数依次插入到一棵空的平衡二叉树中，试构造相应的平衡二叉树。（要求画出每个元素插入过程，若需调整，还需给出调整后的结果，并指出是什么类型的调整，12分）
- 当实现插入直接排序过程中，假设R[0…i-1]为有序区，R[i…n-1]为无序区，现要将R[i]插入到有序区中，可以用二分查找来确定R[i]在有序区中的可能插入位置，这样做能否改善直接插入排序算法的时间复杂度?为什么?
- 简述外排序的两个阶段。
四、算法设计题
- 设计一个算法delminnode(LinkList *&L)，在带头结点的单链表L中删除所有结点值最小的结点（可能有多个结点值最小的结点）。
- 假设二叉树采用二叉链存储结构存储，设计一个算法copy(BTNode *b,BTNode *&t)，由二叉树b复制成另一棵二叉树t。
- 假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序列。