数据结构试题

一、单选题(每题2分，共30分)

1.算法分析的两个主要方面是—A_o

(A)空间复杂度和时间复杂度

(B)正确性和简单性

(C)可读性和可操作性

(D)程序复杂性和数据复杂性

2.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为:

C—

(A)存储结构

(B)逻辑结构

(C)顺序存储结构

(D)链式存储

3.某算法的语句执行频度为(3n+n21°g2n+n3+8),其时间复杂度表示C_。

(A)O(n)

(B)0(nlogzn)

(C)0(n3)

(D)0(log2n)

4.线性表L在一.A_情况下适用于使用顺序存储结构实现。

(A)需不断对L进行按序号查找的

(B)需不断对L进行删除插入

(C)L中含有大量的结点

(D)L中结点结构复杂

5.以下数据结构中哪一个是线性结构？—.A.

（A）栈

（B）树

（C）图

（D）二叉树

6.树最适合用来表示C—o

（A）有序数据元素

（B）无序数据元素

（C）元素之间具有分支层次关系的数据

（D）元素之间无联系的数据

7.栈中元素的进出原则是B_

（A）先进先出

（B）后进先出

（C）栈空则进

（D）栈满则出

8.线性表11=（al,a2,,an）,卜列说法正确的是D

（A）每个元素都有一个直接前驱和一个直接后继

（R）线性表中不可•以为空

（C）表中诸元素的排列顺序必须是由小到大或由大到小

(D)除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后

继

9.已知一个有序表为(L2,3,4,5,6,7,8,9),则折半查找4需要比较

-D次。

(A)1(B)2(C)3(D)4

10.一个栈的入栈序列是a,b,c,d,e,f则栈的不可能的输出序列是_C_

(A)fedcba(B)defcba(C)dcefab(D)abcdef

11.在等概率的条件下，采用顺序查找的方法查找长度为n的线性表时，查找成功的平均

查找长度为(C)。

(A)n(B)n+1(C)(n+1)/2(D)(n-1)/2

12.队列元素的进出原则是—A_

(A)先进先出

(B)后进先出

(C)队列空则进

(D)队列满则出

13.具有线性结构的数据结构是_D-。

(A)图(B)二叉树(C)树(D)队列

14.已知一个有序表为(1,2,3,4,5,6,7,8,9),则顺序查找5需要比较

A次。

5.任何一个无向连通图的最小生成树_B种。

(A).只有一棵(B).有一棵或多棵

(C).一定有多棵(D).可能不存在

6.二叉树是非线性数据结构，所以_Co

(A)它不能用顺序存储结肉存储

(B)它不能用链式存储结构存储；

(C)顺序存储结构和链式存储结构都能存储

(D)顺序存储结构和链式存储结构都不能使用

7.在尢向图中，一个顶点的度是指图中_Bo

(A).通过该顶点的简单路径数

(B).与该顶点相邻接的顶点数

(C).通过该顶点的回路数

8.程序段k=i=O；do{i=i+l;k=k+i：}while(i<=n)；的时间复杂度为_A

(A)O(n)

(B)O(nlog2n)

(C)O(n2)

(D)0(/)

9.两个字符串相等的充要条件是_Co

(A)两个字符串的长度相等

(B)两个字符串中对应位置卜.的字符相等

(C)同时具备(A)和(B)两个条件

(D)以上答案都不对

10.设指针p指向单链表中结点A,指针q指向单链表中结点A的后继结点B,指针s指向被

插入的结点X,则在结点A和结点B插入结点X的操作序列为B_o

(A)s->next=q->next；q->next="s

(B)p->next=s；s->next=q；

(C)q->next=s->next；s->next=q

(D)q->next=s；s->next=p；

11.正常情况下，添加一个顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是—C

(A)top不变

(B)top=0

(C)top=top+l

(D)top=top-l

12.队列的插入操作是在

(A)队尾

(B)队头

(C)队列任意位置

(D)队列指定位置

