完整word版数据结构填空作业题答案

1、数据结构填空作业题答案 第1章 绪论（己校对无谋）1数据结构包括 数据的逻辑结构、 数据的 存储结构和数据的运算三方面的内容。 2.程序包括两个内容：数 据结构和算法o 3. 数据结构的形式定义为：数据结构是一个元组：Data Stmctiwe = （D, S）。 4. 数据的逻辑结构在计算机存储器内的表示，称为数据的 存储结构。 5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。 6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。 7. 在树形结构中，数据元素之间存在 一对多 的关系。 8. 数据的物理结构，指数据元素在 计算机 中的标识（映象），也即 存储结 构 。

2、9 数据的逻辑结构包括线性结构、树形结构和图形结构3种类型, 树型结构和有向图结构合称 为非线性结构。 10 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里, 结点之间的逻辑关系曲存储单元位置的邻接关系来体现。 11链式存储结构是把逻辑上相邻的结点存储在物理上 任意 的存储单元里, 节点之间的逻辑关系由附加的指针域来体现。 12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链 式存储、索引存储和散列存储。 13. 线性结构反映结点间的逻辑关系是 一对一 的，非线性结构反映结点间的 逻辑关系是_对多或多对多o 14. 数据结构在物理上可分为顺序存储结构和链式存储

3、结构。 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的 表示 方式, 还给出了处理数据的实现方法。 16. 数据元素可山若干个 数据项 组成。 17. 算法分析的两个主要方面是 时间 复杂度和 空间 复杂度。 18. 个算法的时间复杂度是用该算法 所消耗的时间 的多少来度量的，一个 算法的空间复杂度是用该算法在运行过程中所占用的 存储空间的大小来度量的。 19. 算法具有如下特点： 有穷性、确定性、 可行性、输入、输出。 20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有 它的确切 的定义，并在有穷时间内计算出结果。 21. 下面程序段的时间复杂度为log

