《数据结构》填空作业题（答案解析）

范文范例 值得参考

2. 二维数组A[0…9，0…19]采用列序为主方式存储，每个元素占一个存储单元，并且元素A[0，0]的存储地址是200，则元素A[6，12]的地址是 332 。

3. 二维数组A[10…20，5…10]采用行序为主方式存储，每个元素占4个存储单元，并且元素A[10，5]的存储地址是1000，则元素A[18，9]的地址是 1208 。 补充：

1. 一维数组的逻辑结构是 线性结构 ，存储结构是 顺序存储结构 。

2. 对于二维数组或多维数组，分为按 以行为主序 和按 以列为主序 两种不同的存储方式存储。 3. 对矩阵压缩存储是为了 节省存储空间 。

4. 二维数组是一种非线性结构，其中的每一个数组元素最多有 二 个直接前驱（或直接后继）。

第6章 树（已校对无误）

4. 结点最少的树为 只有一个结点的树 ，结点最少的二叉树为 空的二叉树 。

5. 根据二叉树的定义，具有三个结点的二叉树有 5 种不同的形态，它们分别是 。 6. 具有n个结点的完全二叉树的深度为 。

8. 以数据集{4，5，6，7，10，12，18}为结点权值所构造的哈夫曼树为 需用图示 ，其带权路径长度为 165 。

9. 哈夫曼树是带权路径长度 最短 的树，通常权值较大的结点离根 较近 。

10. 在 先序 遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。

第7章 图（已校对无误）

1．n个顶点的连通图至少有 n－1 条边。

2．在无权图G的邻接矩阵A中，若（vi，vj）或〈vi，vj〉属于图G的边集，则对应元素A[i][j]等于 1 ，否则等于 0 。

3. 在无向图G的邻接矩阵A中，若A[i][j]等于1，A[j] [i]等于 1 。

4. 已知图G的邻接表如下图所示，其从顶点v1出发的深度优先搜索序列为v1 v2 v3 v6 v5 v4，其从顶点v1出发的广度优先搜索序列为v1 v2 v5 v4 v3 v6。

V1 V2 V5 V4 ^ v2 v3 V5 ^ v3 V6 ^ v4 ^ word完美 整理版

v5 V4 V6 V3 ^ v6 ^ 范文范例 值得参考

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个记录

word完美 整理版

范文范例 值得参考

45插入到有序表时，为寻找插入位置需比较 5 次。

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

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

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

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

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

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

word完美 整理版