《数据结构》期末复习题-答案

1.以下与数据的存储结构无关的术语是（C）

C、哈希表

2.一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是（B）

B、108

3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（C）

C、head-）next==head

4.若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（D）

D、2,3,5,1,6,4

5.下列关键字序列中，构成小根堆的是（A）

A、｛12,21,49,33,81,56,69,41）

6.下列数据结构中，不属于二叉树的是（A）

A、B树

7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中,若结点A[i]有右孩子，则其右孩子是（C）。

C、A[2i+l]

8.设树T的高度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1,则T中叶子数为（D）

D、8

9.有数据｛53,30,37,12,45,24,96）,从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下

面哪个序列输入（B）

B、37,24,12,30,53,45,96

10.对下面有向图给出了四种可能的拓扑序列，其中错误的是（C）

C、5,1,6,3,4,2

11.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于（B）

B、Lm/2]—1

12.散列文件也称为（C）

B、索引文件

13.数据结构是（D）

D、相互之间存在一种或多种特定关系的数据元素的集合

14.从逻辑关系来看,数据元素的直接前驱为0个或1个的数据结构只能是（C）

C、线性结构和树型结构

15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p-llink和p-rlink表示，则同样表示

P指针所指向结点的表达式是（D）

D、pfllinkfrlink

16.若栈采用顺序存储方式存储，现两栈共享空间top[i]代表第i个栈（i=1,2）栈顶，栈1的底在v[l],栈2

的底在V[m],则栈满的条件是（B）

B、top[l]+l=top[2]

17.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（A）

A、10

18.树的先根序列等同于与该树对应的二叉树的（A）

A、先序序列

19.下面关于哈希（Hash,杂凑）查找的说法正确的是（C）

C、不存在特别好与坏的哈希函数,要视情况而定

20.下列序列中，（D）是执行第一趟快速排序后所得的序列。

D、[68,11,69,23,18][93,73]

21.下列关键字序列中，构成小根堆的是（D）

D、（15,28,46,37,84,58,62,41）

22.ISAM文件和VASM文件属于（C）

C、索引顺序文件

23.下面程序段的时间复杂度为（C）

for（i=0；i<m；i++）

for（j=0；j<n；j++）

A[i][j]=i*j;

C、O（m*n）

24.已知指针p和q分别指向某单链表中第一个结点和最后一个结点.假设指针s指向另一个单链表中某个结点,则在s所指结

点之后插入上述链表应执行的语句为（A）

A、q->next=s->next；s->next=p；

25.为便于判别有向图中是否存在回路，可借助于（D）

D、拓扑排序算法

26.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（D）

D、SSSXXSXX

27.设有一顺序栈S,元素si,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,sl,则栈的容量

至少应该是（B）

B、3

28.假设以数组A[m]存放循环队列的元素.已知队列的长度为length,指针rear指向队尾元素的下一个存储位置,则队头元素

所在的存储位置为（B）。

B、（rear-length+m）%m

29.在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（D）。

D、rear->next=s;rear=s;

30.对于哈希函数H（key）=key%13,被称为同义词的关键字是（D）

D、25和51

31.采用二叉链表存储的n个结点的二叉树，共有空指针（A）个.

A、n+1

32.连通网的最小生成树是其所有生成树中（D）

D、边的权值之和最小的生成树

33.对记录序列（314,298,508,123,486,145）依次按个位和十位进行两趟基数排序之后所得结果为（B）

B、508,314,123,145,486,298

34.任何一个无向连通图的最小生成树（C）。

C、一棵或多棵

35.无向图的邻接矩阵是一个（C）

C、对称矩阵

36.设无向图G—=（V,E）和G，二（『，E，），如G'为G的生成树，则下列说法中不正确的是（B）.B、G'为G连通分量

37.以vl为起始结点对下图进行深度优先遍历，正确的遍历序列是（D）

D、vl,v2,v5,v6,v7,v3,v4

38.下面几个符号串编码集合中，不是前缀编码的是（B）

B、{0,1,00,11}

39.希尔排序的增量序列必须是（B）。

B、递减的

40.采用起泡排序法对n个关键字进行升序排序，若要使排序过程中比较关键字的次数最多，则初始时的序列应满足条件

（D）

D、关键字从大到小排列

41.在下列内部排序中（A）是不稳定的。

