算法设计与分析耿国华第八章

.第一章答案1.3 计算下列程序中 x=x+1 的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【解答】 x=x+1 的语句频度为：T(n)=1+(1+2)+ （ 1+2+3） + +（ 1+2+ +n） =n(n+1)(n+2)/61. 4 试编写算法，求 pn(x)=a 0+a1x+a2x2+ .+a nx n的值 pn(x 0), 并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。

注意：本题中的输入为 ai (i=0,1, n) 、 x 和 n, 输出为 Pn(x 0) 。

算法的输入和输出采用下列方法（ 1）通过参数表中的参数显式传递（ 2）通过全局变量隐式传递。

讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。

【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。

缺点：形参须与实参对应，且返回值数量有限。

（2）通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue(){ int i,n;float x,a[],p;printf( “\nn= ”);scanf( “%f”,&n);printf( “\nx= ”);scanf( “%f”,&x);for(i=0;i<n;i++)scanf( “%f ”,&a[i]); /* 执行次数： n 次 */p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x; /* 执行次数： n 次 */x=x*x;}printf( “%f”,p);}算法的时间复杂度： T(n)=O(n)通过参数表中的参数显式传递float PolyValue(float a[ ], float x, int n){float p,s;int i;p=x;s=a[0];for(i=1;i<=n;i++){s=s+a[i]*p; /* 执行次数 :n 次 */p=p*x;}return(p);..}算法的时间复杂度： T(n)=O(n)第二章答案2.7 试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（a1,a 2, ,a n）逆置为 (a n,a n-1 , ,a 1) 。

第一章习题答案2、××√3、（1）包含改变量定义的最小范围（2）数据抽象、信息隐蔽（3）数据对象、对象间的关系、一组处理数据的操作（4）指针类型（5）集合结构、线性结构、树形结构、图状结构（6）顺序存储、非顺序存储（7）一对一、一对多、多对多（8）一系列的操作（9）有限性、输入、可行性4、（1）A（2）C（3）C5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n）第二章习题答案1、（1）一半，插入、删除的位置（2）顺序和链式，显示，隐式（3）一定，不一定（4）头指针，头结点的指针域，其前驱的指针域2、（1）A（2）A：E、AB：H、L、I、E、AC：F、MD：L、J、A、G或J、A、G（3）D（4）D（5）C（6）A、C3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。

首元素结点：线性表中的第一个结点成为首元素结点。

4、算法如下：int Linser(SeqList *L,int X){ int i=0,k;if(L->last>=MAXSIZE-1){ printf(“表已满无法插入”)；return(0);}while(i<=L->last&&L->elem[i]<X)i++;for(k=L->last;k>=I;k--)L->elem[k+1]=L->elem[k];L->elem[i]=X;L->last++;return(1);}5、算法如下：#define OK 1#define ERROR 0Int LDel(Seqlist *L,int i,int k){ int j;if(i<1||(i+k)>(L->last+2)){ printf(“输入的i，k值不合法”);return ERROR;}if((i+k)==(L->last+2)){ L->last=i-2;ruturn OK;}else{for(j=i+k-1;j<=L->last;j++)elem[j-k]=elem[j];L->last=L->last-k;return OK;}}6、算法如下：#define OK 1#define ERROR 0Int Delet(LInkList L,int mink,int maxk){ Node *p,*q;p=L;while(p->next!=NULL)p=p->next;if(mink<maxk||(L->next->data>=mink)||(p->data<=maxk)){ printf(“参数不合法”);return ERROR;}else{ p=L;while(p->next-data<=mink)p=p->next;while(q->data<maxk){ p->next=q->next;free(q);q=p->next;}return OK;}}9、算法如下：int Dele(Node *S){ Node *p;P=s->next;If(p= =s){printf(“只有一个结点，不删除”)；return 0;}else{if((p->next= =s){s->next=s;free(p);return 1;}Else{ while(p->next->next!=s)P=p->next;P->next=s;Free(p); return 1;}}}第三章习题答案2、（1）3、栈有顺序栈和链栈两种存储结构。

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称八皇后问题专业计算机科学与技术班级学号姓名联系方式指导教师2011 年 12 月 25日目录1、数据结构课程设计任务书.............................................................................................. １1.1、题目..................................................................................................................... １1.2、要求..................................................................................................................... １2、总体设计....................................................................................................................... １2.1、功能模块设计 ...................................................................................................... １2.2、所有功能模块的流程图........................................................................................ ２3、详细设计....................................................................................................................... ５3.1、程序中所采用的数据结构及存储结构的说明........................................................ ５3.2、算法的设计思想................................................................................................... ５3.3、稀疏矩阵各种运算的性质变换 ............................................................................. ５4、调试与测试：................................................................................................................ ６4.1、调试方法与步骤： ............................................................................................... ６4.2、测试结果的分析与讨论： .................................................................................... ６4.3、测试过程中遇到的主要问题及采取的解决措施：................................................. ６5、时间复杂度的分析：..................................................................................................... ６6、源程序清单和执行结果 ................................................................................................. ６7、C程序设计总结 ........................................................................................................ １０8、致谢.......................................................................................................................... １０9、参考文献................................................................................................................... １０1、数据结构课程设计任务书1.1、题目八皇后问题1.2、要求编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。

