2021年《数据结构》填空作业题培训资料

1、资料收集于网络，如有侵权请联系网站删除数据结构填空作业题答案第 1 章绪论（已校对无误） |精.|品.|可.|编.|辑.|学.|习.|资.|料. * | * | * | * | |欢.|迎.|下.|载. 1数据结构包括数据的规律结构、数据的储备结构和数据的运算三方面的内容；2程序包括两个内容：数据结构和算法；3. 数据结构的形式定义为：数据结构是一个二元组：Data Structure =（ D， S） ；4. 数据的规律结构在运算机储备器内的表示，称为数据的储备结构；5. 数据的规律结构可以分类为线性结构和非线性结构两大类；6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个；7.

2、 在树形结构中，数据元素之间存在一对多的关系；8. 数据的物理结构，指数据元素在运算机中的标识（映象），也即储备结构；9. 数据的规律结构包括线性结构、树形结构和图形结构3 种类型，树型结构和有向图结构合称为非线性结构；10. 次序储备结构是把规律上相邻的结点储备在物理上连续的储备单元里，结点之间的规律关系由储备单元位置的邻接关系来表达；11. 链式储备结构是把规律上相邻的结点储备在物理上任意的储备单元里，节点之间的规律关系由附加的指针域来表达；12. 数据的储备结构可用4 种基本的储备方法表示，它们分别是次序储备、 链式储备、 索引储备 和 散列储备；13. 线性结构反映结点间的规律关系是一

3、对一的，非线性结构反映结点间的规律关系是一对多或多对多；14. 数据结构在物理上可分为次序储备结构和链式储备结构；15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，仍给出了处理数据的实现方法；16. 数据元素可由如干个数据项组成；17. 算法分析的两个主要方面是时间复杂度和空间复杂度；18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的储备空间的大小来度量的；19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出；20. 对于某一类特定的问题，算法给出明白决问题的一系列操作，每一操作都有它的准确的定义，并

4、在有穷时间内运算出结果；word 可编辑第 1 页，共 8 页资料收集于网络，如有侵权请联系网站删除21. 下面程序段的时间复杂度为 3n；i=1 ； whilei<=ni= i 3；第 2 章线性表 （已校对无误）1. 一线性表表示如下： （a ，a ，a，a ，a，a ），其中每个 a 代表一个数据元素（或12i-1ii+1ni |精.|品.|可.|编.|辑.|学.|习.|资.|料. * | * | * | * | |欢.|迎.|下.|载. 结点）；a1 称为起始结点， an 称为终端结点， i 称为 ai 在线性表中的位置（或序号）；对任意一对相邻结点ai，ai+1 ，（1i n）

5、，ai 称为 ai+1 的直接前驱，ai+1 称为 ai 的直接后继；2. 对一个长度为 n 的线性表，要删除第 i 个元素，就在次序表示的情形下， 运算复杂性为On，在链式表示的情形下，运算复杂性为O1；3. 在一个长度为 n 的次序表中， 向第 i 个元素（ 1 in）之前插入一个新元素时， 需向后移动ni 1个元素；4. 次序表中规律上相邻的元素在物理位置上肯定相连；5. 在 n 个结点的次序表中插入一个结点需平均移动n/2个结点，详细的移动次数取决于表长 n 和插入位置 i；6. 在次序表中拜访任意一个结点的时间复杂度均为O1，因此，次序表也称为随机拜访的数据结构；7. 次序表相对于链

6、表的优点有随机拜访和空间利用率高；8. 在长度为 n 的次序表中插入一个元素的时间复杂度为On；9. 在带有头结点的单链表L 中，如要删除第一个结点， 就须执行以下三条语句：U L->next；L->next=U->next ；free（U）；10. 链表相对于次序表的优点有插入和删除操作便利；11. 在单链表中除首结点外，任意结点的储备位置都由直接前驱结点中的指针指示；12. 在 n 个结点的单链表中要删除已知结点*p ，需找到它的直接前驱结点的地址，其时间复杂度为On；13单链表中设置头结点的作用是简化操作，削减边界条件的判定；14在带表头结点的单链表中，当删除某一指定结

7、点时，必需找到该结点的前驱结点；15. 在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后续结点；16. 带头结点的单链表L 为空的判定条件是L -> next=NULL，不带头结点的单链表L 为空的判定条件是L=NULL；word 可编辑第 2 页，共 8 页资料收集于网络，如有侵权请联系网站删除17. 在单链表中，指针p 所指结点为最终一个结点的条件是p-> next=NULL；18. 循环链表的最大优点是从表中任意结点动身都可拜访到表中每一个元素（或从表中任意结点动身都可遍历整个链表）； |精.|品.|可.|编.|辑.|学.|习.|资.|料. * | * | *

8、 | * | |欢.|迎.|下.|载. 19. 设 rear 是指向非空、带头结点的循环单链表的尾指针，就该链表首结点的储备位置是rear->next->next；20. 带头结点的双向循环表L 为空表的条件是L -> prior= L -> next ；21. 在循环链表中，可依据任一结点的地址遍历整个链表，而单链表中需知道头指针才能遍历整个链表；22. 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是1；第 3 章栈和队列 （已校对无误）1. 栈又称为后进先出表，队列又称为先进先出表；2. 向一个次序栈插入一个元素时，第一使栈顶指针后移一个位置，

