如果位于三角形上的元素a[i][j]存放于b[k]中，那么试给出求得下标值k的计算公式k=f(n,i,j)。对于上例中的a[2][1]，根据计算公式可求得k=5。
答：在三角形中，行号i中元素个数为2i+1，因此，该三角形中0~i -1行的所有元素个数之和=1+3+?+2i - 1=（1+2i-1）*i/2 =i。
设第i行在三角形中的第1个元素的列号为m，则有： i=0,m=2 i=1,m=1 i=2,m=0 ??
归纳起来有：i+m=n/2，即m=n/2 – i，这样： k =i – (n/2 – i)+j
所以，f(n,i,j)=i – (n/2 – i)+j
对于本题图，n=4,i=2,j=1时，k=2*2 – (4/2 – 2)+1=5。
4．特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能？为什么？
答：稀疏矩阵压缩存储后失去了随机存取功能，因为压缩存储采用的三元组（i,j,aij）不是连续的，也就是说，i、j与该三元组在三元组表中的地址没有线性关系，而特殊矩阵在压缩存储后都有这种关系。 5．4．5算法设计题
1.当三对角矩阵采用压缩存储时，写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。
2
2
2
10.4 补充练习题及参考答案
10.4.1 单项选择题
1.在二叉排序树中，凡是新插入的结点，都是没有 的。 A A.孩子 B.关键字 C.平衡因子 D.赋值
2.只有在顺序存储结构上才能实现的查找方法是 法。 B A. 顺序查找 B. 二分查找 C.树型查找 D. 哈希查找
3.在数据元素有序，元素个数较多而且固定不变的情况下，宜采用 法。 A A.二分查找 B.分块查找 C.二叉排序树查找 D.顺序查找
4.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均次数为 。 B
A.35/12 B.37/12 C.39/12 D.43/12
5.有一个有序表R[1?13]={1，3，9，12，32，41，45，62，75，77，82，95，100}，当用二分查找法查找值为82的结点时，经 次比较后查找成功。 C A.1 B.2 C.4 D.8
6.如图10.4(a)所示的一棵二叉排序树，其不成功的平均查找长度是 。 A A.21/7 B.28/7 C.15/6 D.21/6
7.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定节点所在的块，则每块分为 个结点最佳。 B A.9 B.25 C.6 D.625 8.具有5层结点的AVL树至少有 个结点。 B A.10 B.12 C.15 D.17
9.下面关于B-树和B+树的叙述中，不正确的结论是 。 A
A. B-树和B+树都能有效地支持顺序查找 B. B-树和B+树都能有效地支持随机查找
11
C. B-树和B+树都是平衡的多分树 D. B-树和B+树都可用于文件索引结构 10.设有n个关键字，散列查找法的平均查找长度是 。 A A.O(1) B.O(n) C.O(lbn) D.O(n)
11.设哈希表的长m=14，哈希函数H(key)=key mod 11。表中已有4个结点addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空。如用二次探测再散列法处理冲突，则关键字为49的结点的地址是 。 D
A.8 B.3 C.5 D.9 12.散列表的平均查找长度 。 A
A.与处理冲突方法有关而与表的长度无关 B.与处理冲突方法无关而与表的长度有关 C.与处理冲突方法有关而与表的长度有关 D.与处理冲突方法无关而与表的长度无关 10.4.2 填空题
1.衡量查找算法性能好坏的主要标准是 。 答：关键字的比较次数 2.为了实现分块查找，线性表必须采用 方法存储。 答：索引
3.对二叉排序树进行 遍历，可以得到按关键字从小到大排列的结点序列。 答：中序 4.在高度为h含n个结点的二叉排序树上查找一个关键字至多比较次数为 。 答：h
5.在一个10阶的B-树上，每个树根结点中所含的关键字的数目最多允许为 ① 个，最少允许为 ② 个。 答：m=10，[m/2]≤j≤m-1，即4≤j≤9，本题答案为：① 9 ② 4
6.当向B-树中插入关键字时，可能引起节点的 ① ，最终可能导致整个B-树的高度 ② ，当从B-树中删除关键字时，可能引起节点 ③ ，最终可能导致整个B-树的高度 ④ 。 答：① 分裂 ② 增加1 ③ 合并 ④减少1
7.采用哈希存储方法时，用于计算节点存储地址是 。 答：哈希函数 8.评价哈希函数好坏的标准是 。 答：哈希函数取值是否均匀
9.在各种查找方法中，其平均查找长度与节点个数n无关的查找方法是 。 答：哈希表查找法 10.在散列存储中，装填因子α的值越大，则 ① ；α的值越小，则 ② 。
答：由散列查找法可知本题答案为：① 存取元素时发生冲突的可能性就越大 ②存取元素时发生冲突的可能性就越小 10.4.3 判断
1.判断以下叙述的正确性。
⑴顺序查找方法只能在顺序存储结构上进行。 ⑵二分查找可以在有序的双向链表上进行。 ⑶分块查找的效率与线性表被分成多少块有关。 ⑷二叉排序树是用来进行排序的。
⑸在二叉排序树中，每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小。
⑹每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小，这样的二叉树都是二叉排序树。 ⑺在二叉排序树中，新插入的关键字总是处于最底层。 ⑻在二叉排序树中，新结点总是作为树叶来插入的。 ⑼二叉排序树的查找效率和二叉排序树的高度有关。 ⑽在平衡二叉排序树中，每个结点的平衡因子值是相等的。 ⑾在平衡二叉排序树中，以每个分支结点为根的子树都是平衡的。 ⑿哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。 ⒀哈希冲突是指同一个关键字对应多个不同的哈希地址。
⒁哈希查找的过程中，关键字的比较次数和哈希表中关键字的个数直接相关。
⒂在用线性探测法处理冲突的哈希表中，哈希函数值相同的关键字总是存放在一片连续的存储单元中。 答：⑴错误。顺序查找方法也可以在顺序存储结构上进行。
12
2
⑵错误。二分查找只能在可以进行随机查找的存储结构上进行，即只能顺序存储的有序表上进行。 ⑶正确。 ⑷错误。二叉排序树主要用于改进一般二叉树的查找效率。
⑸正确。 ⑹错误。对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字；右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字进行比较。 ⑺错误。 ⑻正确。 ⑼正确。 ⑽错误。每个结点的平衡因子值的绝对值小于2。 ⑾正确。 ⑿正确。每个元素的存储位置通过哈希函数和解决冲突的方法得到。 ⒀错误。哈希冲突是指多个不同一个关键字对应相同的哈希地址。 ⒁错误。只与装填因子有关。 ⒂错误。不一定。 2. 判断以下叙述的正确性。
⑴。用顺序表和单链表表示的有序表均可使用二分查找方法来提高查找速度。
⑵有n个数存放在一堆数组A[1?n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。
⑶若哈希表的装填因子α<1，则可避免冲突的产生。
⑷二叉排序树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。 ⑸在二叉排序树上删除一个节点时，不必移动其他结点，只要将该结点的父亲结点的相应指针域置空即可。 ⑹哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法。 ⑺对二叉排序树的查找都是从根节点开始的，则查找失败一定落在叶子上。 答：⑴错误。链表表示的有序表不能用二分查找法查找。
⑵错误。因顺序查找既适合于有续表也适合于无序表。对这两种表，若对每个元素的查找概率相等，则顺
n?1序查找的ASL相同，并且都是2；对于查找概率不同的情况，则按查找概率由大到小排列的无序表其ASL要比有序表的ASL小。
⑶错误。α越小则只能说明发生冲突的概率越小，但仍有可能发生冲突。 ⑷正确。 ⑸错误。如果删除的是非树叶结点，则必须调整某些结点，使调整后的二叉树仍为二叉排序树。 ⑹正确。 ⑺错误。若非叶子结点无左子树或无右子树时，也都可以是查找失败的外部节点。 10.4.4 简答题
1.试述顺序查找法、二分查找法和分块查找法对被查找的表中元素要求。对长度为n的表来说，三种查找法在查找成功时的平均查找长度各是多少？
2.试问含有8个关键字的3阶B-树最多有几个结点？最少有几个结点？画出其形态。 3.已知一棵3阶B-树如图10.7所示，画出在其中插入关键字18的过程。
图10.7 一棵3阶B-树
4.证明二叉排序树的中序遍历序列是从小到大有序的。
5.某人认为他发现了二叉树的一个重要性质。假设二叉树中对某关键字K的查找在一叶结点处结束，考虑三个集合：集合A包含查找路径左边的关键字；集合B包含查找路径上的关键字；集合C包含查找路径右边的关键字。他由此认为：任何三个关键字a，b，c，a∈A，b∈B，c∈C，都满足a≤b≤c。你认为正确，请说明理由；认为不正确，则给出一个反例并加以说明。
13
9.4 补充练习题及参考答案
9.4.1 单项选择题
1. 所谓简单路径是指 。B
A.任何一条边在这条路径上不重复出现 B.任何一个定点在这条路径上不重复出现 C.这条路径由一个顶点序列构成，不包含边 D.这条路径由一个变得序列构成，不包含顶点 2. 带权有向图G用邻接矩阵A存储，则vi的入度等于A中 。 D A.第i行非∞的元素之和 B.第i列非∞的元素之和 C.第i行非∞且非0的元素个数 D.第i列非∞且非0的元素个数 3.无向图的邻接矩阵是一个 。 A
A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵 4.在一个无向图中，所有顶点的度之和等于边数的 倍。 C A.1/2 B.1 C.2 D.4 5.一个有n个顶点的无向图最多有 条边。 C
A. n B. n(n-1) C. n(n-1)/2 D. 2n A. 5 B. 6 C. 7 D.8 A. n B. n+1 C. n-1 D.n/2
6.具有6个顶点的无向图至少应有 几条边才能确保是一个连通图。 A 7.在一个具有n个顶点的无向图中，要联通全部顶点至少需要 条边。 C 8.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是 。 D
A. n B. (n?1) C. n-1 D. n
229.一个有向图G的邻接表存储如图9.2所示，现按深度优先搜索遍历，从v1出发，所得到的顶点序列是 。 B
V3 V4 V1 V2 A. 1，2，3，4，5 B. 1，2，3，5，4 C. 1，2，4，5，3 D. 1，2，5，3，4
2 3 5 3 5 4 Λ Λ Λ Λ 4 Λ V5 图 9.2 有向图G的邻接表 10.对图9.3所示的无向图，从顶点v1开始进行深度优先遍历，可得到顶点的访问序列 。
A. 1，2，4，3，5，7，6 B. 1，2，4，3，5，6，7 C. 1，2，4，5，6，3，7 D. 1，2，3，4，5，7，6
答：选项B中从顶点5到顶点6不符合深度优先遍历规则；选项C中从顶点5到顶点6不符合深度优先遍历规则；选项D中从顶点2到顶点3不符合深度优先遍历规则。答案为A。
14
2 5 1 4 7
3 图9.3
6
11.对图9.3所示的无向图，从V1开时进行广度优先遍历，可得到顶点访问序列 。
A. 1，3，2，4，5，6，7 B. 1，2，4，3，5，6，7 C. 1，2，3，4，5，6，7 D. 2，5，1，4，7，3，6
答：选项B中124子序列不符合广度优先遍历规则；选项C中457子序列不符合广度优先遍历规则；
选项D中从2开始不符合广度优先遍历规则。答案为A
12.在图9.4所示的有向图中，存在一个强连通分量G=（V，E），其中， A 。
A. V={v2，v3，v5，v6}
E={
E={
E={
E={
13.如果从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点图一定是（Ｂ） Ａ完全图 Ｂ连通图 Ｃ有回路 Ｄ一棵树
14．采用邻接表存储的图的深度优先遍历算法类似于二叉树的 _____ 算法 （A） A前序遍历 B中序遍历 C后序遍历 D按层遍历
15采用邻接表存储的图的广度优先遍历算法类似于二叉树的 _____ 算法 （D） A前序遍历 B中序遍历 C后序遍历 D按层遍历 16任何一个无相连通图_________ 最小生成树 （B）
A只有一棵 B有一棵或多棵 C一定有多棵 D可能不存在 17一个无向连通图的生成树是含有该连通图的全部顶点的_______（A）
A极小连通子图 B极小子图 C极大联通子图 D极大子图 18判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用_____ （A）
A求关键路径的方法 B求最短路径的迪克斯特方法 C广度优先遍历算法 D深度优先遍历算法 19若一个有向图中的顶点不能排成一个拓扑序列，则可判定该有向图______ D
A是个有根有向图 B是个强连通图 C含有多个入度0的顶点 D含有定点数目 大于1的强联通分量
20 对于含有n个顶点的带权连通图，他的最小生成树是指途中任意一个_____ D A由n-1条权值最小的便构成的子图 B由n-1条权值之和最小的边构成的联通子图 C由n-1条权值之和最小的边构成的联通子图 D由n个顶点构成的边的权值之和最小的联通子图
21若图的连接矩阵中主对角线上的元素全是0，其余元素全是1，则可以断定该图一定是_______ D A无向图 B不是带权图 C有向图 D完全图 22关键路径是事件是事件结点网络中______ A
A从源点到汇点的最长路径 B从源点到汇点的最短路径 C最长的回路 D最短的回路 23设有无向图G=（V，E）和G’=(V’,E’),如G’是G的生成树，则下面不正确的说法是_____ A A G’是G的连通分量 B G’是G的无环子图 C G’是G的子图 D G’为G的极个连通子图且V’=V
15