数据结构填空题

《数据结构填空题》由会员分享，可在线阅读，更多相关《数据结构填空题（12页珍藏版）》请在金锄头文库上搜索。

1、 一、填空题一、填空题 1. 数据结构的存储结构包括顺序、（ ）、索引和散列等四种。 【答案】 链接2. 设关键字序列7,12,26,30,47,58,66,70,82,90，当用折半查找方法查找时，所需比较的次数为3次的关 键字分别是（ ） 。 【答案】7 26 58 82 3. 假定一个线性表为 12, 23, 74, 55, 63, 40, 82, 36，若按key%3条件进行划分，使得同一余数的 元素成为一个子表，则包含74的子表长度为（ ）。 【答案】2 4. 和折半查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对( ( ) )结构也无特殊要求。 【答案】 存储5. 设双

2、向循环链表每个结点结构为(data,llink,rlink),则结点*p的前驱结点的地址为( ( ) )。【答案】p-llink 6. n个顶点的连通无向图的生成树含有( ( ) )条边。 【答案】n-1 7. 在一个最大堆中，堆顶结点的值是所有结点中的( ( ) )。 【答案】 最大值 8. 假定对长度n=50的有序表进行折半查找，则对应的判定树中最底下一层的结点数为（ ）个。 【答案】19 9. 对于带头结点的链栈top，取栈顶元素的操作是（ ） 。 【答案】 *y=top-next-data 10. 假定一棵二叉树的结点个数为50，则它的最小高度为（ ）。假定树根结点的深度为0。 【答案

3、】5 11. 二维数组是一种非线性结构，其中的每一个数组元素最多有( ( ) )个直接前驱（或直接后继）。 【答案】 两个 12. 在堆排序中，对任意一个分支结点进行调整运算的时间复杂度为( ( ) )。 【答案】O(log2n) 13. 队列的删除操作在（ ）进行。 【答案】 队头（或队首） 14. 设图G = (V, E)，V = 1, 2, 3, 4, E = , , , ，从顶点1出发，对 图G进行广度优先搜索的序列有( ( ) )种。【答案】2 15. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的（ ）上。 【答案】 左子树 16. 快速排序在平

4、均情况下的时间复杂度为( ( ) )。 【答案】O(nlog2n) 17. 由关键字序列42,97,75,23,68,34建成的最大堆是( ( ) )。 【答案】97，68，75，23，42，3418. 对于关键字序列（,）进行初始建堆，必须从关键 字为（ ）的结点开始。 【答案】60 19. 从有序表(12,18,30,43,56,78,82,95)中折半查找元素56时，其查找长度为（ ）。 【答案】3 20. 设有二叉树根结点的层次为，一棵高度为h的满二叉树中的叶子结点个数是（ ） 。 【答案】2h 21. 在一个最小堆中，堆顶结点的值是所有结点中的( ( ) )。 【答案】 最小值22.

5、 在长度为n的顺序表中删除一个元素时,等概率情况下的平均移动元素的次数是（ ） 。【答案】(n-1)/223. 由关键字序列（57,24,76,63,18,31,15）生成的一棵二叉排序树，其等查找概率情况下查找成功的平均查找长度为 （ ） 。 【答案】 18/724. 数据结构包括逻辑结构、（ ）和数据的运算三个方面。 【答案】 存储结构 25. 在一棵m阶B树上，每个非根结点的关键字数最多为( ( ) )个。 【答案】m-1 26. 在双向链表中, 每个结点除了数据域外, 还有两个指针域, 它们分别指向( ( ) )。 【答案】 前趋结点和后继结点 27. 一般来说,深度优先生成树的高度比

6、广度优先生成树的高度要( ( ) )。【答案】 高 28. 递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是 保存本层的形 式参数和（ ）。 【答案】 局部变量 29. 在一个堆的顺序存储中，若一个元素的下标为i(0in-1)，则它的右子女元素的下标为（ ）。 【答案】2i+2 30. 数据结构的逻辑结构包括线性结构和（ ）结构两大类。 【答案】 非线性31. 队列是具有( ( ) )特性的线性表。 【答案】先进先出 32. 基本数据类型是计算机已经实现了的（ ）。 【答案】 数据结构33. n个顶点且含有环路的无向连通图中，至少含有( ( ) )条边。

7、【答案】 n 34. 若设L是指向带表头的单链表, 语句 L-link=L-link-link的作用是( ( ) )单链表中的第一个结点。 【答案】 删除35. 已知8个数据元素为（34，76，45，18，26，54，92，65） ，按照依次插入结点的方法生成一棵二叉排序 树后，最后两层上的结点总数为（ ） 。 【答案】2 36. 大小为M的顺序存储的循环队列sq队满的条件为（ ） 。 【答案】(sq.rear+1)%M = =sq.front 37. 若设顺序栈的最大容量为MaxSize，top=-1表示栈空，则判断栈满的条件是（ ）。 【答案】top=MaxSize-1 38. 假定一个顺

