数据结构与算法分析模拟试卷.docx

四川大学
《数据结构与算法分析》课程
考试模拟试卷
模拟试卷一
一、 单项选择题（每题2分，共20分）.以下数据结构中哪一个是线性结构？（）
A.有向图B.队列 C.线索二叉树D.B树.在一个单链表HL中，假设要在当前由指针p指向的结点后面插入一个由q指向的结点， 那么执行如下（）语句序列。
A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;
3 .以下哪一个不是队列的基本运算？（）
A.在队列第i个元素之后插入一个元素B.从队头删除一个元素
C.判断一个队列是否为空D.读取队头元素的值.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 （）个不同的字符串？
A. 14B. 5C. 6D. 8
5.
由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）o6.

6.
A. 11 B. 35 C. 19 D. 53
以下6・8题基于图1。
该二叉树结点的前序遍历的序列为（
)°
A. E、 G、 F、 A、 C、 D、 B
B. E、 A、 G、 C、 F、 B、 D
C. E、 A、 C、 B、 D、 G、 F
D. E、 G、 A、 C、 D、 F、 B
该二叉树结点的中序遍历的序列为（
A. A、 B、 C、 D、 E、 G、 F
B. E、 A、 G、 C、 F、 B、 D
)°
C. E、 A、 C、 B、 D、 G、 F
E. B、 D、 C、 A、 F、 G、 E

8.该二叉树的按层遍历的序列为（）o
三、
1.
运算题(每题6分，共24分)
一个6x5稀疏矩阵如右所示，试:

