《数据结构(本)》期末考试复习题

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

一、单选选择题

1.栈和队列的共同特点是（C）。

A.都是先进先出B.都是操作受限的线性结构

C.都是先进后出D.元素都可以随机进出

2.数据的存储结构包括数据元素的表示和（C）。

A.数据处理的方法B.数据元素的类型

C.数据元素间的关系的表示D.相关算法

3.对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，则执行

p=（structnode*）malloc（sizeof（structnode）;p->data=a;和（C）<）

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

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

4.树状结构中数据元素的位置之间存在（B）的关系。

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

C.一对一D.多对多

5.设头指针为head的非空的单向链表，指针p指向尾结点，则通过以下操作（D）可使其成

为单向循环链表。

A.head=p;B.p=head;

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

6.设有一个长度为26的顺序表，要插入一个元素，并使它成为新表的第6个元素，需移动

元素的个数为（D）。

A.22B.19C.20D.21

7.一种逻辑结构（C）.

A.与存储该逻辑结构的计算机相关B,是指某一种数据元素的性质

C.可以有不同的存储结构D.只能有唯一的存储结构

8.头指针为head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为不带头结

点的单向循环链表，可执行head=head-〉nex;和（A）»

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

C.head->next=pD.head->next=p->next

9.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（D）。

A.给数据元素分配存储空间B.数据元素的存储

C.逻辑结构D.存储结构

10.元素111,113,115,117按顺序依次进栈，则该栈的不可能输出序列是（D）（进栈出

栈可以交替进行）。

A.111,113,115,117B.113,111,117,115

C.117,115,113,111D.117,115,111,113

11.图状结构中数据元素的位置之间存在（B）的关系。

A.每一个元素都有一个且只有一个直接前驱和一个直接后继

B.多对多C.一对一D.一对一

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

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

C.栈的特点是先进先出D.栈的特点是先进后出

13.一个单链表中，在p所指结点之后插入一个s所指的结点时，可执行：s->next=p->next;

和（D）。

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

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

14.设有一个20阶的对称矩阵A（第一个元素为al,1）,采用压缩存储的方式，将其下三角

部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵元素a6,2在一维数

组B中的下标是（B）。

A.28B.17C.21D.23

15.元素12,14,16,18顺序依次进栈，则该栈的不可能输出序列是（C）。（进栈出栈可

以交替进行）。

A.18,16,14,12B.12,14,16,18

C.18,16,12,14D.14,12,18,16

16.设有串pl="ABADF",P2="ABAFD",P3="ABADFA",P4="ABAF",以下四个串中最大的是（A）。

A.p2B.p3C.p4D.pl

17.设有一个30阶的对称矩阵A（第一个元素为al,1）,采用压缩存储的方式，将其下三角

部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维

数组B中的下标是（A）。

A.38B.32C.18D.41

18.数组a经初始化chara[]="English";a[7]中存放的是（B）1,

A."h"B.字符串的结束符C.变量hD.字符h

19.设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（B）o

A.15B.24C.22D.14

20.设主串为“ABcCDABcdEFaBc"，以下模式串能与主串成功匹配的是（B）。

A.ABCB.BedC.AbeD.BCd

21.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（C）。

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

22.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（D）。

A.2i+lB.2i-lC.2i+2D.2i

23.一棵具有16个结点的完全二叉树，共有（B）层。（设根结点在第一层）

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

24.如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶

点序列为（A）o

3

A.aecbdfB.aedfcbC.aebcfdD.abecdf

25.如下图所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶

点序列为（C）。

A.aebcfgdB.abecdfgC.aedfcgbD.acfebgd

26.线性表以（B）方式存储，能进行折半查找。

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

27.字符串“DABcdabcd321ABC”的子串是（C）»

A.“321a”B.“aBcd”C.“cd32”D.“ABcD”

28.一棵具有38个结点的完全二叉树，最后一层有（B）个结点。

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

29.如下图所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序

列为（C）»

A.acbfedgB.abcdfegC.abcdfgeD.abcfgde

30.下图的拓扑序列是（

A.23645B.56234C.23564D.52346

31.下面关于线性表的叙述错误的是（D）。

