2022年数据结构填空练习题推荐 .pdf

《2022年数据结构填空练习题推荐 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构填空练习题推荐 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构填空练习题一1. 通常从四个方面评价算法的质量：_、_、_和_。2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2 ，其数量级表示为_。3.假定一棵树的广义表表示为A（C，D（E，F，G）， H（I，J），则树中所含的结点数为_个，树的深度为_，树的度为 _。 4. 后缀算式9 2 3 +- 10 2 / -的值为 _。中缀算式（3+4X）-2Y/3 对应的后缀算式为_。5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有_个指针域，其中有_个指针域是存放了地址，有_个指针是空指针。6. 对于一个具

2、有n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有 _个和 _个。7. AOV网是一种 _的图。8. 在一个具有n 个顶点的无向完全图中，包含有 _条边，在一个具有n 个顶点的有向完全图中，包含有_条边。9. 假定一个线性表为(12,23,74,55,63,40) ，若按 Key % 4条件进行划分，使得同一余数的元素成 为 一 个 子 表 ， 则 得 到 的 四 个 子 表 分 别 为 _ 、_、_和 _。10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度_。11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_，整个堆

3、排序过程的时间复杂度为_。12. 在快速排序、堆排序、归并排序中，_排序是稳定的。1. 正确性易读性强壮性高效率 2. O(n) 3. 9 3 3 4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1 6. e 2e 7. 有向无回路 8. n(n-1)/2 n(n-1) 9. （ 12，40）（ ）（74）（23,55，63） 10.增加 1 11.O(log2n) O(nlog2n) 12.归并名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，

4、共 11 页 - - - - - - - - - 二1. 设有一个顺序共享栈S0：n-1，其中第一个栈项指针top1 的初值为 -1，第二个栈顶指针top2 的初值为n，则判断共享栈满的条件是_。 2. 在图的邻接表中用顺序存储结构存储表头结点的优点是_。 3. 设有一个n 阶的下三角矩阵 A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素） 存放在 n(n+1)个连续的存储单元中，则 Aij 与 A00 之间有 _个数据元素。4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为 _表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以

5、又把队列称为_表。 5. 设一棵完全二叉树的顺序存储结构中存储数据元素为 ABCDEF ，则该二叉树的前序遍历序列为_， 中序遍历序列为_， 后序遍历序列为_。6. 设一棵完全二叉树有128 个结点，则该完全二叉树的深度为_，有_个叶子结点。7. 设有向图 G 的存储结构用邻接矩阵A来表示，则A 中第 i 行中所有非零元素个数之和等于顶点i 的_， 第 i 列中所有非零元素个数之和等于顶点i 的_。8. 设一组初始记录关键字序列(k1，k2， , ，kn)是堆，则对i=1，2， , ，n/2 而言满足的条件为_。9.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。10. 下面程

6、序段的功能是实现二分查找算法，请在下划线处填上正确的语句。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 答案1. top1+1=top2 2. 可以随机访问到任一个顶点的简单链表3. i(i+1)/2+j-1 4. FILO，FIFO 5. ABDECF ，DBEAFC ，DEBFCA 6. 8，64 7. 出度，入度8. ki=k2i & kik 三1. 数据结构按逻辑结构可分为两大类，分别是_和_。 2. 数据的逻辑结构

7、有四种基本形态，分别是_、 _、_和_。3. 线性结构反映结点间的逻辑关系是_的，非线性结构反映结点间的逻辑关系是 _的。4. 一个算法的效率可分为_效率和 _效率。5. 在树型结构中，树根结点没有_结点，其余每个结点的有且只有_个前趋驱结点； 叶子结点没有 _结点；其余每个结点的后续结点可以_。6. 在图型结构中，每个结点的前趋结点数和后续结点数可以_。7. 线 性 结 构 中 元 素 之 间 存 在 _ 关 系 ； 树 型 结 构 中 元 素 之 间 存 在_关系；图型结构中元素之间存在_关系。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

