算法导论第二章答案

算法导论答案算法导论概述《算法导论》是一本经典的计算机科学教材，由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein合著。

这本书详细介绍了算法的设计、分析和实现，并涵盖了算法导论领域的许多重要概念和技术。

本文将为你提供一些关于《算法导论》中一些常见问题的答案。

1. 什么是算法？算法是一系列明确定义的步骤，用于解决特定问题或完成特定任务。

它可以是一个计算过程、一个程序或一个有限的操作序列。

算法通常用于计算和数据处理领域，是计算机科学的核心概念。

2. 为什么学习算法很重要？学习算法的重要性体现在以下几个方面：•提高问题解决能力：算法是解决问题的有效工具。

学习算法可以帮助我们思考和理解问题，并设计出相应的解决方案。

•优化计算性能：算法的设计和分析可以帮助我们提高计算的效率和性能。

合适的算法可以在短时间内处理大规模数据集和复杂计算任务。

•促进技术创新：算法是许多技术和应用的基石，包括人工智能、机器学习、数据挖掘等。

学习算法可以为我们打开更多的研究和创新机会。

3. 《算法导论》提供了哪些内容？《算法导论》这本书详细介绍了算法的基本概念和设计技巧，并提供了许多典型算法的实现和分析。

以下是该书的一些主要内容：•算法分析：对算法进行时间复杂度和空间复杂度的理论分析，帮助我们评估算法的效率和性能。

•排序和查找算法：介绍了各种排序算法（如插入排序、归并排序、快速排序）和查找算法（如二分查找、哈希表）。

•图算法：讨论了图的表示方法和图搜索算法（如深度优先搜索、广度优先搜索）以及最短路径算法（如Dijkstra算法）等。

•动态规划和贪心算法：介绍了动态规划和贪心算法的原理和应用，用于解决具有最优子结构性质的问题。

•分治算法和递归思想：讲解了分治算法的基本原理，并提供了许多使用递归思想解决问题的例子。

•NP完全问题：探讨了NP完全问题的性质和求解方法，引导了读者进入计算复杂性理论的领域。

