广西大学《数据结构》期末复习题及参考答案

数据结构复习资料

超越高度

一.单选题（共23题,36.8分）

1堆排序属于下列哪一种排序算法？（）

A插入排序

B交换排序

C选择排序

D快速排序

正确答案：C

2下面有向图所表示的拓扑排序的结果序列是（）

B125634C516234D123456E521643

正确答案：B

3无向图中一个顶点的度是指图中（）。

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

B与该顶点连通的顶点数

C通过该顶点的回路数

D与该顶点相邻接的顶点数

正确答案：D

4树最适合表示（）

A有序数据元素

B无序数据元素

C元素之间具有层次关系

D元素之间关系任意

正确答案：C

5对n（n22）个权值均不同的字符构成哈夫曼树，关于该树的叙述中，错误的

是（）。

A该树一定是一棵完全二叉树

B该树中一定没有度为1的结点

C树中两个权值最小的结点一定是兄弟结点

D树中任一非叶子结点的权值一定不小于下一层任一结点的权值

正确答案：A

6已知一个有向图的邻接表存储结构如下图所示，根据深度优先遍历算法，从

顶点VI出发，所得到的顶点序列是（）

BV1,V2,V3,V5,V4CV1,V2,V3,V4,V5DV1,V3,V4,V5,V2EV1,V4,V3,V5,V2正

确答案：C

7非空循环单链表head的尾结点p满足（）。

Ap->next==NULL

Bp->next==head

Cp==NULL

Dp==head

正确答案：B

8假定一棵二叉树中，度为2的结点数位15,度为1的结点数为30,则叶子结

点有（）个。

A15B16C17D47

正确答案：B

9抽象数据类型的三个组成部分分别为（）。

A数据对象、数据关系和基本操作

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

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

D数据元素、数据结构和数据类型

正确答案：A

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

该图一定是（）

A完全图

B连通图

C有回路

D一棵树

正确答案：B

11下面（）可以判断出一个有向图是否有回路。

A广度优先遍历

B拓扑排序

C最短路径

D关键路径

正确答案：B

12下面（）算法适合用于构造一个稠密图的最小生成树。

ADijkstra算法

BPrim算法

CFIoyd算法

DKruskal算法

正确答案：B

13按照二叉树的定义，具有3个结点的二叉树有（）种。

A3B4C5D6

正确答案：C

14将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次

对结

A行编号，根结点的编号为1,则编号为49的结点的左孩子编号为（）。

B98C99D50E48

正确答案：A

15一个递增表为采用折半查找方法，在某次成功查找到指定的记录

时，以下（）是可能的记录比较序列。

AR[0]、R[5]、R[2]

BR[0]>R⑹、R[9]

CR[5]>R[8]、R[10]

DR[5]、R⑵、R[4]

正确答案：C

16循环链表的主要优点是（）

A在进行插入、删除操作运算时能保证链表不断开

B在表中任一结点出发都能扫描整个链表

C不再需要头指针

D已知某结点位置后能容易找到其直接前驱

正确答案：B

17在线性表的下列存储结构中，读取元素花费的时间最少的是（）。

A单链表

B双链表

C循环链表

D顺序表

正确答案：D

18在有向图的逆邻接表中，每个顶点邻接表链接这该顶点所有（）邻接点。

A入边

B出边

C入边和出边

D不是出边

正确答案：A

19串是（）。

A不少于一个字母的序列

B任意个字母的序列

C不少于一个字符的任意序列

D有限个字符的序列

正确答案：D

20若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一

个

A,则采用（）存储方式最节省运算时间。

B单链表

C双链表

D单循环链表

E带头结点的双循环链表

正确答案：D

21设图的邻接矩阵为，则该图为（）。

A有向图

B无向图

C强连通图

D完全图

正确答案：A

22栈的插入和删除操作在（）。

A栈底

B栈顶

C任意位置

D指定位置

正确答案：B

23一个顺序表的第一个元素的存储地址是10,每个元素的长度为2,则第5个

元素的地址是（）。

A14B16C18D20

正确答案：C

二.多选题（共13题,20.8分）

1下列说法正确的是（）

A从逻辑关系上，数据结构分为两大类：线性结构和非线性结构

B所谓数据的逻辑结构是指数据元素之间的逻辑关系

C数据的逻辑结构与数据元素本身的内容和形式无关

D数据结构是指相互之间存在一种或多种关系的数据元素的全体

正确答案：ABC

2完全二叉树（）

A适合于顺序结构存储

B不一定适合顺序结构存储

