《数据结构》填空作业题(答案)知识讲解

5. 设x，y是图G中的两顶点，则（x，y）与（y，x）被认为 无向 ，但〈x，y〉与〈y，x〉是 有向 的两条弧。

6. 已知一个图的邻接矩阵表示，删除所有从i个结点出发的边的方法是 将矩阵的第i行全部置为0 。 7. 在有向图的邻接矩阵上，由第i行可得到第 i 个结点的出度，而由第j列可得到第 j 个结点的入度。

8. 在无向图中，如果从顶点v到顶点v′有路径，则称v和v′ 是 连通 。

第8章 查找（已校对无误）

1. 顺序查找法的平均查找长度为 （n＋1）/2 ；哈希表查找法采用链接法处理冲突时的平均查找长度为 1＋？ 。

2. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 哈希表查找法 。 3. 二分查找的存储结构仅限于 有序的顺序存储结构 。 4. 长度为255的表，采用分块查找法，每块的最佳长度是 15 。

5. N个记录的有序顺序表中进行折半查找，最大的比较次数是 ㏒2N ？ 。

6. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为 O(n) ；若采用二分法查找，则时间复杂度为 O(㏒2n) ；若采用分块查找（假定总块数和每块长度均接近n），则时间复杂度为 O(n) 。

7. 在散列存储中，装填因子a的值越大，则 存取元素时发生冲突的可能性就越大 ；a的值越小，则 存取元素时发生冲突的可能性就越小 。

8. 对于二叉排序树的查找，若根结点元素的键值大于被查元素的键值，则应该在二叉树的 左子树 上继续查找。

9. 高度为8的平衡二叉树至少有 54 个结点。 10. 在散列函数H（key）=key % p中，p应取 素数 。

第9章 排序（已校对无误）

1. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第8个记录45插入到有序表时，为寻找插入位置需比较 5 次。

2. 对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为 60的关键字开始。

3. 对n个记录的表r[1…n]进行简单选择排序，所需要进行的关键字间的比较次数为 n(n－1)/2 。 4. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有 希尔排序、选择排序、快速排序、堆排序 。

6

5. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是 快速排序 ，需要内存容量最多的是 基数排序 。

6. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用 堆排序 ，若原始记录无序，则最好选用 快速排序 。

7. 在插入排序和选择排序中，若初始数据基本正序，则选用 插入排序 ；若初始数据基本反序，则选用 选择排序 。

8. 对n个元素的序列进行冒泡排序时，最少的比较次数是 n－1 。 9. 基数 排序不需要进行记录关键字间的比较。

7