13.一组记录的的序列(46,79,56,38,40,84),则利用冒泡排序的方法，经过D

_轮排序，序列变为有序的。

(A)1

（B）2

(C)3

(D)4

14.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是

_A_o

(A)完全图(B)连通图

15.已知一个有序表为(1,2,3,4,5,6,7,8,9),则折半查找2需要比较B次。

(A)1

(B)2

(C)3

(D)4

1.下面程序段的时间复杂度是一C-O

for(j=0;j<m;j-F+)

for(k=0;k<n;k++)

a[j][k]=j*k;

A.0(m2)B.0(n2)C.O(m*n)D.O(m+n)

2.单链表不具有的特点是一A-o

(A)可随机访问任一元素

(B)插入不需要移动元素

(C)不必事先定义存储空间

(D)存储空间与线性表长度成正比

3.算法是一D。

A.计算机代码B.解决问题的计算方法

C.查找算法D.解决问题的有限运算序列

4.一个顺序表的第一个元素的存储地址是90,每个元素的长度为1,则第6个元素的存

储地址是A_o

A.95B.100C.96D.106

5.一组记录的的序列(46,79,56,38,40,84,90),则利用冒泡排序的方法，经

过一D一轮排序，序列变为有序的。

A.5

B.2

C.3

D.4

6插入和删除只能在表的一端进行的线性表，称为—C―。

(A)队列

(B)循环队列

(C)栈

(D)双枝

7.在树中，若结点A有7个兄弟，而且B是A的双亲，则B的度为—D。

(A)6

(B)7

(C)5

(D)8

8.在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是_B

A.p=p->next;B.p->next=p->next->next;

C.p->next=p;D.p->next->next=p;

9.设将整数123.4,5依次进栈，最后都出栈，出栈可以在任何时刻(只要栈不空)进行，

则出校序列不可能是_B

(A)23415

(B).54132

(C)23145

(D)15432

10.2.下面程序的时间复杂为—B—

for(i=l,s=0；i<=n；i++){t=l；for(j=l；j<=i；j++)t=t+j；s=s*t；}

(A)O(n)

(B)0(n2)

(C)O(n3)

(D)0(n4)

11.字符串的长度是指—C一0

(A)串中不同字符的个数

(B)串中不同字母的个装

(C)串中所含字符的个数

(D)串中不同数字的个数

12.判断一个循环队列Q(最多n个元素)为满的条件是—C—o

A.rear==frontB.rear==front+1

C.front==(rear+1)%nD.front==(rear-1)%n

13.在具有n个结点的顺序表上查找值为X的元素时，其时间复杂度为—A.

(A)0(n)

(B)0(1)

(C)0(n2)

(D)0(log2n)

14.在线性表的下列存储结构中，读取元素花费的时间较多的是A_

(A)单链表

(B)顺序表

15.在一个单链表中，已知q结点，若在q后插入一个结点S,则执行一C_So

(A)q=s；

(B)q=s->next;

(C)q->ncxt=o;

(D)q->next=s->next;

1.算法是D-。

A.计算机代码B.解决问题的计算方法

C.查找算法D.解决问题的有限运算序列

2.采用顺序存储结构，长度为n的线性表，在其第j个位置插入一个新元素算法的时间复

杂度C.。

A.O(nlog2n)B.0(1)

C.0(n)D.O(n2)

3.某算法的语句执行频度为(3n+n210g20+)+8),其时间复杂度表示—C—。

A.0(n)B.0(nlog2n)C.0(n3)D.O(log2n)

4.线性表L在_A情况卜.适用于使用顺序存储结构实现。

(A)需不断对L进行按序号查找的

(B)需不断对L进行删除插入

(C)L中含有大量的结点

(D)L中结点结构复杂

5.以下数据结构中哪一个是线性结构？_A

(A)队列

(B)满二叉树

(C)图

（D）二叉树

6.二叉树的深度为k,则二叉树最多有一C个结点。

