全国2014年4月高等教育自考
数据结构导论考试试题
课程代码：02142
请考生按规定用笔将所有考试试题的答案涂、写在答卷纸上。
选择题部分
需要注意的地方：
1.答卷前，考生务势必我们的考试课程名字、名字、准考证号用黑色字迹的签字笔或钢笔填写在答卷纸规定的地方上。
2.每小题选出答案后，用2B铅笔把答卷纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不可以答在考试试题卷上。
1、单项选择题
在每小题列出的四个备选项中只有一个是符合题目需要的，请将它选出并将答卷纸的相应代码涂黑。错涂、多涂或未涂均无分。
1.下列几种算法时间复杂度中，最小的是
A.O B.O
C.O D.O
2.数据的存储方法中除去顺序存储方法和链式存储方法以外，还有
A.索引存储方法和树形存储方法 B.线性存储方法和散列存储方法
C.线性存储方法和索引存储方法 D.索引存储方法和散列存储方法
3.表长为n的顺序表中做删除运算的平均时间复杂度为
A.O B.O
C.O D.O
4.顺序表中定位算法的平均时间复杂度为
A.O B.O
C.O D.O
5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为
A.D B.C
C.B D.A
6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为
A.front==rear B.front!=NULL
C.rear!==NULL D.front==NULL
7.深度为5的二叉树，结点个数最多为
A.31个 B.32个
C.63个 D.64个
8.假如结点A有2个兄弟结点，结点B为A的双亲，则B的度为
A.1 B.3
C.4 D.5
9.将题9图所示的一棵树转换为二叉树，结点C是
A.A的左孩子
B.A的右孩子
C.B的右孩子
D.E的右孩子
10.n为图的顶点个数，e为图中弧的数目，则图的拓扑排序算法的时间复杂度为
A.O B.O
C.O D.O
11.无向图的邻接矩阵是
A.对角矩阵 B.稀疏矩阵
C.上三角矩阵 D.对称矩阵
12.在具备101个元素的顺序表中查找值为x的元素结点时，平均比较元素的次数为
A.50 B.51
C.100 D.101
13.架构散列函数的办法不少，常见的架构办法有
A.数字剖析法、除留余数法、平方取中法
B.线性探测法、二次探测法、除留余数法
C.线性探测法、除留余数法、链地址法
D.线性探测法、二次探测法、链地址法
14.就平均时间性能而言，迅速排序办法最好，其时间复杂度为
A.O B.O
C.O D.O
15.下述算法中，不稳定的排序算法是
A.直接插入排序 B.冒泡排序
C.堆排序 D.归并排序
非选择题部分
需要注意的地方：
用黑色字迹的签字笔或钢笔将答案写在答卷纸上，不可以答在考试试题卷上。
2、填空题
16.数据的基本单位是|||||||||。
17.双向循环链表中，在p所指结点的后面插入一个新结点*t，需要修改四个指针，分别为
t|prior=P;t|next=p|next;|||||||||;p|next=t;。
18.在带有头结点的循环链表中，尾指针为rear，判断指针P所指结点为首结点的条件是|||||||||。
19.若线性表中最常见的操作是求表长和读表元素，则顺序表和链表这两种存储方法中，较节省时间的是|||||||||。
20.不含任何数据元素的栈称为|||||||||。
21.稀疏矩阵一般使用的压缩存储办法是|||||||||。
22.100个结点的二叉树使用二叉链表存储时，用来指向左、右孩子结点的指针域有|||||||||个。
23.已知完全二叉树的第5层有5个结点，则整个完全二叉树有|||||||||个结点。
24.n个顶点的有向图G用邻接矩阵A[1..n，1..n]存储，其第i列的所有元素之和等于顶点
Vi的|||||||||。
25.具备10个顶点的有向完全图的弧数为|||||||||。
26.要完全防止散列所产生的堆积现象，一般使用|||||||||解决冲突。
27.在长度为n的带有岗哨的顺序表中进行顺序查找，查找不成功时，与关键词的比较次数为|||||||||。
28.归并排序算法的时间复杂度是|||||||||。
3、应用题
29.稀疏矩阵A如题29图所示，写出该稀疏矩阵A的三元组表示法。
30.设二叉树的中序遍历序列为BDCEAFHG，后序遍历序列为DECBHGFA，试画出该二叉树。
31.写出题31图所示无向图的邻接矩阵，并写出每一个顶点的度。
题31图
32.已知散列表的地址空间为0至13，散列函数H=kmod11，，待散列序列为，用二次探测法解决冲突，架构该序列的散列表，需要写出处置冲突的过程。
33.将一组键值应用二路归并排序算法从小到大排序，试写出各趟的结果。
4、算法设计题
34.设单链表及链栈S的结构概念如下：
typedef struct node
{ Data Type data;
struct node*next;
｝linkstack;
撰写一个算法void ReverseList，借用于栈S将带头结点单链表head中序号为奇数的结点逆置，序号为偶数的结点维持不变。，逆置后变为)。
说明：栈的初始化运算用InitStack;进栈运算用Push;判栈空运算用EmptyStack;出栈运算用Pop;取栈顶元素运算用GetTOP。
35.以二叉链表作为存储结构，试撰写递归算法达成求二叉树中叶子结点个数。
