数据结构填空作业题答案

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

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

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

4、 3；第2章线性表(已校对无误)1. 一线性表表示如下：(ai,a2,，ai-i, a ,a+i,，an),其中每个a代表一个数据元素(或结点) 。ai称为 起始 结点,an称为 终端 结点,i称为 a在线性表中的 位置(或序号) 。 对任意一对相邻结点ai, ai+i, (Kin), a称为a+i的直接 前驱，a+i称为a的直接 后继。2. 对一个长度为n的线性表，要删除第i个元素，则在顺序表示的情况下，计算复杂性为 0(n),在链式表示的情况下，计算复杂性为0(i)。3. 在一个长度为n的顺序表中，向第i个元素(K i next ;L-next=U-next ； free (U )。10.

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

6、表中，指针p所指结点为最后一个结点的条件是p- next=NULL 。18. 循环链表的最大优点是从表中任意结点出发都可访问到表中每一个元素（或从表中任意结点出发都可遍历整个链表）。19. 设rear是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的存储位置是 rear-n ext- n ext 。20. 带头结点的双向循环表 L为空表的条件是 L- prior= L- next。21. 在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道头指针 才能遍历整个链表。22. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是1 。第3章 栈和队列（已校对无误）1.

7、 栈又称为 后进先出 表，队列又称为 先进先出 表。2. 向一个顺序栈插入一个元素时，首先使 栈顶指针 后移一个位置,然后把待插入元素 写入（或插入）到这个位置上。3. 从一个栈删除元素时，需要前移一位栈顶指针。4. 在一个顺序栈中，若栈顶指针等于1 ，则为空栈；若栈顶指针等于maxSize 1 ，则为满栈。5. 在一个链式栈中，若栈顶指针等于 NULL，则为 空栈：在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为空或该队列只含有一个结点。6. 向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给栈顶指针。7在求表达式值的算符优先算法中使

8、用的主要数据结构是栈。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. 在顺序

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

10、行 top = top-li nk 操作。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

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

12、baabade的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.

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

14、同的形态，它们分别是 。6. 具有n个结点的完全二叉树的深度为 。8. 以数据集4，5,6,7,10，12，18为结点权值所构造的哈夫曼树为需用图示，其带权路径长度为 165 。9. 哈夫曼树是带权路径长度最短 的树，通常权值较大的结点离根较近。10. 在 先序 遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。 第7章图（已校对无误）1. n个顶点的连通图至少有n1条边。2在无权图G的邻接矩阵A中，若（vi，vj）或vi，vj属于图G的边集，则对应元素Aij等于 ，否则等于0 。3. 在无向图G的邻接矩阵A中，若Aij等于1, Aj i等于1。4. 已知图G的邻接表如下

15、图所示，其从顶点 v1出发的深度优先搜索序列为 v1 v2 v3 v6 v5 v4，其从 顶点v1出发的广度优先搜索序列为 v1 v2 v5 v4 v3 v6。5. 设x, y是图G中的两顶点，贝U（ x, 丫）与（y, x）被认为无向，但x, 丫与y, x是有 向的两条弧。6. 已知一个图的邻接矩阵表示，删除所有从i个结点出发的边的方法是 将矩阵的第i行全部置为0 o7. 在有向图的邻接矩阵上，由第i行可得到第i个结点的出度,而由第j列可得到第_j_个结点的 入度。8. 在无向图中，如果从顶点v到顶点v有路径，则称v和v 是 连通。第8章查找（已校对无误）1. 顺序查找法的平均查找长度为（n

16、+ 1） 12 ;哈希表查找法采用链接法处理冲突时的平均查找长度为1 + ?o2. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是哈希表查找法 。3. 二分查找的存储结构仅限于有序的顺序存储结构。4. 长度为255的表，采用分块查找法，每块的最佳长度是15 。5. N个记录的有序顺序表中进行折半查找，最大的比较次数是log ?N ?。6. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为O（n）;若采用二分法查找，则时间复杂度为 。伽如）；若采用分块查找（假定总块数和每块长度均接近jn），则时间复杂度为O（n）。7. 在散列存储中，装填因子a的值越大，则存取元素时发生冲突的可能

17、性就越大：a的值越小，贝U仝取元素时发生冲突的可能性就越小。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. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排