《数据结构》填空作业题(答案).doc

《数据结构》填空作业题答案
第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 。
i=1；
while(i<=n)
i= i﹡3；

第2章 线性表（已校对无误）
1. 一线性表表示如下：（a1，a2，…，ai-1，ai，ai+1，…，an），其中每个ai代表一个 数据元素（或结点） 。a1称为 起始 结点，an称为 终端 结点，i称为ai在线性表中的 位置（或序号） 。对任意一对相邻结点ai，ai+1，（1≤i≤n），ai称为ai+1的直接 前驱 ，ai+1称为ai的直接 后继 。
2. 对一个长度为n的线性表，要删除第i个元素，则在顺序表示的情况下，计算复杂性为 O(n) ，在链式表示的情况下，计算复杂性为 O(1) 。
3. 在一个长度为n的顺序表中，向第i个元素（1≤i≤n）之前插入一个新元素时，需向后移动 n－i＋1 个元素。
4. 顺序表中逻辑上相邻的元素在物理位置上 一定 相连。
5. 在n个结点的顺序表中插入一个结点需平均移动 n/2 个结点，具体的移动次数取决于 表长n和插入位置i 。
6. 在顺序表中访问任意一个结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机访问 的数据结构。
7. 顺序表相对于链表的优点有 随机访问 和 空间利用率高 。
8. 在长度为n的顺序表中插入一个元素的时间复杂度为 O(n) 。
9. 在带有头结点的单链表L中，若要删除第一个结点，则须执行下列三条语句： U＝L->next ；L->next=U->next；free（U）。
10. 链表相对于顺序表的优点有 插入 和 删除 操作方便。
11. 在单链表中除首结点外，任意结点的存储位置都由 直接前驱 结点中的指针指示。
12. 在n个结点的单链表中要删除已知结点*p，需找到 它的直接前驱结点的地址 ，其时间复杂度为 O(n) 。
13．单链表中设置头结点的作用是 简化操作，减少边界条件的判断 。
14．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的 前驱 结点。
15. 在双链表中，每个结点有两个指针域，一个指向 前驱结点 ，另一个指向 后续结点 。
16. 带头结点的单链表L为空的判定条件是 L->next==NULL ，不带头结点的单链表L为空的判定条件是 L==NULL 。
17. 在单链表中，指针p所指结点为最后一个结点的条件是 p->next==NULL 。
18. 循环链表的最大优点是 从表中任意结点出发都可访问到表中每一个元素（或从表中任意结点出发都可遍历整个链表） 。
19. 设rear是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的存储位置是 rear->next->next 。
20. 带头结点的双向循环表L为空表的条件是 L->prior== L->next 。
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，s3，s4，s6，s5，s1，则顺序栈的容量至少为 3 。
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 。
14. 设有算术表达式x＋a*（y－b）－c/d，该表达式的前缀表示为 －＋x*a－yb/cd 。
后缀表示为 xayb－*＋cd/－ 。
15. 用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S、X操作串为 SXSSXSXX 。
16. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行 p->link＝top 和 top＝p 操作。
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. 模式串′abaabade′的next函数值为 01122341
补充：
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]的存储地址是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

v3

v4 ^

v5

v6 ^
V2
V5
V4 ^
v3
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) ；若采用分块查找（假定总块数和每块长度均接近），则时间复杂度为 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. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有 希尔排序、选择排序、快速排序、堆排序 。
5. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是 快速排序 ，需要内存容量最多的是 基数排序 。
6. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用 堆排序 ，若原始记录无序，则最好选用 快速排序 。
7. 在插入排序和选择排序中，若初始数据基本正序，则选用 插入排序 ；若初始数据基本反序，则选用 选择排序 。
8. 对n个元素的序列进行冒泡排序时，最少的比较次数是 n－1 。
9. 基数 排序不需要进行记录关键字间的比较。
7