数据结构课后练习题
一、 选择题
1、在以下 讲述中，正确的是（ B ）。
A、线性表的现行存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出
2、若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ B ）。
A、正确 B、错误
3、二维数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（ A ）。 A、SA+141 B、SA+180 C、SA+222 D、SA+225
4、数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（ C ）。 A、80 B、100 C、240 D、270
5、常对数组进行的两种基本操作是（ C ）。
A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引 6、将一个A[15][15]的下三角矩阵（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A中元素A[6][5]在B数组中的位置K为（ D ）。 A、19 B、26 C、21 D、15
7、若广义表A满足Head(A)=Tail(A)，则A为（ B ）。 A、（） B、（（）） C、（（），（）） D、（（），（），（）） 8、广义表（（a）,a）的表头是（ C ），表尾是（ C ）。 A、a B、b C、(a) D、((a)) 9、广义表（（a,b）,c,d）的表头是（ C ），表尾是（ D ）。 A、a B、b C、(a,b) D、(c,d) 10、广义表（（a））的表头是（ B ），表尾是（ C ）。 A、a B、(a) C、() D、((a)) 11、广义表（a,b,c,d）的表头是（ A ），表尾是（ D ）。 A、a B、(a) C、(a,b) D、(b,c,d) 12、广义表（（a,b,c,d））的表头是（ C ），表尾是（ B ）。 A、a B、() C、(a,b,c,d) D、((a,b,c,d)) 13、下面结论正确的是（ BC ）。
A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表
C、广义表L=（（），（A，B））的表头为空表 D、广义表中原子个数即为广义表的长度 14、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=( D ) A、(G) B、(D) C、C D、 D
15、已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出原子项t的操作是（ D ）。
A、Head(Head(Tail(Tail(L)))) B、Tail(Head(Head(Tail(L)))) C、Head(Tail(Head(Tail(L)))) D、Head(Tail(Head(Tail(Tail(L)))))
16、设A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))=( C ) A. (g) B.(d) C.c D.d 17、对矩阵压缩存储是为了（ B ）
A、方便运算 B、节省空间 C、方便存储 D、提高运算速度 18、稀疏矩阵一般的压缩存储方法有两种，即（ C ）
1
A、二元数组和三元数组 B、三元组和散列 C、三元组和十字链表 D、散列和十字链表
二、 判断题 A—对B—错 1． 数组是同类型值的集合。B
2． 数组的存储结构是一组连续的内存单元。A
3． 数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。B
4． 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。B 5． 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。A
6． 广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。A
7． 线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。A 8． 广义表中原子个数即为广义表的长度。B 9． 广义表中元素的个数即为广义表的深度。B
三、 填空题
1、设a是含有N个分量的整数数组，则求该数组中最大整数的递归定义为（ f(k)=a[0](k=0时)||f(k)=max(f(k-1),a[k])(k>0时)），
最小整数的递归定义为（ f(k)=a[0](k=0时)||f(k)=min(f(k-1),a[k])(k>0时) ）。
2、二维数组A[10][5]采用行序为主方式存储，每个元素占4个存储单元，并且A[5][3]的存储地址是1000，则A[8][2]的地址是（ ）。
3、二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是Loc(A[0][0])，则A[i][j]的地址是（ ）。
4、广义表的（ ）定义为广义表中括弧的重数。 5、设广义表L=（（），（）），则Head(L)=（ ）；Tail(L)=（ ）；L的长度是（ ）；L的深度是（ ）。 6、广义表中的元素可以是（ ），其描述宜采用程序设计语言中的（ ）表示。 7、广义表(((a)))的表头是（ ），表尾是（ ）。 8、广义表((a),((b),c),(((d))))的表头是（ ），表尾是（ ）。 9、设广义表A=(x,((a,b),c,d))，则Head(Head(Tail(A)))=（ ）。 10、设广义表A=(a,b,c),B=(A,(c,d)),C=(a,(B,A),(e,f))，则
（1）Head(A)=( ) (2) Tail(B)=( ) (3) Head(Head(Head(Tail(C))))=( )
11、下三角矩阵A[1..N,1..N]的下三角元素已压缩到一维数组S[1..N*（N+1）/2+1]中，若按行序为主序存储，则A[I,j]对应的S中的存储位置是 。
?0?312、已知一个稀疏矩阵为 ??0??002000?1000?0?? ，则对应的三元组表表示为 。 5??0?13、一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为 。 14、三维数组A[c1..d1,c2..d2..,c3..d3]共有 个元素。
15、数组A[1..10,-2..6,2..8]以行优先顺序存储，设基地址为100，每个元素占3个存储单元，则元素A[5,0,7]的存储地址是 。
16、将一个下三角矩阵A[1..100,1..100]按行优先存入一维数组B[1..n]中，A中元素A[66,65]在B数组中的位置为 。 四、 计算题
1、 数组A[8][6][9]以行主序存储，设第一个元素的首地址是54，每个元素的长度为5，求元素A[2][4][5]
的存储地址。
2
2、 假设二维数组A6x8，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的基地址为1000，
计算：
（1） 数组A的体积（存储量） （2）A的最后一个元素第一个字节的地址
（3）按行存储时，a14的第一个字节的地址 （4）按列存储时，a47的第一个字节的地址。
3、 假设按低下标优先存储整数数组A9x3x5x8时，第一个元素的字节地址是100，每个整数占4个字节。
问下列元素的存储地址是什么？
（1）a0000 （2） a1111 （3） a3125 （4）a8247
4、 按行优先顺序和按列优先顺序分别列出四维数组A[2][2][2][2]所有元素在内存中的存储顺序。 5、 一个n阶对称矩阵A采用一维数组S按行序为主序存放其上三角各元素，写出S[k]与A[i,j]的关系公
式。设A[1，1]存于S[1]中。
6、 写出下面稀疏矩阵对应的三元组表示，并画出十字链表表示法。 A=〔（0，0，2，0），（3，0，0，0），（0，0，-1，5），（0，0，0，0）〕 五、 简答题
1、 什么是广义表，简述广义表与线性表的主要区别？
2、 利用广义表的Head和Tail运算把原子student从下列广义表中分离出来。
（1） L1=（soldier,teacher,student,worker,farmer） （2） L2=（soldier,(teacher,student),(worker,farmer)） 3、 画出下列广义表的存储结构图，并求它的深度。
（1）((( )),a,((b,c)),(((d)))) （2）((((a),(b))),((( ),d),(e,f)))
4、已知图4.4为广义表的存储结构图，写出各图的广义表。 （1） 1 1 ∧
1 1 ∧ 1 ∧ 1 1 ∧
0 x 1 ∧ 1 ∧ 1 ∧
0 y 1 ∧ ∧ 0 z （2） 1 1 1 ∧ ∧ 1 1 ∧ ∧ 1 1 ∧ 1 1 1 ∧ ∧ 0 a 1 ∧ 0 a 0 b 0 b
六、 设计题
1、 对于二维数组A[m][n]，分别编写相应函数实现如下功能：（1）求数组 A靠边元素之和；（2）求从
A[0][0]开始的互不相邻的各元素之和；（3）当m=n时分别求两条对角线上的元素之和，否则打印出m≠n的信息。
2、 如果矩阵A中的一个元素A[i][j]满足下列条件：A[i][j]是第I行中最小的元素，又是第j列中值最大
的元素，则称之为该矩阵的一个马鞍点。编写函数计算m×n的矩阵A的所有马鞍点，并分析算法的时间复杂度。
3
第六章：树和二叉树复习题
一、选择题
1、 有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据
结构是（ ）
A、向量 B、树 C、图 D、二叉树 2、树最适合用来表示（ ）
A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据
3、树B的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ ）
A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c)
4、对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）次序的遍历实现二叉树的结点编号。 A、先序 B、中序 C、后序 D、从根开始按层次遍历 5、按照二叉树的定义，具有3个结点的二叉树有（ ）种。 A、3 B、4 C、5 D、6
6、在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则数的最大高度为（ ），其叶结点数为（ ）；树的最小高度为（ ），其叶结点数为（ ）；若采用链表存储结构，则有（ ）个空链域。
A、n/2 B、[ log2n]+1 C、log2n D、n E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1 K、n2 L、n1+1
7、对一棵满二叉树，m个树叶，n个结点，深度为h，则（ ） A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1
8、设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ），至多为（ ）。
A、2h B、2h-1 C、2h-1 D、2h-1
9、在一棵二叉树上第5层的结点数最多为（ ）（假设根结点的层数为1） A、8 B、16 C、15 D、32
10、深度为5的二叉树至多有（ ）个结点。 A、16 B、32 C、31 D、10
11、一棵有124个叶结点的完全二叉树，最多有（ ）个结点 A、247 B、248 C、249 D、250
12、含有129个叶子结点的完全二叉树，最少有（ ）个结点 A、254 B、255 C、256 D、257
13、假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）个。 A、15 B、16 C、17 D、47
16、用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点（ ）。
A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1]
17、在一棵非空二叉树的中序遍历序列中，根结点的右边（ ）。
A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点 D、只有左子树上的部分结点
18、任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序（ ）。 A、不发生改变 B、发生改变 C、不能确定 D、以上都不对
19、设n、m为一棵树上的两个结点，在中序遍历时，n在m前的条件是（ ）。 A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙
4
20、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（ ），后序遍历中结点B的直接后继是（ ）。
A、B B、D C、A D、I E、F F、C
21、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）。 A、acbed B、decab C、deabc D、cedba
22、若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（ ）遍历方法最合适。
A、前序 B、中序 C、后序 D、层次 23、线索二叉树是一种（ ）结构。
A、逻辑 B、逻辑和存储 C、物理 D、线性
24、如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的（ ）。 A、前序 B、中序 C、后序 D、层次序
25、设T是哈夫曼树，具有5个叶结点，树T的高度最高可以是（ ）。 A、1 B、2 C、3 D、4 E、5 F、6
26、由带权为8，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ ）。 A、23 B、37 C、46 D、43
27、树的后根遍历序列等同于该树对应的二叉树的（ ）。 A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 28、以下说法错误的是（ ）
A、树形结构的特点是一个结点可以有多个直接前趋 B、线性结构中的一个结点至多只有一个直接后继 C、二叉树与树是两种不同的数据结构
D、树(及一切树形结构)是一种“分支层次”结构 29、以下说法错误的是（ ）
A、二叉树可以是空集 B、二叉树的任一结点都有两棵子树
C、二叉树与树具有相同的树形结构 D、二叉树中任一结点的两棵子树有次序之分 30、以下说法错误的是（ ）
A、完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B、在三叉链表上，二叉树的求双亲运算很容易实现 C、在二叉链表上，求根，求左、右孩子等很容易实现 D、在二叉链表上，求双亲运算的时间性能很好 31、以下说法错误的是（ ）
A、一般在哈夫曼树中，权值越大的叶子离根结点越近 B、哈夫曼树中没有度数为1的分支结点
C、若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点
D、若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树
32、将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为（ ）
A 、10 B、 11 C、 41 D、 20
33、任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置（ ） A、肯定发生变化 B、有时发生变化 C、肯定不发生变化 D、无法确定 34、下列说法正确的是（ ）
A、树的先根遍历序列与其对应的二叉树的前序遍历序列相同 B、树的先根遍历序列与其对应的二叉树的后序遍历序列相同 C、树的后根遍历序列与其对应的二叉树的前序遍历序列相同 D、树的后根遍历序列与其对应的二叉树的后序遍历序列相同
5
35、下列说法中正确的是（ ）
A、任何一棵二叉树中至少有一个结点的度为2 B、任何一棵二叉树中每个结点的度都为2
C、任何一棵二叉树中的每个结点的度肯定等于2 D、任何一棵二叉树中的每个结点的度都可以小于2
36、一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（ ）遍历方式就可以得到这棵二叉树所有结点的递减序列。
A、前序 B、中序 C、后序 D、层次
37、对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A 、0 B、 1 C 、2 D、 不存在这样的二叉树
38、在图6.2中的二叉树中，（ ）不是完全二叉树。
A、 B、 C、 D、
图6.2
39、树最适合用来表示（ ）
A、有序数据元素 B、无序数据元素
C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据 40、哈夫曼树的带权路径长度是（ ）
A、所有结点权值之和 B、所有叶结点带权路径长度之和 C、带权结点的值 D、除根以外所有结点权值之和 41、在线索二叉树上，线索是（ ）
A、两个标志域 B、指向结点前驱和后继的指针 C、数据域 D、指向左、右子树的指针 42、已给出如图6.3所示哈夫曼树，那么电文CDAA的编码是( )
A、110100 B、11011100 C、010110111 D、11111100
A
B
C D 图6.3
43、已给出的图6.3所示二叉树，A,B,C,D分别带权值为7，5，2，4则该树的带权路径长度为（A、46 B、36 C、35 D、都不是 44、在线索化二叉树中，t所指结点没有左子树的充要条件是（ ）
A、t->lchild==NULL B、t->ltag==1 C、t->ltag==1&&t->lchild==NULL D、以上都不对
6
）45、下列叙述中正确的是（ ）
A、二叉树是度为2的有序树 B、 二叉树中结点只有一个孩子时无左右之分
C、二叉树中必有度为2的结点 D、 二叉树中结点最多有两棵子树，并且有左右之分 46、下图6.4所示的几种结构中属于树型结构的是（ ）
A、 B、 C、 D、
图6.4
二、 判断题
1、二叉树是树的特殊形式。
2、树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
3、一棵有n个结点的d度树，若用多重链表表示，树中每个结点都是有d个链域，则在树的n*d个链域中，有n*(d-1)+1个是空链域，只有n-1个是非空的。
4、前序遍历树和前序遍历与该树对应的二叉树，其结果相同。 5、后序遍历树和中序遍历与该树对应的二叉树，其结果不同。 6、前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同。 7、中序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。
8、若有一个结点是某二叉树子树的中序遍历序列中最后一个结点，则它必须是该子树的前序遍历序列中的最后一个结点。
9、二叉树具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。 10、在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。 11、中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。 12、在二叉树中插入结点，该二叉树便不在是二叉树。 13、用一维数组存储二叉树时，总是以前序遍历存储结点。
14、已知二叉树的前序遍历和后序遍历序列不能唯一地确定这棵树。 15、不使用递归，也可以实现二叉树的前序，中序，后序遍历。
16、在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。
17、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。
三、 填空题
1、在树型结构中，树根结点没有（ ）结点，其余每个结点有且只有（ ）个前驱结点；叶子结点没有（ ）结点，其余每个结点的后继结点可以（ ）。 2、假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为（ ），树的深度为（ ），终端结点的个数为（ ），单分支结点的个数为（ ），双分支结点的个数为（ ），三分支结点的个数为（ ），C的双亲结点为（ ），其孩子结点为（ ）。
3、设树T中除叶结点外，任意结点的度数都是3，则T的第I层结点的个数为（ ）。 4、在具有n(n>=1)个结点的k叉树中，有（ ）个空指针。 5、一棵含有n个结点的k叉树，可能达到的最大深度为（ ），最小深度为（ ）。 6、一棵深度为k的满二叉树的结点总数为（ ），一棵深度为k的完全二叉树的结点总数的最小值为（ ），从左到右次序给结点编号（从1开始）则编号最小的叶子结点的编号是（ ），最大值为（ ）。
7、设根结点的层次数为0，定义树的高度为树中层次最大的结点的层次加1，则高度为k的二叉树具有的结点数目，最少为（ ），最多为（ ）。 8、n个结点的完全二叉树，若按从上到下、从左到右给结点顺序编号，则编号最大的非叶结点编号为（ ），
7
编号最小的叶结点编号为（ ）。
9、在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=（ ）。 10、一棵二叉树的第I层最多有（ ）个结点，一棵有n个结点的满二叉树共有（ ）个叶子结点和（ ）个非终端结点。
11、一棵完全二叉树的第5层有5个结点，则共有（ ）个结点，其中度为1的结点有（ ）个，度为0的结点有（ ）个。
12、具有n个结点的完全二叉树，其叶子结点的个数为（ ）。
13、对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为（ ）个，其中（ ）个用于链接孩子结点，（ ）个空闲。
14、对于一棵具有n个结点的二叉树，当它为一棵（ ）二叉树时具有最小高度，高度为（ ），当它为一棵单支树时具有（ ）高度，高度为（ ）。
15、树所对应的二叉树其根结点的（ ）子树一定为空。
16、从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是（ ）。
18、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（ ），后序遍历中结点B的直接后继为（ ）。
19、某二叉树的中序遍历序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树结点的前序序列为（ ），该二叉树对应的森林包括（ ）棵树。
20、在一棵二叉排序树上按（ ）遍历得到的结点序列为有序序列。 21、由n个权值构成的哈夫曼树共有（ ）个结点。
22、由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为（ ）。
23、设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。
四、 附加判断题
1、 树中任意结点的子树不必是有序的。（ ） 2、 树可以看成特殊的的无向图。（ ） 3、 可以使用双链表表示树形结构。（ ） 4、 顺序存储方式只能用于存储线性结构。（ ） 5、 完全二叉树的某结点若无左孩子，则必为叶结点。（ ） 6、 如果一个二叉树的结点，或者没有子树，或者恰有两棵非空子树，则此二叉树称为完全二叉树。（ ） 7、 包含两个结点的所有二叉树都是相同的。（ ）
8、 二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。（ ） 9、 二叉树的前序和后序遍历能唯一确定一棵二叉树。（ ） 10、 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索。（ ） 11、 中序线索二叉树中，右线索若不为空，则一定指向其父结点。（ ） 五、 简答题
1、分别画出含3个结点的树与二叉树的所有不同形态。
2、设在树中，结点x是结点y的双亲时，用(x,y)来表示边。已知一棵树边的集合为：{(i,j),(i,k),(b,e),(e,i),(b,d),(a,b),(c,g),(c,f),(c,h),(a,c)}，用树形表示法画出此树，并回答下列问题：
（1） 哪个是根结点？ （2） 哪些是叶子结点？ （3） 哪个是g 的双亲？ （4） 哪些是g的祖先？ （5） 哪些是e的子孙？ （6） 哪些是f的兄弟？ （7） 结点b和j的层次各是多少？
8
（8） 树的深度是多少？ （9） 树的度数是多少？
3、任意一个有n(n>0)个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有m-1个度为2，其余度为1。
4、分别画出图6.6所示二叉树的二叉链表、三叉链表和顺序存储结构。 A B D
E C F 图6.6
5、分别写出图6.7所示二叉树的前序、中序和后序序列。
A B C E F D
图6.7
6、试分别画出图6.8所示树的孩子链表、孩子兄弟链表和静态双亲链表。
A
C B D F G H I E J
L K 图6.8
7、将图6.9所示的森林转换成二叉树。 A G
I B C D H
F E 图6.9
J K L M N 9
8、分别画出图6.10所示各二叉树对应的森林。并写出森林的前序和中序遍历序列。
9、设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。
10、将代数式：y=3*(x+a)-a/x2 描述成表达式树，并写出前缀式和后缀式来。
11、下述编码{00，01，10，11}，{0，1，00，11，}，{0，10，110，111}哪一组不是前缀码？
图6.10 A B D G I E H J K C F
第七章：图 练习题
一、 选择题
1、一个有n个顶点的无向图最多有（ ）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n
2、具有6个顶点的无向图至少有（ ）条边才能保证是一个连通图。 A、5 B、6 C、7 D、8
3、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（ ）。 A、线性图 B、无向完全图 C、无向图 D、简单图 4、具有4个顶点的无向完全图有（ ）条边。 A、6 B、12 C、16 D、20
5、G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点 A、6 B、7 C、8 D、9
6、存储稀疏图的数据结构常用的是（ ）。
A、邻接矩阵 B、三元组 C、邻接表 D、十字链表
7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（ ）。
222
A、n B、(n-1) C、(n+1) D、n
8、设连通图G的顶点数为n，则G的生成树的边数为（ ）。 A、n-1 B、n C、2n D、2n-1
9、对于一个具有N个顶点和E条边的无向图，若采用邻接表表示，则表头向量的大小为（ （1） ）；所有邻接表中的结点总数是（ （2） ）
（1）A、N B、N+1 C、N-1 D、N+E
10
（2）A、E/2 D、E C、2E D、N+E
10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（ ），所有顶点邻接表的结点总数为（ ）。
A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e 11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（ ）。
A、顶点v的度 B、顶点v的出度 C、顶点v 的入度 D、依附于顶点v的边数
12、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（ ）和（ ）
（1） A、abecdf B、acfebd C、acebfd D、acfdeb （2） A、abcedf B、abcefd C、abedfc D、acfdeb
13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（ ）和（ ）。 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历
14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ ）和（ ）。
A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v3,v4,v5,v2 D、v1,v4,v3,v5,v2
15、已知有8个顶点为A，B，C，D，E，F，G，H的无向图，其邻接矩阵存储结构如下，由此结构，从A点开始深度遍历，得到的顶点序列为（ ）。 A B C D E F
A 0 1 0 1 0 0 B 1 0 1 0 1 1 C 0 1 0 1 0 0 D 1 0 1 0 0 0 E 0 1 0 0 0 0 11
F 0 1 0 0 0 0 G 0 1 0 1 0 1 H 0 0 0 0 1 1 G H 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 A、ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDC E、ABEHFGDC F、ABEHGFCD
16、已知一个图如下，在该图的最小生成树中各边上权值之和为（ ），在该图的最小生成树中，从v1到v6的路径为（ ）。
A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v6
17、关键路径是事件结点网络中的（ ）。
A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最长的回路 D、最短的回路 18、正确的AOE网必须是（ ），AOE网中某边权值应当是（ ）。 （1）A、完全图 B、哈密尔顿图 C、无环图 D、强连通图
（2）A、实数 B、正整数 C、正数 D、非负数 19、已知一个图如下，则由该图得到的一种拓扑序列为（ ）。
A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v5
20、下面结论中正确的是（ ）
A、在无向图中，边的条数是顶点度数之和。 B、在图结构中，顶点可以没有任何前驱和后继。 C、在n个顶点的无向图中，若边数大于n-1，则该图必定是连通图 D、图的邻接矩阵必定是对称矩阵。 21、下面结论中正确的是（ ）
A、若有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑排序序列必定存在。 B、网络的最小代价生成树是唯一的。 C、在拓扑排序序列中，任意两个相继顶点vi和vj都存在从vi到vj的路径。 D、在有向图中，从一个顶点到另一个顶点的最短路径是唯一的。 22、下面结论不正确的是（ ）。
A、无向图的连通分量是该图的极大连通子图。 B、有向图用邻接矩阵表示容易实现求顶点度数的操作。 C、无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。 D、有向图的邻接矩阵必定不是对称矩阵。
23、下面结论中正确的是（ ）。
A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按深度优先搜索遍历的结果是唯一的。 C、若有向图G中包含一个环，则G的顶点间不存在拓扑排序。 D、图
12
的拓扑排序序列是唯一的。
24、下面结论中不正确的是（ ）。
A、按广度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按广度优先搜索遍历的结果是唯一的。 C、无向图的邻接表表示法中，表中结点的数目是图中边的条数的2倍。 D、图的多重邻接表表示法中，表中结点数目是图中边的条数。
25、在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A、1/2 B、1 C、2 D、4
26、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A、1/2 B、1 C、2 D、4
27、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ ） A、求关键路径的方法 B、求最短路径的DIJKSTRA方法 C、广度优先遍历算法 D、深度优先遍历算法 28、任何一个带权的无向连通图的最小生成树（ ）
A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在 29、以下说法正确的是（ ）
A、连通图的生成树，是该连通图的一个极小连通子图。
B、无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 C、任何一个有向图，其全部顶点可以排成一个拓扑序列。 D、有回路的图不能进行拓扑排序。 30、以下说法错误的是（ ）
A、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
B、邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。 C、存储无向图的邻接矩阵是对称的，因此也可以只要存储邻接矩阵的下（或上）三角部分。
D、用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am
的第 i行第j列的元素是否为0即可。 31、以下说法正确的是（ ）
A、连通分量是无向图中的极小连通子图。 B、强连通分量是有向图中的极大强连通子图。
C、在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧
D、对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。 二、 判断题
1、用邻接矩阵法存储一个图时，所占用的存储空间大小仅与图中结点个数有关。
2、对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。 3、任何有向网拓扑排序的结果是唯一的。 4、有回路的图不能进行拓扑排序。 5、存储有向图的邻接矩阵是对称的。
6、一个有向图G中若有弧
7、在AOE网中一定有一条关键路径。
8、含有10个顶点的无向连通图其生成树含有9条边。 9、十字链表是图的一种顺序表示法。
三、 填空题
13
1、对具有n个顶点的图，其生成树有且仅有__________条边，即生成树是图的边数__________的连通图。 2、一个无向图有n个顶点和e条边，则所有顶点的度数之和为（ ），其邻接矩阵是一个关于__________对称的矩阵。
3、在图形结构中，每个结点的前驱结点和后继结点可以有（ ）。
5、设无向图G的顶点数为n，图G最少有（ ）边，最多有（ ）条边。若G为有向图，有n个顶点，则图G最少有（ ）条边，最多有（ ）条边。具有n个顶点的无向完全图，边的总数为（ ）条，而有n个顶点的有向完全图，边的总数为（ ）条。
6、在无权图G的邻接矩阵A中，若(vi,vj)或
7、在无向图G的邻接矩阵A中，若A[i][j]=1，则A[j][i]等于（ ）。 8、已知一个图的邻接矩阵表示，计算第I个顶点的入度方法为（ ） 9、在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（ ），而对于无向图而言等于该顶点的（ ）。
10、已知图G的邻接表如图7.4所示，其从顶点V1出发的深度优先搜索序列为__________，其从顶点V1出发的广度优先搜索序列为__________。 4 1 3 ∧ 0 V1 4 ∧ 1 V2 2 2 V3 5 ∧ 3 V ∧ 4 4 V5 5 3 2 ∧ 5 V6 ∧
图7.4
11、n个顶点的弱连通有向图G最多有（ ）条弧，最少有（ ）条弧。 12、在n个顶点e条边的连通图中，连通分量个数为（ ）。
13、任何（ ）的有向图，其所有结点都可以排 在一个拓扑序列中，拓扑排序的方法是先从图中选一个（ ）为0的结点且输出，然后从图中删除该结点及其（ ），反复执行，直到所有结点都输出为止。 14、一个连通图的（ ）是一个极小连通子图。
15、在AOE网中，从源点到汇点各活动时间总和最长的路径为（ ）。
16、在有向图的邻接矩阵上，由第i行可得到第__________个结点的出度，而由第j列可得到第__________个结点的入度。
17、对无向图，设有n个结点，e条边，则其邻接表表示中需要__________个表结点，对有向图，设有n个顶点，e条弧，则其邻接表表示需要__________个表结点。
18、在无权图G的邻接矩阵A中，若 (Vi,Vj)或
19、已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是__________。
删除所有从第i个结点出发的边的方法是__________。
20、设无向图G中顶点数为n，则图G最少有__________条边，最多有 条边。若G为有向图，有n个顶点，则图至少有__________条边，最多有__________条边。
21、某作业工程表示成网络图，如图7.5所示。事件5的最早完成时间是_______。事件4的最迟开始时间是________。事件5的迟缓时间是________。关键路径是__________。
14
e4=4 4 1 e8=12
e1=5 e9=6
2 0 9 e5=10 5 e10=10 e2=9 e3=14 e14=8 6 e11=5
8 e6=3 e12=5
3 e13=8 e7=7
7 图7.5
22、设x,y∈V，若
23、在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是_______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为________。 24、连通分量是无向图中的________连通子图。
25、对无向图，若它有n个顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成头结点，________个结点构成边结点表。
26、对有向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成头结点，________个结点构成边结点表。 27、在邻接表上，无向图中顶点vi的度恰为________________。对有向图，顶点vi的出度是________________。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为________的结点的个数是顶点vi的入度。
28、遍历图的基本方法有________优先搜索和________优先搜索两种。
四、 简答题
1、 对于一个具有n个顶点的连通无向图，如果它有且只有一个简单回路，此图有几条边？一个具有n
个顶点的弱连通图至少有几条边？
2、 已知某图的邻接表，如何建立该图的邻接矩阵？
3、 简述无向图和有向图有哪几种存储结构，并说明各种结构在图的不同操作中有什么优越性？ 什么是AOE网的关键路径？
五、补充应用题
1. 给出无向图如图7.6所示的G1的邻接矩阵和邻接表。
V1 V2 V1 V2 V1
V4 V3 V4 V5 V3 V4 V5
G2 G3
V3
G1 7.6 所示的 G 2 的邻接矩阵、邻接表和逆邻接表。 图7.6 2. 分别给出图
15
V2 V5 3. 分别给出图7.6所示的G3从v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。 4. 求出图7.7的连通分量。
V1 V2 V6 V3 V8 V7 V V5 4 图7.7 5. 设有一无向图G=(V,E),其中
V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)}。 (1)按上述顺序输入后，画出其相应的邻接表；
(2)在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。
6. 已知连通网的邻接矩阵如图7.8所示，顶点集合为{v1,v2,v3,v4,v5}，试画出它所表示的从顶点v1开始
利用Prim算法得到的最小生成树。
?? 1 12 510??1?89??? ??128??2?
? ? ?59??4? ??10?24???
图7.8
1 4 2 7 6 8 5 3 9 图7.9
7. 拓扑排序的结果不是唯一的，对图7.9进行拓扑排序，写出全部不同的拓扑排序序列。 8. 已知图G的邻接表如图7.10所示，顶点V1为出发点，完成要求： （1） 深度优先搜索的顶点序列； （2） 广度优先搜索的顶点序列；
（3） 由深度优先搜索得到的一棵生成树； 1 （4） 由广度优先搜索得到的一棵生成树。 1 4 2 3 2 V1 1 3 4 ∧ 5 4 V2 0 2 5 ∧ 3 8 4 V3 1 4 5 ∧ V4 0 4 V5 0 2 3 5 ∧ 5 2 6 3 6 V6 1 2 4 ∧ 4 5
7 图7.10
图7.11
9. 图7.11所示为一无向连通网络，要求根据Prim算法和Kruskal构造出它的最小生成树。
16
10. 在下图所示的有向图7.12中： V1 V2 V3 V4 图7.12
（1） 该图是强连通图吗？ （2）请给出每个顶点的度、入度和出度。 （3）给出其邻接矩阵、邻接表及逆邻接表。
11. DFS和BFS遍历采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种
遍历？画出以顶点v1为初始源点遍历图7.13所示的有向图所得到的DFS和BFS生成森林。 V 3 V1 V4 V2 V5 V6 V8 V7 图7.13
12. 对图7.14所示的有向网，试利用Dijkstra算法求从源点1到其他各顶点的最短路径。
10 4 6
5 15 4 30 10 4 15 10 图7.14
2 20 2 1 3
13. 已知如图7.16所示的AOE网。求：
（1）每项活动的最早开始时间和最晚开始时间； （2）完成此工程最少需要多少单位时间； （3）关键活动与关键路径。
e3=3 5 2 e8=1
e1=3 e4=2
4 6 1 e7=2 e5=4
e2=2 e6=3 3
图7.16
14. 已知带权连通图，G（V,E）的邻接表如图7.17所示。试画出该图，并分别从顶点1开始的深度优先和
广度优先遍历之，给出遍历中结点的序列，最后画出该图的一棵最小生成树。其中表结点的三个域为
顶点号 边上的权值 指针
17
2 8 2 1 8 3 1 10 4 1 11 5 2 13 图 7.17 1 3 3 2 3 10 3 3 4 4 ∧ 11 5 ∧ 13 4 ∧ 4 5 ∧ 7 4 ∧ 7 ?0?115. 已知某图G的邻接矩阵为 ??0??1101001011?0??，顶点集合为{v1,v2,v3,v4} 1??0?（1）由邻接矩阵画出相应的图G；
（2）如果要使用此图成为完全图还要增加哪几条边。
16. 对于图7.19所示的AOE网络，计算各事件（顶点）的ve(vi)和vl(vj)和活动（边）的e(ai)和l(ai)函数值；
列出各条关键路径和关键活动。 a7=6 A
a1=1 a2=6 D a12=5 B a8=2 a 9=7 C E a11 =8 a20=10 W a 16 =8 a 17 =4 a13=11 a 3=3 a4=4 F V a5=3 G a6=1 I a10=6 a=12 a 18 =4 22H J a14 =10 a19=9 a15=6 a=9 21K 图7.19
第九章：查找复习题
一、 选择题
1、顺序查找一个共有n个元素的线性表，其时间复杂度为（ ），折半查找一个具有n个元素的有序表，其时间复杂度为（ ）。
A、O(n) B、O(log2n) C、O(n2) D、O(nlog2n)
2、在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（ ）。 A、n B、[log2n] C、[log2(n+1)] D、「log2(n+1)
3、采用顺序查找方式查找长度为n的线性表时，平均查找长度为（ ） A、n B、n/2 C、(n+1)/2 D、(n-1)/2
4、采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（ ）对应判定树的高度（设高度大于等于2）。
A、小于 B、大于 C、等于 D、大于等于
18
5、已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（ ）。
A、1 B、2 C、3 D、4
6、对线性表进行折半查找时，要求线性表必须（ ）。
A、以顺序方式存储 B、以链接方式存储 C、以顺序方式存储，且结点按关键字有序排序 D、以链接方式存储，且结点按关键字有序排序
7、顺序查找法适合于存储结构为（ ）的查找表。
A、散列存储 B、顺序或链接存储 C、压缩存储 D、索引存储
8、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（ ）个结点最佳。 A、10 B、25 C、6 D、625
9、从键盘依次输入关键字的值：t,u,r,b,o,p,a,s,c,l，建立二叉排序树，则其先序遍历序列为（ ），中序遍历序列为（ ）。
A、abcloprstu B、alcpobsrut C、trbaoclpsu D、trubsaocpl 10、折半查找和二叉排序树的时间性能（ ）。 A、相同 B、不相同
11、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。 A、2k-1-1 B、2k-1 C、2k-1+1 D、2k-1
12、利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要进行（ ）元素间的比较。
A、4次 B、5次 C、7次 D、10次
13、设Hash地址空间为0到m-1，哈希函数为h(k)=k%p，为了减少发生冲突的可能性，一般取p为（ ）。 A、小于m的最大奇数 B、小于m的最大素数 C、小于m的最大偶数D、小于m的最大合数。 14、长度为10的按关键字有序的查找表采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是（ ）
A、24/10 B、 24/11 C、39/10 D、39/11
15、在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（ ）
A、n+1 B、1 C、n D、n-1
16、设哈希函数为H(key)=key%7,一组关键字为(37，21，9，20，30，19和46)，哈希表T的地址空间为0..6,用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为（ ） A、 0 1 2 3 4 5 6
21 20 21 46 21 19 20 37 37 37 9 30 9 9 37 21 46 30 30 46 30 19 46 19 19 20 20 9 B、 0 1 2 3 4 5 6 C、 0 1 2 3 4 5 6 D、 0 1 2 3 4 5 6 17、设有一个用线性探测法解决冲突得到的哈希表：
T: 0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 哈希函数为H(key)=key,若要查找元素14，探测的次数是（ ） A、 3 B、 6 C、7 D、9 18、在哈希函数H(key)=key%m 中，一般来讲，m应取（ ）
A、奇数 B、偶数 C、 素数 D、充分大的数 19、分块查找的时间性能（ ）
19
A、低于二分查找 B、高于顺序查找而低于二分查找 C、高于顺序查找 D、低于顺序查找而高于二分查找 20、以下说法错误的是（ ）
A、哈希法存储的基本思想是由关键字的值决定数据的存储地址 B、哈希表的结点中只包含数据元素自身的信息，不包含任何指针 C、装填因子是哈希法的一个重要参数，它反映哈希表的装填程度
D、哈希表的查找效率主要取决于哈希表造表时选取的散列函数和处理冲突的方法 21、以下说法正确的是（ ）
A、前序遍历二叉排序树的结点就可以得到排好序的结点序列
B、任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 C、对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的
D、采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要
22、已知采用开放地址法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是（ ） A、将该元素所在的存储单元清空 B、将该元素用一个特殊的符号代替
C、将与该元素有相同Hash地址的后继元素顺次前移一个位置 D、用与该元素有相同Hash地址的最后插入表中的元素替代
23、设哈希表长为M=14，哈希函数H（key）=key。表中已有4个结点：
ADDR(15)=4 ADDR(38)=5 ADDR(61)=6 ADDR(84)=7
其余地址为空，如用二次探测再散列处理冲突，现插入关键字为50的结点的地址应是（ ） A、3 B、8 C、9 D、10
24、有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功所需的平均比较次数为（ ）
A、32/12 B、35/12 C、37/12 D、39/12
25、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应（ ）个结点最佳。
A、25 B、10 C、6 D、625
26、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用（ ）查找方法。
A、分块 B、顺序 C、折半 D、散列 27、深度为6的AVL树至少有（ ）个结点。
A、10 B、12 C、20 D、21 28、哈希表的平均查找长度（ ）
A、与处理冲突的方法有关而与表的长度无关 B、与处理冲突的方法无关而与表的长度有关 C、与处理冲突的方法有关且与表的长度有关 D、与处理冲突的方法无关且与表的长度无关 29、若为查找表长度为m的闭散列表采用二次探测再散列处理冲突，对一个元素第1次计算的哈希地址为d，则第3次计算的哈希地址为（ ）
A、(d+1)%m B、(d-1)%m C、(d+4)%m D、(d-4)%m
30、有数据(49,32,40,6,45,12,56)，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列哪个输入序列（ ）
A、45，12，49，6，40，56，32 B、40，12，6，32，49，45，56 C、6，12，32，40，45，49，56 D、32，12，6，40，45，56，49
31、在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（ ）
A、n B、log2n C、(h+1)/2 D、h
二、 判断题
20
1、 分块查找方法的平均查找长度低于顺序查找，高于折半查找。
2、 采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位
置置为空，因为这会影响以后的查找。
3、 前序遍历二叉排序树的结点就可以得到排好序的结点序列。
4、 在任一二叉排序树上查找某个结点都小于用顺序查找法查找同样结点的线性表的查找时间。 5、 虽然关键字的序列的顺序不一样，但依次生成的二叉排序树却是一样的。 6、 对二棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。 7、 在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空
即可。
8、 在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即
可。
三、 填空题
1、折半查找效率较高，但要求结点（ ）并且要求线性表（ ）；而对于顺序查找，则线性表的存储方式（ ）。
2、假设在有序线性表A[0]—A[9]上进行折半查找，则比较一次查找成功的结点数为（ ），比较二次查找成功的结点数为（ ），比较三次查找成功的结点数为（ ），比较四次查找成功的结点数为（ ），平均查找长度为（ ）。
3、在n个记录的有序顺序表中进行折半查找，最大的比较次数是（ ）。 4、折半查找判定树既是一种（ ），也是一种（ ）。 5、顺序查找法的平均查找长度为（ ）；折半查找法的平均查找长度为（ ）；分块查找法（以顺序查找确定块）的平均查找长度为（ ）；分块查找法（以折半查找确定块）的平均查找长度为（ ）；哈希表查找法采用链接法处理冲突时的平均查找长度为（ ）。
6、对于长度为n的线性表，若进行顺序查找，则时间复杂度为（ ）；若进行折半查找，则时间复杂度为（ ）；若采用分块查找（假定总块数和每块长度均接近n的开方），则时间复杂度为（ ）。 7、用二分法查找一个线性表时，该线性表必须具有的特点是（ ），而分块查找法要求将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间（ ）。 8、采用散列技术来实现查找，需要解决的问题有：（ ）和（ ）。 9、在散列存储中，处理冲突有（ ）和（ ）两类方法。 10、（ ）法构造的哈希函数肯定不会发生冲突。
11、在各种查找方法中，平均查找长度与结点个数无关的查找方法为（ ）。
12、在集合这种逻辑结构中，任何结点之间都不存在________关系，这是集合这种逻辑结构的基本特点。 13、在开散列表上查找键值等于K的结点，首先必须计算该键值的 ，然后在通过指针查找该结点。
14、在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个\索引项\。每个索引项有两个域：块内最大________值和块________位置。
15、索引顺序表上的查找分两个阶段：一、________；二、________。该查找方法称为________查找。 16、二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值________于其左孩子（及其子孙）的键值且________于其右孩子（及其子孙）的键值。
17、在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值________的结点，只需通过结点X的右指针到它的右子树中去找。
18、中序遍历一棵二叉排序树所得的结点访问序列是键值的________序列。
19、二叉排序树上的查找长度不仅与________有关，也与二叉排序树的________有关。
20、二叉排序树的查找效率与树的形态有关。当二叉排序树退化为一条单支树时，查找算法退化为________查找，平均查找长度上升为________。
21、有n个结点的AVL树的深度与________是同数量级的，因而在它上面进行查找的平均查找长度也与________同数量级。
21
22、________查找法的平均查找长度与元素个数n个数无关。
23、在具有20个元素的有序表上进行折半查找，则比较一次查找成功的结点数为________，比较二次查找成功的结点数为________，比较五次查找成功的结点数为________。总的平均查找长度为________。 24、折半查找方法仅适用于这样的表：表中的记录必须________，其存储结构必须是________。
25、考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等于其右子树上的一切结点的值。现把9个数1，2，3，4，5，6，7，8，9填入如图9.1所示的二叉树中，并使之满足上述性质。（圆圈旁边的数字表示插入结点的序号）
1
3 2
4 6 5
8 7 9
图9.1
26、设线性表L=（a1,a2,?,an）(n>2),表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序查找和折半查找与k相等的元素，比较次数分别为s和b ，若检索不成功，则s和b的数量关系是________。 27、某顺序存储的表，其中有10000个元素，已按关键字的值升序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字都不相同。用顺序查找法查找时，查找成功时的平均比较次数为__________，最大比较次数为__________。现把10000个元素按排列顺序划分成若干组，使得每一组中有g个元素（最后一组可能小于g）。查找时，先从头一组开始，通过比较各组的最后一个元素的关键项值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的比较次数最小的g是__________，此时的平均比较次数是__________。
28、长度为225的表，采用分块查找法，每块的最佳长度是__________，应分 块，若每块的长度为10，则平均查找长度为 。
29、已知有序表为(13,17,20,32,48,54,65,79,86,91,97)，当采用折半查找法查找86时需进行 次比较可确定查找成功。查找48时需进行 次比较可确定查找成功，查找100时需进行 次比较才能确定查找不成功。
四、 简答题
1、 简述顺序查找、折半查找和分块检索法对被检索表中元素中的要求。若检索表中每个元素概率相同，
则对一个长度为n的表，用上面三种方法检索时平均查找长度为多少？
2、 画出长度为10的有序表进行折半查找的一棵判定树，并求其等概率下的平均查找长度。
3、 有一个10000项线性表，若采用分区查找，问分成多少块较理想？平均查找长度为多少？若每块为
40 ，则平均查找长度为多少？ 4、 设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key，
采用开放地址法的线性探测再散列方法解决冲突，试在0到18的Hash地址空间中对该关键字序列构造Hash表。
5、 若哈希表的地址范围为0到9，Hash函数为H(key)=(key2+2)mod 9,并采用链地址法处理冲突，画出
元素7，4，5，3，6，2，8，9依次插入哈希表以后该哈希表的状态。
6、 假定有n个关键字，它们具有相同的哈希函数值，用线性探测方法把这n个关键字存入到哈希表中
要做多少次探测？
7、 地址空间为0—14的散列表中，对关键字序列(JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，
SEP，OCT，NOV，DEC)构造哈希函数：H(Key)=?i/2?，其中i为关键字中第一个字母在字母表中的序号。用如下两种处理冲突的方法：（1）线性探测法（2）链地址法
22
分别求出这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。 8、有一个400项的表，欲采用索引顺序查找方法进行查找，问
（1）分成多少块最为理想？（2）每块的理想长度是什么？（3）平均查找长度是多少？ 9、设有一组关键字(19，05，21，24，45，20，68，27，70，11，10)，采用哈希函数：
H(Key)=Key，采用线性探测再散列方法解决冲突，试在0到14的散列地址空间中对该关键字序列构造哈希函数。并求查找成功和不成功时的平均查找长度。 10、线性表的关键字集合(47，26，120，08，39，68，96，23，70，63，57)，已知散列函数为：H(Key)=Key，采用拉链法处理冲突。设计出这种链表结构，并计算该表的查找成功和不成功的平均查找长度。 11、建立一棵具有13个结点的判定树，并求其成功和不成功的平均查找长度值各为多少。
12、分别画出在线性表(06，10，19，24，37，42，50，83)中进行折半查找，查找关键字10和30的过程。 13、设二叉排序树中的关键字由1到100内的整数构成，现要查找关键字为63的结点，下述关键字序列哪一个是不可能在二叉排序树上查找到的序列。
（1）12，25，71，68，33，34，37，63 （2）92，20，91，24，88，25，36，63 （3）95，22，91，24，94，25，63
（4）21，89，77，29，36，38，41，47，63
14、给定表(25，18，48，07，76，52，81，70，92，15)。
（1）试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成之后的二叉排序树。
15、二叉排序树中关键字互不相同，则其中最小元无左孩子，最大元无右孩子，此命题是否正确？最小元和最大元一定是叶子吗？一个新结点总是插在二叉排序树的某叶子上吗？
第十章：内部排序练习题
一、 选择题
1、下述几种排序方法中，平均查找长度最小的是（ ）。
A、插入排序 B、选择排序 C、快速排序 D、归并排序
3、下列排序算法中不稳定的有（ ）。
A、直接选择排序 B、直接插入排序 C、冒泡排序 D、二叉排序 E、Shell排序 F、快速排序 G、归并排序 H、堆排序 I、基数排序
4、内部排序多个关键字的文件，最坏情况下最快的排序方法是（ ），相应的时间复杂度为（ ），该算法是（ ）排序方法。
A、快速排序 B、插入排序 C、归并排序 D、简单选择排序 E、O(nlog2n) F、O(n2) G、O(n2log2n) H、O(n) I、稳定 J、不稳定
5、对初始状态为递增的表按递增顺序排序，最省时间的是（ ）算法，最费时间的算法是（ ）。 A、堆排序 B、快速排序 C、插入排序 D、归并排序 6、下述几种排序方法中，要求内存量最大的是（ ）。
A、插入排序 B、选择排序 C、快速排序 D、归并排序
7、在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序
9、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法为（ ）。 A、快速排序 B、堆排序 C、归并排序 D、直接插入排序
23
10、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列正确位置上的方法，称为（ ）。
A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 11、 每次把待排序的元素划分为左右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间中元素的关键字均大于基准元素的关键字，则此排序方法为（ ）。 A、堆排序 B、快速排序 C、冒泡排序 D、Shell排序
12、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。
A、希尔排序 B、归并排序 C、插入排序 D、选择排序
13、n个记录的直接插入排序所需记录关键码的最大比较次数为（ ）。 A、nlog2n B、n2/2 C、(n+2)(n-1)/2 D、n-1
14、n个记录的直接插入排序所需的记录最小移动次数为（ ）。 A、2(n-1) B、n2/2 C、(n+3)(n-2)/2 D、2n
15、快速排序在（ ）情况下最不利于发挥其长处，在（ ）情况下最易发挥其长处。 A、被排序的数据量很大 B、被排序的数据已基本有序 C、被排序的数据基本无序 D、被排序的数据中最大与最小值相差不大 E、要排序的数据中含有多个相同值。 16、直接插入排序和冒泡排序的平均时间复杂度为（ ），若初始数据有序（正序），则时间复杂度为（ ）。 A、O(n) B、O(log2n) C、O(nlog2n) D、O(n2)
补充选择题
1. 快速排序在最坏的情况下的时间复杂度是（ ）
A 、O(log2n) B、O(n log2n) C、O(n*n) D、O(n*n*n) 2. 具有24个记录的序列，采用冒泡排序最少的比较次数为（ ）
A 、1 B、23 C、24 D、529
3. 用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下：
25 84 21 47 15 27 68 35 20 20 15 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则采用的排序方法是（ ）
A、直接选择排序 B、冒泡排序 C、快速排序 D、二路归并排序 4. 在排序过程中，键值比较的次数与初始序列的排序顺序无关的是（ ）
A、直接插入排序和快速排序 B、直接插入排序和归并排序 C、直接选择排序和归并排序 D、快速排序和归并排序
5. （ ）方法是从未排序序列中依次取出元素与已经排序序列中的元素作比较，将其放入已经排序序列的正确位置上。
A、归并排序 B、插入排序 C、快速排序 D、选择排序 6. （ ）方法是从未排序序列中挑选元素，并将其依次放入已经排序序列的一端。 A、归并排序 B、插入排序 C、快速排序 D、选择排序
7. （ ）方法是对序列中的元素通过适当的位置变换将有关元素一次性的放置在其最终位置上。 A、归并排序 B、插入排序 C、快速排序 D、基数排序
8. 将上万个一组无序并且互不相等的正数序列，存储在顺序存储结构中采取（ ）方法能够最快地找到其中最大的正整数。
A、快速排序 B、插入排序 C、选择排序 D、归并排序 9. 以下四种排序方法，要求附加内存空间最大的是（ ）
A、插入排序 B、选择排序 C、快速排序 D、归并排序
24
10. 以下说法错误的是（ ）
A、直接插入排序的空间复杂度为O(1)。 B、快速排序附加存储开销为O(log2n)。 C、堆排序的空间复杂度为O(n)。
D、二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。 11. 以下不稳定的排序方法是（ ）
A、直接插入排序 B、冒泡排序 C、直接选择排序 D、二路归并排序 12. 以下稳定的排序方法是（ ）
A、快速排序 B、冒泡排序 C、直接选择排序 D、堆排序
2
13. 以下时间复杂性不是O(n)的排序方法是（ ）
A、直接插入排序 B、二路归并排序 C、冒泡排序 D、直接选择排序 14. 以下时间复杂性不是O(nlog2n)的排序方法是（ ）
A、堆排序 B、直接插入排序 C、二路归并排序 D、快速排序 15. 快速排序方法在（ ）情况下最不利于发挥其长处。 A、 要排序的数据量太大 B、 要排序的数据中含有多个相同值 C、 要排序的数据已基本有序 D、 要排序的数据个数为奇
16. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（ ）排序法。 A、起泡排序 B、快速排序 C、堆排序 D、基数排序 17. 快速排序在最坏的情况下的时间复杂度是（ ）
23
A、O(log2n) B、O(nlog2n) C、O(n) D、O(n)
18. 一组记录的关键码为（46，79，56，38，40，84）则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）
A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，79
19. 若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（ ）次比较。
A、33 B、45 C、70 D、91 20. 一组记录的关键字为（32，41，15，39，77，12，48，30，52），按2－路归并排序的方法对该序列进行一趟归并后的结果为（ ）
A、15,32,41,12,39,77,30,48,52 B、12,15,32,39,41,77,30,48,52 C、32,41,15,39,12,77, 30,48,52 D、12,15,30,32,39,41,48,52,77
二、判断题
1． 如果某种排序算法是不稳定的，则该方法没有实际意义。
2． 对于n个记录的集合进行冒泡排序，所需要的平均时间是O（nlog2n）。 3． 对于n个记录的集合进行归并排序，所需要的平均时间是O（nlog2n）。 4． 对于n个记录的集合进行快速排序，所需要的平均时间是O（n）。 5． 堆排序所需的时间与待排序的记录个数无关。
三、填空题 1、在直接插入和直接选择排序中，若初始数据基本有序，则选用（ ），若初始数据基本反序，则选用（ ）。 2、在对一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为（ ），在整个排序过程中共需进行（ ）趟才可完成。 3、n个记录的冒泡排序算法所需最大移动次数为（ ），最小移动次数为（ ）。
25
4、对n个结点进行快速排序，最大比较次数为（ ）。
5、对于直接插入排序、冒泡排序、简单选择排序、堆排序、快速排序有：（1）当文件“局部有序”或文件长度较小时，最佳的内部排序方法是（ ）。（2）快速排序在最坏情况下时间复杂度是（ ）比（ ）性能差；（3）就平均时间而言，（ ）最佳。
6、在堆排序、快速排序和归并排序中，若只从存储时间考虑，则应首先选取（ ）方法，其次选用（ ）方法，最后选用（ ）方法；若只从排序结果的稳定性考虑，则应选取（ ）方法；若只从平均情况下排序最快考虑，则应选取（ ）方法，若只从最坏情况下排序最快并节省内存，则应选取（ ）方法。
四、简答题
1、 简要回答下列问题：
（1） 什么是内部排序、外部排序？（2）什么是排序方法的稳定性？ 2、 已知序列（70，83，100，65，10，32，7，9），请给出采用插入排序、快速排序和冒泡排序方法对
该序列做升序排序的每一趟的结果。
26