21.设散列表长度为11，散列函数h(x)=x%11,给定的关键字序列为：1，13，13，34，38，33，27，22.试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么?
答：
(1)拉链法如下图：
T[0..10]
┌──┐
0│ │→ 33 → 22 →∧
├──┤
1│ │→ 1 → 12 →34→ ∧
├──┤
用拉链法的查找成功平均查找长度为：
ASLsucc=(1*4+2*3+3*1)/8=1.625
查找失败时平均查找长度为：
ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.73
2│ │→ 13 →∧
├──┤
3│ ∧ │
├──┤
4│ ∧ │
├──┤
5│ │→ 38 → 27 →∧
├──┤
6│ ∧ │
├──┤
7│ ∧ │
├──┤
8│ ∧ │
├──┤
9│ ∧ │
├──┤
10│ ∧ │
(2)线性探查法如下图：
下标 0 1 2 3 4 5 6 7 8 9 10
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
T[0..10]│33│1 │13│12│34│38│27│22│ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
探查次数 1 1 1 3 4 1 7 8
用线性探查法查找成功时平均查找长度为：
ASLsucc=(1+1+1+3+4+1+7+8)/8=3.25
查找失败时平均查找长度为：
ASLunsucc=(9+8+7+6+5+4+3+2+1+1+1)/11=4.3
装填因子α拉链=4/11=0.36 α线性探查=8/11=0.73
22.假定有k个关键字互为同义词，若用线性探查法把这些同义词存入散列表中，至少要进行多少次探查?
答：
至少要进行1+2+3...+k-1+k次探查。
也就是说，在散列表的一连串连续空间内，第一个关键字只需探查一次，第二个就要探查2次，如此这般，第k个关键字就要探查k次才能找到位置存放。所以至少要把它们全加起来才够。
23.为什么说当装填因子非常接近1时，线性探查类似于顺序查找?为什么说当装填因子比较小(比如α=0.7左右)时，散列查找的平均查找时间为O(1)?
答：
当α非常接近1时，整个散列表几乎被装满。由于线性探查法在关键字同义时解决冲突的办法是线性地向后查找，当整个表几乎装满时，它就很类似于顺序查找了。
当α比较小时，关键字碰撞的几率比较小，一般情况下只要按照散列函数计算出的结果能够1次性就找到相应结点，因此它的平均查找时间接近于1.
24.设顺序表中关键字是递增有序的，试写一顺序查找算法，将哨兵设在表的高下标端。然后求出等概率情况下查找成功与失败时的ASL.
答:
typedef struct{
KeyType key；
InfoType otherinfo； //此类型依赖于应用
}NodeType；
typedef NodeType SeqList[n+1]； //n号单元用作哨兵
int SeqSearch(Seqlist R，KeyType K)
{ //在关键字递增有序的顺序表R[0..n-1]中顺序查找关键字为K的结点，
//成功时返回找到的结点位置，失败时返回-1
int i；
R[n].key=K； //设置哨兵
for(i=0；R[i].key<=K;i--)； //从表前往后找
if (i
K)
return BinSearch( R，K,low，mid-1)//在R[low..mid-1]中查找
else
return BinSearch( R，K,mid+1，high)； //在R[mid+1..high]中查找
}
return 0； //当low>high时表示查找区间为空，查找失败
} //BinSeareh
26试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同。
解：
由二叉排序树的定义可得：二叉排序树中左子树的所有结点的值都小于根结点的值，所有右子树中结点的值都大于根结点的值。那么只要对待判定的二叉树中的结点按层遍历并判断即可。在该算法中要用到队列保存已遍历的结点指针。
typedef BinTNode *DataType;//循环队列中元素为二叉树结点指针
int BinSortStree(BinTree T)
{
CirQueue Q;
BinTNode *p;
if (!T) return 1;//空树为二叉排序树
InitQueue(&Q);
EnQueue(&Q,T);
while(!QueueEmpty(&Q))
{
p=DeQueue(&Q);
if (p->lchild)
if (p->datalchild->data) return -1;//不是二叉排序树
else EnQueue(&Q,p->lchild);
if (p->rchild)
if (p->data>p->rchild->data) return -1;//不是二叉排序树
else EnQueue(&Q,p->rchild);
}
return 1;//是二叉排序树
}
27.试写一递归算法，从大到小输出二叉排序树中所有其值不小于x的关键字。要求算法的时间为O(lgn+m)，n为树中结点数，m为输出关键字个数(提示：先遍历右子树，后遍历左子树)。
答：
typedef int KeyType； //假定关键字类型为整数
typedef struct node { //结点类型
KeyType key； //关键字项
InfoType otherinfo； //其它数据域，InfoType视应用情况而定，下面不处理它
struct node *lchild，*rchild； //左右孩子指针
} BSTNode；
typedef BSTNode *BSTree；
void OUTPUTNODE(BSTree T,KeyType x)
{//从大到小输出二叉排序树中所有其值不小于x的关键字
if (T)
{
OUTPUTNODE( T->rchild,x);
if (T->key>=x) printf("%d",T->key);
OUTPUTNODE( T->Lchild,x);
}
}
28.写一个遍历B-树的算法，使输出的关键字序列递增有序。算法中的读盘操作可假定为DiskRead。
答：
#define Max l000 //结点中关键字的最大数目：Max=m-1，m是B-树的阶
#define Min 500 //非根结点中关键字的最小数目：Min=「m/2(-1
typedef int KeyType； //KeyType应由用户定义
typedef struct node{ //结点定义中省略了指向关键字代表的
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
的指针
int keynum； //结点中当前拥有的关键字的个数，keynum<=Max
KeyType key[Max+1]； //关键字向量为key[1..keynum]，key[0]不用。
struct node *parent； //指向双亲结点
struct node *son[Max+1]；//孩子指针向量为son[0..keynum]
}BTreeNode；
typedef BTreeNode *BTree；
void travelBtree(BTree T){
//按关键字递增序输出B-树序列
int i;
if (T){
for(i=0;i<=T->keynum;i++)//T->keynum个关键字的结点有T->keynum+1棵子树
{
if (T->son[i]){
DiskRead(T->son[i]);//读入根结点的第i棵子树
travelBtree(T->son[i]);//遍历第i棵子树
}
if (ikeynmu)//若刚遍历的子树不是最后一棵子树
printf("%d",T->key[i+1];
}
}
29若采用除余法作为散列函数，线性探查解决冲突，则9.4.4节中通用的散列表查找算法可改写为对线性探查专用的查找算法：
int HashSearch(HashTable T,KeyType K,int *pos){
int i=0;//记录探查次数
*pos=K%m; //散列函数值作为第一个散列地址
while(i++key=K;p->next=T[addr];T[addr]=p;//将*p插入链表T[addr]的头部
}//endif
}//ChainHashInsert
解：
(1)建表
void ChainHashCreat(CHashTable T){
//设散列函数为h(K)=K%m,建立以拉链法为解决冲突方法的散列表
CNodeType *p;
int addr;
int i;
KeyType K;
for(i=0;ikey=K;p->next=T[addr];T[addr]=p;//将*p插入链表T[addr]的头部
}//endif
scanf("%d",&K);
}//endwhile
}//ChainHashCreat
(2)查找
CNodeType ChainHashSearch(CHashTable T,KeyType K)
{//查找关键字值为K的结点，若有返回该结点指针，否则返回NULL
CNodeType *p;
int addr;
addr=K%m;//求散列函数值
p=T[addr];
while (p)&&(p->key!=K)
p=p->next;
return p;
}
(3)删除
CNodeType ChainHashDelete(CHashTable T,KeyType K)
{//删除关键字值为K的结点，若有返回该结点指针，否则返回NULL
CNodeType *p,*q;
int addr;
addr=K%m;//求散列函数值
p=T[addr];
if (p)&&(p->key==K) T[addr]=p->next;//要删的是 T[addr]表的第一个结点
while (p->next)&&(p->next->key!=K)
p=p->next;
if (p->next)
{q=p;p=p->next;q->next=p->next;//删除p}
return p;
}
浙公网安备 33021202002483