中国科学技术大学：《算法基础》课程教学资源（PPT课件讲稿）算法基础习题课（二）

Schoolof Computer Science and 7ccheologg 1958 算法基础习题课2 助教:刘倩玉 NCAA Network Computing and Advanced Algorithm Laboratory

算法基础习题课2 助教：刘倩玉 1

Schoolof Co buten Seicuac aud technology Page210151-1 。证明 T(n)=1+∑=0T0)T(0)=1 T(n)=2n 数学归纳法 a)T(0)成立 b)假设T(k)成立,推导T(k+1)成立 20221

Page210 15.1-1 2021/2/11 3 。证明 • 𝑻 𝒏 = 𝟏 + ෌𝒋=𝟎 𝒏−𝟏 𝑻(𝒋) 𝑻 𝟎 = 𝟏 • 𝑻 𝒏 = 𝟐 𝒏 ➢ 数学归纳法 a) T(0)成立 b) 假设T(k)成立，推导T(k+1)成立

Schoolof Co buten Seicuac aud technology Page22615.4-1 。求和的一个LCS >LCS: 20221

Page226 15.4-1 2021/2/11 4 。求和的一个LCS ➢ LCS：

Schoolof Co buten Seicuac aud technology Page22615.4-2 设计伪代码,利用完整的表c及原始序列X=和 Y=重构LCS,要求运行时间为O(m+n)不能使用表b。 解: 1. PRINT-LCS(C,X, Y,i,J) 2345 return if xli== Y[jl PRINT-LCS(C,X,Y,i-1,j-1) print xIi 789 else if cli-1,j]>=c[i,j-11 PRINT-LCS(C,X,Y,i-1,j) else PRINT-LCS(C, X,Y,i,j-1) 20221

Page226 15.4-2 2021/2/11 5 。设计伪代码，利用完整的表c及原始序列X = 和 Y=重构LCS，要求运行时间为O(m+n),不能使用表b。 解： 1. PRINT-LCS(c,X,Y,i,j) 2. if i == 0 or j == 0 3. return 4. if X[i] == Y[j] 5. PRINT-LCS(c,X,Y,i-1,j-1) 6. print X[i] 7. else if c[i-1,j] >= c[i,j-1] 8. PRINT-LCS(c,X,Y,i-1,j) 9. else 10. PRINT-LCS(c,X,Y,i,j-1)

Schoolof Co buten Seicuac aud technology Page22615.4-2 设计伪代码,利用完整的表c及原始序列X=和 Y=重构LCS,要求运行时间为O(m+n)不能使用表b。 解: PRINT-LCS(c, X,i,j) if i==0 or return 举例:X=010110110 4 fc[i-1,j-1]==c[i,j]-1 Y=1001 PRINT-LCS(c, X,i-1,J-1) c8,3]=3即100 6 print xli] c9,4]=4即1001 else if cli-1,J== cli,j c[9,4]-1=c[9-1,41]=c[8,3=3 8 PRINT-LCS(C,,i-1,J) 但Xg]的‘0’并不是LCS的构成元素 else 19 PRINT-LCS(,X,i,j-1) 20221

Page226 15.4-2 2021/2/11 6 。设计伪代码，利用完整的表c及原始序列X = 和 Y=重构LCS，要求运行时间为O(m+n),不能使用表b。 解： 1. PRINT-LCS(c,X,i,j) 2. if i == 0 or j == 0 3. return 4. if c[i-1,j-1] == c[i,j] - 1 5. PRINT-LCS(c,X,i-1,j-1) 6. print X[i] 7. else if c[i-1,j] == c[i,j] 8. PRINT-LCS(c,X,i-1,j) 9. else 10. PRINT-LCS(c,X,i,j-1) 举例：X = 0 1 0 1 1 0 1 1 0 Y = 1 0 0 1 c[8, 3] = 3 即 1 0 0 c[9, 4] = 4 即 1 0 0 1 c[9, 4] – 1 = c[9-1, 4-1] = c[8, 3] = 3 但X[9]的‘0’并不是LCS的构成元素

Schoolof Co buten Seicuac aud technology Page22615.4-5 。设计一个O(n2)时间的算法,求一个n个数的序列的最长单调递增子序列(LSs)。 思路1:类比LCS,使用数组A保存原始序列,数组B记录LIS长度,辅助数组C记矛 前驱下标 思路2:将LIS问题转换为LCS问题 1. LIS(A) n A length 23456 Initialize new array B[n]andc[n]//B[i]:以A[i结尾的LIS长度 for i =1 to n //C[i]:以A[i]结尾的LIS中A[i]的上一跳的下标 B[i]=1 C[i]=-1 for i =2 to n 8 for j=1-1 downto 1 9 if ali]=Bi 10 B[i]=B[j]+1 1 c[i]=j return b and c 20221