A.线性表采用链式存储便于插入和删除操作的实现

B.线性表采用链式存储不必占用一片连续的存储空间

C.线性表采用顺序存储必须占用一片连续的存储空间

D.线性表采用顺序存储便于插入和删除操作的实现

32.设有头指针为head的不带头结点的非空的单向循环链表，指针p指向其尾结点，要删除

第一个结点,则可利用下述语句head=head->next;和（D）。

A.p=head;B.head=p;C.p=NULL;D.p->next=head;

33.以下数据结构中是非线性结构的是（C）。

A.线性表B.队列C.二叉树D.栈

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

A.线性表的链式存储结构必须占用连续的存储空间

B.一种逻辑结构可以有不同的存储结构

C.一种逻辑结构只能有唯一的存储结构

D.线性表的顺序存储结构不必占用连续的存储空间

35.设有一个长度为18的顺序表，要删除第7个元素需移动元素的个数为（B）。

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

36.把数据存储到计算机中，并具体体现（A）称为物理结构。

A.数据元素间的逻辑关系B.数据的运算

C.数据的处理方法D.数据的性质

37.两个字符串相等的充要条件是（B）。

A.两个字符串的长度相等B.同时具备（A）和（C）两个条件

C.两个字符串中对应位置上的字符相等D.以上答案都不对

38.顺序表所具备的特点之一是（B）。

A.删除元素的操作不需要移动元素B.可以随机访问任一结点

C.不需要占用连续的存储空间D.插入元素的操作不需要移动元素

39.设某链表中最常用的操作是在链表的尾部插入或删除元素，在已知尾指针的条件下，选

用下列（A）存储方式最节省运算时间。

A.双向链表B.单向链表C.单向循环链表D.双向循环链表

40.图状结构中数据元素的位置之间存在（A）的关系。

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

C.一对多D.一对一

41.元素13,15,19,20顺序依次进栈，则该栈的不可能输出序列是（A）.（进栈出栈可

以交替进行）

A.19,13,15,20B.15,13,20,19

C.13,15,19,20D.20,19,15,13

42,元素20,14,16,18按顺序依次进栈，则该栈的不可能输出序列是（A）。（进栈出栈

可以交替进行）

A.18,16,20,14B.20,14,16,18

C.14,20,18,16D.18,16,14,20

43.设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,则在表中删除

结点B的操作为（A）。

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

C.p->next=q->next；D.p->next；p=q；

44.设有一个12阶的对称矩阵A（左上角第一个元素为al,1）,采用压缩存储的方式，将其

下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a5,4

在一维数组B中的下标是（C）。

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

45.栈和队列的共同特点之一是（A）。

A.只允许在端点处插入和删除元素B.都是先进先出

C.没有共同点D.都是先进后出

46.设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（C）。

A.25B.15C.14D.23

47.用链接方式存储的队列，在进行插入运算时（C）。

A.头、尾指针都需要修改B.头、尾指针都不需要修改

C.需修改尾指针D.需修改头指针

48.在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（D）。

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

49.字符串al="AEIJING",a2="AEI",a3="AEFANG",a4="AEFI"中最大的是（D）。

A.a2B.a3C.a4D.al

50.一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（B）个结点。

A.18B.19C.15D.14

51.设有一个20阶的对称矩阵A（第一个元素为al,l）,采用压缩存储的方式，将

其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩

阵中元素a6,2在一维数组B中的下标是（C）。

A.18B.23C.17D.21

52.如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶

点序列为（A）。

g

A.abcedfgB.abcfgdeC.acbfedgD.abcdfge

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

A.二叉树中任意一个非叶结点的值都大于其左子树上所有结点的值，小于其右子树上所有

结点的值，则该树为二叉排序树。

B.若二叉树中左子树上所有结点的值均小于根结点的值，右子树上所有结点的值均大于根

结点的值。则该树为二叉排序树。

C.前序遍历二叉排序树可得到一个有序序列。

D.二叉树中任意一个结点的值均大于其左孩子的值，小于其右孩子的值。则该树为二叉排

序树。

54.字符串"abcd321ABCD”的子串是（B）.

