《数据结构》填空作业题答案第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. 一线性表表示如下： （a 1，a 2，⋯ ，a i-1，a i ，a i+1，⋯ ，a n ），其中每个 a i 代表一个 数据元素（或结点）。
a 1点， a n点， i a i性表中的 位置（或序号） 。
对任 ai，ai+1，（1≤ i ≤ n ），a i a i +1 的直接，a i +1a i 的直接。
n性表除第i 个元表示的情况O(n) ， 式表示的情况O(1) 。
3. 在n 序表中， 向第 i 个元素（1≤ i ≤ n ）之前插入一个新， 需向n －i ＋1 个元素。
序辑的元素物理位置上 一定。
5. 在 n 序表中插入需平n /2，具体次数取决于 表 长n 和插入位置 i 。
6.序问任意O (1) 因序表问 的构。
序点有 问和利用率高 。
8.n 序表中插入一个元O(n) 。
9.结 L 中，除第行下列句： U ＝ L->next ； L->next=U->next ；free （U ）。
1序点有 插入除 操作方便。
11.链表中点外点位置都由直结点中指示。
12. 在 n 链表除点 *，需找到 它的直结点的地址 O(n) 。
1 链结点作化操作，界条件的判断 。
1 4结链除某一结点的结点。
15. 表中，点有两域，一个指向 ，另一个指向 。
1空的判定条件是 L -> n e x t ==N U L L 定条件是 L==NULL 。
17.链表中p 最后点的条件是 p-> next==NULL 。
218. 循环链表的最大优点是从表中任意结点出发都可访问到表中每一个元素（或从表中任意结点出发都可遍历整个链表）。
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＝p17. 从t o p 点并不需要和， 行 top ＝top->link 操作。
1有一为1000H （1，2，3，4，过P USH ， P U S H ，P O P ，P U S H ，P O P ，P U S H ，P U S H 之出序列是 23 是 100C H 。
，每个元素占4 。
19. 在应栈；应栈是否 空 。
10.用一个1000 队列，当前 r e a r 和 f r o n t 为0 和 994，若要达到队 满的条的元素个数是 993 。
2列的插入操除操行。
21. 在一 Q 中，空的Q .f r o n t ==Q .r e a r ，满的(Q.rear ＋1)％maxSize==Q.front 。
22. 向一队列中插入，需要首队，然后再向所指位置 写入（或 插入） 新插入的元素。
23.n 顺时，若用 t o p n 满的条件为 top==0 。
24.队列的引入，目了克服 假大数据元素 。
第 4 章 串（） 1. 两个串相等的充分必要条件是 两个度相应位置的字符相同 。
2. 空格串是 由一个或多个空格成的串度等于 其包含的空格个数 。
3. 模式串′ a b a a b a d e ′的n e x t 为01122341 补充： 1. 串的两种最基本方方方式 。
2. 空串是 零个字符的串 度等于 零 。
成串的数据元素只能是 字符 。
4. 串是一种特性表，其特殊在 其数据元素都是字符 。
第5 章（） 1. 将下三A [1 .. 8，1.. 8]的下三角部元素占 4元素 A [7，5]的1100 。
2.A [0 ⋯9，0⋯ 19]采用主方，每个元地址是 20元素 A[6 ，12]的地址是 332 。
3.A [1 0⋯ 20，5⋯ 10]采用主方5]地址是100元素 A[18，9]的地址是 1208 。
41. 一维数组的逻辑结构是线性结构，存储结构是顺序存储结构。
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。
V1V2 V5 V4 ^v2v3 V5 ^v3 V6 ^v4 ^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 无关的查找方法是 哈希表查找法。