8、序表的长度为40，并假定顺序查找每个元素的概率都相同，则在查找成功情况下的平均 搜索长度为（ ）。 【答案】20.5 40. 设有程序段为 for (i=1 ;inext=p-next; p-next=s; 62. 以顺序查找方法从长度为n的顺序表或单链表中查找一个元素的渐进时间复杂度为（ ）。 【答案】O(n) 63. 在直接选择排序中，记录比较次数的时间复杂度为( ( ) )。 【答案】O(n2) 64. 栈下溢是指在（ ）时进行出栈操作。 【答案】栈空 65. 在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对( ( ) )进行特殊处理。 【答案】 表头指针66. 一维数组所占

9、用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的( ( ) )存取的。 【答案】 下标（或顺序号）67. 利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和 ( ( ) )。 【答案】值68. 克鲁斯卡尔算法适用于求（ ）的网的最小生成树。 【答案】边稀疏69. 用链表表示线性表,表中元素之间的逻辑关系是通过链表中结点的（ ）来实现的。 【答案】指针 70. 将一棵树按照左孩子-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有（ ）孩 子。 【答案】 右71. 由带权为9，6，2，5，7的五个叶子结点构造的哈夫曼树，其根结点的

10、权值为（ ） 。 【答案】29 72. 11个顶点的连通网络N有10条边，其中权值为1, 2, 3, 4, 5的边各2条，则网络N的最小生成树各边 的权值之和 为( ( ) )。 【答案】30 73. 线性表是由n（n0）个( ( ) )组成的有限序列。 【答案】 数据元素 74. 给定一组数据元素的关键字为46，79，56，38，40，84，对其进行一趟快速排序处理，得到的右 子表中有( ( ) )个元素。 【答案】3 75. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储( ( ) )个 矩阵元素。 【答案】n(n+1)/2 76. 对于一棵具有n个

11、结点的树，该树中所有结点的度数之和为（ ）。 【答案】n-1 77. 在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个( ( ) )上， 才会被加入到生成树中。 【答案】 连通分量78. 设序列25,36,40,45,48,56,60,68,72,85，当用折半查找方法查找36时，所需比较的次数为（ ） 。 【答案】2 79. 哈希查找是通过（ ）来确定记录的存储地址的。 【答案】哈希函数 80. 对n个数据对象进行堆排序，总的时间复杂度为( ( ) )。【答案】O(nlog2n) 81. 在线性表的散列存储中，装载因子 又称为装载系数，若用m表示散列表

12、的长度，n表示待散列存储 的元素的个数，则等于（ ）。 【答案】n/m 82. 设图的顶点数为n，则求解最短路径的Dijkstra算法的时间复杂度为( )。 【答案】O(n2) 83. 已知一棵3阶B树中含有50个关键字，则该树的最大高度为( ( ) )。 【答案】5 84. 从一棵二叉排序树中查找一个元素时，若给定值大于根结点的值，则需要向（ ）继续查找。 【答案】 右子树 85. 链接存储表示的结点存储空间一般在程序的运行过程中进行动态地( ( ) )和释放。 【答案】 分配 86. 线性表的链接存储只能通过( ( ) )顺序访问。 【答案】 链接指针87. 直接插入排序在初始有序时，进行

13、（ ）次关键字比较。 【答案】n-1 89. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫 做( ( ) )排序。 【答案】 交换 90. 单链表中逻辑上相邻的结点而在物理位置上( ( ) )相邻。 【答案】 不一定 91. 链表只适用于( ( ) )查找。 【答案】 顺序 92. 在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用( ( ) )次 调整算法。 【答案】n-193. 向一个顺序栈插入一个元素时，首先使（ ）后移一个位置，然后把待插入元素写入到这个位置上。【答案】栈顶指针94. 在带表头结点的单链表中删除某

14、一指定结点，必须找到该结点的（ ）结点。 【答案】前一个95. 在一棵高度为3的四叉树中，最多含有（ ）个结点，假定树根结点的高度为0。 【答案】85 96. 在含有3个结点a，b，c的二叉树中，前根序列为abc且后根序列为cba的二叉树有（ ）棵。 【答案】4 97. 设图G = (V, E)，V = V0, V1, V2, V3, E = (V0, V1), (V0, V2), (V0, V3), (V1, V3)，则 从顶点V0开始的图G的不同深度优先序列有( ( ) )种。 【答案】4 98. 在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是( ( )

15、)。 【答案】 选择排序 99. 在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作( ( ) )。 【答案】 存储密度 100. 用邻接矩阵存储图，占用的存储空间与图中的( ( ) )数有关。 【答案】 顶点 101. 对称矩阵的行数与列数( ( ) )且以主对角线为对称轴，aij = aji，因此只存储它的上三角部分或下三 角部分即可。 【答案】 相等 102. 在直接选择排序中，记录移动次数的时间复杂度为( ( ) )。 【答案】O(n) 103. 对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为( ( ) )。【答案】 （15，12，11，10，8，16，18，17，13，19）104. 已知完全二叉树有200个结点,则整个二叉树有（ ）个度为1的结点。 【答案】1 105. 普里姆算法适用于求（ ）的网的最小生成树。 【