数据结构（本科）期末综合练习二（填空与判断题）

数据结构（本科）期末综合练习二（填空与判断题）

填空题

1.数据是________的载体，它能够被计算机程序识别、存储和加工处理。

2.数据结构包括逻辑结构、________和数据的运算三个方面。

3.数据结构的逻辑结构包括线性结构和________结构两大类。

4.数据结构的存储结构包括顺序、________、索引和散列等四种。

5.基本数据类型是计算机已经实现了的________。

6.抽象数据类型的特点是________、信息隐蔽、使用与实现分离。

7.算法的一个特性是________，即算法必须执行有限步就结束。

8.面向对象的特征应包括对象、类、________、消息通信。

9.属性与服务相同的对象构成类，类中的每个对象称为该类的________。

10.对象的私有状态只能通过该对象的________才能改变。

11.模板类是一种数据抽象，它把________当作参数，可以实现类的复用。

12.在类的继承结构中，位于上层的类叫做基类，其下层的类则叫做________类。

13.一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的_________存取的。

14.在程序运行过程中不能扩充的数组是__________分配的数组。这种数组在声明它时必须指定它的大小。

15.在程序运行过程中可以扩充的数组是__________分配的数组。这种数组在声明它时需要使用数组指针。

16.二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或直接后继）。

17.若设一个n´n的矩阵A的开始存储地址LOC(0,0)

及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素a[i][j]的存储地址为_________。

18.对称矩阵的行数与列数_________且以主对角线为对称轴，aij

=

aji，因此只存储它的上三角部分或下三角部分即可。

19.将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储_________个矩阵元素。

20.将一个n阶对称矩阵A的上三角部分按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中，则A[I][J]在I≤J时将存放于数组B的_________位置。

21.利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和_________。

22.线性表是由n（n≥0）个_________组成的有限序列。

23.若设串S

=

“documentHash.doc＼0”，则该字符串S的长度为_________。

24.链表是一种采用

存储结构存储的线性表。

25.链表只适用于

查找。

26.在链表中进行插入和

操作的效率比在顺序存储结构中进行相同操作的效率高。

27.链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的__________的值。

28.链接存储表示的结点存储空间一般在程序的运行过程中进行动态地_______和释放。

29.单链表中逻辑上相邻的结点而在物理位置上_______相邻。

30.在单链表中,除了表头结点外,任意结点的存储位置由其直接_____结点的指针域的值所指示。

31.在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对________进行特殊处理。

32.若设L是指向带表头的单链表,语句

L->link=L->link->link的作用是________单链表中的第一个结点。

33.在双向链表中,每个结点除了数据域外,还有两个指针域,它们分别指向_________________。

34.线性表的链接存储只能通过________顺序访问。

35.链表与顺序表、索引表、散列表等都是数据逻辑结构的__________表示。

36.设双向循环链表每个结点结构为(data,llink,rlink),则结点*p的前驱结点的地址为__________。

37.栈是一种限定在表的一端进行插入和删除的线性表，又被称为___________表。

38.队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为________表。

39.向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给________。

40.队列的删除操作在________进行。

41.向一个顺序栈插入一个元素时，首先使________后移一个位置，然后把待插入元素写入到这个位置上。

42.若设顺序栈的最大容量为MaxSize，top==-1表示栈空，则判断栈满的条件是________________。

43.当用长度为MaxSize的数组顺序存储一个栈时，若用top

==

MaxSize表示栈空，则表示栈满的条件为________。

44.向一个循环队列中插入元素时，需要首先移动________指针，然后再向所指位置写入新元素。

45.向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行________和top=p操作。

46.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有________个结点。

47.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有________个结点。

48.如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_________的对象。

49.如果一个过程直接或间接地调用自己，则称这个过程是一个________的过程。

50.递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和_________。

51.函数内部的局部变量是在进入函数过程后才分配存储空间，在函数过程执行结束后就________局部变量所占用的存储空间。