A.2k+lB.2卜1C.2k-lD.2k-l

7.栈中元素的进出原则是_B

（A）先进先出

（B）后进先出

（C）栈空则进

（D）栈满则出

8.顺序表具有的特点是_人。

A.可随机访问任一元素B.插入删除不需要移动元素

C.不必事先估计存储空间D.所需空间与线性表长度成正比

D.除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继

9.已知一个有序表为（L2,3,4,5,6,7,8,9）,则折半杳找4需要比较

D一次。

A.1B.2C.3D.4

10.已知串S=，aaa",则串长为—A。

A.4B.3C.5

11.在等概率的条件下，采用顺序查找的方法查找长度为n的线性表时，查找成功的平均

查找长度为_C—。

A.nB.n+1C.（n+1）/2D.（n-1）/2

12.队列元素的进出原则是_A—

（A）先进先出

（B）后进先出

（C）队列空则进

（D）队列满则出

13.一个顺序表的第一个元素的存储地址是90,每个元素的长度为2,则第6个元素的存

储地址是_Bo

A.102B.100C.106D.

108

14.已知一个有序表为（1,2,3,4,5,6,7,8,9）,则顺序查找4需要比较

D一次。

A.5B.6C.3D.4

15.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针x指向另一

个单链表中某个结点，则在x所指结点之后插入上述链表应执行的语句为_A—。

A.q->next=x->next；x->next=p；

B.s->next=p：q->next=x->next；

C.p->next=x->next；x->next=p；

D.x->next=q：p->next=x->next：

1.抽象数据类型的三个组成部分分别为—B_o

A.数据对象、数据关系和数据操作

B.数据元素、逻辑结构和存储结构

C.数据项、数据元素和数据类型

D.数据元素、逻辑结构和数据类型

2.通过构建有序序列，招待排序的数据，在已排好序的序列中从后向前扫描，找到其相

应位置并进行插入操作，这是—A一排序的基本思想。

A.直接插入排序B.冒泡排序

3.在n个结点的顺序表中，算法的时间复杂度是。（1）的操作是_A：

（A）访问第i个结点（lWiWn）和求第i个结点的直接前驱（2<iWn）

（B）在第i个结点后插入一个新结点（iWiWn）

（C）删除第i个结点（lWiWn）

（D）将n个结点从小到大排序

4.线性表若采用顺序存储结构时，要求内存中可用存储单元的地址—A:

(A)必须是连续的

(B)部分地址必须是连续的

(C)一定是不连续的

(D)连续或不连续都可以

5.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序A_“

A.不发生改变B.发生改变

C.不能确定

6.二叉树是非线性数据结构，所以_Co

(A)它不能用顺序存储结构存储

(B)它不能用链式存储结构存储；

(C)顺序存储结构和链式存储结构都能存储

(D)顺序存储结构和链式存储结构都不能使用

7.在无向图中，一个顶点的度是指图中_B。

A.通过该顶点的简直■路径数

B.与该顶点相邻接的顶点数

C.通过该顶点的Ia路数

8.采用顺序存储结构，长度为n的线性表，在其第i个位置插入一个新元素算法的时间复

杂度C。

A.O(nlogan)B.0(1)

C.0(n)D,O(n2)

9.两个字符串相等的充要条件是_C。

(A)两个字符串的长度相等

(B)两个字符串中对应位置上的字符相等

(C)同时具备(A)和(B)两个条件

(D)以上答案都不对

10.设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对

于S='Beijing&Tianjin',SUBSTR(Sz4,5)=B。

A.Ijing'

B.'jing&'

C.IngTi'

D.Ing&T'

11.正常情况3添加一个顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是

_____C_o

(A)top不变

(B)top=0

(C)top=top+l

(D)top=top-l

12.队列的插入操作是在—Ao

(A)队尾

(B)队头

(C)队列任意位置

(D)队列指定位置

13.一组记录的的序列(46,79,56,38,40,84),则利用冒泡排序的方法，经过

