文档库 最新最全的文档下载
当前位置:文档库 › 第八章程序查找

第八章程序查找

8.4 应用题

1.顺序查找时间为O(n),二分法查找时间为O(log2n),散列法为O(1),为什么有高效率的查找方法而低效率的方法不被放弃?
【答案】不同的查找方法适用的范围不同,高效率的查找方法并不是在所有情况下都比其他查找方法效率要高,而且也不是在所有情况下都可以采用。

2.对含有n个互不相同元素的集合,同时找最大元和最小元至少需进行多少次比较?
【答案】n-1次
【解析】设变量max和min用于存放最大元和最小元(的位置),第一次取两个元素进行比较,大的放入max,小的放入min。从第2次开始,每次取一个元素先和max比较,如果大于max则以它替换max,并结束本次比较;若小于max则再与min相比较,在最好的情况下,比较下去都不用和min相比较,所以这种情况下,至少要进行n-1次比较就能找到最大元和最小元。

3.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找,试在下述两种情况下分别讨论两者在等概率时的平均查找长度:
(1)查找不成功,即表中无关键字等于给定值K的记录;
(2)查找成功,即表中有关键字等于给定值K的记录。
【答案】
(1)不成功时需要n+1 次比较
(2)成功时平均为(n+1)/2次
【解析】有序表和无序表顺序查找时,都需要进行n+1次比较才能确定查找失败。因此平均查找长度都为n+1。查找成功时,平均查找长度都为(n+1)/2,有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。


5.为什么有序的单链表不能进行折半查找?
【答案】因为链表无法进行随机访问,如果要访问链表的中间结点,就必须先从头结点开始进行依次访问,这就要浪费很多时间,还不如进行顺序查找,而且,用链存储结构将无法判定二分的过程是否结束,因此无法用链表实现二分查找。

6.构造有12个元素的二分查找的判定树,并求解下列问题:
(1)各元素的查找长度最大是多少?
(2)查找长度为1、2、3、4的元素各有多少?具体是哪些元素?
(3)查找第5个元素依次要比较哪些元素?
答案

(1)最大查找长度是树的深度4。
(2)查找长度为1的元素有1个,为第6个,查找长度为2的元素有2个,为第3个和第9个,查找长度为3的元素有4个,为第1、4、7、11个,查找长度为4的元素有5个,为第2、5、8、10、12个。
(3)查找第五个元素依次比较6,3,4,5。


8.直接在二叉排序树中查找关键码K与从中序遍历输出的有序序列中用二分查找法查找关键码K,其数据比较次数是否相同?
【答案】不相同。
【解析】因为二分查找得到的判定树和二叉排序树的形状不一定相同。

9.已知

一棵二叉排序树如下:


(1)假如删除关键字28,画出新二叉树。
(2)若查找56,需和哪些关键字比较。
【答案】
(1)删除元素28后,需修改二叉排序树的形态,可用结点28左子树上最大的结点代替它如图(1),也可用其右子树上最小的结点代替它,
2)若要查找56,需和38、49、55、56进行4次比较。

10.设散列函数为h(key)=key%101,解决冲突的方法为线性探测,表中用"-1"表示空单元。

(1)若删去散列表HT中的304(即令HT[1]=-1)之后,在表HT中查找707将会发生什么?
(2)若将删去的表项标记为"-2",查找时探测到"-2"继续向前搜索,探测到"-1"时终止搜索。请问用这种方法删去304后能否正确地查找到707?
【答案】
(1)查找707时,首先根据散列函数计算得出该元素应在散列表中的0单元,但是在0单元没有找到,因此将向下一单元探测,结果发现该单元是-1(为空单元),所以结束查找,这将导致707无法找到。
(2)如果改用"-2"作为删除标记,则可以正确找到707所在的结点。

11.已知散列表的地址区间为0~11,散列函数为H(k)=k % 11,采用线性探测法处理冲突,将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中,试构造出该散列表,并求出在等概率情况下的平均查找长度。
【答案】构造散列表如下(每个元素的查找长度标注在该元素的下方)。