C叶子结点可在任一层出现

D某些结点有右子树，必然有左子树

正确答案：AD

3下面属于常用的表示树的链式结构的有（）

A双亲表示法

B孩子表示法

C孩子兄弟表示法

D父子表示法

正确答案：ABC

4数的表示方法有以下哪几种？（）

A直观表示法

B嵌套集合表示法

C凹入表示法

D广义表表示法

正确答案：ABCD

5以下说法正确的是（）

A数据元素是数据的最小单位

B数据结构是具有结构的数据对象

C数据结构是数据对象与对象数据元素之间关系的集合

D数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的

正确答案：CD

6（）二叉排序树不可以得到一个从小到大的有序序列

A先序遍历

B中序遍历

C后序遍历

D层次遍历

正确答案：ACD

7下列说法正确的是（）

A当队列中无数据元素时，称为空队列

B队列的特点是“先进后出”

C队列是一种操作不受限的线性表

D队列是一种只允许在一端进行插入和删除数据的线性表

正确答案：AD

8下列说法正确的是（）

A图结构中，各结点之间的关系可以是任意的

B树结构构中，各元素之间有明显的层次关系

C树结构中，数据元素之间仅有线性关系

D线性表中，数据元素之间仅有线性关系

正确答案：ABD

9下列和图结构有关的算法是（）

A克鲁斯卡尔算法

B哈夫曼算法

C迪杰斯特拉算法

D拓扑排序算法

正确答案：ACD

10以下说法中正确的是（）

A无向图中的极大连通子图称为连通分量

B连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点

C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D有向图的遍历不可采用广度优先搜索方法

正确答案：ABC

11下列哪一种数据结构适合于插入和删除操作？（）

A单链表

B顺序表

C双链表

D循环链表

正确答案：ACD

12数据元素之间存在着某种关系，这种数据元素相互之间的关系称为结构。根

据数据元素之间关系的不同特性，下面的选项中（）属于其基本结构。

A集合

B线性结构

C树结构

D图结构

正确答案：ABCD

13以下说法正确的是（）

A二叉树meige结点至多只有两棵子树

B二叉树的子树有左右之分

C二叉树只能采用链式存储

D树的结点包含一个数据元素及若干指向其子树的分支。

正确答案：ABD

三.填空题（共13题,20.8分）

1在一个图中，所有顶点的度之和等于边数的倍。

正确答案：2；

2具有100个结点的完全二叉树的深度为o

正确答案：7；

3数据结构算法中，通常用时间复杂度和两种方法衡量其效

率。

正确答案：空间复杂度；

4n个元素进行冒泡排序时，最少的比较次数是次。

正确答案：n-1；

5一棵二叉树中，度为零的结点个数为nO,度为2的结点个数为n2,则n0和

n2之间的关系为o

正确答案：n0=n2+l；

6带有头结点的单链表head为空的条件是。

正确答案：

head->

next=NULL；

7已知完全二叉树的第八层有8个结点，则其叶子结点数是o

正确答案：68；

8分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序

列的表按递增顺序排序，最省时间的是算法。

正确答案：插入排序；

9已知一棵度为4的树中，度为i（i>l）的结点个数有i个，则该树中有

_______________个叶子结点。

正确答案：21；

10在无向图G的邻接矩阵A中，若等于1,则等于。

正确答案：1;

11树的先根遍历序列与其对应的二叉树的相同。

正确答案：中序遍历序列；

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

Vi的O

正确答案：出度；

13在具有n个单元的循环队列中，队满时共有个元素。

正确答案：n-1；

四.简答题（共1题,1.6分）

1已知指针p指向双向链表中的一个结点（非首、非尾结点），则将指针s指向

结点插在p指向结点前的语句序列是：

正确答案：

p->prior->next；s

五.论述题（共6题,9.6分）

1将整数序列（4,5,7,2,1,3,6）中的元素依次插入，给出构造二叉查找

树的过程。

正确答案：

4

2设字符a,b,c,d,e的使用频度分别是0.25,0.3,0.12,0.08,0.25。试构造一课

Huffman树，求出其带权路径长度并给出a,b,c,d,e的Huffman(哈夫曼)编码。

正确答案：

解：Huffman树：

WPL=0.25*2+0.3*2+0.12*3+0.08*3+0.25*2=2.2编码分别为：a:10b:

01c:000d:001e:11

【评分说明】哈夫曼树建立正确5分，WPL正确2分，哈夫曼编码正确3分

