C.e=n-1 D.2e≥n
11.如果从无向图的任一顶点出发进行一次广度优先遍历即可访问所有顶点，则该图一定是。
A.完全图 B.连通图
C.有回路 D.一棵树
12.设有100个元素的有序表，用折半查找时，不成功查找时最大的比较次数是。
A.25 B.50
C.10 D.7
13.从100个元素确定的顺序表中查找其中某个元素（关键字为正整数），如果最多只进行5次元素之间的比较，则采用的查找方法只可能是。
A.折半查找 B.顺序查找
C.哈希查找 D.二叉排序树查找
14.有一个含有n（n>1000）个元素数据序列，某人采用了一种排序方法对其按关键字递增排序，该排序方法需要关键字比较，其平均时间复杂度接近最好的情况，空间复杂度为O
（1），该排序方法可能是。
A.快速排序 B.堆排序
C.二路归并排序 D.都不适合
15.对一个线性序列进行排序，该序列采用单链表存储，最好采用排序方法。
A.直接插入排序 B.希尔排序
C.快速排序 D.都不适合
二、问答题（共3小题，每小题10分，共计30分）
1.如果对含有n（n>1）个元素的线性表的运算只有4种：
删除第一个元素；删除最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用以下哪种存储结构，并简要说明理由。
（1）只有尾结点指针没有头结点指针的循环单链表
（2）只有尾结点指针没有头结点指针的非循环双链表
（3）只有头结点指针没有尾结点指针的循环双链表
（4）既有头结点指针也有尾结点指针的循环单链表
2.对于一个带权连通无向图G，可以采用Prim算法构造出从某个顶点v出发的最小生成树，问该最小生成树是否一定包含从顶点v到其他所有顶点的最短路径。
如果回答是，请予以证明；如果回答不是，请给出反例。
3.有一棵二叉排序树按先序遍历得到的序列为：
（12,5,2,8,6,10,16,15,18,20）。
回答以下问题：
（1）画出该二叉排序树。
（2）给出该二叉排序树的中序遍历序列。
（3）求在等概率下的查找成功和不成功情况下的平均查找长度。
三、算法设计题（共3小题，共计40分）
1.（15分）假设二叉树b采用二叉链存储结构，设计一个算法voidfindparent（BTNode*b,ElemTypex,BTNode*&p）求指定值为x的结点的双亲结点p。
提示，根结点的双亲为NULL，若在二叉树b中未找到值为x的结点，p亦为NULL。
2.（10分）假设一个有向图G采用邻接表存储。
设计一个算法判断顶点i和顶点j（i≠j）之间是否相互连通，假设这两个顶点均存在。
3.（15分）有一个含有n个整数的无序数据序列，所有的数据元素均不相同，采用整数数组R[0..n-1]存储，请完成以下任务：
（1）设计一个尽可能高效的算法，输出该序列中第k（1≤k≤n）小的元素，算法中给出适当的注释信息。
提示：
利用快速排序的思路。
（2）分析你所设计的求解算法的平均时间复杂度，并给出求解过程。
“数据结构”考试试题（A）参考答案
要求：
所有的题目的解答均写在答题纸上，需写清楚题目的序号。
每张答题纸都要写上姓名和学号。
一、单项选择题（共15小题，每小题2分，共计30分）
1.D 2.B 3.A 4.C 5.D
6.B 7.A 8.C 9.A 10.A
11.B 12.D 13.C 14.B 15.A
二、问答题（共3小题，每小题10分，共计30分）
1.答：
本题答案为（3），因为实现上述4种运算的时间复杂度均为O
（1）。
2.答：
不是。
如图1所示的图G从顶点0出发的最小生成树如图2所示，而从顶点0到顶点的2的最短路径为0®2，而不是最小生成树中的0®1®2。
图1一个带权连通无向图G 图2图G的一棵最小生成树
3.答：
（1）先序遍历得到的序列为：
（12,5,2,8,6,10,16,15,18,20），中序序列是一个有序序列，所以为：
（2,5,6,8,10,12,15,16,18,20），由先序序列和中序序列可以构造出对应的二叉树，如图3所示。
4分
（2）中序遍历序列为：
2,5,6,8,10,12,15,16,18,20。
4分
（3）ASL成功=（1×1+2×2+4×3+3×4）/10=29/10。
1分
ASL不成功=（5×3+6×4/11=39/11。
1分
图3
三、算法设计题（共3小题，共计40分）
1.（15分）解：
算法如下：
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;
}
2.（10分）解：
算法如下：
intvisited[MAXV];
voidDFS（ALGraph*G,intv） //深度优先遍历算法
{ ArcNode*p;
visited[v]=1; //置已访问标记
p=G->adjlist[v].firstarc; //p指向顶点v的第一个邻接点
while（p!
=NULL）
{ if（visited[p->adjvex]==0） //若p->adjvex顶点未访问,递归访问它
DFS（G,p->adjvex）;
p=p->nextarc; //p指向顶点v的下一个邻接点
}
}
boolDFSTrave（ALGraph*G,inti,intj）
{ intk;
boolflag1=false,flag2=false;
for（k=0;kn;k++）
visited[k]=0;
DFS（G,i）; //从顶点i开始进行深度优先遍历
if（visited[j]==1）
flag1=true;
for（k=0;kn;k++）
visited[k]=0;
DFS（G,j）; //从顶点j开始进行深度优先遍历
if（visited[i]==1）
flag2=true;
if（flag1&&flage2）
returntrue;
else
returnfalse;
}
3.（15分）
（1）采用快速排序的算法如下：
（12分）
intQuickSelect（intR[],ints,intt,intk）//在R[s..t]序列中找第k小的元素
{ inti=s,j=t;
inttmp;
if（s { tmp=R[s]; //用区段的第1个记录作为基准
while（i!
=j） //从区段两端交替向中间扫描,直至i=j为止
{ while（j>i&&R[j]>=tmp）
j--; //从右向左扫描,找第1个小于tmp的R[j]
R[i]=R[j]; //将R[j]前移到R[i]的位置
while（i i++; //从左向右扫描,找第1个大于tmp的R[i]
R[j]=R[i]; //将R[i]后移到R[j]的位置
}
R[i]=tmp;
if（k-1==i）returnR[i];
elseif（k-1 elsereturnQuickSelect（R,i+1,t,k）; //在右区段中递归查找
}
elseif（s==t&&s==k-1） //区段内只有一个元素且为R[k-1]
returnR[k-1];
}
voidMink（intR[],intn,intk）//输出整数数组R[0..n-1]中第k小的元素
{ if（k>=1&&k<=n）
printf（"%d\n",QuickSelect（R,0,n-1,k））;
}
（2）对于求R中第k小元素的算法Mink（R，n，k），设其算法平均执行时间为T（n），有以下递推式：
（3分）
T
（1）=1
T（n）=T（n/2）+O（n）
则：
T（n）=T（n/2）+O（n）=T（n/22）+O（n）+O（n/2）=…
=T（n/2m）+O（n）+O（n/2）+…+O（n/2m）//m=log2n
=O
（1）+O（n）+O（n）
=O（n）
所以，该算法的平均时间复杂度为O（n）。
升级会员 