Page226 15.4-5 2021/2/11 7 。设计一个O(𝑛 2 )时间的算法，求一个n个数的序列的最长单调递增子序列（LIS）。 • 思路1：类比LCS，使用数组A保存原始序列，数组B记录LIS长度，辅助数组C记录 前驱下标 • 思路2：将LIS问题转换为LCS问题 1. LIS(A) 2. n = A.length 3. Initialize new array B[n] and C[n] //B[i]:以A[i]结尾的LIS长度 4. for i = 1 to n //C[i]:以A[i]结尾的LIS中A[i]的上一跳的下标 5. B[i] = 1 6. C[i] = -1 7. for i = 2 to n 8. for j = i-1 downto 1 9. if A[j] = B[i] 10. B[i] = B[j] + 1 11. C[i] = j 12. return B and C

Schoolof Co buten Seicuac aud technology Page22615.4-5 。设计一个O(n2)时间的算法,求一个n个数的序列的最长单调递增子序列(LSs)。 思路1:类比LCS,使用数组A保存原始序列,数组B记录LIS长度,辅助数组C记矛 前驱下标 思路2:将LIS问题转换为LCS问题 方法2: 原序列记为S1,S1单调递增排序后的序列记为S2,则求解S1的最长单调递增 序列问题可以转换成求解S1和S2的最长公共子序列问题。 其中,公共子序列保证了最后的序列1.是S1的子序列2.是S2的子序列(单语 递增) 20221

Page226 15.4-5 2021/2/11 8 。设计一个O(𝑛 2 )时间的算法，求一个n个数的序列的最长单调递增子序列（LIS）。 • 思路1：类比LCS，使用数组A保存原始序列，数组B记录LIS长度，辅助数组C记录 前驱下标 • 思路2：将LIS问题转换为LCS问题 方法2： 原序列记为S1，S1单调递增排序后的序列记为S2，则求解S1的最长单调递增子 序列问题可以转换成求解S1和S2的最长公共子序列问题。 其中，公共子序列保证了最后的序列 1. 是S1的子序列 2.是S2的子序列（单调 递增）

Schoolof Co buten Seicuac aud technology Page249163-1 。解释:在引理162的证明中,为什么若 xr freq=b∫eq, 则有aeg=bfeg=x:feq=y/req。 引理16.2提供的条件:afeq<=b, freq and x freq<= y freq x freq <=a.fred and y freq <=6. freq 推导出:xfeq<=a/req<= b freq x freq <=y freq <=6 freq x freq= bfreq, a,freq=b freq=x freq=y freq 20221

Page249 16.3-1 2021/2/11 9 。解释：在引理16.2的证明中，为什么若x.freq = b.freq， 则有a.freq= b.freq = x.freq= y.freq。 • 引理16.2提供的条件：a.freq <= b.freq and x.freq <= y.freq x.freq <= a.freq and y.freq <= b.freq • 推导出： x.freq<= a.freq<= b.freq x.freq<= y.freq<= b.freq 当 x.freq = b.freq，a.freq = b.freq= x.freq = y.freq

Schoolof Co buten Seicuac aud technology Page162121-2 。二叉搜索树性质与最小堆性质区别?是否可以使用最小堆性质在O仞m时间内按 序输出有n个结点树的关键字 性质区别:见定义 按序输出相当于堆排序,不可以。 20221

Page162 12.1-2 2021/2/11 10 。二叉搜索树性质与最小堆性质区别？是否可以使用最小堆性质在O(n)时间内按 序输出有n个结点树的关键字？ 性质区别：见定义 按序输出相当于堆排序，不可以

Schoolof Co buten Seicuac aud technology Page1621213 。设计执行二叉搜索树中序遍历的非递归算法。 1. INORDER-TREE-WALK(T) 2. Initialize an empty stacks 3. temp T 4.While(!s empty or temp != NULL 5 while(temp NULL)f 6 s push(temp) 7, temp temp left 8 9 temp=s pop( 10. print temp. val 11. temp= temp. right 12 20221

Page162 12.1-3 2021/2/11 11 。设计执行二叉搜索树中序遍历的非递归算法。 1.INORDER-TREE-WALK(T) 2.Initialize an empty stack s. 3.temp = T 4.while(!s.empty() or temp != NULL){ 5. while(temp != NULL){ 6. s.push(temp) 7. temp = temp.left 8. } 9. temp = s.pop() 10. print temp.val 11. temp = temp.right 12.}