计算机学科专业基础综合（数据结构）题库_普通考研题库

单项选择题

对于有n个数据元素的顺序存储的表，一个递增有序，另一个无序，查找一个元素时采用顺序算法，对有序表从头开始查找，发现当前运算已小于待查找元素时停止查找，确定查找不成功。已知查找任何一个元素的概率相同，则在两种表中成功查找______。

A．平均时间后者小
B．无法确定
C．平均时间前者小
D．平均时间相同

单项选择题

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为，二分法查找只适用于查找顺序存储的有序表，平均比较次数为。在此假定N为线性表中结点数，且每次查找都是成功的。

A．N+1
B．2log2N
C．log2N
D．N/2
E．Nlog2N
F．.N2

单项选择题

当采用分块查找时，数据的组织方式为______。

A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块
C．数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块
D．数据分成若干块，每块(除最后一块外)中数据个数需相同

单项选择题

下面关于二分查找的叙述正确的是______。

A．表必须有序，表可以顺序方式存储，也可以链表方式存储
B．表必须有序且表中数据必须是整型、实型或字符型
C．表必须有序，而且只能从小到大排列
D．表必须有序，且表只能以顺序方式存储

单项选择题

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为，二分法查找只适用于查找顺序存储的有序表，平均比较次数为。在此假定N为线性表中结点数，且每次查找都是成功的。

A．N+1
B．2log2N
C．log2N
D．N/2
E．Nlog2N
F．.N2

单项选择题

二叉查找树的查找效率与二叉树的有天，在时查找效率最低。

A．结点太多
B．完全二叉树
C．呈单枝树
D．结点太复杂

单项选择题

下面关于B-树和B+树的叙述中，不正确的是______。

A．B-树和B+树都是平衡的多分树
B．B-树和B+树都可用于文件的索引结构
C．都能有效地支持随机检索
D．都能有效地支持顺序检索

单项选择题

关于B-树，下列说法不正确的是______。

A．B-树是一种查找树
B．所有的叶结点具有相同的高度
C．2-3树中，所有非叶子结点有1或者3个孩子结点
D．通常情况下，B-树不是二叉树

单项选择题

在采用线性探测法处理冲突，在所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（）。

A．一定都是同义词
B．一定都不是同义词
C．不一定都是同义词
D．都相同

单项选择题

关于散列表的平均查找长度，下列说法正确的是______。

A．与处理冲突的方法有关，但与表的长度无关
B．与处理冲突的方法有关，且与表的长度有关
C．与处理冲突的方法无关，但与表的长度有关
D．与处理冲突的方法无关，且与表的长度无关

单项选择题

关于散列表，下列说法不正确的是______。

A．散列函数以结点关键字为其输入，其输出为结点的存储地址
B．Hash冲突指同一个关键字对应多个不同的Hash地址
C．在散列存储中，装入因子的值越大，则存取结点时发生冲突的概率就越大
D．散列存储法只能存储数据元素的值，但会破坏数据元素之间的关系

单项选择题

若查找每个元素的概率相等，则在长度为n的顺序表上查找到表中任一元素的平均查找长度为______。

A．.n
B．n+1
C．(n-1)/2
D．(n+1)/2

单项选择题

对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一无素的查找成功的平均查找长度为______。

A．n/2
B．(n+1)/2
C．(n-1)/2
D．n/4

单项选择题

对应长度为n的有序顺序表，若采用折半查找，则对所有元素的平均查找长度为的值向上取整，或者为的值向下取整加一，查找任一元素的时间复杂度为__。

A．log2(n+1)
B．log2n
C．n/2
D．(n+1)/2

单项选择题

对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为，查找不成功的平均查找长度为。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为__。

A．20/9
B．18/9
C．25/9
D．34/9

单项选择题

对应长度为n的有序顺序表，若采用折半查找，则对所有元素的平均查找长度为的值向上取整，或者为的值向下取整加一，查找任一元素的时间复杂度为__。

A．log2(n+1)
B．log2n
C．n/2
D．(n+1)/2

单项选择题

对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为，查找不成功的平均查找长度为。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为__。

A．20/10
B．18/10
C．25/10
D．34/10

单项选择题