—.D—轮排序，序列变为有序的。

A.1

B.2

C.3

D.4

14.无向图的邻接矩阵是一个—A_<,

A.对称矩阵B.下三角矩阵

C.上三角矩阵D.对角矩阵

15.已知一个有序表为(1,2,3,4,5,6,7,8,9),则折半查找7需要比较.

B次。

A.1B.2C.3D.4

二、填空题(每空2分，共20分)

1.设栈s和队列q均为空，先将a,b,c,d,e依次进队列q,再将队列q中的前3个元素

顺次出队的元素进栈s。再将栈s中的元素逐个出栈，并将出栈元素顺次进队列q,则队列

q的状态是decba。

2.在无向图G的邻接矩阵A中，若［j］等于1,则［i］等于

1O

3.查找的方法可以分别静态查找和动态查找<,

4.在具有n个元素的循环队列中，队满时具有n-1个元素.

5.n个顶点的连通图至少有n-1边。

6.两个串相等的充分必要条件是两个串的长度相等且对应位置字符相同。

7.树内各结点度的两个串的长度相等称为树的度。

8.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行

删除运算的线性表。

I.队列元素的进出原则是先进先出栈元素RJ进出原则是先进后出—，队

列和栈都是线性—结构。

2.设栈s和队列q均为空，先将a,b,c,d,c依次进队歹Jq,再将队列q中的前4个元素顺

次出队的元素进枝s。再将栈s中的元素逐个出栈，并将出栈元素顺次进队列q,则队列q的

状态是edcba.

3.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：

q=p->next;

p->next=q->next;

4.设循环队列的容量为70,现经过一系列的入队和出队操作后，front为30,rear■为U,

则队列中元素的个数为51。

5.规模为n的序列，使用直接插入排序，则最好情况下的时间更杂度是

O(n),nl,O(n2),最好情况下比较的次数是16_,最坏情况下的时间复杂度是

，最坏情况下比较的次数是(n-l)(n+2)/2,

1.设栈s和队列q均为空，先将a,b,c,d,e依次正栈s,再将栈s中的前2个元素顺

次出栈的元素进队列q。再将队列q中的元素逐个出队，并将出队元素顺次进栈s,则栈s

从栈底到栈顶的元素依次是—abcedo

2.线性结构中元素之间存在——对一关系，树形结构中元素之间存在多对多

关系，图形结构中元素之间存在一对多关系。

3.二叉树的前序和中序遍,万序列能惟一确定这棵二叉树(填写能或者不能)。

4.两个串相等的充分必要条件是两个串的长度相等且对应位置字符相同。

5.栈和队列都是特殊的线性表，栈的元素进出规则是—先进后出,队列的元素

进出规则是—先进先出.

6.由3个结点所构成的二叉树有5种形态。

7.遍历图有深度优先遍历、广度优先遍历等方法。

I.设栈s和队列q均为空，先将a,b,c,d,e依次进栈$,再将栈s中的前3个元素顺次出栈

的元素进队列q。再将队列q中的元素逐个出队，并将出队元素顺次进栈s,则枝s从栈底到

栈顶的元素依次是abedc。

2.在有向图G的邻接矩阵A中，不存在回路，若等于1,则等于

0O

3.查找的方法可以分别静态查找和动态查找。

4.循环队歹U的队头和队尾指针分别为front和rear,则判断循环队列为空的条件是

front==(rear+1)%n。

5.n个顶点的连通图至少有n-1边。

