算法设计与分析c语言描述课后答案

C语言程序设计教程课后习题答案第一章C语言程序设计概述－习题答案1算法的描述有哪些基本方法？答1、自然语言2、专用工具2C语言程序的基本结构是怎样的？举一个例子说明。

答1、C语言程序由函数构成；2、“/*”与“*/”之间的内容构成C语言程序的注释部分；3、用预处理命令#include、#define可以包含有关文件或预定义信息；4、大小写字母在C语言中是有区别的；5、除main()函数和标准库函数外，用户也可以自己编写函数，应用程序一般由多个函数组成，这些函数指定实际所需要做的工作。

3C语言有什么特点？答1、具有结构语言的特点，程序之间很容易实现段的共享；2、主要结构成分为函数，函数可以在程序中被定义完成独立的任务，独立地编译代码，以实现程序的模块化；3、运算符丰富，包含的范围很广；4、数据类型丰富；5、允许直接访问物理地址，即可直接对硬件进行损伤，实现汇编语言的大部分功能；6、限制不太严格，程序设计自由度大，这样使C语言能够减少对程序员的束缚；7、生成的目标代码质量，程序执行效率高，同时C语言编写的程序的可移植性好。

4★指出合法与不合法的标识符命名。

答AB12--√ leed_3-- a*b2--× 8stu--× D.K.Jon--× EF3_3--√ PAS--√ if--×XYZ43K2--√ AVE#XY--× _762--√ #_DT5--× C.D--×5说明下列Turbo C热键的功能。

答F2:源文件存盘 F10:调用主菜单 F4:程序运行到光标所在行（用于调试程序）Ctrl+F9:编译并链接成可执行文件 Alt+F5:将窗口切换到 DOS 下，查看程序运行结果。

6说明下列Turbo C方式下输入并运行下列程序，记录下运行结果。

