科目代码： 407 科目名称： 数据结构 (共4页)
请考生写明题号，将答案全部答在答题纸上，答在试卷上无效
一、单项选择题（本大题共15道小题 ，每小题3分，共45分）
1．若解决某个问题有两个算法X和Y，其中X的时间复杂度为T(n)=O( )，Y 的时间复杂度为T(n)=O(log2n)，就时间复杂度而言，哪个更好？ 【 】
A. 算法X好于算法Y B. 算法Y 好于算法X
C. 不确定 D. 其实两个算法一样
2．由两个栈共享一个向量空间的好处是：
A． 减少存取时间，降低上溢发生的机率 B. 节省存储空间，降低上溢发生的机率
C．减少存取时间，降低下溢发生的机率 D. 节省存储空间，降低下溢发生的几率
3．一个广义表的表头 【 】
不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是子表或原子
4. 某二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则前序序列为 【 】
A. CEDBA B. DECAB C. DEABC D. ACBED
5. 在下列的排序方法中，最耗费内存量的是 【 】
A. 插入排序 B 快速排序 C. 选择排序 D. 归并排序
6. m阶B_树中所有的非叶子（除根之外）结点中的关键字个数必须大于或者等于 【 】
A. B. －1 C. D. －1
7．已知一个有序表为｛3,5,7,8,11,15,17,22,23,27,29,33｝，当采用二分查找法查找值为27时，需要比较几次才能查找成功？ 【 】
A．4 B. 3 C. 10 D. 不确定
8．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为 【 】
A．e B. 2e C. n2－e D. n2－2e
9．为了采用动态查找表进行高效率的查找，数据的组织结构最好采用 【 】
A．有序表 B. 线性链表 C. 二叉排序树 D. 分块有序表
10．若一棵二叉树有21个结点，且无度为1的结点，则叶子结点的个数为 【 】
A．9 B. 10 C. 11 D. 12
11. 设计一个好的哈希函数，其函数值应该以什么概率取其值域的每个值。 【 】
A．同等概率 B. 随机概率 C. 最大概率 D. 最小概率
12. 下列排序方法中，其比较次数与待排序关键字的初始状态无关的是 【 】
A. 冒泡排序 B. 二分法插入排序 C.快速排序 D. 直接插入排序
13. 已知广义表Glist＝((a),(b,c,d),((e)))，使用head和tail函数取出Glist中原子b的运算应是 【 】
A. head(head(Glist)) B. tail(head(Glist))
C. head(head(tail(Glist))) D. head(tail(Glist))
14. 用邻接表表示图进行广度优先遍历时，通常采用哪种结构实现算法。 【 】
A. 栈 B.队列 C.二叉树 D.图
15. 设哈希表长m=14，哈希函数H(K)=K%11。表中已有四个关键字，如果使用二次探测再散列处理冲突，关键字为49的存储地址为 【 】
0 1 2 3 4 5 6 7 8 9 10 11 12 13
17 33 8 21
A. 3 B. 5 C. 8 D. 9
二、填空题（本大题共10小题，每题2分，共20分）
1. 在循环链表中，可根据任意结点的地址遍历整个链表，而单链链表则知道__________才能够遍历整个链表。
2. 在顺序表中，访问任一结点的时间复杂度为__________。
3. 设循环队列的空间大小为MAX，当rear<front时，队列的长度为_________________。
4. 前序序列为A、B、C，并且后序序列为C、B、A的二叉树，共有___________棵。
5. 将一棵树转换为二叉树后，则二叉树的根结点没有_______子树。
6. 用迪杰斯特拉（Dijkstra）算法求某一顶点到其余各顶点的最短路径，是按路径长度_____的次序进行求解的。
7. AOV网的拓扑序列_______唯一的。
8. 在各种查找方法中，平均查找长度与关键字个数n无关的查找方法是________。
9. 设一组记录的关键字为｛45, 80, 55, 35, 40, 85｝，则利用快速排序的方法，以第一个关键字为基准，得到的一次划分结果为______________________。
10. 设一组记录的关键字为｛45, 80, 55, 35, 40, 85｝，则利用堆排序的方法，建立的初始大根堆为_______________________。
三、解答题（本大题共4道小题，每小题10分，共40分）
就顺序队列中的“假溢出”现象，请给出解决它的思想及队空、队满的判断问题。
2. 对给定的关键字集合，以不同的次序插入初始状态为空的树中，是否可以得到同一棵二叉排序树？试给出一个具体的例子证明你的结论。
3. 已知关键字序列为｛Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec｝，试回答：
(1) 按表中元素的顺序，构造一棵平衡二叉排序树。
(2) 在等概率的情况下，求查找成功的ASL值。
4. 已知一个带权的连通图G(V, E)的邻接表如下图所示。请回答：
画出该图。
从顶点V2出发，给出DFS序列。
从顶点V3出发，给出BFS序列。
画出该图的一棵最小生成树。
四、算法阅读题（本大题共2道小题，每题12分，共24分）
【说明】 结构定义
struct ListNode {
elemtype data;
struct ListNode *next;
};
struct BTreeNode {
elemtype data;
struct BtreeNode *lchild, *rchild;
};
1. 下面的是对某个带头结点的单链表的操作，试说明得法的功能。
Void DSNode(ListNode *head)
{ ListNode *p, *q, *r;
p = head->next;
while(p){
q = p; r = q->next;
do{
while( r && r->data != p->data){
q= r;
r= r->next;
}
if(r){
q->next = r->next;
delete r;
r = q->next; }
} while(r);
p = p->next;
}
}
2. 下面的算法是一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。请在空白处填入正确的语句。
Void DoubleBubble{int a[], int n}
{
int i=0, j, temp, exchange =1;
while(exchange){
exchange=0;
for(j=n-i-1;j>i;j--)
if(a[j]<a[j-1]){ // 由底向上
exchange = 1;
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
for(j=_____; j<______; j++)
if(_______){
exchange =_________;
temp = a[j];
___________;
a[j+1]=temp;
}
j++;
}
}
五、算法设计题（本大题共3道小题，每道7分，共21分）
1. 设单链表中存放着若干个字符，试设计算法判断该字符串是否中心对称。例如
ABCBA、ABCCBA都是中心对称的字符串。
【要求】 必须使用栈结构。
int isSymmetry(struct ListNode *head)
{
2. 以单链表为存储结构，试编写一个直接选择排序算法。
【要求】 (1)说明直接选择排序的思想。
(2)给出算法。
Void SelectSort(struct ListNode *head)
{
证明：对一个长度为n的任意顺序表进行排序，至少需要进行nlog2n次比较。
最新评论