(011、

6.设图的邻接矩阵为001,则该图为无向“(填写有向或者无向)

7.树内各结点度的最大值称为树的度。

8.依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了1次删除操作，此时的

队头元素是b0

9.依次在初始为空的栈中插入元素a,b,c,d以后，紧接着做了1次删除操作，此时的栈顶

兀素是c0

1.一个顺序表的第一个元素的存储地址是80,每个元素的长度为1,则第6个元素的存储

地址是85，如果每个元素的长度为2,则第6个元素的存储地址是

90o在具有n个结点的单链表上查找第i个的元素时，其时间复杂度为

O（n）o

2.设栈s和队列q均为空，先将a,b,c,d,e,f,g依次进队列q,再将队列q中的前4

个元素顺次出队的元素进校s。再将栈s中的元素逐个出栈，并将出栈元素顺次进队列q,

则队列q的状态是—efgdcba。

3.带头结点的单链表head为空的条件是q->next。

4.设循环队列的容量为70,现经过一系列的入队和出队操作后，front为30,rear为

11,则队列中元素的个数为head->next==NULL。

5.在一棵具有5层的满二叉树中结点总数为32。

6.在二叉树的第i层上最多有2*'1个节点。

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

出度邻接矩阵上第j列中非零元素的个数即为顶点vj的—入度O

三、计算题（每题10分，共40分）

1、某不带权有向图如下所示。

1）给出其邻接矩阵;

2）画出该图的无向图？

3）求该图的无向图的广度优先遍历序列，以结点A开始?

答：1）该图的邻接矩阵是:

0100011

0000001

0100000

0010000

0001000

1000100

0011010

2）该图的无向图是:

3）以结点A开始，该图的无向图的广度优先遍历序列是：ABGFCDEo

2、请问直接插入排序的思想是什么？写出用直接插入排序将关键字序列

{54,23,89,48,64,50,25,90,88}排序过程的每一•趟结果。

答：初始：54,23,89,48,64,50,25,90,88

1：(23,54)89,48,64,50,25,90,88

2：(23,54,89),48,64,50,25,90,88

3：(23,48,54,89)64,50,25,90,88

4：(23,48,54,64,89)50,25,90,88

5：(23,48,50,54,64,89)25,90,88

6：(23,25,48,50,54,64,89),90,88

7：(23,25,48,50,54,64,89,90),88

8:(23,25,48,50,54,64,88,89,90)

一共8个轮次，，每个轮次1分。

3、

1)请问空格串和空串相同吗？为什么。

u

2)sl=abc",s2=''344"StrConcat(slzs2,s)^flStrConcat(sl,s2)的

操作结果分别是多少？

3)请分析下面代码的功能。

4)str的长度是多少？

String::String()

(

size=l;

str=newchar[size];//(1)

if(str==NULL){

cout<<"甲i青空间失败"vvendl;

exit(1);

)

str[0]=,\0/;//(2)

)

答：1)空串和空格串不相同。串中的字符全是空格的串叫空格串，而长度为0的串叫空串。

2)前者操作结果是s="abc344"；后者操作结果是sl="abc344"

3)代码的功能是构造一个空串；

4)str的长度是1.

4、己知一棵二叉树的先序序列：ABDGJEHCFIKL;中序序列：DJGBEHACK1LF。请回答:

1)请写出二叉树先序遍历的定义。(简答)

2)请写出二叉树中序遍历的定义。(简答)

3)请问这颗二叉树的根节点是哪个节点？

4)请具体画出二叉树的形态。

答：1）先序遍历的定义是：若二又树为空，则结束遍历操作；否则访问根结点；然后先

序遍历根的左子树；最后先序遍历根的右子树。

2）中序遍历的定义是：若二又树为空，则结束遍历操作；否则中序遍历根的左子树；然

后访问根结点；最后中序遍历根的右子树。

3）根节点是A。

4）二叉树的形态如下：

1、设某棵二叉树的中序遍历序列为DBEACGF,前序遍历序列为ABDECFG：

1）要求给出该二叉树的的后序遍历序列。

2）请画出这棵树；

3）请问树的深度的定义是什么，并且这棵树的深度多少？

答：1）该二叉树的的后序遍历序列是：DEBGFCA

2）这颗二叉树是：

3）树的深度是该树中结点最大层次值，这棵树的深度是4.

2、1）写出用直接插入排序将关键字序列｛54,23,89,48,64,50,25｝排序过程的每一趟结

果。

