计算机算法设计与分析课后题答案(第三版)王晓东

习题2-1 求下列函数的渐进表达式：3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。

解答：3n^2+10n=O(n^2),n^2/10+2^n=O(2^n),21+1/n=O(1),logn^3=O(logn),10log3^n=O(n).习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。

解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2 、20n、n^2/3、logn、2习题2-4(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。

在某台计算机上实现并完成该算法的时间为t秒。

现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T（n)=常数，因此算法可解任意规模的问题。

习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。

对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到n'<n+log100=n+6.64习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。

算法设计与分析第三版第四章课后习题答案4.1 线性时间选择问题习题4.1问题描述：给定一个长度为n的无序数组A和一个整数k，设计一个算法，找出数组A中第k小的元素。

算法思路：本题可以使用快速选择算法来解决。

快速选择算法是基于快速排序算法的思想，通过递归地划分数组来找到第k小的元素。

具体步骤如下： 1. 选择数组A的一个随机元素x作为枢纽元。

2. 使用x将数组划分为两个子数组A1和A2，其中A1中的元素小于等于x，A2中的元素大于x。

3. 如果k等于A1的长度，那么x就是第k小的元素，返回x。

4. 如果k小于A1的长度，那么第k小的元素在A1中，递归地在A1中寻找第k小的元素。

5. 如果k大于A1的长度，那么第k小的元素在A2中，递归地在A2中寻找第k-A1的长度小的元素。

6. 递归地重复上述步骤，直到找到第k小的元素。

算法实现：public class LinearTimeSelection {public static int select(int[] A, int k) { return selectHelper(A, 0, A.length - 1, k);}private static int selectHelper(int[] A, int left, int right, int k) {if (left == right) {return A[left];}int pivotIndex = partition(A, left, righ t);int length = pivotIndex - left + 1;if (k == length) {return A[pivotIndex];} else if (k < length) {return selectHelper(A, left, pivotInd ex - 1, k);} else {return selectHelper(A, pivotIndex + 1, right, k - length);}}private static int partition(int[] A, int lef t, int right) {int pivotIndex = left + (right - left) / 2;int pivotValue = A[pivotIndex];int i = left;int j = right;while (i <= j) {while (A[i] < pivotValue) {i++;}while (A[j] > pivotValue) {j--;}if (i <= j) {swap(A, i, j);i++;j--;}}return i - 1;}private static void swap(int[] A, int i, int j) {int temp = A[i];A[i] = A[j];A[j] = temp;}}算法分析：快速选择算法的平均复杂度为O(n)，最坏情况下的复杂度为O(n^2)。

4.1：在我们所了解的早期排序算法之中有一种叫做Maxsort 的算法。

它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max ，然后将该元素同未排序序列中的最后一个元素交换。

这时，max 元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max 已经不在未排序序列之中了。

重复上述过程直到完成整个序列的排序。

(a) 写出Maxsort 算法。

其中待排序序列为E ，含有n 个元素，脚标为范围为0,,1n -K 。