Chapter2 Getting Start2.1 Insertion sort2.1.2 将Insertion-Sort 重写为按非递减顺序排序2.1.3 计算两个n 位的二进制数组之和2.2 Analyzing algorithms2.2.1将函数32/10001001003n n n --+用符号Θ表示2.2.2写出选择排序算法selection-sort当前n-1个元素排好序后，第n 个元素已经是最大的元素了.最好时间和最坏时间均为2()n Θ2.3 Designing algorithms2.3.3 计算递归方程的解22()2(/2)2,1k if n T n T n n if n for k =⎧=⎨+ = >⎩ （1） 当1k =时，2n =，显然有()lg T n n n =（2） 假设当k i =时公式成立，即()lg 2lg22i i i T n n n i ===⋅，则当1k i =+，即12i n +=时，111111()(2)2(2)222(1)22lg(2)lg i i i i i i i i T n T T i i n n ++++++==+=⋅+=+== ()lg T n n n ∴ =2.3.4 给出insertion sort 的递归版本的递归式(1)1()(1)()1if n T n T n n if n Θ =⎧=⎨-+Θ >⎩2.3-6 使用二分查找来替代insertion-sort 中while 循环内的线性扫描，是否可以将算法的时间提高到(lg )n n Θ？虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是2()n Θ2.3-7 给出一个算法，使得其能在(lg )n n Θ的时间内找出在一个n 元素的整数数组内，是否存在两个元素之和为x首先利用快速排序将数组排序，时间(lg )n n Θ，然后再进行查找： Search(A,n,x)QuickSort(A,n);i←1; j←n;while A[i]+A[j]≠x and i<jif A[i]+A[j]<xi←i+1elsej←j -1if A[i]+A[j]=xreturn trueelsereturn false时间复杂度为)(n Θ。

算法导论参考答案算法导论参考答案算法导论是计算机科学领域中一本经典的教材，被广泛应用于计算机科学和工程的教学和研究中。

它涵盖了算法设计和分析的基本概念，以及各种常见算法的实现和应用。

本文将为读者提供一些算法导论中常见问题的参考答案，以帮助读者更好地理解和掌握这门课程。

1. 什么是算法？算法是一系列解决问题的步骤和规则。

它描述了如何将输入转换为输出，并在有限的时间内完成。

算法应具备正确性、可读性、健壮性和高效性等特点。

2. 如何分析算法的效率？算法的效率可以通过时间复杂度和空间复杂度来衡量。

时间复杂度表示算法执行所需的时间量级，常用的时间复杂度有O(1)、O(n)、O(logn)、O(nlogn)和O(n^2)等。

空间复杂度表示算法执行所需的额外空间量级，通常以字节为单位。

3. 什么是渐进符号？渐进符号用于表示算法的时间复杂度或空间复杂度的增长趋势。

常见的渐进符号有大O符号、Ω符号和Θ符号。

大O符号表示算法的上界，Ω符号表示算法的下界，Θ符号表示算法的平均情况。

4. 什么是分治法？分治法是一种算法设计策略，将问题分解为若干个子问题，并对子问题进行独立求解，最后将子问题的解合并得到原问题的解。

典型的分治算法有归并排序和快速排序。

5. 什么是动态规划？动态规划是一种通过将问题分解为相互重叠的子问题来求解的方法。

它通常用于求解具有重叠子问题和最优子结构性质的问题。

典型的动态规划算法有背包问题和最短路径问题。

6. 什么是贪心算法？贪心算法是一种通过每一步选择局部最优解来求解整体最优解的方法。

贪心算法通常不能保证得到全局最优解，但在某些问题上能够得到近似最优解。

典型的贪心算法有霍夫曼编码和最小生成树算法。

7. 什么是图算法？图算法是一类用于解决图结构相关问题的算法。

图由节点和边组成，节点表示对象，边表示对象之间的关系。

图算法包括图的遍历、最短路径、最小生成树和网络流等问题的求解。

8. 什么是NP完全问题？NP完全问题是一类在多项式时间内无法求解的问题。

算法导论答案第一章：算法概述啊算法的定义算法是一系列解决问题的明确指令。

它是一个有穷步骤集，其中每个步骤或操作由确定性和可行性特征。

算法是通过将预期的输入转换为输出来解决问题的工具。

第二章：插入排序插入排序的思想插入排序是一种简单直观的排序算法，其基本思想是将待排序的序列分为已排序和未排序两部分，每次从未排序的部分中取出一个元素，并将其插入到已排序部分的正确位置，直到所有元素都被排序。

插入排序的算法实现以下是插入排序的伪代码：INSERTION-SORT(A)for j = 2 to A.lengthkey = A[j]// Insert A[j] into the sorted sequence A[1.. j-1].i = j - 1while i > 0 and A[i] > keyA[i + 1] = A[i]i = i - 1A[i + 1] = key插入排序的时间复杂度插入排序的时间复杂度为O(n^2)，其中n是排序的元素个数。

虽然插入排序的最坏情况下的复杂度很高，但是对于小规模的数据集，插入排序是一种较快的排序算法。

第三章：分治策略分治策略的基本思想分治策略是一种解决问题的思想，它将问题的规模不断缩小，直到问题足够小而可以直接解决。

然后将子问题的解合并起来，得到原问题的解。

分治策略的应用实例一种经典的应用分治策略的算法是归并排序。

归并排序将待排序的序列划分为两个子序列，分别排序后再将两个有序子序列合并为一个有序序列。

以下是归并排序的伪代码：MERGE-SORT(A, p, r)if p < rq = floor((p + r) / 2)MERGE-SORT(A, p, q)MERGE-SORT(A, q + 1, r)MERGE(A, p, q, r)MERGE(A, p, q, r)n1 = q - p + 1n2 = r - qlet L[1..n1+1] and R[1..n2+1] be new arraysfor i = 1 to n1L[i] = A[p + i - 1]for j = 1 to n2R[j] = A[q + j]L[n1 + 1] = infinityR[n2 + 1] = infinityi = 1j = 1for k = p to rif L[i] <= R[j]A[k] = L[i]i = i + 1elseA[k] = R[j]j = j + 1分治策略的时间复杂度归并排序的时间复杂度为O(nlogn)，其中n是待排序序列的长度。

第二章算法入门由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。

另，思考题2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供个意见。

给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。

插入排序算法伪代码INSERTION-SORT(A)1 for j ←2 to length[A]2 do key ←A[j]3 Insert A[j] into the sorted sequence A[1..j-1]4 i ←j-15 while i > 0 and A[i] > key6 do A[i+1]←A[i]7 i ←i − 18 A[i+1]←keyC#对揑入排序算法的实现:public static void InsertionSort<T>(T[] Input) where T:IComparable<T>{T key;int i;for (int j = 1; j < Input.Length; j++){key = Input[j];i = j - 1;for (; i >= 0 && Input[i].CompareTo(key)>0;i-- )Input[i + 1] = Input[i];Input[i+1]=key;}}揑入算法的设计使用的是增量（incremental）方法：在排好子数组A[1..j-1]后，将元素A[ j]揑入，形成排好序的子数组A[1..j]这里需要注意的是由于大部分编程语言的数组都是从0开始算起，这个不伪代码认为的数组的数是第1个有所丌同，一般要注意有几个关键值要比伪代码的小1.如果按照大部分计算机编程语言的思路，修改为：INSERTION-SORT(A)1 for j ← 1 to length[A]2 do key ←A[j]3 i ←j-14 while i ≥ 0 and A[i] > key5 do A[i+1]←A[i]6 i ←i − 17 A[i+1]←key循环丌变式(Loop Invariant)是证明算法正确性的一个重要工具。

Introduction to Algorithm s Day 10 Massachusetts Institute of Technology 6.046J/18.410J Singapore-MIT Alliance SMA5503 Professors Erik Demaine,Lee Wee Sun,and Charles E.Leiserson Handout12Exercise2-1.Do Exercise5.3-1on page104of CLRS.Solution:R ANDOMIZE-I N-P LACEExchangefor todo ExchangeFor our base case,we have initialized to2.Therefore we must show that for each possible1-permutation,the subarray A[1]contains this1-permutation with probability. Clearly this is the case,as each element has a chance of of being in thefirst position.Exercise2-2.Do Exercise6.1-2on page129of CLRS.Solution:By definition,a element heap has a height of.Therefore where is and our base case is correct.Now we use induction,and assume that all trees with nodes or fewer has a height of. Next we consider a tree with nodes.Looking at the node,we know its height is one greater than its parent(and since we’re not in the base case,all nodes have a parent).The parent of the th node in the tree is also the th node in the tree.Therefore its height is.Then the th node in the tree has a height of. Therefore by induction we have shown that the height of an node tree is.Exercise2-3.Do Exercise6.4-3on page136of CLRS.Solution:The running time of H EAPSORT on an array of length that is already sorted in increasing order is because even though it is already sorted,it will be transformed back into a heap and sorted.The running time of H EAPSORT on an array of length that is sorted in decreasing order will be.This occurs because even though the heap will be built in linear time,every time the element is removed and the H EAPIFY is called it will cover the full height of the tree. Exercise2-4.Do Exercise7.2-2on page153of CLRS.Solution:The running time will be because every time partition is called,all of the elements will be put into the subarray of elements smaller than the partition.The recurrence will bewhich is clearlyExercise2-5.Do Problem7-3on page161of CLRS.Solution:(a)This sort is intuitively correct because the largest rd of the elements will eventually be sorted amung their peers.If they are in thefirst third of the array to begin with,they will be sorted into the middle third.If they are in the middle or last third,then they will obviously be sorted into their proper position.Similarly any element which belongs in the each of the thirds will be sorted into position by the three sub-sorts.(b)Which solves to(c)S TOOGE S ORT is slower than all of the other algorithms we have studied.I NSERTION, M ERGE S ORT,H EAPSORT,and Q UICKSORT.Therefore all other sorts are faster and these professors do not deserve tenure for this work!Problem2-1.Average-case performance of quicksortWe have shown that the expected time of randomized quicksort is,but we have not yet analyzed the average-case performance of ordinary quicksort.We shall prove that,under the assumption that all input permutations are equally likely,not only is the running time of ordinary quicksort,but it performs essentially the same comparisons and exchanges between input elements as randomized quicksort.Consider the implementation of P ARTITION given in lecture on a subarray:P ARTITION123for to4do if5then6exchange7exchange8returnLet be a set of distinct elements which are provided in random order(all orders equally likely) as the input array to P ARTITION,where is the size of the array.Let denote the initial value of.(a)Argue that is a random permutation of,that is,that all permuta-tions of the input subarray are equally likely.Solution:Given that is random(all orders are equally likely),there are possiblepermutations of the elements.Each element has a probabilityof being chosen as the pivot,therefore the number of permutations of the remainingelements is.Consequently the permutations are equallylikely.Define as follows:ififif(b)Consider two input arrays and consisting of the elements of suchthat for all.Suppose that we run P ARTITIONon and and trace the two executions to record the branches taken,indices calculated,and exchanges performed—but not the actual array values ma-nipulated.Argue briefly that the two execution traces are identical.Argue further thatP ARTITION performs the same permutation on both inputs.Solution:P ARTITION takes different branches based only on the comparisons made in thefunction.This is clear by observing line4of the function,as it is the only place wherethe sequence of instructions may differ.As the arrays have identical functionvalues,they must take the same branches,calculate the same indicies and perform thesame exchanges.Consequently P ARTITION will perform the same partition on botharrays,which follows directly as the exchanges performed are identical.Define a sequence to be an input pattern if,for ,and.Define a sequence to be an output pattern ififififWe say that a permutation of satisfies a pattern iffor all.(c)How many input patterns are there?How many output patterns are there?Solution:There are input patterns because we can choose positions out of possible positions to have.There is one()output pattern because the pattern must be exactly negative ones followed by a0,followed byones.(d)How many permutations of satisfy a particular input pattern?How manypermutations of satisfy a particular output pattern?Solution:permutations are possible of to satisfy a particular input pattern.This is the total number of ways to rearrange the elements which have a value ofamongst themselves,and rearrange those with a value of1amongst themselves.Thereare also permutations possible to satisfy a particular output patternfor the same reason.Let be an input pattern,and let be an output pattern.Define to be the set of permutations of that satisfy,and likewise define to be the set of permutations of that satisfy.(e)Argue that P ARTITION implements a bijection from to.(Hint:Use the factfrom group theory that composing afixed permutation with each of the possiblepermutations yields the set of all permutations.)Solution:All members of satisfy and so they all have the same result when the functionis applied to its elements.Therefore by part(b)when all these inputs are given toP ARTITION they are subject to the same ing the hint,we then knowthat after all of the distinct inputs are run through P ARTITION that they will produceall distinct outputs.From part we know that and are thesame size,and also we have proven that P ARTITION is onto,and therefore P ARTITIONmust be a bijection!(f)Suppose that before the call to P ARTITION,the input subarray is a randompermutation of,where.Argue that after P ARTITION,the tworesulting subarrays are random permutations of their respective elements.Solution:Using our solution from part(e),we know that after P ARTITION is run on,we getall values in the set.Therefore we get all permutations of the ones and allpermutations of the negative ones.Furthermore,we get each sub-array permu-tations an equal number of times and so the subarrays are also random permutations.(g)Use induction to show that,under the assumption that all input permutations areequally likely,at each recursive call of Q UICKSORT,every element of be-longing to is equally likely to be the pivot.Solution:The base case for the initial array;we know that it is randomly permuted,and so bypart and each of its subarrays will also be randomly permuted after P ARTITION.Therefore we can inductively apply at each partition to prove that every subarraywill also be randomly permuted.(h)Use the analysis of R ANDOMIZED-Q UICKSORT to conclude that the average-caserunning time of Q UICKSORT on elements is.Solution:By part(g)we know that under the assumption that the input pattern is random everyelement is equally likely to be chosen as the pivot at each recursive call which then pro-duces the same random distribution of quicksort traces as R ANDOMIZED-Q UICKSORT.Therefore as their distribution is the same,the expected-case analysis for R ANDOMIZED-Q UICKSORT will apply to the average case of Q UICKSORT.Therefore the average case of Q UICKSORTalso takes time.Problem2-2.Analysis of-ary heapsA-ary heap is like a binary heap,but(with one possible exception)nonleaf nodes have children instead of2children.(a)How would you represent a-ary heap in an array?Solution:The-ary heap would be similar to a binary heap with the parent and child indexescalculated as follows:th-Child[]whereThe root of the tree would be at index.Alternate Solution:A-ary heap can be represented in a-dimensional array asfollows.The root is kept in,its children are kept in order in through,their children are kept in order in through,and so on.The two procedures that map a node with index to its parent and to its th child(for),respectively,are;D-ARY-P ARENTreturnD-ARY-C HILDreturnTo convince yourself that these procedures really work,verify thatD-ARY-P ARENT D-ARY-C HILDfor any.Notice that the binary heap procedures are a special case of the above procedures when.(b)What is the height of a-ary heap of elements in terms of and?Solution:CORRECTIONA-ary heap would have a height of.We know thatwhich solves to.(c)Give an efficient implementation of E XTRACT-M AX in a-ary max-heap.Analyze itsrunning time in terms of and.Solution:H EAPIFY12for to3if and4then5if6then7Exchange8H EAPIFYThe running time of H EAPIFY is because at each depth we are doing loops,and we recurse to the depth of the tree.In H EAPIFY we compare the the th node and each of its children tofind the maximum value for all of the nodes.Then ifthe maximum child is greater than the th node,we switch the two nodes and recurse on the child.E XTRACT-M AX(A,n)1234H EAPIFY(A,1,n,d)5returnThe running time of this algorithm,is clearly constant work plus the time of H EAPIFY which as shown above is.E XTRACT-M AX works by storing the value of the maximum element,moving the minimum element into the root of the heap,and then calling heapify to restore the heap property.(d)Give an efficient implementation of I NSERT in a-ary max-heap.Analyze its runningtime in terms of and.Solution:See next problem part for I NCREASE-K EY definition.I NSERT123I NCREASE-K EYFrom the following problem part,we know I NCREASE-K EY runs in time, therefore since I NSERT only adds constant time operations it is also.It is rather trivially correct as the algorithm has not changed because all calculations involving the number of children are performed by I NCREASE K EY.(e)Give an efficient implementation of I NCREASE-K EY,whichfirst setsand then updates the-ary max-heap structure appropriately.Analyze its running time in terms of and.Solution:I NCREASE-K EY12if3while and 6。

目录第二章 (2)练习题 (2)2.1-1 (2)2.1-2 (2)2.1-3 (2)2.1-4 (3)2.2-1 (3)2.2-2 (3)2.2-3 (4)2.2-4 (4)2.3-1 (4)2.3-2 (4)2.3-3 (4)2.3-4 (5)2.3-5 (5)2.3-6 (6)*2.3-7 (6)思考题 (6)2-1 （ (6)第二章练习题2.1-1以图2-2为模型，说明INSERTION-SORT在数组A=(31,41,59,26, 41,58〉上的执行过程。

略2.1-2重写过程INSERTION-SORT,使之按非升序（而不是非降序）排序。

//2.1-2.c 插入排序-非升序void InsertionSortNI(int ar[],int n){int i,j,key;for(j=1;j<n;j++){key = ar[j];i = j-1;while(i>=0&& ar[i]<key){ar[i+1]= ar[i];i=i-1;}ar[i+1]= key;}}2.1-3思考下面的查找问题：输入：有n个元素的序列A= (a1,a2,…,an)和一个值v。

输出：下标i（当v=A[i]）, 或者特殊值NIL(当v不在A中出现时)。

写出线性查找的伪代码，它扫描整个序列来查找v。

使用一个循环不变式来证明你的算法是正确的。

确保你的循环不变式满足三条必要的性质。

代码：//2.1-3.c 线性查找int serchv(int A[],int n,int v){int i;for(i=0;i<n;i++){if(A[i]==v)return i;}return 'NULL';}证明：循环不变式：在每一次for循环开始时，子数组A[0, ..., i-1]中的元素都不等于v;初始化：在第一次迭代之前，i=0，子数组是空数组，易知循环不定式是成立的；保持：在每次循环内部，将A[i] 与v比较，若符合，则返回正确结果i；在每次循环结束时，得知子数组A[0, ..., i-2]不含有v，循环不定式维持成立；递增i，使循环遍历数组中的元素，直到找到v或到达数组尽头；终止：终止条件为1. i>=n 或者2. A[i]==v。

第二章算法入门由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。

另，思考题2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供个意见。

给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。

插入排序算法伪代码INSERTION-SORT(A)1 for j ←2 to length[A]2 do key ←A[j]3 Insert A[j] into the sorted sequence A[1..j-1]4 i ←j-15 while i > 0 and A[i] > key6 do A[i+1]←A[i]7 i ←i − 18 A[i+1]←keyC#对揑入排序算法的实现:public static void InsertionSort<T>(T[] Input) where T:IComparable<T>{T key;int i;for (int j = 1; j < Input.Length; j++){key = Input[j];i = j - 1;for (; i >= 0 && Input[i].CompareTo(key)>0;i-- )Input[i + 1] = Input[i];Input[i+1]=key;}}揑入算法的设计使用的是增量（incremental）方法：在排好子数组A[1..j-1]后，将元素A[ j]揑入，形成排好序的子数组A[1..j]这里需要注意的是由于大部分编程语言的数组都是从0开始算起，这个不伪代码认为的数组的数是第1个有所丌同，一般要注意有几个关键值要比伪代码的小1.如果按照大部分计算机编程语言的思路，修改为：INSERTION-SORT(A)1 for j ← 1 to length[A]2 do key ←A[j]3 i ←j-14 while i ≥ 0 and A[i] > key5 do A[i+1]←A[i]6 i ← i − 17 A[i+1]←key循环丌变式(Loop Invariant)是证明算法正确性的一个重要工具。

第2章算法题参考答案1．设计算法，删除顺序表中值为x的所有结点。

int Delete_Sq (SqList *L ,ElemType x){i=1;if (L->len==0) return -1; /* 表已空*/while (i<=L->len)if(L->elem[i]=x){for (j=i;j<=L->len-1;j++)L->elem[j]=L->elem[j+1]; /*被删除元素之后的元素左移*/--L->len;}elsei++;return 1;}2．设线性表(a1，a2，…，a n)存储在带表头结点的单链表中，且线性表中所有元素均不相同。

试设计算法，求出该线性表中值为x的元素的序号。

如果x不存在，则序号为0。

int Index_Linkst( LNode *H, ElemType x){p=H->next; j=1;while( p ){if(p->data!=x){j++;p=p->next;}elsereturn j;}return 0;}3．在一个非递减有序的线性表中，插入一个值为x的元素，使插入后的线性表仍然递增有序。

分别写出用顺序表和单链表表示时的算法。

顺序表：int Insert_Sq (SqList *L , ElemType x){if ( L->len== MAXSIZE-1) return -1; /* 表已满*/i=1;while ( i<= L->len && x>=L->elem[i] )i++;for(j=L->len;j>=i;j--)L->elem[j+1]=L->elem[j];L->elem[i]=x;L->len+=1;}return 1;}单链表：void Insert_Linkst (LNode *H, ElemType x){q=H;p=H->next;s= (LNode *) malloc (sizeof(LNode));s->data=x;while ( p && p->data<x){q=p; p=p->next;}q->next=s;s->next=p;}5.有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法删除链表中多余的元素值相同的结点。