2023年《数据结构》填空作业题超详细解析超详细解析超详细解析答案.pdf

《2023年《数据结构》填空作业题超详细解析超详细解析超详细解析答案.pdf》由会员分享，可在线阅读，更多相关《2023年《数据结构》填空作业题超详细解析超详细解析超详细解析答案.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

5、结点的单链表 L 为空的判定条件是 L=NULL。17.在单链表中，指针 p 所指结点为最后一个结点的条件是 p-next=NULL。3 18.循环链表的最大优点是 从表中任意结点出发都可访问到表中每一个元素（或从表中任意结点出发都可遍历整个链表）。19.设 rear 是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的存储位置是 rear-next-next。20.带头结点的双向循环表 L 为空表的条件是 L-prior=L-next。21.在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道 头指针 才能遍历整个链表。22.将两个各有 n 个元素的有序表归并成一个有序表，

6、其最少的比较次数是 1。第 3 章 栈和队列（已校对无误）1.栈又称为 后进先出 表，队列又称为 先进先出 表。2.向一个顺序栈插入一个元素时，首先使 栈顶指针 后移一个位置，然后把待插入元素 写入（或插入）到这个位置上。3.从一个栈删除元素时，需要前移一位 栈顶指针。4.在一个顺序栈中，若栈顶指针等于 1，则为空栈；若栈顶指针等于 maxSize 1，则为满栈。5.在一个链式栈中，若栈顶指针等于 NULL，则为 空栈；在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为 空 或该队列 只含有一个结点。6.向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给 新结点的指针域，然后把新

7、结点的存储位置赋给 栈顶指针。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.仅允许在

8、同一端进行插入和删除的线性表称为 栈。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 4 操作。17.从一个栈顶指针为 top 的非空链

9、式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 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.队列的

10、插入操作在 队尾 进行，删除操作在 队头 进行。21.在一个循环队列 Q 中，判断队空的条件为 Q.front=Q.rear，判断队满的条件为(Q.rear 1)maxSize=Q.front。22.向一个循环队列中插入元素时，需要首先移动 队尾指针，然后再向所指位置 写入（或插入）新插入的元素。23.当用长度为 n 的数组顺序存储一个栈时，若用 top=n 表示栈空，则表示栈满的条件为 top=0。24.循环队列的引入，目的是为了克服 假溢出时大量移动数据元素。第 4 章 串（已校对无误）1.两个串相等的充分必要条件是 两个串的长度相等且对应位置的字符相同。2.空格串是 由一个或多个空格字符

11、组成的串，其长度等于 其包含的空格个数。3.模式串 abaabade的 next 函数值为 01122341 补充：1.串的两种最基本的存储方式是 顺序存储方式和链接存储方式。2.空串是 零个字符的串，其长度等于 零。3.组成串的数据元素只能是 字符。4.串是一种特殊的线性表，其特殊性表现在 其数据元素都是字符。第 5 章 数组（已校对无误）1.将下三角矩阵 A1.8，1.8的下三角部分逐行地存储到起始地址为 1000 的内存单元中，已知每个元素占 4 个单元，则元素 A7，5的地址为 1100。2.二维数组 A09，019 采用列序为主方式存储，每个元素占一个存储单元，并且元素 A0，0的存

12、储地址是 200，则元素 A6，12的地址是 332。3.二维数组 A10 20，51 0采用行序为主方式存储，每个元素占 4 个存储单元，并且元素 A10，5的存储地址是 1000，则元素 A18，9的地址是 1208。5 补充：1.一维数组的逻辑结构是 线性结构，存储结构是 顺序存储结构。2.对于二维数组或多维数组，分为按 以行为主序 和按 以列为主序 两种不同的存储方式存储。3.对矩阵压缩存储是为了 节省存储空间。4.二维数组是一种非线性结构，其中的每一个数组元素最多有 二 个直接前驱（或直接后继）。第 6 章 树（已校对无误）4.结点最少的树为 只有一个结点的树，结点最少的二叉树为 空

13、的二叉树。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 的边集，则对应元素 Aij等于 1，否则等于 0。

14、3.在无向图 G 的邻接矩阵 A 中，若 Aij等于 1，Aj 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 6 5.设 x，y 是图 G 中的两顶点，则（x，y）与（y，x）被认为 无向，但 x，y与 y，x是 有向 的两条弧。6.已知一个图的邻接矩阵表示，删除所有从 i 个结点出发的边的方法是 将矩阵的第 i 行全部置为 0。7.在有向图的邻接矩阵上

15、，由第 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 的线性表，若进行顺

16、序查找，则时间复杂度为 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，

17、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.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有 希尔排序、选择排序、快速排序、堆排序。7 5.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是 快速排序，需要内存容量最多的是 基数排序。6.在堆排序和快速排序中，若原始记录接近正序或反序，则选用 堆排序，若原始记录无序，则最好选用 快速排序。7.在插入排序和选择排序中，若初始数据基本正序，则选用 插入排序；若初始数据基本反序，则选用 选择排序。8.对 n 个元素的序列进行冒泡排序时，最少的比较次数是 n 1。9.基数 排序不需要进行记录关键字间的比较。