19.(n+1)/220.(n+1)/n*log2(n+1)-121.结点的左子树的高度减去结点的右子树 的高度 22.(1)顺序表(2)树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢 出区 直接定址法24.1ogm2(2)+1 25.0(N) 26.n(n+1)/2 27.54 29.37/12 30.主关键字 31.左子树右子 树 32.插入删除 34.(1)126(2)64(3)33(4)65 35.(1) low<=high (2)(lowthig) Div 2(3)binsrch: =mid(4)binsrch: =0 36.(1)k(2)I<n+1 37.(1rear=mid-1(2)head=mid+1 (3)head>rear (1)p!=null (2)pf=p (3)p!=kt (4)*t=null 四.应用题 1.概念是基本知识的主要部分,要牢固掌握。这里只列出一部分,目的是引起重视,解答 略 2.(1)散列表存储的基本思想是用关键字的值决定数据元素的存储地址 (2)散列表存储中解决碰撞的基本方法 ①开放定址法形成地址序列的公式是:H=(H(key)+d)%m,其中m是表长, d;是增量。根据d1取法不同,又分为三种 1,2,…,m-1称为线性探测再散列,其特点是逐个探测表空间,只要散列 中有空闲空间,就可解决碰撞,缺点是容易造成“聚集”,即不是同义词的关键字争夺同一 散列地址 b.d;=12,-12,2,-2,…,±k2(k≤m/2)称为二次探测再散列,它减少了聚集 但不容易探测到全部表空间,只有当表长为形如4j+3(j为整数)的素数时才有可能。 C.d;=伪随机数序列,称为随机探测再散列 ②再散列法H=RH1(key)i=1,2,…,k,是不同的散列函数,即在同义词产生 碰撞时,用另一散列函数计算散列地址,直到解决碰撞。该方法不易产生“聚集”,但增加 了计算时间。 ③链地址法将关键字为同义词的记录存储在同一链表中,散列表地址区间用 H[O.m1]表示,分量初始值为空指针。凡散列地址为i(0≤i≤m-1)的记录均插在以H[i] 为头指针的链表中。这种解决方法中数据元素个数不受表长限制,插入和删除操作方便,但 增加了指针的空间开销。这种散列表常称为开散列表,而①中的散列表称闭散列表,含义是 元素个数受表长限制。 ④建立公共溢出区设H[0.m1]为基本表,凡关键字为同义词的记录,都填入溢出 区 O[0.m1] (3)用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的 每个元素不是简单的地址,而是关键字和指针两个域,散列地址为i(0≤i≤m-1)的第 个关键字存储在地址空间向量第ⅰ个分量的“关键字”域。前者的指针域是动态指针,指向 同义词的链表,具有上面③的优缺点:后者实际是静态链表,同义词存在同一地址向量空间 (从最后向前找空闲单元),以指针相连。节省了空间,但易产生“堆积”,查找效率低 (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( 2 n +1 )+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)65 35．（1）low<=high (2) (low+hig) DIV 2 (3) binsrch:=mid (4)binsrch:=0 36．(1) k (2) I<n+1 37．(1)rear=mid-1 (2)head=mid+1 (3)head>rear 38．(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 称为线性探测再散列，其特点是逐个探测表空间，只要散列表 中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一 散列地址。 b．di =12，-1 2，2 2，-2 2，… ，k 2（k≤m/2） 称为二次探测再散列，它减少了聚集， 但不容易探测到全部表空间，只有当表长为形如 4j+3（j 为整数）的素数时才有可能。 c．di =伪随机数序列，称为随机探测再散列。 ② 再散列法 Hi=RHi（key） i=1，2，…，k，是不同的散列函数，即在同义词产生 碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加 了计算时间。 ③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用 H[0..m-1]表示，分量初始值为空指针。凡散列地址为 i（0≤i≤m-1）的记录均插在以 H[i] 为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但 增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是 元素个数受表长限制。 ④ 建立公共溢出区 设 H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出 区 O[0..m-1]。 （3）用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的 每个元素不是简单的地址，而是关键字和指针两个域，散列地址为 i（0≤i≤m-1）的第一 个关键字存储在地址空间向量第 i 个分量的“关键字”域。前者的指针域是动态指针，指向 同义词的链表，具有上面③的优缺点；后者实际是静态链表，同义词存在同一地址向量空间 （从最后向前找空闲单元），以指针相连。节省了空间，但易产生“堆积”，查找效率低。 （4）要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路