A."321a"B."21ABC"C."abcABCD"D.abcD

55.二叉树的第k层的结点数最多为（B）。

A.2K-1B.2k-lC.2K+1D.2k-1

56.数组a经初始化chara[]="English”;a[l]中存放的是（D）,

A.字符EB."n"C."E"D.字符n

57.如下图所示，若从顶点6出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序

列为（D）。

A.6,2,8,7,9,3,4B.6,9,2,3,7,8,4

C.6,2,7,9,8,4,3D.6,9,3,2,8,7,4

58.如下图所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶

点序列为（A）。

A.aedfcbB.aebcfdC.abecdfD.acfebd

59.如下图所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序

列为(A)«

A.abcdfgeB.abcfegdC.abcfgdeD.acbfedg

60.下图的拓扑序列是(B)。

A.52346B.52364C.23456D.56423

二'填空题

1.对稀疏矩阵进行压缩存储，可采用三元组表,一个有10行的稀疏矩阵A共有97个零元素,

其相应的三元组表共有3个元素。该矩阵A有10歹U。

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

3.在单向链表中，q指向p所指结点的直接后继结点，要删除q所指结点，可以用操作

p->next=q->next;。

4.n个元素进行冒泡法排序，第j趟冒泡要进行n-j次元素间的比较。

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

标和数组元素三项信息。

6.中序遍历二叉排序树可得到一个有序序列。

7.队列的操作特点是后进后出。

8.待排序的序列为8,3,4,1,2,5,9,采用直接选择排序算法，当进行了两趟选择后，

结果序列为1,2,4,8,3,5,9。

9.n个元素进行冒泡法排序，通常需要进行n泡趟冒泡。

10.广义表((a,b),d,e((i,j),k))的长度是4。

11.中序遍历二叉排序树可得到一个有序的序列。

12.广义表的(c,a,(a,b),d,e,((i,j),k))深度是3。

13.广义表(c,a,(a,b),d,e,((i,j),k))的长度是6。

14.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行10列的稀疏矩阵A共有95

个零元素，其相应的三元组表共有5个元素。

15.广义表的(c,a,(a,b),d,e,((i,j),k))深度是3。

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

7个记录65插入到有序表时，为寻找插入位置需比较3次。

17.循环队列在规定少用一个存储空间的情况下，队空的判定条件为front=rear。

18.一棵有5个叶结点的哈夫曼树，该树中总共有9个结点。

19.c语言中，字符串“E”存储时占2个字节。

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

所在结点为第1层)•

21.一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2,则该树共有n+1个

叶结点。

22.设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为32。

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

7个记录65插入到有序表时，为寻找插入位置需比较3次。

24.有以下程序段：

chara[]="English";

char*p=a;intn=0：

while(*p!='\0'){n++;p++;}

结果中，n的值是7。

25.设：chara[1="AEIJING";该字符串在计算机中存储时占8个字节。

26.栈的特点之一是：元素进、出栈的次序是：先进后出。

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

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

行下标，列下标，数组元素。

29.对稀疏矩阵进行压缩存储,可采用三元组表,一个有8行的稀疏矩阵A共有92个零元素，

其相应的三元组表共有4个元素。该矩阵A有12歹八

30.在对10个记录的序列(9,35,19,77,2,10,53,45,27,68)进行直接插入排序时，

当把第6个记录10插入到有序表时，为寻找插入位置，元素间需比较4次。(按升

序排序)

31.循环链队列中，设front和rear分别为队头和队尾指针，最大存储空间元素为MaxSize,

采用少用一个存储空间的模式，则判断循环链队列为空的条件是front=rear为真。

32.字符串al="beijing",a2="bef",a3="beifang",a4="befi"最小的是a2。

33.n个元素进行冒泡法排序，第j趟冒泡要进行n-j次元素间的比较。

34.10个元素进行冒泡法排序，其中第5趟冒泡共需要进行5次元素间的比较。

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

所在结点为第1层)

36.中序遍历一棵二叉排序树可得到一个有序序列

37.中序遍历一棵二叉排序树树可得到一个有序序列。

38.广义表(c,(a,b,c),(d,e,f),((i,j),k))的长度是4。