3给定权集亚=(2,3,4,7,8,9),试构造关于W的一棵哈夫曼树，并求

其加权路径长度WPL及相应哈夫曼编码。

正确答案：

解：Huffman树：

33

其加权路径长度为：

WPL==7*2+8*2+*9*2+4*3+2*4+3*4=80哈夫曼编码：

2:00003:00014:0019:017:108:11【评分说明】哈夫曼树建立正确5

分，WPL正确2分，哈夫曼编码正确3分

4已知图G的顶点数组和邻接矩阵如下：

A|B|C|D|E

[01101I

10100

11011

00101

[10110]

（1）画出该图；

（2）根据邻接矩阵写出该图的一种邻接表表示；

（3）根据邻接表表示给出从顶点A出发的深度优先和广度优先搜索遍历序

列。

正确答案：

解：（1）（1分）

（2）（5分）此问答案不唯一，每个链表后的结点顺序可以调换，比如A结点

后的1、2、4的顺序可以互换。

0

1

2

3

4

（3）深度优先搜索遍历序列为：ABCDE（2分）

广度优先搜索遍历序列为：ABCED（2分）

5已知图G如下，图示用克鲁斯卡尔算法构造最小生成树的过程。

正确答案：

构造最小生成树的过程如下:

6画出如下图所示无向图G对应的邻接矩阵和邻接表两种存储结构。

正确答案:

解答：

i110

1i101

A=1i111

10111

Lo111V

(a)(b)

【评分说明】(a)邻接矩阵5分,(b)邻接表5分。

六.其它(共4题,10.4分)

1设二叉树以二叉链表为存储结构，编写算法，求一棵给定二叉树的叶子结点

数目。

正确答案:

intleafNodes(BTNode*b)//I分

{if(b==NULL)return0;//2分

elseif(b->lchild==NULL&&b->rchild==NULL)return1;〃3分

elsereturnleatNodes(b->lchild)+leafNodes(b->rchild);//4分

}

2设二叉树T以二叉链表为存储结构，试编写算法shendu(bitreeT),求二叉

树T的深度。

正确答案：

解：

intshendu(bitreeT)1分

{if(!T)return0;2分

ld=shendu(T->lchild)1分

rd=shendu(T->rchild)；1分

if(ld>rd)d=ld+1;2分

elsed=rd+1;2分

returnd;1分

)

3已知某个带头结点单链表L,其结点数据递增有序，试编写算法：

voidinsert(LinkNode*&L,ElemTypex)

在链表L中插入值为x的结点，并保持链表有序性。

正确答案：

解：

voidListInsert(LinkNode*&L,ElemTypex)

{LinkNode*pre=L,*p;//2分

while(pre->next!=NULL&&pre->next->data<x)

pre=pre->next;//4分

p=(LinkNode*)malloc(sizeof(LinkNode));//I分

p->data=x;//1分

p->next=pre->next;

pre->next=p;//2分

}

4设线性表L中的数据元素递增有序，并以带头单链表作存储结构，试写一算

法Del_anx(Linklist&L,ElemTypex)删除表中所有值等于x的元素。

正确答案：

解：

StatusDel_allx(Linklist&L,ElemTypex)1分

p=L->next;q=L;2分

while(p)2分

{if(p->data==x){q->next=p->next;free(p);}3分

elseq=p;1分

p=q->next;1分

数据结构复习资料

一.单选题（共27题,43.2分）

1对n（n22）个权值均不同的字符构成哈夫曼树，关于该树的叙述中，错误的

是（）。

A该树一定是一棵完全二叉树

B该树中一定没有度为1的结点

C树中两个权值最小的结点一定是兄弟结点

D树中任一非叶子结点的权值一定不小于下一层任一结点的权值

正确答案：A

2若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一

个

A,则采用（）存储方式最节省运算时间。

B单链表

C双链表

D单循环链表

E带头结点的双循环链表

正确答案：D

3设G1=（V1,E1）和G2=（V2,E2）为两个图，如果，则称（）。

AG1是G2的子图

BG2是G1的子图

CG1是G2的连通分量

DG2是G1的连通分量

正确答案：A

4已知一个有向图的邻接表存储结构如下图所示，根据深度优先遍历算法，从

顶点VI出发，所得到的顶点序列是（）

BV1,V2,V3,V5,V4CV1,V2,V3,V4,V5DV1,V3,V4,V5,V2EV1,V4,V3,V5,V2正

确答案：C

5抽象数据类型的三个组成部分分别为（）。

A数据对象、数据关系和基本操作

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

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

D数据元素、数据结构和数据类型

正确答案：A

6队列的删除操作是在（）。

A队头

B队尾

C队中

D队列任意位置

正确答案：A

7树最适合表示（）

A有序数据元素

B无序数据元素

C元素之间具有层次关系

D元素之间关系任意

正确答案：C

8以下关于图的存储结构的叙述中正确的是（）。

A邻接矩阵占用的存储空间大小只与图中顶点数有关，而与边数无关

B邻接矩阵占用的存储空间大小只与图中边数有关，而与顶点数无关

C邻接表占用的存储空间大小只与图中顶点数有关，而与边数无关

D邻接表占用的存储空间大小只与图中边数有关，而与顶点数无关

正确答案：A

9设图的邻接矩阵为，则该图为（）。

A有向图

B无向图

C强连通图

D完全图

正确答案：A

10链表不具有的特点是（）。

A随机访问

B不必事先估计存储空间

C插人删除时不需移动元素

D所需的空间与线性表成正比

正确答案：A

11假定一棵二叉树中，度为2的结点数位15,度为1的结点数为30,则叶子结

点有（）个。

A15B16C17D47

正确答案：B

12二分查找法要求查找表中各元素的键值必须是（）排列。

A递增或递减

B递增

C递减

D无序

正确答案：A

13下面有向图所表示的拓扑排序的结果序列是（）

B125634C516234D123456E521643

正确答案：B

14栈的插入和删除操作在（）。

A栈底

B栈顶

C任意位置

D指定位置

正确答案：B

15一个顺序表的第一个元素的存储地址是10,每个元素的长度为2,则第5个

元素的地址是（）。

A14B16C18D20

正确答案：C

16一个队列的入队序列是1,2,3,4,则队列的输出序列是（）。

A4,3,2,lBl,2,3,4Cl,4,3,2D3,2,4,1

正确答案：B

17在有向图的逆邻接表中，每个顶点邻接表链接这该顶点所有（）邻接点。

A入边

B出边

C入边和出边

D不是出边

正确答案：A

18若某线性表最常用的操作是存取指定序号的元素和在最后位置进行插入和删

除运算，则利用（）存储方式最节省时间。

A顺序表

B双链表

C带头结点的单链表

D不带头结点的循环单链表

正确答案：A

19按照二叉树的定义，具有3个结点的二叉树有（）种。

A3B4C5D6

正确答案：C

20数据结构是（）。

A一种数据类型

B数据的存储结构

C一组性质相同的数据元素的集合

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

正确答案：D

21某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的先序遍历序

列是（）o

Adecab

Bdeabc

Ccedba

Dacbed

正确答案：c

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

A只有一棵

B有一棵或多棵

C一定有多棵

D可能不存在

正确答案：B

23有6个元素6,5,4,3,2,1按顺序入栈，则下列哪一个是合法的出栈序

列？（）

A543621B346521C453216D234156

正确答案：B

24循环链表的主要优点是（）

A在进行插入、删除操作运算时能保证链表不断开

B在表中任一结点出发都能扫描整个链表

C不再需要头指针

D已知某结点位置后能容易找到其直接前驱

正确答案：B

25邻接表是图的一种（）。

A顺序存储结构

B链式存储结构

C索引存储结构

D散列存储结构

正确答案：B

26下面（）算法适合用于构造一个稠密图的最小生成树。

ADijkstra算法

BPrim算法

CFloyd算法

DKruskal算法

正确答案：B

27下面（）可以判断出一个有向图是否有回路。

A广度优先遍历

B拓扑排序

C最短路径

D关键路径

正确答案：B

二.多选题（共13题,20.8分）

1下列说法正确的是（）

A当队列中无数据元素时，称为空队列

B队列的特点是“先进后出”

C队列是一种操作不受限的线性表

D队列是一种只允许在一端进行插入和删除数据的线性表

正确答案：AD

2下列关于线性表的描述正确的是（）

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

B线性表采用顺序存储必须占用一段连续的存储空间

C线性表采用链式存储可以分配不连续的存储空间

D线性表采用链式才能出便于插入和删除操作的实现

正确答案：BCD

3根据所哟数据成员之间的逻辑关系的不同个，数据结构分为（）

A非线性结构

B逻辑结构

C物理结构

D线性结构

正确答案：AD

4下列关于链式存储结构，哪一项是正确的？（）

A结点除自身外，还包括指针域，因此存储密度小于顺序存储结构

B逻辑上相邻的结点物理上不必邻接

C可以通过计算直接得到第i个结点的存储地址

D插入、删除操作方便，不必移动结点

正确答案：ABD

5下面叙述正确的是（）

A线性表在链式存储时，查找第i个元素的时间同i值无关

B线性表在链式存储时，查找第i个元素的时间同i值成正比

C线性表在顺序存储时，查找第i个元素的时间同i值无关

D线性表在顺序存储时，查找第i个元素的时间同i值程增比

正确答案：BC

6下列哪些是图的遍历算法？（）

A深度优先遍历

B广度优先遍历

C先根遍历

D后根遍历

正确答案：AB

7数的表示方法有以下哪几种？（）

A直观表示法

B嵌套集合表示法

C凹入表示法

D广义表表示法

正确答案：ABCD

8下列说法正确的是（）

A图结构中，各结点之间的关系可以是任意的

B树结构构中，各元素之间有明显的层次关系

C树结构中，数据元素之间仅有线性关系

D线性表中，数据元素之间仅有线性关系

正确答案：ABD

9完全二叉树（）

A适合于顺序结构存储

B不一定适合顺序结构存储

C叶子结点可在任一层出现

D某些结点有右子树，必然有左子树

正确答案：AD

10以下说法正确的是（）

A二叉树meige结点至多只有两棵子树

B二叉树的子树有左右之分

C二叉树只能采用链式存储

D树的结点包含一个数据元素及若干指向其子树的分支。

正确答案：ABD

11以下说法中正确的是（）

A无向图中的极大连通子图称为连通分量

B连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点

C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D有向图的遍历不可采用广度优先搜索方法

正确答案：ABC

12线性结构的特点是（）

A集合中必存在唯一的一个“第一元素”

B集中中必存在唯一的一个“最后元素”

C除最后元素外，具有唯一的后继

D除第一元素外，均有唯一的前驱

正确答案：ABCD

13下列哪一种数据结构适合于插入和删除操作？（）

A单链表

B顺序表

C双链表

D循环链表

正确答案：ACD

三.填空题（共11题,17.6分）

1已知完全二叉树的第八层有8个结点，则其叶子结点数是。

正确答案：68；

2哈希查找性能主要与3个因素有关，分别是：装填因子、所采用的哈希函

数、o

正确答案：解决冲突的方法；

3在有序表A［21］中，数据元素存储在A［l］到A［20］单元，采用二分查找算法

查找元素值等于AE12］的元素，所比较过的元素的下标依次为—、15、

120

正确答案：10;

4在无向图G的邻接矩阵A中，若等于1,则等于。

正确答案：1;

5在具有n个单元的循环队列中，队满时共有个元素。

正确答案：n-1；

6已知一棵度为4的树中，度为i(i>l)的结点个数有i个，则该树中有

_______________个叶子结点。

正确答案：21；

7带有头结点的单链表head为空的条件是o

正确答案：

head->

next=NULL；

8分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序

列的表按递增顺序排序，最省时间的是算法。

正确答案：插入排序；

9一棵二叉树中，度为零的结点个数为n0,度为2的结点个数为n2,则nO和

n2之间的关系为o

正确答案：n0=n2+l；

10具有100个结点的完全二叉树的深度为0

正确答案：7；

11在循环队列hq中(最多n个元素)，判断队列满的条件是o

正确答案：

hq->

front==（hq・>

rear+l）%n；

四.简答题（共1题,1.6分）

1已知指针p指向双向链表中的一个结点（非首、非尾结点），则将指针s指向

结点插在p指向结点前的语句序列是：

正确答案：p->prior->next；s

五.论述题（共6题,9.6分）

1给定权集亚=（2,3,4,7,8,9）,试构造关于W的一棵哈夫曼树，并求

其加权路径长度WPL及相应哈夫曼编码。

正确答案：

解：Huffman树：

其加权路径长度为:

WPL==7*2+8*2+*9*2+4*3+2*4+3*4=80哈夫曼编码：

2:00003:00014:0019:017:108:11【评分说明】哈夫曼树建立正确5

分，WPL正确2分，哈夫曼编码正确3分

2已知图G的顶点数组和邻接矩阵如下：

ABCL)E

01101

10100

11011

0010

0110

(1)画出该图;

(2)根据邻接矩阵写出该图的一种邻接表表示;

(3)根据邻接表表示给出从顶点A出发的深度优先和广度优先搜索遍历序

列。

正确答案:

解:

(2)(5分)此问答案不唯一，每个链表后的结点顺序可以调换，比如A结点

后的1、2、4的