4、 11 O 3.一 1 i=l： while(iiiext ； L-iiext=U-next； free (U)o 10. 链表相对于顺序表的优点有插入和删除操作方便。 11在单链表中除首结点外，任意结点的存储位置都山 直接前驱 结点中的指 针指示。 12.在n个结点的单链表中要删除已知结点*p,需找到 它的直接前驱结点的地 址,其时间复杂度为0(n) o 13单链表中i殳置头结点的作用是 简化操作，减少边界条件的判断。 14. 在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的 前 驱 结点o 15. 玉龙链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向 后续结点 o

5、16. 带头结点的单链表L为空的判定条件是L-next=NULL，不带头结点的单 链表L为空的判定条件是L=NULL o 17. 在单链表中，指针p所指结点为最后一个结点的条件是p-next=NULL。 18. 循环链表的最大优点是从表中任意结点出发都可访问到表中每一个元素 （或从表中任意结 点出发都可遍历整个链表）o 19. iS rear是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的存 储位置是 rear-iiext-iiext 。 20. 带头结点的双向循环表L为空表的条件是L-prior= L-next。 21. 在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需

6、知道 头指针才能遍历整个链表。 22. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是1 。 第3章 栈和队列（已校对无谋）1 栈乂称为 后进先出 表，队列乂称为 先 进先出 表。 2. 向一个顺序栈插入一个元素时，首先使 栈顶指针 后移一个位置，然后把 待插入元素 写入（或插入） 到这个位置上。 3从一个栈删除元素时，需要前移一位栈顶指针。 4. 在一个顺序栈中，若栈顶指针等于 一1 ,则为空栈； 若栈顶指针等于 maxSize-1,则为满栈。 5. 在一个链式栈中，若栈顶指针等于NULL,则为空栈；在一个链式队列 中，若队头指针与队尾指针的值相同，则表示该队列为 空 或该队

7、 列只含有_个结点O 6向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针 域,然后把新结点的存储位置赋给栈顶指针。 7. 在求表达式值的算符优先算法中使用的主要数据结构是栈。 8设有一个顺序栈S,元素si, s2, s3, s4, s5, s6依次进栈，如果6个元素 的出栈顺序为s2, s3, s4, s6, s5, si,则顺序栈的容量至少为3。 9. 设有一个空栈，现输入序列为1, 2, 3, 4, 5。经过push, push, pop, push, pop, push, pop, push 后，输出丿了:列是 2 3 4 o 10. 在按算符优先法求解表达式3 1+5*

8、2时，最先执行的运算是* ,最后执 行的运算是一O 11. 在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求 栈 存在o 12. 仅允许在同一端进行插入和删除的线性表称为栈。 13. 在顺序栈s中，栈为空的条件是s.top=s.base ,栈为满的条件是s.top s.base =s.stacksize。 14. 设有算术表达式x+a* （yb） c/d,该表达式的前缀表示为 x*a yb/cd o 后缀表示为xayb *+cd/ o 15. 用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234,为了得到 1342出栈顺序，相应的S、X操作串为 SXSSXSXX 。 16

9、. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行p-liiik= top 和 top=p 3 操作。 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、O 10.用一个大小为1000的数组来实现循环队列，当前wai和加mt的值分别为0 和994,若要达到队满的条件，还需要继续入队的元素个数是993 o 20. 队列的插入操作在 队尾 进行，删除操作在 队头 进行。 21 在一个循环队列Q中，判断队空的条件为Q.front=Q.rear ，判断队满的 条件为 （Q.rear l）%maxSize=Q.front 22向一个循环队列中插入元素时，需要首先移动队尾指针，然后再向所指 位置 写入（或插入） 新插入的元素。 23. 当用长度为n的数组顺序存储一个栈时，若用top=n表示栈空，则表示栈 满的条件为 top=0 o 24. 循环队列的引入，

11、Id的是为了克服 假溢出时大量移动数据元素。 第4章 串（已校对无误）1.两个串相等的充分必要条件是 两个串的长度相 等且对应位置的字符相同。 2. 空格串是 由一个或多个空格字符组成的串，其长度等于 其包含的空格 个数 3. 模式串abaabade的 iwxt 函数值为 01122341 补充： 1. 串的两种最基本的存储方式是顺序存储方式和链接存储方式。 2. 空串是 零个字符的串,其长度等于 零。 3. 组成串的数据元素只能是 字符。 4. 串是一种特殊的线性表，其特殊性表现在其数据元素都是字符。 第5章 数组（已校对无谋）1将下三角矩阵A18, 18的下三角部分逐行地 存储到起始地址为

12、1000的内存单元中，已知每个.元素占4个单元，则元素 A7, 5的地址为 1100 o 2. 二维数组A0-9, 0-19釆用列序为主方式存储，每个元素占一个存储单元， 并且元素A0,0的存储地址是200,则元素A6,12的地址是332 。 3. 二维数组A10-20, 5-10采用行序为主方式存储，每个元素占4个存储单 元，并且元素A10, 5的存储地址是1000,则元素A18, 9的地址是1208 。 补充： 1. 一维数组的逻辑结构是 线性结构,存储结构是 顺序存储结构。 2. 对于二维数组或多维数组，分为按 以行为主序 和按 以列为主序 两种 不同的存储方式存储。 3. 对矩阵压缩存

13、储是为了节省存储空间。 4. 二维数组是一种非线性结构，其中的每一个数组元素最多有 二 个直接前 驱（或直接后继）。 第6章 树（已校对无谋）4.结点最少的树为只有一个结点的树，结点最少 的二叉树为空的二叉树。 5. 根据二叉树的定义，具有三个结点的二义树有5种不同的形态，它们分别 是 O 6. 具有n个结点的完全二叉树的深度为。 8. 以数据集4, 5, 6, 7, 10, 12, 18为结点权值所构造的哈夫曼树为需用 图示,其带权路径长 度为165 o 9. 哈夫曼树是带权路径长度最短的树，通常权值较大的结点离根较近 10. 在先序遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接

14、跟在该结点之后。 第7章 图（已校对无误）1.个顶点的连通图至少有1】一1条边。 2.在无权图G的邻接矩阵A中，若（vi, vj）或vi, vj属于图G的边集， 则对应元素Aij等于 1,否则等于0 。 3在无向图G的邻接矩阵A中，若等于1, Aj i等于1 。 4. 已知图G的邻接表如下图所示，其从顶点vl出发的深度优先搜索序列为vlv2 v3 v6 v5 v4,其从顶点vl出发的广度优先搜索序列为vl v2 v5 v4 v3 v6。 VI V2 V5 V4 A v2 A V5 v3 V6 v3 A v4 V4 V6 V3 A v5 Av6 有，x是x, y与y, y）与（y, x）被认为无

15、向，但x5设x, y是图 G中的两顶点，则（的两条弧。向 一 。行全部置为0个结点出发的边的方法是已知一个图的邻接矩阵表示，删除所 有从i将矩阵的第i6 个结点的j个结点的岀度，而山第j列可得到第7.在有向图的邻接矩阵上， 由第i行可得到第i 入度。 是 连通在无向图中，如果从顶点8v到顶点V有路径，则称v 和V 查找 第8章（已校对无谋）；哈希表查找法采用链接法处理冲突时的平均查找 长/2+ （nl） 1顺序查找法的平均査找长度为 O 度为1 + ? O哈希表查找法2在各种查找方法中， 平均查找长度与结点个数n无关的查找方法是 o有序的 顺序存储结构二分查找的存储结构仅限于3. o 15 4

16、长度为255的表，采用分块查找法，每块的最佳长度是 o ? 个记录的有序顺序表中进行折半查找，最大的比较次数是logN 5.N: .;若采用二分法查找，则时间 O(n)6对于长度为11的线性 表，若进行顺序查找，则时间复杂度为小 则时间复杂度为；若采用 分块查找(假定总块数和每块长度均接近0( log n) 复杂度为2 _ 0(11) o 7. 在散列存储中，装填因子a的值越大，则存取元素时发生冲突的可能性就越 大；a的值越小，则存取元 素时发生冲突的可能性就越小。 &对于二叉排序树的查找，若根结点元素的键值大于被查元素的键值，则应该 在二叉树的左子树 上继续查找。 9高度为8的平衡二叉树至少

17、有54个结点。 10.在散列函数H (kuy) =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个记录的表rl迅进行简单选择排序，所需要进行的关键字间的比较次 数为 n(n1)/2 o 4. 在插入排序.希尔排序、选择排序、快速排序、堆排序、归并排序和基数排 序中，