《第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同步练习题答案一、
