for(j=0;j<=i;j++)
① s+=j;
A.(m+1)(m-1)/2 B.m(m-1)/2
C.(m+2)(m-1)/2 D.m(m+1)/2
3.求单链表中当前结点的后继和前驱的时间复杂度分别是( )
A.O(n)和O
(1) B.O
(1)和O
(1)
C.O
(1)和O(n) D.O(n)和O(n)
4.非空的单循环链表的头指针为head,尾指针为rear,则下列条件成立的是( )
A.rear->next==head B.rear->next->next==head
C.head->next==rear D.head->next->next==rear
5.若允许表达式内多种括号混合嵌套,则为检查表达式中括号是否正确配对的算法,通常选用的辅助结构是( )
A.栈 B.线性表
C.队列 D.二叉排序树
6.已知主串s=″ADBADABBAAB″,模式串t=″ADAB″,则应用朴素的串匹配算法进行模式匹配过程中,无效位移的次数是( )
A.2 B.3
C.4 D.5
7.串s=″DataStructure″中长度为3的子串的数目是( )
A.9 B.11
C.12 D.14
8.假设以行优先顺序存储三维数组R[6][9][6],其中元素R[0][0][0]的地址为2100,且每个元素占4个存储单元,则存储地址为2836的元素是( )
A.R[3][3][3] B.R[3][3][4]
C.R[4][3][5] D.R[4][3][4]
9.除第一层外,满二叉树中每一层结点个数是上一层结点个数的( )
A.1/2倍 B.1倍
C.2倍 D.3倍
10.对于含n个顶点和e条边的图,采用邻接矩阵表示的空间复杂度为( )
A.O(n) B.O(e)
C.O(n+e) D.O(n2)
11.如果求一个连通图中以某个顶点为根的高度最小的生成树,应采用( )
A.深度优先搜索算法 B.广度优先搜索算法
C.求最小生成树的prim算法 D.拓扑排序算法
12.快速排序在最坏情况下的时间复杂度是( )
A.O(n2log2n) B.O(n2)
C.O(nlog2n) D.O(log2n)
13.能进行二分查找的线性表,必须以( )
A.顺序方式存储,且元素按关键字有序
B.链式方式存储,且元素按关键字有序
C.顺序方式存储,且元素按关键字分块有序
D.链式方式存储,且元素按关键字分块有序
14.为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为( )
A.05 B.37
C.41 D.62
15.ISAM文件的周期性整理是为了空出( )
A.磁道索引 B.柱面索引
C.柱面基本区 D.柱面溢出区
二、填空题(本大题共10小题,每小题2分,共20分)
请在每小题的空格中填上正确答案。
错填、不填均无分。
16.数据类型按其值能否分解,通常可分为_________两种类型。
17.队列的修改是按_________的原则进行的。
18.两个串相等的充分必要条件是两个串的长度相等且_________。
19.数组采用顺序存储方式表示是因为通常不对数组进行_________操作。
20.用广义表的取表头head和取表尾tail的运算,从广义表LS=(b,c,(f),((d)))中分解出原子c的操作为_________。
21.结点数为20的二叉树可能达期的最大高度为_________。
22.带权连通图的生成树的权是该生成树上_________。
23.所谓“就地排序”,是指排序算法辅助空间的复杂度为_________的排序方法。
24.5阶B树的根结点至少含有_________个关键字。
25.索引文件中的索引表指示记录的关键字与_________之间一一对应的关系。
三、解答题(本大题共4小题,每小题5分,共20分)
26.假设以有序对
表示从双亲结点到孩子结点的一条边,若已知树中边的集合为{,,,,,,,,,},请回答下列问题:
(1)哪个结点是根结点?
(2)哪些结点是叶子结点?
(3)哪些结点是k的祖先?
(4)哪些结点是j的兄弟?
(5)树的深度是多少?
(1)
(2)
(3)
(4)
(5)
27.已知有向图G的深度优先生成森林和广度优先生成森林如下。
请写出该图的深度优先遍历序列和广度优先遍历序列。
28.当将两个长度均为n的有序表A=(a1,a2,…,an)与B=(b1,b2,…,bn)(ai≠bj,
1≤i,j≤n)归并为一个有序表C=(c1,c2,…,c2n)时,所需进行的元素比较次数最少可达n,最多可达2n-1。
(1)假设有序表C=(2,4,5,6,7,9),试举出两组A与B的例子,使它们在归并过程中进行的元素比较次数分别达到最少和最多;
(2)写出一般情况下,使归并所需进行的元素比较次数分别达到最少和最多时,A与B中的元素应满足的条件。
(1)
(2)
29.对下列关键字序列(33,25,48,59,36,72,46,07,65,20)构造表长为19的散列表。
假设散列函数为h(key)=key%13,用开放地址法解决冲突,探查序列为d=h(key),d+12,d-12,d+22,d-22,d+32,d-32,…,等等。
(1)画出该散列表;
(2)计算该散列表的装填因子α;
(3)求出等概率情况下查找成功的平均查找长度ASL。
(1)
(2)
(3)
四、算法阅读题(本大题共4小题,每小题5分,共20分)
30.已知head为带头结点的单循环链表的头指针,链表中的数据元素依次为(a1,a2,a3,a4,…,an),A为指向空的顺序表的指针。
阅读以下程序段,并回答问题:
(1)写出执行下列程序段后的顺序表A中的数据元素;
(2)简要叙述该程序段的功能。
if(head->next!
=head)
{
p=head->next;
A->length=0;
while(p->next!
=head)
{
p=p->next;
A->data[A->length++]=p->data;
if(p->next!
=head)p=p->next;
}
}
(1)
(2)
31.已知链串的存储结构描述如下:
#defineNodeSize4
typedefstructNode{
chardata[NodeSize];
structNode*next;
}*LinkStr;
阅读下列算法,并回答问题:
(1)t1和t2的串值分别为″Chinese″和″China″时,写出f31(t1,t2)的返回值;
(2)t1和t2的串值分别为″Japan″和″Japanese″时,写出f31(t1,t2)的返回值;
(3)t1和t2的串值都为″string″时,写出f31(t1,t2)的返回值;
(4)简述函数f31的功能。
inff31(LinkStrt1,LinkStrt2)
{//串值以′′为结束符
inti;
while
(1){
for(i=0;iif(t1->data[i]==′′&&t2->data[i]==′′return0;
if(t1->data[i]==′′))return–1;
if(t2->data[i]==′′))return1;
if(t1->data[i]>t2->data[i]return1;
if(t1->data[i]data[i]return–1;
}
t1=t1->next;
t2=t2->next;
}
}
(1)
(2)
(3)
(4)
32.设二叉树采用二叉链表存储结构,结点的数据域data为字符类型。
阅读下列算法,并回答问题:
(1)对于如图所示的二叉树,写出执行函数f32的输出结果;
(2)简述函数f32的功能。
voidf32(BinTreeT)
{Stacks; //定义栈s
BinTreep,q;
if(T==NULL)return;
InitStack(&s);
p=T;
do{
while(p){
Push(&s,p);
if(p->lchild)p=p->lchild;
elsep=p->rchild;
}
while(!
StackEmpty(s)&&q=StackTop(s)&&q->rchild==p){
p=Pop(&s);
printf(″%c″,p->data);
}
if(!
StackEmpty(s)){
q=StackTop(s);
p=q->rchild;
}
}while(!
StackEmpty(S));
}
(1)
(2)
33.已知有向图的邻接表表示的形式说明如下:
#defineMaxNum 50 //图的最大顶点数
typedefstructnode{
intadjvex; //邻接点域
structnode*next; //链指针域
}EdgeNode; //边表结点结构描述
typedefstruct{
charvertex; //顶点域
EdgeNode*firstedge; //边表头指针
}VertexNode;//顶点表结点结构描述
typedefstruct{
VertexNodeadjlist[MaxNum]; //邻接表
intn,e; //图中当前的顶点数和边数
}ALGraph;//邻接表结构描述
下列函数f33是从有向图G中删除所有以vi为弧头的有向边。
请在空缺处填入合适的内容,使其成为一个完整的算法。
voidf33(ALGraph*G,inti)
{intj;
EdgeNode*p,*q;
for(j=0;jn;j=++){
p=G->adjlist[j].firstedge;
while(
(1) {
q=p; p=p->next;
}
if(p!
=NULL){
if(p!
=G->adjlist[j].firstedge)q->next=p->next;
else(
(2) ;
free(p);
G->e=( (3) ;
}
}
}
(1)
(2)
(3)
五、算法设计题(本大题10分)
34.在带头结点的循环链表L中,结点的数据元素为整型,且按值递增有序存放。
给定两个整数a和b,且a