《数据结构》第九章 查找

9.1 若对大小均为n的有序的顺布标和无序的顺序表分别进行顺序查找,试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同?
(1)查找不成功,即表中没有关键字等于给定值K的记录;
(2)查找成功,且表中只有一个关键字等于给定值K的记录;
(3)查找成功,且表中有若干个关键字等于给定值K的记录,一次查找要求找出所有记录。此时平均查找长度应考虑找到所有记录所用的比较次数。

9.2 试分别画出在线性表(a,b,c,d,e,f,g)中进行折半查找,以查关键等于e,f和g的过程。

9.3 画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查找长度。

ASL=\frac{1}{10}\left ( 1X1+2X2+3X4+4X3 \right )=2.9

9.4 假设按下述递归方法进行顺序表的查找:若表长<=10,则进行顺序查找,否则进行折半查找。试画出对表长n=50的顺序表进行上述查找时,描述该查找的判定树,并求出在等概率情况下查找陈宫的平均查找长度。

 

 
 

9.7 已知一个有序表的表长为8N,并且表中没有关键字相同的记录。假设按如下所述方法查找一个关键字等于给定值K的记录:先在第8,16,24,…,,8K,…,8N个记录中进行顺序查找,或者查找成功,或者由此确定出一个继续进行折半查找的范围。画出描述上述查找过程的判定树,并求等概率查找时查找成功的平均查找长度。

平均查找长度\frac{N+1}{2}+\frac{17}{8}

 