8、 - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 8. 下面程序段的时间复杂度是_。第 8 题9 题10 题11 题9. 下面程序段的时间复杂度是_。10. 下面程序段的时间复杂度是_。11. 下面程序段的时间复杂度是_。12. 衡量算法正确性的标准通常是_。13. 算法时间复杂度的分析通常有两种方法，即_和_的方法，通常我们对算法求时间复杂度时，采用后一种方法。答案1.线性结构，非线性结构2.集合，线性，树，图3. 一对一，一对多或多对多4. 时间，空间5. 前趋，一，后继，多6. 有多个7. 一对一，一对多，多对多12

9、. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。13. 事后统计，事前估计四1. 线性表是一种典型的_结构。2. 在一个长度为n 的顺序表的第i 个元素之前插入一个元素，需要后移_个元素。3. 顺序表中逻辑上相邻的元素的物理位置_。4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_一个位置，移动过程是从 _向_依次移动每一个元素。5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心

10、整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 6. 在双向链表中，每个结点含有两个指针域，一个指向_结点，另一个指向_结点。7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_存储结构为宜。8. 顺序表中逻辑上相邻的元素，物理位置_相邻，单链表中逻辑上相邻的元素，物理位置 _相邻。9. 线性表、栈和队列都是_结构，可以在线性表的_位置插入和删除元素；对于栈只能在 _位置插入和删除元素；对于队列只能在_位置插入元素和在_位置删除元素。10. 根据线性表的链式存储结构

11、中每个结点所含指针的个数，链表可分为_和_；而根据指针的联接方式，链表又可分为_和_。11. 在单链表中设置头结点的作用是_。12. 对于一个具有n 个结点的单链表，在已知的结点p 后插入一个新结点的时间复杂度为_，在给定值为x 的结点后插入一个新结点的时间复杂度为_。 13. 对于一个栈作进栈运算时，应先判别栈是否为_，作退栈运算时，应先判别栈是否为 _，当栈中元素为m 时，作进栈运算时发生上溢，则说明栈的可用最大容量为_。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时， 应将两栈的 _分别设在这片内存空间的两端，这样只有当 _时才产生上溢。14. 设有一空

12、栈，现有输入序列1，2， 3，4，5，经过 push, push, pop, push, pop, push, push后，输出序列是_。15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为 _。答案1线性 2n-i+1 3相邻 4前移，前，后5物理存储位置，链域的指针值 6前趋，后继7顺序，链接 8 一定，不一定9线性，任何，栈顶，队尾，队头10单链表，双链表，非循环链表，循环链表11使空表和非空表统一；算法处理一致12O(1)，O(n) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

13、师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 13栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇142、3 15 O(1) 五1. 计算机软件系统中，有两种处理字符串长度的方法：一种是_ ，第二种是_。2. 两个字符串相等的充要条件是_和_。3. 设字符串 S1= “ABCDEF ”，S2= “PQRS ”，则运算 S=CONCAT （SUB （S1，2，LEN （S2），SUB （S1，LEN （ S2）， 2）后的串值为_。4. 串是指 _。5. 空串是指 _，空格串是指 _。1. 固定长度，设置长度指针2. 两个串的长度相

14、等，对应位置的字符相等3. “BCDEDE ”4. 含 n 个字符的有限序列（n0）5. 不含任何字符的串，仅含空格字符的字符串六1. 一维数组的逻辑结构是_，存储结构是 _；对于二维或多维数组，分为 _和_两种不同的存储方式。2. 对于一个二维数组Amn ，若按行序为主序存储，则任一元素Aij 相对于 A00 的地址为_。3. 一个广义表为 (a,(a,b),d,e,(i,j),k)，则该广义表的长度为_，深度为 _。4. 一个稀疏矩阵为如右图，则对应的三元组线性表为_。5. 一 个n n 的 对 称 矩 阵 ， 如 果 以 行 为 主 序 或 以 列 为 主 序 存 入内 存 ， 则 其容

