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. 在直接选择排序中，记录比较次数的时间复杂度为________。
21
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的线性表进行索引顺序搜索，并假定每个子表的长度均为n，则进
22
行索引顺序搜索的时间复杂度为________。
124. 假定对长度n=100的线性表进行索引顺序搜索，并假定每个子表的长度均为n，则进行索引顺序搜索的平均搜索长度为________。
125. 若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为________。
126. 若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则二级索引表的长度为________。
127. 假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m = 20的散列表，每个散列地址的同义词子表（单链表）的长度平均为________。
128. 在线性表的散列存储中，装载因子 ? 又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则 ? 等于________。
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个，并且它的左、右兄弟结点中的关键码个数均等于________，则必须进行结点合并。
23
判断题
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. 线性表若采用链式存储表示, 在删除时不需要移动元素。
24
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 + 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。
25