2023年数据结构(本)期末综合练习(12月)

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

2023年12月

期末综合练习一

一、单项选择题

1.数据口勺物理构造（）。

A.与数据的逻辑构造无关B.仅仅包括数据元素的I表达

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

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

A.只能有一种数据项构成

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

C.可以是一种数据项也可以由若干个数据项构成

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

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

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

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

4.线性表日勺次序构造中，（）。

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

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

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

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

5.如下表中可以随机访问II勺是（）。

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

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

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

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

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

7.设次序存储口勺线性表长度为n,对于删除操作，设删除位置是等概率的，则删除一种元素平均移动元素的次数为

（

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

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

A.一对一B.一对多

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

9.设top是一种链栈的J栈顶指针，栈中每个结点由一种数据域data和指针域next构成，设用x接受栈顶元素，则

出栈操作为（）o

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

C.x=iop->nexi;（op=iop->data;D.iop->nexi=iop;x=iop->daia;

10.设次序存储的J线性表长度为n,要删除第i个元素，按书本日勺算法，当i=（）时，移动元素的次数为3

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

11.如下说法对的H勺是（）。

A.队列是后进先出

B.栈口勺特点是后进后出

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

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

12.如下说法不对的的是（）o

A.栈口勺特点是后进先出B.队列日勺特点是先进先出

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

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

13.串函数StrCmp（“abA”,“aba"）口勺值为（）。

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

14.一种栈的进栈序列是a,b,c,d,则栈的不也许的出栈序列是（）。

A.adbcB.bead

C.cbadD.deba

15.设有一种12阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中（矩阵A

内第一种元素为川」，数组b的下标从1开始），则矩阵A中笫4行的元素在数组b中H勺下标i一定有（）。

A.7WiW10B.UWiW15C.9WiW14D.6WiW9

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

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

17.设有一种带头结点的链队列，队列中每个结点由一种数据域data和指针域next构成，front和rear分别为徒队

列的头指针和尾指针，要执行出队操作，用x保留出队元素的值，p为指向结点类型W、J指针，可执行如下操作：

p=front->next;x=p->data;然后执行（）。

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

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

18.如下说法不对的的是（）。

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

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

C.连通图G日勺生成树中不一定包括G日勺所有边

D.连通图GH勺生成树可以是不连通日勺

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

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

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

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

D.基于二分查找的措施

20.空串的长度为（）0

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

21.排序过程中，每一趟从无序子表中将一种待排序的记录按其关键字的大小放置到已经排好序H勺子序列的合适位

置，直到所有排好序为止，该排序算法是（）0

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

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

22.采用次序查找法对长度为n的线性表进行查找（不采用表尾设监视哨的措施），最坏的状况下要进行（）

次元素间的比较。

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

23.设有一种10阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩阵A

的第一种元素为aL1,数组b日勺下标从1开始），则矩阵元素a5.3对应一维数组b日勺数组元素是（）。

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

24.如图1若从顶点a出发按广度优先搜索法进行遍历，则也许得到H勺顶点序列为（）。

A.acebdfgh

B.aebcghdf

C.aedfbcgh

D.abecdfgh

图1

25.巳知如图2所示丛J一种图，若从顶点a出发,按深度优先搜索法进行遍历，则也许得到的一种顶点序列为（）。

D.aedfcb

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

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

二、填空题

1.一般数据H勺逻辑构造包括集合、线性、、四种类型。

2.一般可以把某都市中各公交站点间的线路图抽象成构造。

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

表，可用语句。

4.设有一种单向循环链表，头指针为head,链表中结点的指针域为next,p指向尾结点的直接前驱结点，若要删

除尾结点，得到一种新H勺单向循环链表，可执行操作o

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

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

___；LS；

7.设有一种链栈，栈顶指针为hs,既有一种s所指向欧I结点要入栈，则可执行操作

___________________和hs=s；

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

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

r=s；

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

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

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

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

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

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

16.把数据存储到计算机中,并详细体现数据之间H勺逻辑构造称为构造。

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

18.如图3所不淤J二叉树，其后序遍历序列为

图3

19.根据搜索措施时不一样，图的遍历有、两种措施。

20.二叉树为二叉排序的充足必要条件是其任一结点的值均不小于其左孩子11勺值、不不小于其右孩子"勺值。这种

说法是的。（回答对的或不对的J）

21.一种有序表｛3,4,10,14,34,43,46,64,75,78,90,96,130｝用折半查找法查找值为90的J结点，经

次比较后查找成功。

三、综合题

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

（2）若上述二叉树的各个结点的字符分别代表不一样的整数（其中没有相等的），并恰好使该树成为一棵二叉排

