数据结构（本）期末综合练习

数据结构（本）期末综合练习

2010年12月

期末综合练习一

一、单项选择题

1.数据的物理结构（）。

A.与数据的逻辑结构无关B.仅仅包括数据元素的表示

C.只包括数据元素间关系的表示D.包括数据元素的表示和关系的表示

2.数据元素是数据的基本单位，它（）。

A.只能有一个数据项组成

B.至少有二个数据项组成

C.可以是•个数据项也可以由若干个数据项组成

D.至少有一个数据项为指针类型

3.从n个数中选取最大元素，（）o

A.基本操作是数据元素间的交换B.算法的时间复杂度是O（E）

C.算法的时间复杂度是O（n）D.需要进行（n+1）次数据元素间的比较

4.线性表的顺序结构中，（）。

A.逻辑上相邻的元素在物理位置上不一定相邻

B.数据元素是不能随机访问的

C.逻辑上相邻的元素在物理位置上也相邻

D.进行数据元素的插入、删除效率较高

5.以下表中可以随机访问的是（）。

A.单向链表B.双向链表

C.单向循环链表D.顺序表

6.带头结点的单向链表为空的判断条件是（）（设头指针为head）。

A.head==NULLB.head->next==NULL

C.head->next==headD.head!=NULL

7.设顺序存储的线性表长度为n,对于删除操作，设删除位置是等概率的，则删除一个

元素平均移动元素的次数为（）。

A.（n+1）/2B.nC.2nD.n-i

8.线性结构中数据元素的位置之间存在（）的关系。

A.一对一B.一对多

C.多对多D.每一个元素都有一个直接前驱和一个直接后继

9.设top是一个链栈的栈顶指针，栈中每个结点由个数据域data和指针域next组成，

设用x接收栈顶元素，则出栈操作为（）。

A.x=top->data;top=top->next;B.top=top->next;x=top->data;

C.x=top->next;top=top->data;D.top->next=top;x=top->data;

10.设顺序存储的线性表长度为n,要删除第i个元素，按课本的算法，当i=（）

时，移动元素的次数为3

A.3B.n/2C.n-3D.4

11.以下说法正确的是（）。

A.队列是后进先出

B.栈的特点是后进后出

C.栈的删除和插入操作都只能在栈顶进行

D.队列的删除和插入操作都只能在队头进行

12.以下说法不正确的是（）。

A.栈的特点是后进先出B.队列的特点是先进先出

C.栈的删除操作在栈底进行，插入操作在栈顶进行

D.队列的插入操作在队尾进行，删除操作在队头进行

13.串函数S任。即（匕5人'；加葭）的值为（）。

A.1B.0C.“abAaba”D.-1

14.一个栈的进栈序列是a,b,c,d,则栈的不可能的出栈序列是（）。

A.adbcB.bead

C.cbadD.deba

15.设有一个12阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储

到一维数组b中（矩阵A的第一个元素为au，数组b的下标从1开始），则矩阵A

中第4行的元素在数组b中的下标i一定有（）。

A.74W10B.UWiW15C.9WiW14D.6WiW9

16.已知一个图的边数为m,则该图的所有顶点的度数之和为（）。

A.2mB.mC.2m+lD.m/2

17.设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组

亦front和rear分别为链队列的头指针和尾指针，要执行出队操作，用x保存出队元素的

值，p为指向结点类型的指针，可执行如下操作：p=front->next;x=p->data;然后执行

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

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

18.以下说法不正确的是（）o

A.连通图G一定存在生成树

B.连通图G的生成树中一定包含G的所有顶点

C.连通图G的生成树中不一定包含G的所有边

D.连通图G的生成树可以是不连通的

19.散列查找的原理是（）o

A.在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系

B.按待查记录的关键字有序的顺序方式存储

C.按关键字值的比较进行查找

D.基于二分查找的方法

20.空串的长度为（）。

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

21.排序过程中，每一趟从无序子表中将•个待排序的记录按其关键字的大小放置到已

经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是（）o

A.选择排序B.快速排序

C.冒泡排序D.直接插入排序

22.采用顺序查找法对长度为n的线性表进行查找（不采用表尾设监视哨的方法），最坏

的情况下要进行（）次元素间的比较。

A.n+2B.nC.n-1D.n/2

23.设有一个10阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储

到--维数组b中。（矩阵A的第•个元素为山」，数组b的下标从1开始），则矩阵