2）n规模的数据元素进行递增排序，请分析插入排序在最好情况卜.的时间效率是多少？为什么？

最坏情况下时间效率是多少？为什么？

答：1）关键字序列｛54,23,89,48,64,50,25｝的直接插入排序过程如下:

第一趟：[54],23,89,48,64,50,25

第二趟：［23,54],89,48,64,50,25

第三趟：［23,54,89],48,64,50,25

第四趟：［23,48,54,89],64,50,25

笫五趟：［23,48,54,64,89],50,25

第六趟：［23,48,50,54,64,89],25

第七趟：［23,25,48,50,54,64,89]

2）答：最好情况下，原始数据已经按照关键字递增排序，此时时间复杂度是T（n）；最坏

情况下，原始数据是按照关键字递减排序，此时时间复杂度是T（n，2）

（1）画出该图的邻接矩阵；

（2）根据邻接表分别画出从顶点G出发进行深度优先遍历的顺序。

（3）根据邻接表分别画出从顶点G出发进行广度优先遍历的顺序。

答:⑴图邻接矩阵结构如下。

⑵从顶点G出发进行深度优先遍历的顺序:GABCDEF;

⑶从顶点G出发进行广度优先遍历的顺序:GACFDBE。

1、设有一棵二叉树，它的中序和后序遍历结果如下，。

中序：143562

后序：465321

1）请画出该二叉树

2）该树的深度是多少?

3）下面的结构从左到右依次用标号a,b,c,d表示，请问哪个是树结构，哪个不是？

答：1）该二叉树是:

2）该树的深度是5

3）只有第一个，即标号为a的结构是树。其他都不是

2、如图所示，解答如F问题:

(1)写出从定点A出发，深度和广度优先遍历

方法遍历该图的顶点序列，

(2)写出该树的邻接矩芳

答:

(1)从定点A出发，深度优先遍历的顶点序列是：ABGFDEC,广度优先遍历的序列是:

ABECDGF

(2)该树的邻接矩阵是：

0111100

1000001

1000100

1000010

1010010

0001101

0100010

3、

1)写出用冒泡排序将关键字序列｛54,23,89,48,64,50,25｝排序过程的第一趟结果。

2)写出用直接插入排序将关键字序列｛54,23,89,48,64,50,25｝排序过程的每一趟结果。

答：1)冒泡排序的第一趟结果：

()(54,23,89,48,64,50,25)

()(54,23,89,48,64,25,50)

()(54,23,89,48,25,64,50)

()(54,23,89,25,48,64,50)

()(54,23,25,89,48,64,50)

()(54,23,25,89,48,64,50)

(23)(54,25,89,48,64,50)

2）直接插入排序:

第一趟:[54],23,89,48,64,50,25

第二趟：[23,54],89,48,64,50,25

第三趟：[23,54,89],48,64,50,25

第四趟；[23,48,54,89],64,50,25

第五趟：[23,48,54,64,89],50,25

第六趟：[23,48,50,54,64,89],25

第七趟：[23,25,48,53,54,64,89]

1、设某棵二叉树的中序遍历序列为HDBEACGF,前序遍历序列为ABDHECFG：

1）要求给出该二叉树的的后序遍历序列。

2）请画出这棵树；

3）请问树的深度的定义是什么，并且这棵树的深度多少？

答：］）该二叉树的的后序遍历序列是：HDEBGFCA

3）这颗二叉树是：

3）树的深度是该树中结点最大层次值，这棵树的深度是4.

2、1）写出用直接插入排序将关键字序列｛94,23,89,48,54,70,25,56｝排序过程的每一趟

结果。

2）n规模的数据元素进行递增排序，请分析插入排序在最好情况下的时间效率是多少？为什么？

最坏情况下时间效率是多少？为什么？

答1）关键字序列｛94,23,89,48,54,70,25,56｝的直接插入排序过程如下：（6分）

第一趟：［94］,23,89,48,54,70,25,56

