网络安全的级别 - welcome to nginx!

《网络安全的级别 - welcome to nginx!》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第9章文件与动态存储管理329查找与索引技术作业8单项选择题1．若在线性表中采用折半查找法查找元素，该线性表应该（　　　）。（北方名校经典试题）A）元素按值有序B）采用顺序存储结构C）元素按值有序，且采用顺序存储结构D）元素按值有序，且采用链式存储结构【分析】能采用折半查找法查找元素的线性表，必须是有序表，且是顺序存储的，不能是链式存储。这题由于折半查找要求能够直接定位线性表中任一元素，而链式结构无法做到这一点。【答案：C】2．在下列查找方法中，平均查找速度是快的是（　　　）。A）顺序查找B）折半查找C）分块查找D）二叉排序树查找【分

2、析】顺序查找的平均时间复杂度为O(n2)，分块查找的平均时间复杂度为O((n/s+1)/2+1)或O(log2(n/s+1)+s/2)，都比折半查找平均时间复杂度O(log2n)大，虽然二叉排序树查找时在随机情况下的时间复杂度也为O(log2n)，但是折半查找在最坏情况下的时间复杂度为O(log2n)，而当二叉排序树查找为单支树时，查找时与顺序查找相同，时间复杂度为O(n2)，所以本题应选择B。【答案：B】3．在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与（　　　　）量级相当。（东部名校经典试题）A）顺序查找B）折

3、半查找C）分块查找D）前面都不正确【分析】在随机的情况下，二叉排序树的平均查找长度的数据量级为O(log2n)，与折半查找同数量级。【答案：B】二、综合题1．已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。（东部名校经典试题）【解答】构造二叉排序树的过程如下图所示。　　　　　　　　　　　　　　　　　　　　第9章文件与动态存储管理329图　构造二叉排序树的过程示意图构造的二叉排序树如下图所示：图　二叉排序树示意图2．已知一组关键字为（19，14，23，1，68，20，84，27，55，11，10，79），哈希函数：

4、H(key)=keyMOD13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。（东部名校经典试题）【解答】哈希表如下图所示：图　哈希表示意图平均查找长度为ASL=(1*6+2*4+3*1+4*1)=1.753．已知哈希表地址空间是0..8，哈希函数是H(k)=k%7，采用线性探测再散列处理冲突，将序列{100,20,21,35,3,78,99,45}数据序依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。（东部名校经典试题）【解答】哈希表及查找各关键字的比较次数如下表所示：　　　　

5、　　　　　　　　　　　　　　　　第9章文件与动态存储管理329哈西表及查找各关键字的比较次数哈希地址012345678关键字2135100378992045比较次数12114515平均查找长度=4．已知关键字序列{12,26,38,89,56}，试构造平衡二叉树。【解答】在构造平衡二叉树时，与构造二叉排序树类似，也是从空二叉树开始，用二叉排序树的方法依次插入结点，如出现不平衡时，作适当的旋转操作使用变成平衡二叉树即可，本题构造过程如下图7-32所示：图　构造平衡二叉树的过程示意图如下图所示：图　平衡二叉树示意图5．编写判定给定的二叉树

6、是否是二叉排序树的函数。（南方名校经典试题）注：此题选做。【解答】判定二叉树是否为二叉排序树同样是建立在中序遍历的框架基础下，在遍历中附设一指针pre指向当前访问结点的中序直接前驱，每访问一个结点便比较前驱结点pre和此结点是否有序，若遍历结束后各结点和其中序直接前驱均满足有序，则此二叉树为二叉排序树；否则只要有一个结点不满足，那么此二叉树就不是二叉排序树。C++语言版测试程序见8_2_5c++，具体算当如下：template　　　　　　　　　　　　　　　　　　　　第9章文件与动态存储管理329boolIsBST

7、(Binary_node*sub_root,Binary_node*pre=NULL)//判断二叉树sub_root是否为二叉排序树,pre为当前被遍历结点的前驱，初值为空{if(sub_root){if(IsBST(sub_root->left,pre)==false)returnfalse;//如左子树不为二叉排序树，则返回falseif(pre){if(pre->data>sub_root->data)returnfalse;//如果pre与当前结点无序，则返回false}pre=sub_ro

8、ot;if(IsBST(sub_root->right,pre)==false)returnfalse;//如左子树不为二叉排序树，则返回false}returntrue;}template