《数据结构》课件第7章 (2).ppt

8.有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为()。A.?35/12 B.?37/12 C.?39/12 D.?43/129．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为()。A.从第0个元素往后查找该数据元素B.从第1个元素往后查找该数据元素C.从第n个元素开始往前查找该数据元素D.与查找顺序无关10．解决哈希法中出现的冲突问题常采用的方法是()。A.数字分析法、除留余数法、平方取中法B.数字分析法、除留余数法、线性探查法C数字分析法、线性探查法、双哈希函数探查法D.线性探查法、双哈希函数探查法、拉链法11．采用线性探查法解决冲突问题，所产生的一系列后继散列地址()。A.必须大于等于原哈希地址B.必须小于等于原哈希地址C.可以大于或小于但不能等于原哈希地址D.地址大小没有具体限制12．对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于()。A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D.两种表都不适合13.哈希表的平均查找长度()。A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关而与表的长度有关D.与处理冲突方法无关而与表的长度无关三、应用题1.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。2.已知一组关键字序列{49，38，65，97，76，13，27，44，82，35，50}，画出由此生成的二叉排序树。3.已知一组关键字序列{49，38，65，97，76，13，27，44，82，35，50}，画出由此生成的平衡二叉树。4．设有一组关键字{19，1，23，14，55，20，84，27，68，11，10，77}，采用哈希函数Hash(key)=key%13，用开放地址法的平方探查法解决冲突，试在0～18的哈希地址空间中对该关键字序列构造哈希表。实训指导

一、二叉排序树查找【实训目的】(1)熟练掌握二叉排序树中插入结点的递归算法；(2)熟练掌握二叉树中的创建、删除和查找算法。【实训内容】输入若干个整数，建立二叉排序树，在其上进行插入、删除和查找操作。【实现提示】首先实现插入算法，然后调用插入算法来实现生成算法。删除算法和查找算法中注意体会指针的运用。【实现过程】#includestdio.htypedefintKeytype; //关键字类型typedefstructnode{Keytypekey; //关键字的值structnode*lchild,*rchild; //左右指针}BSTNode,*BSTree;voidInsertBST(BSTree*bst,Keytypekey){...} //算法7-4voidCreateBST(BSTree*bst){...} //算法7-5BSTNode*DelBST(BSTreet,Keytypek){...} //算法7-6BSTreeSearchBST(BSTreebst,Keytypekey){...} //算法7-7voidInorder(BSTreet){...} //中序遍历算法main(){BSTreebst,p;Keytypekey;printf(建立二叉排序树);CreateBST(bst);printf(中序遍历结果为:);Inorder(bst);printf(请输入待删除关键字:);scanf(%d,key);bst=DelBST(bst,key);printf(中序遍历结果为:);Inorder(bst);printf(请输入待插入关键字:);scanf(%d,key);InsertBST(bst,key);printf(中序遍历结果为:);Inorder(bst);printf(请输入待查找关键字:);scanf(%d,key);