西大成人教育数据结构期末考试复习题及参考答案

数据结构一.单选题（共27题,43.2分）1对n（n≥2）个权值均不同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。

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已知一个有向图的邻接表存储结构如下图所示，根据深度优先遍历算法，从顶点V1出发，所得到的顶点序列是（）ABV1,V2,V3,V5,V4

CV1,V2,V3,V4,V5

DV1,V3,V4,V5,V2

EV1,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，则叶子结点有（）个。

A15

B16

C17

D47正确答案：B

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

A递增或递减

B递增

C递减

D无序正确答案：A

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

AB125634

C516234

D123456

E521643正确答案：B

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

A栈底

B栈顶

C任意位置

D指定位置正确答案：B

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

A14

B16

C18

D20正确答案：C

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

A4,3,2,1

Bl,2,3,4

C1,4,3,2

D3,2,4,1正确答案：B

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

A入边

B出边

C入边和出边

D不是出边正确答案：A

18若某线性表最常用的操作是存取指定序号的元素和在最后位置进行插入和删除运算，则利用（）存储方式最节省时间。

A顺序表

B双链表

C带头结点的单链表

D不带头结点的循环单链表正确答案：A

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

A3

B4

C5

D6正确答案：C

20数据结构是（）。

A一种数据类型

B数据的存储结构

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

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

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

）。

Adecab

Bdeabc

Ccedba

Dacbed正确答案：C

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

A只有一棵

B有一棵或多棵

C一定有多棵

D可能不存在正确答案：B

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

A543621

B346521

C453216

D234156正确答案：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个因素有关，分别是：装填因子、所采用的哈希函数、_______________________________。正确答案：第一空：解决冲突的方法；3在有序表A［21］中，数据元素存储在A[1]到A[20]单元，采用二分查找算法查找元素值等于A［12］的元素，所比较过的元素的下标依次为____、15、12。正确答案：第一空：10；4在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于

。正确答案：第一空：1；5在具有n个单元的循环队列中，队满时共有________________个元素。正确答案：第一空：n-1；6已知一棵度为4的树中，度为i（i>1）的结点个数有i个，则该树中有_______________个叶子结点。正确答案：第一空：21；7带有头结点的单链表head为空的条件是_________

。第一空：正确答案：第一空：head->第二空：next=NULL；8分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是______________算法。正确答案：第一空：插入排序；9一棵二叉树中，度为零的结点个数为n0，度为2的结点个数为n2，则n0和n2之间的关系为_________。正确答案：第一空：n0=n2+1；10具有100个结点的完全二叉树的深度为____________。正确答案：第一空：7；11在循环队列hq中（最多n个元素），判断队列满的条件是_________

。正确答案：第一空：hq->第二空：front==(hq->第三空：

rear+1)%n；四.简答题（共1题,1.6分）1已知指针p指向双向链表中的一个结点（非首、非尾结点），则将指针s指向结点插在p指向结点前的语句序列是：正确答案：p->prior->next；s五.论述题（共6题,9.6分）1给定权集W＝（2，3，4，7，8，9），试构造关于W的一棵哈夫曼树，并求其加权路径长度WPL及相应哈夫曼编码。正确答案：解：Huffman树：

其加权路径长度为：WPL＝＝7*2＋8*2＋*9*2＋4*3＋2*4＋3*4＝80哈夫曼编码：2:0000

3:0001

4:001

9:01

7:10

8:11【评分说明】哈夫曼树建立正确5分，WPL正确2分，哈夫曼编码正确3分2已知图G的顶点数组和邻接矩阵如下：（1）画出该图；（2）根据邻接矩阵写出该图的一种邻接表表示；（3）根据邻接表表示给出从顶点A出发的深度优先和广度优先搜索遍历序列。正确答案：解：（1）（1分）

（2）（5分）此问答案不唯一，每个链表后的结点顺序可以调换，比如A结点后的1、2、4的顺序可以互换。（3）深度优先搜索遍历序列为：ABCDE

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

（2分）3画出如下图所示无向图G对应的邻接矩阵和邻接表两种存储结构。正确答案：解答：