第二趟：[23,94],89,48,54,70,25,56

第三趟：[23,89,94],48,54,70,25,56

第四趟:[23,48,89,94],54,70,25,56

第五趟:[23,48,54,89,94],70,25,56

第六趟：[23,48,54,70,89,94],25,56

第七趟：[23,25,48,54,70,89,94],56

第八趟：[23,25,48,54,56,70,89,94]

2）最好情况下，原始数据已经按照关键字递增排序（1分），此时时间发杂度是T（nj（1

分）；最坏情况下，原始数据是按照关键字递减排序（1分），此时时间复杂度是T（M2）

（1分）。

3、

）设有一表如下，一共有11个元素，已经按照从小到大的顺序排好序，方框里面为关键字，

方框上面对应的数值为该关键字的标号。请画出利用折半查找关键字19时，每一轮比较过程

中，left、mid和right指针指向的位置。为了清楚表达,建议标left、mid和right指针位

置的时候，每一轮画下表送行标识，则应有几轮比较画几个下表。

1234567891011

41319213r566465808490

.A

2）当需要在上表查找关键字80时，请画出每一轮比较过程中，left、mid和right指针指向

的位置。

答：1）查找关键字19时:

第一轮比较：

1234567891011

413192137566465808490

lowmdhigh

第二轮比较：

1234567891011

413192137566465808490

lowmidhigh

2）查找关键字67时:

第一轮比较：

1234567891011

413192137566465808490

lowmidhigh

第二轮比较：

1234567891011

413192137566465808490

lowmidhigh

1、某不带权有向图的邻接矩阵如下

-0100011

0000001

0100000

0010000

0001000

1000100

0011010

1）请画出该有向图；

2）该图的入度和出度分别是多少？

3）求该图的无向图的广度优先遍历序列，以结点A开始？

答：1）该图如下

2）该图的出度和入度相同，都等于12

3）以结点A开始，该图的无向图的广度优先遍历序

列是:ABGFCDEo

2、请问冒泡排序的步骤是什么？（请详细写出步骤）写出用冒泡排序将关键字序列

{54,23,89,48,64,50,25,90,88,75}排序过程的第一趟排序过程。

答：冒泡排序的步骤如下：

1：将整个排序表E划分为两个部分（己经按递增或递减排序的有序区）（无序区）。初

始时，所有数据元素都处在无序区。

2：从无序区右边开始，依次对相邻记录的关键码进行两两比较，如不满足排序要求则进

行交换。

3：将无序区的一个记录移至有序区的尾部。

4：重复上述两个步骤直到全部记录有序为止。

{54,23,89,48,64,50,25,90,88,75}的冒泡排序过程的第一趟排序过程如下:

1：()(54,23,89,48,64,50,25,90,88,75)

2：()(54,23,89,48,64,50,25,90,75,88)

3：()(54,23,89,48,64,50,25,75,90,88)

4：()(54,23,89,48,64,50,25,75,90,88)

5：()(54,23,89,48,64,25,50,75,90,88)

6：()(54,23,89,48,25,64,50,75,90,88)

7：()(54,23,89,25,48,64,50,75,90,88)

8：()(54,23,25,89,48,64,50,75,90,88)

9：()(54,23,25,89,48,64,50,75,90,88)

10：(23)(54,25,89,48,64,50,75,90,88)

3、设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用

二分查找，要求

1）计算出查找关键字62时的比较次数,left,mid,right指针在每次比较过程中分别指向

哪个关键字，为什么

2）ASL是衡量查找算法效率的重要指标，全称是什么？

答：1）比较次数是2。

Mid指针在第一次比较过程中指向47关键字,因为left指向第1个关键字13,right指向

第9个关键字90,mid指向的关键字下标等于（1+9）/2=5。

因为47比62小，因此在第二次比较过程中，令left指向的关键字下标6（关键字为50）,

right的指向不变（指向第9个关键字90）,因为（6+9）/2=7.5,向下取整为7,mid指向

