备选算法试题参考解答--算法设计与分析教研室

《备选算法试题参考解答--算法设计与分析教研室》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1给出一个的算法解：假设A中元素个数为n,B中元素个数为m.1.算法思想：输入两个序列A、Ba.分别对A、B进行归并排序b.同时扫描A、B,设两个指针分别指向A、B的当前扫描元素。初始时i、j分别指向A[0]、B[0]c.若A[i]B[j]则将B[j]存入C中，j后移若A[i]=B[j]则同时将i、j后移，直到分别出现与其前一个元素值不同的元素为止。d重复c直至A、B同时扫描完或某一个扫描完，此时将另一个序列所有剩余元素直接插入C中即可。归并排序的时间复杂度为,扫描的时间复杂度为，总的时间复杂度为。2书后习题4.8a.Howman

2、ykeycomparisonswouldbedoneintheworstcase?b.Howmanytimesareelementsmovedintheworstcase?c.Whatistheasymptoticorderoftheworst-caserunningtime?d.Canthenumberofmovesbereducedbyputtingtheelementsinalinkedlistinsteadofanarray?Explain.答案：a.；b.i+2次;c.d.采用链式存储结构可以减少移动次数，但这种结构不能使用折半查找。3输入n个元素，输出其不同元素。（O

3、(nlogn)）答案：n个元素保存在数组E[n]中；(1)对E[n]进行排序(归并等时间复杂度为的算法);(2)直接输出E[0];(3)FORi=1TOn-1,如果(E[i]==E[i-1])忽略该元素;否则输出E[i]。4给出最坏情况下，只需7次比较的5个元素的排序算法答：假设5个元素为a1，a2，a3，a4，a51.对a1,a2,a3,a4进行3次比较若a3>a4,a3和a4对换；若a1>a2,a1和a2对换；若a2>a4,a2和a4对换且a1和a3对换.生成序列为2.将a5插入以上序列（用折半查找思想，共需2次比较）结果可能为：3.将a3插入到以上四种可能，用折半查找，最多

4、需要2次比较由1、2、3得，此方法只需7次比较。5输入n个元素，输出其和为m的全部整数对。答：首先对n个元素按升序排序，对排好序元素设置首尾两个指针low,high,当lowm,high—当Low==high时，程序结束。6输入n个元素，输出其包含的最长等差数列。定义三元组，其中i、j为元素标号且i

5、存最长等差数列的值。(1)将输入的n个元素按照升序排序，对于所有，构造以上定义的三元组。(2)将三元组按照d值升序排序，具有相同d值的三元组，再依次按照i、j的值升序排序，得到有序的三元组数组E[K](K为所有三元组的个数)。由于三元组中，d、i、j的取值范围可知，分别为，所以排序时可以使用基数排序。(1)对于所有具有相同公差d的三元组{}，查找“最长链”，就可以找到公差为d的最长的等差数列，长度为。具体方法如下：e_start，e_end分别记录具有同一公差的三元组在E[K]中的起始、终止位置，初始e_start=1，e_end=-1。顺序遍历有序的三元组数组E[K]中每一个三

6、元组，其中t从2开始如果且，那么继续遍历下一个三元组；否则，如果置e_end=t-1；如果置e_end=t；并对E[K]中标号从e_start到e_end的三元组执行找“最长链”的操作，找出的最长链长度为，如果，则并将保存到result中。之后，置e_start=t。查找中“最长链”方法如下：数组next[n]，next[i]初始值为-1，最终记录元素i应该链接的下一个元素的标号；数组label[n]，label[i]初始为false，记录每一个元素是否已经被访问过。顺序遍历E[k][]中的每一个元组，如果为-1，则；否则，继续遍历下一个三元组。从当前未被遍历的最小下标s开始遍历

7、，直到所有元素都被遍历过，执行操作：如果next[s]是-1，那么label[s]=true，记录下整数对(s,1)；否则执行start=s,counter=1；执行操作label[s]=true，s=next[s]，counter++，直到next[s]是-1为止；记录下整数对(start,counter)。综上，counter值最大的整数对中的start值，就是中最长的等差数列的起始位置，对应的最长链为，其中next[end]=-1。7.归并排序的优点及优化措施.答:基于比较