《数据结构第五章查找答案.pdf》由会员分享，可在线阅读，更多相关《数据结构第五章查找答案.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 请浏览后下载，资料供参考，期待您的好评与关注！数据结构与算法上机作业 第五章 查找 请浏览后下载，资料供参考，期待您的好评与关注！一、选择题 1、若构造一棵具有 n 个结点的二叉排序树，在最坏情况下，其高度不超过 B 。A.n/2 B.n C.(n+1)/2 D.n+1 2、分别以下列序列构造二叉排序数（二叉查找树），与用其他 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,120,130,110)3、不
2、可能生成下图所示的二叉排序树的关键字的序列是 A 。A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5 42513 4、在二叉平衡树中插入一个结点造成了不平衡，设最低的不平衡点为 A，并已知 A 的左孩子的平衡因子为 0，右孩子的平衡因子为 1，则应作 C 型调整使其平衡。A.LL B.LR C.RL D.RR 5、一棵高度为 k 的二叉平衡树，其每个非叶结点的平衡因子均为 0，则该树共有 C 个结点。A.2k-1-1 B.2k-1+1 C.2k-1 D.2k+1 6、具有 5 层结点的平衡二叉树至少有 A 个结点。A.12 B.11 C.10 D.
3、9 7、下面关于 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.3 B.4 C.5 D.6 12、有一个结点的关键字为 3276012483，采用移位叠加法生成 4 位
5、散列地址，则生成的地址为 B 。A.3482 B.3583 C.9018 D.9019 二、填空题 1、在查找过程中有插入或删除元素操作的，称为 动态 查找。2、一个无序序列可以通过构造一棵 二叉排序 树而变为一个有序序列，构造树的过程即为对无序序列进行排序的过程。3、对于一棵二叉排序树，按 中根 方法遍历得出的结点序列是从小到大排列的。4、对二叉排序树进行查找的方法是用待查找的值与根结点的键值进行比较，若比根结点的值小，则继续在 左 子树中查找。5、AVL 树为在构造二叉排序树时，为确保搜索的性能而保持树的平衡，保持平衡的方法为在构建 AVL 树时根据特定条件而进行 LL,RR,LR,RL
6、四种旋转操作，如对于下图的树，应该进行 RL RR 旋转。251932274026新插入结点 251932274045新插入结点 6、在 m 阶一棵 B-树中，若在某个结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是 m-1 ；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是 m/2-1 。7、127 阶 B-树中每个结点最多有 126 个关键字；除根结点外所有非终端结点至少有 棵子树；65 阶 B+树中，除根结点外所有非叶结点至少有 33 个关键字，最多有 65 棵子树 8、假设有 k 个关键字互为同义词（哈希值相同），若用线性探测再散列法把这
7、k 个关键字存入散列表中，至少要进行 k(k-1)/2 次探测。9、在散列排序法中，折叠法的哈希函数可分为 移位法和分界法 两种类型。10、散列法的填充因子=表中填入的记录数 /哈希表的长度 。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)中的元素，生成一棵二叉排序数，要求
8、：1、试画出生成之后的二叉排序树。2、对该二叉排序数作中根遍历，写出遍历序列。3、编程构建一个二叉排序数，并中根遍历验证上述结果。四、二叉排序树如下图所示，分别画出：1、删除关键字 15 以后的二叉树，并要求平均查找长度尽可能小。2、在原二叉排序树(即没有删除 15)上，插入关键字 20 40890156212233295 五、编写一个判别给定二叉树是否为二叉排序树的算法，假设二叉树是用左右链方式存储。六、试画出从空树开始，有字符序列(t,d,e,s,u,g,b,j,a,k,r,i)构成的二叉平衡树，并为每一次平衡处理指明旋转类型。七、假设一棵平衡二叉树的每个结点都标明了平衡因子 b，试设计一
9、个算法，利用平衡因子求平衡二叉树的高度。八、设有三阶 B-树（如下图所示），1、画出依次插入 18、33、97 后的 B-树 2、分别画出删除 66、16、43 后的 B-树 432655 601635 41485766 88 请浏览后下载，资料供参考，期待您的好评与关注！九、给定一组记录，其关键字为字符。各关键字插入顺序为 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 树：Amio
10、t,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 文件中，文件名格式为“学号+姓名”