《算法与数据结构(9-11章)》由会员分享，可在线阅读，更多相关《算法与数据结构(9-11章)（31页珍藏版）》请在金锄头文库上搜索。
1、第第 9 章章 集合集合一、基础知识题一、基础知识题9.1 若对长度均为 n 的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别 讨论二者在等概率情况下平均查找长度是否相同？ （1）查找不成功，即表中没有和关键字 K 相等的记录； （2）查找成功，且表中只有一个和关键字 K 相等的记录； （3）查找成功，且表中有多个和关键字 K 相等的记录，要求计算有多少个和关键字 K 相等的记录。 【解答】 （1）平均查找长度不相同。前者在 n+1 个位置均可能失败，后者失败时的查找长度都是 n+1。 （2）平均查找长度相同。在 n 个位置上均可能成功。 （3）平均查找长度不相同。前者在某
2、个位置上(1datarchild; f 是 p 的双亲else if(p-dataAi) f=p;p=p-lchild; s=(BSTree)malloc(sizeof (BiNode); 申请结点空间s-data=Ai; s-lchild=null; s-rchild=null;if(f=null) T=s; 根结点else if(s-datadata) f-lchild=s; 左子女else f-rchild=s; 右子树根结点的值大于等于根结点的值 算法结束 9.28 编写删除二叉排序树中值是 X 的结点的算法。要求删除结点后仍然是二叉排序树，并且高度没 有增长。 【题目分析】在二叉排序
3、树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接 将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点 代替该结点，从而不增加树的高度。void Delete(BSTree bst, keytype X) 在二叉排序树 bst 上，删除其关键字为 X 的结点 BSTree f,p=bst;while(p p=p-lchild; else f=p; p=p-rchild; if(p=null) printf(“无关键字为 X 的结点n”); exit(0); if (p-lchild=null) 被删结点无左子树if(f-lchild
4、=p) f-lchild=p-rchild; 将被删结点的右子树接到其双亲上else f-rchild=p-rchild;else q=p; s=p-lchild; 被删结点有左子树while(s-rchild !=null) 查左子树中最右下的结点(中序最后结点) q=s; s=s-rchild; p-key=s-key; 结点值用其左子树最右下的结点的值代替if(q=p) p-lchild=s-lchild; 被删结点左子树的根结点无右子女else q-rchild=s-lchild; s 是被删结点左子树中序序列最后一个结点free(s);else 算法结束 9.29 假设二叉排序树的各
5、个元素值均不相同，设计一个递归算法按递减次序打印各元素的值。 【题目分析】按着“右子树根结点左子树”遍历二叉排序树，并输出结点的值。void InOrder(BSTree bt) 按递减次序输出二叉排序树结点的值 BiTree s,p=bt; s 是元素为二叉树结点指针的栈，容量足够大 int top=0; while(p | top0) while(p) s+top=p; bt=p-rchild; 沿右子树向下if(top0) p=stop-; printf(p-data); p=p-lchild; 结束 以下是递归输出，算法思想是一样的。void InvertOrder(BSTree bt
6、)按递减次序输出二叉排序树结点的值 BiTree p=bt; if(p) InOrder(bt-rchild); 中序遍历右子树printf(p-data); 访问根结点InOrder(bt-lchild); 中序遍历左子树if结束 9.30 设记录 R1，R2，Rn 按关键字值从小到大顺序存储在数组 r1.n中，在 rn+1处设立一个监 视哨，其关键字值为+; 试写一查找给定关键字 k 的算法;并画出此查找过程的判定树，求出在等概率情 况下查找成功时的平均查找长度。int Search(rectype r，int n，keytype k) 在 n 个关键字从小到大排列的顺序表中，查找关键字为
7、 k 的结点 rn+1.key=MAXINT; 在高端设置监视哨 i=1;while(ri.keydata!=X) 查找值为 X 的结点，f 指向当前结点的双亲f=p;if(p-datarlink; else p=p-llink; if(!p) 无值为 x 的结点，插入之p=(BiTNode *)malloc(sizeof (BiTNode);p-data=X; p-llink=null; p-rlink=null;if(t=null) t=p; 若初始为空树，则插入结点为根结点 else if(f-dataX) f-llink=p; else f-rlink=p; else p-count+
8、; 查询成功，值域为 X 的结点的 count 增 1 Search_InsertX 9.32 假设一棵平衡二叉树的每个结点都标明了平衡因子 b，试设计一个算法，求平衡二叉树的高度。 【题目分析】 因为二叉树各结点已标明了平衡因子 b，故从根结点开始记树的层次。根结点的层次为 1， 每下一层，层次加 1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子 b 为 0 时， 任选左、右一分枝向下查找，若 b 不为 0，则沿左(当 b=1 时)或右(当 b=-1 时)子树向下查找。int Height(AVLTree t) 求平衡二叉树 t 的高度level=0; p=t; whil
9、e(p)level+; 树的高度增 1 if(p-bfrchild; bf=-1 沿右分枝向下else p=p-lchild; bf=0 沿左分枝向下 whilereturn (level); 平衡二叉树的高度 算法结束 9.33 设二叉排序树的存储结构为：typedef struct nodeElemType key; int size:int; struct node *lchild， *rchild，*parents;node，*BiTree; 一个结点*x 的 size 域的值是以该结点为根的子树中结点的总数（包括*x 本身） 。例如，下图中 x 所指结点 的 size 值为 4。设树
10、高为 h，试写一时间为 O(h)的算法 Rank(BiTree T，node *x)返回 x 所指结点在二叉排 序树 T 的中序序列里的排序序号，即：求 x结点是根为 T 的二叉排序树中第几个最小元素。 【题目分析】 因为 T 是二叉排序树，则可利用二叉排序树的性质，从根往下查找结点*x。若 T 的左子树 为空，则其中序序号为 1，否则为 T-lchild-size+1。设 T 的中序序号为 r，其左子女 p 的中序序号和右子 女 q 的中序序号分别为 r-p-rchild-size-1 和 r+q-lchild-size+1。 int Rank(tree T，node *x) 在二叉排序树
11、T 上，求结点 x 的中序序号if(T-lchild) r=T-lchild-size+1; else r=1; 根结点的中序序号while(T)if(T-keyx-key) 到左子树去查找T=T-lchild; if(T) if(T-rchild) r=r-T-rchild-size-1; else r=r-1; else if(T-keykey) 到右子树去查找T=T-rchild;if(T)if(T-lchild)r=r+T-lchild-size+1; else r=r+1; else return (r); 返回*x 结点的中序序号return (0); T 树上无 x 结点结束算法
12、 Rank算法 2：本题的另一种解法是设 r 是以*x 为根的中序序号。初始时，若 x 的左子树为空，r=1;否则， r=x-lchild-size+1。利用结点的双亲域，上溯至根结点，即可求得*x 的中序序号。 int Rank(tree T，node *x) 在二叉排序树 T 上，求结点 x 的中序序号if(x-lchild)r=x-lchild-size+1; else r=1; x 的这个序号是暂时的p=x; p 要上溯至根结点 T，求出*x 的中序序号while(p!=T)if(p=p-parents-rchild) p 是其双亲的右子女，if(p-parents-lchild=nu
13、ll) r+; p 结点的双亲排在 p 结点的前面else r=r+p-parent-lchild-size+1; 双亲及左子树均排在 p 前面p=p-parents;while return (r);Rank 9.34 已知某哈希表 HT 的装填因子小于 1，哈希函数 H(key)为关键字的第一个字母在字母表中的序号。(1) 处理冲突的方法为线性探测再散列。编写按第一个字母的顺序输出哈希表中所有关键字的算法。 (2) 处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。 【题目分析】 本题未直接给出哈希表表长，但已给出装填因子小于 1，且哈希函数 H(k)为关
14、键字第一个 字母在字母表中的序号，字母A的序号为 1，表长可设为 n(n27)，而链地址法中，表长 26。查找不 成功是指碰到空指针为止(另一种观点是空指针不计算比较次数)。(1)void Print(rectype h)按关键字第一个字母在字母表中的顺序输出各关键字int i,j;for(i=1;i26；i+) 哈希地址 1 到 26j=1；printf(“n”);while(hj!=null) 设哈希表初始值为 nullif(ord(hj)=i) ord()取关键字第一字母在字母表中的序号printf(“%s” ，hj)； j=(j+1)% n；while for end (2)int ASLHash(rectype h) 链地址解决冲突的哈希表查找不成功时平均查找长度int i,j; count=0; 记查找不成功的总的次数 LinkedList p; for(i=1;inext; count+=j;return (count/26.0);9.35 有一个 100*100 的稀疏矩阵，其中 1%的元素为非零元素，现要求用哈希表作存储结构。 （1）请设计一个哈希表 （2）请写一个对你所设计的哈希表中
