9
《数据结构》填空作业题答案
第 1 章 绪论 （已校对无误）
1．数据结构包括 数据的逻辑结构 、 数据的存储结构 和 数据的运算 三方面的内容。
2．程序包括两个内容： 数据结构 和 算法 。
3. Data Structure =（ D， S） 。 数据结构的形式定义为：数据结构是一个二元组：4. 数据的逻辑结构在计算机存储器内的表示，称为数据的 存储结构 。
5. 结构两大类。 线性 结构和 非线性 数据的逻辑结构可以分类为6. 在图状结构中，每个结点的前驱结点数和后继结点数可以 。 有多个7. 的关系。 一对多 在树形结构中，数据元素之间存在 8.中的标识（映象），也即数据的物理结构，指数据元素在 存储结构 。 计算机 9.图形结构 3 种类型，树型结构和有向 、和 数据的逻辑结构包括 线性结构 树形结构 。图结构合称为 非线性结构
连续 10. 顺序存储结构是把逻辑上相邻的结点存储在物理上 的存储单元里，结点之间的逻辑
关系由存储单元位置的邻接关系来体现。
任意 链式存储结构是把逻辑上相邻的结点存储在物理上11. 的存储单元里，节点之间的逻辑 关系由附加的指针域来体现。
12. 数据的存储结构可用 4 种基本的存储方法表示，它们分别是 顺序存储 、 链式存储 、 索引存储 和 散列存储 。
一 的，非线性结构反映结点间的逻辑关系是 一对一 线性结构反映结点间的逻辑关系是13. 对多或多对多 。
存储结构。 14. 数据结构在物理上可分为顺序 存储结构和链式
方式，还给出了处理数 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示 实现方法据的 。
16. 数据元素可由若干个组成。数据项
复杂度。空间 复杂度和 算法分析的两个主要方面是时间17.
一个算法的时间复杂度是用该算法所消耗的时间 的多少来度量的，一个算法的空间复杂18. 的大小来度量的。度是用该算法在运行过程中所占用的存储空间
19. 算法具有如下特点：有穷性 、确定性、、输入、输出。可行性
20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切 内计算出结果。有穷时间的定义，并在
㏒ 下面程序段的时间复杂度为21. 3n 。
1
9
i=1 ；
while(i<=n)
；﹡3i= i
（已校对无误）第 2 章 线性表
ai+1 ，?，an），其中每个 ai 代表一个 数据元素（或ai 1. 一线性表表示如下：（a1 ，a2，? ，ai-1，，
结点， i 称为 ai 。位置（或序号） 在线性表中的 。结点） a1 称为 起始 结点， an 称为 终端
。后继 称为 ai 的直接 ）， ai，ai+1 ，（1≤i ≤nai 称为 ai+1 的直接 前驱 ，ai+1 对任意一对相邻结点2. O(n) 对一个长度为 n 的线性表，要删除第 i 个元素，则在顺序表示的情况下， ， 计算复杂性为
。在链式表示的情况下，计算复杂性为 O(1)
3. n
在一个长度为 n 的顺序表中，向第 i 个元素（ 1≤ i≤n）之前插入一个新元素时， 需向后移动
1
个元素。－i ＋ 4. 顺序表中逻辑上相邻的元素在物理位置上 相连。 一定n/2 5. 个结点，具体的移动次数取决于 表 在 n 个结点的顺序表中插入一个结点需平均移动 和插入位置 i 。长 n
6. O(1)
在顺序表中访问任意一个结点的时间复杂度均为 ，因此，顺序表也称为 随机访问
的数据结构。 7. 和随机访问 。空间利用率高 顺序表相对于链表的优点有O(n)
8. 在长度为 n 的顺序表中插入一个元素的时间复杂度为。
9. 在带有头结点的单链表 L 中，若要删除第一个结点， 则须执行下列三条语句： U＝ L->next ；
）。L->next=U->next ；free（U
10. 链表相对于顺序表的优点有插入 和 删除 操作方便。
结点中的指针指示。 在单链表中除首结点外，任意结点的存储位置都由直接前驱 11.
它的直接前驱结点的地址 ，其时间复 ，需找到*p 在12. n 个结点的单链表中要删除已知结点
O(n)
杂度为 。
13．单链表中设置头结点的作用是 简化操作，减少边界条件的判断。
14．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的 前驱 结点。
。 后续结点 15. 在双链表中，每个结点有两个指针域，一个指向 前驱结点，另一个指向
16. 带头结点的单链表 L 为空的判定条件是 L -> next==NULL ，不带头结点的单
链表 L 为空的判定条件是
L==NULL 。
17. 在单链表中，指针 p 所指结点为最后一个结点的条件是 。p-> next==NULL
2
9
18. 循环链表的最大优点是 从表中任意结点出发都可访问到表中每一个元素（或从表中任意结 点出发都可遍历整个链表） 。
19. 设 rear 是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的存储位置是 rear->next->next 。
20. 为空表的条件是 L -> prior== L -> next 。带头结点的双向循环表 L
21.头指针 才能遍 在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道 历整个链表。 22. n 个元素的有序表归并成一个有序表，其最少的比较次数是 。1 将两个各有
（已校对无误） 第 3 章栈和队列
1. 表，队列又称为 表。先进先出 栈又称为 后进先出
2. 向一个顺序栈插入一个元素时， 首先使 栈顶指针 写入 后移一个位置， 然后把待插入元素 （或插入） 到这个位置上。
3. 从一个栈删除元素时，需要前移一位 。 栈顶指针
4. 在一个顺序栈中，若栈顶指针等于 － 1 ，则为空栈；若栈顶指针等于 maxSize－1 ，则为满栈。
5. 在一个链式栈中，若栈顶指针等于 NULL ，则为 空栈 ；在一个链式队列中，若队头指针与 队尾指针的值相同，则表示该队列为 空 或该队列 只含有一个结点 。
6. 向一个链式栈插入一个新结点时， 首先把栈顶指针的值赋给 新结点的指针域 ，然后把新结点的存储位置赋给
栈顶指针 。
7．在求表达式值的算符优先算法中使用的主要数据结构是 栈 。
8．设有一个顺序栈 S，元素 s1， s2，s3， s4，s5， s6 依次进栈，如果 6 个元素的出栈顺序为 s2，
。，则顺序栈的容量至少为 3 s3， s4，s6， s5，s1
9. 设有一个空栈，现输入序列为 1，2，3，4，5。经过 push，push，pop，push，pop，push，pop， push
后，输出序列是 2 3 4 。
10. 在按算符优先法求解表达式 3－1＋5*2 时，最先执行的运算是 * ，最后执行的运算是 － 。
11. 在栈的 ADT 定义中，除初始化操作外，其他基本操作的初始条件都要求 栈存在 。
12. 。 仅允许在同一端进行插入和删除的线性表称为栈
13. 在顺序栈 s 中，栈为空的条件是 s.top==s.base ，栈为满的条件是 s.top－ s.base＞=s.stacksize 。
。后缀表示 yb/cd －＋ x*a －，该表达式的前缀表示为）－（＋设有算术表达式14. x a* y－b c/d * xayb为－＋cd/－。
15. 1234，为了得到 1342 出栈顺序， X S 用表示入栈操作，表示出栈操作，若元素入栈顺序为
X S相应的、操作串为 SXSSXSXX 。16. p
top 向一个栈顶指针为的链式栈中插入一个新结点＝ top 时，应执行 *p 和top ＝p->link 3
9
操作。
17. 从一个栈顶指针为 top 的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 top＝top->link 操作。
18. 设有一个空栈，栈顶指针为 1000H（十六进制。现有输入序列为 1，2，3，4，5，经过 PUSH，
PUSH，POP， PUSH，POP，PUSH， PUSH 之后，输出序列是 2，3 ，而栈顶指
针是 100C H。
设栈为顺序栈，每个元素占 4 个字节。
19. 在作入栈运算时应先判别栈是否 满 ；在作出栈运算时应先判别栈是否 空 。
10. 用一个大小为 1000 的数组来实现循环队列，当前 rear 和 front 的值分别为 0 和 994，若要达到队
满的条件，还需要继续入队的元素个数是 993 。
20. 队列的插入操作在 队尾 进行，删除操作在 队头 进行。
21. 在一个循环队列 Q 中，判断队空的条件为 Q.front==Q.rear ，判断队满的条件为 (Q.rear
＋ 1)％maxSize==Q.front 。
22. 向一个循环队列中插入元素时，需要首先移动 队尾指针 ，然后再向所指位置 写入（或
插入） 新插入的元素。
23. 当用长度为 n 的数组顺序存储一个栈时，若用 top==n 表示栈空，则表示栈满的条件为
top==0 。
24. 循环队列的引入，目的是为了克服 假溢出时大量移动数据元素 。
第 4 章 串（已校对无误）
1. 两个串相等的充分必要条件是 两个串的长度相等且对应位置的字符相同。
2. 空格串是 由一个或多个空格字符组成的串 ，其长度等于 其包含的空格个数 。
3. 01122341
函数值为模式串′ abaabade′的 next
补充：
1. 串的两种最基本的存储方式是 顺序存储方式和链接存储方式 。
2. 空串是 零个字符的串 ，其长度等于 零 。
3. 组成串的数据元素只能是字符 。
4. 串是一种特殊的线性表，其特殊性表现在其数据元素都是字符 。
第 5 章 数组 （已校对无误）
1. 将下三角矩阵 A[1 .. 8，1.. 8]的下三角部分逐行地存储到起始地址为 1000 的内存单元中，已知每个
元素占 4 个单元，则元素 A[7 ，5]的地址为 1100 。
2. 二维数组 A[0 ?9，0? 19]采用列序为主方式存储，每个元素占一个存储单元，并且元素 A[0 ，0]的
12]的地址是 。332 ，存储地址是 200，则元素 A[6
，10]?采用行序为主方式存储，每个元素占 A[10 个存储单元，并且元素4 520 A[1 03. 二维数组?，
5] 1208 A[18 1000的存储地址是，则元素。 9]，的地址是 4
9
补充：
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. 。A[j] [i] 等于 1 1中，若在无向图 G 的邻接矩阵 A A[i][j] 等于， v1 v2 v3 v6 v5 v4 的邻接表如下图所示，其从顶点 ，其从出发的深度优先搜索序列为v1 G 4. 已知图 顶点 v1 出发的广度优先搜索序列为 v1 v2 v5 v4 v3 v6。
V1
V5 V4
^
V5 ^
v3 v2
V6 v3 ^
v4 ^
V3 V6
v5 ^ V4
v6 ^
V2
5
9
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. O(n)
的线性表，若进行顺序查找，则时间复杂度为对于长度为 n ；若采用二分法查找，则时间
2
㏒复杂度为 O( ），则时间复杂度为n 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
9
5. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是
快速排序 ，需要内存容量最多的是 基数排序 。
6. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用 堆排序 ，若原始记
录无序，则最好选用 快速排序 。
7. 在插入排序和选择排序中，若初始数据基本正序，则选用 插入排序 ；若初始数据基本反序，则选用 选择排序 。
8. 对 n 个元素的序列进行冒泡排序时，最少的比较次数是 n－1 。
9. 基数 排序不需要进行记录关键字间的比较。
7
建筑装潢资料 教育培训 学习资料 考试专业资料．
9