7 .二叉树是指度为2的 树。一棵结点数为N的二叉树，其所有结
点的度的总和是 o.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个 o对一棵由
算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为 个,
其中 个用于指向孩子，个指针是空闲的。
8 .假设对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A 中，即编号为0的结点存储到A[0]中。其余类推，那么A[ i ]元素的左孩子元素为, 右孩子元素为，双亲元素为 O.在线性表的散列存储中，处理冲突的常用方法有 和
9 .当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用
排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用
排序。
(1)写出它的三元组线性表;(2)给出三元组线性表的顺序存储表示。0000
10 设有一个输入数据的序列是{ 46,25,78,62, 12,80 },试画出从5000
空树起，逐个输入各个数据而生成的二叉搜索树。
11 对于图6所示的有向图假设存储它采用邻接表，并且每个顶点邻L0070
接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：
(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树；
(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树；一个图的顶点集V和边集E分别为：
V={1,2, 3,4, 5,6, 7};伞―_E={<2, 1>, <3, 2>, <3, 6>, <4, 3>, <4, 5
>,<4, 6>, <5, 1>, <5, 7>, <6, 1>, <6, 2>, <6,/假设存储它采用邻接表，并且每个顶点二
邻接表中的边结点都是按照终点序号从—^^5
小到大的次序链接的，按主教材中介绍的
拓朴排序算法进行排序，试给出得到的拓图6
朴排序的序列。
四、 阅读算法(每题7分，共14分)int Prime(int n)
int i=l;int x=(int) sqrt(n);
while (++iv=x)if (n%i==0) break;
if (i>x) return 1; else return 0;⑴指出该算法的功能；
(2)该算法的时间复杂度是多少？
2. 写出下述算法的功能：
void AJ(adjlist GL, int i, int n) (Queue Q;
InitQueue (Q);cout<<i<<，';
visited[i]=true;QInsert(Q, i);
while(!QueueEmpty (Q)) {int k=QDelete (Q);
edgenode* p=GL[k];
while(p!二NULL) (int j=p->adjvex;
if(!visited[j]) (cout<<j<<J ';
visited[j]=true;QInsert (Q,j);
) p=p->next; )}
i i算法填空(共8分)
如下为二分查找的非递归算法，试将其填写完整。
Int Binsch(ElemType A[ ],int n,KeyType K) (
int low=0;
int high=n-l;
while (low<=high) {int mid=；
if (K==A[mid].key) return mid; //查找成功，返回元素的下标 else if (K<[mid].key)；//在左子表上继续查找
else;//在右子表上继续查找
)
return -1;〃查找失败，返回-1

）六、
编写算法（共8分）

HL是单链表的头指针，试写出删除头结点的算法。
ElemType DeleFront(LNode * & HL)模拟试卷三参考答案
一、 单项选择题(每题2分，共20分)
l.B 2.A 3.B 4.C 5.D 6.B 7.D8.A9.D10.C
二、 填空题(每空1分，共26分)
1. 联系图(或图结构)
2. 尾首
3. top==0
4. O (1) O (n)
5. 12844108
6. 33
7. 有序 n-1
8. 有序序列后缀表达式(或逆波兰式)
9.
10.
11.
2n n-1
2i+l
开放定址法
n+1
2i+2(i-l)/2
链接法

12.快速归并运算题(每题6分，共24分)
1 .(1)((1,5,1),(32-D,(45-2),(5,1,5),(6,3,7))(3 分)(2)三元组线性表的顺序存储表示如图7示。
2 .如图8所示。

3 . DFS：①②③④⑤
BFS：②③④⑤①.拓朴排序为：4 3 6 5 7 2 1
三、 阅读算法(每题7分，共14分)(1)判断n是否是素数(或质数)
(2) O ( Vh )2.功能为：从初始点环出发广度优先搜索由邻接表GL所表示的图。
四、 算法填空(8分)(low+high)/2

(low+high)/2
high=mid-l
low=mid+l
编写算法(8分)
ElemType DeleFront(LNode * & HL)
if(HL==NULL){
cerr«"空表"<<endl; exit(l);
LNode* p=HL;
HL=HL->next;
ElemType temp=p->data;
delete p;
return temp;)
模拟试卷四
一、 单项选择题（每题2分，共20分）.以下数据结构中哪一个是线性结构？（）
A.有向图B.栈 C.二叉树 D.B树.假设某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，那么采
B.双链表
D.单循环链表
B.从队头删除一个元素
用（）存储方式最节省时间。
A.单链表C带头结点的双循环链表
1 .以下哪一个不是队列的基本运算？（） A.在队列第i个元素之后插入一个元素C.判断一个队列是否为空

C.判断一个队列是否为空
D.读取队头元素的值

2 .字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以 组成（）个不同的字符串？
A. 15
B. 14
C. 16
D. 21
5 .由权值分别为476,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）o
A. 11 B. 37 C. 19 D. 53

6 .由权值分别为476,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）o
A. 11 B. 37 C. 19 D. 53
以下6・8题基于下面的表达：假设某二叉树结点的中序遍历的序列为A、B、C、D、E、
F、G,后序遍历的序列为B、D、C、A、F、G、E。
7 .那么该二叉树结点的前序遍历的序列为（）.
A. E、 G、 F、 A、 C、 D、 B
C. E、 A、 C、 B> D、 G、 F
7 .该二叉树有（）个叶子。
A. 3B. 2C. 5
8 .该二叉树的按层遍历的序列为（）
A. E、 G、 F、 A、 C、 D、 B
C. E、 A、 G、 C、 F、 B、 D
9 .下面的二叉树中，（）不是完全二叉树。
B.E、A、G、C、F、B、D
D.E、G、A、C、D、F、B
D. 4
B. E、A、C、B、D、G、F
D. E、G、A、C、D、F、B
A.

A.
B.
C.
D.

10.设有关键码序列(q, g, m, z, a),下面哪一个序列是从上述序列出发建的小根堆的结 果?()A. a, g , m, q, zB. a, g , m, z, q
C. g , m, q, a, zD. g, m, a, q, z填空题(每空1分，共26分)
1 .数据结构是指数据及其相互之间的 o当结点之间存在1对N (1： N)
的联系时，称这种结构为 O. 一个广义表中的元素分为 元素和 元素两类。
2 .对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为， 在表尾插入元素的时间复杂度为 o.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是
删除一个结点时，需要执行的操作是 (假设栈不空而且 无需回收被删除结点)。
3 .栈又称为 表，队列又称为 表。
4 .在稀疏矩阵所对应的三元组线性表中，每个三元组元素按 为主序、
为辅序的次序排列。
5 .假设一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为K,那么左、 右子树皆非空的结点个数是 o.以折半(或二分)查找方法从长度为8的有序表中查找一个元素时，平均查找长度为
6 .表示图的三种常用的存储结构为、和 o.对于线性表(78, 4, 56, 30, 65)进行散列存储时，假设选用H (K)=K %5作为散列
函数，那么散列地址为0的元素有 个，散列地址为4的有 个。
7 .在归并排序中，进行每趟归并的时间复杂度为，整个排序过程的时间复杂度为 ，空间复杂度为 O.在n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为 o WPL 称为 o
8 .在索引表中，假设一个索引项对应主表的一个记录，那么此索引为 索引，假设对
应主表的假设干条记录，那么称此索引为 索引。
二、 运算题(每题6分，共24分).写出以下中缀表达式的后缀形式：
(1) 3X/(Y-2H)+12+X*(Y+3)
1 .假定一棵二叉树广义表表示为a(b(c),d(e,D)，分别写出对它进行先序、中序、后序、按 层遍历的结果。
先序：
中序：
后序：
按层：
2 .一个无向图的顶点集为｛a, b, c, d, e｝，其邻接矩阵如下所示
(1)画出该图的图形；
(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序 列。
3 .一个图的顶点集V和边集E分别为：
V= {0,1,2, 3,4, 5,6, 7);E= {(0, 1)8, (0, 2)5, (0, 3)2, (1,5)6, (2, 3)25, (2, 4) 13, (3, 5)9, (3, 6) 10,
(4,6)4, (5, 7)20);按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
三、 阅读算法(每题7分，共14分)void AE(Stack& S) {
InitStack(S);Push(S, 3);
Push (S, 4);int x=Pop(S)+2*Pop (S);
Push(S, x);int i,a[5] = {2, 5, 8, 22, 15);
for(i=0;i<5;i++) Push(S, a[i]);while(!StackEmpty(S)) cout<<Pop(S)<<?';
)该算法被调用后得到的输出结果为：
1. int akm ( unsigned m, unsigned n ) {
if ( m == 0 ) return n+1;else if ( n - 0 ) return akm ( m-1, 1 );
else return akm ( m-1, akm ( m, n-1 ));)
该函数执行的功能是什么？
四、 算法填空(共8分)二叉搜索树的查找一非递归算法
bool Find(BTreeNode* BST, ElemTypefe item)
{while(BST(!=NULL){if (item==) {
item = BST-〉data; 〃查找成功return true;}
else if(item<BST->data)BST=BST->;
else BST=BST->;
}//whilereturn ; 〃查找失败
)编写算法(共8分)
用递归的算法编写出对存入在a[n+l]数组中的n个有序元素进行二分(又称折半)查找 (假定a[0]单元不用)的程序。
int halfsearch(SSTable *a, KeyType k,int low,int high)模拟试卷四参考答案
一、 单项选择题(每题2分，共20分)l.B 2.C 3.A 4.B 5.B 6.C 7.A 8.C 9.C 10.B
二、 填空题(每空1分，共26分)
1 .联系树(或树结构)
2 .单 (子)表
3 . 0(n) 0(1)
4 , p->next=HS;HS=pHS=HS->next
5 .先进后出先进先出
6 .行歹U
7 . k-1
8 . 2.625
9 .邻接矩阵邻接表边集数组
10 .21
11 . 0(n)0 (nlog2n) 0 (n)
12 .哈夫曼树带权路径长度
13 .稠密稀疏运算题(每题6分，共24分)
1. (1) 3 X *Y 2 H*-/l +2)2 X Y 3 + * +
2 .先序：a,b,c,d,e,f中序：c, b, a, e, d, f
后序: c, b, e, f, d, a 按层：a,b,d,c,e,f
3 . (1)该图的图形如图9示：
(2)深度优先遍历序列为：abdce 广度优先遍历序列为：abedc
4.普里姆:(0,3)2, (0,2)5, (0』)8, (1,5)6, (3,6)10, (6,4)4, (5,7)20阅读算法(每题7分，共14分)
3 .15 22 8 5 2 10.该函数的功能是:
h + 1求.akm(m,n) = < akrnQn -1, 1)
akm(m-1, akm(m,n-1))当m = 0时
当加w 0,〃 = 0时 当mw 0/2 w 0 时

当m = 0时
当加w 0,〃 = 0时 当mw 0/2 w 0 时
五、 算法填空(共8分，每一空2分)BST->data left right false
六、 编写算法(8分)
递归算法：
int halfsearch(SSTable *a, KeyType k, int low, int high)
{ if (low>high)return 0;
else {int mid=(low+high)/2
if EQ(k, a[mid]. key) return mid;else if LT(k, a[mid]. key) return halfsearch(a, k, low, mid-1);
else return halfsearch(a, k, mid+1, high);模拟试卷五
单项选择题（每题2分，共20分）
1 .栈和队列的共同特点是（ ）oA.只允许在端点处插入和删除元素
B.都是先进后出C.都是先进先出
D.没有共同点
2 .用链接方式存储的队列，在进行插入运算时（）.
A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改
3 .以下数据结构中哪一个是非线性结构？（）A.队列B.栈 C.线性表 D.二叉树
A. 688
B. 678 C. 692 D. 696
4 .设有一个二维数组A[词㈤，假设A[0][0]存放位置在644（io）, A⑵⑵存放位置在 676（]0）,每个元素占一个空间，问43][3]（⑼存放在什么位置？脚注（⑼表示用10进制 表示。
B.无序数据元素
D.元素之间无联系的数据
D. 2k-1

5 .树最适合用来表示（）oA.有序数据元素
C.元素之间具有分支层次关系的数据
6 .二叉树的第k层的结点数最多为（）.
A. 2-1 B. 2K+1 C. 2K-1.假设有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[l]中，现进行二 分查找，那么查找A [3]的比拟序列的下标依次为（）
A. 1, 2, 3B. 9, 5, 2, 3C.9, 5, 3D.9, 4, 2, 3
7 .对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. 0(1) B. 0 (n) C. 0 (log2n) D. 0 (n2)
8 .对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，假设选用H (K) 二K%9作为散列函数，那么散列地址为1的元素有()个，A. 1B. 2C. 3D. 4
9 .设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。
A.5B.6C.7D.8填空题(每空1分，共26分)
1 .通常从四个方面评价算法的质量：、、和 o. 一个算法的时间复杂度为("+〃21og2〃+14〃)》2,其数量级表示为 o
2 .假定一棵树的广义表表示为A (C, D (E, F, G), H (I, J)),那么树中所含的结点数 为 个，树的深度为，树的度为 o.后缀算式9 23 +- 10 2/ -的值为 o中缀算式(3+4X) -2Y/3对应的后缀算式
为 O.假设用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有 个指针域，其中有 个
指针域是存放了地址，有 个指针是空指针。
3 .对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有 个和 个O. AOV网是一种 的图。
4 .在一个具有n个顶点的无向完全图中，包含有 条边，在一个具有n个顶点的有
向完全图中，包含有 条边。
5 .假定一个线性表为(12,23,74,55,63,40),假设按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，那么得到的四个子表分别为、
、和 O.向一棵B_树插入元素的过程中，假设最终引起树根结点的分裂，那么新树比原树的高度
6 .在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为，整个堆排序 过程的时间复杂度为 O.在快速排序、堆排序、归并排序中，排序是稳定的。
二、 运算题(每题6分，共24分)请画出图10的邻接矩阵和邻接表。

请画出图10的邻接矩阵和邻接表。
2.
3.
1 .在如下数组A中链接存储了一个线性表，表头指针为A[0].next,试写出该线性表。

60
50
78
90
34

40
3
5
7
2
0
4

1
A01234567data next

图10
一个图的顶点集V和边集E分别为：
V二{1,2, 3, 4, 5, 6, 7};
E={(1,2)3, (1,3)5, (1,4)8, (2, 5)10, (2,3)6, (3,4)15, (3, 5) 12, (3, 6) 9, (4, 6)4, (4, 7) 20, (5, 6) 18, (6, 7) 25);用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树
中依次得到的各条边。
4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。
四、
阅读算法（每题7分，共14分）

1. LinkList mynote(LinkList L){//L是不带头结点的单链表的头指针
if(L&&L->next){q=L； L=L—>next； p=L；
SI ：while(p—>next) p=p—>next；S2：p—>next=q； q —>next=NULL；
)
return L； )请回答以下问题：
(1)说明语句SI的功能；(2)说明语句组S2的功能；
(3)设链表表示的线性表为(al9a2,…,即)，写出算法执行后的返回值所表示的线性 表。
2. void ABC(BTNode * BT)(
if BT (ABC (BT->left);
ABC (BT->right);cout«BT->data«*
})
该算法的功能是：
五、 算法填空(共8分)二叉搜索树的查找一递归算法：
bool Find(BTreeNode* BST, ElemTypefe item)
(if (BST二二NULL)
return false; 〃查找失败else (
if (item==BST->data) {item=BST->data; 〃查找成功
return;} else if (item<BST->data)return Find(, item);
else return Find(, item);}//if
)编写算法(共8分)
统计出单链表HL中结点的值等于给定值X的结点数。
int CountX(LNode* HL,ElemType x)A. E、 G、 F、 A、 C、 D、 B

B. E、 G、 F、 A、 C、 D、 B
C. E、A、C、
B、 D、 G、 F
D. E、 A、 G、 C、 F、 B、 D
E. E、G、A、
C、 D、 F、 B
.下面关于图的存储的表达中正确的选项是()o
A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关
D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关.设有关键码序列(q, g, m, z, a, n, p, x, h),下面哪一个序列是从上述序列出发建 堆的结果?()
A. a, g, h, m, n, p, q, x, zB.a, g, m, h, q, n, p, x, zC. g, m, q, a, n, p, x, h, zD.h, g, m, p, a, n, q, x, z
二、 填空题(每空1分，共26分).数据的物理结构被分为、、和 四种。
1 .对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为, 在表尾插入元素的时间复杂度为 O.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是; 删除一个结点时，需要执行的操作是(假设栈不空而 且无需回收被删除结点)。
2 .对于一棵具有n个结点的二叉树，一个结点的编号为i(lWiWn),假设它有左孩子那么左孩 子结点的编号为,假设它有右孩子，那么右孩子结点的编号为，假设它有双 亲，那么双亲结点的编号为 o.当向一个大根堆插入一个具有最大值的元素时，需要逐层 调整，直到被调整
到 位置为止。
3 .以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为 o.表示图的三种常用的存储结构为、和 o
4 .对于线性表(70, 34, 55, 23, 65, 41, 20)进行散列存储时，假设选用H (K) =K %7 作为散列函数，那么散列地址为。的元素有 个，散列地址为6的有 个。
5 .在归并排序中，进行每趟归并的时间复杂度为,整个排序过程的时间复杂度为 ，空间复杂度为 O.在一棵m阶B_树上,每个非树根结点的关键字数目最少为 个,最多为
个，其子树数目最少为，最多为运算题(每题6分，共24分)
1 .写出以下中缀表达式的后缀形式：
(1) 3X/(Y-2)+l2+X*(Y+3)
2 .试对图2中的二叉树画出其：
(1)顺序存储表示的示意图；
(2)二叉链表存储表示的示意图。
3 .判断以下序列是否是小根堆？如果不是，将它调 整为小根堆。
(1) { 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }
4. 一个图的顶点集V和边集E分别为：
V二｛1,2, 3, 4, 5,6, 7);模拟试卷五参考答案
单项选择题(每题2分，共20分)
1 .A 2.D 3.D 4.C 5.C 6.D 7.D8.C9.D10,A
二、填空题(每空1分，共26分)正确性易读性强壮性高效率
1. 0(n)933
2. -134X* + 2Y*3/-2nnTn+1
3. e2e有向无回路
4. n(nT)/2 n(n-l)(12, 40)( )(74)(23,55, 63)
5. 增加10(log2n) 0(nlog2n)
6. 归并 运算题(每题6分，共24分)线性表为：(78, 50, 40, 60, 34, 90)
1 0
1 0 1
2.邻接矩阵：1 1 0
0 1
1 10 1
1 0j邻接表如图11所示:
图11
3.用克鲁斯卡尔算法得到的最小生成树为：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

图11
3.用克鲁斯卡尔算法得到的最小生成树为：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4.见图12

2

图12
四、 阅读算法(每题7分，共14分). (1)查询链表的尾结点
(2)将第一个结点链接到链表的尾部，作为新的尾结点 (3)返回的线性表为(a2,a3,-\an,ai).递归地后序遍历链式存储的二叉树。
五、 算法填空(每空2分，共8分)true BST->left BST->right
六、 编写算法(8分)int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;〃i 为计数器 while(p!=NULL){ if (P->data==x) i++;
p=p->next;}//while,出循环时i中的值即为x结点个数
return i;
}//CountX模拟试卷六
一、单项选择题(在每题的四个备选答案中，选出一个正确的答案，并将其号码填在 题干后的括号内。每题1分，共10分)
1 .下面程序段
for(i=l;i<=n;i++)for(j=l；j<=i；j++)
x=x+l;
的时间复杂度为( )oA) O(n)B) O(n2)
C) O(n*i)D) O(n+i)
2 .设一个栈的入栈序列是ABCD,那么借助于一个栈所得到的出栈序列不可能是 ()oA) ABCDB) DCBA
C) ACDBD) DABC
3 .当求链表的直接后继与求直接前驱的时间复杂度都相同时，此链表应为()o4.
(

4.
(
A)单链表
C)单向循环链表
串 s^BBABBABBA1,
)o
A) 'BBABABA'
C) 'BBAAA'
B）双向链表D）前面都不正确
c=A,执行置换操作REPLACE（s,t,c）后，s应为B) 'BBAABA'
6.
7.
5.
下面AOE网中，关键路径长度为
(
F,
B,
）。
)o
C, E, G,
G, E, C,
A) 16
C) 10
B) 13
D) 9
用Dijkstra算法求从源点到其它各顶点的最短路径的时间复杂度为（
）。
A) O(n)
C) O(n3)
B) O(n2)
D) O(nlogn)
8.
在以下查找方法中，平均查找速度最快的是（
)o
9.
A）顺序查找
C）分块查找
B）折半查找
D）二叉排序树查找
哈希表的地址区间为0-17,哈希函数为H（K尸K% 17。采用线性探测法处理冲突,
并将关键字序列26, 25, 72, 38, 8, 18, 59依次存储到哈希表中。那么59存放在哈希表中
的地址是（
A） 8
C） 10
)°
B) 9
D) 11
10.快速排序算法的平均时间复杂度是（
)o
A) O(n)
C) O(nlog2n)
B) O(n2)
D) O(log2n)
二、填空题（每空1分，共15分）
1 .设有一个记录r,设其类型为LNode,那么r实际所占用的存储空间的大小为 ）。
2 . 一个算法的时间复杂度为（5nZ3nlog2n+7n-9）/（6n）,其数量级表示为（
3 .如将nXn的对称矩阵压缩存储于sa[k]中，那么k等于（
)o
)°
D) 'BBABABBA1
4 .如一二维数组A[L.m, L.n]按行排列，设的相对位置为0,每个元素的大小为1,那么任一元素A[i, j]的地址为（

