《2022年数据结构第五章查找答案.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构第五章查找答案.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构与算法上机作业第五章 查找精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 6 页 - - - - - - - - - - 一、选择题1、若构造一棵具有n 个结点的二叉排序树，在最坏情况下，其高度不超过 B 。A. n/2 B. n C. (n+1)/2 D. n+12、分别以下列序列构造二叉排序数（二叉查找树） ，与用其他 3 个序列所构造的结果不同的是 C ：A. (100, 80, 90, 60, 120, 110, 130) B. (100, 120, 110, 130, 80,
2、 60, 90)C. (100, 60, 80, 90, 120, 110, 130) D. (100, 80, 60, 90, 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 5425134、在二叉平衡树中插入一个结点造成了不平衡，设最低的不平衡点为A，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 C 型调整使其平衡。A. LL B. LR C. RL D. RR5、一棵高度为k 的二叉平衡树， 其每个非叶结点的平衡因子均为0，则该树共有
3、 C 个结点。A. 2k-1-1 B. 2k-1+1 C. 2k-1 D. 2k+16、具有 5层结点的平衡二叉树至少有 A 个结点。A. 12 B. 11 C. 10 D. 97、下面关于B-和 B+树的叙述中，不正确的是 C 。A. B- 树和 B+树都是平衡的多叉树B. B- 树和 B+树都可用于文件的索引结构C. B- 树和 B+树都能有效地支持顺序检索精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 6 页 - - - - - - - - - - D. B- 树和 B+树都能有效地支持
4、随机检索8、下列关于m阶 B-树的说法错误的是 D 。A. 根结点至多有m棵子树B. 所有叶子结点都在同一层次C. 非叶结点至少有m/2（m为偶数）或m/2+1(m 为奇数 ) 棵子树D. 根结点中的数据是有序的9、下面关于哈希查找的说法正确的是 C 。A. 哈希函数构造得越复杂越好，因为这样随机性好，冲突小B. 除留余数法是所有哈希函数中最好的C. 不存在特别好与坏的哈希函数，要视情况而定D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可10、与其他查找方法相比，散列查找法的特点是 C 。A. 通过关键字的比较进行查找B. 通过关键字计算元素的存储地址进行查
5、找C. 通过关键字计算元素的存储地址并进行一定的比较进行查找D. 以上都不是11、有一组关键字8, 24, 16, 3, 12, 32, 51 ，采用除留余数法构造散列函数：H(key)=key mod 12，则将发生次冲突。A. 3 B. 4 C. 5 D. 612、有一个结点的关键字为83，采用移位叠加法生成4 位散列地址，则生成的地址为B 。A. 3482 B. 3583 C. 9018 D. 9019二、填空题1、在查找过程中有插入或删除元素操作的，称为动态查找。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - -
6、- - -第 3 页，共 6 页 - - - - - - - - - - 2、一个无序序列可以通过构造一棵二叉排序树而变为一个有序序列，构造树的过程即为对无序序列进行排序的过程。3、对于一棵二叉排序树，按中根方法遍历得出的结点序列是从小到大排列的。4、对二叉排序树进行查找的方法是用待查找的值与根结点的键值进行比较，若比根结点的值小，则继续在左子树中查找。5、AVL 树为在构造二叉排序树时，为确保搜索的性能而保持树的平衡，保持平衡的方法为在构建 AVL树时根据特定条件而进行LL, RR, LR, RL四种旋转操作，如对于下图的树，应该进行 RL RR 旋转。251932274026新插入结点25
7、1932274045新插入结点6、在 m阶一棵 B-树中，若在某个结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是 m-1 ；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是m/2 -1 。7、127 阶 B-树中每个结点最多有 126 个关键字； 除根结点外所有非终端结点至少有棵子树； 65 阶 B+树中，除根结点外所有非叶结点至少有 33 个关键字， 最多有 65 棵子树8、假设有 k 个关键字互为同义词（哈希值相同） ，若用线性探测再散列法把这k 个关键字存入散列表中，至少要进行 k(k-1)/2 次探测。9、在散列排序法中，折叠法的哈希函数
8、可分为移位法和分界法两种类型。10、散列法的填充因子= 表中填入的记录数 / 哈希表的长度。11、设散列函数H和关键字 k1, k2 ，若 k1 不等于 k2，而 H(k1)=H(k2) ，则称这种现象为冲突。12、在哈希函数H(key)=key % p中， p 一般应取不大于表长的质数或是不含20 以下的精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 6 页 - - - - - - - - - - 质因数的合数。三、依次输入表(30, 15, 28, 20, 24, 10, 12, 68,
9、35, 50, 46, 55)中的元素，生成一棵二叉排序数，要求： 1、试画出生成之后的二叉排序树。 2、对该二叉排序数作中根遍历，写出遍历序列。 3、编程构建一个二叉排序数，并中根遍历验证上述结果。四、二叉排序树如下图所示，分别画出： 1、删除关键字15 以后的二叉树，并要求平均查找长度尽可能小。 2、在原二叉排序树( 即没有删除 15) 上，插入关键字2040890156212233295五、编写一个判别给定二叉树是否为二叉排序树的算法，假设二叉树是用左右链方式存储。六、试画出从空树开始，有字符序列(t, d, e, s, u, g, b, j, a, k, r, i)构成的二叉平衡树，并
10、为每一次平衡处理指明旋转类型。七、假设一棵平衡二叉树的每个结点都标明了平衡因子b，试设计一个算法，利用平衡因子求平衡二叉树的高度。八、设有三阶B-树（如下图所示） ， 1、画出依次插入18、33、97 后的 B-树精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 6 页 - - - - - - - - - - 2、分别画出删除66、16、43 后的 B-树432655 601635 41485766 88九、给定一组记录，其关键字为字符。各关键字插入顺序为C, S, M, T, A, E, P,
11、 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
12、, 25, 46, 18, 70，散列地址空间为HT13 ， 若采用除留余数法构造散列函数( 假设 p 取 11) 和线性探测法( 假设步长为 3) 处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，并求出平均查找长度。要求：1、上述作业要求在单独完成；2、完成后，于规定期限内提交到ftp服务器的相应目录中中，注意，在提交时将所编写的程序统一拷贝到一个Word 文件中，文件名格式为“学号+姓名”精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 6 页 - - - - - - - - - -