当对一个线性表R[60]进行索引顺序查找(分块查找)时，若共分成了10个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序查找，则查找每一个表项的平均查找长度为。既希望较快的查找又便于线性表动态变化的查找方法是。

A．7
B．8
C．9
D．10

单项选择题

对应长度为n的有序顺序表，若采用折半查找，则对所有元素的平均查找长度为的值向上取整，或者为的值向下取整加一，查找任一元素的时间复杂度为__。

A．O(n)
B．O(n2)
C．O(1)
D．O(log2n)

单项选择题

散列函数有共同的性质，即函数值应当以（）概率取其值域的每一个值。

A．最大
B．最小
C．平均
D．同等

单项选择题

对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为，查找不成功的平均查找长度为。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为__。

A．3
B．4
C．5
D．6

单项选择题

当对一个线性表R[60]进行索引顺序查找(分块查找)时，若共分成了10个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序查找，则查找每一个表项的平均查找长度为。既希望较快的查找又便于线性表动态变化的查找方法是。

A．顺序查找
B．折半查找
C．散列查找
D．索引顺序查找

单项选择题

设散列地址空间为0～m-1，key为表项的关键字，散列函数采用除留余数法，即Hash(key)=key%p。为了减少发生冲突的频率，一般取p为______。

A．.m
B．小于等于m的最大质数
C．大于m的最小质数
D．小于等于m的最大合数

单项选择题

在开地址法中散列到同一个地址而引起的“堆积”问题是由于______引起的。

A．同义词直接发生冲突
B．非同义词直接发生冲突
C．同义词之间或非同义词之间发生冲突
D．散列表“溢出”

单项选择题

在采用拉链法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的______相同。

A．关键字值
B．元素值
C．散列地址
D．含义

单项选择题

对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为______。

A．5
B．5
C．39/8
D．19/4

单项选择题

对长度为3的顺序表进行查找，若查找第一个元素的概率为1/2，查找第二个元素的概率为1/3，查找第三个元素的概率为1/6，则查找到表中任一元素的平均查找长度为______。

A．5/3
B．2
C．7/3
D．4/3

单项选择题

在一棵高度为h的B树中，叶结点处于第层，插入一个新关键字时，为查找插入位置需读取个结点。

A．h-1
B．.h
C．h+1
D．h+2

单项选择题

在10阶B树中根结点所包含的关键字个数最多为，最少为。

A．7
B．8
C．9
D．10

单项选择题

在10阶B树中根结点所包含的关键字个数最多为，最少为。

A．0
B．1
C．3
D．4

单项选择题

E知一棵10阶B+树中含有960个关键码，则该树的最小高度为______。

A．3
B．5
C．10
D．12

单项选择题

设有一个含200个表项的散列表，用线性探测法解决冲突，按关键字查询时找到一个表项的平均探测次数不超过1.5，则散列表项应能够至少容纳______个表项。
(设查找成功的平均查找长度为Snl={1+1/(1-α)}/2，其中α为装填因子)

A．400
B．526
C．624
D．676

单项选择题

在一棵高度为h的B树中，叶结点处于第层，插入一个新关键字时，为查找插入位置需读取个结点。

A．h-1
B．.h
C．h+1
D．h+2

对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为______，查找不成功的平均查找长度为______。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为______。

你可能感兴趣的试题

若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为______。

二叉查找树的查找效率与二叉树的______有天，在______时查找效率最低。

如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法______

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为______，二分法查找只适用于查找顺序存储的有序表，平均比较次数为______。在此假定N为线性表中结点数，且每次查找都是成功的。

当采用分块查找时，数据的组织方式为______。

下面关于二分查找的叙述正确的是______。

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为______，二分法查找只适用于查找顺序存储的有序表，平均比较次数为______。在此假定N为线性表中结点数，且每次查找都是成功的。

二叉查找树的查找效率与二叉树的______有天，在______时查找效率最低。

下面关于B-树和B+树的叙述中，不正确的是______。

关于B-树，下列说法不正确的是______。

在采用线性探测法处理冲突，在所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（）。

关于散列表的平均查找长度，下列说法正确的是______。

关于散列表，下列说法不正确的是______。

