算法与数据结构 C语言版 第二版 (陈守孔 孟佳娜 武秀川 著) 机械工业出版社 课后答案 第9章 查找

课后答案网 9 章 集合 一、基础知识题 若对长度均为 n 的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论二者在等概率情况下平均查找长度是否相同？ （ 1）查找不成功，即表中没有和关键字 K 相等的记录； （ 2）查找成功，且表中只有一个和关键字 K 相等的记录； （ 3）查找成功，且表中有多个和关键字 K 相等的记录，要求计算有多少个和关键字 K 相等的记录。 【解答】 （ 1）平均查找长度不相同。前者在 n+1 个位置均可能失败，后者失败时的查找长度都是 n+1。 （ 2）平均查找长度相同。在 n 个位置上均可能成功 。 （ 3）平均查找长度不相同。前者在某个位置上 (1 f 是 p 的双亲 if(p-i) f=p;p=p- s=(; 申请结点空间 s-i; s- s-if(f= T=s; 根结点 if(s- f-s; 左子女 f-s; 右子树根结点的值大于等于根结点的值 算法结束 写删除二叉排序树中值是 X 的结点的算法。要求删除结点后仍然是二叉排序树，并且高度没有增长。 【题目分析】在二叉排序树上删除结 点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。 X) 在二叉排序树 ，删除其关键字为 X 的结点 f,p=p & p-X) 查找值为 X 的结点 if(p-) f=p; p=p- f=p; p=p- if(p= 无关键字为 X 的结点 n” ); ); p- 被删结点无左子树 if(f-p) f-p- 将被删结点的右子树接到其双亲上 f-p- q=p; s=p- 被删结点有左子树 s-= 查左子树中最右下的结点 (中序最后结点 ) q=s; s=s- p-s- 结点值用其左子树最右下的结点的值代替 if(q=p) p-s- 被删结点左子 树的根结点无右子女 q-s- s 是被删结点左子树中序序列最后一个结点 s); 算法结束 设二叉排序树的各个元素值均不相同，设计一个递归算法按递减次序打印各元素的值。 【题目分析】按着“右子树根结点左子树”遍历二叉排序树，并输出结点的值。 按递减次序输出二叉排序树结点的值 课后答案网 s,p= s 是元素为二叉树结点指针的栈，容量足够大 ; p | ) p) s+p; bt=p- 沿右子树向下 if() p=s p- p=p- 结束 以下是递归输出，算法思想是一样的。 按递 减次序输出二叉排序树结点的值 p= if(p) 中序遍历右子树 p- 访问根结点 中序遍历左子树 结束 记录 ， 关键字值从小到大顺序存储在数组 r1.，在 rn+1处设立一个监视哨，其关键字值为 + ; 试写一查找给定关键字 k 的算法 ;并画出此查 找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。 r， n， k) 在 n 个关键字从小到大排列的顺序表中，查找关键字为 k 的结点 rn+1 在高端设置监视哨 i=1; riX) 查找值为 X 的结点， f 指向当前结点的双亲 f=p; if(p-p=p- 课后答案网 p) 无值为 x 的 结点，插入之 p=(); p-; p- p-if(t= t=p; 若初始为空树，则插入结点为根结点 if(f-) f-p; f-p; p-; 查询成功，值域为 X 的结点的 1 设一棵平衡二叉树的每个结点都标明了平衡因子 b，试设计一个算法，求平衡二叉树的高度。 【题目分析】 因为二叉树各结点已标明了平衡因子 b，故从根结点开始记树的层次。根结点的层次为 1，每下一层，层次加 1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子 b 为 0 时，任选左、右一分枝向下查找，若 b 不为 0，则沿左 (当 b=1 时 )或右 (当 b= )子树向下查找。 t) 求平衡二叉树 t 的高度 ; p=t; p) ; 树的高度增 1 if(p- 1 沿右分枝向下 p=p- 0 沿左分枝向下 ( 平衡二叉树的高度 算法结束 二叉排序树的存储 结构为： *一个结点 *x 的 的值是以该结点为根的子树中结点的总数（包括 *x 本身）。例如，下图中 x 所指结点的 为 4。设树高为 h，试写一时间为 O(h)的算法 ， x)返回 x 所指结点在二叉排序树 T 的中序序列里的排序序号，即：求 x结点是根为 T 的二叉排序树中第几 个最小元素。 【题目分析】 因为 T 是二叉排序树，则可利用二叉排序树的性质，从根往下查找结点 *x。若 T 的左子树为空，则其中序序号为 1，否则为 T-。设 T 的中序序号为 r，其左子女 p 的中序序号和右子女 q 的中序序号分别为 r+q-。 ， x) 在二叉排序树 T 上，求结点 x 的中序序号 - r=T-; r=1; 根结点的中序序号 ) -x- 到左子树去查找 T=T-) -r= r= - 到右子树去查找 T=T-) -r=r+T-; r=r+1; 课后答案网 r); 返回 *x 结点的中序序号 0); T 树上无 x 结点 结束算法 法 2：本题的另一种解法是设 r 是以 *x 为根的中序序号。初始时，若 x 的左子树为空， r=1;否则，r=x-。利用结点的双亲域，上溯至根 结点，即可求得 *x 的中序序号。 ， x) 在二叉排序树 T 上，求结点 x 的中序序号 if(x-r=x-; r=1; x 的这个序号是暂时的 p=x; p 要上溯至根结点 T，求出 *x 的中序序号 p!=T) if(p=p- p 是其双亲的右子女， if(p-r+; p 结点的双亲排在 p 结点的前面 r=r+p-; 双亲及左子树均排在 p 前面 p=p- r); 知某哈希表 装填因子小于 1，哈希函数 H(关键字的第一个字母在字母表中的序号。 (1) 处理冲突的方法为线性探测再散列。编写按第一个字母的顺序输出哈希表中所有关键字的算法。 (2) 处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。 【题目分析】 本题未直接给出哈希表表长，但已给出装填因子小于 1，且哈希函数 H(k)为关键字第一个字母在字母表中的序号，字母 A的序号为 1，表长可设为 n(n 27)，而链地址法中，表长 26。查找不成功是指碰到空指针为止 (另一种观点是空指针不计算比较次数 )。 (1)h)按关键字第一个字母在字母表中的顺序输出各关键字 i,j; i=1;i 26； i+) 哈希地址 1 到 26 j=1； n” ); hj!= 设哈希表初始值为 if(hj)=i) 取关键字第一字母在字母表中的序号 %s”， hj)； j=(j+1)% n； 2)h) 链地址解决冲突的哈希表查找不成功时平均查找长度 i,j; ; 记查找不成功的总的次数 p; i=1; j; ( 课后答案网 一个 100*100 的稀疏矩阵，其中 1%的元素为非零元素，现要求用哈希表作存储结构。 （ 1）请设计一个哈希表 （ 2）请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对算法所需时间和用一维数组 (每个分量存放一个非零元素的行值、列值和元素值 )作存储结构时存取元素的算法进行比较。 【题目分析】非零元素个数是 100，负载因子取 长 125 左右，取 p 为 127，散列地址为 0 到 126。哈希函数用 H(k)=(3*i+2*j) % 127， i， j 为行值和列值。 #m 127 i,j; v;m) 生成稀疏矩阵的哈希表，表中元素值初始化为 0 k=0； k100； k+) i,&j,& 设元素值为整型 h=(3*i+2*j)% m; 计算哈希地址 Th0