等概率情况下成功时的平均查找长度为(1×5+2+3+4+5)/9=19/9

12.设散列函数为H(k)=k % 11,采用拉链法处理冲突,将上例中关键字序列依次存储到散列表中,并求出在等概率情况下的平均查找长度。
【答案】

在等概率情况下成功的平均查找长度为:
(1*5+2*2+3*1+4*1)/9=16/9

13.假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70),散列地址空间为HT[13],若采用除留余数法构造散列函数和线性探测法处理冲突,试求出每一元素的初始散列地址和最终散列地址,画出最后得到的散列表,求出平均查找长度。
答案

在等概率情况下成功的平均查找长度为(1*7+2*5+3*1+4*1)/14=24/14

14.散列表的地址区间为0~15,散列函数为H(key)=key%13。设有一组关键字{19,01,23,14,55,20,84}, 采用线性探测法解决冲突,依次存放在散列表中。问:
(1)元素84存放在散列表中的地址是多少?
(2)搜索元素84需要的比较次数是多少?
【答案】构造的散列表如下:

(1)元素84存放在散列表中的地址是8。
(2)搜索元素84需要的比较3次。

8.5 算法设计题

1.已知顺序表A长度为n,试写出将监视哨设在高端的顺序查找算法。
【算法分析】
将监视哨放在高端,即元素从下标为0的位置开始存放,将

A[n]设置为待查键值,作为监视哨。查找成功时返回元素下标,否则返回n。
【算法源代码】
#include "type.h"
int seach_seq(SSTable A,ElemType key)
{int i,n;
n=A.length;
A.elem[n].key=key;
for(i=0;A.elem[i].key!=key;++i)
return i;
}

2.若线性表中各结点的查找概率不等,则可用如下策略提高顺序查找的效率∶若找到指定的结点,则将该结点和其前驱结点交换,使得经常被查找的结点尽量位于表的前端。试对线性表的链式存储结构写出实现上述策略的顺序查找算法(查找时必须从表头开始向后扫描)。
【算法分析】
设指针变量p指向当前结点,q指向其前驱结点。过程如下图所示。若要将当前结点和第一个结点交换,通过指针的变化需要经过4步(如图所示):①第一个结点的next域指向q的后继结点。②将头指针指向当前结点。③当前结点的next域等于第一个结点的next域。④其前驱结点的next指向原来的第一个结点。
【算法源代码】
#include "type.h"
LNode *search_Slist(LNode *L,int key)
{ LNode *q,*p; int t;
p=L;
q=NULL;
while(p->next!=NULL)
if(p->data!=key) /*当前结点不是要查找结点,继续向后查找*/
{q=p; p=p->next;}
else /*当前结点是要查找结点*/
if(q!=NULL) /*当前结点有前驱*/
{ t=q->data;q->data=p->data; p->data=t;return p;}
}