39.待排序的序列为9,4,5,1,2,6,10,采用直接选择排序算法，当进行了两趟选择后,

结果序列为。

40.广义表的(c,(b,a,b),f,e,((i,j),k))深度是3。

41.广义表((a,b),d,e,((i,j),k))的长度是4。

42.序列4,2,5,3,8,6,采用冒泡排序算法(升序)，经一趟冒泡后，结果序列是

2,4,3,5,6,8。

43.广义表的(c,a,(a,b),d,e,((i,j),k))深度是3。

44.待排序的序列为8,3,4,1,2,5,9,采用直接选择排序算法，当进行了两趟选择后，

结果序列为1,2,4,8,3,5,9。

45.线性表用顺序方式存储需要占用连续的存储空间。

46.线性表用顺序方式存储可以随机访问。

47.线性表用关键字有序的顺序方式存储,可以用二分法排序。

48.顺序表6,5,1,2,4,3,8,7经过一趟(1,1)归并后的结果序列为(5,6),(1,2),

(3,4),(7,8)。

三、综合题

1.有一个长度为11的有序表(1,2,11,15,24,28,30,56,69,70,80),元素的下

标依次为：1,2,3,……，11,按折半查找对该表进行查找。

(1)画出对上述查找表进行折半查找所对应的判定树。

(2)说出成功查找到元素56,需要依次经过与哪些元素的比较？

(3)说出不成功查找元素72,需要进行元素比较的次数？

(3)4次

2.(1)以3,4,5,8,9,作为叶结点的权，构造一棵哈夫曼树。

(2)给出相应权重值叶结点的哈夫曼编码。

(3)n个叶结点的哈夫曼树，总共有多少个结点？

(1)答：

(2)答：3:0004:0015:018:109:11

(3)2n-l

3.(1)一组记录的关键字序列为(57,90,67,50,51,56),利用堆排序(堆顶元素是

最小元素)的方法建立初始堆(要求以完全二叉树描述)。

(2)对关键字序列(56,51,71,54,46,106)利用快速排序，以第一个关键字为分割元

素，给出经过一次划分后结果。

(3)一组记录的关键字序列为(60,47,80,57,39,41,46,30),利用归并排序的方

法，分别给出(1,1)归并、(2,2)归并、(4,4)归并的结果序列。

(1)答:

(2)46,51,54,56,71,106

(3)(47,60)(57,80)(39,41)(30,46)

(47,57,60,80)(30,39,41,46)

(30,39,41,46,47,57,60,80)

4.(1)设有数据集合{40,29,7,73,101,4,55,2,81,92,39},依次取集合中各数

据构造一棵二叉排序树。

(2)在上述二叉排序树上进行查找，给出成功查找到元素92的查找路径，其中共经过了多

少次元素间的的比较。

(3)有一个长度为10的有序表，按折半查找对该表进行查找，给出在等概率情况下查找成

功的平均比较次数为。

(1)

(2)40,73,101,81,92.共5个元素比较。

(3)29/10

5.(1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树。

(2)给出相应权重值叶结点的哈夫曼编码。

(3)一组记录的关键字序列为(47,80,57,39,41,46),利用堆排序的方法建立的初

始堆(堆顶元素是最小元素，以树的形式给出)。

(1)

(2)2：0000

3：0001

4：001

7：10

8：11

9:01

(3)

6.(1)一组记录的关键字序列为(36,69,46,28,30,35),给出利用堆排序(堆顶元

素是最小元素)的方法建立的初始堆(要求以完全二叉树描述)。

(2)对关键字序列(36,69,46,28,30,74)采用快速排序，给出以第一个关键字为分

割元素，经过一次划分后的结果。

(3)设有数据集合｛30,73,101,4,8,9,2,81),依次取集合中各数据构造一棵二叉排

序树。

答：(1)28,30,35,69,36,46

(2)30,28,36,46,69,74

(3)

7.(1)已知某二叉树的后序遍历序列是debca,中序遍历序列是dbeac,试画出该二叉树。

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

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

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

(1)

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

(3)abdec

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

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

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

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

画4065433595

35406543困95

3540囤436595

354043囹6595