的关键字下标等于7（指向关键字62）,于是找到了需要的关键字62。

2）ASL的全称是平均查找长度。

4、已知一棵二叉树的先序序列：ABDGJEHCFIKL;中序序列：DJGBEHACKILFo请回答:

1）请写出二叉树先序遍历的定义。（简答）

2）请写出二叉树中序遍历的定义。（简答）

3）请问这颗二叉树的根节点是哪个节点？

4）请具体画出二叉树的形态。

答：1）先序遍历的定义是：若二义树为空，则结束遍历操作；否则访问根结点；然后先

序遍历根的左子树；最后先序遍历根的右子树。

2）中序遍历的定义是：若二叉树为空，则结束遍历操作；否则中序遍历根的左子树；然

后访问根结点；最后中序遍历根的右子树。

3）根节点是A。

4）二叉树的形态如下：

四、阅读算法题（每题10分，共10分）

卜.面是实现：假设已经存在一个顺序表，将该顺序表逆转。其中已经存在的顺序表用数组

b来表示，顺序表的元素个数是n,最后将逆转的顺序表继续存在数据b里。

1）请问：数据b的第一个元素的存储地址是80,每个元素的长度为2,则第6个元素的

存储地址是多少？写出计算公式。

2）请问：在该顺序表中，查找第i个元素的时间复杂度是多少？

3)请将缺少的代码补充完整，并分析算法的时间复杂度。

voidsimsort(ElemTypeb[],intn)

(日emTypea[n];〃辅助存储空间n个

for(i=l;i<n;i++)a[i]=(1);

for(j=l;j<n;j++)(2);

)

4)上面算法需要辅助的存储空间n个，即数组a[n],请设计一种算法，实现与上面算法

相同的功能，但只用1个辅助存储空间，设为x,请写出该算法。如下给出了该算法的算

法名称。

算法2：

voidsimsort(ElemTypeb[]zintn)

(日emTypex;〃辅助存储空间1个

〃请在这里将算法补充完

)

答：1)第6个元素的存储地址是90,计算公式是：80+2*(6-1)=90。

2)在该顺序表中，查找第i个元素的时间复杂度是0(11。

3)第一个横线处:b[n-i+l]；

第二个横线处：b[j]=a[j]；

时间复杂度是0(M).

4)补充的算法代码部分是：

for(i=l;i<n/2;i++)

{x=b[i]

b[i]=b[n-i+l];

b[n-i+l]=x;

)

1、卜面算法的功能是统计出单链表HL中结点的值等于给定值X的结点个数，请补充空白处的

代码。

intCountX(LNode*HL,ElemTypex)

{inti=0;LNode*p=HL;//i为计数器

while(Q))

{if(⑵)i++;

(3);

}//while,出循环时i中的值即为x结点个数

(4);

}//CountX

答：1、第一个横线处：p!=NULL

第二个横线处：P->data==x

第三个横线处：p=p->next

第四个横线处：returni

2、下面是顺序查找的代码.请将缺少的代码补充完整。请问6个关键字为：61,31,104,43,

47,73,如果要查找关键字47要比较几次？要查找关键字100要比较几次？

voidSqtablc::sq_scarch(KcyTypcK)〃已知表r、关键数据K、表长n

((1)；〃设置监视哨

inti=0;

while((2)))i++;

if((3))

cout«"\n查找成功，记录下标为:"«i«endl;

elsecout«"\n查找失败!\n"«endl;

)

2、第一个横线处：rm】.key=K；

第二个横线处：巾］.key!=K

第三个横线处：i<n

要查找关键字47要比较5次2,要查找关键字100要比较6次，结果是查找不到关健字

100..

1、

补充横线处缺少的代码，己知MAXSIZE是线性表的最大长度值。

intSequenList::Insert(DataTypex,inti)

{//在线性表的第i个数据元素之前插入一个新的数据元素x

intj;

if(len>=(G))

{cout«"overflow!n«endl;〃数据溢出

retu