9、然后把待插入元素写入（或插入）到这个位置上；3. 从一个栈删除元素时，需要前移一位栈顶指针；4. 在一个次序栈中，如栈顶指针等于 1，就为空栈；如栈顶指针等于maxSize1，就为满栈；5. 在一个链式栈中，如栈顶指针等于NULL ，就为空栈；在一个链式队列中，如队头指针与队尾指针的值相同，就表示该队列为空或该队列只含有一个结点；6. 向一个链式栈插入一个新结点时，第一把栈顶指针的值赋给新结点的指针域，然后把新结点的储备位置赋给栈顶指针；7在求表达式值的算符优先算法中使用的主要数据结构是栈；8设有一个次序栈S，元素 s1， s2，s3， s4，s5， s6 依次进栈，假如6 个元素的出栈次序为

10、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.top s.base=s.stacksize ；14. 设有算术

11、表达式x a*（ yb） c/d，该表达式的前缀表示为 x*a yb/cd ；后缀表示为xayb* cd/；15. 用 S 表示入栈操作， X 表示出栈操作，如元素入栈次序为1234，为了得到 1342 出栈次序，word 可编辑第 3 页，共 8 页 |精.|品.|可.|编.|辑.|学.|习.|资.|料. * | * | * | * | |欢.|迎.|下.|载. 资料收集于网络，如有侵权请联系网站删除相应的 S、X 操作串为SXSSXSXX；16. 向一个栈顶指针为top 的链式栈中插入一个新结点*p 时，应执行p->link top和topp操作；17. 从一个栈顶指针为top 的非

12、空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行toptop->link操作；18. 设有一个空栈，栈顶指针为1000H（十六进制；现有输入序列为1，2，3，4，5，经过 PUSH，PUSH，POP， PUSH，POP，PUSH， PUSH 之后，输出序列是2，3，而栈顶指针是100CH；设栈为次序栈，每个元素占4 个字节；19. 在作入栈运算时应先判别栈是否满；在作出栈运算时应先判别栈是否空；10. 用一个大小为1000 的数组来实现循环队列，当前rear 和 front 的值分别为 0 和 994，如要达到队满的条件，仍需要连续入队的元素个数是993；20. 队列的插入

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

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

15、页资料收集于网络，如有侵权请联系网站删除储备地址是 200，就元素 A6 ，12的地址是332；3. 二维数组 A1 020，510采纳行序为主方式储备，每个元素占4 个储备单元，并且元素A10 ， 5 的储备地址是 1000，就元素 A18 ， 9的地址是1208；补充： |精.|品.|可.|编.|辑.|学.|习.|资.|料. * | * | * | * | |欢.|迎.|下.|载. 1. 一维数组的规律结构是线性结构，储备结构是次序储备结构；2. 对于二维数组或多维数组，分为按以行为主序和按以列为主序两种不同的储备方式储备；3. 对矩阵压缩储备是为了节约储备空间；4. 二维数组是一种非线性

16、结构，其中的每一个数组元素最多有二个直接前驱（或直接后继） ；第 6 章树（已校对无误）4. 结点最少的树为只有一个结点的树，结点最少的二叉树为空的二叉树；5. 依据二叉树的定义，具有三个结点的二叉树有5种不同的形状，它们分别是；6. 具有 n 个结点的完全二叉树的深度为；8. 以数据集 4 ，5，6，7，10，12， 18为结点权值所构造的哈夫曼树为需用图示，其带权路径长度为165；9. 哈夫曼树是带权路径长度最短的树，通常权值较大的结点离根较近；10. 在先序遍历二叉树的序列中，任何结点的子树上的全部结点，都是直接跟在该结点之后；第 7 章图（已校对无误）1n 个顶点的连通图至少有n1 条

17、边；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；V1v2 v3v4v5 word 可编辑v6V2V5V4v3V5V6V4V6V3第 5 页，共 8 页资料收集于网络，如有侵权请联系网站删除5. 设 x， y 是图 G 中的两顶点，就（ x，

18、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；哈希表查找法采纳链接法处理冲突时的平均查找长度为

19、1？；2. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是哈希表查找法；3. 二分查找的储备结构仅限于有序的次序储备结构；4. 长度为 255 的表，采纳分块查找法，每块的正确长度是15；5. N 个记录的有序次序表中进行折半查找，最大的比较次数是 2N？；6. 对于长度为 n 的线性表，如进行次序查找，就时间复杂度为 On ；如采纳二分法查找，就时间复杂度为 O 2n ；如采纳分块查找（假定总块数和每块长度均接近 n ），就时间复杂度为On ；7. 在散列储备中，装填因子 a 的值越大，就 存取元素时发生冲突的可能性就越大；a 的值越小，就 存取元素时发生冲突的可能性就越小；8. 对于二叉排序树的查找，如根结点元素的键值大于被查元素的键值，就应当在二叉树的左子树上连续查找；9. 高度为 8 的平稳二叉树至少有54个结点；word 可编辑第 6 页，共 8 页资料收集于网络，如有侵权请联系网站删除10. 在散列函数 H（ key）=key % p 中， p 应取素数； |精.|品.|可.|编.|辑.|学.|习.|资.|料. *