354043国6595

(1)

(2)404565433595

404345653595

354043456595

9.(1)设headl和pl分别是不带头结点的单向链表A的头指针和尾指针，head2和p2分

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

以headl为头指针的单向循环链表，写出其中两个关键的赋值语句(不用完整程序，结点的

链域为next)o

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

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

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

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

答：(1)pl->next=head2；p2->next=headl；

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

10.(1)设根为第1层，对给定权值1,3,4,4,5,6,构造深度为5的哈夫曼树。

提示：构造中当出现被选的结点值有多个相等时;可尝试不同组合，以得到要求的树的深度。

(2)求树的带权路径长度。

(3)用链接法存储上述哈夫曼树，结点中共有多少个指针域为空，说明理由？

(4)给出对上述哈夫曼树中序遍历得到的的序列。

(5)一棵哈夫曼树有n个非叶结点，构造该树共有多少个权重值？简述理由？

2

答：(1)

(2)WPL=l*4+3*4+4*3+6*2+4*2+5*2=58

(3)有12个空指针域，因为共11个结点，22个指针域，除根结点外，每个结点对应一个

指针域，共10个指域非空，故有22-10=12个空指针域。(针对哈夫曼树还可有其它理由)

(4)1,4,3,8,4,14,6,23,4,9,5

(5)n+1,因为叶结点比非叶结点多1,

四、程序填空

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

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

voidInorder(structBTreeNode*BT)

(

if(BT!=NULL)

(1)(norder(BT->left)；

(2)printfBT->data)；

Inorder(BT->right);

)

利用上述程序对下图进行遍历，结果是(3)dbfeac。

2.设线性表为(16,20,26,24),以不带头结点的单向链表存储，链表头指针为head,

以下程序的功能是输出链表中各结点中的数据域data。

structnode

(

intdata;

structnode*next;

)；

typedefstructnodeNODE;

#defineNULL0

voidmain()

NODE*head,*p;

p=head;/*p为工作指针*/

do

printf("炊l\n”,(1));

(2);

}while((3));

}

答:(1)p->data

(2)p=p->next

(3)p!=NULL

3.以下冒泡法程序对存放在a[l],a[2],……，a[n]中的序列进行排序，完成程序中的空

格部分，其中n是元素个数，要求按升序排列。

voidbsort(NODEa[],intn)

(

NODEtemp;

inti,j,flag;

for(j=l;(1);.j++)

(

flag=0;

for(i=l;(2);i++)

if(a[i].key>a[i+l],key)

(

flag=l;

temp=a[i];

(3);

(4);

)

if(flag==0)break;

)

)

设有序列6,4,5,8,2,1,给出由该程序经过两趟冒泡后的结果序列(5)。

答：⑴j<=n-l

(2)i<=n-j

(3)a[i]=a[i+l]

(4)a[i+l]=temp

(5)4,5,2,1,6,8

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

完成程序中的空格：

typedefstruct

(

intkey;

}NODE;

voidseisort(NODEa[],intn)

inti,j,k;

NODEtemp;

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

(

k=i;

for(j=i+l;K=⑵；j++)

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

if(i!=k)

(

temp=a[i];

(4);

(5);

)

)

)

答:(1)n-1

(2)n

(3)k=j

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

(5)a[k]=temp

5.设线性表为(1,3,7,5),以下程序用说明结构变量的方法建立单向链表，并输出链表

中各结点中的数据。

structnode

(

intdata;

structnode*next;

)

typedefstructnodeNODE;

#defineNULL0

Voidmain()

(

NODEa,b,c,d,*head,*p;

a.data=6;

b.data=10;

c.data=16;

c.data=4;/*d是尾结点*/

head=(1):

a.next=&b;

b.next二&c;

c.next=&d;

(2)/*以上结束建表过程*/

p二head;/*p为工作指针，准备输出链表*/

do

printf("%d\n〃，(3));

(4);

}while(p!=NULL);

)

画出按该程序建立的单向链表的示意图，说明程序运行结束后p的指向。⑸

答：(1)&a

(2)d->next=NULL

(3)p->data

(4)p=p->next

(5)P指向NULL

head

