习题六
一、用适当内容填空
1．数据结构是指具有【】、相互【】的数据集合。
2．数据结构主要研究数据的【逻辑结构】、数据的存储结构，以及【】。
3．数据之间有四种逻辑结构，分别是【】、线性、树形和图形。
4．根据数据结构中数据元素之间前件与后件关系的复杂程度，将数据的逻辑结构分为线性结构和【】。
5．在数据的存储结构中，不仅要存放各个数据元素，还要存放数据元素之间【】关系信息。数据的存储结构是逻辑结构在计算机存储器中的表示。
6．数据元素在计算机中通常有4种存储方式，即【】、链式、索引和散列。
7．顺序存储结构是指在内存中开辟一块【】的单元用于存放数据，逻辑上相邻的结点在物理位置上也邻接，结点之间的逻辑关系由存储单元的【】关系来体现。
8．在链式存储结构中，结点由两部分组成：一部分用于存放数据元素的值，称为【】；另一部分用于存放前件或后件的存储地址，称为【】。链式存储结构是通过指针反映出数据元素之间的逻辑关系。
9．算法的设计基于数据的【】，而算法的实现依赖于数据的【】。
10．一个算法应该具有的基本特征有【】、确定性、有穷性、输入性和输出性。
11．算法的复杂度有【】和【】。
12．栈是在表的同一端进行插入运算和删除运算的线性表。将允许进行插入运算和删除运算的一端称为【】，另一端称为【】。栈遵循先进后出或后进先出的原则。
13．队列是在一端进行插入运算，而在另一端进行删除运算的线性表。允许删除的一端称为【】，允许插入的一端称为【】。队列遵循先进先出或后进后出的原则。
14．所谓循环队列是将队列的存储空间想象成一个首尾【】的环状空间。
15．判断循环队列为满的条件是【】。
16．判断循环队列为空的条件是【】。
17．树是一种常用的【】结构，树结构中结点之间既具有分支关系又具有【】关系。
18．在树结构中，有且只有一个根结点，根结点有【】个前件，其他结点只有【】
个前件。结点的【】称为该结点的子结点，该结点是其子结点的双亲结点。将没有后件的结点称为【】。一个结点所拥有后件个数称为该结点的【】。
19．二叉树的遍历分为【】遍历、中序遍历和后序遍历。
20．先序遍历是先访问【】，然后遍历【】，最后再遍历【】。
21．中序遍历是先遍历【】，然后访问【】，最后再遍历【】。
22．后序遍历是先遍历【】，然后遍历【】，最后再访问【】。
23．二分查找法只适用于【】存储结构的线性表，且数据元素按数据值升序或降序排列。
二、从参考答案中选择一个最佳答案
1．数据在计算机存储器中的表示称为【】。
A．数据的逻辑结构B．数据的存储结构
C．数据的顺序结构D．数据的链式结构
2．根据数据结构中各元素之间前后件关系的复杂程度，将数据结构分成【】。
A．内部结构和外部结构B．线性结构和树型结构
C．线性结构和非线性结构D．图型结构和树型结构
3．关于链式存储结构，下列叙述中错误的是【】。
A．逻辑上相邻结点物理上不必邻接B．插入、删除操作方便，不用移动结点
C．便于随机存取D．花费的存储空间较顺序存储空间多
4．有关线性表的叙述错误的是【】。
A．线性表采用顺序存储，必须占用一片连续的内存单元
B．线性表采用链式存储，所占内存单元可以不连续
C．顺序表便于进行插入和删除操作
D．链表便于进行插入和删除操作
5．以下数据结构中，【】是非线性结构。
A．二叉树B．队列
C．栈D．线性链表
6．设变量front、rear分别指向队头和队尾，判断队列是否为空的条件是【】。A．front=0 B．front=1
C．front=rear D．front=rear=0
7．若进栈顺序是1、2、3、4，进栈和出栈可以穿插进行，则不可能的出栈序列是【】。
A．1,2,3,4 B．2,3,4,1
C．3,1,4,2 D．3,4,2,1
8．依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时队头元素是【】。
A．a B．b
C．c D．d
9．树型结构适合用来表示【】。
A．有序数据B．元素之间没有关系的数据
C．无序数据D．元素之间具有层次关系的数据
10．算法指的是【】。
A．计算机程序B．排序算法
C．查找算法D．解决问题的有限运算序列
11．一个深度为k的满二叉树的结点个数是【】。
A．2k B．2k-1
C．2k-1 D．2k+1-1
12．有关二叉树的叙述中正确的是【】。
A．二叉树的度一定为2 B．二叉树中任何一个结点的度都为2
C．一棵二叉树的度可以小于等于2 D．二叉树的深度一定为2
13．具有3个结点的二叉树有【】种。
A．3 B．4
C．5 D．6
14．含有16个结点二叉树的最小深度是【】。
A．3 B．4
C．5 D．6
15．在一棵非空二叉树的中序遍历序列中，根结点的右边【】。
A．只有左子树上的部分结点B．只有左子树上的所有结点
C．只有右子树上的部分结点D．只有右子树上的所有结点
16．如果一棵二叉树的后序遍历序列是DBECA，中序遍历序列是DBACE，则它的前序遍历序列是【】。
A．ACBED B．ABDCE
C．DECAB D．EDBAC
17．如果一棵二叉树的前序遍历序列是ABDFCEG，中序遍历序列是DFBACEG，则它的后序遍历序列是【】。
A．ACFKDBG B．GDBFKCA
C．KCFAGDB D．FDBGECA
18．在线性表（2，5，7，9，12，23，27，34，40，56，61）中，用顺序查找法查找数据15，所需的比较次数为【】。
A．1 B．4
C．6 D．11
19．设有一个已按各元素值排好序的线性表（表长度大于2），分别用顺序查找法和二分查