序树，试给出a、b、c、d、el月大小关系。

（3〕给出该树日勺前序遍历序列

2.（1）一组记录的关键字序列为｛45,40,65,43,35,95｝,写出运用迅速排序日勺措施，以第一种记录为基准得

到的一趟划分R勺成果（规定给出一趟划分中每次扫描和互换H勺成果）

（2）对序列｛45,40,65,43,35,95｝运用直接插入排序，写出逐次插入过程（从第一种元素一直到第六个元

素）。

3.（1）设有一种整数序列｛40,28,6,72,100,3,54｝依次取出序列中时数，构造一棵二叉排序树

（?）对上述二叉排序树，在等概率条件下，求成功杳找的平均查找长度

4.

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

（2）阐明怎样通过序列H勺二又排序树得到对应序列的排序成果。

5.(1)运用筛选过程把序列｛42,82,67,102,16,32,57,52｝建成堆(小根堆)，画出对应的完全二叉树(不规

定中间过程)

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

四、程序填空题

I.如下函数在a［0］到aH-1］中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回

-I,完毕程序中的空格

typedefstruct

｛inikey;

|NODE:

intBinary_Search(NODEa[],intn,intk)

(

intlow,mid,high;

1ow=0；

high=n-l;

whi1e((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*)ma11oc((1));

p->data=x;

⑵；

(3);

}

3.如下函数为链队列H勺入队操作，x为要入队的结点的数据域区I值，front、rear分别是链队列的队头、队尾指针

structnode

ElemTypedata;

structnode*ncxt;

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.C12.C13.D14.A15.A

16.A17.B18.D19.A20.A21.D22.B23.C24.D25.D26.D

二、填空题

1.树形；图状

2.图状

3.p->next=head;

4.p->ncxt=hcad：

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分）

I.(1)

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

(3)abdcc

2.

□

354065436595

354043436595

354043456595

(2)404565433595

404345653595

354043456595

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

4.(1)

(2)

中序遍历

5.

四、程序填空题

1.(1)lo\v<=high

(2)mid

(3)a[midl.key<k;

(4)hish=mid-l

(5)return-1;

2.(1)low<=high

(2)mid

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

(4)high=mid-1

(5)return-1;

3.(1)sizeof(structnode)

(2)p->next=top

(3)top=p

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

(2)rear->next=p

(31p

期末综合练习二

一、单项选择题

1.（）是性质相似的数据元素口勺集合，是数据的子集。

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

九同一种逻辑构造（）。

A.只能有唯一U勺存储构造B.可以有不一样的存储构造

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

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.链表所具有的特点是()o

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

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

5.设次序存储的线性长度为n,要在第i个元素之前插入一种新元素，按书本的I算法当i=()时，移动元

素次数为2

A.n/2B.nC.ID.n-l

6.数据的物理构造().

A.与数据H勺逻辑构造无关B.仅仅包括数据元素H勺表达

C.只包括数据元素间关系H勺表达I).包括数据元素的表达和关系的表达

7.一种栈的进栈序列是1,2,3,4,则栈的不也许U勺出栈序列是()(进出栈操作可以交替进行)

A.3,2,4,1B.L4,2,3

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

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

A.一对一B.一对多

C.多对多D.每一种元素均有一种直接前驱和〜种直接后继

9.设有一种带头结点曰勺链队列，队列中每个结点由一种数据域dma和指针域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.如下说法不对Fl勺的是（

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

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

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

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

12.算法的时间复杂度与（）有关。

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

C.与算法自身D.与数据构造

13.设有一种20阶H勺对称矩阵A,采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中（矩阵A

H勺第一种元素为a”，数组b的J下标从1开始），则矩阵元素a.在一维数组b中口勺下标是（）。

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

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

A.n-i+1B.n-iC.n-i-1D.i

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

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

16.在一种单链表中，D、Q分别指向表中两个相邻日勺结点，且Q所指结点是D所指结点日勺直接后继，现要删除Q所

指结点，可用口勺语句是（)o

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

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

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

18.从一种栈顶指针为top的J链栈中删除一种结点时，用变量x保留被删结点口勺值，则执行（）。

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

C.top=top->next;x=top->data;I）.top=top->next;x=data;

19.如下说法对的的是（）。

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

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

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

D.连通图GH勺生成树一定是连通而不包括回路的）

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-lC.n-jD.n-j-1

22.一种栈的进栈序列是a,b,c,d,e,则栈的J不也许输出序列是（）（进栈出栈可以交替进行）。

A.dceabB.edcbaC.decbaI）,abcde

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

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

24.有•种长度为10的有序表，按折半查找对该表进行查找，在笔概率状况下查找成功的平均比较次数为（）。

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

25.如图1若从顶点a出发按深度优先穆索法讲行遍历，则也许/I\得到的顶点序列为（）。

A.acbcfd

B.abcdcf

C.accbdf

D.acfbde

图1

26.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的I元素进行比较（规定比较次数尽量

少），然后将其放入已排序序列日勺对的位置的措施是（）。

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.数据时（）构造与所使用的I计算机无关。

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

30.在一种无向图中,所有顶点日勺度数之和等于边数的（)倍,

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