为1,那么任一元素A[i, j]的地址为（
)°

个顶点的有向完全图中，包含有（
）条弧。
）o
）倍。
）条边；在一个具有n

5 .线性表的顺序存储结构中存取元素的时间复杂度为是（）o
6 .队列的插入操作在（）进行，删除操作在（）进行。
7 .后缀表达式“45 * 3 2 + +”的值为（）。
8 .对于一棵具有n个结点的树，此树中所有结点的度数之和为（）,设叶 子结点数为no,度为二的结点数为112,那么它们之间的关系为（
9 .在一个无向图中，所有顶点的度数之和等于所有边数的（
10 .在一个具有n个顶点的无向完全图中，包含有（

11 .每次从无序表中取一个最小或最大元素，把它们交换到有序表的一端，此种排序方）排序。

）排序。
法称为（
12 . 一种抽象数据类型应包括数据和（）两大局部。
三、判断改错题（判断正误，将正确的划上错误的划上“X。每题1分，共 10分）
1 .从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。 （ ）
2 .数组可看成线性结构的一种推广，所以可对数组进行插入与删除操作。 （
3 .在删除链表结点时，计算机能自动地将其后继的各个结点向前移动。（）
4 .利用栈求表达式的值时，设立操作数栈OPND,设OPND只有2个存储单元，那么表达式（A-B）*C+D将不会发生发生上溢现象。（）
5 .串是n个字母的有限序列（n>=0）o（）
6 . n阶下三角矩阵的非零元素的个数最多为智2。（）
7 .二叉树只能采用二叉链表来存储。（）
8 .图G的某一最小生成树的代价一定小于其它生成树的代价。（）
9 . B+树是一种特殊的二叉树。（）
10 .所有的简单排序（即时间复杂度为0（/）的排序）都是稳定排序。（
）
四、简答题（每题4分，共20分）
1.对于以下双向链表，设结构为（prior,data,next）,结点类型为Inode,试写出在p所指 结点之前插入元素x的语句序列。
2.对于以下图，用Prim算法从结点 变化情况。
出发构造出一棵最小生成树，要求图示出每一步的