void Maxsort(Element[] E) { int maxID = 0;for (int i=E.length; i>1; i--) { for (int j=0; j<i; j++) {if (E[j] > E[maxID]) maxID = k; E[i] <--> E[maxID];(b) 说明在最坏情况下和平均情况下上述算法的比较次数。

最坏情况同平均情况是相同的都是11(1)()2n i n n C n i -=-==∑。

4.2：在以下的几个练习中我们研究一种叫做“冒泡排序”的排序算法。

该算法通过连续几遍浏览序列实现。

排序策略是顺序比较相邻元素，如果这两个元素未排序则交换这两个元素的位置。

也就说，首先比较第一个元素和第二个元素，如果第一个元素大于第二个元素，这交换这两个元素的位置；然后比较第二个元素与第三个元素，按照需要交换两个元素的位置；以此类推。

(a)起泡排序的最坏情况为逆序输入，比较次数为11(1)()2n i n n C n i -=-==∑。

(b) 最好情况为已排序，需要(n-1)次比较。

4.3： (a)归纳法：当n=1时显然成立，当n=2时经过一次起泡后，也显然最大元素位于末尾；现假设当n=k-1是，命题也成立，则当n=k 时，对前k-1个元素经过一次起泡后，根据假设显然第k-1个元素是前k-1个元素中最大的，现在根据起泡定义它要同第k 个元素进行比较，当k 元素大于k-1元素时，它为k 个元素中最大的，命题成立；当k 元素小于k-1元素时，它要同k-1交换，这时处于队列末尾的显然时队列中最大的元素。

大学教材部分答案参考网站 (供大家学习)1、C 程序设计第三版 (谭浩强著) 清华大学出版社课后答案/bbs/viewthread.php?tid=80&fromuid=92、复变函数与积分变换第四版 (张元林西安交大著) 高等教育出版社课后答案/bbs/viewthread.php?tid=612&fromuid=9C 语言程序设计教程第三版(谭浩强张基温著) 高等教育出版社课后答案[khdaw_lxywyl]/bbs/viewthread.php?tid=79&fromuid=9C 语言程序设计教程第二版 (谭浩强张基温著) 高等教育出版社课后答案【khdaw】/bbs/viewthread.php?tid=256&fromuid=9离散数学（第三版）(耿素云屈婉玲张立昂著) 清华大学出版社课后答案【khdaw_ricardo】/bbs/viewthread.php?tid=293&fromuid=9耿国华数据结构课后答案/bbs/viewthread.php?tid=103&fromuid=9严蔚敏《数据结构(c 语言版)习题集》答案/bbs/viewthread.php?tid=102&fromuid=9谭浩强C++程序设计习题答案/bbs/viewthread.php?tid=420&fromuid=9《微机原理与接口技术》清华（冯博琴吴宁）版课后答案/bbs/viewthread.php?tid=707&fromuid=9数据库系统概论 (王珊萨师煊著) 清华大学出版社课后答案/bbs/viewthread.php?tid=991&fromuid=9C 程序设计第二版 (谭浩强著) 课后答案/bbs/viewthread.php?tid=47&fromuid=9清华大学《数据结构》习题+课后答案/bbs/viewthread.php?tid=249&fromuid=9《数学物理方法》（梁昆淼第二版）习题解答谢希仁版《计算机网络教程》课后答案/bbs/viewthread.php?tid=203&fromuid=9《计算机网络第四版》答案【khdaw】/bbs/viewthread.php?tid=340&fromuid=9数据结构习题集（C 版）答案/bbs/viewthread.php?tid=374&fromuid=9计算机操作系统 (汤子赢著) 西安电子科技大学课后答案/bbs/viewthread.php?tid=1083&fromuid=9离散数学 (左孝凌著) 上海科学技术文献出版社课后答案【khdaw】/bbs/viewthread.php?tid=466&fromuid=9近世代数基础 (刘绍学著) 高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=177&fromuid=9计算机组成原理习题＆答案唐朔飞高等教育出版社【khdaw】/bbs/viewthread.php?tid=984&fromuid=9计算机网络（第4 版）清华（Andrew S.Tanenbaum）版答案（中文版）【khdaw】/bbs/viewthread.php?tid=201&fromuid=9《常微分方程》王高雄高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=567&fromuid=9数学分析（陈传璋版）习题答案下载/bbs/viewthread.php?tid=714&fromuid=9计算机算法设计与分析(第 3 版) (王晓东著) 电子工业出版社课后答案【khdaw_ricardo】/bbs/viewthread.php?tid=3162&fromuid=9《计算机系统结构》清华第2 版习题解答(chm)【khdaw】/bbs/viewthread.php?tid=1303&fromuid=9《编译原理》课后习题答案/bbs/viewthread.php?tid=175&fromuid=9《计算机网络》(第三版) (Andrew S.Tanenbaum 著) 清华大学出版社课后答案《软件工程》课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=896&fromuid=9C++语言程序设计(第3 版) (郑莉著) 清华大学出版社课后答案/bbs/viewthread.php?tid=988&fromuid=9计算机操作系统第三版 (汤子瀛哲凤屏汤小丹著) 西安电子科技大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=691&fromuid=9微型计算机接口技术及应用【khdaw】/bbs/viewthread.php?tid=375&fromuid=9常微分方程 (王高雄)第三版高等教育出版社课后答案【khdaw】/bbs/viewthread.php?tid=2563&fromuid=9编译原理第三版 (陈火旺著) 国防工业出版社课后答案/bbs/viewthread.php?tid=1476&fromuid=9《常微分方程》(王高雄版)习题答案/bbs/viewthread.php?tid=489&fromuid=9大学计算机基础教程答案/bbs/viewthread.php?tid=379&fromuid=980x86 汇编语言程序设计 (沈明美温冬禅著) 清华大学出版社课后答案/bbs/viewthread.php?tid=523&fromuid=9IBM-PC 汇编语言程序设计课后习题答案 (美明温冬婵著) 清华大学出版社课后答案/bbs/viewthread.php?tid=370&fromuid=9数学分析 (华东师范大学数学系著) 高等教育出版社课后答案/bbs/viewthread.php?tid=238&fromuid=9李春葆：数据结构习题与解析-C 语言版/bbs/viewthread.php?tid=1005&fromuid=9visual basic 示例程序、实验答案下载/bbs/viewthread.php?tid=508&fromuid=9汇编语言 (王爽著) 课后答案清华版《编译原理》课后答案/bbs/viewthread.php?tid=228&fromuid=9离散数学（高等教育出版社）耿素云屈婉玲【khdaw】/bbs/viewthread.php?tid=1224&fromuid=9离散数学及其应用 (傅彦顾小丰著) 电子工业出版社课后答案/bbs/viewthread.php?tid=233&fromuid=9《计算机网络》机械工业出版社（James F.Kurose, Keith W.Ross）答案【khdaw_cola】/bbs/viewthread.php?tid=730&fromuid=9计算机网络(第5 版)课后习题答案【khdaw】/bbs/viewthread.php?tid=2981&fromuid=9常微分方程课后习题答案(华东师范版)/bbs/viewthread.php?tid=172&fromuid=9《Visual FoxPro 程序设计教程》课后习题答案(刘卫国主编)/bbs/viewthread.php?tid=232&fromuid=9有关《计算机组成原理》相关课后答案发布/bbs/viewthread.php?tid=3565&fromuid=9《计算机组成原理》课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=505&fromuid=9C 程序设计第三版 (谭浩强著) 清华大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=3690&fromuid=9离散数学教程 (耿素云屈婉玲王捍贫著) 北京大学出版社课后答案/bbs/viewthread.php?tid=36&fromuid=9数据库系统概念答案【khdaw_cola】/bbs/viewthread.php?tid=759&fromuid=9数据库系统概论答案清华版【khdaw_cola】/bbs/viewthread.php?tid=337&fromuid=9所有有关《操作系统》的答案发布和一些版本的答案求助【khdaw】/bbs/viewthread.php?tid=3320&fromuid=9/bbs/viewthread.php?tid=2653&fromuid=9数据库系统概论(第四版)王珊、萨师煊【khdaw】/bbs/viewthread.php?tid=2291&fromuid=9数学分析答案复旦陈纪修【khdaw_cola】/bbs/viewthread.php?tid=328&fromuid=9《数据库系统概论》课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=219&fromuid=9数据库系统概论-第四版-高教版-王珊-封面看内图【khdaw_cola】/bbs/viewthread.php?tid=2344&fromuid=9计算机组成原理课后答案(白中英版)/bbs/viewthread.php?tid=173&fromuid=9所有《数据结构》版本课后答案发布/bbs/viewthread.php?tid=4310&fromuid=9《数值分析》（第４版）李庆扬编清华大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=3596&fromuid=9《数学分析》（第三版）华东师范大学高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=7192&fromuid=9数学分析复旦大学陈传章/bbs/viewthread.php?tid=448&fromuid=9近世代数基础 (张禾瑞著) 课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=269&fromuid=9《计算机组成与结构》王爱英(第四版)答案/bbs/viewthread.php?tid=4836&fromuid=9《软件工程导论》张海潘第五版清华大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=7159&fromuid=9所有有关《数据库系统概论》的答案发布和一些有关数据库版本的答案求助【khdaw】/bbs/viewthread.php?tid=3321&fromuid=9离散数学耿素云屈婉玲高等教育出版社课后习题参考答案【khdaw】C++语言程序设计（第3 版）（郑莉版）郑莉清华大学出版社【khdaw_lxywyl】/bbs/viewthread.php?tid=1106&fromuid=9目前最完整的数据结构1800 题包括完整答案（word 版本）/bbs/viewthread.php?tid=1244&fromuid=9《操作系统》（中国铁道出版社，刘振鹏，李亚平，王煜，张明）习题答案/bbs/viewthread.php?tid=348&fromuid=9机械工业版《c++程序设计语言》题解下载/bbs/viewthread.php?tid=254&fromuid=9《数字逻辑》（第二版）鲍家元毛文林高教出版课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=1081&fromuid=9《Visual FoxPro 及其应用系统开发》(简明版)谭浩强清华大学出版【khdaw_cola】/bbs/viewthread.php?tid=1362&fromuid=9《数据结构题集》严蔚敏 (C 语言版)答案【khdaw】/bbs/viewthread.php?tid=3319&fromuid=9《计算机组成原理与汇编语言程序设计》教材答案【khdaw_cola】/bbs/viewthread.php?tid=1233&fromuid=9计算机网络第二版 (吴功宜著) 清华大学出版社课后答案/bbs/viewthread.php?tid=4403&fromuid=9计算机网络谢希仁第五版电子工业出版社课后参考答案【khdaw_cola】/bbs/viewthread.php?tid=6495&fromuid=9复变函数与积分变换第四版西安交大课后答案/bbs/viewthread.php?tid=2181&fromuid=9《数学物理方法》学习指导【khdaw_cola】/bbs/viewthread.php?tid=1142&fromuid=9数值分析【khdaw_cola】/bbs/viewthread.php?tid=1521&fromuid=9信息论与编码学习辅导及习题详解/bbs/viewthread.php?tid=1903&fromuid=9/bbs/viewthread.php?tid=3048&fromuid=9VB 高教版课后答案/bbs/viewthread.php?tid=250&fromuid=9实变函数与泛函分析课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=1332&fromuid=9《微机系统原理与接口技术》课后答案【khdaw_cola】/bbs/viewthread.php?tid=1304&fromuid=9清华版编译原理课后答案(chm)【khdaw】/bbs/viewthread.php?tid=1302&fromuid=9计算机网络教程谢希仁版/bbs/viewthread.php?tid=1082&fromuid=9数值分析第四版 (李庆扬王能超易大义著) 清华大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=8086&fromuid=9耿国华数据结构---C 语言的描课后大部分习题答案西安电大学出版社【khdaw_cola】/bbs/viewthread.php?tid=2015&fromuid=9新版汇编语言程序设计 (钱晓捷著) 电子工业出版社课后答案/bbs/viewthread.php?tid=692&fromuid=9《计算机组成原理》唐朔飞第二版高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=9774&fromuid=9计算机组成原理白中英第四版课后答案【khdaw_cola】/bbs/viewthread.php?tid=3419&fromuid=9IBM-PC 汇编语言程序设计（第2 版） (沈美明温冬婵编著著) 清华出版社课后答案/bbs/viewthread.php?tid=3497&fromuid=9初等数论答案严士健高教版【khdaw_cola】/bbs/viewthread.php?tid=2360&fromuid=9计算机组成原理唐朔飞版高等教育出版社（部分答案）【khdaw】/bbs/viewthread.php?tid=3422&fromuid=9西电汤操作系统第三版【khdaw_cola】计算机应用基础 (不详著) 不详课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=262&fromuid=9数学模型（第三版）习题参考解答/bbs/viewthread.php?tid=4879&fromuid=9微型计算机原理与接口技术 (冯博琴著) 清华出版课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=2617&fromuid=9离散答案（王元元张桂蕓编著）科学出版社【khdaw_cola】/bbs/viewthread.php?tid=1100&fromuid=9《C 程序设计》谭浩强（第三版）清华大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=2608&fromuid=9C++ 程序设计(第二版)高等教育出版课件例题源代码及习题答案/bbs/viewthread.php?tid=1751&fromuid=9计算机网络教程第五版 (谢希仁著) 电子工业出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=11354&fromuid=9计算机网络第4 版 (谢希仁著) 电子工业出版社课后答案【khdaw】/bbs/viewthread.php?tid=225&fromuid=9软件工程导论第五版 (张海藩著) 清华大学出版社课后答案【khdaw】/bbs/viewthread.php?tid=7449&fromuid=9数据结构教程（第2 版）李春葆答案/bbs/viewthread.php?tid=3334&fromuid=9数值分析 (未知著) 华中科技大课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=3525&fromuid=9数据结构（C 语言版） (严蔚敏吴伟民米宁著) 清华大学出版社课后答案/bbs/viewthread.php?tid=2067&fromuid=9泛函分析讲义－习题解答张恭庆、林源渠北大版【khdaw_cola】/bbs/viewthread.php?tid=3139&fromuid=9近世代数基础 (张禾瑞著) 课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=3510&fromuid=9【khdaw_ricardo】/bbs/viewthread.php?tid=11229&fromuid=9白中英《计算机组成原理_试题、题解与题库》电子书（超星版）/bbs/viewthread.php?tid=1085&fromuid=9电子工业版《vb 语言程序设计》习题答案/bbs/viewthread.php?tid=107&fromuid=9C++ 程序设计教程(第二版) (钱能著) 清华大学出版课后答案/bbs/viewthread.php?tid=2503&fromuid=9计算机应用基础理论习题参考答案/bbs/viewthread.php?tid=116&fromuid=9数学模型第三版 (姜启源谢金星叶俊著) 高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=1972&fromuid=9Java 编程思想.第四版.课后练习答案/bbs/viewthread.php?tid=1846&fromuid=9《Java2 实用教程》（第三版）清华（耿祥义张跃平）版课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=6922&fromuid=9中文原版《编译原理》课后答案机械工业出版社李建中编/bbs/viewthread.php?tid=1847&fromuid=9计算机组成原理（教师用书）附带答案蒋本珊清华大学出版社【khdaw】/bbs/viewthread.php?tid=9254&fromuid=9《积分变换》张元林第四版东南大学答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5074&fromuid=9《马克思主义基本原理概论》课后答案（很全哦）（2008 年修订版）【khdaw_cola】/bbs/viewthread.php?tid=6053&fromuid=9<计算机操作系统教程>清华大学第二版/第三版张尧学课后习题答案【khdaw】/bbs/viewthread.php?tid=9091&fromuid=9<计算机网络教程> 谢希仁第二版人民邮电出版社课后答案【khdaw_cola】/bbs/viewthread.php?tid=4862&fromuid=9/bbs/viewthread.php?tid=7785&fromuid=9vfp 数据库课后题答案/bbs/viewthread.php?tid=231&fromuid=9单片机基础第3 版李广第朱月秀冷祖祁编著北京航空航天大学出版社【khdaw_cola】/bbs/viewthread.php?tid=4271&fromuid=9电工学第六版 (秦曾煌著) 高等教育出版社课后答案【khdaw_ricardo】/bbs/viewthread.php?tid=11241&fromuid=9《数据通信与计算机网络》高传善(第二版)高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=6610&fromuid=9《计算机组成原理》唐朔飞第4，5 章课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=1144&fromuid=9软件工程导论第五版 (张海藩著) 清华大学出版社课后答案【khdaw】/bbs/viewthread.php?tid=13716&fromuid=9初等数论第三版 (闵嗣鹤著) 高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=1508&fromuid=9《数据库系统概论》王珊萨师煊（第四版）高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5249&fromuid=9计算机数值方法 (施吉林著) 高等教育出版社课后答案/bbs/viewthread.php?tid=3903&fromuid=9离散数学耿素云屈婉玲课后答案/bbs/viewthread.php?tid=7839&fromuid=9数据结构---C 语言描述答案（耿国华）高教版【khdaw_cola】/bbs/viewthread.php?tid=2094&fromuid=9软件工程导论课后答案/bbs/viewthread.php?tid=5172&fromuid=9数据结构(殷人昆主编)【khdaw】/bbs/viewthread.php?tid=3077&fromuid=9《c 程序设计语言》英文第2 版课后答案严蔚敏数据结构例题算法代码/bbs/viewthread.php?tid=1031&fromuid=9国防科学技术大学计算机学院离散数学课后习题答案/bbs/viewthread.php?tid=100&fromuid=9计算机网络-自顶向下方法与Internet 特色第三版英文课后答案【khdaw_cola】/bbs/viewthread.php?tid=2495&fromuid=9《计算机组成原理》白中英第三版课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=3423&fromuid=9数据结构（C++版）王红梅，胡明，王涛版课后答案【khdaw_cola】/bbs/viewthread.php?tid=4426&fromuid=9清华版编译原理【khdaw_cola】/bbs/viewthread.php?tid=1027&fromuid=9微机原理与接口技术-基于IA-32 处理器和32 为汇编语言 (钱晓捷著) 机械工业出版社课后答案【khdaw_cola】/bbs/viewthread.php?tid=5668&fromuid=9《离散数学》左孝凌,刘永才上海科学技术文献出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5236&fromuid=9网络操作系统课后答案/bbs/viewthread.php?tid=430&fromuid=9《点集拓扑讲义》高教（熊金城）版课后答案【khdaw_cola】/bbs/viewthread.php?tid=6441&fromuid=9数学分析第二版 (陈传章著) 高等教育出版社课后答案【khdaw_cola】/bbs/viewthread.php?tid=2442&fromuid=9软件工程【khdaw】/bbs/viewthread.php?tid=3072&fromuid=9操作系统教程第4 版 (张钟秀著) 高等教育出版社课后答案/bbs/viewthread.php?tid=7703&fromuid=9信息论与编码技术--冯桂林其伟陈东华--清华大学出版社【khdaw_cola】/bbs/viewthread.php?tid=3332&fromuid=9编译原理课程设计报告（词法，语法等）【khdaw_cola】/bbs/viewthread.php?tid=2514&fromuid=9微机原理与接口技术楼顺天，周佳社科学出版社【khdaw_cola】/bbs/viewthread.php?tid=5304&fromuid=9《单片机原理及接口技术》梅丽凤清华大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5538&fromuid=9数据库系统概论_王珊、萨师煊第四版（chm 格式）【khdaw】/bbs/viewthread.php?tid=6403&fromuid=9数字逻辑答案第三版(华中科大欧阳星明)/bbs/viewthread.php?tid=6833&fromuid=9算法导论（英文版）答案【khdaw_cola】/bbs/viewthread.php?tid=2792&fromuid=9数学物理方法第三版 (梁昆淼著) 高等教育出版社课后答案/bbs/viewthread.php?tid=2398&fromuid=9微型计算机原理与接口技术 (周荷琴吴秀清著) 课后答案/bbs/viewthread.php?tid=4086&fromuid=9《工程数学概率统计简明教程(同济大学应用数学系)》课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=7219&fromuid=9复变函数答案【khdaw_cola】/bbs/viewthread.php?tid=6557&fromuid=9复变函数与积分变换 (马柏林著) 复旦大学课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=14749&fromuid=9计算机操作系统教程（第二版）左万历周长林【khdaw_cola】/bbs/viewthread.php?tid=1690&fromuid=9计算机组成原理（唐朔飞）答案高等教育出版社【khdaw】/bbs/viewthread.php?tid=8804&fromuid=9信息论与编码陈运电子工业出版社【khdaw_cola】/bbs/viewthread.php?tid=2828&fromuid=9计算机网络英文原版（第4 版）【khdaw】/bbs/viewthread.php?tid=3239&fromuid=9《数据库系统概念》（第五版影印版）高级教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5283&fromuid=9离散数学 (王义和著) 哈尔滨工业大学出版社课后答案【khdaw_ricardo】/bbs/viewthread.php?tid=5724&fromuid=9IBM-PC 汇编语言程序设计（沈美明2 版）【khdaw_cola】/bbs/viewthread.php?tid=5203&fromuid=9《C 程序设计解题与上机指导》谭浩强第二版清华大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=1551&fromuid=9《组合数学》第四版机械工业出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=4346&fromuid=9《计算机英语（第2 版）》参考译文与习题解答【khdaw】/bbs/viewthread.php?tid=2963&fromuid=9C 语言程序设计教程杨路明北京邮电大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=10074&fromuid=9《数据库系统及应用》崔魏（第二版）高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=2482&fromuid=9编译原理第三板 (陈火旺刘春林著) 国防工业课后答案/bbs/viewthread.php?tid=7680&fromuid=9《SQL SERVER 2005 数据库开发与实现》微软公司课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=1335&fromuid=9信号与线性系统管致中第4 版答案/bbs/viewthread.php?tid=6729&fromuid=9《计算机算法基础》（第三版）华中科技大4、5、6、8 章课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=4348&fromuid=9计算机系统结构第二版清华大学出版社课后答案/bbs/viewthread.php?tid=5370&fromuid=9《visual basic》课后作业答案【khdaw_lxywyl】常微分方程（张禾瑞）第三版【khdaw_cola】/bbs/viewthread.php?tid=1654&fromuid=9《数学分析》陈传璋课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=2217&fromuid=9高等几何梅学明高教版【khdaw_cola】/bbs/viewthread.php?tid=5698&fromuid=9数学分析高教出版社第二版复旦数学系主编/bbs/viewthread.php?tid=3025&fromuid=9编译原理第三版西北工业大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5614&fromuid=9数值分析数值计算方法曾金平湖南大学出版社课后答案【khdaw】/bbs/viewthread.php?tid=9628&fromuid=9C 语言程序设计 (何钦铭颜晖著) 浙江科学技术出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=14395&fromuid=9计算机网络第四版【khdaw_cola】/bbs/viewthread.php?tid=1084&fromuid=9数据结构课后答案（高等教育出版社唐策善版）)【khdaw】/bbs/viewthread.php?tid=5994&fromuid=9微型计算机技术及应用答案/bbs/viewthread.php?tid=6013&fromuid=9实变函数论第三版(江泽坚吴智泉纪友清著) 高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=11505&fromuid=9《微积分》人教版课后课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5190&fromuid=9严蔚敏《数据结构(c 语言版)习题集》答案/bbs/viewthread.php?tid=6170&fromuid=9微型计算机原理与接口技术 (邹逢兴著) 清华大学出版社课后答案【khdaw_cola】数据结构习题答案+耿国华主编【khdaw_cola】/bbs/viewthread.php?tid=7218&fromuid=9《数据库系统概论》王珊萨师煊（第四版）课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=6054&fromuid=9计算机组成与结构第四版 (王爱英著) 清华大学出版社课后答案【khdaw_ricardo】/bbs/viewthread.php?tid=11208&fromuid=9《数据结构习题集》答案严蔚敏【khdaw_cola】/bbs/viewthread.php?tid=6552&fromuid=9概率论与数理统计 (同济大学应用数学系著) 高等教育出版社课后答案/bbs/viewthread.php?tid=9101&fromuid=9立体几何大题30 题（有详细答案）[整理]人教版/bbs/viewthread.php?tid=333&fromuid=9计算机答案合集（组成原理，操作系统...）/bbs/viewthread.php?tid=5204&fromuid=9《应用概率统计》（张国权）版科学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=7334&fromuid=9《C 程序设计》谭浩强编习题答案【khdaw_cola】/bbs/viewthread.php?tid=7836&fromuid=9数据结构（C 语言版）习题答案/bbs/viewthread.php?tid=5200&fromuid=9编译原理 (陈火旺著) 国防工业出版社课后答案/bbs/viewthread.php?tid=2978&fromuid=9微机原理与接口技术第三章 (郭兰英赵祥模著) 清华出版社课后答案_khdaw/bbs/viewthread.php?tid=7347&fromuid=9计算机网络第二版） (冯博琴陈文革著) 高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5989&fromuid=9《数据结构》清华大学答案+例程+ppt 课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=9713&fromuid=9软件工程第二版 (张海藩著) 人民邮电出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=10940&fromuid=9计算机专业英语课后答案【khdaw_cola】/bbs/viewthread.php?tid=7258&fromuid=9数值计算课后答案曾喆昭文卉编著【khdaw_cola】/bbs/viewthread.php?tid=2538&fromuid=9计算机组成与结构(第4 版)习题解答（上）【khdaw_cola】/bbs/viewthread.php?tid=6286&fromuid=9数据结构(c 语言版)习题集答案/bbs/viewthread.php?tid=6096&fromuid=9vb 程序设计（第四版）课后习题答案【khdaw】/bbs/viewthread.php?tid=2994&fromuid=9汇编语言（清华大学出版社）【khdaw】/bbs/viewthread.php?tid=3421&fromuid=9离散数学答案修订版 (耿素云屈婉玲著) 高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=15917&fromuid=9《编译原理》蒋立源课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=4518&fromuid=9《数字逻辑》（第二版）华中科技大学出版社（欧阳星明）版课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=7332&fromuid=9严蔚敏数据机构实习报告部分答案【khdaw_cola】/bbs/viewthread.php?tid=1036&fromuid=9数值分析部分答案/bbs/viewthread.php?tid=3523&fromuid=9《数字图像处理》（第二版）英文版习题答案（全）【khdaw_lxywyl】/bbs/viewthread.php?tid=5854&fromuid=9C 程序设计(第二版)谭浩强习题解答清华大学出版社课后答案【khdaw_cola】/bbs/viewthread.php?tid=5679&fromuid=9微分几何梅向明第三版黄敬之高等教育出版社课后答案【khdaw】/bbs/viewthread.php?tid=9287&fromuid=9c++语言基础教程 (吕凤葛著) 清华大学出版社课后答案【khdaw】/bbs/viewthread.php?tid=14461&fromuid=9求《数值分析》第五版答案/bbs/viewthread.php?tid=6704&fromuid=9微分几何第三章、第四章 (梅向明著) 高等教育出版社课后答案/bbs/viewthread.php?tid=4721&fromuid=9《计算机组成原理》白中英（第四版•立体化教材）课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5281&fromuid=9数值分析/bbs/viewthread.php?tid=4245&fromuid=9c 程序设计 (谭浩强著) 清华大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=7611&fromuid=9《数据库原理》课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=4345&fromuid=9数据结构/bbs/viewthread.php?tid=1624&fromuid=9现代微机原理与接口技术 (杨全胜著) 电子工业出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=11531&fromuid=9《计算机系统组成与体系结构》人民邮电出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=2852&fromuid=9求数值分析（第４版）李庆扬编/bbs/viewthread.php?tid=6580&fromuid=9java2 实用教程（第三版）【khdaw_cola】/bbs/viewthread.php?tid=7256&fromuid=9数据结构答案【khdaw】/bbs/viewthread.php?tid=2066&fromuid=9人工智能原理及其应用王万森电子工业出版社（2-7 章）【khdaw】/bbs/viewthread.php?tid=9145&fromuid=9JAVA 大学实用教程第二版 (耿祥义张跃平著) 电子工业出版社课后答案【khdaw】/bbs/viewthread.php?tid=15805&fromuid=9Visual C++面向对象编程教程(第2 版) (王育坚著) 清华大学出版社课后答案【khdaw】/bbs/viewthread.php?tid=14404&fromuid=9清华大学出版社计算机网络第4 版中文答案【khdaw_cola】/bbs/viewthread.php?tid=8080&fromuid=9计算机网络第四版 (潘爱民译著) 清华大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=15080&fromuid=9初等数学研究学习指导 (叶立军著) 华东师范大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=13939&fromuid=9《复变函数论》张锦豪邱维元版高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5919&fromuid=9算法导论原书第二版 (潘金贵顾铁成李成法著) 机械工业出版社课后答案【khdaw】/bbs/viewthread.php?tid=12100&fromuid=9张禾瑞的＜＜近世代数基础＞＞的答案/bbs/viewthread.php?tid=1540&fromuid=9c++程序设计/bbs/viewthread.php?tid=5608&fromuid=9《概率论与统计学》浙大出版社（复习指南）课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=4871&fromuid=9计算机基础课后答案(浙江科学出版社)/bbs/viewthread.php?tid=2014&fromuid=9《C 语言程序设计》张世禄，潘大志，冯天敏电子工业出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=2568&fromuid=9C 语言程序设计(洪维恩)课后答案【khdaw】/bbs/viewthread.php?tid=1955&fromuid=9《计算机组成原理》白中英第四版科学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=6433&fromuid=9微机原理与接口技术第 4 版 (周荷琴，吴秀清著) 中国科学技术大学出版社课后答案【khdaw】/bbs/viewthread.php?tid=15151&fromuid=9数值计算课后答案（清华大学出版）/bbs/viewthread.php?tid=5246&fromuid=9java 程序设计【khdaw_cola】/bbs/viewthread.php?tid=7541&fromuid=9《高等数值分析》清华大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5692&fromuid=9数据与计算机通信（第七版） William Stallings 等【khdaw_cola】/bbs/viewthread.php?tid=5201&fromuid=9数值方法第二版 (金一庆陈越著) 机械工业出版社课后答案/bbs/viewthread.php?tid=11539&fromuid=9高等代数北师大高教第三版张和瑞【khdaw】/bbs/viewthread.php?tid=8607&fromuid=9微波技术与天线(第二版) 王新稳李萍李延平编电子工业出版社【khdaw_cola】/bbs/viewthread.php?tid=6534&fromuid=9数据结构（陈慧南编 C＋＋描述）南京邮电大学课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=9506&fromuid=9四川大学出版社编的离散数学教程答案【khdaw_cola】/bbs/viewthread.php?tid=7402&fromuid=9计算机组成原理（白中英版）【khdaw_cola】/bbs/viewthread.php?tid=3243&fromuid=9现代微型计算机与接口教程课后答案杨文显主编寿庆余副主编【khdaw_cola】/bbs/viewthread.php?tid=7964&fromuid=9C 语言程序设计 3-5 章部分程序题答案杨路明北京邮电大学出版社【khdaw】/bbs/viewthread.php?tid=8775&fromuid=9《操作系统》汤子赢西安电子科技大学答案【khdaw_lxywyl】/bbs/viewthread.php?tid=6055&fromuid=9数据库原理与应用教程第二版陈志泊人民邮电出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=9933&fromuid=9数据结构与算法分析（C++ 第二版）Clifford A. Shaffer 电子工业出版社【khdaw】/bbs/viewthread.php?tid=9211&fromuid=9《程序设计基础》练习题及答案【khdaw_lxywyl】/bbs/viewthread.php?tid=2801&fromuid=9《多媒体技术基础(第2 版)》林福宗清华大学出版社课后参考答案【khdaw】/bbs/viewthread.php?tid=9299&fromuid=9计算机专业英语(含课文、译文、模拟试题、专业英语习题、答案)【khdaw】/bbs/viewthread.php?tid=9364&fromuid=908 版考研概率复习指南答案/bbs/viewthread.php?tid=509&fromuid=9计算机网络（第4 版） (Andrew S.Tanenbaum 著) 清华大学出版社课后答案/bbs/viewthread.php?tid=11361&fromuid=9计算机图形学王汝传 1－4 章人民邮电出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=10000&fromuid=9计算机网络教程（第3 版）习题答案【khdaw_cola】/bbs/viewthread.php?tid=7777&fromuid=9c++语言程序设计（实验部分）第 3 版(郑莉著) 清华大学出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=15124&fromuid=9数字信号处理学习指导与题解 (丁美玉高西全王军宁著) 电子工业出版社课后答案【khdaw】/bbs/viewthread.php?tid=15168&fromuid=9计算机网络第五版 (谢希仁著) 电子工业出版社课后答案/bbs/viewthread.php?tid=16108&fromuid=9数学物理方程与特殊函数第三版完整 (东南大学数学系王元明著) 高等教育出版社课后答案【khdaw】/bbs/viewthread.php?tid=17311&fromuid=9《操作系统概念》英文版高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=3491&fromuid=9计算机网络第二版蔡开裕朱培栋徐明（国防科技大学版）【khdaw】/bbs/viewthread.php?tid=9239&fromuid=9《C++语言程序设计教程》吕凤翥人民邮电出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=8119&fromuid=9电工学第七版下册 (秦曾黄著) 高等教育出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=19778&fromuid=9vfp 表修复工具/bbs/viewthread.php?tid=73&fromuid=9C++语言基础教程吕凤翥人民邮电出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=10016&fromuid=9数据库及其应用教材课后习题答案_【khdaw_lxywyl】/bbs/viewthread.php?tid=9530&fromuid=9Turbo C 错误信息表/bbs/viewthread.php?tid=70&fromuid=9《微机原理及汇编技术》课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=5684&fromuid=9复变函数答案第四版 (余家荣著) 高等教育出版社课后答案【khdaw】/bbs/viewthread.php?tid=17004&fromuid=9Java 程序设计(第二版) (朱喜福著) 人民邮电出版社课后答案【khdaw_lxywyl】/bbs/viewthread.php?tid=10576&fromuid=9计算机专业英语教程译文（第 4 版） (金志权等主编著) 电子工业出版社课后答案【khdaw】/bbs/viewthread.php?tid=14170&fromuid=9数据结构习题/bbs/viewthread.php?tid=4344&fromuid=9《计算机英语》第２版全书翻译及课后答案_【khdaw_lxywyl】。

作业一学号：______ 姓名：________P1352.a.为一个分治算法编写伪代码，该算法同时求出一个n元素数组的最大元素和最小元素的值。

解：算法：EXTREMUM(A[m..n],EXTREMUM_MAX, EXTREMUM_MIN)//递归调用EXTREMUM函数来找出数组A[m..n]的最大元素和最小元素。

//输入：数值数组A[m..n]//输出：最大值EXTREMUM_MAX和最小值EXTREMUM_MINif(m=n) //只有一个元素EXTREMUM_MAX←A[m];EXTREMUM_MIN←A[n];elseif n−m=1 //有两个元素if A[m]≤A[n]EXTREMUM_MAX←A[n]; EXTREMUM_MIN←A[m]; elseEXTREMUM_MAX←A[m]; EXTREMUM_MIN←A[n]; elseEXTREMUM(A[m..(m+n)/2],EXTREMUM_MAX_01,EXTREMUM_MIN_01);EXTREMUM(A[(m+n)/2..n],EXTREMUM_MAX_02,EXTREMUM_MIN_02);if EXTREMUM_MAX_01< EXTREMUM_MAX_02EXTREMUM_MAX = EXTREMUM_MAX_02;If EXTREMUM_MIN_02< EXTREMUM_MIN_01EXTREMUM_MIN = EXTREMUM_MIN_02;b. 假设n=2k,为该算法的键值比较次数建立递推关系式并求解。

解：C(n)=C(2k)=2C(2k−1)+2=2[2C(2k−2)+2]+2=22[2C(2k−3)+2]+22+2=2k−1C(2)+2k−1+2k−2+...+2=3n2−2c.将该算法与解决同样问题的蛮力法做一个比较蛮力法时间时间复杂度为2n-2，分治算法的为3n/2-2,虽然都属于Θ(n)级别，但是分治算法速度要比蛮力算法快。

第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。

若f=Ο(g)，则必然存在常数c1>0和n0，使得∀n≥n0，有f≤c1*g(n)。

由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。

必要性。

同理，若g=Ω(f)，则必然存在c2>0和n0，使得∀n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。

2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得∀n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。

由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。

3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。

证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得∀n≥n1，有F(n) ≤ c1 (f(n)+g(n))= c1 f(n) + c1g(n)≤ c1*max{f,g}+ c1*max{f,g}=2 c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g))对于Ω和Θ同理证明可以成立。