52.迷宫问题是一个回溯控制的问题，最好使用__________的方法来解决。

53.非空广义表的除第一个元素外其他元素组成的表称为广义表的________。

54.广义表A

（(a,b,c),(d,e,f))的表尾为________。

55.广义表是一种递归的数据结构，子表结点则指示下一层广义表的________。

56.广义表的深度定义为广义表括号的________。

57.对于一棵具有n个结点的树，该树中所有结点的度数之和为______。

58.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点k的所有祖先的结点数为________个。

59.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为_________。假定树根结点的层数为0。

60.假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为________。假定树根结点的深度为0。

61.在一棵高度为3的四叉树中，最多含有________个结点，假定树根结点的高度为0。

62.在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有________个。

63.一棵高度为5的完全二叉树中，最多包含有________个结点。假定树根结点的高度为0。

64.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则该树的高度为________。假定树根结点的高度为0。

65.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为________个。

66.假定一棵二叉树的结点数为18，则它的最小高度为________。假定树根结点的高度为0。

67.在一棵高度为h的理想平衡二叉树中，最少含有________个结点。假定树根结点的高度为0。

68.在一棵高度为h的理想平衡二叉树中，最多含有________个结点。假定树根结点的高度为0。

69.若将一棵树A(B(C,D,E),F(G(H),I))按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点的个数为________个。

70.将一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有________子女。

71.在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的左子女元素的下标为______。

72.在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的右子女元素的下标为________。

73.在一个最小堆中，堆顶结点的值是所有结点中的________。

74.在一个最大堆中，堆顶结点的值是所有结点中的________。

75.以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素的渐进时间复杂度为________。

76.对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为pi,搜索长度（即在搜索过程中依次同有关元素比较的总次数）为ci，则在搜索成功情况下的平均搜索长度的计算公式为________。

77.假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为________。

78.从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为________。

79.假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为______个。

80.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向________继续搜索。

81.向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的________上。

82.根据n个元素建立一棵二叉搜索树的渐进时间复杂度大致为_____________。

83.在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。

84.根据一组记录(56,42,50,64,48)依次插入结点生成一棵AVL树时，当插入到值为_______的结点时需要进行旋转调整。

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树时，当插入到值为_______的结点时才出现不平衡，需要进行旋转调整。

88.在一棵具有n个结点的AVL树上进行插入或删除元素的渐进时间复杂度大致为_________。

若3个顶点的图G的邻接矩阵为，则图G一定是________向图。有

89.n

(n﹥0)

个顶点的连通无向图各顶点的度之和最少为________。

90.用邻接矩阵存储图，占用的存储空间与图中的________数有关。

91.设图G

=

(V,E)，V

=

{V0,V1,V2,V3},E

=

{(V0,V1),(V0,V2),(V0,V3),(V1,V3)}，则从顶点V0开始的图G的不同深度优先序列有________种。

92.设图G

=

(V,E)，V

=

{1,2,3,4},E

=

