东北大学：《数据结构》课程教学资源（学习资料）第六章参考答案.doc_大学文库

第六章参考答案四、简答及应用作为静态查找表存储结构的顺序表的类型定义如下: # define maxsize静态查找表的表长 typedef struct i keytype key /*关键字* *其他域* S rec typedef struct i rec item[ maxsize+ 1 /*最后一个数据元素的下标* 9 stable 静态查找表中的数据元素存放在上述数组的第1到第n个单元中,第n+1到最后个单元为备用区,0或n+1单元被用于设置“岗哨”,以便简化査找运算的实现 2.一棵二叉排序树(又称二叉查找树)或者是一棵空树,或者是一棵同时满足下列条件的二叉树: ①若它的左子树不空,则左子树上所有结点的键值均小于它根结点键值。 ②若它的右子树不空,则右子树上所有结点的键值均大于它根结点键值 ③它的左、右子树也分别为二叉排序树 3.开散列表的组织方式如下:设选定的散列函数为H,H的值域(即散列地址的集合)为0..n-1。设置一个“地址向量” pointer HP[n]其中的每个指针HP订]指向个单链表用于存储所有散列地址为i的数据元素即所有散列地址为ⅱ的同义词。每一个样的单链表称为一个同义词子表。由地址向量以及向量中的每个指针所指的同义词子表构成存储结构称为开散列表。这种开散列解决冲突的方法又称“拉链法”。开散列表类型定义如下 type struct tagnode *next /*其他其他域* i' pinter, nod tyedef poiner openhah(n 4.闭散列表是一个一维数组,其元素的类型与动态查找表中数据元素的类型一致 # define maxsize闭散列表的容量 typedef struct /*其他域* typedef element closehash[ maxsize I 5.闭散列表是一个大小固定的一维数组,解决冲突的基本思想是在需要时为每个键值 K生成一个散列地址序列do,d1,…,d,…,dml。其中d=H(K)是K的散列地址:所有 d(0<<m)是后继散列地址。当插入K时,若位置do=H(K)上的结点已被别的数据元素占用, 则按上述地址序列依次探测,将找到的第一个空闲位置d作为K的存储位置。若所有后继散列地址都不空闲,说明该闭散列表已满(溢出)。相应地,查找或删除K时将按同样的后

1 第六章参考答案四、简答及应用 1．作为静态查找表存储结构的顺序表的类型定义如下： #define maxsize 静态查找表的表长 ; typedef struct { keytype key ; /* 关键字 */ …… /* 其他域 */ } rec ; typedef struct { rec item [ maxsize + 1 ] ; int n ; /* 最后一个数据元素的下标 */ } sqtable ; 静态查找表中的数据元素存放在上述数组的第 1 到第 n 个单元中，第 n+1 到最后一个单元为备用区，0 或 n+1 单元被用于设置“岗哨”，以便简化查找运算的实现。 2．一棵二叉排序树（又称二叉查找树）或者是一棵空树，或者是一棵同时满足下列条件的二叉树： ① 若它的左子树不空，则左子树上所有结点的键值均小于它根结点键值。; ② 若它的右子树不空，则右子树上所有结点的键值均大于它根结点键值。; ③ 它的左、右子树也分别为二叉排序树。 3．开散列表的组织方式如下：设选定的散列函数为 H ，H 的值域（即散列地址的集合）为 0．．n – 1。设置一个“地址向量”pointer HP[ n ],其中的每个指针 HP[ i ]指向个单链表用于存储所有散列地址为 i 的数据元素,即所有散列地址为 ii 的同义词。每一个样的单链表称为一个同义词子表。由地址向量以及向量中的每个指针所指的同义词子表构成存储结构称为开散列表。这种开散列解决冲突的方法又称“拉链法”。开散列表类型定义如下： typedef struct tagnode { keytype key ; struct tagnode *next ; ．．．．．． /*其他其他域*/ }*pinter,nod ; tyedef poiner openhah[n] ; 4．闭散列表是一个一维数组，其元素的类型与动态查找表中数据元素的类型一致： #define maxsize 闭散列表的容量 typedef struct { keytype key ; ．．．．．． /*其他域*/ } element ; typedef element closehash[ maxsize ] ; 5．闭散列表是一个大小固定的一维数组，解决冲突的基本思想是在需要时为每个键值 K 生成一个散列地址序列 d0，d1，…，di，…，dm-1。其中 d0=H(K)是 K 的散列地址；所有 di(0<i<m)是后继散列地址。当插入 K 时，若位置 d0=H(K)上的结点已被别的数据元素占用，则按上述地址序列依次探测，将找到的第一个空闲位置 di 作为 K 的存储位置。若所有后继散列地址都不空闲，说明该闭散列表已满（溢出）。相应地，查找或删除 K 时将按同样的后

