|
设散列表长度为散列函数h(x)=x%给定的关键字序列为试画出分别用拉链法和线性探查法解决沖突时所构造的散列表并求出在等概率情况下这两种方法查找成功和失败时的平均查找长度请问装填因子的值是什么? 假定有k个关键字互为同义词若用线性探查法把这些同义词存入散列表中至少要进行多少次探查? 为什么说当装填因子非常接近时线性探查类似于顺序查找?为什么说当装填因子比较小(比如α=左右)时散列查找的平均查找时间为O()? 设顺序表中关键字是递增有序的试写一顺序查找算法将哨兵设在表的高下标端然后求出等概率情况下查找成功与失败时的ASL 试写出二分查找的递归算法 试写一算法判别给定的二叉树是否为二叉排序树设此二叉树以二叉链表为存储结构且树中结点的关键字均不相同 试写一递归算法从大到小输出二叉排序树中所有其值不小于x的关键字要求算法的时间为O(lgn+m)n为树中结点数m为输出关键字个数(提示先遍历右子树后遍历左子树) 写一个遍历B树的算法使输出的关键字序列递增有序算法中的读盘操作可假定为DiskRead 若采用除余法作为散列函数线性探查解决沖突则节中通用的散列表查找算法可改写为对线性探查专用的查找算法 int HashSearch(HashTable TKeyType Kint *pos){ int i=;//记录探查次数 *pos=K%m; //散列函数值作为第一个散列地址 while(i++<m) //最多探查m次 { if(T[*pos]key==K) return ;//查找成功返回 if(T[*pos]key==NIL) return ;//查找失败返回 *pos=(*pos+)%m;//用线性探查法求下一个探查地址 } return ;//查找失败且表满 }//HashSearch 假设散列表上的删除操作已将结点的关键字标记为DELETED(例如不妨设DELETED为)请修改上述散列表上的查找算法及插入算法HashInsert使之能正确地查找和插入 用拉链法解决沖突有关的类型说明和插入算法如下请据此写出散列表的建表查找及删除算法 typedef struct node{ KeyType key;//关键字 InfoType Otherinfo;//以下不处理此域 struct node *next;//链域 }CNodeType; typedef CNodeType *CHashTable[m];//散列表类型是一个指针数组 void ChainHashInsert(CHashTable TKeyType K){ //将关键字K插入表T中设散列函数为h(K)=K%m CNodeType *p; int addr; p=ChainHashSearch(TK);//在T中查找有无关键字为K的结点 if (p) printf(duplicate key!);//关键字已存在 else {//申请一个新结点将其关键字置为K并插入相应链表的头上 addr=K%m;//求散列函数值作为散列地址 p=(CNodeType *)malloc(sizeof(CNodeType)); p>key=K;p>next=T[addr];T[addr]=p;//将*p插入链表T[addr]的头部 }//endif }//ChainHashInsert |