若查找每个元素的概率相等，则在长度为n的顺序表上查找到表中任一元素的平均查找长度为______。

对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一无素的查找成功的平均查找长度为______。

对应长度为n的有序顺序表，若采用折半查找，则对所有元素的平均查找长度为______的值向上取整，或者为______的值向下取整加一，查找任一元素的时间复杂度为______。

对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为______，查找不成功的平均查找长度为______。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为______。

对应长度为n的有序顺序表，若采用折半查找，则对所有元素的平均查找长度为______的值向上取整，或者为______的值向下取整加一，查找任一元素的时间复杂度为______。

对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为______，查找不成功的平均查找长度为______。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为______。

对应长度为n的有序顺序表，若采用折半查找，则对所有元素的平均查找长度为______的值向上取整，或者为______的值向下取整加一，查找任一元素的时间复杂度为______。

散列函数有共同的性质，即函数值应当以（）概率取其值域的每一个值。

对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为______，查找不成功的平均查找长度为______。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为______。

设散列地址空间为0～m-1，key为表项的关键字，散列函数采用除留余数法，即Hash(key)=key%p。为了减少发生冲突的频率，一般取p为______。

在开地址法中散列到同一个地址而引起的“堆积”问题是由于______引起的。

在采用拉链法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的______相同。

对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为______。

对长度为3的顺序表进行查找，若查找第一个元素的概率为1/2，查找第二个元素的概率为1/3，查找第三个元素的概率为1/6，则查找到表中任一元素的平均查找长度为______。

在一棵高度为h的B树中，叶结点处于第______层，插入一个新关键字时，为查找插入位置需读取______个结点。

在10阶B树中根结点所包含的关键字个数最多为______，最少为______。

在10阶B树中根结点所包含的关键字个数最多为______，最少为______。

E知一棵10阶B+树中含有960个关键码，则该树的最小高度为______。

设有一个含200个表项的散列表，用线性探测法解决冲突，按关键字查询时找到一个表项的平均探测次数不超过1.5，则散列表项应能够至少容纳______个表项。 (设查找成功的平均查找长度为Snl={1+1/(1-α)}/2，其中α为装填因子)

在一棵高度为h的B树中，叶结点处于第______层，插入一个新关键字时，为查找插入位置需读取______个结点。

对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为，查找不成功的平均查找长度为。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为__。

二叉查找树的查找效率与二叉树的有天，在时查找效率最低。

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为，二分法查找只适用于查找顺序存储的有序表，平均比较次数为。在此假定N为线性表中结点数，且每次查找都是成功的。

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为，二分法查找只适用于查找顺序存储的有序表，平均比较次数为。在此假定N为线性表中结点数，且每次查找都是成功的。

二叉查找树的查找效率与二叉树的有天，在时查找效率最低。

对应长度为n的有序顺序表，若采用折半查找，则对所有元素的平均查找长度为的值向上取整，或者为的值向下取整加一，查找任一元素的时间复杂度为__。

对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为，查找不成功的平均查找长度为。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为__。

对应长度为n的有序顺序表，若采用折半查找，则对所有元素的平均查找长度为的值向上取整，或者为的值向下取整加一，查找任一元素的时间复杂度为__。

对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为，查找不成功的平均查找长度为。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为__。

对应长度为n的有序顺序表，若采用折半查找，则对所有元素的平均查找长度为的值向上取整，或者为的值向下取整加一，查找任一元素的时间复杂度为__。

对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均查找长度为，查找不成功的平均查找长度为。对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为__。

在一棵高度为h的B树中，叶结点处于第层，插入一个新关键字时，为查找插入位置需读取个结点。

在10阶B树中根结点所包含的关键字个数最多为，最少为。

在10阶B树中根结点所包含的关键字个数最多为，最少为。

设有一个含200个表项的散列表，用线性探测法解决冲突，按关键字查询时找到一个表项的平均探测次数不超过1.5，则散列表项应能够至少容纳______个表项。
(设查找成功的平均查找长度为Snl={1+1/(1-α)}/2，其中α为装填因子)

在一棵高度为h的B树中，叶结点处于第层，插入一个新关键字时，为查找插入位置需读取个结点。