4.有递增排序的顺序线性表A[n],写出利用二分查找算法查找元素K的递归算法。若找到则给出其位置序号,若找不到则其位置号为0。
【算法源代码】
#include "type.h"
int Binsch(SSElement A[],int low,int high,ElemType K)
{int mid;
if(low<=high )
{ int mid=(low+high)/2;
if(K==A[mid].key)
return mid; /* 查找成功,返回元素的下标*/
else if(Kreturn Binsch(A,low,mid-1,K);/*在左子表上继续查找*/
else
return Binsch(A,mid+1,high,K);/*在右子表上继续查找*/
}
else return 0; /* 查找失败,返回0*/
}

5.设计一个算法,求出指定结点在给定的二叉排序树中所在的层数。
【算法分析】查找成功时的比较次数即为结点所在层数。可设置查找时计数,比较一次计数器加1。如查找成功时返回计数器累加数字,不成功时,返回0。
【算法源代码】
#include "stdio.h"
#include "type.h"
int search_depth(BiTree T,ElemType key)
/*求当前结点所在层数 */
{
BiTNode *p;
int dep=0;
p=T;
while(p)
{ if(key==T->data)
{dep++;break;}
else
if(key>T->data) {dep++; p=p->rchild;}
else { dep++; p=p->lchild;}
}
if(p) return dep;
else return 0;
}

6.设计一个算法,以求出给定二叉排序树中值为最大的结点。
【算法分析】二叉排序树上最大的结点肯定在右子树上。因此,首

先从根结点开始查找,然后顺着右子树查找,直到结点没有右子树为止。
【算法源代码】
#include "stdio.h"
#include "type.h"
ElemType search_max(BiTree T) /*求二叉排序树最大值*/
{ BiTNode *p;
ElemType max;
p=T;
if (T==NULL)
{p=NULL; printf("树为空\n"); return 0;}
while(p)
{max=p->data; p=p->rchild;} /*访问右孩子,直到空为止*/
return max;
}

7.设计一个递归算法,向以BT为树根的二叉排序树上插入值为x的结点。
【算法源代码】
#include "type.h"
#include "stdio.h"
BiTree insort(BiTree bt, ElemType x)/*函数返回二叉排序树头指针*/
{ BiTree p,q;
p=( BiTree)malloc(sizeof(BiTNode)); /*生成新结点*/
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
q=bt;
if(q==NULL) bt=p; /*二叉排序树为空*/
else /*二叉排序树不空*/
{while((q->lchild!=p)&&( q->rchild!=p))
{ if(xdata) /*插入到左子树*/
{ if(q->lchild!=NULL) q=q->lchild; else q->lchild=p; }
else /*插入到右子树*/
{if(q->rchild!=NULL) q=q->rchild; else q->rchild=p;}
}
}
return(bt); /*返回二叉排序树的头指针*/
}

8.假设二叉排序树采用链表结构存储,设计一个算法,从大到小输出该二叉排序树中所有关键字不小于X的数据元素。
【算法分析】
若对二叉排序树中序遍历,则遍历结果的序列是递增有序的,若遍历先左后右,则输出递增序列。若要输出递减序列,采取先遍历右子树,遍历根结点,再遍历左子树的策略,直到小于X为止。
【算法源代码】
#include "type.h"
void inorder(BiTree bst,ElemType x)
{if(bst)
{ inorder(bst->rchild, x); /*遍历右子树*/
if(bst->data>=x) printf("%c",bst->data); /*访问结点*/
else return; /*找到小于x的结点停止*/
inorder(bst->lchild,x); /*遍历左子树*/
}
}


10.试编写利用二分查找法确定记录的所在块的分块查找算法。
【算法分析】
采用分块查找时,除了顺序表之外,还要有索引表。其中索引表中含有各块索引。在各块中进行顺序查找时,监视哨可设在本块的表尾,即将下一块的第一个记录暂时移走(若本块内记录没有填满,则监视哨的位置仍在本块的尾部),待块内顺序查找完成后再移回来。此时增加了赋值运算,但免去了判断下标变量是否越界的比较。注意,最后一块需进行特殊处理。在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失。
【算法源代码】
#include "type.h"
int Search_Idx(IdxSqlist L,int key)
{ /*分块查找,二分查找确定块,块内顺序查找*/
int i,j,k,low,high,mid,found,temp;
if(key>L.idx[L.blknum].maxkey) return -1; /*超过最大元素,返回-1*/
low=1;high=L.blknum;

found=0;
while(low<=high&&!found)
{
mid=(low+high)/2;
if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)
found=1;
else if(key>L.idx[mid].maxkey) low=mid+1;
else high=mid-1;
}
i=L.idx[mid].firstloc; /*块的下界*/
j=i+blksize-1;
temp=L.elem[i-1]; /*保存相邻元素*/
L.elem[i-1]=key; /*设置监视哨*/
for(k=j;L.elem[k]!=key;k--); /*顺序查找*/
L.elem[i-1]=temp; /*恢复元素*/
if(kreturn k;
}

相关文档
相关文档 最新文档