二、填空题

1.一般可以把一本具有不一样章节的书的目录构造抽象成构造。

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

3.要在一种单向链表中p所指向的结点之后插入一种s所指向的新结点，若链表中结点的指针域为next,可执行

和p->next=s;日勺操作。

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

5.设有一种非空的I链栈，栈顶指针为hs,要进行出栈操作，用x保留出栈结点艮|值，栈结点日勺指针域为nexi,则

可执行x=hs->data;«

6.根据数据元素间关系的不一样特性，一般可分为集合、线性、、四类基本构造。

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

进行出队操作，并用变量x寄存出队元素的数据值，则有关操作为x=f->data;o

8.规定在n个数据元素中找其中值最大的元素，设基本操作为元素间II勺比较。则比较的次数和算法U勺时间复杂度

分别为和o

9.循环队列的最大存储空间为MaxSizc=8,采用少用一种元素空间以有效的I判断栈空或栈满，若队头指针fronl=4,

则当队尾指针rear=时，队列为空，当rear=时，队列有6个元素。

10.稀疏矩阵存储时，采用一种由__________、、3部分信息构成的三元组唯一确定矩

阵中日勺一种非零元素。

II.在二叉树日勺链式存储构造中，一般每个结点中设置三个域，它们是值域、

12.一棵二叉树次序编号为6的结点（树中各结点的编号与等深度H勺完全二叉中对应位置上结点的编号相似），若

它存在右孩子，则右孩子的编号为。

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

14.在一种链队中，设f和1•分别为队头和队尾指针，则插入s所指结点的操作为和r=s;（结点时指针域为

next）

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

图2

16.设有一棵深度为4的J完全二叉树，第四层上有5个结点，该树共有个结点。(根所在结点为第1层)

17.在队列口勺次序存储构造中，当插入一种新口勺队列元素时，指针时值增I,当删除一种元素队列时，

指针口勺值增1。

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

___三项信息。

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

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

插入位置需比较次。

三、综合题