3 .一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。
先序序歹U： ABCDEFGHIJ
中序序歹U： CBEDAGHFJI
4 .给定一组权值{3, 4, 7, 14, 15, 20},试画出相应的哈夫曼树，并计算带树路径长 度WPL的值。
5 .有关键字序列{7,23,6,9,17,19,21,22,5}, Hash函数为H(key尸key % 5,采用链地址法 处理冲突，试构造哈希表。
五、算法题(共25分)
1 .程序填空题(每空2分，共8分)
下面程序的功能是二叉树的中序遍历的非递归算法，其中二叉树的结点结构为 (lchild,data,rchild),栈的常用方法有：入栈Push,出栈Pop,判空StackEmpty；试将程序补 充完整。
template<class Type>BiTreeNode ：liBiTree<Type>::GoFarLeft(BiTreeNode<Type> *T, Stack< BiTreeNode<Type> *>& S){ if(!T) return NULL;
while (T->lchild){Push(S, T);
T 二； ) return T;
)
template<class Type>
void BiTree<Type>::Inorder(BiTreeNode<Type> *T, void (*visit)(Type & e)){Stack< BiTreeNode<Type> *>& S;
t = GoFarLeft(T, S); //找到最左下的结点while(t){
visit(t->data);if (t->rchild)
t = GoFarLeft(, S);else if ( ! StackEmpty(S ))
t=；else
t=;//栈空说明遍历结束} // while
}// Inorder
2 .程序填空题(每空2分，共8分)
下面程序的功能是用线性探测再散列处理冲突(即Hi=(H(key)+i)%m),哈希函数为 H(key)=kcy % m,进行哈希表的插入算法。(如表中已存在关键字相同的记录或无插入位置, 那么不进行插入)，试将程序补充完整。
typedef enum {SUCCESS,UNSUCCESS,OVERFLOW} Status;
template<class Type>
typedef struct {Type *elem;
int m;
JHashTable;
template<class Type>
Status SerchHashTable(HashTable<Type> H,Type e){int i=O,k=; //i为冲突的次数,k为哈希函数的值
while(i<m && H.elem[k].key! =NULLKEY && p->elem.key!=e.key){p=(p+i)%m;
}//whileif(i>=m)return OVERFLOW;
else if(p->elem.key!=e.key)return ;else{
H.elem[p].elem=;return SUCCESS;
}//if
} //Serch