继地址序列依次查找。査找成功时回送该位置或删除该位置上的数据元素(实际上是对该结点加以标记):查找不成功时回送一个特殊标志 6对地址单元d=H(K),如发生冲突,以d为中心在左右两边交替进行探测。按照二次探测法,键值K的散列地址序列为: do=h(K) d:=(do+12)mod m d2=(do-12)mod m d3=(do+ 2)mod m da=(do-2)mod m 7.此法要求设立多个散列函数H,i=1,…,k。当给定值K与闭散列表中的某个键值是相对于某个散列函数H的同义词因而发生冲突时,继续计算该给定值K在下一个散列函数H1+1下的散列地址,直到不再产生冲突为止。 8.散列表由两个一维数组组成。一个称为基本表,另一个称为溢出表。插入首先在基本表上进行;假如发生冲突,则将同义词存入溢出表。 9.假设长度为20的有序序列为(a,a,…,ao),按二分查找法得到的判定树如图简答题9所示。成功平均查找长度为:(1+2*2+3*4+4*8+5*5)/20=74/20=37 010203040506070809 1213141516 ①006087155188220465505508511 656670700766897908 ②00608715518220465505508511586656670700766897908 mid ③006087155188220465505508511586656670700766897908 low mid hig 11.分析:平衡二叉树AVL要求二叉树上任何一个结点的平衡因子为-1,0,1,如有个元素的平衡因子不是-1,0,1,此二叉树就不是平衡二叉树,必须通过调整把此二叉树变成平衡二叉树。平衡二叉树是二叉树排序树(对结点数结点相同的二叉树)平均查找次数最小的一种二叉树。答案见图简答题11(1)(2)所示。成功平均查找长度为:ASL=(1+2*2+3*4+4*4) /11=33/1=3 2.分析:开散列表上查找失败的平均査找次数的计算方法,是对每一种情况(即一个下标)计算查找失败次数的总和除以表的长度,即(3+1+2+2+1+4+3+3+1+2+1+1 +1+1)/14≈2 闭散列表查找失败的平均查找次数的计算方法,是对每一种情况(即每一个下标)计算查找失败次数的总和除以表的长度,即(5+4+3+2+1+9+8+7+6+5+4+3+2+1)/4=6014≈4 开散列表见图简答题12-1 闭散列表见图简答题12-2 012345678910111213 2

