A.iB.n-iC.n-i+1D.不确定
25）向一个栈顶指针为HS的链式栈中插入一个s所指的结点时，则执行
（）
A.HS->next=s;B.s->next=HS->next;HS->next=s;
C.s->next=HS;HS=s;D.s->next=HS;HS=HS->next;
26）设栈S的初始状态为空，6个元素入栈的顺序为1,2,3,4,5,6。
若出栈的顺序是2,4,3,6,5,1,则栈S的容量至少应该是（）
A.6B.4C.3D.2
27）为了减少栈溢出的可能性，可以让两个栈共享一片连续存储空间，两个栈的
栈底分别设在这片空间的两端，这样只有当寸才可能产生上溢。
（）
A.两个栈的栈顶在栈空间的某一位置相遇
B.其中一个栈的栈顶到达栈空间的中心点
C.两个栈的栈顶同时到达栈空间的中心点
D.两个栈均不空，且一个栈的栈顶到边另一栈的栈底
28）
下列关于栈的叙述中正确的是
。
（）
A.在栈中只能插入数据B.
在栈中只能删除数据
C.栈是先进先出的线性表D
栈是先进后出的线性表
29）
下列关于队列的叙述中正确的是
。
（）
A.在队列中只能插入数据
B.
在队列中只能删除数据
C.队列是先进先出的线性表
D.
队列是先进后出的线性表
30）
栈和队列的共同点是。
（
）
A.都是先进后出
B.都是先进先出
C.只允许在端点处插入和删除兀素
D.没有共同点
31）对线性表，下列情况下应当采用链表表示的是（）
A.经常需要随机地存取元素B.经常需要进行插入和删
除操作
C.表中元素需要占据一片连续的存储空间D.表中元素个数不变
32）在一个链式队列中，假设f和r分别为队头与队尾指针，则删除结点的运算是（）
A.r=f->nextB.r=r->nextC.f=f->nextD.
f=r->next
33）设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为<
（）
A.349B.350C.255D.351
34）若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是
dgbaechf，则其后序遍历的结点访问顺序是（）
A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca
35）设树T的度为4,其中度为1,2,3,4的结点个数分别为4,2,1,1。
则T中的
叶子结点数为（）
A.8B.7C.6D.5
36）树最适合用来表示（）
A.有序数据元素B.无序数据元素
C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
37）某二叉树的先序和后序遍历顺序正好相反，则该二叉树一定是（）
n在m之前的条件是
a
深度等于其结点数
38）设n，m为一棵二叉树上的两个结点，在中序遍历中,
（）
A.n在m右子树上B.n是m的祖先
C.n在m左子树上D.n是m的子孙
39）如图所示二叉树的中序遍历序列是（）
A.abcdgefB.dfebagc
C.dbaefcgD.abcdefg
40）树是结点的集合，它的根结点数目是（）
A.有且只有1B.1或多于1C.0或1D.
41）在一棵二叉树上第5层的结点数最多是0（）
A.8B.16C.32D.1542）对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为
0（）
A.N+1B.NC.（N+1）/2D.N/2
43）顺序查找适合于存储结构为的线性表（）
A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存
储
44）采用顺序法查找长度为n的线性表时，每个元素的平均查找长度为
（）
A.nB.n/2C.（n+1）/2D.（n-1）/2
45）希尔排序法属于哪一种类型的排序法。
（）
A.交换类排序法B.插入类排序法C.选择类排序法D.建堆排序法
46）在待排序的兀素序列基本有序的前提下，效率最高的排序方法是（）
A.冒泡排序B.选择排序C.快速排序D.归并排序
47）设有1000个元素，希望用最快的速度选出其中前10个最大的元素，最好选用卡序法。
（）
A.冒泡B.快速C.堆D.选择
48）在下列排序法中，法可能出现下列情况：
在最后一趟开始之间，所
有的元素都不在其最终位置上。
（）
A.冒泡B.快速C.插入D.堆
49）在下列几种排序方法中，要求内存量最大的是。
（）
A.插入排序B.选择排序C.快速排序D.归并排序
50）已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是
。
（）
A.堆排序B.直接插入排序C.快速排序D.直接选择排序
9.2填空题
1）算法的复杂度主要包括复杂度和空间复杂度。
2）现有按中序遍历二叉树的结果为abc，那么有种不同形态的二叉树可以得到这一遍历结果。
3）若要对1000个元素排序，要求即快又节省空间，则最好采用方法。
4）在平均情况下速度最快的排序方法为排序。
5）有关键码序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按关键码递增顺
序排序。
采用冒泡排序法，则第二趟冒泡后的结果
为
6）有关键码序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按关键码递增顺
序排序。
采用初始增量为4的希尔排序，则一趟扫描后的结果为。
7）假定一组记录为（46,79,56,38,40,80）对其进行快速排序的过程中，共需
要趟排序。
8）假定一组记录为（46,79,56,38,40,80）对其进行快速排序的第一次划分结
果为。
9）对任意7个关键字进行排序，至少要进行次关键字之间的两两比较。
10）算法的基本特征是可行性、确定性、__和拥有足够的情报。
11）顺序存储方法是把逻辑上相邻的结点存储在物理位置的存储单元
12）数据的逻辑结构在计算机存储空间中的存放形式称为数据的
13）栈的基本运算有三种：
入栈、退栈和。
14）如图所示的二叉树，其中序遍历序列是；
前序遍历序歹U是;后序遍历序歹U是
15）设一棵完全二叉树共有499个结点，则在该二叉树中有__个叶子结点。
16）在最坏情况下，冒泡排序的时间复杂度为。
17）在最坏情况下，堆排序需要比较的次数为
18）在计算机中，可以采用结构来表示算术表达式
19）具有90个结点的完全二叉树的深度为
20）对具有n个元素的任意序列进行排序，在最坏情况下，采用简单排序法时需要次比较；采用希尔排序法进行排序时，时间复杂度
为;采用简单排序法进行排序时，需要比较次；采
用堆排序法进行排序时需要比较的次数为。
1）算法的复杂度主要包括复杂度和空间复杂度。
2）现有按中序遍历二叉树的结果为abc，那么有种不同形态的二叉树可以得到这一遍历结果。
3）若要对1000个元素排序，要求即快又节省空间，则最好采用方法。
4）在平均情况下速度最快的排序方法为排序。
5）有关键码序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按关键码递增顺
序排序。
采用冒泡排序法，则第二趟冒泡后的结果
为。
6）有关键码序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按关键码递增顺
序排序。
采用初始增量为4的希尔排序，则一趟扫描后的结果
为。
7）假定一组记录为（46,79,56,38,40,80）对其进行快速排序的过程中，共需
要趟排序。
8）假定一组记录为（46,79,56,38,40,80）对其进行快速排序的第一次划分结
果为。
9）对任意7个关键字进行排序，至少要进行次关键字之间的两两比较。
10）算法的基本特征是可行性、确定性、___和拥有足够的情报。
11）顺序存储方法是把逻辑上相邻的结点存储在物理位置___的存储单元中。
O
12）数据的逻辑结构在计算机存储空间中的存放形式称为数据的
13）栈的基本运算有三种：
入栈、退栈和。
14）如图所示的二叉树，其中序遍历序列是；
前序遍历序歹U是;后序遍历序歹U是
15）设一棵完全二叉树共有499个结点，则在该二叉树中有个叶
子结点。
16）在最坏情况下，冒泡排序的时间复杂度为___。
17）在最坏情况下，堆排序需要比较的次数为____。
18）在计算机中，可以采用结构来表示算术表达式。
19）具有90个结点的完全二叉树的深度为。
20）对具有n个元素的任意序列进行排序，在最坏情况下，采用简单排序法时需
要次比较；采用希尔排序法进行排序时，时间复杂度
为;采用简单排序法进行排序时，需要比较次；采
用堆排序法进行排序时需要比较的次数为。
1-5CCDBD6-10CDCCD11-15BADAB16-20CAADC21-25CCBCC
26-30CADCC31-35BCBDA36-40CDCBA41-45BBBCB46-50ACCDB
1）时间
2）5
3）堆排序
4）快速
5）4,9,15,2,13,16,17,5,8,18,24,25
6）15,2,4,18,16,5,8,24,17,9,13,25
7）3
8）40,38,46,56,79,80
9）15
题解：
Iog2（n!
）=Iog2（7!
）
10）
有穷性
11）
相邻
12）
模式（逻辑模式）（概念模式）
13）
读栈顶元素
14）dgbaechif,abdgcefhi,gdbeihfca
15）250_
16）n（n-1）/2或O（n（n-1）/2）
17）O（nlog2n）
18）树型
19）7
20）n（n-1）/2,O（n1.5）,n（n-1）/2,O（nlog2n）
升级会员 