第九章集合答案.doc

"集合答案" 本资源是一个关于集合的答案文档，涵盖了选择题、判断题、填空题和应用题四部分。下面是对每个部分的详细知识点解释： 选择题： * C2.A3.1D3.2C4.D5.B6.D7.D8.C9.A10.D11.B12.1C12.2C13.1C13.2D13.3G13.4H14.1E14.2B14.3E14.4B14.5B15.1B15.2A16.A17.C18.C19.C20.D21.B22.C23.B24.C25.1B25.2F25.3I26.A27.D28.C29.1A29.2C30.B31.D32.D33.C34.D35.1D35.2C36.C 这些选择题涵盖了集合的基本概念、哈希函数、哈希表、链表、树、二叉排序树、平衡二叉树等知识点。 判断题： * 1.√2.√3.×4.×5.×6.√7.√8.×9.×10.×11.×12.√13.√14.×15.×16.×17.√18.×19.√20.×21.×22.×23.×24.×25.√26.×27.×28.√29.√30.×31.×32.√33.√34.×35.√36.√ 这些判断题要求学生对集合的基本概念和相关算法有深入的理解，能够正确地判断每个题目的真伪。 填空题： * 1．n n+1 2．4 3．6,9,11,12 4．5 5．26（第 4 层是叶子结点，每个结点两个关键字） 6．1,3,6,8,11,13,16,197．5,96 8．m-1,「m/2￿-1 9．2,4,310．(1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6)简单11．AVL 树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于 1。12．小于等于表长的最大素数或不包含小于 20 的质因子的合数 13．16 14．￿㏒2n」+115．(1)45 (2)45 (3)46（块内顺序查找） 16．k(k+1)/2 17．30，31.5（块内顺序查找）18．(1)顺序存储或链式存储 (2)顺序存储且有序 (3)块内顺序存储，块间有序 (4) 散列存储19．(n+1)/2 20．(n+1)/n*log2(n+1)-1 21．结点的左子树的高度减去结点的右子树的高度22．(1)顺序表(2)树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢出区23．直接定址法 24．log￿m/2￿()+1 25．O(N) 26．n(n+1)/2 27．54 28．31 29．37/12 30．主关键字 31．左子树 右子树32．插入 删除 33．14 34．(1)126 (2)64 (3)33 (4)6535．（1）low<=high (2) (low+hig) DIV 2 (3) binsrch:=mid (4)binsrch:=021n ￿36．(1) k (2) I<n+1 37．(1)rear=mid-1 (2)head=mid+1 (3)head>rear38．(1)p!=null (2)pf=p (3)p!=*t (4)*t=null 这些填空题涵盖了集合的基本概念、哈希函数、哈希表、链表、树、二叉排序树、平衡二叉树等知识点。 应用题： * 1．概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。 * 2．（1）散列表存储的基本思想是用关键字的值决定数据元素的存储地址 （2）散列表存储中解决碰撞的基本方法： ① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中 m 是表长，di 是增量。根据 di 取法不同，又分为三种：a．di =1，2，…，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。 这些应用题要求学生对集合的基本概念和相关算法有深入的理解，并能够将这些概念应用到实际问题中。 这个资源涵盖了集合的基本概念和相关算法，对学生的理解和应用能力提出了较高的要求。