中南林业科技大学课程考试试卷
课程名称： 数据结构 ；考试时间：120分钟
一、
判断题(每题1分,共10分，正确划“√”，错误划“×”)
（ ） 1、算法分析的两个主要方面是空间复杂度和时间复杂度。
（ ）2、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧
邻。
（ ）3、在对不带头结点的链队列作出队操作时，不会改变头指针的值。 （ ）4、空串是由空白字符组成的串。 （ ）5、树的度是树内各结点的度之和。
( ) 6、任一AOE 网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。 （ ）7、若一个图的邻接矩阵为对称矩阵，则该图必为无向图。 （ ）8、任何AOV 网拓扑排序的结果都是唯一的。
（ ）9、在哈希表中，若装填因子越大，则发生冲突的机会越少。 （ ）10、直接插入排序的时间复杂度为O （n ）。
二、填空题（每题2分，共20分）
1、数据的逻辑结构可形式化地用一个二元组B=（K ，R ）来表示，其中K 是 , R 是 。
2、在一个长度为n 的向量中删除第i （1≤i ≤n ）个元素时，需向前移动 个元素。
3、用下标0开始的N 元数组实现循环队列时，为实现下标变量m 加1后在数组有效下标范围内循环，可采用的表达式是：m =____________________。
4、从一个栈顶指针为HS 的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 操作。
5、在无向网G 的邻接矩阵A 中，若A[i][j]等于100，则A[j][i]等于 。
软件工程 专业班级 软件工程 专业班级 1、2，程 专业班级 1、2，3，4
装订线(答题不得超过此线)
6、遍历图的基本方法有优先搜索和深度优先搜索。
7、有序表(05,13,19,21,37,56,64,75,80,88,92)中，折半查找56时，其关键码的比较次数为。
8、直接选择排序是不稳定的，它的时间复杂度为。
9、具有n个结点的二叉树，采用二叉链表存储，共有个空链域。
10、在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的。
三、单项选择题（每题2分，共20分）
1、算法分析的目的是（）。
A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系
C.分析算法的效率以求改进
D. 分析算法的易懂性和文档性
2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A．单链表 B. 仅有头指针的单循环链表
C . 双链表
D . 仅有尾指针的单循环链表
3、一个栈的入栈序列是1,2,3,4,5，则下列序列中不可能的出栈序列是( )
A. 2,3,4,1,5
B. 5,4,1,3,2
C. 2,3,1,4,5
D. 1,5,4,3,2
4、队列操作的原则是( )。
A. 先进先出
B. 后进先出
C. 只能进行插入
D. 只能进行删除
5、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。
A．15 B. 16 C. 17 D.47
6、由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为( )。
A. 23
B. 37
C. 46
D. 44
7、n个顶点的强连通图至少有( )条边。
A. n
B. n-1
C. n+1
D. n(n-1)
8、采用邻接表存储的图的广度优先遍历类似于二叉树的( )。
A．按层次遍历 B. 中序遍历 C. 后序遍历 D. 先序遍历
9、10个元素的有序表，等概率条件下折半查找成功的平均查找长度是（）。
A．2.9 B. 3 C. 4.5 D. 5.0
10、若数据表中每个元素已距其最终位置不远时，则采用（）算法进行排序最省时间。
A．堆排序 B. 选择排序 C. 快速排序 D. 插入排序
四、简答题（共30分）
1、在《数据结构》课程中，你学习了哪些算法？请至少列举10个算法名称。（5分）
2、指定Hash函数H(k)=3*kmod11及线性探测开放地址法处理冲突，试在0~10的散列空间中对关键字序列（22,41,53,46,30,13,01,67）构造哈希表，并求在等概率下查找成功的平均查找长度。（6分）
3、下列算法的功能是求带头结点的单链表的表长，请完善。（3分）
int count(LinkList head)
{ ; length=0;
while ( p!=NULL )
{ length++ ; ; }
;
}
4、有7个顶点（v1,v2,v3,v4,v5,v6,v7）的有向图
（1）画出该有向图（2分）
（2）画出邻接表（2分）
（3）写出从v1出发的深度优先遍历和广度优先遍历序列（4分）
5、设文件中各记录的关键码为{49，38，65，97，76，13，27}。欲用快速排序算法将其按关键
码从小到大排序。请写出每一趟的排序结果。(4分)
6、阅读下列算法，并回答问题（4分）
(1)Q,，Q1和Q2都是队列结构，设队列Q=(1,0,-5,2,-4,-8,9),其中1为队头元素，写出执行f31(&Q,&Q1,&Q2)之后Q，Q1和Q2 的状态；
（2）简述算法f31的功能。
（注InitQueue,EnQueue,DeQueue和QueueEmpty分别是队列初始化、入队、出队和队空的操作） Void f31(Queue *Q,Queue *Q1,Queue *Q2) {
int e;
InitQueue(Q1);
InitQueue(Q2);
While(!QueueEmpty(Q)) {
E=DeQueue(Q);
if (e>=0) EnQueue(Q1,e);
else EnQueue(Q2,e);
}
}
五、设二叉树以二叉链表形式存储，请编写一个求叶子结点总数的算法。（10分）
六、设单链表L中的结点按data域数值递减排列，试设计一个算法将L中的结点按data域数值递增排列，要求算法的时间复杂性为O（n）。（10分）
