《数据结构》填空作业题(答案).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(inext ；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 ，则为空栈；若栈顶指针等于 maxSize1 ，则为满栈。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. 在按算符优先法求解表达式315*2时，最先执行的运算是 * ，最后执行的运算是 。11. 在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求 栈存在 。12. 仅允许在同一端进行插入和删除的线性表称为 栈 。13. 在顺序栈s中，栈为空的条件是 s.top=s.base ，栈为满的条件是 s.tops.base=s.stacksize 。14. 设有算术表达式xa*（yb）c/d，该表达式的前缀表示为 x*ayb/cd 。后缀表示为 xayb*cd/ 。15. 用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S、X操作串为 SXSSXSXX 。16. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行 p-linktop 和 topp 操作。17. 从一个栈顶指针为top的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 toptop-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.rear1)maxSize=Q.front 。22. 向一个循环队列中插入元素时，需要首先移动 队尾指针 ，然后再向所指位置 写入（或插入） 新插入的元素。23. 当用长度为n的数组顺序存储一个栈时，若用top=n表示栈空，则表示栈满的条件为 top=0 。24. 循环队列的引入，目的是为了克服 假溢出时大量移动数据元素 。第4章 串（已校对无误）1. 两个串相等的充分必要条件是 两个串的长度相等且对应位置的字符相同 。2. 空格串是 由一个或多个空格字符组成的串 ，其长度等于 其包含的空格个数 。3. 模式串abaabade的next函数值为 01122341 补充：1. 串的两种最基本的存储方式是 顺序存储方式和链接存储方式 。2. 空串是 零个字符的串 ，其长度等于 零 。3. 组成串的数据元素只能是 字符 。4. 串是一种特殊的线性表，其特殊性表现在 其数据元素都是字符 。第5章 数组（已校对无误）1. 将下三角矩阵A1.8，1.8的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则元素A7，5的地址为 1100 。2. 二维数组A09，019采用列序为主方式存储，每个元素占一个存储单元，并且元素A0，0的存储地址是200，则元素A6，12的地址是 332 。3. 二维数组A1020，510采用行序为主方式存储，每个元素占4个存储单元，并且元素A10，5的存储地址是1000，则元素A18，9的地址是 1208 。补充：1. 一维数组的逻辑结构是 线性结构 ，存储结构是 顺序存储结构 。2. 对于二维数组或多维数组，分为按 以行为主序 和按 以列为主序 两种不同的存储方式存储。3. 对矩阵压缩存储是为了 节省存储空间 。4. 二维数组是一种非线性结构，其中的每一个数组元素最多有 二 个直接前驱（或直接后继）。第6章 树（已校对无误）4. 结点最少的树为 只有一个结点的树 ，结点最少的二叉树为 空的二叉树 。5. 根据二叉树的定义，具有三个结点的二叉树有 5 种不同的形态，它们分别是 。6. 具有n个结点的完全二叉树的深度为 。8. 以数据集4，5，6，7，10，12，18为结点权值所构造的哈夫曼树为 需用图示 ，其带权路径长度为 165 。9. 哈夫曼树是带权路径长度 最短 的树，通常权值较大的结点离根 较近 。10. 在 先序 遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。第7章 图（已校对无误）1n个顶点的连通图至少有 n1 条边。2在无权图G的邻接矩阵A中，若（vi，vj）或vi，vj属于图G的边集，则对应元素Aij等于 1 ，否则等于 0 。3. 在无向图G的邻接矩阵A中，若Aij等于1，Aj i等于 1 。4. 已知图G的邻接表如下图所示，其从顶点v1出发的深度优先搜索序列为v1 v2 v3 v6 v5 v4，其从顶点v1出发的广度优先搜索序列为v1 v2 v5 v4 v3 v6。V1v2v3v4 v5v6 V2V5V4 v3V5 V4V6V3 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. 顺序查找法的平均查找长度为 （n1）/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个记录的表r1n进行简单选择排序，所需要进行的关键字间的比较次数为 n(n1)/2 。4. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有