数据结构考试题9.doc

(完整word版)数据结构考试题9
要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。
一、单项选择题（每小题2分，共20小题，共计40分）
1、设n是描述问题规模的非负整数，下面程序片段的时间复杂度为（ ）。
x=1;
while (x<=n)
x=5*x;
A. O(log5n) B.O(n) C.O(nlog5n) D.O(n5)
2、顺序表和链表相比存储密度较大，这是因为（ ）。
A.顺序表的存储空间是预先分配的
B.顺序表不需要增加指针来表示元素之间的逻辑关系
C.链表中所有节点的地址是连续的
D.顺序表中所有元素的存储地址是不连续的
3、在长度为n（n≥1）的循环双链表L中，在尾节点之后插入一个新节点的时间复杂度为（ ）。
A. O(n2) B.O(n) C. O(1) D.O(nlog2n)
4、设栈的输入序列是1、2、3、4，则（ ）不可能是其出栈序列。
A.1，2，4，3 B.2，1，3，4 C.1，4，3，2 D.4，3，1，2
5、当用一个数组data[0..n-1]存放栈中元素时，栈底最好（ ）。
A. 设置在data[0]或data[n-1]处 B.设置在data[n-1]处
C. 设置在data[0]处 D.设置在data数组的任何位置
6、在数据处理过程中常需要保存一些中间数据，如果先保存的数据先处理，则使用（ ）来保存这些数据。
A.线性表 B. 队列 C. 栈 D.单链表
7、在环形队列中，元素的排列顺序（ ）。
A.与队头和队尾指针的取值有关 B.与元素值的大小有关
C.由元素进队的先后顺序确定 D.与存放队中元素的数组大小有关
8、将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。
A.100 B.40 C.80 D.55
9、设目标串为s，模式串为是t，在KMP模式匹配中，next[4]=2的含义是（ ）。
A.表示t4字符前面最多有2个字符和开头的2个字符相同
B.表示s4字符前面最多有2个字符和开头的2个字符相同
C.表示目标串匹配失败的位置是i=4
D.表示模式串匹配失败的位置是j=2
10、由权值分别为9、2、7、5的四个叶子节点构造一棵哈夫曼树，该树的带权路径长度为（ ）。
A.23 B.44 C.37 D.27
11、对于无向图的邻接矩阵来说，（ ）。
A.第i行上、第i列上非零元素总数等于顶点i的度数
B.矩阵中的非零元素个数等于图中的边数
C.第i行上的非零元素个数和第i列的非零元素个数一定相等
D.邻接矩阵中非全零行的行数等于图中的顶点数
12、有一个顶点编号为0～4的带权有向图G，现用Floyd算法求任意两个顶点之间的最短路径，在算法执行的某时刻，已考虑了0～2的顶点，现考虑顶点3，则以下叙述中正确的是（ ）。
A.只可能修改从顶点0～2到顶点3的最短路径
B.只可能修改从顶点3到顶点0～2的最短路径
C.只可能修改从顶点0～2到顶点4的最短路径
D.所有两个顶点之间的路径都可能被修改
13、适合于折半查找的数据组织方式是（ ）。
A.以顺序表存储的有序线性表 B.以顺序表存储的线性表
C.以链表存储的有序线性表 D. 以链表存储的线性表
14、对含有n个元素的顺序表采用顺序查找方法，不成功时的比较次数是（ ）。
A. 1 B. n C. n-1 D. n+1
15、在一棵平衡二叉树中，每个节点的平衡因子的取值范围是（ ）。
A. 1～2 B. -2～2 C. -1～1 D. 0～1
16、在一棵m阶B-树中删除一个关键字会引起合并，则该节点原有（ ）个关键字。
A. 1 B. ém/2ù C. ém/2ù+1 D. ém/2ù-1
17、以下关于哈希查找的叙述中正确的是（ ）。
A.哈希查找中不需要任何关键字的比较
B.采用拉链法解决冲突时，查找每个元素的时间是相同的
C.哈希表在查找成功时的平均查找长度仅仅与表长有关
D.哈希表的装填因子等于表中填入的记录数除以哈希表的长度
18、以下排序方法中，（ ）在初始序列已基本有序的情况下，排序效率最高。
A.二路归并排序 B. 快速排序 C. 直接插入排序 D.堆排序
19、如要在1000个整数中找出前10个最小的整数，在以下排序方法中最好采用（ ）。
A.直接插入排序 B. 冒泡排序 C.二路归并排序 D. 希尔排序
20、有n个十进制整数进行基数排序，其中最大的整数为5位，则基数排序过程中临时建立的队数个数是（ ）。
A.10 B.n C.5 D.2
二、问答题（共4小题，共计35分）
1、（8分）已知一棵二叉树的先序遍历序列为ABDGHCEIF，它的中序遍历序列是BGDHAEICF，请构造出这棵二叉树，并给出其层次遍历序列。
2、（8分）一棵二叉排序树的结构如图1所示，其中各结点的关键字依次为32～40，请标出各结点的关键字。