2 继地址序列依次查找。查找成功时回送该位置或删除该位置上的数据元素（实际上是对该结点加以标记）；查找不成功时回送一个特殊标志。 6.对地址单元 d = H ( K ) ,如发生冲突，以 d 为中心在左右两边交替进行探测。按照二次探测法，键值 K 的散列地址序列为： d0 = H ( K ) , d1 = (d0 + 12 ) mod m , d2 = (d0-1 2 ) mod m , d3 = (d0 + 22 ) mod m , d4 = (d0 - 2 2 ) mod m , …… 7．此法要求设立多个散列函数 Hi, i= 1 , …, k 。当给定值 K 与闭散列表中的某个键值是相对于某个散列函数 Hi 的同义词因而发生冲突时，继续计算该给定值 K 在下一个散列函数 Hi+1 下的散列地址，直到不再产生冲突为止。 8．散列表由两个一维数组组成。一个称为基本表，另一个称为溢出表。插入首先在基本表上进行；假如发生冲突，则将同义词存入溢出表。 9．假设长度为 20 的有序序列为（ a1 , a2 , … , a20 ）,按二分查找法得到的判定树如图简答题 9 所示。成功平均查找长度为：（ 1 + 2 * 2 + 3 * 4 + 4 * 8 + 5 * 5 ）/ 20= 74 /20 = 3.7 10． 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 ①006 087 155 188 220 465 505 508 511 586 656 670 700 766 897 908 ↑ ↑ ↑ low mid hig ②006 087 155 188 220 465 505 508 511 586 656 670 700 766 897 908 ↑ ↑ ↑ low mid hig ③006 087 155 188 220 465 505 508 511 586 656 670 700 766 897 908 ↑ ↑ ↑ low mid hig （成功） 11．分析：平衡二叉树 AVL 要求二叉树上任何一个结点的平衡因子为-1，0，1，如有一个元素的平衡因子不是-1，0，1，此二叉树就不是平衡二叉树，必须通过调整把此二叉树变成平衡二叉树。平衡二叉树是二叉树排序树（对结点数结点相同的二叉树）平均查找次数最小的一种二叉树。答案见图简答题 11（1）（2）所示。成功平均查找长度为：ASL=( 1 +2 * 2 + 3 * 4 + 4 * 4 ) / 11 = 33 /11 = 3 . 12．分析：开散列表上查找失败的平均查找次数的计算方法，是对每一种情况（即一个下标）计算查找失败次数的总和除以表的长度，即（3 + 1 + 2 + 2 + 1 + 4 + 3 + 3 + 1 + 2 + 1 +1 + 1 + 1 ）/ 14 ≈2。闭散列表查找失败的平均查找次数的计算方法，是对每一种情况（即每一个下标）计算查找失败次数的总和除以表的长度，即（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14 = 60/14≈4。开散列表见图简答题 12-1。闭散列表见图简答题 12-2。 0 1 2 3 4 5 6 7 8 9 10 11 12 13

