1、由如图(a)所示的二叉树，回答以下问题：
（1）画出和其对应的顺序存储结构。
（2）画出a结点左子树对应的二叉链表。
（3）求其先序遍历序列、中序遍历序列和后序遍历序列。
（4）画出该二叉树对应的森林。
2、根据给定的图（b），求解下列问题：
（1）写出上图非带权图形式的邻接矩阵。（注：邻接矩阵为非带权图形式，以a---h为行和列的顺序）
（2）作出上图的邻接表。（注：邻接表中，每个顶点的单链表的表结点的邻接点域按递减顺序排列）
（3）根据（2）得出的邻接表，写出从d顶点出发的深度优先搜索遍历序列和广度优先搜索遍历序列。
（4）试用克鲁斯卡尔算法构造出图（b）所示图的一棵最小生成树（写出具体过程）。
3、有一份电文中，共使用八个字符：a,b,c,d,e,f,g,h,它们出现的频率依次为5,6,7,8,9,17,16,32,试画出对应的赫夫曼树，求出每个字符的赫夫曼编码。
i
k a
b
c
d e g h
j f a b
c d e
f g
h 1
1 1
1 2
2 2 2 2
3 4
1、（1）顺序存储结构为：
bt 1 2 3 4 5 6 7 8 9 10 11
结点 a b h c e g i d f
bt 12 13 14 15 16 17 18 19 20 21
结点 j k
（2）a结点左子树对应的二叉链表见下页。
（3） 先根序序列：abcdjefkhgi
中根序序列：jdcbfkeaghi
后根序序列：jdckfebgiha
（4） 对应的森林为：
2、
（1）邻接矩阵为： 0 1 1 0 0 0 0 0 （按a---h的顺序）
1 0 0 1 0 0 0 0
1 0 0 1 0 0 0 0
0 1 1 0 1 1 0 0
1
《数据结构》期末复习题及参考答案 - 第7章 图
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
注意：做复习题时，请结合阅读教材，钻研教材，参考课件
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
一、 选择题
1、以下数据结构中，哪种具有非线性结构？
A．栈 B．队列 C．双向链表 D．十字链表
2、下面关于图的存储的叙述中正确的是（ ）。
A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。
C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
3、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的
（ ）
A.先根遍历 B.中根遍历 C.后根遍历 D.按层次遍历
4、图的广度优先遍历算法类似于树的（ ）。
A. 中根遍历 B. 先根遍历
C. 后根遍历 D. 按层次遍历
5、设无向图的顶点个数为n，则该图最多有（ ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0
6、设有n个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
数据结构第 1 页 中南大学现代远程教育课程考试（考试）复习题及参考答案
数 据 结 构
(使用教材：余腊生编著，人民邮电出版社出版，《数据结构—基于C++模板类的实现》
一、判断题
1． 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。 [ ]
2． 链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 [ ]
3． 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 [ ]
4． 通常递归的算法简单、易懂、容易编写，而且执行的效率也高。 [ ]
5． 一个广义表的表尾总是一个广义表。 [ ]
6． 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。 [ ]
7． 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。 [ ]
8． 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 [ ]
9． 直接选择排序是一种稳定的排序方法。 [ ]
10． 30、闭散列法通常比开散列法时间效率更高。 [ ]
11． 有n个结点的不同的二叉树有n!棵。 [ ]
数据结构强化习题课汇总复习过程
数据结构强化习题课
汇总
第⼀章绪论
考点1 数据结构基础知识1.数据的逻辑结构是指（），数据的存储结构是指（）
分析：数据结构包括三⽅⾯的内容：数据的逻辑结构、存储结构和数据的运算。其中，逻辑结构是指各数据元素之间的逻辑关系，存储结构是
指逻辑结构⽤计算机语⾔的实现。
解答：数据元素之间的逻辑关系；数据的逻辑结构⽤计算机语⾔的实现。2.在数据结构中，从逻辑上可以把数据结构分为：（A）
A 线性和⾮线性结构
B 紧凑和⾮紧凑结构
C 动态和静态结构
D 内部和外部结构
分析：数据结构中，逻辑上可以把数据结构分成线性结构和⾮线性结构。
线性结构的顺序存储结构是⼀种随机存取的存储结构，线性表的链式
存储结构是⼀种顺序存储结构。线性表若采⽤链式存储表⽰时，所有
结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本⾝
的形式、内容、相对位置、所含结点个数⽆关。
关键考点点评：线性结构的特征，有且仅有⼀个开始结点和终端结点，所有结点最多只有⼀个直接前驱和后继。栈和队列。⾮线性结构的结点
有多个前驱或后继，树和图。3.数据结构在物理上可以分为（）存储结构和链式存储结构。
分析：物理存储
解答：顺序4.下列术语中，（）与数据的存储结构⽆关
A 循环队列
B 堆栈
C 散列表
D 单链表
解答： A5.（）不是算法所必须具备的特性
A 有穷性
B 确定性
C ⾼效性D 可⾏性
分析：算法的五个重要特征：有穷性、确定性、可⾏性、输⼊和输
出。
解答：C
考点2 时间复杂度计算1.设n是描述问题规模的⾮负整数，下⾯程序段的时间复杂度是（）2.
第⼆章线性表
考点1 线性表的基本概念1.线性表是n个（）的有限序列。
A 字符 B数据元素 C 由数据项 D 信息项解析：
解答 B2.线性表是⼀个（）。A 有限序列，可以为空
B 有限序列，不能为空
C ⽆限序列，可以为空
D ⽆限序列，不能为空
解答 A
关键考点点评：
对于⾮空线性表1.有且仅有⼀个开始结点，没有直接前驱，有且仅有⼀个直接后
