1、计算机学科专业基础综合数据结构-7 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：28，分数：74.00)1.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL 为_。（分数：2.00）A.(n-1)/2B.n/2C.(n+1)/2Dn顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为_，二分法查找只适用于查找顺序存储的有序表，平均比较次数为_。在此假定 N 为线性表中结点数，且每次查找都是成功的。（分数：4.00）A.N+1B.2log2NC.log2ND.N/2E.Nlog2NFN2A
2、.N+1B.2log2NC.log2ND.N/2E.Nlog2NFN22.下面关于二分查找的叙述正确的是_。（分数：2.00）A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型、实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储二叉查找树的查找效率与二叉树的_有天，在_时查找效率最低。（分数：4.00）A.高度B.结点的多少C.树形D.结点的位置A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂3.当采用分块查找时，数据的组织方式为_。（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不
3、必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同4.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法?_（分数：2.00）A.分块B.顺序C.二分法D.哈希5.对于有 n 个数据元素的顺序存储的表，一个递增有序，另一个无序，查找一个元素时采用顺序算法，对有序表从头开始查找，发现当前运算已小于待查找元素时停止查找，确定查找不成功。已知查找任何一个元素的概率相同，则在两种表中成功查找_。（分数：2.00）A.平均时间后者小B
4、.无法确定C.平均时间前者小D.平均时间相同6.下面关于 B-树和 B+树的叙述中，不正确的是_。（分数：2.00）A.B-树和 B+树都是平衡的多分树B.B-树和 B+树都可用于文件的索引结构C.都能有效地支持随机检索D.都能有效地支持顺序检索7.关于 B-树，下列说法不正确的是_。（分数：2.00）A.B-树是一种查找树B.所有的叶结点具有相同的高度C.2-3 树中，所有非叶子结点有 1 或者 3 个孩子结点D.通常情况下，B-树不是二叉树8.在采用线性探测法处理冲突，在所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值_。（分数：2.00）A.一定都
5、是同义词B.一定都不是同义词C.不一定都是同义词D.都相同9.关于散列表的平均查找长度，下列说法正确的是_。（分数：2.00）A.与处理冲突的方法有关，但与表的长度无关B.与处理冲突的方法有关，且与表的长度有关C.与处理冲突的方法无关，但与表的长度有关D.与处理冲突的方法无关，且与表的长度无关10.关于散列表，下列说法不正确的是_。（分数：2.00）A.散列函数以结点关键字为其输入，其输出为结点的存储地址B.Hash 冲突指同一个关键字对应多个不同的 Hash 地址C.在散列存储中，装入因子的值越大，则存取结点时发生冲突的概率就越大D.散列存储法只能存储数据元素的值，但会破坏数据元素之间的关系
6、11.若查找每个元素的概率相等，则在长度为 n 的顺序表上查找到表中任一元素的平均查找长度为_。（分数：2.00）AnB.n+1C.(n-1)/2D.(n+1)/212.对长度为 n 的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一无素的查找成功的平均查找长度为_。（分数：2.00）A.n/2B.(n+1)/2C.(n-1)/2D.n/4对应长度为 n 的有序顺序表，若采用折半查找，则对所有元素的平均查找长度为_的值向上取整，或者为_的值向下取整加一，查找任一元素的时间复杂度为_。（分数：6.00）A.log2(n+1)B.log2nC.n/2D.(n+1)/2A.log2(n+1)
7、B.log2nC.n/2D.(n+1)/2A.O(n)B.O(n2)C.O(1)D.O(log2n)对于长度为 9 的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为_，查找不成功的平均查找长度为_。对于长度为 18 的有序顺序表，若采用折半查找，则查找第 15 个元素的查找次数为_。（分数：6.00）A.20/9B.18/9C.25/9D.34/9A.20/10B.18/10C.25/10D.34/10A.3B.4C.5D.6当对一个线性表 R60进行索引顺序查找(分块查找)时，若共分成了 10 个子表，每个子表有 6 个表项。假定对索引表和数据子表都采用顺序查找，则查找每
8、一个表项的平均查找长度为_。既希望较快的查找又便于线性表动态变化的查找方法是_。（分数：4.00）A.7B.8C.9D.10A.顺序查找B.折半查找C.散列查找D.索引顺序查找13.散列函数有共同的性质，即函数值应当以_概率取其值域的每一个值。（分数：2.00）A.最大B.最小C.平均D.同等14.设散列地址空间为 0m-1，key 为表项的关键字，散列函数采用除留余数法，即 Hash(key)=key%p。为了减少发生冲突的频率，一般取 p 为_。（分数：2.00）AmB.小于等于 m 的最大质数C.大于 m 的最小质数D.小于等于 m 的最大合数15.在开地址法中散列到同一个地址而引起的“
9、堆积”问题是由于_引起的。（分数：2.00）A.同义词直接发生冲突B.非同义词直接发生冲突C.同义词之间或非同义词之间发生冲突D.散列表“溢出”16.在采用拉链法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的_相同。（分数：2.00）A.关键字值B.元素值C.散列地址D.含义17.对长度为 10 的顺序表进行查找，若查找前面 5 个元素的概率相同，均为 1/8，查找后面 5 个元素的概率相同，均为 3/40，则查找到表中任一元素的平均查找长度为_。（分数：2.00）A.5B.5C.39/8D.19/418.对长度为 3 的顺序表进行查找，若查找第一个元素的概率为 1/2，查找第二个元
10、素的概率为 1/3，查找第三个元素的概率为 1/6，则查找到表中任一元素的平均查找长度为_。（分数：2.00）A.5/3B.2C.7/3D.4/3在 10 阶 B 树中根结点所包含的关键字个数最多为_，最少为_。（分数：4.00）A.7B.8C.9D.10A.0B.1C.3D.4在一棵高度为 h 的 B 树中，叶结点处于第_层，插入一个新关键字时，为查找插入位置需读取_个结点。（分数：4.00）A.h-1BhC.h+1D.h+2A.h-1BhC.h+1D.h+219.E 知一棵 10 阶 B+树中含有 960 个关键码，则该树的最小高度为_。（分数：2.00）A.3B.5C.10D.1220.
11、设有一个含 200 个表项的散列表，用线性探测法解决冲突，按关键字查询时找到一个表项的平均探测次数不超过 1.5，则散列表项应能够至少容纳_个表项。 (设查找成功的平均查找长度为 Snl=1+1/(1-)/2，其中 为装填因子)（分数：2.00）A.400B.526C.624D.67621.对包含 n 个元素的散列表进行查找，平均查找长度_。（分数：2.00）A.为 O(log2n)B.为 O(n)C.不直接依赖于 nD.直接依赖于 m二、综合应用题(总题数：7，分数：26.00)22.写出含有下列元素a，g，f，b，k，d，h，m，j，e，s，i，r，x，c，l，n，t，u，p的 5 阶 B
12、-树生成过程。 （分数：2.50）_23.编写一个在顺序表上执行顺序查找的递归算法，在算法的参数表中增加一个整数形参 loe，指明查找的开始位置。函数的首部为： int seqSearch1 (seqList 其中，DataType 是顺序表中每个元素的数据类型，假设已经定义可直接使用。 （分数：2.50）_24.编写一个递归算法实现在有序顺序表上的折半查找。算法的参数表中应增加两个形参 left 和 right，分别指定算法在本层之下时的奁找区间均左、右端点。当查找成功时函数返回查找到的元素的存放位置；当查找不成功时函数返回-1。 递归算法的首部为 int binarySearch1(seq
13、List其中，DataType 是顺序表中每个元素的数据类型，假设已经定义可直接使用。 （分数：2.50）_正确答案：()解析：使用递归算法实现顺序查找的基本思想是：先判断是否检测到表尾，是则返回 L.n，表示查找失败，次数 loc(0locL.n-1)停留在 L.n 位置，函数返回-1。不是则再判断位于 loc 位置的元素的关键字是否等于 x，是则查找成功，返回元素的位置。否则算法递归检测下一个位置 loc+1。该递归算法的调用语句形式为： int Pos=seqSearch1(L,x,0); int seqSearchl(seqList /查找不成功 else if(L.dataloc=x
14、)return loc; /查找成功 else return seqSearchl(L,x,loc+1); /继续递归查找 每次递归，查找区间的左端点向待查找元素所在位置逼近一个位置，直到递归到达待查找元素所在位置，查找成功。如果递归下去，直到查找区间为空(loc=L.n)，查找失败。函数返回找到的位置。算法的递归深度与待查找元素在表中的位置有关，最好情形是一开始就找到待查找元素，递归深度为 l；最坏情形是递归深度等于表的长度 O(n)。24.编写一个递归算法实现在有序顺序表上的折半查找。算法的参数表中应增加两个形参 left 和 right，分别指定算法在本层之下时的奁找区间均左、右端点。当
15、查找成功时函数返回查找到的元素的存放位置；当查找不成功时函数返回-1。 递归算法的首部为 int binarySearch1(seqList if (left=right) mid=(left+right)/2; if(xdatamid)mid=binarySearchl(L,x,mid+1,right); /右缩区间 else if(xdatamid)mid=binarySearch(L,x,left,mid-1); /左缩区间 return mid; 这个算法把规模为 n 的复杂问题经一次递归调用转化为一个规模减半的小子问题求解，再经过一次递归调用转化为规模再减半的更小子问题求解，如此继续
16、，直到最终能够直接找到解为止。算法的时间复杂度为：T(n)=c+T(n/2)=c+(c+T(n/4)=2c+T(n/4)=2c+(c+T(n/8)=3c+T(n/8)=clog 2 n+T(1)。算法中用到一个递归工作栈，其规模与递归深度直接相关，也是 O(log 2 n)。25.利用 B 树作文件索引时，若假设磁盘页块的大小是 4000 字节(实际应是 2 的 n 次幂，题目为了计算方便，假定是 4000 字节)，指示磁盘地址的指针需要 5 个字节。现在有 20000000 个记录构成的文件，每个记录为 200 字节，其中包括关键字 5 个字节。 试问在此采用 B 树作索引的文件中，B 树的
17、阶数应为多少?假定文件数据部分未按关键字有序排列，则索引部分需要占用多少磁盘页块? （分数：2.50）_正确答案：()解析：根据 B 树的概念，一个索引结点应适应操作系统一次读写的物理记录大小，其大小应取不超过但最接近一个磁盘页块的大小。假设 B 树为 m 阶，一个 B 树结点最多存放 m-1 个关键字(5 个字节)和对应的记录地址(5 个字节)，外加 m 个子树指针(5 个字节)和 1 个指示结点中实际关键字个数的整数(2 个字节)。根据假设，每个关键字和指针都占用 5 个字节，则有： 2(m-1)+n5+24000 计算结果，m267。 一个索引结点最多可以存放 m-1=266 个索引项，
18、最少可以存放m/2-1=133 个索引项。全部有 n=20000000个记录，每个记录占用空间 200 个字节，每个页块可以存放 4000/200=20 个记录，则全部记录分别在20000000/20=1000000 个页块中，则最多需要占用 1000000/133=7519 个磁盘页块作为 B 树索引，最少需要占用 1000000/266=3759 个磁盘页块作为 B 树索引。(注意 B 树与 B+树的不同。B 树所有对数据记录的索引项分别在各个层次的结点中，B+树所有对数据记录的索引项都在叶结点中)一棵 2-3 树的形状定义如下： 一个结点包含一个关键字或两个关键字。 每个结点最少有两个子
19、女(如果它包含一个关键字)，最多有三个子女(如果它包含两个关键字)。 每个结点的结构是(leftChild,leftKey,midChild,rightKey,rightChild)。 其中，关键字 leftKeyrightKey，且指针 leftChild 所指子树上所有结点包含的关键字均小于leftKey；指针 midChild 所指子树上所有结点包含的关键字均大于 leftKey，小于 rightKey；指针：rightChild 所指子树上所有结点包含的关键字均大于 rightKey。 所有失败结点都在树的同一层上，它们都是查找失败到达的结点，指向它们的指针都是空的。因此树的高度总是平
20、衡的。 根据以上定义，试回答下列问题，并说明理由：（分数：11.00）(1).2-3 树可否看作是 B 树的特殊情况?（分数：2.75）_正确答案：()解析：2-3 树可以看作是 3 阶 B 树，它们在形态上都是一样的，都是有序树。但 2-3 树定义中有左、中、右子树之分，B 树是第 0 棵、第 1 棵、第 2 棵子树。(2).2-3 树可否看作是平衡的 3 叉查找树?（分数：2.75）_正确答案：()解析：2-3 树可以看作是平衡 3 叉查找树。正像 B 树可以继承 m 路查找树一样，2-3 树可以继承 3 叉查找树，但平衡性要求更高。(3).平衡的 3 叉查找树可否看作是 2-3 树?（分
21、数：2.75）_正确答案：()解析：平衡的 3 路查找树不一定是 2-3 树。因为平衡的 3 叉查找树的叶结点不要求一定在同一层上，而2-3 树有此要求。(4).二叉排序树可否看作是二叉树的特殊情况?（分数：2.75）_正确答案：()解析：二叉排序树是二叉树的特殊情况，二叉排序树继承了二叉树，但它限制结点中的数据必须满足：根的左子树中所有结点的关键字值必须小于根结点的关键字值，根的右子树中所有结点的关键字值必须大于根结点的关键字值。26.下图是一个 3 阶 B 树。分别画出在插入 65、15、40、30 后 B 树的变化。 （分数：2.50）_正确答案：()解析：插入过程： 插入 65 后，如下图所示： 插入 65 后的 3 阶 B 树插入 15 后，如下图所示： 插入 15 后的 3 阶 B 树插入 40 后，如下图所示： 插入 40 后的 3 阶 B 树插入 30 后，如下图所示： 27.下图是一个 3 阶 B 树。试分别画出在删除 50、40 之后 B 树的变化。 （分数：2.50）_正确答案：()解析：删除过程，如图 1 和图 2 所示： 图 1 插入 50 后的 3 阶 B 树