3 Apr | Aug | Dec | Feb | | Jan |Mar | May | Jun | Jul | Sep | Oct | Nov | 1 2 1 1 1 1 2 4 5 2 5 6 图简答题 12-2 闭散列表开散列表上查找成功的平均查找长度： ASL =（1+2+1+1+1+2+3+1+2+1+2+1）/12 = 18/12 = 1.5 开散列表上查找不成功的平均查找长度： ASL =（3+1+2+2+1+4+3+3+1+2+1+1+1+1）/14 = 26/14≈2 闭散列表上查找成功的平均查找长度： ASL =（1+2+1+1+1+1+2+4+5+2+5+6）/12 = 31/12≈2.6 闭散列表上查找不成功的平均查找长度： ASL =（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14 = 60/14≈4 13．开散列表见图简答题 13。查找成功的平均查找长度为：（4*2+8）/ 12 = 4/3。 14．衡量算法的标准有很多，时间复杂度只是其中之一。尽管有些算法时间性能很好，但是其他方面可能就存在着不足。比如散列查找的时间性能很优越，但是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象，为了解决冲突，还得采用其他方法。二分查找也是有代价的，因为事先必须对整个查找区间进行排序，而排序也是费时的，所以常应用于频繁查找的场合。对于顺序查找，尽管效率不高，但却比较简单，常用于查找范围较小或偶而进行查找的情况。五、算法设计 1．分析：将岗哨设置在高下标端，表示从线性表低端查找时，在不成功的情况下，算法自动在岗哨处终止。另外，在等概率前提下，查找成功的平均查找长度等于每一个元素查找次数之和除以结点总数。 Int sqsearch0 (sqtable A,keytype X) /*数组有元素 n 个*/ { i=1; A.item[n+1].key=X; /*设置哨兵*/ while (A.item[n+1].key!=X) i++; return (i% (n+1)); /*找不到返回 0，找到返回其下标*/ } 查找成功平均查找长度为：（1+2+3+…+n）/ n =（1+n）/ 2。查找不成功平均查找长度为：n+1。 2．（1）int sqsearch1 (sqtable A,keytype X) /*数组有元素 n 个*/ { i=1; a.item[n+1].key!=X; /*设置哨兵*/ while (A.item[n+1].key!=X) i++; if ( (i!=1)&&(inext; q=head;

TNULL /*r是q的前趋,q是p的前趋* while(pl=NUL)&&(p-> datal=X)){r=q;q=pp=p->next}/搜索结点X*/ if(p!=head->next)&&(p!=NULL)) {q->next=p->next;p->next=qr→next=p,}/*交换q,p结点顺序* return(p) 3.分析:在等查区间的上、下界处设两个指针,由此计算出中间元素的序号,当中间元素大于给定值X时,接下来到其低端区间去查找:当中间元素小于给定值Ⅹ时,接下来到其高端区间去查找;当中间元素等于给定值Ⅹ时,表示查找成功,输出其序号 Int binlist(stable A, int s, t, keytype X) 体*、s分别为查找区间的上、下界* /*查找失败* switch( mid) case xA item(mid).key: return(a, mid+1, t, X) 在高端区间上递归* 4.分析:采用递归方法,从根结点开始查找结点p,若查询结点是所要找的结点,返回其深度h0。否则,到左、右子树上去找,查找深度加1 nt findI( birtreptr T, p, int h0 /在二叉树排序树T中查找结点p的层次,若不在时返回空值。h0为根结点T的层次 i if( p== null )return(0) /*没找到,返回0* /*找到* else if(p->datadata) return( find1(T- -lchild, p,ho)+1);/*到左子树去找* else return( findI(T-> rchild, p, h0)+ 1) /*到右子树去找* int find( birtrptr T,p) return( findI (t,p, 1)) 5.分析:根据题目要求分下面情况进行讨论 (1)若A为根结点,则A为公共祖先 (2)若A->datatata且T>data data,T为公共祖先: (3)若A->datadata且B->datadata或A>data>T>data且B->data>T>data, 则到T的左右子树去查找 bitreptr ANS(bitreptr T, A, B) /*T为二叉排序树的根结点* i if(t==NULL) return (NULL); /*不存在* else if((A->datadata)&&(T->datadata)ll /*T为公共祖先* (A->data==T->data))return(T) else if(A->data>T>data) return(ANS(T> schild,AB);/*到右子树上查找* else return(ANS(T->Child, A, B)) *到左子树上查找* 6.分析:对二叉排序树来讲,其中根遍历序列为一个递增有序序列。因此,对给定的二叉树进行中根遍历,如果始终能保证前一个值比后一个值小,则说明该二叉树是二叉排序树

4 r=NULL; /*r 是 q 的前趋，q 是 p 的前趋*/ while ((p!=NULLl)&&(p->data!=X)) {r=q;q=p;p=p->next;} /*搜索结点 X*/ if ((p!=head->next)&&(p!=NULL)) {q->next=p->next;p->next=q;r->next=p;} /*交换 q，p 结点顺序*/ return (p); 3．分析：在等查区间的上、下界处设两个指针，由此计算出中间元素的序号，当中间元素大于给定值 X 时，接下来到其低端区间去查找；当中间元素小于给定值 X 时，接下来到其高端区间去查找；当中间元素等于给定值 X 时，表示查找成功，输出其序号。 Int binlist (sqtable A,int s,t,keytype X) /*t、s 分别为查找区间的上、下界*/ { if(sA.item[mid].key: return(a,mid+1,t,X)); /*在高端区间上递归*/ } } } 4．分析：采用递归方法，从根结点开始查找结点 p，若查询结点是所要找的结点，返回其深度 h0。否则，到左、右子树上去找，查找深度加 1。 int find1 ( birtreptr T , p , int h0 ) /*在二叉树排序树 T 中查找结点 p 的层次，若不在时返回空值。h0 为根结点 T 的层次*/ { if ( p == NULL ) return ( 0 ) ; /* 没找到，返回 0 */ if( p ==T) return( h0 ) ; /* 找到 */ else if (p -> data data ) return( find1( T ->lchild,p,h0) +1) ; /* 到左子树去找 */ else return ( find1 ( T -> rchild,p,h0) + 1); /* 到右子树去找 */ } int find2( birtrptr T, p ) { return ( find1 ( T, p,1 ) ) ; } 5．分析：根据题目要求分下面情况进行讨论：（1）若 A 为根结点，则 A 为公共祖先；（2）若 A->datatata 且 T->datadata,T 为公共祖先；（3）若 A->datadata 且 B->datadata 或 A->data>T->data 且 B->data>T->data, 则到 T 的左右子树去查找。 bitreptr ANS (bitreptr T,A,B) /*T 为二叉排序树的根结点*/ { if (T==NULL) return (NULL); /*不存在*/ else if ((A->datadata)&&(T->datadata)|| /*T 为公共祖先*/ (A->data==T->data)) return (T); else if ((A->data>T->data) return (ANS(T->rchild,A,B)); /*到右子树上查找*/ else return (ANS(T->lchild,A,B)); /*到左子树上查找*/ } 6．分析：对二叉排序树来讲，其中根遍历序列为一个递增有序序列。因此，对给定的二叉树进行中根遍历，如果始终能保证前一个值比后一个值小，则说明该二叉树是二叉排序树

5 int bsbtr (bitreptr T) /*predt 记录当前结点前趋值，初值为-∞*/ { if (T==NULL) return(1); else {b1=bsbtr(T->lchild); /*判断左子树*/ if (!b1 || (predt>=T->data)) return(0); /*当前结点和前趋比较*/ predt=T->data; /*修改当前结点的前趋值*/ return(bsbtr(T->rchild)); /*判断右子树并返回最终结果*/ } } 7．分析：在二叉排序树上删除指定结点 p，首先要找到 p 的双亲结点 Pre。删除结点 p 又分三种情况（下面仅以 p 为其双亲左孩子举例）： ① 若 p 结点为叶子结点，只要令 pre->lchild=null 即可。 ② 若 p 结点只有一棵子树树，令其子树代替结点，即 pre->lchild=p->lchild 或 Pre->lchild=p->rchild。 ③ 若结点 p 的左子树和右子树均不空，做法是 p 的直接前趋（或直接后继）替代 p，然后再从二叉排序树中删除它的直接前趋（或直接后继）。 bitreptr srch_bstree (bitreptr pre, bitreptr bst, keytype k, int found) /*pre 为 bst 结点的双亲，k 为删除结点的关键字，found 为查找标志，若找到关键字为 k 的结点，则置 found 值为 1，找不到 found 值为 0*/ { if (bst==NULL) {found=0; return(p); } else if (bst->key==k) {found=1; return(pre); } else if (kkey) {pre=bst; return(srch_bstre(pre,bst->lchild,k,found)); }; else {pre=bst;return(srch_bstree(pre,bst->rchild,k,found)) }; } void del_bstree(bitreptr pre,bst,p) /*bst 为二叉树根结点，p 为删除结点，pre 为 p 的双亲结点，若 p 为根结点，则 Pre 为 Null*/ { k=p->key; found=0; pre=srch_bstree( pre,bst,k,found) if (found) switch{ case (p->lchild==NULL)&&(p->rchild==NULL): /*p 为叶结点*/ pre->lchild=NULL; free(p); break; case (p->lchild==NULL)&&(p->rchild!=NULL): /*p 有右孩子*/ pre->lchild=p->rchild; free(p); break; case (p->lchild!=NULL)&&(p->rchild==NULL): /*p 有左孩子*/ pre->lchild=p->lchild; free(p); break; case (p->lchild!=NULL)&&(p->rchild!=NULL): /*p 有左右孩子*/ { q=p; s=p->lchild; while (s->rchild!=NULL) {q=s;s=s->rchild;} /*找 p 的直接前趋*/ p->data=s->data /*p直接前趋的值传给p*/ if (q!=p) q->rchild=s->lchild; /*删除 p 直接前趋结点*/ else q->lchild=s->lchild; /*q=p 时，即为 p 的左孩子*/ free (s); }

/*end switch*/ else{/*p为双亲右孩子,类似p为双亲左孩子,略。*/ else printf((“没有找到结点P,删除结点有错误。”); 8.分析:显然,AVL树的插入算法应在二叉排序树插入算法的基础上扩充以下功能: ①判断插入结点之后是否平衡;②若是,寻找最小失衡子树并转③;③判断失衡类型并做相应调整。失衡的判断可以与寻找最小失衡子树结合起来,最小失衡子树的根结点一定是离插入结点最近,且插入之前平衡因子的绝对值为1的结点。AVL树插入算法的基本步骤如下 ①在寻找新结点的插入位置的过程中,记下离该位置最近,且平衡因子不等于零的结点a(此结点即为可能出现的最小失衡树的根) ②修改自该结点至插入位置路径上所有结点的平衡因子(注意:树上其他结点的平衡因子均不受插入的影响) ③判断实施插入操作之后,结a点的平衡因子的绝对值是否大于1(即判断是否失衡)。若是,进一步判断失衡类型并做相应调整;否则插入过程结束仍以二叉链表作为AVL树的存储结构。但每个结点需增加一个域用于存储平衡因子类型定义如下: typedef struct taganode i keytype key /*键值* 平衡因子域* struct taganode *lchild, *rchild; /*孩子指针域* 其他域* i anode, *avlpt 在此存储结构上,AVL树的插入算法如下: avlpt insert avltree(keytype K, avlpt T) is-malloc(size); S->key=K; S->Child=NULL; S->rchild=NULL; /*生成以K为键值的新结点* if (T==NULL) return(s) /查找s的插入位置,并记录a* f f-NULL; a=T; q =NULL while(p=NULL) f if(p->bf=0)(a=p f=ql /*a记录b=0的结点,其终值指向离插入位置最近的bf!=0的结点* q-P if(s->keykeykey)q->lchild=s 插入s* ifs>keykey)|p=a> Child;b=p,d=1;/s插入在a的左子树上,增量d为1*/ else (p=a->rchild; b=p: d=-1 /*s插入在a的右子树上,增量d为-1* while(pl=s) /*修改自a的孩子到s路径上结点的平衡因子* /*若s在p的左子树上* {p>bf=1;p=p-> lchild,}/"p的平衡因子加1。原来为0,因为p是a的子孙考

6 } /*end switch*/ else {/*p 为双亲右孩子，类似 p 为双亲左孩子，略。*/} else printf (“没有找到结点 P，删除结点有错误。”); } 8．分析：显然，AVL 树的插入算法应在二叉排序树插入算法的基础上扩充以下功能： ①判断插入结点之后是否平衡；②若是，寻找最小失衡子树并转③；③判断失衡类型并做相应调整。失衡的判断可以与寻找最小失衡子树结合起来，最小失衡子树的根结点一定是离插入结点最近，且插入之前平衡因子的绝对值为 1 的结点。AVL 树插入算法的基本步骤如下： ①在寻找新结点的插入位置的过程中，记下离该位置最近，且平衡因子不等于零的结点 a（此结点即为可能出现的最小失衡树的根）； ②修改自该结点至插入位置路径上所有结点的平衡因子（注意：树上其他结点的平衡因子均不受插入的影响）； ③判断实施插入操作之后，结 a 点的平衡因子的绝对值是否大于 1（即判断是否失衡）。若是，进一步判断失衡类型并做相应调整；否则插入过程结束。仍以二叉链表作为 AVL 树的存储结构。但每个结点需增加一个域用于存储平衡因子。类型定义如下： typedef struct taganode { keytype key; /*键值*/ int bf; /*平衡因子域*/ struct taganode *lchild, *rchild; /*孩子指针域*/ …… /*其他域*/ } anode, *avlpt; 在此存储结构上，AVL 树的插入算法如下： avlpt insert_avltree (keytype K, avlpt T) {s=malloc(size); s->key=K; s->lchild=NULL; s->rchild=NULL; /*生成以 K 为键值的新结点*/ if (T==NULL) return(s); /*查找 s 的插入位置，并记录 a*/ else { f=NULL; a=T; q=NULL; while (p!=NULL) { if (p->bf!=0) {a=p; f=q} /*a 记录 bf!=0 的结点，其终值指向离插入位置最近的 bf!=0 的结点*/ q=p; if (s->keykey) q->lchild=s; else p=p->rchild; } /*与 while 对应*/ if (s->keykey) q->lchild=s; else q->rchild=s; /*插入 s*/ if(s->keykey){p=a->lchild; b=p; d=1;}/*s 插入在 a 的左子树上，增量 d 为 1*/ else {p=a->rchild; b=p; d=-1;} /*s 插入在 a 的右子树上，增量 d 为-1*/ while (p!=s) /*修改自 a 的孩子到 s 路径上结点的平衡因子*/ if (s->keykey) /*若 s 在 p 的左子树上*/ {p->bf=1; p=p->lchild;}/*p 的平衡因子加 1。原来为 0，因为 p 是 a 的子孙*/

东北大学：《数据结构》课程教学资源（学习资料）第六章 参考答案

东北大学：《数据结构》课程教学资源（学习资料）第六章参考答案