数据结构第 1 页 中南大学现代远程教育课程考试（考试）复习题及参考答案
数 据 结 构
(使用教材：余腊生编著，人民邮电出版社出版，《数据结构—基于C++模板类的实现》
一、判断题
1． 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。 [ ]
2． 链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 [ ]
3． 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 [ ]
4． 通常递归的算法简单、易懂、容易编写，而且执行的效率也高。 [ ]
5． 一个广义表的表尾总是一个广义表。 [ ]
6． 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。 [ ]
7． 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。 [ ]
8． 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 [ ]
9． 直接选择排序是一种稳定的排序方法。 [ ]
10． 30、闭散列法通常比开散列法时间效率更高。 [ ]
11． 有n个结点的不同的二叉树有n!棵。 [ ]
第1页共4页 1 专升本《数据结构》
一、 （共75题，共150分)
1. 数据的基本单位是（)。 （2分）
A.数据元素 B。记录 C.数据对象 D。数据项
.标准答案：A
2. ()是数据的不可分割的最小单位。 (2分)
A.数据对象 B.数据元素 C。数据类型 D。数据项
。标准答案:D
3。 算法的空间复杂度是对算法（）的度量. （2分）
A。时间效率 B.空间效率 C。可读性 D。健壮性
。标准答案：B
4。 （）是限制了数据元素的内部结构仅为一个字符的线性表. (2分)
A.栈 B.队列 C。串 D。数组
.标准答案：B
5。 串的长度是指串中所含（）的个数。 （2分）
A.不同字符 B.不同字母 C。相同字符 D。所有字符
。标准答案：D
6. 采用带头结点双向链表存储的线性表,在删除一个元素时，需要修改指针（)次. (2分）
A.1 B。2 C。3 D.4
。标准答案:B
7。 线性表的顺序存储结构是一种（）的存储结构。 （2分）
A。顺序存取 B。随机存取 C。索引存取 D。Hash存取
。标准答案:B
8。 数组a［1.。m］采用顺序存储，a［1］和a［m］地址分别为1024和1150,每个元素占2字节，则m是（)。 （2分）
A。64 B.32 C.16 D.8
。标准答案：A
填空题（ 10 ＊ 1’ = 10' ）
一、概念题
2。2.当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。
2。3。当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。
2。6。带头结点的单链表L中只有一个元素结点的条件是L—〉Next->Next==Null。
3。6。循环队列的引入,目的是为了克服假溢出.
4。2。长度为0的字符串称为空串。
4。5.组成串的数据元素只能是字符。
4。8.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配 ，又称P为模式。
7.2。为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。
5.7。广义表的深度是广义表中括号的重数
7。8.有向图G可拓扑排序的判别条件是有无回路。
7.9。若要求一个稠密图的最小生成树，最好用Prim算法求解。
8。8. 直接定址法法构造的哈希函数肯定不会发生冲突。
9。2。排序算法所花费的时间，通常用在数据的比较和交换两大操作。
1。1。通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。
1。2.对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系 树形关系﹑图状关系四种。
1。3。存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种 。
1。4。抽象数据类型的定义仅取决于它的一组逻辑特性,而与存储结构无关，即不论其内部结构如何变化，只要它的
数学特性不变,都不影响其外部使用。
1。5.一个算法具有五大特性:有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。
2.8.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句:
s—〉prior= p—〉prior; s-〉next= p; p-〉prior- next= s； p-〉prior= s；。
《数据结构》第五章习题参考答案
一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打
“×”）
1、知道一颗树的先序序列和后序序列可唯一确定这颗树。( × )
2、二叉树的左右子树可任意交换。（ × ）
3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发
生改变。（ √ ）
4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。（ √
）
5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。( × )
6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。( √ )
7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ × ）
8、度为2的树就是二叉树。（ × ）
二、单项选择题
1．具有10个叶结点的二叉树中有（ B ）个度为2的结点。
A．8 B．9 C．10 D．11
2．树的后根遍历序列等同于该树对应的二叉树的( B )。
A. 先序序列 B. 中序序列 C. 后序序列
3、二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历：HFIEJKG 。
该二叉树根的右子树的根是：( C )
A. E B. F C. G D. H0
4、在下述结论中，正确的是（ D ）。
①具有n个结点的完全二叉树的深度k必为┌log2(n+1)┐； ②二叉树的度为2；③二叉
树的左右子树可任意交换；④一棵深度为k(k≥1)且有2k-1个结点的二叉树称为满二叉
树。A．①②③ B．②③④ C．①②④ D．①④
5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。
A．空或只有一个结点 B．完全二叉树C．二叉排序树 D．高度等于其结点数
三、填空题
1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为__2n____
个，其中___n-1_____个用于指向孩子结点，___n+1___个指针空闲着。2、一棵深度为k(k≥1)的满二叉树有_____2k-1______个叶子结点。