4）log(n!)= Θ(nlogn)证明：∙由于log(n!)=∑=n i i 1log ≤∑=ni n 1log =nlogn ，所以可得log(n!)= Ο(nlogn)。

∙由于对所有的偶数n 有，log(n!)= ∑=n i i 1log ≥∑=n n i i 2/log ≥∑=nn i n 2/2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。

当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得∀n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。

《计算机算法设计与分析》习题及答案一．选择题1、二分搜索算法是利用（ A ）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ A ）。

A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（ A ）的一搜索方式。

A、分支界限法B、动态规划法C、贪心法D、回溯法4. 回溯法解旅行售货员问题时的解空间树是（ A ）。

A、子集树B、排列树C、深度优先生成树D、广度优先生成树5．下列算法中通常以自底向上的方式求解最优解的是（ B ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法6、衡量一个算法好坏的标准是（ C ）。

A 运行速度快B 占用空间少C 时间复杂度低D 代码短7、以下不可以使用分治法求解的是（ D ）。

A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题8. 实现循环赛日程表利用的算法是（ A ）。

A、分治策略B、动态规划法C、贪心法D、回溯法9．下面不是分支界限法搜索方式的是（ D ）。

A、广度优先B、最小耗费优先C、最大效益优先D、深度优先10．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法11.备忘录方法是那种算法的变形。

（ B ）A、分治法B、动态规划法C、贪心法D、回溯法12．哈夫曼编码的贪心算法所需的计算时间为（ B ）。

A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）13．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。

A、最小堆B、最大堆C、栈D、数组14．最长公共子序列算法利用的算法是（ B ）。

A、分支界限法B、动态规划法C、贪心法D、回溯法15．实现棋盘覆盖算法利用的算法是（ A ）。

A、分治法B、动态规划法C、贪心法D、回溯法16.下面是贪心算法的基本要素的是（ C ）。

A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解17.回溯法的效率不依赖于下列哪些因素（ D ）A.满足显约束的值的个数B. 计算约束函数的时间C.计算限界函数的时间D. 确定解空间的时间18.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ）A．递归函数 B.剪枝函数 C。

习题2-1 求下列函数的渐进表达式：3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。

解答：3n^2+10n=O(n^2),n^2/10+2^n=O(2^n),21+1/n=O(1),logn^3=O(logn),10log3^n=O(n).习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。

解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2 、20n、n^2/3、logn、2习题2-4(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。

在某台计算机上实现并完成该算法的时间为t秒。

现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T（n)=常数，因此算法可解任意规模的问题。

习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。

对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到n'<n+log100=n+6.64习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。