（a）

（b）【评分说明】（a）邻接矩阵5分，（b）邻接表5分。4已知图G如下，图示用克鲁斯卡尔算法构造最小生成树的过程。正确答案：构造最小生成树的过程如下：5依次输入关键字：{17，26，35，10，8，15，18，20，12}，给出构造二叉查找树的过程。正确答案：6设字符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:10

b:01

c:000

d:001

e:11【评分说明】哈夫曼树建立正确5分，WPL正确2分，哈夫曼编码正确3分六.其它（共2题,7.2分）1已知某个带头结点单链表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));

//1分

p->data=x;

//1分

p->next=pre->next;

pre->next=p;

//2分}2设线性表L中的数据元素递增有序，并以带头单链表作存储结构，试写一算法Del_allx(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分

}

}数据结构 

一.单选题（共24题,38.4分）1堆排序属于下列哪一种排序算法？（）

A插入排序

B交换排序

C选择排序

D快速排序正确答案：C

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

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

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

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

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

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

A只有一棵

B有一棵或多棵

C一定有多棵

D可能不存在正确答案：B

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

A单链表

B双链表

C循环链表

D顺序表正确答案：D

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

A随机访问

B不必事先估计存储空间

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

D所需的空间与线性表成正比正确答案：A

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

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

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

C不再需要头指针

D已知某结点位置后能容易找到其直接前驱正确答案：B

7若某线性表最常用的操作是存取指定序号的元素和在最后位置进行插入和删除运算，则利用（）存储方式最节省时间。

A顺序表

B双链表

C带头结点的单链表

D不带头结点的循环单链表正确答案：A

8一个顺序表的第一个元素的存储地址是10，每个元素的长度为2，则第5个元素的地址是（）。

A14

B16

C18

D20正确答案：C

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

A3

B4

C5

D6正确答案：C

10数据结构是（）。

A一种数据类型

B数据的存储结构

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

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

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

A543621

B346521

C453216

D234156正确答案：B

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

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

B单链表

C双链表

D单循环链表

E带头结点的双循环链表正确答案：D

13一棵高度为h（h≥1）的完全二叉树至少有（）个结点。

A2h-1

B2h

C2h+1

D2h-1+1正确答案：A

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

A完全图

B连通图

C有回路

D一棵树正确答案：B

15用顺序存储的方法，将完全二叉树种所有结点按层次逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（）。

AR[2i-1]

BR[2i]

CR[2i+1]

DR[i/2]正确答案：C

16链表不具备的特点是（）。

A插入和删除操作不需要移动元素

B不必事先估计存储空间

C可随机访问任一元素

D所需空间与线性表长度成正比正确答案：C

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

A广度优先遍历

B拓扑排序

C最短路径

D关键路径正确答案：B

18假定一棵二叉树中，度为2的结点数位15，度为1的结点数为30，则叶子结点有（）个。

A15

B16

C17

D47正确答案：B

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

Ap->next==NULL

Bp->next==head

Cp==NULL

Dp==head正确答案：B

20一个递增表为R[0..11]，采用折半查找方法，在某次成功查找到指定的记录时，以下（）是可能的记录比较序列。

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

BR[0]、R[6]、R[9]

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

DR[5]、R[2]、R[4]正确答案：C

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

A栈底

B栈顶

C任意位置

D指定位置正确答案：B

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

A队头

B队尾

C队中

D队列任意位置正确答案：A

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

A4,3,2,1

Bl,2,3,4

C1,4,3,2

D3,2,4,1正确答案：B

24串是（）。

A不少于一个字母的序列

B任意个字母的序列

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

D有限个字符的序列正确答案：D

二.多选题（共14题,22.4分）1以下说法正确的是（）

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

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

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

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

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

A深度优先遍历

B广度优先遍历

C先根遍历

D后根遍历正确答案：AB

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

A克鲁斯卡尔算法

B哈夫曼算法

C迪杰斯特拉算法

D拓扑排序算法正确答案：ACD

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