_►6_10_16_k4NULL

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

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

typedefstruct

(

intkey;

}N0DE;

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);

)

return-1;

)

设数组元素：a[0]=2；a[l]=5；a[2]=3；a[3]=4；a[4]=9；a[5]=6；a[6]=l；a[7]=10；按

上述程序查找元素5,能否成功查到，说明理由(5)。

答：(1)low<=high

(2)mid

(3)a[mid].key<k

(4)high=mid-l

(5)不能，因为不是有序序列，不能用折半查找。

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

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

voidInorder（structBTreeNode*BT）

if(BT!=NULL)

(

(1)；

Inorder(BT->right);

(2);

利用上述程序对下图进行遍历，结果是一（3）。

答：(1)Inorder(BT->left)

(2)printf('%c”,BT->data)

(3)f,d,e,b,c,a

8.以下函数为链队列的入队操作，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)malloc(sizeof(structnode))

(2)rear->next=p

(3)p

9,设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量,

P指向链表中某结点a(设链表中没有结点的数据域与结点a的数据域相同)，写出相关语

句：(1)使该单向链表成为单向循环链表；(2)删去a结点

q=p;x=p->data;

while(q->next!=NULL)q=q->next;

(1)；

q=p;p=p->next;

while(p->data!=x)

{

q二P；

(2);

)

(3);

答：(1)q->next=head

(2)p=p->next

(3)q->next=p->next

模拟练习题（一）

一、单项选择题（每小题2分，共30分）

1、单向链表所具备的特点是（C）。

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

C.插入删除不需要移动元素D.可以通过某结点的指针域访问其前驱结点

2、设有一个长度为18的顺序表，要在第6个元素之前插入一个元素（也就是插入元素作为

新表的第6个元素），则移动元素个数为（A）。

A.13B.5.C.12D.6

3、栈和队列的共同特点是（C）。

.A.都是先进后出B.都是先进先出C.都是线性结构D.元素都可以随机进出

4、元素1,3,5,7按顺序依次入队列，按该队列的出队序列进栈，该栈的可能输出序列是

（B）（进栈出栈可以交替进行）。

.A.5,1,3,7B.7,5,3,1C.7,5,1,3D.7.3,1,5

5、在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则对该队列进行出队

操作中并把结点的值保存在变量e中，其运算为e=ffdata；和（C）。

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

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

数组B中（数组下标从1开始），B数组共有45个元素，则该矩阵是（B）阶的

对称矩阵。

.A.11B.9.C.15D.10

7、下列是C语言中"abcd321ABCD”的子串的选项是（B）。

.A.abcDB."21ABC".C."abcABCD"D."321a”

8、字符串al="BEIJING",a2="BEF",a3="BEFANG",a4="BEFI"最小的是（D）。

.A.alB.a3C.a4D.a2

9、一棵有20个结点采用链式存储的二叉树中，共有（D）个指针域为空。

.A.18B.19C.20D.21

10、设一棵哈夫曼树共有18个叶结点，则该树有（C）个非叶结点。

A.16B.19C.17D.18

11、如下图所示的一个图，若从顶点g出发，按深度优先搜索法进行遍历，则可能得到的一

种顶点序列为（C）。

.A.gaebcfdB.gabecdfC.gaedfcb.D.gacfebd

12、线性表以（C）方式存储，能进行折半查找。

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

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

均比较次数为（D）。

.A.22/8B.20/8C.23/8D.21/8

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

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

.A.归并排序B.选择排序C折半插入排序D.直接插入排序

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

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

.A.快速B.选择.C.冒泡.D.堆

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

16、广义表（a,（a,b）,d,e,（（i,j）,k））的长度是5

17、广义表的（c,a,（a,b）,d,e,（（i,j）,k））深度是3

18、设顺序队列的类型为

typedefstruct

ElemTypedata[MaxSise];

intfront,rear;

}Squeue;

Squeue*sq;

sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教课书约定，可用语句

sq->data[sq->rear]=x;和sq->rear++.。

19、序列4,2,5,3,8,6,采用冒泡排序算法，经一趟冒泡后，序列的结果是2,4,3,5,6,8

（按由小到大顺序）