{<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有________种。

93.n

(n﹥0)

个顶点的无向图中顶点的度的最大值为________。

94.在重连通图中每个顶点的度至少为________。

95.n个顶点的连通无向图的生成树含有________条边。

96.11个顶点的连通网络N有10条边，其中权值为1,2,3,4,5的边各2条，则网络N的最小生成树各边的权值之和为_________。

97.在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个________上，才会被加入到生成树中。

98.一般来说,深度优先生成树的高度比广度优先生成树的高度要________。

99.求解带权连通图最小生成树的Prim算法使用图的________作为存储结构。

100.设图的顶点数为n，则求解最短路径的Dijkstra算法的时间复杂度为________。

101.第i

(i

=

1,2,…,n-1)

趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做__________排序。

102.第i

(i=0,1,...,n-2)

趟从参加排序的序列中第i个至第n-1个元素中挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做_________排序。

103.每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做__________排序。

104.每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做_________排序。

105.在直接选择排序中，记录比较次数的时间复杂度为________。

106.在直接选择排序中，记录移动次数的时间复杂度为__________。

107.在堆排序中，对n个记录建立初始堆需要调用__________次调整算法。

108.在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用_________次调整算法。

109.在堆排序中，对任意一个分支结点进行调整运算的时间复杂度为____________。

110.对n个数据对象进行堆排序，总的时间复杂度为______________。

111.给定一组数据对象的关键码为{46,79,56,38,40,84}，则利用堆排序方法建立的初始堆（最大堆）为_______________。

112.快速排序在平均情况下的时间复杂度为___________。

113.快速排序在最坏情况下的时间复杂度为____________。

114.快速排序在平均情况下的空间复杂度为____________。

115.快速排序在最坏情况下的空间复杂度为____________。

116.给定一组数据对象的关键码为{46，79，56，38，40，84}，对其进行一趟快速排序处理，得到的右子表中有________个对象。

117.在对n个数据对象的二路归并排序中，每趟归并的时间复杂度为____________。

118.在对n个数据对象进行的二路归并排序中，整个归并过程的时间复杂度为___________。

119.在索引表中，每个索引项至少包含有__________域和地址域这两项。

120.假定一个线性表为

{12,23,74,55,63,40,82,36}，若按key%3条件进行划分，使得同一余数的元素成为一个子表，则包含74的子表长度为________。

121.假定一个线性表为

(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的以a为第一个字母的子表长度为________。

122.在索引表中，若一个索引项对应数据对象表中的一个表项，则称此索引为稠密索引，若对应数据对象表中的若干表项，则称此索引为________索引。

123.假定对长度n

=

100的线性表进行索引顺序搜索，并假定每个子表的长度均为，则进行索引顺序搜索的时间复杂度为________。

124.假定对长度n=100的线性表进行索引顺序搜索，并假定每个子表的长度均为，则进行索引顺序搜索的平均搜索长度为________。

125.若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为________。

126.若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则二级索引表的长度为________。

127.假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m

=

20的散列表，每个散列地址的同义词子表（单链表）的长度平均为________。

128.在线性表的散列存储中，装载因子

a

又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则

a

等于________。

129.对于包含n个关键码的m阶B树，其最小高度为____________。

130.已知一棵3阶B树中含有50个关键码，则该树的最小高度为________。

131.已知一棵3阶B树中含有50个关键码，则该树的最大高度为________。

132.在一棵m阶B树上，每个非根结点的关键码数最少为__________个。

133.在一棵m阶B树上，每个非根结点的子树最少为________棵。

134.在一棵m阶B树上，每个非根结点的关键码数最多为________个。

135.在对m阶B树插入元素的过程中，每向一个结点插入一个关键码后，若该结点的关键码个数等于________个，则必须把它分裂为2个结点。

136.在从m阶B树删除关键码的过程中，当从一个结点中删除掉一个关键码后，所含关键码个数等于ém/2ù-2个，并且它的左、右兄弟结点中的关键码个数均等于________，则必须进行结点合并。

判断题

1.数据元素是数据的最小单位。

2.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。

3.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。

4.数据的逻辑结构与数据元素本身的内容和形式无关。

5.算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。

6.只有用面向对象的计算机语言才能描述数据结构算法。

7.如果采用如下方式定义一维字符数组：

const

int

maxSize

=

30;

char

a[maxSize];

则这种数组在程序执行过程中不能扩充。

8.如果采用如下方法定义一维字符数组：

int

maxSize

=

30;

char

*

a

=

new

char[maxSize];

则这种数组在程序执行过程中不能扩充。

9.数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。

10.多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

11.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。

12.顺序表和一维数组一样，都可以按下标随机（或直接）访问。

13.插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。

14.使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

15.用字符数组存储长度为n的字符串，数组长度至少为n+1。

16.线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。

17.线性表若采用链式存储表示,在删除时不需要移动元素。

18.在线性链表中删除中间的结点时，只需将被删结点释放。

19.在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。

20.每次从队列中取出的是具有最高优先权的元素,这种队列就是优先级队列。

21.链式栈与顺序栈相比,一个明显的优点是通常不会出现栈满的情况。

22.在一个顺序存储的循环队列中,队头指针指向队头元素的后一个位置。

23.栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同。

24.在使用后缀表示实现计算器类时用到一个栈的实例,它的作用是暂存运算器对象。

25.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

26.若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。

27.在用单链表表示的链式队列Q中，队头指针为Q->front，队尾指针为Q->rear，则队空条件为Q->front

==

Q->rear。

28.递归定义的数据结构通常用递归算法来实现对它的操作。

29.递归的算法简单、易懂、容易编写，而且执行效率也高。

30.递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。

31.递归方法和递推方法本质上是一回事，例如求n!

时既可用递推的方法，也可用递归的方法。

32.用非递归方法实现递归算法时一定要使用递归工作栈。

33.将f

=

+

1/2

+

1/3+

…

+

1/n转化为递归函数时，递归部分为f

(n)

=

f

(n-1)

+

1/n，递归结束条件为f

(1)

=

1。

34.一个广义表的表头总是一个广义表。

35.一个广义表的表尾总是一个表。

36.一个广义表

（(a),（(b),c),（（(d))))的长度为3，深度为4。