元素a±3对应一维数组b的数组元素是（）。

A.b[18]B.b[8]C.b[13]D.b[10]

24.如图1若从顶点a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为

()。

A.acebdfgh

B.aebcghdf

C.aedfbcgh

D.abecdfgh

25.已知如图2所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可

能得到的一种顶点序列为（）。

A.abecdfB.acfebdC.aebcfdD.aedfcb

26.一棵哈夫曼树总共有23个结点，该树共有（）个叶结点（终端结点）。

二、填空题

1.通常数据的逻辑结构包括集合、线性、、四种类型。

2.通常可以把某城市中各公交站点间的线路图抽象成结构。

3.设有一个单向链表，结点的指针域为next,头指针为head,p指向尾结点，为了使

该单向链表改为单向循环链表，可用语句。

4.设有一个单向循环链表，头指针为head,链表中结点的指针域为next,p指向尾结

点的直接前驱结点，若要删除尾结点，得到•个新的单向循环链表，可执行操作

5.循环队列的队头指针为f,队尾指针为r,当______时表明队列已空。

6.在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next,则插入一个

s所指结点的操作为；r=s；

7.设有一个链栈，栈顶指针为hs,现有一个s所指向的结点要入栈，则可执行操作

___________________和hs=s；

8.循环队列的队头指针为f,队尾指针为r,当______________时表明队列为空。

9.在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next,则插入一个

s所指结点的操作为;r=s；

10.“A”在存储时占个字节。

11.串的两种最基本的存储方式分别是和。

12.一棵二叉树没有单分支结点，有6个叶结点，则该树总共有个结点。

13.一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别

为、°

14.按照二叉树的递归定义,对二叉树遍历的常用算法有、、

三种。

15.两个串相等的充分必要条件是o

16.把数据存储到计算机中，并具体体现数据之间的逻辑结构称为结构。

17.一棵二叉树叶结点（终端结点）数为5,单分支结点数为2,该树共有个结

点。

18.如图3所示的二叉树，其后序遍历序列为。

图3

19.根据搜索方法的不同，图的遍历有、两种方法。

20.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其

右孩子的值。这种说法是的。（回答正确或不正确）

21.一个有序表｛3,4,10,14,34,43,46,64,75,78,90,96,130｝用折半查找

法查找值为90的结点，经次比较后查找成功。

三、综合题

1.（1）已知某二叉树的后序遍历序列是debca,中序遍历序列是dbeac,试画出该二叉

树