15、 量 为_。6. 已知广义表A=(a,b,c),(d,e,f)，则运算 head(tail(tail(A)=_ 。7. 设有一个 10 阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00 为第一个元素，其存储地址为0，每个元素占有1 个存储地址空间，则a85 的地址为 _。8. 已知广义表Ls=(a,(b,c,d),e)，运用head 和 tail函数取出Ls 中的原子b 的运算是_。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - -

16、- - - 9. 三维数组Rc1, d1,c2, d2,c3, d3共含有 _个元素。（其中：c1d1,c2d2,c3d3）10. 数组A1, 10，-2, 6，2, 8以行优先的顺序存储，设第一个元素的首地址是100，每个元素占 3 个存储长度的存储空间，则元素A5，0， 7的存储地址为 _。1.线性结构，顺序结构，以行为主序，以列为主序2. in+j 个元素位置3. 5，3 4.（ 0，2，2），（ 1，0，3），（ 2， 2，-1），（ 2，3，5）5. n(n+1)/2 6. e 7. 41 8. head(head(tail(Ls) 9.（d1-c1+1）（ d2-c2+1）（ d3

17、-c3+1）10. 913 七1. 假定一棵树的广义表表示为A（B（E），C （F （H，I，J），G），D），则该树的度为_，树的深度为 _，终端结点的个数为_，单分支结点的个数为_，双分支结点的个数为 _，三分支结点的个数为_，C 结点的双亲结点为_，其孩子结点为_和_结点。2. 设 F是一个森林，B是由 F转换得到的二叉树，F中有 n 个非终端结点，则B 中右指针域为空的结点有 _个。3. 对于一个有n 个结点的二叉树，当它为一棵_二叉树时具有最小高度，即为_，当它为一棵单支树具有_高度，即为 _。4. 由带权为3，9，6，2，5 的 5 个叶子结点构成一棵哈夫曼树，则带权路径长度为_。

18、5. 在一棵二叉排序树上按_遍历得到的结点序列是一个有序序列。6. 对于一棵具有n 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_个，其中 _个用于链接孩子结点，_个空闲着。7. 在一棵二叉树中，度为0 的结点个数为n0，度为 2 的结点个数为n2，则 n0=_。 8. 一棵深度为k 的满二叉树的结点总数为_，一棵深度为k 的完全二叉树的结点总数的最小值为 _，最大值为 _。9. 由三个结点构成的二叉树，共有_种不同的形态。10. 设高度为h 的二叉树中只有度为0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为 _。11. 一棵含有n 个结点的k 叉树， _形态达到最

19、大深度，_形态达到最小深度。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 12. 对于一棵具有n 个结点的二叉树，若一个结点的编号为i(1in)，则它的左孩子结点的编号为 _，右孩子结点的编号为_，双亲结点的编号为_。13. 对于一棵具有n 个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_个，其中 _个用于链接孩子结点，_个空闲着。14. 哈夫曼树是指 _的二叉树。15. 空树是指 _，最小的树是指_。16. 二叉

20、树的链式存储结构有_和_两种。17. 三叉链表比二叉链表多一个指向_的指针域。18. 线索是指 _ 。19. 线索链表中的rtag 域值为 _时，表示该结点无右孩子，此时_域为指向该结点后继线索的指针。20. 本节中我们学习的树的存储结构有_、_和_。1. 3，4，6，1，1，2，A，F，G 2. n+1 4. 55 5. 中序6. 2n，n-1，n+1 7. n2+1 8. 2k-1， 2k-1，2k-1 9. 5 10. 2h-1 11. 单支树，完全二叉树12. 2i， 2i+1，i/2i/213. 2n，n-1， n+1 14. 带权路径长度最小15. 结点数为 0，只有一个根结点的树

21、16. 二叉链表，三叉链表17. 双亲结点18. 指向结点前驱和后继信息的指针19. 1，RChild 20. 孩子表示法，双亲表示法，长子兄弟表示法八1. 在一个图中，所有顶点的度数之和等于所有边数的_倍。2. 在一个具有n 个顶点的无向完全图中，包含有 _条边，在一个具有n 个顶点的有向完全图中，包含有_条边。3. 假定一个有向图的顶点集为a,b,c,d,e,f，边集为 , , , , , ，则出度为 0 的顶点个数为 _，入度为 1 的顶点个数为 _。 4. 在一个具有n 个顶点的无向图中，要连通所有顶点则至少需要_条边。5.表示图的两种存储结构为_和_。6.在一个连通图中存在着_个连通

22、分量。 7. 图中的一条路径长度为k，该路径所含的顶点数为_。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 8. 若一个图的顶点集为a,b,c,d,e,f ，边集为 (a,b),(a,c),(b,c),(d,e)，则该图含有 _个连通分量。 9. 对于一个具有n 个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为_。 10. 对于具有 n 个顶点和e 条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为 _和_。

23、 11. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有_和_结点。 12. 对于一个具有n 个顶点和e 条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为_和_。 13. 假定一个图具有n 个顶点和e 条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为 _和_。 14. 一个图的边集为(a,c),(a,e),(b,e),(c,d),(d,e) ，从顶点a 出发进行深度优先搜索遍历得到的顶点序列为_，从顶点a 出发进行广度优先搜索遍历得到的顶点序列为_。 15. 一个图的边集为,，从顶点 a 出发进行深度优先搜索遍历得到的顶点序列

24、为_， 从顶点 a 出发进行广度优先搜索遍历得到的顶点序列为_。 16. 图的 _优先搜索遍历算法是一种递归算法，图的 _优先搜索遍历算法需要使用队列。 17. 对于一个具有n 个顶点和e 条边的连通图， 其生成树中的顶点数和边数分别为_和_。 18. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是_（唯一 /不唯一）的。19. 根据图的存储结构进行某种次序的遍历，得到的顶点序列是_（唯一 /不唯一）的。20. 假定一个有向图的边集为,，对该图进行拓扑排序得到的顶点序列为 _。1. 2 2. n(n-1)/2 ，n(n-1) 3. 2，4 4. n-1 5. 邻接矩阵，邻接表 6.

25、1 7. k+1 8. 3 9. n，n 10. 2e ，e 11. 出边，入边 12. O （n）， O（ e/n）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 13.O（n2）， O（n+e） 14. acdeb ，acedb （答案不唯一） 15. acfebd， acefbd （答案不唯一）16. 深度，广度17. n，n-1 18.唯一19. 唯一 20. aebdcf （答案不唯一）九1. 以顺序查找方法从长度为

26、n 的顺序表或单链表中查找一个元素时，平均查找长度为_，时间复杂度为_。2. 对长度为n 的查找表进行查找时，假定查找第i 个元素的概率为pi,查找长度 （即在查找过程中依次同有关元素比较的总次数）为 ci，则在查找成功情况下的平均查找长度的计算公式为_。3. 假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度_，在查找不成功情况下的平均查找长度_。4. 以折半查找方法从长度为n 的有序表中查找一个元素时，平均查找长度约等于_的向上取整减1，时间复杂度为_。5. 以折半查找方法在一个查找表上进行查找时，该查找表必须组织成_存储的_表。 6. 从有序表

27、(12,18,30,43,56,78,82,95) 中分别折半查找43 和 56 元素时，其比较次数分别为_和_。 7. 假定对长度n=50 的有序表进行折半查找，则对应的判定树高度为_，最后一层的结点数为 _。 8. 假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查找的平均查找长度为_。 9. 在索引查找中，假定查找表（即主表）的长度为96，被等分为8 个子表，则进行索引查找的平均查找长度为_。 10. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定_该结点的值，右子树上所有结点的值一定_该结点的值。11. 对一棵二叉排序树进行中序遍历时，得到的结点序列

28、是一个_。12. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明 _，若元素的值小于根结点的值，则继续向 _查找， 若元素的值大于根结点的值，则继续向_查找。13. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - _插入，若元素的值大于根结点的值，则接着向根结点的_插入。14. 根据 n 个元素建立一棵二叉排序树的时间复杂度大致为

29、_。15. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过_。 16. 假定对线性表 (38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到_次存储冲突。 17. 假定对线性表 (38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则平均查找长度为_。18. m 表示哈希表的长度，n 表_。19. 对线性表 (18,25,63,50,42,32,90) 进行哈希存储时，若选用H(K)=K % 9作为哈希函数，则哈希地址为 0 的

30、元素有 _个，哈希地址为5 的元素有 _个。1. (n+1)/2, O(n) 3. 20.5, 41 4. log2(n+1)O(log2n) 5. 顺序 有序 6. 1， 3 7. 6， 19 8. (n/s+s)/2+1 9. 11 10.小于，大于11. 有序序列 12. 查找成功，左子树，右子树13. 左子树，右子树 14. O(nlog2n) 15. 1 16. 5 17. 2 18. n/m 19. 3， 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -