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

1.现在有一个已排序的字典，请改写二分法检索算法，使之当排序码key在字典中重复出现时算法能找出第一个key出现的元素下标(用*position来保存)。保持算法时一般的二分法检索算法只要找出关键码key在字典中的一个下标。在比较的过程中，一旦发现相等，记录下当前下标mid就符合要求。程序如下：数据结构字典采用6.1.4节中的顺序表示法。二分法检索算法}改写后的算法想要找出关键码key在字典中第一次出现的下标。在比较中，如果遇到相(1)如果当前下标mid等于0,或者key与pdic->element[mid-1].key不等，那么mid一定是key第一次出现的下标，返回mid即可。(2)如果情形(1)不成立，那么mid一定大于等于key第一次出现的下标，需要在low和mid-1之间继续进行搜索，找出key第一次出现的下标。下面算法中，加粗的部分是对原算法的修改。修改后的二分法检索算法if(pdic->element[mid].key==key){}}代价分析该算法的时间复杂度为O(logn)。2.试编写一算法求出指定结点在给定的二叉排序树中所在的层数。【答】采用7.1.3节中字典的二叉排序树表示。if(p->key==pnode->key)if(p->key>pnode->key){}}代价分析3.试编写一算法在给定的二叉排序树上找出任意两个不同结点最近的公共祖先(若在两结点A,B中，A是B的祖先，则认为A,B最近的公共祖先就是A)。数据结构同上题4.设计一个有效的算法，在1000个无序的元素中，挑选出其中前5个最大的元素。数据结构typedefintKeyType;typedefstruct/*记录的其它字段*/typedefstruct这里不需要整体排序，故选择一种能较快得出最终排序段的前一部分的算法改造即可，如直接选择排序，起泡排序，堆排序都能最先得出前5个最大元素。综合考虑算法的时间代价，选择直接选择排序算法改造即可。算法函数返回一个数组，数组中存着挑出的元素，为动态分配的。returnNULL;}{returnNULL;{}}代价分析0(n*m)(设从n个元素中选出m个最大元素)。5.写一个算法来判断对给定有向图中的指定顶点是否至少存在一条有向边指向它。【答】图有三种表示方法：出边表(邻接表的一种),入边表(邻接表的一种)和邻接矩阵。相应的有三种算法。设n为顶点数，m为边数。对于出边表，顺次搜索一遍边即可，时间代价为O(m)。对于入边表，判断指定顶点的边表头指针是否非空即可，时间代价为0(1)。对于邻接矩阵，搜索矩阵中指定顶点对应的列，判断其中是否有非0元即可，时间代价以出边表为例，给出一个算法如下。数据结构采用9.1.3节中有向图的邻接表(出边表)表示法。p=g.vexs[i].edgelist}代价分析该算法的时间复杂度为0(m)。6.设计一个算法，确定(无权)图中每一对结点之间的可达关系。【答】数据结构采用图的邻接矩阵表示法。这里介绍Warshall算法，该算法解决了(无权)图的可达性问题。算法用到了一个矩阵a(a作为算法的参数之一)。开始时，对矩阵a中元素赋值，使a与图的邻接矩阵相等。这样，矩阵a记录的就是所有直接的边连接。算法的核心部分是一个三重循环。其中外重循环的循环次数为n,每次循环更新a中的元素。循环一次后，a中记录的就是所有直接连接或者只经由结点0而形成的通路的情况。循环k(1≤k≤n)次后，a中记录的就是所有至多只经由结点0,1,..,k-1而形成的通路的情况。这样，算法结束时，矩阵a中记录的就是每一对结点之间的可达性信息。a[j[]为1,表示从结点i到结点j是可达的；为0,则表示不可达。代价分析算法的核心部分是一个三重循环,每重的循环次数为n,因此该算法的时间代价为O(n³)。调试结果该示例程序计算下图的可达性：运行结果如下：000001010000000111011110000、00,00【下载