37.一个广义表

（(a),（(b),c),（（(d))))的表尾是

（(b),c),（（(d)))。

38.当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。

39.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

40.二叉树是一棵无序树。

41.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。

b42.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。

43.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。

44.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的结果。

45.在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。

46.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。

47.对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。

48.对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。

49.在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。

50.线索二叉树中的每个结点通常包含有5个数据成员。

51.对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。

52.在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。

53.进行折半搜索的表必须是顺序存储的有序表。

54.能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。

55.假定有两个用单链有序表表示的集合，则这两个集合的交运算可得到一个新的集合单链表，其长度小于等于参加运算的任意一个集合单链表的长度。

56.假定有两个用单链有序表表示的集合，则这两个集合的差运算可得到一个新的集合单链表，其长度小于参加运算的任意一个集合单链表的长度。

57.折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。

58.对于同一组关键码互不相同的记录，若生成二叉搜索树时插入记录的次序不同则得到不同形态的二叉搜索树。

59.对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。

60.对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。

61.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优二叉搜索树。

62.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。

63.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。

64.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

65.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。

66.存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。

67.强连通分量是有向图中的极大强连通子图。

68.对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。

69.有回路的有向图不能完成拓扑排序。

70.在AOE网络中一定只有一条关键路径。

71.用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。

72.对于AOE网络，加速任一关键活动就能使整个工程提前完成。

73.对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。

74.在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。

75.对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。

76.图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。

77.如果无向图中每个顶点的度都大于等于2，则该图中必有回路。

78.如果有向图中各个顶点的度都大于2，则该图中必有回路。

79.图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。

80.图的广度优先搜索算法通常采用非递归算法求解。

81.对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。

82.直接选择排序是一种稳定的排序方法。

83.若将一批杂乱无章的数据按堆结构组织起来,则堆中数据必然按从小到大的顺序线性排列。

84.当输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。

85.在任何情况下，快速排序需要进行关键码比较的次数都是O(nlog2n)。

86.若用m

个初始归并段参加

k

路平衡归并排序，则归并趟数应为élog2mù。

87.堆排序是一种稳定的排序算法。

88.任何基于排序码比较的算法，对n个数据对象进行排序时，最坏情况下的时间复杂度都不会大于O(nlog2n)。

89.装载因子是散列表的一个重要参数，它反映了散列表的装满程度。

90.在用散列表存储关键码集合时，可以用双散列法寻找下一个空位置。在设计再散列函数时，要求计算出的值与表的大小m

