数据结构第五章 查找 答案.doc

《数据结构第五章 查找 答案.doc》由会员分享，可在线阅读，更多相关《数据结构第五章 查找 答案.doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构第五章 查找 答案.精品文档.数据结构与算法上机作业第五章 查找一、选择题1、若构造一棵具有n个结点的二叉排序树，在最坏情况下，其高度不超过 B 。A. n/2B. nC. (n+1)/2D. n+12、分别以下列序列构造二叉排序数（二叉查找树），与用其他3个序列所构造的结果不同的是 C ：A. (100, 80, 90, 60, 120, 110, 130)B. (100, 120, 110, 130, 80, 60, 90)C. (100, 60, 80, 90, 120, 110, 130)D. (100, 80, 60, 90

2、, 120, 130, 110)3、不可能生成下图所示的二叉排序树的关键字的序列是 A 。A. 4 5 3 1 2 B. 4 2 5 3 1 C. 4 5 2 1 3 D. 4 2 3 1 54、在二叉平衡树中插入一个结点造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 C 型调整使其平衡。A. LLB. LRC. RLD. RR5、一棵高度为k的二叉平衡树，其每个非叶结点的平衡因子均为0，则该树共有 C 个结点。A. 2k-1-1B. 2k-1+1C. 2k-1D. 2k+16、具有5层结点的平衡二叉树至少有 A 个结点。A. 12B. 11C

3、. 10D. 97、下面关于B-和B+树的叙述中，不正确的是 C 。A. B-树和B+树都是平衡的多叉树B. B-树和B+树都可用于文件的索引结构C. B-树和B+树都能有效地支持顺序检索D. B-树和B+树都能有效地支持随机检索8、下列关于m阶B-树的说法错误的是 D 。A. 根结点至多有m棵子树B. 所有叶子结点都在同一层次C. 非叶结点至少有m/2（m为偶数）或m/2+1(m为奇数)棵子树D. 根结点中的数据是有序的9、下面关于哈希查找的说法正确的是 C 。A. 哈希函数构造得越复杂越好，因为这样随机性好，冲突小B. 除留余数法是所有哈希函数中最好的C. 不存在特别好与坏的哈希函数，要视

4、情况而定D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可10、与其他查找方法相比，散列查找法的特点是 C 。A. 通过关键字的比较进行查找B. 通过关键字计算元素的存储地址进行查找C. 通过关键字计算元素的存储地址并进行一定的比较进行查找D. 以上都不是11、有一组关键字8, 24, 16, 3, 12, 32, 51，采用除留余数法构造散列函数：H(key)=key mod 12，则将发生 次冲突。A. 3B. 4C. 5D. 612、有一个结点的关键字为3276012483，采用移位叠加法生成4位散列地址，则生成的地址为 B 。A. 3482B. 358

5、3C. 9018D. 9019二、填空题1、在查找过程中有插入或删除元素操作的，称为 动态 查找。2、一个无序序列可以通过构造一棵 二叉排序 树而变为一个有序序列，构造树的过程即为对无序序列进行排序的过程。3、对于一棵二叉排序树，按 中根 方法遍历得出的结点序列是从小到大排列的。4、对二叉排序树进行查找的方法是用待查找的值与根结点的键值进行比较，若比根结点的值小，则继续在 左 子树中查找。5、AVL树为在构造二叉排序树时，为确保搜索的性能而保持树的平衡，保持平衡的方法为在构建AVL树时根据特定条件而进行LL, RR, LR, RL四种旋转操作，如对于下图的树，应该进行 RL RR 旋转。6、在

6、m阶一棵B-树中，若在某个结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是 m-1 ；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是 m/2 -1 。7、127阶B-树中每个结点最多有 126 个关键字；除根结点外所有非终端结点至少有 棵子树；65阶B+树中，除根结点外所有非叶结点至少有 33 个关键字，最多有 65 棵子树8、假设有k个关键字互为同义词（哈希值相同），若用线性探测再散列法把这k个关键字存入散列表中，至少要进行 k(k-1)/2 次探测。9、在散列排序法中，折叠法的哈希函数可分为 移位法和分界法 两种类型。10、散列法的填充因子=

7、 表中填入的记录数 / 哈希表的长度 。11、设散列函数H和关键字k1, k2，若k1不等于k2，而H(k1)=H(k2)，则称这种现象为 冲突 。12、在哈希函数H(key)=key % p中，p一般应取 不大于表长的质数或是不含20以下的质因数的合数 。三、依次输入表(30, 15, 28, 20, 24, 10, 12, 68, 35, 50, 46, 55)中的元素，生成一棵二叉排序数，要求： 1、试画出生成之后的二叉排序树。 2、对该二叉排序数作中根遍历，写出遍历序列。 3、编程构建一个二叉排序数，并中根遍历验证上述结果。四、二叉排序树如下图所示，分别画出： 1、删除关键字15以后的

8、二叉树，并要求平均查找长度尽可能小。 2、在原二叉排序树(即没有删除15)上，插入关键字20五、编写一个判别给定二叉树是否为二叉排序树的算法，假设二叉树是用左右链方式存储。六、试画出从空树开始，有字符序列(t, d, e, s, u, g, b, j, a, k, r, i)构成的二叉平衡树，并为每一次平衡处理指明旋转类型。七、假设一棵平衡二叉树的每个结点都标明了平衡因子b，试设计一个算法，利用平衡因子求平衡二叉树的高度。八、设有三阶B-树（如下图所示）， 1、画出依次插入18、33、97后的B-树 2、分别画出删除66、16、43后的B-树九、给定一组记录，其关键字为字符。各关键字插入顺序为

9、C, S, M, T, A, E, P, U, X, K, G, B 1、给出从空树开始，顺序插入这些关键字后的3阶B+树，假设叶节点所能容纳最大关键码的数量为4。 2、分别给出在(1)建立的B+树上删除E、P、T后的3阶B+树十、画出如下数据集合的Trie树：Amiot, Avenger, Avro, Heinkel, HellDivder, Macchi, Marauder, Mustang, SpitFire, Sykhoi。 1、对关键字实行从左到右一次一个字符采样 2、利用单字符采样，在上述数据上构造最少层数的Trie树。十一、假定一个待散列存储的线性表为32, 75, 29, 63, 48, 94, 25, 46, 18, 70，散列地址空间为HT13，若采用除留余数法构造散列函数(假设p取11)和线性探测法(假设步长为3)处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，并求出平均查找长度。要求：1、上述作业要求在单独完成；2、完成后，于规定期限内提交到ftp服务器的相应目录中中，注意，在提交时将所编写的程序统一拷贝到一个Word文件中，文件名格式为“学号+姓名”