中科大算法导论期末试卷及答案

【实例简介】
算法导论期末试卷以及其答案，期末算法导论备考资料。
c*f(n 21-14c 2 71+5(C-1) 21-14 米n2 3n-5 即a()≤c(m)满足主定理第三条 综上,T(n)=((n))=6( 4.(卷1)求解递归方程Tn)=3T(n-1)+n2n+1。 解: T(n)=3T(n-1)+(n-1)2 T(n-1)=3T(n-2)+(n-2) T(n)-T(n-1)=3T(n-1)+(n-1}2-3T(n-2)-(n22=3T(n-1-3T(n-2)+2n-3 T(n)T(n-1)+n=3(T(n-1)-2T(n2)+n-1) 令cn)=T(n)-T(n-1)+n,则有cn)=3c(n-1) 由于T(1)=1,则T(2)=4,c(2)=T(2)-T(1)+2=5 则cn)=5*32, T(n)-T(n-1)+n=5*32 将(1)式和(2)式联合求解可得 T(n)=(5*31-n2-n-1/2 (卷2)求解递归方程T(n)=2T(n-1)+n2-2n+1 解 Tn)=2T(n-1)+(n-1)2 T(n-1)=2T(n-2)+(n-2 T(n)T(n1)=2T(n-1)+(n1)22T(n2)n22=2T(n-1)-2T(n2)+2n3 T(n)-T(n-1)+2n+1=2(T(n-1)-2T(n-2)+2(n1)+1) 令c(n)=T(n)T(n-1)+2n+1,则有cn)=2c(n1) 由于T(1)=1,则T(2)=3,c(2)=(2)-T(1)+5=7 则cn)=7*2n2, T(n)T(n1)+2n+1=7*22 将(1)式和(2)式联合求解可得 T()=7*21n2n-3 计算题 1、(卷1)已知数组A[1.14]"12,416,3,7,2122,15,8528,20,9,11”,请给出将数组A调整为 Min-堆的过程 解:调整过程如下,带[的节点表示正在调整以该节点为根的堆为小根堆。 16 16 4 22 21 11 15 5 2820911 15 2820 922 12 4 16 3 9 3 9 11 15 2820212 15 2820 21 12 16 5 9 11 5 16 11 15 28202122 15 28202122 12 12 4 16 11 4 16 15 28202122 15 2820 2122 3 4 9 12 16 11 8 16 11 15 28202122 15 12 28202122 9 8 5 16 11 15 127 2820 2122 (卷2)已知数组A[1.14-12,4,6,13,17,21,24,19,83,27,29,14,2",请给出将数组A 调整为Min-堆(二叉堆的过程。 解:调整过程如下,带匚的节点表示正在调整以该节点为根的堆为小根堆。 12 6 6 13 17 21 24 13 17 21 2 19 83 272914 19 83 2729 1424 12 2 6 4 13 17 14 2 13 3 14 19 27292124 19 81727292124 2 6 4 8 14 2 14 19 131727292124 1317 27292124 12 2 8 4 14 6 8 14 19 13172729 24 19 131727292124 6 3 6 8 14 12 8 14 19 131727292124 19131727292124 2、(卷1请在图1所示的红黑树中先插入关键字为23的结点,在插入关键字为21的结 点,给出具体的变化过程。 414 144 24 354 10 1622476 图1 解:第一幅图为在图1中插入结点23 294 19 41 插入结点23 14 214 35 1 b 22+26 19 414 改变颜色 14 24 10 16 22 26 234 24 41 左旋 19 35 14 104 16 19 右旋 14 41 10J 16 35 4 194 29 插入结点21 14 1 21+ 23 (卷2)请在图1所示的红黑树中先插入关键字为37的结点,再插入关键字为32的结点, 给出具体变化过程。 29 41 14 244 10H 16224 26 图1 解答:从原图基础上开始画变化过稈下 插入结点37 10n161242 37 29 194 左旋 14 24 37 10 1622+l26-35 右旋 19 11 2441 3 41 1 22 2日 插入结点32 19 3了 14 24 41 104|1641221264324 【实例截图】
【核心代码】