算法设计与分析算题.doc

《算法设计与分析》排序和查找是经常遇到的问题。按照要求完成以下各题:(1)对数组A={15,29,135,18,32,1,27,25,5},用快速排序方法将其排成递减序。解:(1)第一步:15291351832127255第二步:29135183227251515第三步:13532291827251551第四步:13532292725181551(2)请描述递减数组进行二分搜索的基本思想,并给出非递归算法。解:基本思想:首先将待搜索元素v与数组的中间元素进行比较,如果,则在前半部分元素中搜索v;若,则搜索成功;否则在后半部分数组中搜索v。非递归算法:输入:递减数组A[left:right],待搜索元素v。输出:v在A中的位置pos,或者不在A中的消息(-1)。步骤:intBinarySearch(intA[],intleft,intright,intv){ intmid; while(left<=right) { mid=int((left+right)/2); if(v==A[mid])returnmid; elseif(v>A[mid])right=mid-1; elseleft=mid+1; } return-1; }(3)给出上述算法的递归算法。解:输入:递减数组A[left:right],待搜索元素v。输出:v在A中的位置pos,或者不在A中的消息(-1)。步骤:【3分】intBinarySearch(intA[],intleft,intright,intv){ intmid; if(left<=right) { mid=int((left+right)/2); if(v==A[mid])returnmid; elseif(v>A[mid])returnBinarySearch(A,left,mid-1,v); elsereturnBinarySearch(A,mid+1,right,v); } else return-1; }(4)使用上述算法对(1)所得到的结果搜索如下元素,并给出搜索过程:18,31,135。解:搜索18:首先与27比较,18<27,在后半部分搜索;再次与18比较,搜索到,返回5。搜索31:首先与27比较,31>27,在前半部分搜索;再次32比较,31<32,在后半部分搜索,与29比较,31>29,此时只有一个元素,未找到,返回-1。搜索135:首先与27比较,135>27,在前半部分搜索;再次32比较,135>32,在前半部分搜索;与135比较,相同,返回0。二、排序和查找是常用的计算机算法。按照要求完成以下各题:(1)对数组A={15,9,115,118,3,90,27,25,5},使用合并排序方法将其排成递减序。(2)若改变二分搜索法为三分搜索法,即从一个递减序列A中寻找元素Z,先与元素比较,若,则在前面个元素中寻找Z;否则与比较,总之使余下的序列为个元素。给出该方法的伪代码描述。(3)使用上述算法对(1)所得到的结果搜索如下元素,并给出搜索过程:118,31,25。解:(1)第一步:159115********** 第二步:159118********** 第三步:118115********** 第四步:11811590272515935 第五步:11811590272515953(2)输入:递减数组A[left:right],待搜索元素v。输出:v在A中的位置pos,或者不在A中的消息(-1)。步骤:intBinarySearch(intA[],intleft,intright,intv){ intmid; while(left<=right) { first=left+(right-left+1)/3; second=left+(right-left+1)/3*2; if(v==A[first])returnfirst; elseif(v>A[first])right=first-1; elseif(v==A[second])returnsecond; elseif(v>A[second]){left=first+1;right=second-1;} elseleft=second+1; } return-1; }搜索118:118>27,所以right=3;118>115,所以right=1;118=118,找到。搜索31:31>27,所以right=3;31<90,所以left=4,结束,未找到。搜索25:9<25<27,所以left=5,right=6;25=25,找到。三、Dijkstra算法求单源最短路径d[u]:s到u的距离p[u]:记录前一节点信息Init-single-source(G,s)foreachvertexv∈V[G]do{d[v]=∞;p[v]=N