算法与数据结构C语言习题参考答案-9章.doc

《算法与数据结构C语言习题参考答案-9章.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1.现在有一个已排序的字典，请改写二分法检索算法，使之当排序码key在字典中重复出现时算法能找出第一个key出现的元素下标（用*position来保存）。保持算法时间代价为O(logn)。【答】思路一般的二分法检索算法只要找出关键码key在字典中的一个下标。在比较的过程中，一旦发现相等，记录下当前下标mid就符合要求。程序如下：数据结构字典采用6.1.4节中的顺序表示法。typedefintKeyType;typedefintDataType;二分法检索算法intbinarySearch(SeqDi

2、ctionary*pdic,KeyTypekey,int*position){intlow,mid,high;low=0;high=pdic->n-1;while(low<=high){mid=(low+high)/2;if(pdic->element[mid].key==key){*position=mid;returnTRUE;}elseif(pdic->element[mid].key>key)high=mid-1;elselow=mid+1;}*position=low;returnFALS

3、E;}改写后的算法想要找出关键码key在字典中第一次出现的下标。在比较中，如果遇到相等（key与pdic->element[mid].key相等），则需要分情形讨论。（1）如果当前下标mid等于0，或者key与pdic->element[mid-1].key不等，那么mid一定是key第一次出现的下标，返回mid即可。（2）如果情形（1）不成立，那么mid一定大于等于key第一次出现的下标，需要在low和mid-1之间继续进行搜索，找出key第一次出现的下标。下面算法中，加粗的部分是对原算法的修改。

4、修改后的二分法检索算法intbinarySearch1(SeqDictionary*pdic,KeyTypekey,int*position){/*算法结束后，*position存放key第一次出现的下标*/intlow,mid,high;low=0;high=pdic->n-1;最新可编辑word文档while(low<=high){mid=(low+high)/2;if(pdic->element[mid].key==key){if(mid==0

5、

6、key!=pdic->element[mid-

7、1].key){*position=mid;returnTRUE;}/*此时mid就是key在字典中第一次出现的下标*/elsehigh=mid-1;/*在左半段继续搜索*/}elseif(pdic->element[mid].key>key)high=mid-1;elselow=mid+1;}*position=low;returnFALSE;}代价分析该算法的时间复杂度为O(logn)。2.试编写一算法求出指定结点在给定的二叉排序树中所在的层数。【答】数据结构采用7.1.3节中字典的二叉排序树表

8、示。算法intsearch_layer(PBinTreepbtree,PBinTreeNodepnode){/*返回二叉排序树*pbtree中结点*pnode所在层数，要求所给结点在树中*/intlayer=0;PBinTreeNodep=*pbtree;while(p!=NULL){if(p->key==pnode->key)returnlayer;/*查找结点成功，返回层数*/if(p->key>pnode->key){p=p->llink;/*进入左子树继续查找*/layer++;}else{

9、p=p->rlink;/*进入右子树继续查找*/layer++;}}return-1;/*查找结点失败*/}最新可编辑word文档代价分析假设二叉排序树有n个结点，高度是h(n<=h<=n)，算法执行的时间代价最坏为O(h)。A注意根结点为零层。3.试编写一算法在给定的二叉排序树上找出任意两个不同结点最近的公共祖先(若在两结点A，B中，A是B的祖先，则认为A，B最近的公共祖先就是A)。数据结构同上题算法intFindLowestCommonAncestor(pBinSearchNoderoot,in

10、tvalue1,intvalue2){pBinSearchNodecurnode=root;while(1){if(curnode->key>value1&&curnode->key>value2)curnode=curnode->llink;elseif(curnode->keykeyrlink;elsereturncurnode->key;}}4.设计一个有效的算法，在1000个