互质。

91.一棵3

阶B树是平衡的3

路搜索树，反之，一棵平衡的3

路搜索树是3

阶B树。

92.闭散列法通常比开散列法时间效率更高。

93.一棵

m

阶

B

树中每个结点最多有

m-1

个关键码，最少有

ém/2ù-1个关键码。

94.在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。

95.在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采用折半搜索。

96.在散列法中采取开散列（链地址）法来解决冲突时,其装载因子的取值一定在(0,1)之间。

97.AVL树（平衡二叉搜索树）的所有叶结点不一定在同一层次上，同样，平衡m路搜索树的叶结点也不一定在同一层次上。

98.在一棵B树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加1。

99.向一棵B树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。

100.从一棵B树删除关键码的过程中，若最终引起树根结点的合并，则新树比原树的高度增加1。

填空题参考解答

1.信息

2.存储结构

3.非线性

4.链接

5.数据结构

6.数据封装

7.有穷性

8.继承

9.实例

10.操作（或服务）11.数据类型

12.派生（或子）

13.下标（或顺序号）14.静态

15.动态

16.两个

17.LOC(0,0)+(i*n+j)*d

18.相等19.n(n+1)/2

20.(2n-I-1)*I/2+J

21.值

22.数据元素

23.16

24.链式（或链接）

25.顺序

26.删除

27.指针域

28.分配

29.不一定

30.前驱

31.表头指针

32.删除

33.前趋结点和后继结点34.链接指针

35.存储

36.p->llink

37.后出先进

38.先进先出

39.栈顶指针

40.队头（或队首）

41.栈顶指针

42.top==MaxSize-1

43.top

==

0

44.队尾45.p->link=top

46.1

47.一

48.递归

49.递归

50.局部变量

51.释放

52.递归

53.表尾

54.（(d,e,f))

55.表头结点

56.重数

57.n-1

58.2

59.3

60.4

61.85

62.6

63.63

64.3

65.6

66.4

67.2h

68.2h+1-1

69.2

70.右

71.2i+1

72.2i+2

73.最小值

74.最大值

75.O(n)

76.77.20.5

78.3

79.19

80.右子树

81.左子树

82.O(nlog2n)

83.1

84.50

85.先右后左双旋转86.右单旋转

87.64

88.O(log2n)

89.2(n-1)

90.顶点

91.4

92.2

93.n-1

94.2

95.n-1

96.30

97.连通分量

98.高

99.邻接矩阵

100.O(n2)

101.直接插入

102.直接选择

103.交换

104.二路归并

105.O(n2)106.O(n)

107.n/2

108.n-1

109.O(log2n)

110.O(nlog2n)

111.84，79，56，38，40，46

112.O(nlog2n)

113.O(n2)

114.O(log2n)

115.O(n)

116.3

117.O(n)

118.O(nlog2n)

119.关键码

120.2

121.3

122.稀疏

123.O()124.11

125.500

126.25

127.5

128.n/m

129.élogm(n+1)ù

130.4

131.5

132.ém/2ù-1

133.ém/2ù

134.m-1

135.m

136.ém/2ù-1

判断题参考解答

1.错2.对3.错4.对5.错6.错7.对8.错9.错10.对

11.错12.对13.错14.对15.对16.对17.对18.错19.对

20.对21.对22.错23.对24.对25.对26.错27.错28.对29.错

30.对31.错32.错33.对34.错35.对36.对37.错38.对39.对

40.错41.错42.对43.错44.对45.对46.对47.错48.错49.错

50.对51.错52.对53.对54.错55.对56.错57.对58.对59.错

60.对61.对62.错63.对64.错65.对66.对67.对68.错69.对

70.错71.对72.错73.对74.对75.对76.对77.对78.错79.对

80.对81.错82.错83.错84.对85.错86.错87.错88.错89.对

90.对91.错92.错93.错94.对95.对96.错97.对98.对99.错

100.错