图1 一棵二叉排序树的结构
3、（8分）一组记录关键字为（5，11，7，2，3，17），利用堆排序方法建立初始大根堆，给出你建立的初始大根堆对应的关键字序列。
4、（11分）对于一个带权连通无向图G，可以采用Prim算法构造出从某个顶点v出发的最小生成树，问该最小生成树一定包含从顶点v到其他所有顶点的最短路径吗？如果回答是，请予以证明；如果回答不是，请给出反例。
三、算法设计题（共2小题，共计25分）
1. （15分）有两个递增有序表，所有元素为整数，均采用带头结点的单链表存储，结点类型定义如下：
typedef struct node
{ int data;
struct node *next;
} LinkNode;
设计一个尽可能高效的算法，将两个递增有序单链表ha、hb合并为一个递减有序单链表hc，要求算法空间复杂度为O(1)。
2、（10分）设二叉树中每个结点存放单个字符，其结点类型如下：
typedef struct node
{ char data;
struct node *lchild，*rchild;
} BTNode;
设计一个算法求其中单分支的结点个数。
“数据结构”考试试题（A）参考答案
一、单项选择题（每小题2分，共20小题，共计40分）
1、A 2、B 3、C 4、D 5、A
6、B 7、C 8、D 9、A 10、B
11、C 12、D 13、A 14、B 15、C
16、D 17、D 18、C 19、B 20、A

二、问答题（共4小题，共计35分）
1、（8分）最后构造的二叉树如图1所示（4分），其层次遍历序列为ABCDEFGHI（4分）。

A
B
C
D
G
H
F
I
E

图1 一棵二叉树
2、（8分）得到如图2所示的二叉排序树（中序序列是递增的）。
36
32
40
35
37
33
38
34
39

图2 一棵二叉排序树
3、（8分）初始大根堆对应的关键字序列为（17，11，7，2，3，5），如果画出树正确但没有给出序列扣2分。
4、（11分）不是。
反例：如图3所示的图G从顶点0出发的最小生成树如图4所示，而从顶点0到顶点的2的最短路径为0®2，而不是最小生成树中的0®1®2。

图3 一个带权连通无向图G 图4 图G的一棵最小生成树
评分说明：回答“不是”或者“不一定”给5分，反例部分为6分。回答“是”本题为0分。
三、算法设计题（共2小题，共计25分）
1. （15分）参考算法如下：
void merge(LinkNode *ha， LinkNode *hb， LinkNode *&hc)
{ LinkNode *pa=ha->next，*pb=hb->next，*q;
free(hb);
hc=ha; hc->next=NULL; //hc利用ha的头结点，并设置为空
while (pa!=NULL && pb!=NULL) //扫描ha、hb的数据结点
{ if (pa->data<pb->data) //将较小结点采用头插法插入到hc中
{ q=pa->next;
pa->next=hc->next;
hc->next=pa;
pa=q;
}
else
{ q=pb->next;
pb->next=hc->next;
hc->next=pb;
pb=q;
}
}
if (pb!=NULL) pa=pb;
while (pa!=NULL) //将没有扫描完的结点采用头插法插入到hc中
{ q=pa->next;
pa->next=hc->next;
hc->next=pa;
pa=q;
}
}
评分说明：上述算法的时间复杂度为O(m+n)。若设计的算法时间复杂度为O(m*n)，至少扣3分，若设计的算法空间复杂度不为O(1)，扣2分。
2、（10分）参考算法如下：
int singleodes(BTNode *b)
{ if (b==NULL) return 0;
if ((b->lchild==NULL && b->rchild!=NULL) || //单分支的结点
(b->lchild!=NULL && b->rchild==NULL)
return singleodes(b->lchild)+ singleodes(b->rchild)+1;
else
return singleodes(b->lchild)+ singleodes(b->rchild);
）
评分说明：可以采用任意一种遍历方法。判断单分支的结点为3分。