(2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好

使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系。

(3)给出该树的前序遍历序列

2.(1)组记录的关键字序列为｛45,40,65,43,35,95｝,写出利用快速排序的方

法，以第一个记录为基准得到的一趟划分的结果(要求给出一趟划分中每次扫描和交换的

结果)

(2)对序列｛45,40,65,43,35,95｝利用直接插入排序，写出逐次插入过程(从

第一个元素一直到第六个元素)。

3.(1)设有一个整数序列｛40,28,6,72,100,3,54｝依次取出序列中的数，构造

一棵二叉排序树

(2)对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度

4.

(1)设有查找表｛5,14,2,6,18,7,4,16,3｝,依次取表中数据，构造一棵二叉排序树.

(2)说明如何通过序列的二叉排序树得到相应序列的排序结果。

5.(1)利用筛选过程把序列｛42,82,67,102,16,32,57,52｝建成堆(小根堆)，画出

相应的完全二叉树(不要求中间过程)

(2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列

四、程序填空题

1.以下函数在a[0]到a[n-l]中，用折半查找算法查找关键字等于k的记录，查找成功返回

该记录的下标，失败时返回-1,完成程序中的空格

typedefstruct

｛intkey;

}NODE;

intBinary_Search(NODEa[],intn,intk)

{

intlow,mid,high;

low=0;

high二nT;

while((1))

(

mid=(low+high)/2;

if(a[mid].key==k)

return(2);

elseif((3))

low=mid+l;

else(4);

)

—(5);

}

2.以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针

structnode

{ElemTypedata;

structnode*next;

)；

structnode*top;

voidPush(ElemTypex)

(

structnode*p;

p=(structnode*)maHoc((1));

p->data=x;

⑵；

(3):

)

3.以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front,rear分别是

链队列的队头、队尾指针

structnode

{ElemTypedata;

structnode*next;

)；

structnode*front,*rear;

voidInQueue(ElemTypex)

{

structnode*p;

p=(structnode*)___(1);

p->data=x;

p->next=NULL;

一(2);

rear=___(3);

)

期末综合练习一答案

一、单项选择题

1.D2.C3.C4.C5.D6.B7.A8.A9.A10.C11.C

12.C13.D14.A15.A16.A17.B18.D19.A20.A21.D22.B

23.C24.D25.D26.D

二、填空题

1.树形；图状

2.图状

3.p->next=head;

4.p->next=head；

5.r=f

6.r->next=s

7.s->next=hs;

8.r==f

9.r->next=s

10.2

11.顺序存储链式存储

12.11

13.2i和2i+l

14.先序；中序；后序

15.串长度相等且对应位置的字符相等

16.物理(存储)

17.11

18.gdbeihfca

19.深度优先搜索遍历广度优先搜索遍历

20.错误

21.4

三、综合应用题(每小题10分，共30分)

1.(1)

(2)d<b<e<a<c

(3)abdec

2.

(1)叵的65433595

35406543回5

3540网36595

3540碰引6595

35404®6595

(2)404565433595

404345653595

354043456595

3.(1)

(2)ASL=(1x14-2x2+3x3+4)/7=18/7

4.(1)

(2)

中序遍历

5.

(1)

初始树

(2)102,52,42,82,16,67,32,57

四、程序填空题

1.(1)low<=high

(2)mid

(3)a[mid].key<k;

(4)high=mid-l

(5)return-1;

2.(1)low<=high

(2)mid

(3)a[mid].key<k;

(4)high=mid-l

(5)return-1;

3.(1)sizeof(structnode)

(2)p->next=top

(3)top=p

4.(1)malloc(sizeof(structnode))

(2)rear->next=p

(3)p

期末综合练习二

一、单项选择题

1.()是性质相同的数据元素的集合，是数据的子集。

A.数据元素B.数据对象C.数据结构D.数据项

2.同一种逻辑结构()。

A.只能有唯一的存储结构B.可以有不同的存储结构

C.只能表示某一种数据元素之间的关系D.以上三种说法均不正确

3.设链表中的结点是NODE类型的结构体变量，且有NODE*p；为了申请一个新结点,

并由p指向该结点，可用以下语句()。

A.p=(NODE*)malloc(sizeof(NODE));

B.p=(*NODE)malloc(sizeof(NODE));

C.p=(NODE)malloc(sizeof(p));

D.p=(NODE*)malloc(sizeof(p));

4.链表所具备的特点是()。

A.可以随机访问任一结点B.占用连续的存储空间

C.插入删除元素的操作不需要移动元素结点1).可以通过下标对链表进行直接访问

5.设顺序存储的线性长度为n,要在第i个元素之前插入一个新元素，按课本的算法当

i=()时，移动元素次数为2

A.n/2B.nC.1D.n-1

6.数据的物理结构()。

A.与数据的逻辑结构无关B.仅仅包括数据元素的表示

C.只包括数据元素间关系的表示D.包括数据元素的表示和关系的表示

7.一个栈的进栈序列是1,2,3,4,则栈的不可能的出栈序列是()(进出栈操

作可以交替进行)

A.3,2,4,IB.I,4,2,3

C.4,3,2,1D.3,2,1,4

8.线性结构中数据元素的位置之间存在()的关系。

A.一对一B.一对多

C.多对多D.每一个元素都有一个直接前驱和一个直接后继

9.设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成,

front和rear分别为链队列的头指针和尾指针。设p指向要入队的新结点(该结点已

被赋值)，则入队操作为()。

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

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

