A[i][j]=i*j;
A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)
24.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。
假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为()
A、q->next=s->next;s->next=p;B、s->next=p;q->next=s->next;
C、p->next=s->next;s->next=q;D、s->next=q;p->next=s->next;
25.为便于判别有向图中是否存在回路,可借助于()
A、广度优先搜索算法B、最小生成树算法
C、最短路径算法D、拓扑排序算法
26.若以S和X分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是()
A、SXSSXXXXB、SXXSXSSX
C、SXSXXSSXD、SSSXXSXX
27.设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是()
A、2B、3C、5D、6
28.假设以数组A[m]存放循环队列的元素。
已知队列的长度为length,指针rear指向队尾元素的下一个存储位置,则队头元素所在的存储位置为()。
A、(rear-length+m+1)%mB、(rear-length+m)%m
C、(rear-length+m-1)%mD、(rear-length)%m
29.在一个链队列中,front和rear分别为头指针和尾指针,则插入一个结点s的操作为()。
A、s->next=rear;rear=s;B、front=front->next;
C、s->next=front;front=s;D、rear->next=s;rear=s;
30.对于哈希函数H(key)=key%13,被称为同义词的关键字是()
A、35和41B、23和39C、15和44D、25和51
31.采用二叉链表存储的n个结点的二叉树,共有空指针()个。
A、n+1B、nC、n-1D、2n-1
32.连通网的最小生成树是其所有生成树中()
A、顶点集最小的生成树B、边集最小的生成树
C、顶点权值之和最小的生成树D、边的权值之和最小的生成树
33.对记录序列(314,298,508,123,486,145)依次按个位和十位进行两趟基数排序之后所得结果为()
A、123,145,298,314,486,508B、508,314,123,145,486,298
C、486,314,123,145,508,298D、298,123,508,486,145,314
34.任何一个无向连通图的最小生成树()。
A、一定有多棵B、可能不存在C、一棵或多棵D、只有一棵
35.无向图的邻接矩阵是一个()
A、对角矩阵B、上三角矩阵C、对称矩阵D、零矩阵
36.设无向图G-=(V,E)和G’=(V’,E’),如G’为G的生成树,则下列说法中不正确的是()。
A、G’为G的无环子图B、G’为G连通分量
C、G’为G极小连通子图且V’=VD、G’为G的子图
37.
以v1为起始结点对下图进行深度优先遍历,正确的遍历序列是()
A、v1,v2,v3,v4,v5,v6,v7
B、v1,v2,v5,v4,v3,v7,v6
C、v1,v2,v3,v4,v7,v5,v6
D、v1,v2,v5,v6,v7,v3,v4
38.下面几个符号串编码集合中,不是前缀编码的是()
A、{0,10,110,1111}B、{0,1,00,11}
C、{00,010,0110,1000}D、{b,c,aa,ac,aba,abb,abc}
39.希尔排序的增量序列必须是()。
A、递增的B、递减的C、随机的D、非递减的
40.采用起泡排序法对n个关键字进行升序排序,若要使排序过程中比较关键字的次数最多,则初始时的序列应满足条件()
A、关键字完全无序B、关键字基本有序
C、关键字从小到大排列D、关键字从大到小排列
41.在下列内部排序中()是不稳定的。
A、希尔排序B、起泡排序C、直接插入排序D、归并排序
42.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是()。
A、(100,80,90,60,120,110,130)B、(100,120,110,130,80,60,90)
C、(100,60,80,90,120,110,130)D、(100,80,60,90,120,130,110)
43.在查找过程中,冲突指的是()。
A、两个元素具有相同序号B、两个元素的键值不同
C、不同键值对应相同的存储地址D、两个元素的键值相同
44.对有14个元素的有序表A[1..14]作二分查找,查找元素A[4]时的被比较元素依次为()。
A、A[1],A[2],A[3],A[4]B、A[1],A[14],A[7],A[4]
C、A[7],A[5],A[3],A[4]D、A[7],A[3],A[5],A[4]
45.
以v1为起始结点对下图进行广度度优先遍历,正确的遍历序列是()
A、v1,v2,v3,v4,v5,v6,v7
B、v1,v2,v5,v6,v7,v3,v4
C、v1,v2,v5,v6,v7,v3,v4
D、v1,v4,v5,v7,v6,v2,v3
二、填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分)
1.数据的物理结构包括的存储和的存储。
2.若一个算法中的语句频度之和为T(n)=1921n+4nlogn,则算法的时间复杂度为。
3.下面程序段的时间复杂度是。
i=1;
while(i<=n)i=i*3;
4.循环队列用数组A[0..m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列的元素个数是。
5.在单链表中设置头结点的作用是____。
6.线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是_。
7.已知一无向图G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图,得到的序列为abecd,则采用的是遍历方法。
8.如果排序过程不改变之间的相对次序,则称该排序方法是稳定的。
9.从顺序表中删除一个元素时,表中所有在被删元素之后的元素均需一个位置。
10.当问题的规模n趋向无穷大时,算法执行时间T(n)的数量级被称为算法的。
11.若以邻接矩阵表示有向图,则邻接矩阵上第i行中非零元素的个数即为顶点vi的。
12.一棵含999个结点的完全二叉树的深度为。
13.假设S和X分别表示进栈和出栈操作,由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX,则由“a*b+c/d”得到“ab*cd/+”的操作序列为。
14..如图所示的有向无环图可以排出种不同的拓扑序列。
15.
从空树起,依次插入关键字1l,27,35,48,52,66和73构造所得的二叉排序树,在等概率查找的假设下,查找成功时的平均查找长度为。
16.带头结点的双循环链表L中只有一个元素结点的条件是。
17.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中的数目正相关。
18.已知一棵完全二叉树中共有768结点,则该树中共有个叶子结点。
19.实现图的广度优先搜索,除了一个标志数组标志已访问的图的结点外,还需要存放被访问的结点以实现遍历。
20.Prim(普里姆)算法适用于求的网的最小生成树;kruskal(克鲁斯卡尔)算法适用于求的网的最小生成树。
21.对长度为20的有序表进行二分查找的判定树的高度为。
22.设一棵完全二叉树有128个结点,则该完全二叉树的深度为,有_个叶子结点。
23.高度为h的完全二叉树中最少有个结点,最多有个结点。
24.设连通图G中有n个顶点e条边,则对应的最小生成树上有条边。
25.构造n个结点的强连通图,至少有条弧。
26.表达式求值是应用的一个典型例子。
27.设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈的容量至少应该是。
28.快速排序算法在最差的情况下其时间复杂度是。
29.对序列{55,46,13,05,94,17,42}进行基数排序,第一趟排序后的结果是。
三、应用题(本大题共5小题,每小题6分,共30分)
1.已知二叉树的先序遍历序列ABCDEFGH,中序遍历序列为CBEDFAGH,画出二叉树。
2.如图请给出邻接表、邻接矩阵及逆邻接表。
3.由字符集{s,t,a,e,I}及其在电文中出现的频度构建的哈夫曼树如图所示。
已知某段电文的哈夫曼编码为111000010100,请根据该哈夫曼树进行译码,写出原来的电文。
4.请画出下图所示的树所对应的二叉树,并写出对应二叉树的先序遍历和中序遍历。
5.设散列表为HT[13],散列函数为H(key)=key%13。
用闭散列法解决冲突,对下列关键码序列12,23,45,57,20,03,78,31,15,36造表。
采用线性探查法寻找下一个空位,画出相应的散列表,并计算等概率下搜索成功的平均搜索长度。
6.已知带权图G如图所示,画出图G的一棵最小生成树。
7.假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成,这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10},请为这8个字母设计哈夫曼编码。
8.试用权集合{12,4,5,6,1,2}构造哈夫曼树,并计算哈夫曼树的带权路径长度。
9.画出与如图所示森林对应的二叉树。
10.已知一个散列表如下图所示:
35
20
33
48
59
0123456789101112
其散列函数为h(key)=key%13,处理冲突的方法为双重散列法,探查序列为:
hi=(h(key)+
*h1(key))%m
=0,1,…,m-1
其中:
h1(key)=key%11+1
回答下列问题:
(1)对表中关键字35,20,33和48进行查找时,所需进行的比较次数各为多少?
(2)该散列表在等概率查找时查找成功的平均查找长度为多少?
11.请画出与下列二叉树对应的森林。
12.对于给定结点的关键字集合K={5,7,3,1,9,6,4,8,2,10},
(1)试构造一棵二叉排序树;
(2)求等概率情况下的平均查找长度ASL。
13.给出下图对应的邻接矩阵,并给出A,B,C三个顶点的出度与入度
14.已知图5.32如下所示,求从顶点a到其余各顶点的最短路径。
(给出求解过程)
15.阅读下列算法,并回答问题:
(1)假设串由合法的英文字母和空格组成,并以’\0’作结束符。
设串s=”⊔⊔I⊔am⊔a⊔⊔⊔student”(⊔表示空格符),写出f30(s)的返回值;
(2)简述算法f30的功能。
intf30(char*s)
{
inti,n,inword;
n=inword=0;
for(i=0;s[i]!
=’\0’;i++)
if(s[i]!
=’⊔’&&inword==0)
{
inword=1;
n++;
}
elseif(s[i]==’⊔’&&inword==1)
inword=0;
returnn;
}
16.阅读下列函数,并回答问题:
(1)假设队列q中的元素为(a,b,c,d,e),其中“a”为队头元素。
写出执行函数调用Conv(&q)后的队列q;
(2)简述算法Conv的功能。
voidConv(Queue*Q)
{
StackS;
InitStack(&S);
while(!
QueueEmpty(Q))
Push(&S,DeQueue(Q));
while(!
StackEmpty(&S))
EnQueue(Q,Pop(&S));
}
17.阅读下列函数,并回答问题:
已知整形数组L[1..8]中的元素依次为(19,18,15,17,16,13,12,10),阅读下列函数,并写出执行函数调用sort(L,8)时,对L进行的头两趟(pass分别为0和1)处理结果。
voidsort(intR[],intn)
{
intpass=0,k,exchange,x;
do{
k=pass%2+1;
exchange=0;
while(k{
if(R[k]>R[k+1])
{
x=R[k];R[k]=R[k+1];R[k+1]=x;
exchange=1;
}
K+=2;
}
pass++;
}while(exchange==1||pass<=1);
}
18.
key
next
已知带头结点的单链表中的关键字为整数,为提高查找效率,需将它改建为采用拉链法处理冲突的散列表。
设散列表的长度为m,散列函数为Hash(key)=key%m。
链表的结点结构为:
。
请在空缺处填入适当内容,使其成为一个完整算法。
voidf33(LinkListL,LinkListH[],intm)
{//由带头结点的单链表L生成散列表H,散列表生成之后原链表不再存在
inti,j;
LinkListp,q;
for(i=0;iH[i]=
(1);
p=L->next;
while(p)
{
q=p->next;
j=p->key%m;
(2);
H[j]=p;
(3);
}
free(L);
}
19.下列函数的功能是,对以带头结点的单链表作为存储结构的两个递增有序表(表中不存在值相同的数据元素)进行如下操作:
将所有在Lb表中存在而La表中不存在的结点插入到La中,其中La和Lb分别为两个链表的头指针。
请在空缺处填入合适内容,使其成为一个完整的算法。
voidunion(LinkListLa,LinkListLb)
{
//本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中
LinkListpre=La,q;
LinkListpa=La->next;
LinkListpb=Lb->next;
free(Lb);
while(pa&&pb)
{
if(pa->datadata)
{pre=pa;pa=pa->next;}
elseif(pa->data>pb->data)
{
(1);
pre=pb;
pb=pb->next;
(2);
}
else
{
q=pb;pb=pb->next;free(q);
}
}
if(pb)
(3);
}
20.阅读算法f30,并回答问题:
下列算法为有向图拓扑排序,请在空缺处填入合适的内容,使其成为一个完整的算法。
voidf30(hdnodesgraph[],intn)
{
inti,j,k,top;node_pointerptr;
top=-1;
for(i=0;iif(!
graph[i].count){graph[i].count=top;top=i;}
for(i=0;iif_
(1)___
{fprintf(stderr,"\ngraphhasacycle\n");exit
(1);}
else
{j=top;_
(2)__;
printf("v%d,",j);
for(ptr=graph[j].link;ptr;ptr=ptr->link)
{
k=ptr->vertex;graph[k].count--;
if((3)){graph[k].count=top;top=k;}
}
}
}
21.阅读算法f31,并回答问题:
下列算法功能为在数组a的前n(n>=1)个元素中找出第k(1<=k<=n)小的值。
这里假设数组a中各元素的值都不相同。
请在空缺处填入合适的内容,使其成为一个完整的算法。
#defineMAXN100
inta[MAXN],n,k;
intf31(