9.9 已知如下所示长度为12的表
(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。
(2)若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
(3)按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。

 

9.11 试推导含12个结点的平衡二叉树的最大深度,并换出一棵这样的树。

9.12 在B-树定义中,特性3的意图是什么?试思考:若把\left \lceil m/2 \right \rceil改为\left \lceil 2m/3 \right \rceil\left \lceil m/3 \right \rceil是否可行?所得到的树结构和B-树有何区别?

9.13 含9个叶子结点的3阶B-树中至少有多少个非叶子结点?含10个叶子结点的3阶B-树中至多有多少个非叶子结点?

9.14 试从空树开始,画出按以下次序向2-3树即3阶B-树中插入关键码的建树过程:20,30,50,52,60,68,70。如果此后删除50和68,画出每一步执行后2-3树的形态。

9.15 试证明:高度为h的2-3树中叶子结点的数目在2^{h-1}3^{h-1}之间。

9.16 在含有n个关键码的m阶B-树中进行查找时,最多访问多少个结点?

9.17 B+树和B-树的主要差异是什么?

9.18 试画一个对应于关键字集{program,programmer,programming,processor,or}的Trie树,对每个关键字从右向左取样,每次一个字母。

9.19 选取哈希函数H(k)=(3k)MOD11.用开放定址法处理冲突,di=i((7k)MOD 10+1)(i=1,2,3,…)。试在0~10的散列地址空间中对关键字序列(22,41,53,46,30,01,67)造哈希表,并求等概率情况下查找成功的平均查找长度。

9.20 试为下列关键字建立一个装载因子不小于0.75的哈希表,并计算你所构造的哈希表的平均查找长度。
(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG,CHANG,CHAO,YANG,JIN)

9.21 在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表:
(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
(1)用线性探测开放定址法处理冲突;
(2)用连地址法处理。
并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。
设哈希函数H(x)=\left \lfloor i/2 \right \rfloor,其中i为关键字中第一个字母在字母表中的序号。

9.22 已知一个含有1000个记录的表,关键字为中国人姓氏的拼音,请给出此表的一个哈希表设计方案,要求它在等概率情况下查找成功的平均查找长度不超过3.

9.23 设有一个关键字取值范围为正整数的哈希表,空表项的值为-1,用开放定址法解决冲突。现有两种查处策略:一是将待删除表项的关键字置为-1,;二是将探测序列上的关键字顺序递补,即用探测序列上下一个关键字覆盖待测关键字,并将原序列上之后一个关键字置为-1,这两种方法是否可行?为什么?给出一个可行的方法,并叙述它对查找和插入算法所产生的影响。

 
 

9.25 假设顺序表按关键字自大至小有序,试改写教科书9.1.1节中的顺序查找算法,将监视哨设在高下标端。然后画出描述此查找过程的判定树,分别求出等概率情况下查找成功和不成功的平均查找长度。

int Search_Sq(SSTable ST,int key){
	//在有序表上顺序查找的算法,监视哨设在高下标端
	ST.elem[ST.length+1].key=key;
	for(i=1;ST.elem[i].key>key;i++);
	if(i>ST.length||ST.elem[i].key<key)
		return ERROR;
	return i;
}

9.26 试讲折半查找的算法改写成递归算法。

int Search_Bin_Recursive(SSTable ST,int key,int low,int high){
	//折半查找的递归算法
	if(low>high) 
		return 0;
	mid=(low+high)/2;
	if(ST.elem[mid].key==key) 
		return mid;
	else if(ST.elem[mid].key>key)
		return Search_Bin_Recursive(ST,key,low,mid-1);
	else 
		return Search_Bin_Recursive(ST,key,mid+1,high);
}

9.27 试改写教科书9.1.2节中折半查找的算法,当r[i].key<=K=r[n].key时,返回n。

int Locate_Bin(SSTable ST,int key){
    //折半查找,返回小于或等于待查元素的最后一个结点号
    int *r;
    r=ST.elem;
    if(key<r .key)
        return 0;
    else if(key>=r[ST.length].key)
        return ST.length;
    low=1;high=ST.length;
    while(low<=high){
        mid=(low+high)/2;
        if(key>=r[mid].key&&key             return mid;
        else if(key<r[mid].key)
            high=mid;
        else 
            low=mid;
    } 
}

9.28 试编写利用折半查找确定记录所在块的分块查找算法。并讨论在块中进行顺序查找时使用“监视哨”的优缺点,以及必要时如何在分块查找的算法中实现设置“监视哨”的技巧。

typedef struct {
	int maxkey;
	int firstloc;
} Index;
typedef struct {
	int *elem;
	int length;
	Index idx[MAXBLOCK];
	int blknum;
} IdxSqList;
int Search_IdxSeq(IdxSqList L,int key){
	//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法
	if(key>L.idx[L.blknum].maxkey) 
		return ERROR; //超过最大元素
	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(k<i) return ERROR; //未找到
	return k;
}

9.29 已知一非空有序表,表中记录按关键字递增排列,以不带头结点的单循环链表作存储结构,外设两个指针h和t,其中h始终指向关键字最小的结点,t则在表中浮动,其初始位置和h相同,在每次查找之后指向刚查找到的结点。查找算法的策略是:首相将给定值K和t->key进行比较,若相等,则查找成功;否则因K小于或大于t->key而从h所指结点或t所指结点的后继结点起进行查找。
(1)按上述查找过程编写查找算法;
(2)画出描述此查找过程的判定树,并分析在等概率查找时查找成功的平均查找长度(假设表长为n,待查关键码K等于每个结点关键码的概率为1/n,每次查找都是成功的,因此在查找时,t指向每个结点的概率也为1/n)。

typedef struct {
	LNode *h; //h 指向最小元素
	LNode *t; //t 指向上次查找的结点
} CSList;
LNode *Search_CSList(CSList &L,int key){
	//在有序单循环链表存储结构上的查找算法,假定每次查找都成功
	if(L.t->data==key) 
		return L.t;
	else if(L.t->data>key)
		for(p=L.h,i=1;p->data!=key;p=p->next,i++);
	else
		for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);
	L.t=p;
	return p;
}

9.30 将9.28题的存储结构改为双向循环链表,且外设一个指针sp,其初始位置指向关键字最小的结点,在每次查找之后指向刚查找到的结点。查找算法的策略是:首先将给定值K和sp->key进行比较,若相等,则查找成功;否则依K小于或大于sp->key继续从*sp的前驱或后继结点进行查找。编写查找算法并分析等概率查找时查找成功的平均查找长度。

typedef struct {
	DLNode *pre;
	int data;
	DLNode *next;
} DLNode;
typedef struct {
	DLNode *sp;
	int length;
} DSList; //供查找的双向循环链表类型
DLNode *Search_DSList(DSList &L,int key){
	//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功
	p=L.sp;
	if(p->data>key){
		while(p->data>key) 
			p=p->pre;
		L.sp=p;
	}
	else if(p->data<key){
		while(p->data<key)
			p=p->next;
		L.sp=p;
	}
	return p;
}

9.31 试写一个判断给定二叉树是否为二叉排序树的算法,设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。

int last=0,flag=1;
int Is_BSTree(Bitree T){
	//判断二叉树T 是否二叉排序树,是则返回1,否则返回0
	if(T->lchild&&flag) 
		Is_BSTree(T->lchild);
	if(T->data<last)
		flag=0; //与其中序前驱相比较
	last=T->data;
	if(T->rchild&&flag) 
		Is_BSTree(T->rchild);
	return flag;
}

9.32 已知一棵二叉排序树上所有关键字中的最小值为-max,最大值为max,有-max<x<max,编写递归算法,求该二叉排序上的小于x且最靠近x的值a和大于x且最靠近x的值b。

int last=0;
void MaxLT_MinGT(BiTree T,int x){
	//找到二叉排序树T 中小于x 的最大元素和大于x 的最小元素
	if(T->lchild) 
		MaxLT_MinGT(T->lchild,x);
	if(last<x&&T->data>=x) //找到了小于x 的最大元素
		printf("a=%d\n",last);
	if(last<=x&&T->data>x) //找到了大于x 的最小元素
		printf("b=%d\n",T->data);
	last=T->data;
	if(T->rchild) 
		MaxLT_MinGT(T->rchild,x);
}

9.33 编写递归算法,从大到小输出给定二叉排序树中所有关键字不小于x的数据元素。要求你的算法的时间复杂度为O\left ( log_{n}+m \right ),其中n为排序树中所含结点数,m为输出的关键字个数。

void Print_NLT(BiTree T,int x){
	//从大到小输出二叉排序树T 中所有不小于x 的元素
	if(T->rchild) 
		Print_NLT(T->rchild,x);
	if(T->data<x) 
		exit(); //当遇到小于x 的元素时立即结束运行
	printf("%d\n",T->data);
	if(T->lchild) 
		Print_NLT(T->lchild,x); //先右后左的中序遍历
}

9.34 试写一时间复杂度为O\left ( log_{n}+m \right )的算法,删除二叉排序树中所有关键字不小于x的结点,并释放结点空间。其中n为树中所含结点数,m为被删除的结点个数。

void Delete_NLT(BiTree &T,int x){
	//删除二叉排序树T 中所有不小于x 元素结点,并释放空间
	if(T->rchild) 
		Delete_NLT(T->rchild,x);
	if(T->data<x) 
		exit(); //当遇到小于x 的元素时立即结束运行
	q=T;
	T=T->lchild;
	free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根
	if(T) 
		Delete_NLT(T,x);
}

9.35 假设二叉排序树以后继线索链表作存储结构,编写输出该二叉排序中所有大于a且不小于b的关键的算法。

void Print_Between(BiThrTree T,int a,int b){
	//打印输出后继线索二叉排序树T 中所有大于a 且小于b 的元素
	p=T;
	while(!p->ltag) 
		p=p->lchild; //找到最小元素
	while(p&&p->data<b){
		if(p->data>a) 
			printf("%d\n",p->data); //输出符合条件的元素
		if(p->rtag) 
			p=p->rtag;
		else{
			p=p->rchild;
			while(!p->ltag) p=p->lchild;
		}
	}
}

9.36 同9.35题的结构,编写在二叉排序树中插入一个关键字的算法。

void BSTree_Insert_Key(BiThrTree &T,int x){
	//在后继线索二叉排序树T 中插入元素x
	if(T->data<x){
		if(T->rtag) {
			p=T->rchild;
			q=(BiThrNode*)malloc(sizeof(BiThrNode));
			q->data=x;
			T->rchild=q;T->rtag=0;
			q->rtag=1;q->rchild=p;
		}
		else 
			BSTree_Insert_Key(T->rchild,x);
	}
	else if(T->data>x){ //插入到左子树中
		if(!T->lchild){ //T 没有左子树时,作为左孩子插入
			q=(BiThrNode*)malloc(sizeof(BiThrNode));
			q->data=x;
			T->lchild=q;
			q->rtag=1;q->rchild=T; //修改自身的线索
		}
		else 
			BSTree_Insert_Key(T->lchild,x);//T 有左子树时,插入左子树中
	}
}

9.37 同9.35题的结构,编写从二叉排序中删除一个关键字的算法。

Status BSTree_Delete_key(BiThrTree &T,int x){
	//在后继线索二叉排序树T 中删除元素x
	BTNode *pre,*ptr,*suc;//ptr 为x 所在结点,pre 和suc 分别指向ptr 的前驱和后继
	p=T;last=NULL; //last 始终指向当前结点p 的前一个(前驱)
	while(!p->ltag) 
		p=p->lchild; //找到中序起始元素
	while(p){
		if(p->data==x){ //找到了元素x 结点
			pre=last;
			ptr=p;
		}
		else if(last&&last->data==x) 
			suc=p; //找到了x 的后继
		if(p->rtag) 
			p=p->rtag;
		else{
			p=p->rchild;
			while(!p->ltag) 
				p=p->lchild;
		} //转到中序后继
		last=p;
	}
	if(!ptr) 
		return ERROR; //未找到待删结点
	Delete_BSTree(ptr); //删除x 结点
	if(pre&&pre->rtag)
		pre->rchild=suc; //修改线索
	return OK;
}
void Delete_BSTree(BiThrTree &T){
	//课本上给出的删除二叉排序树的子树T 的算法,按照线索二叉树的结构作了一些改动
	q=T;
	if(!T->ltag&&T->rtag) //结点无右子树,此时只需重接其左子树
		T=T->lchild;
	else if(T->ltag&&!T->rtag) //结点无左子树,此时只需重接其右子树
		T=T->rchild;
	else if(!T->ltag&&!T->rtag){ //结点既有左子树又有右子树
		p=T;r=T->lchild;
		while(!r->rtag){
			s=r;
			r=r->rchild; 
		}
		T->data=r->data; 
		if(s!=T)
			s->rchild=r->lchild;
		else 
			s->lchild=r->lchild; //重接r 的左子树到其双亲结点上
		q=r;
	}
	free(q); //删除结点
}

9.38 试写一算法,将一棵二叉排序树合并为一棵二叉排序树。

void BSTree_Merge(BiTree &T,BiTree &S){
	//把二叉排序树S 合并到T 中
	if(S->lchild) 
		BSTree_Merge(T,S->lchild);
	if(S->rchild) 
		BSTree_Merge(T,S->rchild); //合并子树
	Insert_Key(T,S); //插入元素
}
void Insert_Node(Bitree &T,BTNode *S){
	//把树结点S 插入到T 的合适位置上
	if(S->data>T->data){
		if(!T->rchild) 
			T->rchild=S;
		else 
			Insert_Node(T->rchild,S);
	}
	else if(S->data<T->data){
		if(!T->lchild)
			T->lchild=S;
		else 
			Insert_Node(T->lchild,S);
	}
	S->lchild=NULL; //插入的新结点必须和原来的左右子树断绝关系
	S->rchild=NULL; //否则会导致树结构的混乱
}

9.39 试写一算法,将一棵二叉排序树分裂为两棵二叉排序树,使得其中一棵树的所有节点的关键字都小于或等于x,另一棵树的任一结点的关键字均大于x。

void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x){
	//把二叉排序树T 分裂为两棵二叉排序树A 和B,其中A 的元素全部小于等于x,B 的元素全部大于x
	if(T->lchild)
		BSTree_Split(T->lchild,A,B,x);
	if(T->rchild)
		BSTree_Split(T->rchild,A,B,x); //分裂左右子树
	if(T->data<=x) 
		Insert_Node(A,T);
	else 
		Insert_Node(B,T); //将元素结点插入合适的树中
}
void Insert_Node(Bitree &T,BTNode *S){
	//把树结点S 插入到T 的合适位置上
	if(!T) T=S;
	else if(S->data>T->data){
		if(!T->rchild) 
			T->rchild=S;
		else 
			Insert_Node(T->rchild,S);
	}
	else if(S->data<T->data){
		if(!T->lchild) 
			T->lchild=S;
		else
			Insert_Node(T->lchild,S);
	}
	S->lchild=NULL;
	S->rchild=NULL;
}

9.40 在平衡二叉排序树的每个结点中增设一个lsize域,其值为它的左子树中的结点数加1,。试写一时间复杂度为O(logn)的算法,确定书中第k小的结点的位置。

typedef struct {
	int data;
	int bf;
	int lsize; 
	BlcNode *lchild,*rchild;
} BlcNode,*BlcTree; 
BTNode *Locate_BlcTree(BlcTree T,int k){
	//在含lsize 域的平衡二叉排序树T 中确定第k 小的结点指针
	if(!T) 
		return NULL; 
	if(T->lsize==k)
		return T; 
	else if(T->lsize>k)
		return Locate_BlcTree(T->lchild,k); //在左子树中寻找
	else 
		return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改k 的值
}

9.41 为B+树设计结点类型并写出算法,随机(而不是顺序)地查找给定的关键字K,求得它所在的叶子结点指针和它在该结点中的位置(提示:B+树中有两种类型的指针,结点结构也不尽相同,考虑利用记录的变体。)

typedef struct {
	enum {LEAF,BRANCH} tag; //结点类型标识
	int keynum;
	BPLink parent; //双亲指针
	int key[MAXCHILD]; //关键字
	union {
		BPLink child[MAXCHILD];//非叶结点的孩子指针
		struct {
			rectype *info[MAXCHILD];//叶子结点的信息指针
			BPNode *next; //指向下一个叶子结点的链接
		} leaf;
	}
} BPNode,*BPLink,*BPTree;//B+树及其结点类型
Status BPTree_Search(BPTree T,int key,BPNode *ptr,int pos){
	//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr 以及关键字在叶子结点中的位置pos
	p=T;
	while(p.tag==BRANCH){
		//沿分支向下查找
		for(i=0;i<p->keynum&&key>p->key[i];i++); //确定关键字所在子树
		if(i==p->keynum) 
			return ERROR; 
		p=p->child[i];
	}
	for(i=0;i<p->keynum&&key!=p->key[i];i++); //在叶子结点中查找
	if(i==p->keynum) 
		return ERROR; 
	ptr=p;pos=i;
	return OK;
}

9.42 假设Trie树上叶子结点的最大层次为h,同义词放在同一叶子结点中,试写在Trie树中插入一个关键字的算法。

void TrieTree_Insert_Key(TrieTree &T,StringType key){
	// 在Trie 树T 中插入字符串key
	q=(TrieNode*)malloc(sizeof(TrieNode));
	q->kind=LEAF;
	q->lf.k=key; 
	klen=key[0];
	p=T;i=1;
	while(p&&i<=klen&&p->bh.ptr[ord(key[i])]){
		last=p;
		p=p->bh.ptr[ord(key[i])];
		i++;
	} 
	if(p->kind==BRANCH){
		p->bh.ptr[ord(key[i])]=q; 
		p->bh.num++;
	}
	else{
		r=(TrieNode*)malloc(sizeof(TrieNode)); 
		last->bh.ptr[ord(key[i-1])]=r; 
		r->kind=BRANCH;r->bh.num=2;
		r->bh.ptr[ord(key[i])]=q;
		r->bh.ptr[ord(p->lf.k[i])]=p; 
	}
}

9.43 同9.42的假设,试写在Trie树中删除一个关键字的算法。

Status TrieTree_Delete_Key(TrieTree &T,StringType key){
	//在Trie 树T 中删除字符串key
	p=T;i=1;
	while(p&&p->kind==BRANCH&&i<=key[0]){ //查找待删除元素
		last=p;
		p=p->bh.ptr[ord(key[i])];
		i++;
	}
	if(p&&p->kind==LEAF&&p->lf.k=key){ //找到了待删除元素
		last->bh.ptr[ord(key[i-1])]=NULL;
		free(p);
		return OK;
	}
	else 
		return ERROR; 
}

9.44 已知某哈希表的装载因子小于1,哈希函数H(key)为关键字(标识符)的第一个字母在字母表中的序号,处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。

void Print_Hash(HashTable H){
	//按第一个字母顺序输出Hash 表中的所有关键字,其中处理冲突采用线性探测开放定址法
	for(i=1;i<=26;i++)
		for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex]) 
			if(H(H.elem[j].key)==i) printf("%s\n",H.elem[j]);
}
int H(char *s){//求Hash 函数
	if(s) 
		return s[0]-96; 
	else return 0;
}