10.以下表中可以随机访问的是(）。

A.单向链表B.双向链表

C.单向循环链表D.顺序表

11.以下说法不正确的是()。

A.顺序栈中，栈满时再进行进栈操作称为“上溢”

B.顺序栈中，栈空时再作出栈栈操作称为“下溢”

C.顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满

D.顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空

12.算法的时间复杂度与()有关。

A.所使用的计算机B.与计算机的操作系统

C.与算法本身D.与数据结构

13.设有一个20阶的对称矩阵A,采用压缩存储方式，将其下三角部分以行序为主序存

储到一维数组中（矩阵A的第一个元素为a”，数组b的下标从1开始），则矩阵元素

a4在一维数组b中的下标是（）。

A.30B.28C.40D.33

14.设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为（）。

A.n-i+lB.n-iC.n-i-lD.i

15.深度为5的完全二叉树第5层上有4个结点，该树一共有（）个结点。

A.28B.30C.31D.19

16.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是P所指结点

的直接后继，现要删除q所指结点，可用的语句是（）。

A.p=q->nextB.p->next=qC.p->next=q->nextD.q->next=NULL

17.已知一个图的所有顶点的度数之和为m,则m一定不可能是（）。

A.4B.8C.12D.9

18.从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执

行（）。

A.x=top->data;top=top->next;B.x=top->data：

C.top=top->next;x=top->data;D.top=top->next;x=data;

19.以下说法正确的是（）。

A.连通图G的生成树中可以包含回路

B.连通图G的生成树可以是不连通的

C.连通图G的生成树一定是唯一的

D.连通图G的生成树一定是连通而不包含回路的

20.在一个链队中，假设f和r分别为队头和队尾指针,则删除一个结点的运算为（

A.r=f->next;B.r=r->next;C.f=f->next;D.f=r->next;

21.对n个元素进行冒泡排序，通常要进行n-1趟冒泡，在第j趟冒泡中共要进行（）

次元素间的比较。

A.jB.j-1C.n-jD.n-j-1

22.一个栈的进栈序列是a,b,c,d,e,则栈的不可能输出序列是（）（进栈出栈

可以交替进行）。

A.dceabB.edcbaC.decbaD.abcde

23.在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是（）。

A.冒泡B.选择C.直接插入D.折半插入

24.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功

的平均比较次数为（）。

A.26/10B.29/10C.29/9D.31/10

25.如图1若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（）。

A.aebcfdAA

B.abedcf/\\

C.acebdf

D.acfbde（br—（e）Yc）

d

图1

26.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进

行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（）。

A.冒泡B.直接插入C.折半插入D.选择排序

27.一棵哈夫曼树有n个叶子结点（终端结点），该树总共有（）个结点。

A.2n-2B.2n-lC.2nD.2n+2

28.设有一个10阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主存

储到一维数组B中（数组下标从1开始），则矩阵中元素A&5在一维数组B中的下标是

（）。

A.33B.32C.85D.41

29.数据的（）结构与所使用的计算机无关。

A.逻辑B.物理C.存储D.逻辑与存储

30.在一个无向图中，所有顶点的度数之和等于边数的（）倍。

A.3B.2.5C.1.5D.2

二、填空题

1.通常可以把一本含有不同章节的书的目录结构抽象成结构。

2.栈和队列的操作特点分别是和。

3.要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点，若链表中结

点的指针域为next,可执行和p->next=s;的操作。

4.结构中的数据元素存在多对多的关系称为结构。

5.设有一个非空的链栈，栈顶指针为hs,要进行出栈操作，用x保存出栈结点的值，

栈结点的指针域为next,则可执行x=hs->data;。

6.根据数据元素间关系的不同特性，通常可分为集合、线性、、四类基

本结构。

7.在一个不带头结点的非空链队中，f和r分别为队头和队尾指针，队结点的数据域为

data,指针域为next,若要进行出队操作，并用变量x存放出队元素的数据值，则相

关操作为x=f->data;。

8.要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较

的次数和算法的时间复杂度分别为和。

9.循环队列的最大存储空间为MaxSize=8,采用少用一个元素空间以有效的判断栈空

或栈满，若队头指针front=4,则当队尾指针rear=时，队列为空，当rear=

时，队列有6个元素。

10.稀疏矩阵存储时，采用一个由_________、、3部分信

息组成的三元组唯一确定矩阵中的一个非零元素。

II.在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、

12.一棵二叉树顺序编号为6的结点（树中各结点的编号与等深度的完全二叉中对应位

置上结点的编号相同），若它存在右孩子，则右孩子的编号为。

13.向一个栈顶指针为h的链栈中插入一个s所指结点时,可执行s->next=h;和。

14.在一个链队中，设f和r分别为队头和队尾指针,则插入s所指结点的操作为

和r=s;(结点的指针域为next)

15.如图2所示的二叉树，其前序遍历序列为。

图2

16.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有个结

点。(根所在结点为第1层)

17.在队列的顺序存储结构中，当插入一个新的队列元素时，指针的值增1，当

删除一个元素队列时，指针的值增1。

18.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的

、和三项信息。

19.循环队列的引入，目的是为了克服。

20.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65

插入到有序表时，为寻找插入位置需比较次。

三、综合题

1.(1)设head,和pi分别是不带头结点的单向链表A的头指针和尾指针,head2和P2分

别是不带头结点的单向链表B的头指针和尾指针，若要把B链表接到A链表之

后，得到一个以head,为头指针的单向循环链表，写出其中两个关键的赋值语句

(不用完整程序，结点的链域为next)。

(2)单向链表的链域为next,设指针p指向单向链表中的某个结点，指针s指向一个

要插入链表的新结点，现要把s所指结点插入p所指结点之后，某学生采用以下

语句：

p->next=s;s->next=p->next;

这样做正确吗？若正确则回答正确，若不正确则说明应如何改写

2.

(1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树(要求每个结点的左子树根

结点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。

(2)一棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由？

3.(1)画出对长度为10的有序表进行折半查找的判定树(以序号1,2,……10表示

树结点)

(2)对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度

4.一组记录的关键字序列为(46,79,56,38,40,84)

(1)利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果(给出逐次交

换元素的过程，要求以升序排列)

(2)对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。

5.(1)利用筛选法，把序列｛37,77,62,97,11,27,52,47｝建成堆(小根堆)，画

出相应的完全二叉树

(2)写出对上述堆所对应的二叉树进行前序遍历得到的序列

6.设查找表为(50,60,75,85,96,98,105,110,120,130)

(1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较？

(2)为了折半查找元素95,经过多少次元素间的比较才能确定不能查到？

(3)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点)

四、程序填空题

1.以下函数为直接选择排序算法，对a[l],a[2],…a[n]中的记录进行直接选择排序，完成

程序中的空格

typedefstruct

｛intkey;

}NODE;

voidselsort(NODEa[],intn)

(

inti,j,k;

NODEtemp;

for(i=1;i<=___(1);i++)

(

k=i;

for(j=i+l;j<=_(2)；j++)

if(a[jj.key<alkj.key)_(3):

if(i!=k)

(

temp=a[i];

—(4);

一(5)一；

)

)

)

2.以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从

前向后依次为1,2,3..........n,完成程序中空格部分。

NODE*create(n)

{NODE*head,*p,*q;

inti;

p=(NODE*)malloc(sizeof(NODE));

head=(1);(2);pfnext=NULL;/*建立头结点*/

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

{P=(3)；

p-^data=i;

p^next=NULL;

q-^next=(4);

⑸；

)

return(head);

3.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、

右指针域分别为left和right,数据域data为字符型，BT指向根结点)。

voidInorder(structBTreeNode*BT)

{if(BT!=NULL){

(1)__________________；

_(2)__________________；

(3);

)

期末综合练习二答案

一、单项选择题

1.B2.B3.A4.C5.D6.D7.B8.A9.A10.D11.C

12.C13.D14.B15.D16.C17.D18.A19.D20.C21.C22.A

23.D24.B25.B26.C27.B28.A29.A30.D

二、填空题

1.树形

2.先进后出、先进先出

3.s->next=p->next；

4.图状(网状)

5.hs=hs->next;

6.树形图状

7.f=f->next;

8.n-l,0(n)

9.4；2

10.行号；列号；非零元

11.左指针右指针

12.13

13.h=s;

14.r->next=s;

15.abdefcg

16.12

17.尾头

18.行下标、列下标、非零元素值

19.假上溢

20.3

三、综合应用题

1.

(1)pr>next=head2;p2->next=head］；

(2)不对，s->next=p->next；p->next=s；

2.

4：110

7：00

8：01

9：10

（2）2n-l个，因为非叶结点数比叶结点数少一个。

(2)ASL=(1x14-2x2+3x4+4x3)/10=29/10

(1)初始序列

538

79,6,40,84

753

409,6,8,,84

7_5

408,6,38,79

40_8,6,6,,84

35H-

408,i6,79,84

l|3一]

4035-a5

-79,84

34-5

79,84

初始树堆

(1)3次

⑵4次

图5

四、程序填空题

1.(1)n-1

(2)n

(3)k=j

(4)a[i]=a[k]

(5)a[k]=temp

2.

(1)p

(2)q=p

(3)(NODE*)malloc(sizeof(NODE))

(4)p

(5)q=p

(1)Inorder(BT->left)

(2)printf(a%c?,,BT->data)

(3)Inorder(BT->right)

期末综合练习三

一、单项选择题

1.深度为5的完全二叉树共有20个结点，则第5层上有（）个结点（根所在结点

为第一层）。

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

2.在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。

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

3.已知一个图的边数为m,则该图的所有顶点的度数之和为（）。

A.2mB.mC.2m+lD.m/2

4.串函数StrCat（a,b）的功能是进行串（）。

A.比较B.复制C.赋值D.连接

5.数据结构中，与所使用的计算机无关的是数据的（）结构。

A.物理B.存储C.逻辑与物理D.逻辑

6.一棵有n个结点采用链式存储的二叉树中，共有（）个指针域为空。

A.n+1B.nC.n_lD.n_2

7.链表所具备的特点是（）。

A.可以随机访问任一结点B.占用连续的存储空间

C.插入删除不需要移动元素结点D.可以通过下标对链表进行直接访问

8.设一棵哈夫曼树共有n个非叶结点,则该树有（）个叶结点。

A.nB.n+1C.n-1D.2n

9.线性表只要以（）方式存储就能进行折半查找。

A.链接B.顺序C.关键字有序的顺序D.二叉树

10.从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则

执行（）。

A.x=top->data;top=top->next;B.x=top->data;

C.top=top->next;x=top->data;D.top=top->next;x=data;

11.散列查找的原理是（）。

A.在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系

B.按待查记录的关键字有序的顺序方式存储

C.按关键字值的比较进行查找

D.基于二分查找的方法

12.一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（）个结点。

A.30B.20C.21D.23

13.对n个元素进行冒泡排序若某趟冒泡中只进行了（）次元素间的交换，则表

明序列已经排好序。

A.1B.2C.0D.n-1

14.在一个无向图中，所有顶点的度数之和等于边数的（）倍。

A.3B.2.5C.1.5D.2

15.排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已

经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是（）。

A.直接插入排序B.快速排序

C.冒泡排序D.选择排序

16.已知如图1所示的一个图，若从顶点%出发，按深度优先搜索法进行遍历，则可能

得到的一种顶点序列为（

A.V1V2VMV5V3V6MB.VMVMVN3V6%

C.V1V2V.iV8V3V5V6V-D.VMVeVMVM%

图1

17.在对一组元素（64,48,106,33,25,82,70,55,93）进行直接插入排序时，当

进行到要把第7个元素70插入到已经排好序的子表时，为找到插入位置，需进行

（）次元素间的比较（指由小到大排序）。

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

18.已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能

得到的一种顶点序列为（）。

A.abcedfB.abcefdC.aebcfdD.acfdeb

图2

19.采用顺序查找法对长度为n的线性表进行查找（不采用表尾设监视哨的方法），最坏

的情况下要进行（）次元素间的比较。

A.n+2B.nC.n-1D.n/2

20.对二叉排序树进行（）遍历，可以使遍历所得到的序列是有序序列。

A.按层次B.后序C.中序D.前序

21.如图3,若从顶点a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为

（）o

A.acebdgf

B.abecdgf

C.acfedgb

D.abecfdg

图3

22.在有序表⑵4,7,14,34,43,47,64,75,80,90,97,120｝中，用折半查找

法查找值80时，经（）次比较后查找成功。

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

23.元素2,4,6,8按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈

可以交替进行）。

A.8,6,4,2B.2,4,6,8

C.4,2,8,6D.8,6,2,4

24.有一个长度为9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功

的平均比较次数为（）。

A.25/10B.25/9C.20/9D.17/9

25.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）

的一端的方法，称为（）排序。

A.归并B.插入C.选择D.快速

26.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素

进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是

()。

A.冒泡B.直接插入C.折半插入D.选择排序

27.一棵哈夫曼树总共有23个结点，该树共有（）个叶结点（终端结点）

A.10B.13C.11D.12

28.一组记录的关键字序列为（46,79,56,38,40,84）,利用快速排序，以第一个关

键字为分割元素，经过一次划分后结果为（）。

A.40,38,46,79,56,84B.40,38,46,56,79,84

C.40,38,46,84,56,79D.38,40,46,56,79,84

29.队列的插入操作在（）进行。

A.队头B.队尾C.队头或队尾D.在任意指定位置

二、填空题（每小题2分，共24分）

1.一棵二叉树没有单分支结点，有