A双亲表示法

B孩子表示法

C孩子兄弟表示法

D父子表示法正确答案：ABC

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

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

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

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

D插入、删除操作方便，不必移动结点正确答案：ABD

6数据元素之间存在着某种关系，这种数据元素相互之间的关系称为结构。根据数据元素之间关系的不同特性，下面的选项中（）属于其基本结构。

A集合

B线性结构

C树结构

D图结构正确答案：ABCD

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

A非线性结构

B逻辑结构

C物理结构

D线性结构正确答案：AD

8下列说法正确的是（）

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

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

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

D线性表中，数据元素之间仅有线性关系正确答案：ABD

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

A单链表

B顺序表

C双链表

D循环链表正确答案：ACD

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

A直观表示法

B嵌套集合表示法

C凹入表示法

D广义表表示法正确答案：ABCD

11以下说法正确的是（）

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

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

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

D树的结点包含一个数据元素及若干指向其子树的分支。正确答案：ABD

12线性结构的特点是（）

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

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

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

D除第一元素外，均有唯一的前驱正确答案：ABCD

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

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

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

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

D有向图的遍历不可采用广度优先搜索方法正确答案：ABC

14下列说法正确的是（）

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

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

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

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

三.填空题（共13题,20.8分）1在具有n个单元的循环队列中，队满时共有________________个元素。正确答案：第一空：n-1；2一棵二叉树中，度为零的结点个数为n0，度为2的结点个数为n2，则n0和n2之间的关系为_________。正确答案：第一空：n0=n2+1；3若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为定点Vi的_________。正确答案：第一空：出度；4在循环队列hq中（最多n个元素），判断队列满的条件是_________

。正确答案：第一空：hq->第二空：front==(hq->第三空：

rear+1)%n；5一棵有n个叶子结点的哈夫曼树共有_______个结点。正确答案：第一空：2n-1；6已知一棵度为4的树中，度为i（i>1）的结点个数有i个，则该树中有_______________个叶子结点。正确答案：第一空：21；7具有100个结点的完全二叉树的深度为____________。正确答案：第一空：7；8在有序表A［21］中，数据元素存储在A[1]到A[20]单元，采用二分查找算法查找元素值等于A［12］的元素，所比较过的元素的下标依次为____、15、12。正确答案：第一空：10；9在一个图中，所有顶点的度之和等于边数的_______倍。正确答案：第一空：2；10在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动_____个元素。正确答案：第一空：n-i+1；11在单链表中，删除指针P所指结点的后继结点的语句是___________________。正确答案：第一空：P->第二空：next=P->第三空：

next->第四空：

next；12带有头结点的单链表head为空的条件是_________

。正确答案：第一空：head->第二空：next=NULL；13在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于

。正确答案：第一空：1；四.简答题（共1题,1.6分）1已知指针p指向双向链表中的一个结点（非首、非尾结点），则将指针s指向结点插在p指向结点前的语句序列是：正确答案：p->prior->next；s五.论述题（共5题,8.0分）1已知图G如下，图示用克鲁斯卡尔算法构造最小生成树的过程。正确答案：构造最小生成树的过程如下：2依次输入关键字：{17，26，35，10，8，15，18，20，12}，给出构造二叉查找树的过程。正确答案：3画出如下图所示无向图G对应的邻接矩阵和邻接表两种存储结构。正确答案：解答：

（a）

（b）【评分说明】（a）邻接矩阵5分，（b）邻接表5分。4给定权集W＝（2，3，4，7，8，9），试构造关于W的一棵哈夫曼树，并求其加权路径长度WPL及相应哈夫曼编码。正确答案：解：Huffman树：

其加权路径长度为：WPL＝＝7*2＋8*2＋*9*2＋4*3＋2*4＋3*4＝80哈夫曼编码：2:0000

3:0001

4:001

9:01

7:10

8:11【评分说明】哈夫曼树建立正确5分，WPL正确2分，哈夫曼编码正确3分5将整数序列（4，5，7，2，1，3，6）中的元素依次插入，给出构造二叉查找树的过