20、在对一组记录（50,34,92,19,11,68,56,41,79）进行直接插入排序（由小到大

排序），当把第7个记录56插入到有序表时，为寻找插入位置需比较3次。

21、数据结构中，数据元素可以由一个或多个数据项组成。

22、循环队列中，设front和rear分别为队头和队尾指针，（最多元素为MaxSize,采用

少用一个元素的模式），判断循环队列为满的条件为front==（rear+l）%MaxSize为

真。

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

进行比较，然后将其放入已排序序列的正确位置的方法是直接插入排序

24、对稀疏矩阵进行压缩存储，可采用三元组表，一个6行7列的稀疏矩阵A共有34个零

元素，其相应的三元组表共有8.个元素。

25、在双向链表中,要删除p所指的结点，可以先用语句（p->prior）->next=p->next；然

后再用语句（p->next）->prior=p->prior;。

26、在双向链表中，每个结点有两个指针域，一个指向结点的直接后继，另一个指向结点

的直接前驱。

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

三、综合题（每小题15分，共30分）

28、设数据集合a={l,12,5,8,3,10,7,13,9）

（1）依次取a中各数据，构造一棵二叉排序树。

（2）说明如何依据此二叉树得到a的有序序列。

（3）对该二叉树进行查找，成功查找到7要进行多少次元素间的比较？

（4）给出对该二叉树后序遍历的序列。

（5）画出在二叉树中删除12后的树结构（要求结点13的位置不变）。

答：⑴

(2)中序遍历1,3,5,7,8,9,10,12,13

(3)5次

(4)3,7,9,10,8,5,13,12,1

(5)

29、设有序表为(2,5,11,12,30,48,58,70,78,79,90),元素的序号依次为1,

2,3,...,11。

(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用序号表示)

(2)说明成功查找到元素2需要经过多少次比较？

(3)说明不成功查找元素75需要经过多少次比较？

(4)给出后序遍历该折半查找判定树的序列

(5)给出中序遍历该折半查找判定树的序列

答：⑴

(2)3次

(3)4次

(4)2,1,5,4,3,8,7,11,10,9,6(序号)

(5)1,2,3,4,5,6,1,8,9,10,11(序号)

四、程序填空题(每空2分，共16分)

30、设有一个不带头结点的单向链表，头指针为head,p、prep是指向结点类型的指针，该

链表在输入信息时不慎把相邻两个结点的信息重复输入，以下程序段是在该单向链表中查找

这相邻两个结点，把该结点的数据域data打印出来，并把其中之一从链表中删除，填写程

序中的空格。

prep=head;

p=prep->next;

while(p->data!=prep->data)

prep=p;

(1)

)

printf("min=%d”,(2));

prep->next=(3);

答：(1)p=p->next;

(2)p->data或prep->data

(3)p->next

31、以下程序是折半插入排序的算法(按记录中关键字key排序)设待排序的记录序列存放

在a[l],…，a[n]中，以a[0]作为辅助工作单元，以下程序是要把a[i]插入到已经有序

的序列a[l],…，中。

voidbinsort(NODEa[],intn)

(

intx,i,j,s,k,m;

for(i=2；i〈=(1);i++)

(

a[0]=a[i];

x=a[i].key;

s=l；

j=i-l：

while(s〈=j)

(

m=(2);

if(x<a[m].key)

(3);

else

(4)

)

for(k=i-l;k>=j+l;k—)

(5)=a[k];

a[j+l]=a[0];

)

)

答：⑴n

(2)(s+j)/2

(3)j=m-l

(4)s=m+l

(5)a[k+l]

模拟练习题（二）

一、单项选择题（每小题2分，共30分）

1、头指针为head的带头结点的单向链表为空的判定条件是（C）为真。

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

C.head->next=NULLD.head->next=NULL;

2、设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（B）o

.A.9B.24C.25.D.8

3、一个栈的进栈序列是2,4,6,8,10,则栈的不可能输出序列是（A）（进栈出栈可

以交替进行）。

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

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

4、一个队列的入队序列是a,b,c,d,按该队列的可能输出序列使各元素依次入栈，该栈

的可能输出序