数据结构习题精编查找.docx
《数据结构习题精编查找.docx》由会员分享，可在线阅读，更多相关《数据结构习题精编查找.docx（27页珍藏版）》请在冰点文库上搜索。
数据结构习题精编查找
数据结构习题精编：
查找
一、选择题
1．对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查
找长度为
A．（n-1）/2B．n/2C．（n+1）/2D．n
2．若有序表的关键字序列为（b，c，d，e，f，g，q，r，s，t），则在折半查找关键字
b的过程中，先后进行比较的关键字依次为
A．f、c、bB．f、d、bC．g、c、bD．g、d、b
3．在关键字序列（12，23，34，45，56，67，78，89，91）中折半查找关键字为45、
89和12的元素时，所需进行的比较次数分别为
A．3，3，4B．3，4，4C．4，3，3D．4，4，3
4．已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查
找一个不存在的元素，则比较次数最多的是
A．4B．5C．6D．7
5．对具有12个关键字的有序表进行折半查找，在查找概率相等的情况下，查找成功的
平均查找长度为
A．2.5B．3.1C．4D．5
6．某索引顺序表共有元素395个，平均分成5块。
若先对索引表采用顺序查找，再对
块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是
A．43B．79C．86D．198
7．下列关于静态查找表的说法中，正确的是
A．用数组和单链表表示的有序表均可使用折半查找方法来提高查找速度。
B．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。
C．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅
与表中元素个数有关，而且与每块中元素个数有关。
D．有n个数存放在一维数组A[1..n]中，采用顺序查找，在等概率查找的情况下，
这n个数的排列有序或无序时，其平均查找长度相同。
8．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过
A．n/2B．（n+1）/2C．nD．n+1
9．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的
结点，且新结点的关键字小于根结点的关键字，则新结点将成为
A．左子树的叶子结点B．左子树的分支结点
C．右子树的叶子结点D．右子树的分支结点
10．已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生
成一棵二叉排序树，则该树的深度为
A．4B．5C．6D．7
11．由同一关键字集合构造的各棵二叉排序树
A．其形态均相同，平均查找长度也都相同
B．其形态均相同，但平均查找长度不一定相同
C．其形态不一定相同，但平均查找长度相同
D．其形态不一定相同，平均查找长度也不一定相同
12．已知二叉排序树T，要输出其结点的有序序列，则采用的遍历方法是
A．先序遍历B．中序遍历C．后序遍历D．层次遍历
13．已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况
下查找成功的平均查找长度等于
A．1.0B．2.9C．3.4D．5.5
14．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是
A．（100，60，80，90，120，110，130）
B．（100，80，60，90，120，130，110）
C．（100，80，90，60，120，110，130）
D．（100，120，110，130，80，60，90）
15．对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是
A．12、25、71、68、33、34B．21、89、77、29、36、38
C．92、20、91、34、88、35D．95、22、91、24、94、71
16．下列关于二叉排序树的说法中，正确的是
A．二叉排序树删除一个叶子结点后，仍是二叉排序树。
B．在二叉排序树中插入一个新结点，总是插入到叶结点的下面。
C．在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树
与原二排序叉树相同。
D．某二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点的值；
其右子树根结点的值大于该结点的值，则此二叉树一定是二叉排序树。
17．在一棵平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并
已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，为使其平衡应做
A．LL型调整B．LR型调整C．RL型调整D．RR型调整
18．在下图1所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新
平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是
图1平衡二叉树
A．13，48B．24，48C．24，53D．24，90
19．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的
结点总数为
A．10B．20C．32D．33
20．下列叙述中，不符合m阶B树定义要求的是
A．根结点最多有m棵子树B．所有叶结点都在同一层上
C．叶结点之间通过指针链接D．各结点内关键字均升序或降序排列
21．既希望较快的查找又便于线性表动态变化的查找方法是
A．顺序查找B．折半查找C．索引顺序查找D．哈希法查找
22．下列关于哈希查找的说法中，正确的是
A．哈希函数的选取以除留余数法最好。
B．Hash表的平均查找长度与处理冲突的方法无关。
C．若哈希表的装填因子α<1，则可避免冲突的产生。
D．在哈希查找中，“比较”操作一般也是不可避免的。
23．对于哈希函数H（key）=key%13，被称为同义词的关键字是
A．15和44B．23和39C．25和51D．35和41
24．设有一组关键字（19，14，23，1，6，20，4，27，5，11，10，9），用哈希函数
H（key）=key%13构造哈希表，用拉链法解决冲突，哈希地址为1的链中记录个数为
A．1B．2C．3D．4
25．假定有k个关键字互为同义词，若用线性探测法将这k个关键字对应的记录存入
哈希表中，至少要进行的探测次数为
A．k-1B．kC．k+1D．k*（k+1）/2
二、填空题
1．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最少为________次，最多为________次；当使用监视哨时，若查找失败，则比较关键字的次数为_________。
2．己知有序表为（8，11，12，18，24，35，42，47，50，62，83，90，115，134），当用折半查找法查找90时，需__________次查找成功，所比较的元素依次为__________。
查60时，需__________次才能确定不成功，所比较的元素依次为__________。
3．在有序表A[1..20]中，按折半查找方法进行查找，查找长度为5的元素个数是__________。
4．有一个包含2000个元素的表，欲采用索引顺序查找方法进行分块查找，则每块的理想长度是__________，分成__________块最为理想，平均查找长度是_________。
5．用分块查找法对一个有2000个元素的表进行查找，若每块长度为25，用顺序查找确定块时，平均查找长度为__________；用折半查找确定块时，平均查找长度为__________。
6．如果按关键字值递增的顺序依次将关键字插入到二叉排序树中，则对这样的二叉排序树查找时，平均比较次数为__________。
7．如果关键字按值有序排列，而后用折半查找法依次查找这些关键字，并把查找中遇到的在二叉树中没有出现的关键字依次插入到二叉排序树中，则对这样的二叉排序树查找时，平均比较次数为__________。
8．已知一棵二叉排序树（结点值大小按字母顺序）的先序遍历序列为EBACDFHG，则此二叉排序树的后序遍历序列为____________________。
9．深度为8的平衡二叉树的结点数至少有__________个。
设以Nm表示深度为m的平衡二叉树中含有的最少结点数，则有N0=0，N1=1，N2=________，N3=_______，N4=________，…，Nm=Nm-1+_____________（m≥2）。
10．深度为4的3阶B-树中，至少有________个关键字，最多有________个关键字。
11．含9个叶子结点的3阶B-树中至少有________个非终端结点，此时，树的深度为________，树中每个非终端结点均含________棵子树；含10个叶子结点的3阶B-树中至多有______个非终端结点，此时树的深度为________，除叶子结点所在层外，其它各层非终端结点数依次为________________。
12．在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是__________；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是__________。
13．127阶B-树中每个结点最多有__________个关键字；除根结点外所有非终端结点至少有__________棵子树。
14．动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。
15．某哈希表的地址区间为0~17，哈希函数为H（K）=Kmod17。
采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到哈希表中。
元素59存放在哈希表中的地址是___________，存放元素59需要探测的次数是_________。
三、解答题
1．用折半查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。
元素下标
1
2
3
4
5
6
7
8
9
10
比较次数
2．图2中二叉排序树的各结点的值为1～9，标出各结点的值。
图2二叉排序树
3．从空树起，依次插入关键字（37，50，42，18，48，12，56，30，23），构造一棵二叉排序树。
（1）画出该二叉排序树。
（2）对该二叉排序树作中序遍历，写出遍历序列。
（3）求在等概率情况下，查找成功的平均查找长度。
（4）画出从
（1）所得树中删除关键字为37的结点之后的二叉排序树。
4．由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。
请画出4棵含1、2、3、4、5、6六个元素且以元素1为根、深度为4的二叉排序树。
5．给定关键字序列（15，11，8，20，14，13，24，22，23），试画出从一棵初始时为空的二叉排序树开始，依次插入该序列中的关键字所构成的平衡二叉树，并为每一次的平衡处理指明旋转类型。
6．深度为h的m阶B树至少有多少个结点？
7．设有一棵空的３阶B-树，依次插入关键字30、20、10、40、80、58、47、50、29、22、56、98、99，请画出该B-树。
8．对如图3所示的3阶B-树，依次执行下列操作，画出各步操作的结果。
（1）插入90，
（2）插入25，（3）插入45，（4）删除60，（5）删除80。
图33阶B-树
9．将关键字序列（7、8、30、11、18、9、14）散列存储到哈希表中，哈希表的存储空间是一个下标从0开始的一个一维数组，哈希函数为：
H（key）=（key*3）MODT（T为表长），处理冲突采用线性探测再散列法，要求装填因子为0.7。
（1）请画出所构造的哈希表。
（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。
10．设一组关键字序列为{1，10，11，14，20，23，27，29，55，68}，采用的哈希函数是H（key）=keyMOD13，冲突用链地址法解决。
（1）试画出插入上述关键字序列后的哈希表。
（2）求出在等概率情况下查找成功时的平均查找长度。
四、分析题
1．阅读下列函数，并回答问题。
voidFun741_1（intH[]）
{
intk,m,p;
cout<<"请输入一个正整数序列，输入0表示结束：
"<cin>>k;
while（k!
=0）
{
m=13;
p=k%m;
while（H[p]!
=0&&k!
=H[p]）
{
p=（p+1）%m;
if（p==k%m）
break;
}
if（H[p]==0）
H[p]=k;
cin>>k;
}
}
voidFun741_2（intH[],intm）
{
intcnt1=0,cnt2=0,i;
for（i=0;i{
if（H[i]!
=0）
{
cnt2++;
cnt1=cnt1+（i-H[i]%m+m）%m+1;
}
}
cout<}
（1）设有定义inta[15]={0};，执行函数调用Fun741_1（a）;，依次输入整数序列为19、14、23、1、68、20、84、27、55、11、10、79、0，函数调用结束后，数组a中各元素的值是什么？
请根据执行结果填写下面的表格。
i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
a[i]
（2）在执行完上面的函数调用Fun741_1（a）后，接着执行函数调用Fun741_2（a,13）;，输出的结果是什么？
（3）简述函数Fun741_1（）和函数Fun741_2（）的功能。
2．下列函数的功能是求出指定关键字在给定的二叉排序树中所在的层次。
请在空缺处填入合适的内容，将程序补充完整。
intlevelKey（BiTreebst,KeyTypek）
//求关键字k所在结点在二叉排序树中的层次，若k不存在，返回0
{
intlevel=0;
BiTNode*p=bst;
while（p!
=NULL）
{
__________;//
（1）
if（p->key__________;//
（2）
elseif（p->key>k）
__________;//（3）
else
break;
}
if（p!
=NULL）
return__________;//（4）
else
return__________;//（5）
}
3．已知不带头结点的单链表中的关键字为正整数，为提高查找效率，将它改建为采用拉链法处理冲突的哈希表。
设哈希表的长度为m，哈希函数为Hash（key）=key%m。
链表的类型定义如下：
typedefintKeyType;
structLNode
{
KeyTypekey;
LNode*next;
};
typedefLNode*LinkList;
请在下面函数中的空缺处填入适当的内容，将程序补充完整。
voidReCreate（LinkList&L,LinkListH[],intm）
//由不带头结点的单链表L生成哈希表H，哈希表生成之后原链表不再存在
{
inti;
LinkListp,q,f,r;
for（i=0;iH[i]=___________;//
（1）
___________;//
（2）
while（p）
{
q=p->next;
i=p->key%m;
f=NULL;r=H[i];
while（r!
=NULL&&r->keykey）
{
f=r;r=r->next;//查找插入位置
}
if（r!
=NULL&&r->key==p->key）
{
deletep;//当前p所指结点在Hash表中已存在，直接释放其存储空间
}
else
{
if（f!
=NULL）
{
p->next=__________;//（3）
_________________;//（4）
}
else
{
p->next=__________;//（5）
__________;//（6）
}
}
__________;//（7）
}
L=__________;//（8）
}
4．阅读下列函数，并回答问题。
voidCreateHashList（LinkListH[],intm,inta[],intn）
//用链地址法解决冲突，将数组a中的n个整数作为关键字构造哈希表，
//哈希函数用H（key）=key%m
{
inti,j;
LinkListp;
for（i=0;iH[i]=NULL;//初始化
for（i=0;i{
j=a[i]%m;
p=newLNode;
p->key=a[i];
p->next=H[j];
H[j]=p;
}
}
（1）设有数据定义：
LinkListH[7];
inta[12]={19,14,23,1,68,20,84,27,55,11,10,79};
试给出执行函数调用CreateHashList（H,7,a,12）;后，数组H的情况。
（2）对上问所构造的哈希表进行查找，查找成功时的平均查找长度是多少？
（3）上面给出的函数不是很严谨，没有考虑数组a中的n个元素可能重复，而哈希表中不应该存在重复的元素。
你觉得应怎样解决这个问题？
请给出修改后的程序。
5．设二叉排序树采用二叉链表存储。
下面的函数DeleteAllX（bst,x）的功能是在二叉排序树bst中，删除所有关键字值小于等于x的结点。
其基本思想是：
利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。
若根结点的值大于x，则沿着左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。
请在空缺处填入合适的内容，将程序补充完整。
voidDelTree（BiTree&root）//非递归删除以root为根的二叉排序树
{
BiTreep,S[100];//S是栈，假定容量足够大，栈中元素是二叉排序树结点的指针
inttop=0;
while（root!
=NULL||top>0）
{
while（root!
=NULL）//沿左分枝向下
{
S[___________]=root;//
（1）
__________________;//
（2）
}
if（top>0）//退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间
{
p=___________;//（3）
root=___________;//（4）
deletep;
}
}
}
voidDeleteAllX（BiTree&bst,KeyTypex）
//在二叉排序树bst中，删除所有关键字值小于等于x的结点
{
BiTreep,q;
while（bst&&bst->key<=x）//根结点的值小于等于x
{
p=bst;
bst=___________;//（5）
____________________;//（6）
DelTree（p）;
}
if（bst）
{
q=bst;p=bst->lchild;//q记p的双亲
while（p）
{
while（p&&p->key>x）//沿根结点左分枝向下，查小于等于x的结点
{
q=p;___________;//（7）
}
if（p）//p结点的值小于等于x
{
q->lchild=___________;//（8）
____________________;//（9）
DelTree（p）;
}
______________________;//（10）
}
}
}
五、设计题
1．设数组A中存储有300个元素，下面的程序段可以求出这300个元素中的最大值和最小值。
max=min=a[0];
for（i=1;i<300;i++）
{
if（maxif（min>a[i]）min=a[i];
}
这段程序中，比较次数为598（2n-1）次。
能否用448（3n/2-2）次的比较次数找出这300个元素中的最大值和最小值呢？
若能，请说明所采取的方法并写出程序代码段。
若不能，给出你的理由。
2．编写一个函数，判别一棵采用二叉链表存储的二叉树是否为二叉排序树。
3．设二叉排序树采用二叉链表存储，类型定义为：
typedefintKeyType;
structBiTNode
{
KeyTypekey;
BiTNode*lchild;
BiTNode*rchild;
};
typedefBiTNode*BiTree;
编写一个函数，删除结点关键字值是key的结点。
要求删除该结点后，此树仍然是一棵二叉排序树。
4．设平衡二叉树的结点定义为
structBiTNode
{
KeyTypekey;
intbf;//结点的平衡因子
BiTNode*lchild;
BiTNode*rchild;
};
其中，bf域标明了每个结点的平衡因子。
编写一个函数，采用非递归的方法求平衡二叉树的深度。
5．编写从哈希表中删除关键字为K的一个记录的算法，设哈希函数为：
H（key）=keyMODT（T为表长），处理冲突采用线性探测再散列法。
哈希表定义及建立的哈希表同本章的实例7-8。
删除时，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。
参考答案
一、选择题
1．C
2．A
3．C
4．B
5．B
6．A
7．C
8．C
9．A
10．B
11．D
12．B
13．B
14．A
15．D
16．A
17．C
18．C
19．B
20．C
21．C
22．D
23．C
24．C
25．D
二、填空题
1．1nn+1
2．442、83、115、90442、83、50、62
3．54．454546（块内顺序查找）
5．53.5196．（n+1）/27．
8．ADCBGHFE
9．54247Nm-2+110．7
升级会员 