A、希尔排序

42.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(C)。

A、(100,80,90,60,120,110,130)

43.在查找过程中，冲突指的是(C)。

C、不同键值对应相同的存储地址

44.对有14个元素的有序表A[l。。14]作二分查找，查找元素A[4]时的被比较元素依次为(D)。

D、A[7],A[3],A[5],A[4]

45.以vl为起始结点对下图进行广度度优先遍历，正确的遍历序列是(A)

A、vl,v2,v3,v4,v5,v6,v7

二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)

1.数据的物理结构包括数据元素的存储和数据之间关系的存储。

2.若一个算法中的语句频度之和为T(n)=1921n+4nlogn,则算法的时间复杂度为皿n.

3.下面程序段的时间复杂度是_log3n_。

i=l;

while(i〈=n)i=i*3；

4.循环队列用数组A[0oom-11存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是

(rear-front+m)%m

5.主要是使插入和删除等操作统一

6.(n-1)12。

7.在单链表中设置头结点的作用是深度优先.

8.线性表L=(al,a2,…，an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是

相同值关键字.

9.已知一无向图G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法

从顶点a开始遍历图，得到的序列为abecd,则采用的是前移遍历方法。

10.如果排序过程不改变时间复杂度之间的相对次序,则称该排序方法是稳定的。

11.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需一个位置。

12.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的100

13.若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的sxssxxssxssxxx.

14.一棵含999个结点的完全二叉树的深度为120

15.假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX,贝岫“a*b+c/d”

得到“ab*cd/+”的操作序列为。

16.o如图所示的有向无环图可以排出L—〉next・>next==L

17.边种不同的拓扑序列。

18.从空树起，依次插入关键字11,27,35,48,52,66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时

的平均查找长度为384.

19.带头结点的双循环链表L中只有一个元素结点的条件是队列。

20.求最小生成树的克鲁斯卡尔（Kruskal）算法耗用的时间与图中边稠密、边稀疏的数目正相关。

21.已知一棵完全二叉树中共有768结点，则该树中共有5个叶子结点。

22.实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需要8、64存放被访问的结点以实现遍历.

23.Prim（普里姆）算法适用于求上匚_的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求上L的网的最小生成树。

24.对长度为20的有序表进行二分查找的判定树的高度为n—1。

25.设一棵完全二叉树有128个结点，则该完全二叉树的深度为n,有个叶子结点.

26.高度为h的完全二叉树中最少有栈个结点,最多有个结点。

27.设连通图G中有n个顶点e条边.则对应的最小生成树上有3条边.

28.构造n个结点的强连通图，至少有0（I?）条弧。

29.表达式求值是（42,13,94,55,05,46,17）应用的一个典型例子。

30.设栈S和队列Q的初始状态为空，元素eLe2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出

队的序列是e2,e4,e3,e6,e5,el,则栈的容量至少应该是。

31.快速排序算法在最差的情况下其时间复杂度是o

32.对序列｛55,46,13,05,94,17,42）进行基数排序，第一趟排序后的结果是。

三、应用题（本大题共5小题，每小题6分，共30分）

1.已知二叉树的先序遍历序列ABCDEFGH,中序遍历序列为CBEDFAGH,画出二叉树。

答案：二叉树形态

2.如图请给出邻接表、邻接矩阵及逆邻接表。

（1）邻接表：（注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值一1）

vertexfirstedgenext

（2）逆邻接表:

(3)

0101

0010

1000

0010

3.由字符集｛s,t,a,e,1｝及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100,

请根据该哈夫曼树进行译码，写出原来的电文。

答案:原来的电文为：eatst

4.请画出下图所示的树所对应的二叉树，并写出对应二叉树的先序遍历和中序遍历。

答案:

先序遍历为：12345687中序遍历为：34867521

5.设散列表为HT[13],散列函数为H(key)=key%13。用闭散列法解决冲突，对下列关键码序列12,23,45,57,

20,03,78,31,15,36造表。采用线性探查法寻找下一个空位，画出相应的散列表，并计算等概率下搜索成功的平均搜

索长度。

答案：

使用散列函数H(key)=keymod13,有

H(12)=12,H(23)=10,H(45)=6,H(57)=5,

H(20)=7,H(03)=3,H(78)=0,H(31)=5,

H(15)=2,H(36)=10o

利用线性探查法造表：

0123456789101112

78150357452031233612

(1)(1)(1)(1)(1)(1)(4)(1)(2)(1)

搜索成功的平均搜索长度为

114

ASLsucc=----(1+1+1+1+1+1+4+1+2+1)=-----

1010

6.已知带权图G如图所示，画出图G的一棵最小生成树.

7.假设用于通信的电文由字符集｛a,b,c,d,e,f,g,h｝中的字母构成，这8个字母在电文中出现的概率分别为｛0。07,

0.19,0.02,0o06,0.32,0.03,0.21,0.10),请为这8个字母设计哈夫曼编码。

1.00

0

O-4X0.60

^0^28©0.32

0.210.19o

V17'X11

少@Qo.05

0.100.070.06（/Al

©©

哈夫曼编内树0.030.02

哈夫曼编码为：a：1001b：01c：10111d：1010e:llf：10110g:00h：1000

注意：答案不唯一

8.试用权集合｛12,4,5,6,1,2｝构造哈夫曼树，并计算哈夫曼树的带权路径长度。

h

300CD

WPL=12*1+(4+5+6)*3+(1+2)*4=12+，45+12=69

9.画出与如图所示森林对应的二叉树。

吟

））©©

答:

10.已知一个散列表如下图所示:

0123456789101112

其散列函数为h(key尸key%13,处理冲突的方法为双重散列法，探查序列为:

hi=(h(key)+1*hl(key))%m1=0,1,…，m-1

其中：hl(key)=key%ll+l

回答下列问题:

(1)对表中关键字35,20,33和48进行查找时，所需进行的比较次数各为多少？

(2)该散列表在等概率查找时查找成功的平均查找长度为多少？

答:

(1)对关键字35、20、33和48进行查找的比较次数为3、2、1、1；

…3+2+1+1+29

(2)平均查找长度ASL=--------------=-

55

11.请画出与下列二叉树对应的森林。

答:

12.对于给定结点的关键字集合K={5,7,3,1,9,6,4,8,2,10),

(1)试构造一棵二叉排序树;

(2)求等概率情况下的平均查找长度ASL.

答:

5

(2)ASL=(1*1+2*2+3*4+4*3)/10=2.9

13.给出下图对应的邻接矩阵,并给出A,B,C三个顶点的出度与入度

答案：邻接矩阵为：

ABCDEF

AFO00100

B101000

C000111

D000000

E110100

FLO10010

其中顶点A的入度为2,出度为1；

其中顶点B的入度为2,出度为2;

其中顶点C的入度为1,出度为3；

14.已知图5.32如下所示，求从顶点a到其余各顶点的最短路径。（给出求解过程）

5

答:

终点最短路径求解过程

b6(a,b)5(a,c,b)

C3(a,c)

doo6(a,c,d)6(a,c,d)

eoo7(a,c,e)7(a,c,e)7(a,c,e)

fooooco9(a,c,d,f)9(a,c,d,f)

vjcbdef

S{a,c}{a,c,b}{a,c,d}{a,c,e}{a,c,d,f)

15.阅读下列算法，并回答问题：

(1)假设串由合法的英文字母和空格组成，并以'\0作结束符。设串s="LJLIIIJamLJaLJLJLJstudent”(口表示空格符)，写出f30

(s)的返回值；

(2)简述算法f30的功能.

intf30(char*s)

答案：

(1)4

(2)算法功能：统计单词的个数。

16.阅读下列函数，并回答问题：

(1)假设队列q中的元素为(a,b,c,d,e),其中“a”为队头元素。写出执行函数调用Conv(&q)后的队列q；

(2)简述算法Conv的功能。

答案：

(1)e,d,c,b,a

(2)将队列里的值反转

17.阅读下列函数，并回答问题：

已知整形数组L[1。.8]中的元素依次为(19,18,15,17,16,13,12,10),阅读下列函数，并写出执行函数调用sort(L,

8)时，对L进行的头两趟(pass分别为0和1)处理结果。

答案:

(1)第一趟(pass=0)1915181617121310

(2)第二趟(pass=1)1915161812171013

18.已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的

长度为m,散列函数为Hash(key尸key%m。链表的结点结构为：.请在空缺处填入适当内容，使其成为一个完整算法。

keynext

答案：

(1)NULL(2)p—>next=H[j]p=q

19.下列函数的功能是,对以带头结点的单链表作为存储结构的两个递增有序表(表中不存在值相同的数据元素)进行如下操

作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填

入合适内容，使其成为一个完整的算法。

答案：

(1)pre-〉next=pb(2)pre->next=pa(3)pre-〉next=pb

20.阅读算法f30,并回答问题：下列算法为有向图拓扑排序，请在空缺处填入合适的内容，使其成为一个完整的算法。

答案：

(l)top=­1(2)top=graph[j].count(3)graph[k].count==0

21.阅读算法131,并回答问题：下列算法功能为在数组a的前n(n>=l)个元素中找出第k(l〈=k<=n)小的值.这里假设数组

a中各元素的值都不相同。请在空缺处填入合适的内容，使其成为一个完整的算法。

答案：

(1)(i==k)return;(2)i+l(3)i—1

22.阅读算法f33,并回答问题:下列算法功能为奇偶交换排序，思路如下：第一趟对所有奇数的i,将aLi]和a[i+l]进行

比较,第二趟对所有偶数的i,将a[i]和a[i+l]进行比较,每次比较时若a[i]〉a[i+1],将二者交换；以后重复上述二

趟过程，直至整个数组有序。请在空缺处填入合适的内容，使其成为一个完整的算法。

答案：

(l)a[i]=t(2)(i=2；i<=n;i+=2)(3)flag

四、算法设计题(本大题共2小题，每小题10分，共20分)

1.已知单链表的结点类型为Lnode,包含next和data成员。编写算法，实现带头结点单链表的逆置算法。

参考答案:

voidinvent(Lnode*head)

(

Lnode*p,*q；

if(!head—〉next)returnERROR；

p=head—〉next；q=p->next;p->next=NULL;

while(q)

{p=q;q=q-)next；p->next=head->next;head—>next=p;}

)

2.编写一个函数，要求借助一个栈把一个数组中的数据元素逆置。

其中，栈类型为SeqStack,可以直接使用InitStack(SeqStack**)、

Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函数。

参考答案：

voidInverse(ElemTypearr[],intn)

(

SeqStack*s；

inti;

InitStack(&s);

for(i=0；i〈n；i++)〃数组元素依次入栈

Push(s,arr[i])；

for(i=0;i<n;i++)〃栈中元素依次出栈，存入数组，是数组逆序

Pop(s,&arr[i])；

}

3.二叉树采用链接存储结构，结点类型为Btree,包括left、right和data三个成员，试设计一个算法计算一棵给定二叉树的度

为2的结点的个数。

参考答案：

inttwochild(Btree*b)

{intnuml,num2;

if(b==NULL)return0；

else

{numl=twochild1(b一〉left)；

num2=twochildl(b—>right)；

if(b—>left!=NULL&&b—〉right!=NULL)return(numl+num2+l)；

elsereturn(numl+num2);

}

4.假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示：

typedefcharDataType；

typedefstructnode{

DataTypedata;

structnode*lchild,^rchild；//左右孩子指针

structnode*parent；〃指向双亲的指针

}BinTNode;

typedefBinTNode*BinTree;

若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继.

(1)就后继的不同情况，简要叙述实现求后继操作的方法；

参考答案：

(1)分两种情况讨论

①当*px的右子树不为空时，则从*px的右孩子开始，沿其左孩子往下查找，直到找到一个没有左孩子的节点为止，则该

结点为*px在中序序列中的后继；

②当*px的右孩子为空时，则沿*px的双亲指针链向上查找，直至找到其左子树中包含*px的最年轻祖先，则该祖先结

点为*px在中序序列中的后继.

(2)编写算法求px所指结点的中序序列后继,并在算法语句中加注注释.

(2)BinTreef34(BinTreepx)

|

BinTreeq=px->rchild；

if(q!=NULL){〃沿左孩子往下查找

px=q；

while(px-)lchild!=NULL)

px=px->lchild；

}

else{〃沿双亲指针链向上查找

while(px!=NULL&&px—>rchild==q){

q=px；

px=px——>parent;

}

}

returnpx;〃返回所找到的中序序列后继结点的指针

〃或者无后继结点时返回空指针

5.已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。

参考答案：

voidAllSPdfs(AdjListg,vertypeu,vertypev)

{〃求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(