数据结构考试题3.doc
《数据结构考试题3.doc》由会员分享，可在线阅读，更多相关《数据结构考试题3.doc（7页珍藏版）》请在冰点文库上搜索。
要求：
所有的题目的解答均写在答题纸上，需写清楚题目的序号。
每张答题纸都要写上姓名和学号。
一、单项选择题（每小题2分，共计40分）
1.数据结构是指。
A.一种数据类型
B.数据的存储结构
C.一组性质相同的数据元素的集合
D.相互之间存在一种或多种特定关系的数据元素的集合
2.以下算法的时间复杂度为。
voidfun（intn）
{ inti=1;
while（i<=n）
i++;
}
A.O（n） B.O（）
C.O（nlog2n） D.O（log2n）
3.现要设计一个高效的算法，在一个长度为n的有序顺序表中删除所有元素值为x的元素（假设这样的元素是不唯一的），这样的算法时间复杂度为。
A.O（n） B.O（nlog2n）
C.O（n2） D.O（）
4.在一个带头结点的循环双链表L中，要删除p所指结点，算法的时间复杂度为。
A.O（n） B.O（）
C.O
（1） D.O（n2）
5.若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针top为n，则以下元素x进栈的正确操作是。
A.top++;s[top]=x; B.s[top]=x;top++;
C.top--;s[top]=x; D.s[top]=x;top--;
6.中缀表达式“2*（3+4）-1”的后缀表达式是，其中#表示一个数值的结束。
A.2#3#4#1#*+- B.2#3#4#+*1#-
C.2#3#4#*+1#- D.-+*2#3#4#1#
7.设循环队列中数组的下标为0～N-1，其队头、队尾指针分别为front和rear（front指向队列中队头元素的前一个位置，rear指向队尾元素的位置），则其元素个数为。
A.rear-front B.rear-front-1
C.（rear-front）％N+1 D.（rear-front+N）％N
8.若用一个大小为6的数组来实现循环队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。
若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。
A.1和5 B.2和4
C.4和2 D.5和1
9.一棵高度为h（h≥1）的完全二叉树至少有个结点。
A.2h-1 B.2h
C.2h+1 D.2h-1+1
10.一棵含有n个结点的线索二叉树中，其线索个数为。
A.2n B.n-1
C.n+1 D.n
11.设一棵哈夫曼树中有1999个结点，该哈夫曼树用于对个字符进行编码。
A.999 B.998
C.1000 D.1001
12.一个含有n个顶点的无向连通图采用邻接矩阵存储，则该矩阵一定是。
A.对称矩阵 B.非对称矩阵
C.稀疏矩阵 D.稠密矩阵
13.设无向连通图有n个顶点e条边，若满足，则图中一定有回路。
A.e≥n B.eC.e=n-1 D.2e≥n
14.对于AOE网的关键路径，以下叙述是正确的。
A.任何一个关键活动提前完成，则整个工程一定会提前完成
B.完成整个工程的最短时间是从源点到汇点的最短路径长度
C.一个AOE网的关键路径一定是唯一的
D.任何一个活动持续时间的改变可能会影响关键路径的改变
15.设有100个元素的有序表，用折半查找时，不成功时最大的比较次数是。
A.25 B.50
C.10 D.7
16.在一棵m阶B-树中删除一个关键字会引起合并，则该结点原有个关键字。
A.1 B.ém/2ù
C.ém/2ù-1 D.ém/2ù+1
17.哈希查找方法一般适用于情况下的查找。
A.查找表为链表
B.查找表为有序表
C.关键字集合比地址集合大得多
D.关键字集合与地址集合之间存在着某种对应关系。
18.对含有n个元素的顺序表采用直接插入排序方法进行排序，在最好情况下算法的时间复杂度为。
A.O（n） B.O（nlog2n）
C.O（n2） D.O（）
19.用某种排序方法对数据序列{24,88,21,48,15,27,69,35,20}进行递增排序，元素序列的变化情况如下：
（1）{24,88,21,48,15,27,69,35,20}
（2）{20,15,21,24,48,27,69,35,88}
（3）{15,20,21,24,35,27,48,69,88}
（4）{15,20,21,24,27,35,48,69,88}
则所采用的排序方法是。
A.快速排序 B.简单选择排序
C.直接插入排序 D.二路归并排序
20.以下排序方法中，不需要进行关键字的比较。
A.快速排序 B.归并排序 C.基数排序 D.堆排序
二、问答题（共4小题，每小题10分，共计40分）
1.如果一个含有n（n>1）个元素的线性表的运算只有4种：
删除第一个元素；删除最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用以下哪种存储结构（所有链表均带有头结点），并简要说明理由。
（1）只有尾结点指针没有头结点指针的循环单链表
（2）只有尾结点指针没有头结点指针的非循环双链表
（3）只有头结点指针没有尾结点指针的循环双链表
（4）既有头结点指针也有尾结点指针的循环单链表
2.对于图1所示的带权有向图，采用Dijkstra算法求从顶点0到其他顶点的最短路径，要求给出求解过程，包括每一步的S集合、dist和path数组元素。
图1一个有向图
3.有一棵二叉排序树按先序遍历得到的序列为：
（12,5,2,8,6,10,16,15,18,20）。
回答以下问题：
（1）画出该二叉排序树。
（2）给出该二叉排序树的中序遍历序列。
（3）求在等概率下的查找成功和不成功情况下的平均查找长度。
4.一个含有n个互不相同的整数的数组R[1..n]，其中所有元素是递减有序的，将其看成是一棵完全二叉树，该树构成一个大根堆吗？
若不是，请给一个反例，若是，请说明理由。
三、算法设计题（每小题10分，共计20分）
1.设A和B是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。
设计一个尽可能高效的算法求A和B的交集，要求不破坏A、B的结点，将交集存放在单链表C中。
给出你所设计的算法的时间复杂度和空间复杂度。
2.假设二叉树b采用二叉链存储结构，设计一个算法voidfindparent（BTNode*b,ElemTypex,BTNode*&p）求指定值为x的结点（假设这样的结点是唯一的）的双亲结点地址p，提示，根结点的双亲为NULL，若在b中未找到值为x的结点，p亦为NULL。
“数据结构”考试试题（A）参考答案
要求：
所有的题目的解答均写在答题纸上，需写清楚题目的序号。
每张答题纸都要写上姓名和学号。
一、单项选择题（每小题2分，共计40分）
1.D 2.A 3.A 4.C 5.C
6.B 7.D 8.B 9.A 10.C
11.C 12.A 13.A 14.D 15.D
16.C 17.D 18.A 19.A 20.C
二、问答题（共4小题，每小题10分，共计40分）
1.答：
本题答案为（3），因为实现上述4种运算的时间复杂度均为O
（1）。
【评分说明】选择结果占4分，理由占6分。
若结果错误，但对各操作时间复杂度作了分析，可给2～5分。
2.答：
该图对应的邻接矩阵如下：
在求最短路径时，S（存放顶点集），dist[]（存放最短路径长度）和path[]（存放最短路径）的变化如下：
Sdist[]path[]
0123401234
{0}
{0,4}
{0,1,4}
{0,1,2,4}
{0,1,2,3,4}
0
6
9
∞
2
0
0
0
-1
0
0
5
9
9
2
0
4
0
4
0
0
5
6
7
2
0
4
1
1
0
0
5
6
7
2
0
4
1
1
0
0
5
6
7
2
0
4
1
1
0
最后得到的结果如下：
顶点0到顶点1的最短距离为5，最短路径为：
0、4、1
顶点0到顶点2的最短距离为6，最短路径为：
0、4、1、2
顶点0到顶点3的最短距离为7，最短路径为：
0、4、1、3
顶点0到顶点4的最短距离为2，最短路径为：
0、4。
3.答：
（1）先序遍历得到的序列为：
（12,5,2,8,6,10,16,15,18,20），中序序列是一个有序序列，所以为：
（2,5,6,8,10,12,15,16,18,20），由先序序列和中序序列可以构造出对应的二叉树，如图2所示。
（2）中序遍历序列为：
2,5,6,8,10,12,15,16,18,20。
（3）ASL成功=（1×1+2×2+4×3+3×4）/10=29/10。
ASL不成功=（5×3+6×4/11=39/11。
图2
【评分说明】
（1）小题占6分，
（2）（3）小题各占2分。
4.该数组一定构成一个大根堆。
当R是递减时，其数组元素为k1、k2、…、kn，从中看出下标越大的元素值越小，对于任一元素ki，有ki>k2i，ki>k2i+1（i【评分说明】回答是给5分，说明理由给5分。
三、算法设计题（每小题10分，共计20分）
1.设A和B是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。
设计一个尽可能高效的算法求A和B的交集，要求不破坏A、B的结点，将交集存放在单链表C中。
给出你所设计的算法的时间复杂度和空间复杂度。
解：
算法如下：
voidinsertion（LinkList*A,LinkList*B,LinkList*&C）
{ LinkList*p=A->next,*q=B->next,*s,*t;
C=（LinkList*）malloc（sizeof（LinkList））;
t=C;
while（p!
=NULL&&q!
=NULL）
{ if（p->data==q->data）
{ s=（LinkList*）malloc（sizeof（LinkList））;
s->data=p->data;
t->next=s;
t=s;
p=p->next;
q=q->next;
}
elseif（p->datadata）
p=p->next;
else
q=q->next;
}
t->next=NULL;
}
算法的时间复杂度为O（m+n），空间复杂度为O（MIN（m,n））。
【评分说明】算法为8分，算法的时间复杂度和空间复杂度各占1分。
2.假设二叉树b采用二叉链存储结构，设计一个算法voidfindparent（BTNode*b,ElemTypex,BTNode*&p）求指定值为x的结点的双亲结点p，提示，根结点的双亲为NULL，若未找到这样的结点，p亦为NULL。
解：
算法如下：
voidfindparent（BTNode*b,ElemTypex,BTNode*&p）
{ if（b!
=NULL）
{ if（b->data==x）p=NULL;
elseif（b->lchild!
=NULL&&b->lchild->data==x）
p=b;
elseif（b->rchild!
=NULL&&b->rchild->data==x）
p=b;
else
{ findparent（b->lchild,x,p）;
if（p==NULL）
findparent（b->rchild,x,p）;
}
}
elsep=NULL;
}
【评分说明】本题有多种解法，相应给分。
升级会员 