发布时间 : 星期五 文章2015(1)年度中国石油大学数据结构试题及答案更新完毕开始阅读5709dbb731d4b14e852458fb770bf78a65293ab7
可唯一确定这棵二叉树。
21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。 22、已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。若完全二叉树的第7有10个叶子结点，则整个二叉树的结点数最多是（235）
23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。
24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（ ５ ），判定树中前５层的结点数为（３１），最后一层的结点数为（１９）。
25、在一个无向图中，所有顶点的度数之和等于所有边数的（２）倍。在一个具有n个顶点的无向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n个顶点的有向完全图中，包含有（ n(n-1) ）条边。
26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（n）和（n-1）。
27、设线性表中元素的类型是实型，其首地
址为1024，则线性表中第6个元素的存储位置是( 1044)。
28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序，则最好选择（选择排序）。
29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。 30、对于一个具有n个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为（n） 31、构造哈希函数有三种方法，分别为(平方取中)法、(除留余数)法、(折迭移位)法。 32、处理冲突的三种方法，分别为(线性探测)、（ 随机探测 ）、（ 链地址法）。
33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其
2
时间复杂度为（ Ｏ（n） ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（Ｏ（elog2e） ）
34、快速排序在平均情况下的时间复杂度为（Ｏ（nlog2n）），在最坏情况下的时间复
2
杂度为（Ｏ（n））；快速排序在平均情况下的空间复杂度为（Ｏ（log2n）），在最坏情况下的空间复杂度为（Ｏ（n））。
35、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行归并排序的过程中，第二趟排序后的结果是（［３８ ４６ ５６ ７９］［４０ ８０］） 36、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行快速排序的第一次划分的结果是（［３８ ４０］４６［５６ ７９ ８０］）。
37、一个结点的子树的（ 个数 ）称为该结点的度。度为（ 零 ）的结点称为叶结点或终端结点。度不为（ 零 ）的结点称为分支结点或非终端结点。树中各结点度的（ 最大值 ）称为树的度。 38、设Ki=Kj (1<=i<=n, 1<=j<=n,j<>i)且在排序前的序列中Ri领先于Rj (i 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”的个数的一半是图中的（边数）。