《第09章 查找1.doc》由会员分享,可在线阅读,更多相关《第09章 查找1.doc(7页珍藏版)》请在金锄头文库上搜索。
1、第九章 查找练习题一、选择题1适合于顺序查找法的存储结构是( )。 A. 顺序存储和链式存储 B. 索引存储 C. 压缩存储 D. 散列存储2进行二分法查找要求查找表( )。 A. 采用链式存储结构且关键字有序 B. 采用顺序存储结构 C. 采用顺序存储结构且关键字有序 D. 采用链式存储结构3对长度为n的线性表进行顺序查找,在等概率情况下,平均查找长度为( ). A. n B. n-1 C. n/2 D. (n+1)/24设有序表的关键字序列为(2,23,34,45,65,76,87,89,201,223,320),当用二分法查找法查找关键字值为89的比较次数是( )。 A. 2 B. 3
2、C. 4 D. 55在分块查找中,若线性表中共有625个元素,当采用顺序查找确定块时,每块的长度是( )。 A. 15 B. 25 C. 30 D. 356采用二分法查找,平均查找长度为( )。 A. O(n) B. O(n2) C. O(nlog2n) D. O(log2n)7设有n个元素构成二叉排序树,最差情况下,平均查找长度是( )。 A. O(n) B. O(n2) C. O(nlog2n) D. O(log2n)8在m阶B-树除根结点外,其余结点的关键字个数至少应有( )。 A. -1 B. B. +1 D. m-19设有n个元素构成二叉排序树,最好情况下,平均查找长度是( )。 A
3、. O(n) B. O(n2) C. O(nlog2n) D. O(log2n)10在m阶B-树中插入一个关键字,首先插入在某个叶子结点上,若该结点的关键字树超过( )时,则应对该结点进行分裂。 A. -1 B. B. +1 D. m-111处理冲突的方法是( )。 A. 除留余数法 B. 平方取中法 C 随机数法 D. 开放定址法12若表长为m,散列函数为h(key)=key%p ,则p的选取原则是( )。 A. p=m B. prchild); p=(linknode *)malloc(sizeof(Linknode); p-data=t-key; p-next=La; La=p; ino
4、rdbst(T-lchild); (1)指出程序功能;(2)若二叉排序树T右图所示:试画出*La的结构;2 阅读程序指出程序功能int searchhash(keytype k, Hashtable T) /T0.m-1为散列表,pmint i=0,pos,h; h=k%p; pos=h; while(Tpos.key!=k&Tpos.key)i+; pos=(h+i)%m;if (Tpos.key=k) return pos;else return 1; 3阅读程序填上适当的语句(二分法查找)int BinSearch(Seqlist R,keytype K)/R1.n为有序表 int lo
5、w=1,high=n,mid; while(lowK) (2) else low=mid+1; (3) 五、程序设计题1 散列表中删除一个结点的算法。2 二叉排序树查找的非递归算法。3 链表结构上实现顺序查找,要求利用监视哨技术。4设顺序表中关键字是递增有序的,试写一顺序查找算法,将哨兵设在表的高下标端。然后求出等概率情况下查找成功与失败时的平均查找长度ASL。5试写出二分法查找的递归算法。6试写一算法判别给定的二叉树是否为二叉排序树,设此二叉树以二叉链表为存储结构,且树中结点的关键字均不相同。7试写一递归算法,从大到小输出二叉排序树中所有其值不小于x的关键字。要求算法的时间为O(lgn+m)
6、,n为树中结点数,m为输出的关键字个数(提示:先遍历右子树,后遍历左子树)。8写一个遍历B-树的算法,是输出的关键字序列递增有序。算法中的读盘操作可假定为Diskread。9若采用除余法作为散列函数,线性探测法解决冲突,则9.4.4节中通用的散列表查找算法可以改写为对线性探测法专用的算法:假设散列表上的删除操作已将结点的关键字标记为DELETE(例如,不妨设DELETE为-2)。请修改上述散列表上的查找算法及插入算法Hashinsert,使之能正确的查找和插入。10用拉链法解决冲突,有关的类型说明和插入算法如下,请据此写出散列表的建表、查找及删除算法。typedef struct node K
7、eytype key;Infotype otherinfo;struct node *next;Cnodetype;typedef Cnodetype *Chashtablem;void chainhashinsert(Chashtable T,Keytype K) Cnodetype *p; int addr; p=chainhashsearch(T,K); if (p) printf(duplicate key!); else addr=K%m;p=(Cnodetype*)malloc(sizeof(Cnodetype);p-key=K;p-next=Taddr;Taddr=p;endif/chainhashinsert同步练习题答案一、