《数据结构期末综合练习二》由会员分享，可在线阅读，更多相关《数据结构期末综合练习二（22页珍藏版）》请在金锄头文库上搜索。
1、数据结构期末综合练习二数据结构期末综合练习二 填空题 1. 数据是_信息_的载体，它能够被计算机程序识别、存储和加工处理。 2. 数据结构包括逻辑结构、_存储结构_和数据的运算三个方面。 3. 数据结构的逻辑结构包括线性结构和_非线性_结构两大类。 4. 数据结构的存储结构包括顺序、_链接_、索引和散列等四种。 5. 基本数据类型是计算机已经实现了的_数据结构_。 6. 抽象数据类型的特点是_数据封装_、信息隐蔽、使用与实现分离。 7. 算法的一个特性是_有穷性_，即算法必须执行有限步就结束。 8. 面向对象的特征应包括对象、类、_继承_、消息通信。 9. 属性与服务相同的对象构成类，类中的每
2、个对象称为该类的_实例_。 10. 对象的私有状态只能通过该对象的_操作_才能改变。 11. 模板类是一种数据抽象，它把_数据类型_当作参数，可以实现类的复用。 12. 在类的继承结构中，位于上层的类叫做基类，其下层的类则叫做_派生_类。 13. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的_下标_存取的。 14. 在程序运行过程中不能扩充的数组是_ 静态_分配的数组。这种数组在声明它时必须指定它的大小。 15. 在程序运行过程中可以扩充的数组是_ 动态_分配的数组。这种数组在声明它时需要使用数组指针。 16. 二维数组是一种非线性结构，其中的每一个数组元素最多有_两
3、个_个直接前驱。 17. 若设一个nn的矩阵A的开始存储地址LOC(0, 0) 及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素aij的存储地址为_ LOC(0,0)+(i*n+j)*d_。 1 18. 对称矩阵的行数与列数_相等 _且以主对角线为对称轴，aij = aji，因此只存储它的上三角部分或下三角部分即可。 19. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储_n(n+1)/2 _个矩阵元素。 20. 将一个n阶对称矩阵A的上三角部分按行压缩存放于一个一维数组B中，A00存放于B0中，则AIJ在IJ时将存放于数组B的_(2n-I-1)
4、*I/2+J_位置。 21. 利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和_值_。 22. 线性表是由n个_数据元素_组成的有限序列。 23. 若设串S = “documentHash.doc0”，则该字符串S的长度为_16_。 24. 链表是一种采用 链式 存储结构存储的线性表。 25. 链表只适用于 顺序 查找。 26. 在链表中进行插入和 删除 操作的效率比在顺序存储结构中进行相同操作的效率高。 27. 链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的_指针域_的值。 28. 链接存储表示的结点存储空间一般在程序的运行过
5、程中进行动态地_分配_和释放。 29. 单链表中逻辑上相邻的结点而在物理位置上_不一定_相邻。 30. 在单链表中, 除了表头结点外, 任意结点的存储位置由其直接_前驱_结点的指针域的值所指示。 31. 在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对_表头指针_进行特殊处理。 32. 若设L是指向带表头的单链表, 语句 L-link=L-link-link的作用是_删除_单链表中的第一个结点。 33. 在双向链表中, 每个结点除了数据域外, 还有两个指针域, 它们分别指向_前趋结点和后继结点_。 34. 线性表的链接存储只能通过_链接指针_顺序访问。 2 35. 链表与顺序表、索
6、引表、散列表等都是数据逻辑结构的_存储_表示。 36. 设双向循环链表每个结点结构为(data,llink,rlink),则结点*p的前驱结点的地址为_p-llink_。 37. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为_后出先进_表。 38. 队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为_先进先出_表。 39. 向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给_栈顶指针_。 40. 队列的删除操作在_队头_进行。 41. 向一个顺序栈插入一个元素时，首先使_栈顶指针_后移一个位置，然后把待插入元素写入到这个位置上。
7、 42. 若设顺序栈的最大容量为MaxSize，top=-1表示栈空，则判断栈满的条件是_top=MaxSize-1_。 43. 当用长度为MaxSize的数组顺序存储一个栈时，若用top = MaxSize表示栈空，则表示栈满的条件为_top = 0 _。 44. 向一个循环队列中插入元素时，需要首先移动_队尾_指针，然后再向所指位置写入新元素。 45. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行_p-link=top_和top=p操作。 46. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有_1_个结点。 47. 在一个链式队列中，若队头指针与队尾指针
8、的值相同，则表示该队列至多有_ 一_个结点。 48. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_递归_的对象。 49. 如果一个过程直接或间接地调用自己，则称这个过程是一个_递归_的过程。 50. 递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和_局部变量_。 51. 函数内部的局部变量是在进入函数过程后才分配存储空间，在函数过程执行结束后就_释放_局部变量所占用的存储空间。 3 52. 迷宫问题是一个回溯控制的问题，最好使用_递归_的方法来解决。 53. 非空广义表的除第一个元素外其他元素组成的表称为广义表的_表尾_
9、。 54. 广义表A ( (a, b, c), (d, e, f ) ) 的表尾为_( (d, e, f ) ) _。 55. 广义表是一种递归的数据结构，子表结点则指示下一层广义表的_表头结点_。 56. 广义表的深度定义为广义表括号的_重数_。 57. 对于一棵具有n个结点的树，该树中所有结点的度数之和为_n-1_。 58. 一棵树的广义表表示为a(b(c,d(e,f),g(h),i(j,k(x,y)，结点k的所有祖先的结点数为_2_个。 59. 一棵树的广义表表示为a(b(c,d(e,f),g(h),i(j,k(x,y)，结点f的层数为_3 _。假定树根结点的层数为0。 60. 假定一棵
10、三叉树的结点个数为50，则它的最小高度为_ 4 _。假定树根结点的深度为0。 61. 在一棵高度为3的四叉树中，最多含有_85_个结点，假定树根结点的高度为0。 62. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有_6_个。 63. 一棵高度为5的完全二叉树中，最多包含有_ 63 _个结点。假定树根结点的高度为0。 64. 假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)，则该树的高度为_3_。假定树根结点的高度为0。 65. 在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为_ 6 _个。 6
11、6. 假定一棵二叉树的结点数为18，则它的最小高度为_4_。假定树根结点的高度为0。 67. 在一棵高度为h的理想平衡二叉树中，最少含有_ 2 _个结点。假定树根结点的高度为0。 68. 在一棵高度为h的理想平衡二叉树中，最多含有_2-1_个结点。假定树根结点的高度为0。 h+1h 4 69. 若将一棵树A(B(C,D,E),F(G(H),I)按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点的个数为_2_个。 70. 将一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有_右_子女。 71. 在一个堆的顺序存储中，若一个元素的下标为i(0in-1)，则它的
12、左子女元素的下标为_2i+1_。 72. 在一个堆的顺序存储中，若一个元素的下标为i(0in-1)，则它的右子女元素的下标为_2i+2_。 73. 在一个最小堆中，堆顶结点的值是所有结点中的_ 最小值_。 74. 在一个最大堆中，堆顶结点的值是所有结点中的_最大值_。 75. 以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素的渐进时间复杂度为_ O(n)_。 76. 对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为pi,搜索长度为ci，则在搜索成功情况下的平均搜索长度的计算公式为_pc_。 iii=1n 77. 假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，则在
13、搜索成功情况下的平均搜索长度为_20.5_。 78. 从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为_3_。 79. 假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为_19_个。 80. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向_右子树_继续搜索。 81. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_左子树_上。 82. 根据n个元素建立一棵二叉搜索树的渐进时间复杂度大致为_O(nlog2n)_。 83. 在一棵AVL树中，每个结点的左子树高度与右子树高度
14、之差的绝对值不超过_1_。 5 84. 根据一组记录(56,42,50,64,48)依次插入结点生成一棵AVL树时，当插入到值为_50_的结点时需要进行旋转调整。 85. 根据一组记录(56,74,63,64,48)依次插入结点生成一棵AVL树时，当插入到值为63的结点时需要进行_先右后左双旋转_调整。 86. 根据一组记录(56,42,38,64,48)依次插入结点生成一棵AVL树时，当插入到值为38的结点时需要进行_右单旋转_调整。 87. 根据一组记录(56,42,73,50,64,48,22)依次插入结点生成一棵AVL树时，当插入到值为_ 64 _的结点时才出现不平衡，需要进行旋转调整。 88. 在一棵具有n个结点的AVL树上进行插入或删除元素的渐进时间复杂度大致为_O(log2n)_。 89. n (n0) 个顶点的连通无向图各顶点的度之和最少为_2(n-1)_。 90. 用邻接矩阵存储图，占用的存储空间与图中的_顶点_数有关。 91. 设图G = (V, E)，V = V0, V1, V2, V3, E = (V0, V1), (V0, V2), (V0, V3), (