①main(){printf("********************\n");printf(" welcome you \n");printf(" very good \n);printf("********************\n");}②main(){ int a,b,c,t;printf("please input three numbers;");scanf("%d,%d,%d",&a,&b,&c); /*教材S是错误的*/t=max(max(a,b),c);printf("max number is:%d\n",t);}int max(int x, int y){ int z;if(x>y)z=x;else z=y;return(z);}答运行结果：********************welcome youvery good********************运行结果：please input three numbers;3,1,4 /*左侧下划线内容为键盘输入*/max number is:47一个C程序是由若干个函数构成的，其中有且只能有一个＿＿＿函数。

《C语言程序设计》课后习题参考答案第1章C语言及程序设计概述1.单选题（1）A （2）B （3）A （4）B （5）C2.填空题（1）//，/*…*/（2）scanf（）（3）printf（）3.判断题（1）对(2)错（3）错（4）对第二章：数据类型运算符与表达式1.单选题（1）C （2）D （3）C （4）B （5）C （6）A （7）B （8）D （9）A（8）D（9）A（10）B（11）C（12）C（13）D（15）B（16）C（17）A（18）A（19）B（20）C（21）C（22）D（23）C（24）A（25）D（26）B（27）C（28）B（29）B（30）A2.填空题（1）sqrt(pow(y,x)+log10(y)) （2）36（3）6（4）3 3（6）36（7）int x=8,y=8;（8）1（9）E（10）6,7,8,9（11）6（12）66,96（13）240（14）1,1,-1,-1（15）5,2,6（16）1（17）！（18）2（19）(a>0&&a<101)&&(a%3==0||a%7==0) （20）A3.程序分析题（1）2 72 74 94 412 12116（3）100 d 68 D97 a 49 1 （4）0 1 0 1 （5）2 4 6 7-0.58 7046.587.5（6）33 12 113 13 082 32（7）618 30181814.改错题（1）①无初始赋值，不能输出②数据精度丢失③少“；”号④单字符变量不能保存字符串常量⑤不能连续初始化⑥非法标识符（2）short i=38000溢出PI=3.1416 常量不能修改值Printf(“%d”,x%y) %必须是整数a*=(b+c)/=d符合赋值左边不能是表达式第三章：算法概念与顺序结构程序设计1.选择题（1）D（2）B、D（3）D（4）B（5）C（6）A（8）C（9）B（10）D2．填空题.（1）一条语句；（2）小于左右（3）%%（4）输出项列表输出控制符（5）取地址取a的地址（6）从盘获取一个字符（7）大括号（8）f=68.00（9）n1=%d\n n2=%d（10）7,5,c=33．程序分析题.（1）i=100,c=a,f=1.234000（2）65535,65536（10）1234,123.5,12345.5第四章：选择结构程序设计（1）C （2）B （3）B （4）B （5）D （6）D （7）D （8）A （9）B （10）A （11）B （12）B （13）D （14）A （15）C （16）A （17）C （18）D （19）B （20）D （21）A（23）A（24）A2．填空题.（1）1（2）5 8 8（3）4 5 99（4）2（5）10 20 0（6）2 1（7）-4（8）3（9）No（10）25（11）45 45（12）0（13）5.5（14）13（15）3第五章：循环结构程序设计（1）C（2）A（3）D（4）B（5）D（6）B（7）A A或B（8）输出4444（9）B（10）A（11）B（12）C（13）A（14）B2．填空题.（1）r=m;m=n;n=rm%n（2）3（3）-5（4）i%3==2&&i%5==3&&i%7==2 j==5j!=k（6）int s=8,j=i+2k+i+j==8（7）8（8）k&&i<=500 k/10 continue第六章：数组1.选择题（1）B（2）C（3）D（4）D（5）B（6）C（7）B（8）A（9）A（10）D2．填空题.（1）按行序优先的原则（2）0 9（4）1 2（5）6（6）前者以回车后者以空格或回车作为间隔符（7）gets（）（8）&a[i]（9）char k -1（10）9 83．程序分析题.（1）1 3 7 15（2）0 0 0（3）读取输入字符串中数字字符（4）①if(str1==str2) (strcmp(str1,str2)==0)②&c1[0]③m[i][k-1]第七章：函数的调用1.选择题（1）B（2）C（3）C（4）A（6）D（7）D（8）D（9）B（10）D（11）A（12）A（13）B（14）B2．填空题.（1）有参无参（2）顺序类型（3）定义调用（4）①fmax(a,N) ②s[k]=s[p]（5）①age(n-1)+2 ②age(5)（6）①prt(c,n-1) ②prt(…‟,n-i) ③prt(…*‟,2*i-1) 3．程序分析题.（1）h l o（2）3（3）2 6（4）5 25。

函数一、选择题1-5 ADCBD 6-10 DADAC11-15 DBDCC 16-17 DC二、填空题（1）3,2,2,3 （2）4,3,5 （3）t*10 （4）double max 从键盘上输入两个数据,输出最大值（5）m=fun(a,4)+fun(b,4)-fun(a+b,3) （6）a=1.0；b=1.0；s=1.0；（7）x x*x+1 （8）9 （10）-f指针一、选择题1-5 CADBC 6-10 CAACD 11-15 CACBD 16-20 ACCAA二、填空题（1）3 5 （2）5 3 （3）k *k （4）8 4 （5）0 7数组与指针一、选择题1-5 CBDCA 6-10 DCDAB 11-15 CADAD 16-20 BCBDD 21-25 ABBAC 26-30 DBDDB31-33 CCA二、填空题（1）1111 （2）24 （3）6 （4）19 （5）6 （6）5756 （7）2 4（8）1 2 3 （9）92 （10）580 5 60 0 9数组与函数一、选择题1-5 BADCA 6-10 BABCA 11-15 BACDA 16-17 BC二、填空题（1）s=18 （2）11 （3）br[i] （4）j<i a[i][j]=a[j][i] （5）x[i][i] x[i-1][j-1]+x[i-1][j]（6）a[k][i] *sum x,&s （7）row a[row][colum] （8）j+1 i%2==1 （9）a[row][col]>max max<min字符串一、选择题1-5 CDAAC 6-10 ACBCB 11-15 DABDD 16-20 BCBDC 21-25 BDCBB 26-30 DAAAC31-35 CDDCA二、填空题（1）abcfg（2）efgh（3）*t（4）bcdefgha（5）gae（6）*2*4*6*8*（7）*t++（8）cdeab （9）s-1 *s++ （10）p+n（11）str+strlen(str)-1 t==0 huiwen(str) （12）s[i]>='0'&&s[i]<='9' （13）c=getchar() 1对C语言的深入讨论一、选择题1-5 CDCDB 6-10 DACDA 11-15 ADBDC 16-20 CAADA 21-25 CDDCB 26-28 DC 二、填空题（1）findbig （2）c（3）!knahT （4）3*sizeof(double) 1.50,2.50,3.75 （5）11110111 （6）/i结构体与共用体一、选择题1-5 DBDCB 6-10 CDBAD 11 (1)C (2)A (3)B 12-16 ACBDD二、填空题（1）struct node * （2）sizeof(struct node) （3）p!=NULL p->next （4）->next->data （5） 2002shangxian （6）struct DATE d={2006,10,1}；文件一、选择题1-5 CDDBA 6-10 BCDCA 11-15 DBADA 16-17 DB二、填空题（1）"d1.dat","rb" （2）"a" （3）!feof(fp) （4）"wb""rb" （5）Hell （6）fopen ftell。

数据结构与算法分析：C语⾔描述（原书第2版简体中⽂版！！！）PDF+源代码+习题答案转⾃：/Linux/2014-04/99735.htm数据结构与算法分析：C语⾔描述（原书第2版中⽂版！！！） PDF+源代码+习题答案数据结构与算法分析：C语⾔描述（原书第2版）是《data structures and algorithm analysis in c》⼀书第2版的简体中译本。

原书曾被评为20世纪顶尖的30部计算机著作之⼀，作者mark allen weiss在数据结构和算法分析⽅⾯卓有建树，他的数据结构和算法分析的著作尤其畅销，并受到⼴泛好评．已被世界500余所⼤学⽤作教材。

在本书中，作者更加精炼并强化了他对算法和数据结构⽅⾯创新的处理⽅法。

通过c程序的实现，着重阐述了抽象数据类型的概念，并对算法的效率、性能和运⾏时间进⾏了分析。

数据结构与算法分析：C语⾔描述（原书第2版） PDF下载：百度⽹盘免费下载地址：（本⼈是从这⾥下载的，感谢原博主）全书特点如下： ●专⽤⼀章来讨论算法设计技巧，包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法 ●介绍了当前流⾏的论题和新的数据结构，如斐波那契堆、斜堆、⼆项队列、跳跃表和伸展树 ●安排⼀章专门讨论摊还分析，考查书中介绍的⼀些⾼级数据结构 ●新开辟⼀章讨论⾼级数据结构以及它们的实现，其中包括红⿊树、⾃顶向下伸展树。

treap树、k-d树、配对堆以及其他相关内容 ●合并了堆排序平均情况分析的⼀些新结果⽬录出版者的话专家指导委员会译者序前⾔第1章引论第2章算法分析第3章表、栈和队列第4章树第5章散列第6章优先队列（堆）第7章排序第8章不相交集ADT第9章图论算法第10章算法设计技巧第11章摊还分析第12章⾼级数据结构及其实现索引。

数据结构与算法分析c语言描述中文答案一、引言数据结构与算法是计算机科学中非常重要的基础知识，它们为解决实际问题提供了有效的工具和方法。

本文将以C语言描述中文的方式，介绍数据结构与算法分析的基本概念和原理。

二、数据结构1. 数组数组是在内存中连续存储相同类型的数据元素的集合。

在C语言中，可以通过定义数组类型、声明数组变量以及对数组进行操作来实现。

2. 链表链表是一种动态数据结构，它由一系列的节点组成，每个节点包含了数据和一个指向下一个节点的指针。

链表可以是单链表、双链表或循环链表等多种形式。

3. 栈栈是一种遵循“先进后出”（Last-In-First-Out，LIFO）原则的数据结构。

在C语言中，可以通过数组或链表实现栈，同时实现入栈和出栈操作。

4. 队列队列是一种遵循“先进先出”（First-In-First-Out，FIFO）原则的数据结构。

在C语言中，可以通过数组或链表实现队列，同时实现入队和出队操作。

5. 树树是一种非线性的数据结构，它由节点和边组成。

每个节点可以有多个子节点，其中一个节点被称为根节点。

在C语言中，可以通过定义结构体和指针的方式来实现树的表示和操作。

6. 图图是由顶点和边组成的数据结构，它可以用来表示各种实际问题，如社交网络、路网等。

在C语言中，可以通过邻接矩阵或邻接表的方式来表示图，并实现图的遍历和查找等操作。

三、算法分析1. 时间复杂度时间复杂度是用来衡量算法的执行时间随着问题规模增长的趋势。

常见的时间复杂度有O(1)、O(log n)、O(n)、O(n^2)等，其中O表示“量级”。

2. 空间复杂度空间复杂度是用来衡量算法的执行所需的额外内存空间随着问题规模增长的趋势。

常见的空间复杂度有O(1)、O(n)等。

3. 排序算法排序算法是对一组数据按照特定规则进行排序的算法。

常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等，它们的时间复杂度和空间复杂度各不相同。

Program算法设计与分析基础中文版答案习题1.15..证明等式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//输出:实根或者无解信息If a≠0D←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. 这个断言是正确的。

数据结构与算法分析c语言描述中文答案【篇一：数据结构(c语言版)课后习题答案完整版】选择题：ccbdca6．试分析下面各程序段的时间复杂度。

（1）o（1）（2）o（m*n）（3）o（n2）（4）o（log3n）（5）因为x++共执行了n-1+n-2+??＋1= n(n-1)/2，所以执行时间为o（n2）（6）o(n)第2章线性表1．选择题babadbcabdcddac 2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

elemtype max (linklist l ){if(l-next==null) return null;pmax=l-next; //假定第一个结点中数据具有最大值 p=l-next-next; while(p != null ){//如果下一个结点存在if(p-data pmax-data) pmax=p;p=p-next; }return pmax-data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

void inverse(linklist l) { // 逆置带头结点的单链表 l p=l-next; l-next=null; while ( p) {q=p-next; // q指向*p的后继p-next=l-next;l-next=p; // *p插入在头结点之后p = q; }}（10）已知长度为n的线性表a采用顺序存储结构，请写一时间复杂度为o(n)、空间复杂度为o(1)的算法，该算法删除线性表中所有值为item的数据元素。

[题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。

本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。

因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。

第一章R 51-3.最大公约数为1。

快1414倍。

主要考虑循环次数，程序1-2的while 循环体做了 10次，程序1-3的while 循环体做了 14141次（14142-2 循环） 若考虑其他语句，则没有这么多，可能就 601倍。

第画线语句的执行次数为 T n 。

2-10. （1） 当F 1 2时,5n 8n2 5n 2 ，所以，可选c 5 , n 0 1 o 对于nn,f(n) 5n 28n 2 5n 2，所以，5n 2 8n 2(n 2)。

（2） 当F8时，L 2ccL25n 8n 2 5n2n 224n ，所以，可选c 4 ,n 0 8。

对于n n 0,f(n) 5n 28n 2 4n 22，所以，5n8n 2 (n 2)。

（3） 由（1 ）、（: 2 )可 '知，取 G 4, c 2 5 ,n 。

8，当n n 0时，有2qn 5n 28n2qn' 「，所以5n28n 2 (n 2）。

2-11. (1) 当 n 3 时，log nlog 3n ，所以 f (n) 20n logn 21n ， g(n)n log 3n 2n 。

可选 21一，n o 3。

对于 n 2 n o ，f(n) cg(n)，即 f(n)（g （n ））。

注意：是f （n ）和g （n ）的关系。

(2) 2 2log n ，所以 f (n) n /log nn 2，g(n) n log 2 n n 2。

可选 c 1，n o 对于 n n o ， f(n) 2n cg(n)，即 f(n) (g(n))。

因为 f(n) (log n)lognjogdogn)，g(门)门/ log n n log n 2。

当 F4 时，f(n) nlog(logn)2-8. （1）画线语句的执行次数为logn 。

（log n ）。

划线语句的执行次数应该理解为一格整体。

(2)画线语句的执行次数为 n(n 1)(n 2)。

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. 这个断言是正确的。