《算法设计与分析》课程实验与设计福州大学王晓东第1章算法引论算法实现题1-1 统计数字问题算法实现题1-2 字典序问题算法实现题1-3 最多约数问题算法实现题1-4 金币阵列问题算法实现题1-5 最大间隙问题第2章递归与分治策略算法实现题2-1 输油管道问题算法实现题2-2 众数问题算法实现题2-3 邮局选址问题算法实现题2-4 马的Hamilton周游路线问题算法实现题2-5 半数集问题算法实现题2-6 半数单集问题算法实现题2-7 士兵站队问题算法实现题2-8 有重复元素的排列问题算法实现题2-9 排列的字典序问题算法实现题2-10 集合划分问题算法实现题2-11 集合划分问题2算法实现题2-12 双色Hanoi塔问题算法实现题2-13 标准2维表问题算法实现题2-14 整数因子分解问题算法实现题2-15 有向直线2中值问题第3章动态规划算法实现题3-1 独立任务最优调度问题算法实现题3-2 最少硬币问题算法实现题3-3 序关系计数问题算法实现题3-4 多重幂计数问题算法实现题3-5 编辑距离问题算法实现题3-6 石子合并问题算法实现题3-7 数字三角形问题算法实现题3-8 乘法表问题算法实现题3-9 租用游艇问题算法实现题3-10 汽车加油行驶问题算法实现题3-11 圈乘运算问题算法实现题3-12 最少费用购物算法实现题3-13 最大长方体问题算法实现题3-14 正则表达式匹配问题算法实现题3-15 双调旅行售货员问题算法实现题3-16 最大k乘积问题算法实现题3-17 最小m段和问题算法实现题3-18 红黑树的红色内结点问题第4章贪心算法算法实现题4-1 会场安排问题算法实现题4-2 最优合并问题算法实现题4-3 磁带最优存储问题算法实现题4-4 磁盘文件最优存储问题算法实现题4-6 最优服务次序问题算法实现题4-7 多处最优服务次序问题算法实现题4-8 d森林问题算法实现题4-9 汽车加油问题算法实现题4-10 区间覆盖问题算法实现题4-11 硬币找钱问题算法实现题4-12 删数问题算法实现题4-13 数列极差问题算法实现题4-14 嵌套箱问题算法实现题4-15 套汇问题算法实现题4-16 信号增强装置问题算法实现题4-17 磁带最大利用率问题算法实现题4-18 非单位时间任务安排问题算法实现题4-19 多元Huffman编码问题算法实现题4-20 多元Huffman编码变形算法实现题4-21 区间相交问题算法实现题4-22 任务时间表问题第5章回溯法算法实现题5-1 子集和问题算法实现题5-2 最小长度电路板排列问题算法实现题5-3 最小重量机器设计问题算法实现题5-4 运动员最佳匹配问题算法实现题5-5 无分隔符字典问题算法实现题5-6 无和集问题算法实现题5-7 n色方柱问题算法实现题5-9 拉丁矩阵问题算法实现题5-10 排列宝石问题算法实现题5-11 重复拉丁矩阵问题算法实现题5-12 罗密欧与朱丽叶的迷宫问题算法实现题5-13 工作分配问题算法实现题5-14 独立钻石跳棋问题算法实现题5-15 智力拼图问题算法实现题5-16 布线问题算法实现题5-17 最佳调度问题算法实现题5-18 无优先级运算问题算法实现题5-19 世界名画陈列馆问题算法实现题5-20 世界名画陈列馆问题（不重复监视）算法实现题5-21 部落卫队问题算法实现题5-22 虫蚀算式问题算法实现题5-23 完备环序列问题算法实现题5-24 离散01串问题算法实现题5-25 喷漆机器人问题算法实现题5-26 n2-1谜问题第6章分支限界法算法实现题6-1 最小长度电路板排列问题算法实现题6-2 最小长度电路板排列问题算法实现题6-3 最小权顶点覆盖问题算法实现题6-4 无向图的最大割问题算法实现题6-5 最小重量机器设计问题算法实现题6-6 运动员最佳匹配问题算法实现题6-7 n皇后问题算法实现题6-8 圆排列问题算法实现题6-9 布线问题算法实现题6-10 最佳调度问题算法实现题6-11 无优先级运算问题算法实现题6-12 世界名画陈列馆问题算法实现题6-13 骑士征途问题算法实现题6-14 推箱子问题算法实现题6-15 图形变换问题算法实现题6-16 行列变换问题算法实现题6-17 重排n2宫问题算法实现题6-18 最长距离问题第7章概率算法算法实现题7-1 模平方根问题算法实现题7-2 素数测试问题算法实现题7-3 集合相等问题算法实现题7-4 逆矩阵问题算法实现题7-5 多项式乘积问题算法实现题7-6 皇后控制问题算法实现题7-7 3SAT问题算法实现题7-8 战车问题算法实现题7-9 圆排列问题算法实现题7-10 骑士控制问题算法实现题7-11 骑士对攻问题第9章近似算法算法实现题9-1旅行售货员问题的近似算法算法实现题9-2 可满足问题的近似算法算法实现题9-3 最大可满足问题的近似算法算法实现题9-4 子集和问题的近似算法算法实现题9-5 子集和问题的完全多项式时间近似算法算法实现题9-6 实现算法greedySetCover算法实现题9-7 装箱问题的近似算法First Fit算法实现题9-8 装箱问题的近似算法Best Fit算法实现题9-9 装箱问题的近似算法First Fit Decreasing 算法实现题9-10 装箱问题的近似算法Best Fit Decreasing 算法实现题9-11 装箱问题的近似算法Next Fit第10章算法优化策略算法实现题10-1 货物储运问题算法实现题10-2 石子合并问题算法实现题10-3 最大运输费用货物储运问题算法实现题10-4 五边形问题算法实现题10-5 区间图最短路问题算法实现题10-6 圆弧区间最短路问题算法实现题10-7 双机调度问题算法实现题10-8 离线最小值问题算法实现题10-9 最近公共祖先问题算法实现题10-10 达尔文芯片问题算法实现题10-11 多柱Hanoi塔问题算法实现题10-12 线性时间Huffman算法算法实现题10-13 单机调度问题算法实现题10-14 最大费用单机调度问题算法实现题10-15 飞机加油问题《算法设计与分析》期中试卷1 试题1 数列极差问题试题2 双调TSP回路问题试题3 最佳调度问题《算法设计与分析》期中试卷2 试题1 石子合并问题试题2 整数因子分解问题试题3 汽车加油问题《算法设计与分析》期终试卷1 试题1 乘法表问题试题2 工作分配问题试题3 飞行员配对方案问题《算法设计与分析》期终试卷2 试题1 直线k中值问题试题2 图形变换问题试题3 无向图的最大割问题。

