计算机学科专业基础综合数据结构-7
一、单项选择题(总题数：28，分数：74.00)
1.若查每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查法查一个记录，其平均查长度ASL为______。
 A.(n-1)/2
 B.n/2
 C.(n+1)/2 √
&
此结论需要考生当作定理一样的牢记。
顺序查法适用于查顺序存储或链式存储的线性表，平均比较次数为______，二分法查只适用于查顺序存储的有序表，平均比较次数为______。在此假定N为线性表中结点数，且每次查都是成功的。（分数：4.00）
 A.N+1
 B.2log2N
 C.log2N
 D.N/2 √
 E.Nlog2N
 F..N2
 A.N+1
 B.2log2N
 C.log2N √
 D.N/2
 E.Nlog2N
 F..N2
2.下面关于二分查的叙述正确的是______。
 A.表必须有序，表可以顺序方式存储，也可以链表方式存储
 B.表必须有序且表中数据必须是整型、实型或字符型
 C.表必须有序，而且只能从小到大排列
 D.表必须有序，且表只能以顺序方式存储 √
二叉查树的查效率与二叉树的______有天，在______时查效率最低。（分数：4.00）
 A.高度
 B.结点的多少
 C.树形 √
 D.结点的位置
 A.结点太多
 B.完全二叉树
 C.呈单枝树 √
 D.结点太复杂
3.当采用分块查时，数据的组织方式为______。
 A.数据分成若干块，每块内数据有序
 B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块 √
 C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块
 D.数据分成若干块，每块(除最后一块外)中数据个数需相同
本题主要考查分块查的相关概念。
4.如果要求一个线性表既能较快地查，又能适应动态变化的要求，可以采用下列哪一种查方法?______
 A.分块 √
 B.顺序
 C.二分法
 D.哈希
由于题目只说明是线性表，因此排除二分法。哈希算法虽然有最快的查效率，但建立哈希表无法适应动态变化的要求。在数据量大的查中，顺序查显然缺乏效率，因此应选择使用分块查方法。
5.对于有n个数据元素的顺序存储的表，一个递增有序，另一个无序，查一个元素时采用顺序算法，对有序表从头开始查，发现当前运算已小于待查元素时停止查，确定查不
成功。已知查任何一个元素的概率相同，则在两种表中成功查______。
 A.平均时间后者小
 B.无法确定
 C.平均时间前者小
 D.平均时间相同 √
顺序查算法的性能与查表是否有序无关，注意题目中所问是成功查的效率。
6.下面关于B-树和B+树的叙述中，不正确的是______。
 A.B-树和B+树都是平衡的多分树
 B.B-树和B+树都可用于文件的索引结构
 C.都能有效地支持随机检索
 D.都能有效地支持顺序检索 √
因为B+树所有的叶子结点中包含了全部关键字信息，以及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接，所以支持从根结点开始的随机检索和直接从叶子结点开始的顺序检索，但是B-树不具有这种结构特性，所以只支持从根结点开始的随机检索，而不支持直接从叶子结点开始的顺序检索。
7.关于B-树，下列说法不正确的是______。
 A.B-树是一种查树
 B.所有的叶结点具有相同的高度
 C.2-3树中，所有非叶子结点有1或者3个孩子结点 √
 D.通常情况下，B-树不是二叉树
B-树定义如下：
一棵m阶B-树，或者是空树，或者是满足以下性质的m叉树：
(1)根结点或者是叶子结果，或者至少有两棵子树，至多有m棵子树；
(2)除根结点外，所有非终端结点至少有1棵子树，至多有m棵子树；
(3)所有叶子结点都在树的同一层上；
(4)每个结点应包含如下信息：(n，A 0 ，K 1 ，A 0 ，A 1 ，A 2 ，…，K n ，A n )其中：
二叉树的深度为k
K(1≤i≤n)是关键字，且K＜K i+1 (1≤i≤n-1)
A i (i=0，1，…，n)为指向孩子结点的指针，且A i-1 所指向的子树中所有结点的关键字都小于K i ，A i 所指向的子树中所有结点的关键字都大于K i ；
n是结点中关键字的个数，且-1≤n≤m-1，n+1为子树的棵数。
8.在采用线性探测法处理冲突，在所构成的散列表上进行查，可能要探测多个位置，在查成功的情况下，所探测的这些位置的键值______。
 A.一定都是同义词
 B.一定都不是同义词
 C.不一定都是同义词 √
 D.都相同
采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。
9.关于散列表的平均查长度，下列说法正确的是______。
 A.与处理冲突的方法有关，但与表的长度无关 √
 B.与处理冲突的方法有关，且与表的长度有关
 C.与处理冲突的方法无关，但与表的长度有关
 D.与处理冲突的方法无关，且与表的长度无关
