一、单选题
1．下列查方法中，不属于动态的查方法是( )。
A ．二叉排序树法
B ．平衡树法
C ．散列法
D ．二分查法国土资源部关于调整部分地区土地等别的通知
2．适用于静态的查方法为( )。
A ．二分查、二叉排序树查
B ．二分查、索引顺序表查
C ．二叉排序树查、索引顺序表查
D ．二叉排序树查、散列法查
3．静态查表与动态查表二者的根本差别在于( )。
A ．它们的逻辑结构不一样
B ．施加在其上的操作不同
C ．所包含的数据元素的类型不一样sia001
D ．存储实现不一样
4．对长度为10的顺序表进行查，若查前面5个元素的概率相同，均为1/8，查后面5个元素的概率相同，均为3/40，则查任一元素的平均查长度为( )。
A ．5.5
B ．5
C ．39/8
D ．19/4
5．( )存储方式适用于折半查。
A ．键值有序的单链表
B ．键值有序的顺序表
C ．键值有序的双链表
D ．键值无序的顺序表
6．对线性表进行二分查时，要求线性表必须( )。
A ．以顺序方式存储
B ．以链接方式存储
D ．链式存储，且结点按关键字有序排序
7．在索引顺序表中查一个元素，可用的且最快的方法是( )。
A ．用顺序查法确定元素所在块，再用顺序查法在相应块中查
B ．用顺序查法确定元素所在块，再用二分查法在相应块中查
C ．用二分查法确定元素所在块，再用顺序查法在相应块中查
D ．用二分查法确定元素所在块，再用二分查法在相应块中查
8．在索引查中，若主表长度为144，它被均分为12子表，每个子表的长度均为12，则索引查的平均查长度为( )。
A ．13
B ．24
C ．12
D ．79
9．由同一关键字集合构造的各棵二叉排序树( )。
A ．形态和平均查长度都不一定相同
B ．形态不一定相同，但平均查长度相同
C ．形态和平均查长度都相同
D ．形态相同，但平均查长度不一定相同
10．对二叉排序树进行( )，可以得到各结点键值的递增序列。
A ．先根遍历
B ．中根遍历
C ．层次遍历
D ．后根遍历
11．下述序列中，哪个可能是在二叉排序树上查35时所比较过的关键字序列？
A ．2，25，40，39，53，34，35
B ．25，39，2，40，53，34，35
C ．53，40，2，25，34，39，35
D ．39，25，40，53，34，2，35
12．在A VL 树中，每个结点的平衡因子的取值范围是( )。
A ．-1~1
B ．-2~2
C ．1~2
D ．0~1
13．在AVL 树中，任一结点的( )。
A ．左、右子树的高度均相同
B ．左、右子树高度差的绝对值不超过1
C ．左、右子树的结点数均相同
D ．左、右子树结点数差的绝对值不超过1
14．下面关于B 树和B +树的叙述中，不正确的是
A ．都是平衡的多叉树
B ．都是可用于文件的索引结构
C ．都能有效地支持顺序检索
D ．都能有效地支持随机检索
15．右图是一棵( )。
2822221915100528
2610
A．4阶B-树B．4阶B+树C．3阶B-树D．3阶B+树16．对包含n个关键字的散列表进行检索，平均检索长度是( )。 A．O(log2n) B．O(n) C．不直接依赖于n D．O(nlog2n) 17．在散列查中，平均查长度主要与( )有关。
A．散列表长度B．散列元素的个数C．装填因子D．处理冲突方法18．要解决散列引起的冲突问题，常采用的方法有( )。
A．数字分析法、平方取中法B．数字分析法、线性探测法
C．二次探测法、平方取中法D．二次探测法、链地址法
19．从理论上讲，将数据以( )结构存放，查一个数据的时间不依赖于数据的个数n。A．二叉查树B．链表C．散列表D．顺序表
20．假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行( )次探侧。
男生恋爱后患接吻病A．k-1 B．k C．k+1 D．k(k+1)/2
二、判断题
1．顺序查法不仅可用于顺序表上的查，也可用于链表上的查。
华南理工化工学院
2．二分查所对应的判定树，是一棵理想平衡的二叉排序树。
3．二叉排序树的形态与关键字的输入序列有关，但平衡二叉排序树是相同的。
4．如果根结点的左子树和右子树高度差不超过1，则该二叉树是平衡二叉树。
5．二叉排序树上，以根到任一结点的路径为界，则：路径左边结点＜路径结点＜路径右边结点。
6．在二叉排序树中，即使删除一个结点后马上再插入该结点，该二叉排序树的形态也可能不同。
7．用线性探测法解决突出时，同义词在散列表中是相邻的。
8．不论数据如何组织，分别在10000个结点和10个结点的查表中进行查，前者的平均查长度肯定比后者大。
9．在开散列表中不会出现堆积现象。
10．开散列表和闭散列表的装填因子都可大于、等于或小于1。
三、填空题
1．评价查效率的主要标准是____。安利如新
2．查表的逻辑结构是____。集合
3．对长度为100的顺序表，在等概率情况下，查成功时的平均查长度为____，在查不成功时的平均查长度为____。
4．在150个结点的有序表中二分法查，不论成功与否，键值比较次数最多为____。5．索引顺序表上的查分两个阶段：____、____。
6．从n个结点的二叉排序树中查一个元素，平均时间复杂性大致为____。
7．散列表中同义词是指____。
8．散列表既是一种____方式又是一种____方法。
9．散列表中要解决的两个主要问题是：____、____。
10．散列表的冲突处理方法有____和____两种，对应的散列表分别称为开散列表和闭散列表。
四、应用题、综合题
4．对关键字序列{11,78,10,34,47,2,59,21}构造散列表，取散列函数为H(K)＝K％11，用链地址法解决冲突，画出相应的散列表，并分别求查成功和不成功时的平均查长度。4．根据元素插入的先后次序不同，可构成多种形态的二叉排序树。请画出4棵含1，2，3，4四个元素且以1为根、深度为4的二叉排序树。
4．将一组键值{28,21,41,6,12,70}插入到散列表中，散列函数为H(key)=key％5，
1）计算各关键字的散列地址；
2）画出相应的开散列表；
3）计算等概率下查成功时的平均查长度。
4．对关键字序列（25, 16, 34, 39, 28, 56），
1）画出按此序列生成的二叉排序树。
2）计算等概率下查成功时的平均查长度。
4．已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，
1）画出对应的二分查判定树；
2）计算等概率时查成功的平均查长度。
4．将一组键值{28,21,41,6,12,70,69}插入到表长为9的散列表中，散列函数采用除余法，用线性探查法解决冲突，
1）计算各关键字的散列地址；
2）画出相应的闭散列表；
3）计算等概率下查成功时的平均查长度。
4．将一组键值{18,21,41,6,12,67}插入到散列表中，散列函数为H(key)=key％7，
1）计算各关键字的散列地址；
2）画出相应的开散列表；
3）计算等概率下查成功时的平均查长度。
1．已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的二分查判定树，求出其平均查长度。
平均查长度等于29/10
2．假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序生成的一棵二叉排序树，求出查成功和不成功的平均查长度(指关键字比较次数)。若查键值20，需要进行几次关键字比较？
成功时平均查长度32/10；比较3次：38、25、16
3．请画出从下面的二叉排序树中删除关键码40后的结果。
20
1140
62450
835
4560
3
28
4．对关键字序列{23,45,14,17,9,29,37,18}构造散列表，取散列地址为HT[0..6]，散列函数为H(K)＝K％7，用拉链法解决冲突，画出相应的散列表，并求在等概率下，查成功时的平均查长度。
5．已知散列函数为H(k)＝k％11，关键值序列为25、21、41、6、12、69、20、15、22。6．用线性探测法处理冲突，散列表长度为12。试画出该散列表，并分别计算查成功和不成功时关键字的平均比较次数。
7．在包含n个关键字的线性表里进行顺序查，若查第i个关键字的概率为p i，p i如下分布：p1=1/2,p2=1/4,......,p n-1=1/2n-1,p n=1/2n。求成功检索的平均比较次数。
8．若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?
(1).搜索失败;
(2).搜索成功, 且表中只有一个关键码等于给定值k的对象;
(3).搜索成功, 且表中有若干个关键码等于给定值k的对象, 要求一次搜索
出所有对象。
解：(1) 不同。因为有序顺序表搜索到其关键码比要查值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜
索失败。
(2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。
(3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就
可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表
中对象才能确定相同关键码的对象都了出来，所需时间就不相同了。
五、程序分析与填空
1．编写算法，返回二叉排序树中的关键字最大（或最小）的结点地址。
提示：关键字最大的结点是“最右下”的结点；关键字最小的结点是“最左下”的结点。
pointer search(bitree t)
{
pointer p;
if(t==NULL)
return NULL; //空树
p=t;
while(p->rchild!==NULL) p=p->rchild; //向右下搜索
return p;
}
2．编写算法，在二叉排序树中查键值为K的结点。
pointer search(bitree t,keytype K) //递归算法
{
if(t==NULL) return NULL; //空树
if(t->data==K) return t; //到
else if(t->data>K)
return search(t->lchild,K); //左子树
else
return search(t->rchild,K); //右子树
}
=》候选
2．对有n个记录的有序表采用二分查，其平均查长度的量级为( )。
A O(n)
B O(n2)
C O(1)
D O(log2n) 2．对长度为n的有序表二分查，则对所有元素的最长查长度为( )。
软硬件环境
A.⎡log2(n+1)⎤
B. ⎡log2n⎤
C. ⎡n/2⎤
D. ⎡(n+1)/2⎤
2．对长度为n的有序表二分查，则对所有元素的最长查长度为( )。
A. ⎣log2(n+1)⎦+1
B. ⎣log2n⎦+1
C. ⎣n/2⎦+1
D. ⎣(n+1)/2⎦+1 2．对长度为100的有序表二分查，若查不成功，至少比较( )次。
A、9
B、8
C、7
D、6 6．二分查法要求查表中各元素的键值必须是( )排列。
33．散列存储中，冲突是指( )。
A．两个元素具有相同的序号B．两个记录的关键字相同
C．数据元素过多D．不同关健字值对应相同的存储地址
20．查表内元素的关键字一定是整型量。
20．静态查表的检索与修改被分成两个不交叉的阶段分别进行。
20．在n个结点的有序表中进行二分查，关键字比较次数最多为(n+1)/2。
10．二叉排序树的中序遍历序列是递增的，所以前序或后序遍历序列不可能也是递增的。20．若两棵二叉排序树的中序序列相同，则它们的形态也相同。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议