期末复习练习题(含答案)

第6章
考试范围：6.1、6.2、6.3、6.6
重点：P133 图6.12
第7章
考试范围：7.1、7.2（只考7.2.1 数组表示法和7.2.2 邻接表）、7.3（图
的深度、广度优先搜索遍历是必考的）、7.4（只考7.4.3，普里姆和克
鲁斯卡尔两种算法生成图的最小生成树）、7.6（只考7.6.1，迪杰斯特
拉算法求的从某个源点到其余各顶点的最短路径，P190的表要说清
楚）
第9章
考点：顺序表的查找、折半查找（重点，要懂得画折半查找过程的判
定树，P220 图9.2一定要掌握！）、平均查找长度ASL、索引顺序表
的查找、二叉排序树、哈希表（不作为重点）
第10章
考点：直接插入排序、希尔排序、起泡排序、快速排序、简单选择排
序

练习1
1、树转成二叉树后，二叉树的根结点没有( A )：
A、右子树 B、左子树 C、前驱 D、后继
2、一个队列的出队序列是1 2 3 4，则队列的入队序列是( B )。
A、4 3 2 1 B、1 2 3 4 C、1 4 3 2 D、3 2 4 1
3、对稀疏矩阵进行压缩存储是为了( C )。
A、便于进行矩阵运算 B、便于输入和输出
C、节约存储空间 D、降低运算的时间复杂度
4、设计一个判别表达式中左、右括号是否配对出现的算法，采用( B )数据结
构最佳。
A、线性表的顺序存储结构 B、栈
C、队列 D、线性表的链式存储结构
5、含有n个结点的三叉链表中空链域个数是（ D ）。
A、n-1 B、n+1 C、2n-1 D、n+2
6、对含有n个记录的表进行顺序查找，设表中每个元素的查找概率相等，则ASL
为( A )。
A、(n+1)/2 B、n/2 C、(n-1)/2 D、n/2 +1
7、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为
第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为( B )。
A、13 B、33 C、18 D、40
8、下面无向图的广度优先搜索遍历所得顶点序列错误的是 ( A )。

A、123456 B、126543 C、156243 D、126543
9、队列与一般的线性表的区别在于( C )。
A、数据元素的类型不同 B、 数据元素的个数不同
C、运算是否受限制 D、逻辑结构不同
10、在顺序表中，只要知道( D )，就可在相同时间内求出任一结点的存储地址。
A、基地址 B、结点大小
C、向量大小 D、基地址和结点大小

练习2
1、栈的逻辑结构与( D )的逻辑结构不同。
A、线性表 B、串 C、队列 D、树
2、下面关于判定树和二叉排序树的描述正确的是（ B ）。
A、折半查找长度为n的表的判定树是和含有n个结点的二叉排序树都是唯
一的。
B、折半查找长度为n的表的判定树是唯一的，而含有n个结点的二叉排序
树却不唯一。
C、折半查找长度为n的表的判定树是不唯一的，而含有n个结点的二叉排

3
4
5 6 2
1
序树却唯一。
D、折半查找长度为n的表的判定树是和含有n个结点的二叉排序树都是不
唯一的。
3、设字符S1＝‘ABCDEFG’，S2＝‘PQRST’，则运算S＝CONCAT（SUB
（S1,2,LENGTH（S2）），SUB（S1，LENGTH（S2）,2））后结果为（ D ）。
A、‘BCQR’ B、‘BCDEF’ C、‘BCDEFG’ D、‘BCDEFEF’
4、关键字（49，38，65，97，76，13，27， ，55，04）取d=5用希尔排序后，
得到的排序结果为 ( A )。

A、13，27，，55，04，49，38，65，97，76;
B、13，27，49，55，04， ，38，65，97，76; C、13，27，38，49，55， ，04，65，97，76; D、13，27，49，55，04， ，38，65，76，97; 5、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为50的结点的右孩子的编号为( C )。 A、100 B、101 C、没有 D、99 6、折半查找的适用条件为( A ) A、采用顺序存储结构的有序表。 B、采用链式存储结构的有序表。 C、采用顺序存储结构的无序表。 D、采用链式存储结构的无序表。 7、“假上溢”现象会出现在( B )中。 A、循环队列 B、顺序队列 C、链队列 D、队列 8、有向图中，顶点Vi的入度是（ A ）。 A、邻接矩阵中第i列元素之和。 B、邻接矩阵中第i行元素和第i列元素之和。 C、 邻接矩阵中第i列元素之和的2倍。 D、邻接矩阵中第i行元素之和。 9、若让元素1，2，3依次进栈，则出栈次序不可能出现（ C ）种情况。 A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2 10、在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行( D )。 A、q->next = p->next ; p->next = q; B、p->next = q->next; q = p; 49 49

49
49

49
C、q->next = p->next; p->next = q;
D、p->next = q->next ; q->next = p;
练习3

1、有n个结点的判定树的深度为__1log2n__。
2、二叉树在先序遍历和中序遍历二叉树时，得到的结点访问序列相同，该二叉
树是单右子树。
3、队列的插入操作在队尾进行，删除操作在队头进行。
4、顺序存储线性表表头插入的时间复杂度是：O(n)。
5、完全二叉树中任一结点，若其右分支下子孙的最大层次为L，则其左分支下
子孙的最大层次必为L或L+1。
练习4
1、中缀算术表达式3+4/（25-（6+15））*8 所对应的后缀算术表达式为3 4 25 6
15+-/8*+。
2、在多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。因此，
数组是一种随机存取结构。
3、循环队列采用的是顺序存储结构。
4、在起泡排序中，若初始序列为“逆序”序列，则必须进行比较的次数为
n(n+1)/2。
5、树的孩子表示法便于那些涉及孩子的操作的实现。
练习5

1、在起泡排序中，时间复杂度为O(n2)。
2、在一个长度为n的顺序表中的第i个(1≤i≤n)元素之前插入一个元素时,需要
移动n-i+1个元素。
3、对任何一棵二叉树，如果度为2的结点数为30，则其叶子结点数为31。
4、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的行标、列标
和元素值三项。
5、含有n个结点的二叉链表中空链域个数是n+1。
练习6
1、分别画出和下列树对应的各个二叉树。
（略，参考书本p138）
2、填空使下面的程序段实现顺序表的直接插入排序。
Void insertSort(SqList &L){
For (i=2;i<=L.length;++i)
If (LT(L.r[i].key,L.r[i-1].key))
{ L. r[0]= L. r[i] ;
L. r[i]= L. r[i-1];
for (j=i-2; L. r[0]= L. r[j] .key);--j) L. r[j+1]= L. r[j];
L. r[j+1]= L. r[0];
}
}
3、写出下面二叉树的先序遍历、中序遍历和后序遍历。

（略，参考书本p128）
4、在选择算法时，除首先考虑正确性外，还应考虑哪三点?
选用的算法首先应该是"正确"的。此外，主要考虑如下三点：
① 执行算法所耗费的时间；
② 执行算法所耗费的存储空间，其中主要考虑辅助存储空间；
③ 算法应易于理解，易于编码，易于调试,等等。

5、根据下面图的邻接矩阵，画出相应图的逆邻接表。
1 2 3 4 5 6
1 0 0 0 0 0 0
2 0 0 1 0 0 0

D
C B
A

A B C A B C A
B C D

E F G H
3 0 0 0 1 0 0
4 0 0 0 0 1 0
5 0 0 0 0 0 1
6 1 1 0 6 0 0
（略，参考书本p164）