算法分析与设计教程习题解答第1章 算法引论1. 解：算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列计算方法。

频率计数是指计算机执行程序中的某一条语句的执行次数。

多项式时间算法是指可用多项式函数对某算法进行计算时间限界的算法。

指数时间算法是指某算法的计算时间只能使用指数函数限界的算法。

2. 解：算法分析的目的是使算法设计者知道为完成一项任务所设计的算法的优劣，进而促使人们想方设法地设计出一些效率更高效的算法，以便达到少花钱、多办事、办好事的经济效果。

3. 解：事前分析是指求出某个算法的一个时间限界函数（它是一些有关参数的函数）；事后测试指收集计算机对于某个算法的执行时间和占用空间的统计资料。

4. 解：评价一个算法应从事前分析和事后测试这两个阶段进行，事前分析主要应从时间复杂度和空间复杂度这两个维度进行分析；事后测试主要应对所评价的算法作时空性能分布图。

5. 解：①n=11； ②n=12； ③n=982； ④n=39。

第2章 递归算法与分治算法1． 解：递归算法是将归纳法的思想应用于算法设计之中，递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对于相关且必要的信息的保存与恢复；分治算法是把一个问题划分为一个或多个子问题，每个子问题与原问题具有完全相同的解决思路，进而可以按照递归的思路进行求解。

2． 解：通过分治算法的一般设计步骤进行说明。