Hash表的查算法复杂度为O(1)，因此其与表的长度无直接关系，但它与Hash表的装入因子有关，同时与Hash表冲突处理方法有关。
10.关于散列表，下列说法不正确的是______。
 A.散列函数以结点关键字为其输入，其输出为结点的存储地址
 B.Hash冲突指同一个关键字对应多个不同的Hash地址 √
 C.在散列存储中，装入因子的值越大，则存取结点时发生冲突的概率就越大
 D.散列存储法只能存储数据元素的值，但会破坏数据元素之间的关系
Hash冲突指不同关键字被Hash函数映射到相同的地址。
11.若查每个元素的概率相等，则在长度为n的顺序表上查到表中任一元素的平均查长度为______。
&
 B.n+1
 C.(n-1)/2
 D.(n+1)/2 √
若在一个长度为n的顺序表中做顺序查，在相等查概率下平均查长度为
或
12.对长度为n的有序单链表，若查每个元素的概率相等，则顺序查表中任一无素的查成功的平均查长度为______。
 A.n/2
 B.(n+1)/2 √
 C.(n-1)/2
 D.n/4
在有序单链表上做顺序查，查成功的平均查长度与在顺序表或有序顺序表上做顺序查时的平均查长度相同，都是(n+1)/2。
对应长度为n的有序顺序表，若采用折半查，则对所有元素的平均查长度为______的值向上取整，或者为______的值向下取整加一，查任一元素的时间复杂度为______。（分数：6.00）
 A.log2(n+1) √
 B.log2n
 C.n/2
 D.(n+1)/2
 A.log2(n+1)
 B.log2n √
 C.n/2
 D.(n+1)/2
 A.O(n)
 B.O(n2)
 C.O(1)
 D.O(log2n) √
对于长度为n的有序顺序表，采用折半查时可用判定树做性能分析，该判定树可视为理想平衡树，其深度的计算与完全二叉树相同，最大深度为 ，也可以写成d= 。查任一元素的时间复杂度为O(log 2 n)。
对于长度为9的有序顺序表，若采用折半查，在等概率情况下查成功的平均查长度为______，查不成功的平均查长度为______。对于长度为18的有序顺序表，若采用折半查，则查第15个元素的查次数为______。（分数：6.00）
 A.20/9
 B.18/9
 C.25/9 √
 D.34/9
 A.20/10
 B.18/10
 C.25/10
 D.34/10 √
 A.3
 B.4 √
 C.5
 D.6
在长度为9的有序顺序表中做折半查，在相等查概率下的查性能可以用下图(a)所示的判定树来分析，查成功的平均查长度和查不成功的平均查长度分别为25/9和34/10。
在长度为18的有序顺序表中做折半查，查第15个元素(如图(b)所示)的查次数为4。
当对一个线性表R[60]进行索引顺序查(分块查)时，若共分成了10个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序查，则查每一个表项的平均查长度为______。既希望较快的查又便于线性表动态变化的查方法是______。（分数：4.00）
 A.7
 B.8
 C.9 √
 D.10
 A.顺序查
 B.折半查
 C.散列查
 D.索引顺序查 √
设表项个数为n，分成b个子表，则需要b个索引项存放在索引表中，又每个子表中有s个表项，则有b=[n/s]。若对索引表和子表都采用顺序查，且n=60，b=10，s=6，则有：
既希望较快的查又便于线性表动态变化的查方法是索引顺序查方法。
13.散列函数有共同的性质，即函数值应当以______概率取其值域的每一个值。
 A.最大
 B.最小
 C.平均
 D.同等 √
设计散列函数时要求散列函数的定义域应能覆盖表项的关键字集合，而值域应在散列表的地址空间范围内。同时为了减少冲突，要求计算出的结构应以同等概率分布到值域的各个部分。
14.设散列地址空间为0～m-1，key为表项的关键字，散列函数采用除留余数法，即Hash(key)=key%p。为了减少发生冲突的频率，一般取p为______。
&
 B.小于等于m的最大质数 √
 C.大于m的最小质数
 D.小于等于m的最大合数
在除留余数法中，除数p一般取小于或等于m的最大质数(当m本身就是质数时，p取m的值)，其结果在0…m-1之内。
15.在开地址法中散列到同一个地址而引起的“堆积”问题是由于______引起的。
 A.同义词直接发生冲突
 B.非同义词直接发生冲突
 C.同义词之间或非同义词之间发生冲突 √
 D.散列表“溢出”
在开地址法中散列到同一个地址而引起的“堆积”问题是由于解决同义词冲突的探测序列和非同义词之间不同的探测序列交织在一起，导致关键字就位需要经过较长的探测距离，降低了散列的效率。所以必须选择好的解决冲突的方法以避免“堆积”。
16.在采用拉链法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的______相同。
 A.关键字值
 B.元素值
 C.散列地址 √
 D.含义
在拉链法中每一个散列地址所链接的同义词子表中各个表项的散列地址相同。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。