(完整版)数据结构---C语言描述-(耿国华)-课后习题答案
第一章习题答案 2、××√ 3、(1)包含改变量定义的最小范围 (2)数据抽象、信息隐蔽 (3)数据对象、对象间的关系、一组处理数据的操作 (4)指针类型 (5)集合结构、线性结构、树形结构、图状结构 (6)顺序存储、非顺序存储 (7)一对一、一对多、多对多 (8)一系列的操作 (9)有限性、输入、可行性 4、(1)A(2)C(3)C 5、语句频度为1+(1+2)+(1+2+3)+…+(1+2+3+…+n) 第二章习题答案 1、(1)一半,插入、删除的位置 (2)顺序和链式,显示,隐式 (3)一定,不一定 (4)头指针,头结点的指针域,其前驱的指针域 2、(1)A(2)A:E、A B:H、L、I、E、A C:F、M D:L、J、A、G或J、A、G (3)D(4)D(5)C(6)A、C 3、头指针:指向整个链表首地址的指针,标示着整个单链表的开始。 头结点:为了操作方便,可以在单链表的第一个结点之前附设一个结点,该结点的数据域可以存储一些关于线性表长度的附加信息,也可以什么都不存。 首元素结点:线性表中的第一个结点成为首元素结点。 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]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 0 Int 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 0 Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(minknext->data>=mink)||(p->data<=maxk)) { printf(“参数不合法”); return ERROR; } else { p=L; while(p->next-data<=mink)
算法设计与分析第三版王晓东算法实现题部分答案_可复制编辑!
算法实现题3-7 数字三角形问题 问题描述: 给定一个由n行数字组成的数字三角形,如图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 编程任务: 对于给定的由n行数字组成的数字三角形,编程计算从三角形的顶至底的路径经过的数字和的最大值。 数据输入: 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n,1n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。 结果输出: 程序运行结束时,将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序: #include "stdio.h" void main() { int n,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in,out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i=0;row--)//从上往下递归计算 for(int col=0;col<=row;col++) if(triangle[row+1][col]>triangle[row+1][col+1]) triangle[row][col]+=triangle[row+1][col]; else triangle[row][col]+=triangle[row+1][col+1]; out=fopen("output.txt","w"); 振动时效设备https://www.doczj.com/doc/2f5222444.html,/
算法设计与分析课后习题
第一章 1. 算法分析题 算法分析题1-1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是,n^2 < 2 ^n 所以,当n >= 1时,n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为:f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以:f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为:log(n) < √n; f(n) = 2log(n); g(n)= √n 所以:f(n) = O(g(n)) (3)因为:log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以;f(n) = Ω(g(n)) (4)因为:f(n) = nlogn +n; g(n) = logn 所以:f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10)
所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为:f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1-9 证明:如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答: 因此,Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章 算法分析题
算法设计与分析 王红梅 胡明 习题答案
习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler ,1707—1783)提出并解决了该问题。七桥问题是这样描述的:一个人是否能在一次步行中穿越哥尼斯堡(现 在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经过一次, 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来,并判断此问题是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1, 一次步行 2, 经过七座桥,且每次只经历过一次 3, 回到起点 该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2.在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 ??m=n ???n=r ??r=m-n 3?输出m 3.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码和C ++描述。 编写程序,求n 至少为多大时,n 个“1”组成的整数能被2013整除。 #include using namespace std; int main() { double value=0; 图 七桥问题
for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< using namespace std; int main () { double a,b; double arctan(double x);圣经上说:神6天创造天地万有,第7日安歇。为什么是6天呢?任何一个自然数的因数中都有1和它本身,所有小于它本身的因数称为这个数的真因数,如果一个自然数的真因数之和等于它本身,这个自然数称为完美数。例如,6=1+2+3,因此6是完美数。神6天创造世界,暗示着该创造是完美的。设计算法,判断给定的自然数是否是完美数 #include using namespace std; int main() { int value, k=1; cin>>value; for (int i = 2;i!=value;++i) { while (value % i == 0 ) { k+=i;有4个人打算过桥,这个桥每次最多只能有两个人同时通过。他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的:甲过桥要用1分钟,乙过桥要用2分钟,丙过桥要用5分钟,丁过桥要用10分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥最少要用多长时间? 由于甲过桥时间最短,那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如: 第一趟:甲,乙过桥且甲回来
《算法设计与分析》课程实验与设计 福州大学 王晓东
《算法设计与分析》课程实验与设计 福州大学王晓东 第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 磁盘文件最优存储问题
《数据结构(C语言-耿国华版)》复习大纲
第一章绪论 1.数据:人们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活动的描述。凡是能被计算机输入、存储、处理和输出的一切信息都叫数据。 2.数据元素:数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据元素的组成:一个数据元素通常由一个或若干数据项组成。 数据项:指具有独立含义的最小标识单位。 3.数据对象:性质相同的数据元素的集合,是数据的一个子集。 4.数据结构:研究的是数据的逻辑结构和物理结构,以及它们之间的相互关系和所定义的算法在计算机上运行的学科。 5.算法:是对待定问题求解步骤的一种描述,是指令的有限序列。算法应满足以下性质: 1)输入性:具有零个或若干个输入量; 2)输出性:至少产生一个输出; 3)有穷性:每条指令的执行次数是有限的; 4)确定性:每条指令的含义明确,无二义性; 5)可行性:每条指令都应在有限的时间内完成。 6.评价算法优劣的主要指标: 1)执行算法后,计算机运行所消耗的时间,即所需的机器时间; 2)执行算法时,计算机所占存储量的大小,即所需的存储空间; 3)所设计的算法是否易读、易懂,是否容易转换成其他可运行的程序语言。 7.会估算某一算法的总执行时间和时间复杂度。 8.熟悉习题P32:3(5)-(9)、4(2)(3) 第二章线性表 1.线性表(P7):是性质相同的一组数据元素序列。 线性表的特性: 1)数据元素在线性表中是连续的,表中数据元素的个数可以增加或减少,但调整后数据元素仍必须是连续的,即线性表是一种线性结构。 2)数据元素在线性表中的位置仅取决于自己在表中的序号,并由该元素数据项中的关键字(key)加以标识。 3)线性表中所有数据元素的同一数据项,其属性是相同的,数据类型也是一致的。 线性表的主要运算有:插入、删除、查找、存取、长度、排序、复制、合并。 线性表的顺序存储结构及特点(就是把表中相邻的数据元素存放在内存邻接的存储单元,这种存储方法叫做顺序分配,又称顺序映像。其特点:逻辑上相邻的数据元素, 它们的物理次序也是相邻的。),存储地址的计算方式(Loc(a i )=Loc(a )+i*s)。 2.线性表的查找、插入和删除 熟悉线性表的查找算法(P38)、插入算法(P39)和删除算法(P40)。 3.理解线性表的顺序存储结构的优缺点。 4.熟悉线性链表的存储结构(P43) 线性链表(由若干结点链接而成的一种存储结构。)、结点(由存放数据元素值的部分—数据域和存放另一元素存储地址的部分—指针域或链域两部分信息组成的存储结构。)、单链表(线性链表)的概念。 5.熟悉线性链表的建立(P45-47)、查找(P47-48)、插入(P49-50)和删除(P50-51)的算法; 6.明了什么是循环链表(链表中最后一个结点指针域回指向链表的第一个结点,使得整个链表通过链指针成为一个环形,这种形式的链表称为循环链表。)? 7.明了双向链表的结构(链表中的每个结点有两个指针域,一个是向前链接的左指针(Lnext或prior),另一个是向后链接的右指针(Rnext或next),同时还有一个数据域(Data)。);了解双向链表的插入和删除的算法。 8.理解链表的优缺点(P48)。 9.熟悉习题P68:1、2 第三章限定性线性表----栈和队列 1.栈和队列 明确什么是栈及其特点(只允许在一端进行插入和删除的线性表。允许插入和删除
最新算法设计与分析复习要点(1)
算法设计与分析的复习要点 第一章:算法问题求解基础 算法是对特定问题求解步骤的一种描述,它是指令的有限序列。 一.算法的五个特征: 1.输入:算法有零个或多个输入量; 2.输出:算法至少产生一个输出量; 3.确定性:算法的每一条指令都有确切的定义,没有二义性; 4.可行性:算法的每一条指令必须足够基本,它们可以通过已经实现的基本运算执行有限次来实现; 5.有穷性:算法必须总能在执行有限步之后终止。 二.什么是算法?程序与算法的区别 1.笼统地说,算法是求解一类问题的任意一种特殊的方法;较严格地说,算法是对特定问题求解步骤的一种描述,它是指令的有限序列。 2.程序是算法用某种程序设计语言的具体实现;算法必须可终止,程序却没有这一限制;即:程序可以不满足算法的第5个性质“有穷性”。 三.一个问题求解过程包括:理解问题、设计方案、实现方案、回顾复查。 四.系统生命周期或软件生命周期分为: 开发期:分析、设计、编码、测试;运行期:维护。 五.算法描述方法:自然语言、流程图、伪代码、程序设计语言等。 六.算法分析:是指对算法的执行时间和所需空间的估算。算法的效率通过算法分析来确定。 七.递归定义:是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分:基础情况和递归部分; 基础情况:以直接形式明确列举新事物的若干简单对象; 递归部分:有简单或较简单对象定义新对象的条件和方法 八.常见的程序正确性证明方法: 1.归纳法:由基础情况和归纳步骤组成。归纳法是证明递归算法正确性和进行算法分析的强有力工具; 2.反证法。 第二章:算法分析基础 一.会计算程序步的执行次数(如书中例题程序2-1,2-2,2-3的总程序步数的计算)。二.会证明5个渐近记法。(如书中P22-25例2-1至例2-9) 三.会计算递推式的显式。(迭代法、代换法,主方法) 四.会用主定理求T(n)=aT(n/b)+f(n)。(主定理见P29,如例2-15至例2-18)五.一个好的算法应具备的4个重要特征: 1.正确性:算法的执行结果应当满足预先规定的功能和性能要求; 2.简明性:算法应思路清晰、层次分明、容易理解、利于编码和调试; 3.效率:算法应有效使用存储空间,并具有高的时间效率; 4.最优性:算法的执行时间已达到求解该类问题所需时间的下界。 六.影响程序运行时间的主要因素: 1.程序所依赖的算法; 2.问题规模和输入数据规模; 3.计算机系统性能。 七.1.算法的时间复杂度:是指算法运行所需的时间;
算法设计与分析第一章习题解1.1,1.10,1.15
1.15练习 1.1(a) 1)A[1…60] = A[(1+60)/2]=A[30]=40 由于33<40,舍弃A[30…60]; 2)A[1…29] = A[(1+29)/2]=A[15]=25 由于33>25,舍弃A[1…15]; 3) A[16…29]= A[(16+29)/2]=A[22]=32 由于33>32,舍弃A[16…22]; 4) A[23…29] = A[(23+29)/2]=A[26]=36 由于33<36,舍弃A[26…29]; 5) A[23…25] = A[(23+25)/2]=A[24]=34; 由于33<34,舍弃A[24, 25]; 6) A[23] = 11 12 13 … 68 69 70 11 12 13 … 37 38 39 26 27 28 … 37 38 39 33 34 35 36 37 38 39 33 34 35 33
由于33=33,搜索完毕。 综上,搜索33共执行了6次比较。 同理可得(b )搜索7共执行了5次比较。 (c )搜索70共执行了6次比较。 (d )搜索77共执行了6次比较。 1.10 对11 12 1 5 15 3 4 10 7 2 16 9 8 14 13 6用bottomupsort 算法,按非降序排列。 解:用图示,如下进行。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 3 4 5 10 11 12 15 1 5 11 1 2 1.15用Θ表示函数。 (b) 2 6 7 8 9 1 3 1 4 16 3 4 10 1 5 2 7 9 1 6 6 8 13 14 11 12 1 5 15 3 4 10 2 7 9 16 8 14 6 13
算法设计与分析C++语言描述(陈慧南版)课后答案
第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数,程序1-2的while 循环体做了10次,程序1-3的while 循环体做了14141次(14142-2循环) 若考虑其他语句,则没有这么多,可能就601倍。 第二章 32P 2-8.(1)画线语句的执行次数为log n ??? ?。(log )n O 。划线语句的执行次数应该理解为一格整体。 (2)画线语句的执行次数为 111 (1)(2)16 j n i i j k n n n ===++= ∑∑∑。3 ()n O 。 (3)画线语句的执行次数为 。O 。 (4)当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++, 当n 为偶数时画线语句的执行次数为 2(2)4 n +。2 ()n O 。 2-10.(1) 当 1n ≥ 时,225825n n n -+≤,所以,可选 5c =,01n =。对于0n n ≥, 22()5825f n n n n =-+≤,所以,22582()n n n -+=O 。 (2) 当 8n ≥ 时,2222582524n n n n n -+≥-+≥,所以,可选 4c =,08n =。对于0n n ≥, 22()5824f n n n n =-+≥,所以,22582()n n n -+=Ω。 (3) 由(1)、(2)可知,取14c =,25c =,08n =,当0n n ≥时,有22212582c n n n c n ≤-+≤,所以2 2 582()n n n -+=Θ。 2-11. (1) 当3n ≥时,3 log log n n n <<,所以()20log 21f n n n n =+<,3 ()log 2g n n n n =+>。可 选 21 2 c = ,03n =。对于0n n ≥,()()f n cg n ≤,即()(())f n g n =O 。注意:是f (n )和g (n )的关系。
算法设计与分析第三章课后答案吕国英主编.
2、#include void main() { int a[6][6],b[6],i,j; printf("请输入6个整数:"); for(i=0;i<6;i++) { scanf("%d",&b[i]); } for(i=0;i<6;i++) { a[0][i]=b[i]; } for(i=1;i<=5;i++) a[i][0]=b[6-i]; for(i=1;i<=5;i++) for(j=1;j<=5;j++) { a[i][j]=a[i-1][j-1]; } for(i=0;i<=5;i++) { for(j=0;j<=5;j++) printf("%d ",a[i][j]); printf("\n"); } } 3、#include void main() { int i,j,count,n; int a[100][100]; printf("请输入矩阵的阶n="); scanf("%d",&n); count=1; for(i=1;i<=n/2;i++) { for(j=i;j<=n-i+1;j++)//上侧 { a[i][j]=count; count++; } for(j=i+1;j<=n-i;j++)//右侧 {
a[j][n-i+1]=count; count++; } for(j=n-i+1;j>=i+1;j--)//下侧 { a[n-i+1][j]=count; count++; } for(j=n-i+1;j>=i+1;j--)//左侧 { a[j][i]=count; count++; } } if(n%2==1) { i=(n+1)/2; a[i][i]=n*n; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%2d ",a[i][j]); printf("\n"); } } 4、#include void main() { int i,j,n,a[100][100],count=1; printf("请输入方阵的阶n:"); scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=i;j++) { a[i-j+1][j]=count; count++; } for(i=1;i<=n;i++) { for(j=1;j<=n-i+1;j++) printf("%4d",a[i][j]); printf("\n");