3． 解：int fibonacci(int n) {if(n<=1) return 1;return fibonacci(n-1)+fibonacci(n-2); }4. 解：void hanoi(int n,int a,int b,int c) {if(n>0) {hanoi(n-1,a,c,b); move(a,b);hanoi(n-1,c,b,a); } } 5. 解：①22*2)(−−=n n f n② )log *()(n n n f O =6． 解：算法略。

5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty. (―lazy deletion ‖)第2章 习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。

第1章绪论1.基本概念：数据、数据元素、数据项、抽象数据类型2.数据的逻辑结构：集合结构、线性结构、树型结构、图形结构3.数据的存储结构：顺序存储、链式存储4.数据相关的运算集合（随具体应用而不同）5.算法：定义、算法的分析6.本章重点和难点（1）抽象数据类型（2）算法的时间复杂度的分析第2章线性表1.线性表的概念2.顺序表的概念、类型构造、基本运算3.链表的概念、类型构造、基本运算4.顺序表与链表各自的特点、适用场合5.一元多项式的表示和处理6.本章重点难点（1）顺序表的插入、删除等基本运算（2）单链表的插入、删除等基本运算（3）循环链表、双向链表的基本运算（4）链式存储表示的一元多项式的运算第3章栈和队列1.栈：（1）栈的定义、特点（2）顺序栈及基本运算的实现、两栈共享技术（3）链栈及基本运算的实现（注意指针的方向）2.队列：（1）队列的定义、特点（2）循环队列及基本运算的实现（3）链队列及基本运算的实现3.本章重点难点：（1）栈的应用（基于栈的表达式括号匹配检验、二叉树的先序/中序遍历等）（2）队列的应用（基于队列的二叉树的层序遍历、图的广度优先遍历等）第4章字符串1.串：（1）逻辑结构：定义、特点、串长、子串等（2）存储结构：定长顺序串、堆串、块链串（了解）2.本章重点难点：（1）简单模式匹配算法（2）KMP算法第5章数组和广义表1.数组：（1）数组的定义与运算、数组的顺序存储（以行序为主序存储、以列序为主序存储）（2）特殊矩阵的压缩存储：对称矩阵、三角矩阵、带状矩阵（3）稀疏矩阵的压缩存储：三元组顺序表、十字链表2.广义表（1）广义表的逻辑结构：定义、表头、表尾、长度、深度（2）广义表的存储结构：头尾链表存储、扩展线性表存储3.本章重点难点：（1）以行序（或列序）为主序存储时，数组元素地址的计算（2）稀疏矩阵的压缩存储（3）广义表的存储结构第6章树和二叉树1.树的逻辑结构：树的定义及相关术语2.二叉树的逻辑结构：二叉树的定义、特点、二叉树的5个性质、完全二叉树、满二叉树3.二叉树的存储结构：（1）顺序存储（适合满二叉树和完全二叉树）（2）链式存储：二叉链表、三叉链表4.二叉树的运算：遍历及其它运算5.树、二叉树和森林：（1）树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法（2）树和二叉树的转换、森林和二叉树的转换6.哈夫曼树：哈夫曼树的定义、特点、构造过程、哈夫曼编码7.本章重点难点：（1）二叉树的性质（2）二叉树的算法设计：基于栈的先序、中序非递归遍历，基于队列的层序遍历等（3）树的存储结构（4）哈夫曼树及哈夫曼编码第7章图1.图的逻辑结构：图的定义、图的相关术语2.图的存储结构：（1）数组表示法（又称邻接矩阵表示法）（2）邻接表（3）有向图的十字链表（4）无向图的邻接多重表3.图的运算：（1）深度优先遍历DFS、广度优先遍历BFS（算法代码设计）（2）连通图的最小代价生成树算法：Prim算法、Kruskal算法（3）拓扑排序、关键路径（4）最短路径算法：Dijkstra算法、Floyd算法4.本章重点难点：（1）图的存储结构（2）图的遍历算法设计（3）图的其它运算的逻辑过程第8章查找1.基于线性表的查找2.基于树表的查找：二叉排序树、平衡二叉树、m阶B-树3.哈希查找（1）哈希函数（重点掌握除留余数法）（2）解决冲突的方法（重点掌握线性探测再散列、链地址法）4.本章重点难点：（1）折半查找过程及分析（2）平衡二叉树的生成过程（3）哈希查找第9章内部排序1.希尔排序的过程、算法代码的阅读与设计2.快速排序的过程、算法代码的阅读与设计3.堆排序的过程、算法代码的阅读与设计。