1.(1〕设head1和田分别是不带头结点U勺单向链表AU勺头指针和尾指针，head2和P2分别是不带头结点的单向链表

B的头指针和尾指针，若要把B链表接到A链表之后，得到一种以headi为头指针的单向循环链表，写出其

中两个关键的赋值语句(不月完整程序，结点的链域为next)。

(2〕单向链表口勺链域为next,设指针p指向单向链表中的某个结点，指针s指向一种要插入链表的新结点，现要

把s所指结点插入p所指结点之后，某学生采用如下语句：

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

这样做对的吗？若对H勺则回答对於J,若不对口勺则阐明应怎样改写

2.

(1)以2,3,4,7,8,9作为叶结点的I权，构造一棵哈夫曼树(规定每个结点的左子树根结点口勺权不不小于等于右

子树根结点的权)，给出对应权重值叶结点的I哈夫曼编码。

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

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

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

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

(1)运用迅速排序口勺措施，给出以第一种记录为基准得到的一次划分成果(给出逐次互换元素日勺过程，规定以升

序排列)

(2)对上述序列用堆排序的措施建立大根堆，规定以二叉树逐次描述建堆过程。

5.(1)运用筛选法，把序列｛37,77,62,97,II,27,52,47｝建成堆(小根堆)，画出对应的完全二叉树

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

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

(I)说出进行折半查找成功查找到元素12()需要进行多少次元索间口勺比较？

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

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

四、程序填空题

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

typedefstruct

{intkey;

}NODE;

voidsclsort(NODEal],intn)

(

inti,j,k;

NODEtemp;

for(i=1;i<=_⑴;i++)

{

k=i;

for(j=i+l;j<=_⑵:j++)

if(a[j].key<a[k].key)_(3);

if(i!=k)

(

tcmp=a[ij;

—(4)；

一(5)一；

}

2.如下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1,2,3,

完毕程序中空格部分。

NODE*crcate(n)

{NODE*head,*p,*q;

inti;

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

head=(1);(2);p->next=NULL;/*建立头结点*/

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

{P=<3)_______________；

p->data=i;

p->next=NULL;

q->ncxt=(4);

(5)：

reiurn(head);

)

3.如下程序是中序遍历二叉树的递归算法的程序，完毕程序中空格部分(树构造中左、右指针域分别为lefl和right,

数据域data为字符型，BT指向根结点)。

voidInorder(structBTreeNode*BT)

{if(BT!=NULL){

(1)

(2)

(3)

期末综合练习二答案

一、单项选择题

1.B2.B3.A4.C5.D6.D7.B8.A9.A10.D11.C12.C13.D14.B

15.D16.C17.D18.A19.D20.C21.C22.A23.D24.B25.B26.C27.B28.A

29.A30.D

二、填空题

I.树形

2.先进后出、先进先出

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

4.图状(网状)

5.hs=hs->next;

6.树形图状

7.f=f->next;

8.n-1,O(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)p)->next=headz;p2->next=headi；

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

2.

(1)

/

2：1110

3:1111

4：110

7：00

8：01

9：10

(2)2n-l个，由于非叶结点数比叶结点数少一种。

(2)ASL=(Ixl+2x2+3x4+4x3)/10=29/10

4.

(1)初始序列

圆，79,56,38,40,84

40,79,56,38,阳，84

40,园，56,38,79,84

40,38,56,园79,84

40,38,园，56,79,84

40,38,园，56,79,84

图3

必

(2)11,37,47,97,77,27,62,52

6.

(1)3次

(2)4次

(3)

图5

四、程序填空题

1.(1)n-1

(2)n

(3)k=j

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

(5)a[k]=tenip

(1)p

(2)q=p

(S)(NODE*)mal1oc(sizeof(NODE))

(4)p

(5)q=p

(1)Inorder(BT->left)

(2)printf(,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,则该图日勺所有顶点的I度数之和为（）。

A.2mB.mC.2ni+1D.m/2

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

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

5.数据构造中，与所使用日勺计算机无关H勺是数据的J(）构造,

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

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

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

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

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

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

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

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

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

A.链接B.次序C.关键字有序R勺次序D.二又树

10.从一种栈顶指针为topH勺链栈中删除一种结点时•，用变量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.散列查找的原理是（）o

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

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

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

D.基于二分杳找的措施

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

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

13.对n个元素进行冒泡排序若某趟冒泡中只进行了（）次元素间的互换，则表明序列已经排好序。

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

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

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

15.排序过程中，每一趟从无序子表中将一种待排序的记录按其关键字的大小放置到已经排好序R勺子序列的合适位

置，直到所有排好序为止，该排序算法是（）。

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

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

16.已知如图1所示的•种图，若从顶点V,出发，按深度优先搜索法进行遍历，则也许得到的一种顶点序列为（）。

A.V,V2V,V.sV5V3V6V7B.VIV2V,V5V«V3V6V7

C.VN2VNN3V5VN7D.VN3VNN2VNN8

图1

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

插入到已经排好序的子表时，为找到插入位置，需进行（）次元素间的比较（指由小到大排序）。

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

18.已知如图2所示的一种图，若从顶点a出发，按广度优先搜索法进行遍历，则也许得到的一种顶点序列为（）。

A.abccdfB.abccfdC.acbcfdD.acfdcb

19.采用次序查找法对长度为n的线性表进行查找（不采用表尾设监视哨的措施），最坏的状况下要进行（）

次元素间的J比较。

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

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

A.按层次B.后序C.中序I）.前序

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

A.acebdgf

B.abecdgf

C.acfcdgb

D.abccfdg

图3

22.在有序表［2,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/9I）.17/9

25.排序措施中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端FI勺措施，称为（）

排序。

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

26.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（规定比较次数尽

量少），然后将其放入已排序序列的对的位置日勺措施是（）。

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

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

A.10B.13C.IlD.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,79I）.38,40,46,56,79,84

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

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

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

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

2.在二叉树的链式存储构造中，一般每个结点中设置三个域，它们是、

右指针。

3.设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点H勺双亲结点的编号为10,该完全二

叉树一共有个结点。

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

5.按照二义树H勺递归定义，对二义树遍历的常用算法有.三种。

6.串R勺两种最基本的存储方式是和。

7.数据构造中H勺数据元素存在一对多的关系称为构造。

8.一棵有2n-l个结点的二叉树，其每一种非叶结点的度数都为2,则该树共有个叶结点。

9.把数据存储到计算机中，并详细体现数据之间的逻辑构造称为构造。

10.对于一棵具有n个结点的二叉树，其对应的链式存储构造中共有