30、对于一个具有n个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为（n）
31、构造哈希函数有三种方法，分别为(平方取中)法、(除留余数)法、(折迭移位)法。
32、处理冲突的三种方法，分别为(线性探测)、（ 随机探测 ）、（ 链地址法）。 33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（ Ｏ（n2） ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（Ｏ（elog2e） ）
34、快速排序在平均情况下的时间复杂度为（Ｏ（nlog2n）），在最坏情况下的时间复杂度为（Ｏ（n2））；快速排序在平均情况下的空间复杂度为（Ｏ（log2n）），在最坏情况下的空间复杂度为（Ｏ（n））。
35、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行归并排序的过程中，第二趟排序后的结果是（［３８ ４６ ５６ ７９］［４０ ８０］）
36、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行快速排序的第一次划分的结果是（［３８ ４０］４６［５６ ７９ ８０］）。 37、一个结点的子树的（ 个数 ）称为该结点的度。度为（ 零 ）的结点称为叶结点或终端结点。度不为（ 零 ）的结点称为分支结点或非终端结点。树中各结点度的（ 最大值 ）称为树的度。
38、设Ki=Kj (1<=i<=n, 1<=j<=n,j<>i)且在排序前的序列中Ri领先于Rj (i 40 、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（Ｏ（log2n）），整个排序过程的时间复杂度为（Ｏ（nlog2n））。 41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两项。 42、假定一个线性表为 （”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”）,若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为（３），（３），（２）。 43、对于包含５０个关键码的３阶B-树，其最小高度为（４），最大高度为（５）。 44、从一棵B-树删除关键码的过程，若最终引起树根结点的合并，则新树比原树的高度（减１） 45、假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表的长度平均为（５）。 46、在散列存储中，装载因子α又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则α等于（n/m）。 47、在有向图的邻接矩阵中，第i行中“1”的个数是第i个顶点的（出度），第i列中“1”的个数是第i个顶点的（入度）。在无向图的邻接矩阵中，第i行（列）中“1”的个数是第i个顶点的（度），矩阵中“1”的个数的一半是图中的（边数）。 48、在对m阶B-树中，每个非根结点的关键码数最少为（「m/2┐-1）个，最多为（m-1）个，其子树棵数最少为（「m/2┐），最多为（m）。 三、 判断题 1、 数据元素是数据的最小单位（╳）。 2、 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的(√). 3、 数据结构是指相互之间存在一种或多种关系的数据元素的全体（╳）。 4、 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构（√）。 5、 线性表的逻辑顺序与物理顺序总是一致的（╳）。 6、 二维数组是其数组元素为线性表的线性表（╳）。 7、 每种数据结构都应具备三种基本运算：插入、删除、搜索（√）。 8、 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。（╳ ） 9、 空串与由空格组成的串没有区别。（╳ ） 10、将T在S中首次出现的位置作为T在S中的位置的操作称为串的模式匹配。（√） 11、深度为h的非空二叉树的第h层最多有2h-1个结点（╳ ） 12、完全二叉树就是满二叉树。（╳） 13、已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。（√ ） 14、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。（√） 15、线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。（ √ ） 16、若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则 它一定是该子树的前序遍历结果序列的最后一个结点。（√） 17、任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。（╳） 18、最优二叉搜索树一定是平衡的二叉搜索树。（√） 19、AOE网是一种带权的无环连通图。（√ ） 20、对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的（╳）。 21、二叉排序树可以是一棵空树（√ ） 22、线性表中所有结点的类型必须相同。 （√ ） 23、n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。（√ ） 24、任何无环的有向图，其结点都可以排在一个拓扑序列里。（√ ） 25、队列逻辑上是一个下端口和上端能增加又能减少的线性表（╳ ） 26、二叉树是树的一种特殊情况（ √ ） 27、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关（√）。 28、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（╳） 29、连通分量是无向图中的极小连通子图。（╳） 30、在ＡＯＥ网络中一定只有一条关键路径。（╳） 31、关键活动不按期完成就会影响整个工程的完成时间。（√） 32、平衡二叉树的左右子树深度之差的绝对值不超过1。（√ ） 33、快速排序是对起泡排序的一种改进。( √ ) 34、直接选择排序稳定。（ ╳ ） 35、堆排序占用的辅助空间很大。（ ╳ ） 36、在散列法中采取开散列法来解决冲突时，其装载因子的取值一定在（０，１） 之间。（╳） 37、B-树是一种动态索引结构，它既适用于随机搜索，也适用于顺序搜索。（ ╳） 38、在散列法中，一个可用散列函数必须保证绝对不产生冲突。（╳） 39、任何一个关键活动延迟，那么整个工程将会延迟。（√） 40、任何一个关键活动提前完成，那么整个工程将会提前完成。（╳） 四、运算应用题 1、在一个有n个元素的顺序表的第i个元素（1 ? i ? n）之前插入一个新元素时，需要向后移动多少个元素？ 答案：需要向后移动 n- i + 1个元素 2、当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321是否是合理的出栈序列？ 答案： 1114?13?12?11?10?9?87C14???4297?187?6?5?4?3?2?1 可能的出栈序列有 种，6457321不是合理的出栈序列。 3、简单（直接）选择排序是一种稳定的排序方法吗？试举例说明？ 答案：是不稳定的排序方法。下面就是不稳定的例子。只要能举出反例即可。 { 275 275* 512 061 } i = 1 { 061 275* 512 275 } i = 2 { 061 275* 512 275 } i = 3 { 061 275* 275 512 }