9.45 假设哈希表长为m,哈希函数H(x),用连地址法处理冲突。试编写输入一组关键字并建造哈希表的算法。

typedef *LNode[MAXSIZE] CHashTable; //链地址Hash 表类型
Status Build_Hash(CHashTable &T,int m){
	//输入一组关键字,建立Hash 表,表长为m,用链地址法处理冲突.
	if(m<1)
		return ERROR;
	T=malloc(m*sizeof(WORD)); 
	for(i=0;i<m;i++) T[i]=NULL;
	while((key=Inputkey())!=NULL){ 
		q=(LNode*)malloc(sizeof(LNode));
		q->data=key;q->next=NULL;
		n=H(key);
		if(!T[n]) 
			T[n]=q; //作为链表的第一个结点
		else{
			for(p=T[n];p->next;p=p->next);
			p->next=q; 
		}
	}
	return OK;
}

9.46 假设有一个1000*1000的稀疏矩阵,其中1%的元素为非零元素,现要求用哈希表作存储结构、试设计一个哈希表并编写相应的算法,对给定的行值确定矩阵元素在哈希表上的位置。请将你的算法与在稀疏矩阵的三元组表存储结构上存取元素的算法(不必写出)进行时间复杂度的比较。

Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k){
	//根据行列值在Hash 表表示的稀疏矩阵中确定元素key 的位置k
	h=2*(100*(row/10)+col/10); 
	while(H.elem[h].key&&!EQ(H.elem[h].key,key))
		h=(h+1)%20000;
	if(EQ(H.elem[h].key,key)) 
		k=h;
	else k=NULL;
}