2022年数据结构填空题题库 .pdf

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

1、1 1 1. 线性结构中元素之间存在着 （一对一） 关系，树型结构中元素之间存在着 （一对多）关系。2. 评价数据结构的两条基本标准是： （存储需要量）和（运算的时间效率） 。3. 算法的五个特性是指（有穷性/ 确定性、可行性、输入和输出） 。4. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的（存储结构）无关，是独立于计算机的。5. 数据的逻辑结构包括（线性结构）和非线性结构。6. 针对线性链表的基本操作有很多，但其中最基本的4 种操作分别为（插入） 、删除、查找和排序。7. 对于长度为n 的顺序存储的线性表，当随机插入和删除一个元素时，需平均移动元素的个数为（ n/2 ） 。8. 在单链

2、表中设置头结点的作用是（简化插入、删除算法）。9. 访问单链表中的结点，必须沿着（指针域或next 域）依次进行。10. 在双向链表中，每个结点有两个指针域，一个指向（前驱结点），另一个指向（后继结点）。11. 在一个带头结点的单循环链表中， p 指向尾结点的直接前驱， 则指向头结点的指针 head 可用 p表示为 head=（p-next-next） 。12. 设单链表中指针P指向结点 m ，若要删除 m之后的结点（若存在），则需修改指针的语句是：（p-next=p-next-next） 。13. 已知广义表 A=(a,(b,(c,d),则表尾是（ (b,(c,d)） ，深度为（ 3） 。1

3、4. 广义表 A(a ， b ， c) ， (d ， e ， f)的表头为 （(a,b,c)） ， 长度为（2） 。15. 将一个 n 阶三对角矩阵 A的三条对角线上的元素按行压缩存放于一个一维数组 B中，A00存放于 B0 中。对于任意给定数组元素AIJ，如果它能够在数组 B中找到，则它应在（ 2*I+J 位）置。16. 存储稀疏矩阵的方法是多种多样的，其中的四种方法有 （三元组表示法），（伪地址表示法）， （带辅助行向量的二元组表示法） ， （行-列表示法）17. 三元组表示法， 每个结点包括个字段， 分别为该非零元素的 （行下标） （列下标）和（值）。18. 在串 S=“stud ”中，

4、子串有（ 11）个。19. 设 s1=”study ”,s2=” hard ”, 则调用函数 strcat(s1, s2) 后得到 （study hard） 。20. 设有两个串 p 和 q，求 q 在 p 中首次出现位置的运算称做（模式匹配）21. 设有一个顺序栈S，元素 sl ，s2， s3 ， s4 ， s5 ， s6 依次进栈，如果 6 个元素的出栈顺序为s2，s3，s4，s6，s5，sl ，则顺序栈的容量至少应为（3） 。22. 栈的特点是：（后进先出），栈顶的位置是随着进栈和出栈_操作而变化的。23. 若有一个栈的输入序列为1,2,3, ,n ，输出序列的第一个元素为n，则第 i个

5、输出元素是（ n-i+1 ） 。24. 通常程序在调用另一个程序时，都需要使用一个（栈）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。25. 通常元素进栈的顺序是（先移动栈顶指针，然后存入元素）。26. 通常元素出栈的顺序是（先取出栈顶元素，然后移动栈顶指针）。27. 队列的特点是：（先进先出），其插入操作在（队尾）进行，删除操作在（对头）进行。28. 有数据元素 1、2、3，依次进队列，其出队列序列为（123） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第

6、1 页，共 3 页 - - - - - - - - - 2 2 29. 从一个循环队列中删除一个元素，通常的操作是（先取出元素，然后移动队头指针） 。30. 向一个循环队列中插入一个元素，通常的操作是（先存放元素，然后移动队尾指针） 。31. 在一棵二叉树上第8 层的结点数最多是（ 128）32. 在深度为 5 的满二叉树中，叶子结点的个数为（16） 。33. 在深度为 5 的满二叉树中，共有（ 31）个结点。34. 设一棵完全二叉树共有699 个结点，则在该二叉树中的叶子结点数为 （350） 。35. 深度为 k 的完全二叉树至少有（）个结点，至多有（）个结点，若按自上而下，从左到右的次序编

7、号（从1 开始） ，则编号最小的叶子结点的编号是（） 。36. 设二叉树根结点的层次为O ，对含有100 个结点的二叉树，可能的最大树深和最小树深分别是（） 。 37. 深度为 n 的二叉树最多有（ 2N次方-1） 个结点。 38.设二叉树的根为第一层，则第i 层上的结点数最多有（ 2i ） 。39. 在一棵二叉树中，度为2 的结点的个数是 5，则叶结点的个数为（ 6） 。 40.n 个结点的完全二叉树，其深度h=（log2n+1 ） 。41. 在一棵二叉树中 , 度为 2 的结点个数为 8, 则叶结点个数为（9） 。42. 已知一颗完全二叉树中共有767 结点，则该树中共有（ 384）个叶子

8、结点。43.200 个结点的完全二叉树，其深度h= （8） 。44. 对有 n 个结点的完全二叉树，编号为i(i1)结点的双亲结点的编号为（） ，当 i%2=0时，该结点是其双亲的（） 。45. 一颗有 6 个结点的完全二叉树，其结点按编号存放数据为：A、B、C、D、E、F，若按中根遍历该树得到的数据序列为：（DBEAFC）。46. 现有按中序遍历二叉树的结果为abc ，问有（ 5）种不同形态的二叉树可以得到这一遍历结果。47. 若按（中序）遍历二叉排序树可得到一个关键字的有序序列。48. 树是结点的集合，它的根结点数目是（1） 。49. 若 某二 叉树 的前 序 遍 历 访 问 顺 序 是

9、abdgcefh ， 中 序 遍 历 访 问 顺 序是dgbaechf ，则其后序遍历的结点访问顺序是（gdbehfca ） 。50. 设树 T 的度为 4 ，其中度为 1 、2 、3 和 4 的结点的个数分别为4 、2 、1 、1 ，则 T 中叶子结点的个数为（ 8） 。51. 树和二叉树的 3 个主要差别（树的结点个数至少为1，而二叉树的结点个数可以为 0） ；树中的最大度数没有限制，而二叉树结点的最大度数为2 ；树的结点无左右之分，而二叉树的结点有左右之分。52. 从概念上说，树与二叉树是两种不同的数据结构，通过某种算法将树转化成二叉树的基本目的是（树可采用二叉树的存储结构并利用二叉树的

10、已有的算法解决树的有关问题）。53. 假定一棵树的广义表表示为A（B（E（K，L） ，C （G ） ，D(H(M),I,J)） ）, 则该树的度为（ 3），树的深度为（3） 。554. 在一棵树中，有且仅有一个结点没有前驱，称为（根）结点; 非根结点有且仅有一个（双亲）。 55.n 个顶点的无向完全图具有（n(n-1)/2）条边， n 个顶点的有向完全图具有（n(n-1) ）条弧。56.n 个顶点的连通图的生成树具有（n-1 ）条边。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2

11、 页，共 3 页 - - - - - - - - - 3 3 57. 对长度为 n 的线性表进行顺序查找，在最坏情况下所需要的比较次数为（n）58. 行二分法查找，最大的比较次数是（log2n+1） 。59. 设线性表（ al , a2 ， ，a500 ）元素的值由小到大排列，对一个给定的k 值用二分法查找线性表，在查找不成功的情况下至多需比较（9）次。60. 二分法查找的存储结构仅限于（顺序存储结构），且是有序的。61 顺序查找的平均查找长度为（0（n） ）折半查找只适用于有序 表，且限于 顺序存储结构，其平均查找长度为： （0(log2n) ） 。62. 设有 100 个元素，用折半查找时

12、，最大比较次数是（7） 。63. 在有序表（ 12，24，36，48，60，72，84）中二分查找关键字72 时所需进行的关键字比较次数为（2） 。64. 希尔排序法属于（插入）排序。65。在对一组记录（ 54 , 38 ,99 , 23 ，15，72 , 60 , 45 , 83 ）进行直接插入排序时， 当把第 7 个记录 60 插入到有序表时， 为寻找插入位置需比较 （3）次。66. 每次从无序子表中取出一个元素，然后把它插入到有序子表中的适当位置，此种排序方法叫做（插入）排序，每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种方法叫做（选择）排序。67. 在对一组记录

13、（ 10,50,25,70,35,22,30,85,40）进行直接插入排序时，当把第 6 个记录 22 插入到有序表时，为寻找插入位置需比较（2） 次。68. 堆排序法属于（选择）排序。69. 对一组记录（ 50,40,95,20,15,70,60,45,80）进行简单选择排序时，第4 次交换和选择后，未排序记录（即无序数）为（ 50,70,60,95,80 ） 。70. 假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为（n(n-1)/2 ） 。71. 对 n 个元素的序列进行冒泡排序时，最少的比较次数是（n-1） 。72. （快速堆）排序方法采用的是二分法的思想，其数据的组织采用完全二叉树结构。73。在堆排序和快速排序中，若原始记录接近正序或反序，则选用（堆排序），若原始记录无序，则最好选用（快速排序）。74. 在插入和选择排序中，若初始数据基本正序，则选用（插入排序）；若初始数据基本反序，则选用（选择排序） 。75. 希尔排序是属于（直接插入）排序的改进方法。76. 在单链表上难以实现的排序方法有（快速排序、堆排序、希尔排序）。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -