查找 答案.docx

《查找 答案.docx》由会员分享，可在线阅读，更多相关《查找 答案.docx（13页珍藏版）》请在三一办公上搜索。

1、查找 答案一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找 。 2. 线性有序表high) return 0; /查找不到时返回0 mid=(low+high)/2; if(ST.elemmid.key= =key) return mid; else if(ST.elemmid.keykey) return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); /Search_Bin_Recursive 2.试写一个判别

2、给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。 解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树” 原则）。 若要采用递归算法，建议您采用如下的函数首部： bool BisortTree(BiTree T, BiTree&PRE)，其中PRE为指向当前访问结点的前驱的指针。 一个漂亮的算法设计如下： int last=0, flag=1; / last是全局变量，用来记录前驱结点值，只要每个结点都比前

3、驱大就行。 int Is_BSTree(Bitree T) /判断二叉树T是否二叉排序树，是则返回1，否则返回0 if(T-lchild&flag) Is_BSTree(T-lchild); if(T-datadata; if(T-rchild&flag) Is_BSTree(T-rchild); return flag; /Is_BSTree 3. 已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。 解：设计哈希表的步骤为： a) 根据所选择的处理冲突的方法求出装载因子a的上界； b) 由a值设计哈希

4、表的长度m； c) 根据关键字的特性和表长m选定合适的哈希函数。 刘注：要求ASL3，则m必然要尽量长，以减少冲突； 7 4. 已知某哈希表的装载因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。 解：注意此题给出的条件：装载因子a1, 则哈希表未填满。由此可写出下列形式简明的算法： void PrintWord(Hash Table ht) /按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法。 for(i=1; i=26; i+) j=i; While(ht.elemj.key) if(Hash(ht.elemj.key=i)printf(ht.elemj.key); j=(j+1)%m; /PrintWord 8