下载文档原格式
算法与数据结构---C语言描述（第三版）第1章绪论1、解释以下概念：逻辑结构，存储结构，操作，数据结构，数据结构的表示，数据结构的实现，抽象数据类型，算法，算法的时间代价，算法的空间代价，大O表示法，贪心法，回溯法，分治法。
答：(1)逻辑结构（数学模型）：①指数据元素之间地逻辑关系。
②具体解释：指数学模型（集合，表，树，和图）之间的关系。
③描述方式：B = <K,R>, K是节点的有穷集合，R是K上的一个关系。
(2)存储结构（物理结构）：数据的逻辑结构在计算机存储器中的映射（或表示）。
(3) 操作（行为）：指抽象数据类型关心的的各种行为在不同的存储结构上的具体算法（或程序）。
(4) 数据结构：①传统观念：数据结构是计算机中表示（存储）的、具有一定逻辑关系和行为特征的一组数据。
②根据面向对象的观点：数据结构是抽象数据类型的物理实现。
(5) 数据结构的表示：(6) 数据结构的实现：(7) 抽象数据类型：(8) 算法：是由有穷规则构成（为解决某一类问题）的运算序列。
-算法可以有若干输入（初始值或条件）。
-算法通常又有若干个输出（计算结果）。
-算法应该具有有穷性。
一个算法必须在执行了有穷步之后结束。
-算法应该具有确定性。
算法的每一步，必须有确切的定义。
-算法应该有可行性。
算法中国的每个动作，原则上都是能够有机器或人准确完成的。
(9) 算法的时间代价：(10) 算法的空间代价：(11) 大O表示法：-更关注算法复杂性的量级。
-若存在正常数c和n0，当问题的规模n>=c*f(n), 则说改算法的时间（或空间）代价为O（f(n)）(12) 贪心法：当追求的目标是一个问题的最优解是，设法把整个问题的求解工作分成若干步来完成。
在其中的每一个阶段都选择都选择从局部来看是最优的方案，以期望通过各个阶段的局部最有选择达到整体的最优。
例如：着色问题：先用一种颜色尽可能多的节点上色，然后用另一种颜色在为着色节点中尽可能多的节点上色，如此反复直到所有节点都着色为止；(13) 回溯法有一些问题，需要通过彻底搜索所有的情况寻找一个满足某些预定条件的最优解。
算法设计与分析第三版第四章课后习题答案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)。
第1章概述习题(答案)一．选择题1. D2. B3. CD4. C5.A6. ABC7. A8. C9.B 10. B11. C12. A13. ABC14.B 15. ABCD16.C 17.ABCDE二．简答题1．简述计算机的发展阶段计算机的出现是20世纪最辉煌的成就之一，按照采用的电子器件划分，计算机大致经历了四个阶段。
1. 第一代计算机(1946—1957)其主要特征是逻辑器件使用了电子管，用穿孔卡片机作为数据和指令的输入设备，用磁鼓或磁带作为外存储器，使用机器语言编程。
第一台计算机需要工作在有空调的房间里，如果希望它处理什么事情，需要把线路重新连接接，把成千上万的线重新焊接。
1949年发明了可以存储程序的计算机，这些计算机使用机器语言编程，可存储信息和自动处理信息，存储和处理信息的方法开始发生革命性的变化。
第一代计算机体积大、运算速度低、存储容量小、可靠性低。
几乎没有什么软件配置，主要用于科学计算。
尽管如此，第一代计算机却奠定了计算机的技术基础，如二进制、自动计算及程序设计等，对以后计算机的发展产生了深远的影响。
其代表机型有：ENIAC、IBM650(小型机)、IBM709(大型机)等。
2. 第二代计算机(1958—1964)其主要特征是使用晶体管代替了电子管，内存储器采用了磁芯体，引入了变址寄存器和浮点运算部件，利用I/O处理机提高了输入输出能力。
这不仅使得计算机的体积缩小了很多，同时增加了机器的稳定性并提高了运算速度，而且计算机的功耗减小，价格降低。
在软件方面配置了子程序库和批处理管理程序，并且推出了Fortran、COBOL、ALGOL等高级程序设计语言及相应的编译程序，降低了程序设计的复杂性。
除应用于科学计算外，它还开始应用在数据处理和工业控制等方面。
其代表机型有IBM7090、IBM7094、CDC7600等。
3. 第三代计算机(1965—1972)其主要特征是用半导体中、小规模集成电路(Integrated Circuit，IC)作为元器件代替晶体管等分立元件，用半导体存储器代替磁芯存储器，使用微程序设计技术简化处理机的结构，这使得计算机的体积和耗电量显著减小，而计算速度和存储容量却有较大提高，可靠性也大大加强。
信息与数据信息是人们对某种事物的理解，通常可以是一件事情、一种状况或者是基于研究和经验所获得的知识。
数据是信息的表达。
例如，在线书店必须记录图书的书名、作者、客户、订单、书籍评论、书籍版本、送货等非常多的信息。
不同的用户所要保存和使用的数据各不相同，具体应该保存哪些数据由业务需求决定，保存数据的目的是使业务的运作更有效。
在任何数据库中，一般都保存有两种类型的数据：∙静态的，或者是历史的数据。
∙动态的，或者是事务性的数据。
文件系统最早用计算机实现对数据的管理是使用文件方式进行的，然而，文件的组织结构往往与生成该文件的程序有关，其他人要共享该文件，就必须要熟悉文件的格式等信息。
这为共享信息带来了诸多不便。
通过文件共享数据，还有一致性修改的问题，即如果文件结构被修改了，则共享者的程序也要相应地做修改，否则就会出错。
数据以文件形式保存，不仅使读文件的程序可以多次使用，而且其他程序只要知道数据格式和组织方式也可以使用，这就叫做数据资源共享。
商业应用中数据共享是必须的。
数据库系统信息共享和信息的易维护性是信息管理发展的必然要求。
为了解决这些问题，产生了数据库技术。
数据库技术的发展主要是用来克服文件系统的缺陷，克服这些缺陷主要是在应用程序和数据库之间增加了一个功能强大的软件——DBMS。
下图说明了在数据库系统中，数据库用户、数据库应用程序及数据库管理系统之间的关系。
用户与数据库应用程序交互，数据库应用程序与DBMS交互，由DBMS负责访问数据库中的数据。
也就是应用程序不直接与数据库打交道。
而在文件处理系统中，应用程序是直接访问存储数据的文件的。
这个改变非常重要，它使得编程工作变得非常简单，因为应用程序不再需要关心数据的记录结构和物理存储方式。
这样，开发人员就可以将注意力集中在如何满足用户的需要上，而不必集中在计算机系统如何组织数据的问题上。
从上述分析可以看到数据库具有如下特点：∙数据是集成的∙数据重复少∙程序与数据相对独立∙容易提供符合用户不同要求的信息提取方式∙易于提供安全保障9.2 数据模型模型是指明事物本质的方法，是对事物、现象、过程等客观系统的简化描述，是理解系统的思维工具。
计算机数学基础（第三版）习题参考答案第1-3章习题1.11．（1）D （2）A （3）A （4）D （5）D （6）C （7）C （8）D （9）C 2．（1）]14,6[],3,2[-=-=f fR D ; （2）];1,0[],1,1[=-=f fR D（3）);,0[),,(+∞=+∞-∞=f fR D （4）);,0[),,(+∞=+∞-∞=f fR D（5）]1,1[),,(-=+∞-∞=f fR D3．（1）（2）不同；（3）（4）相同。
4．（1）];2,2[-=fD （2）),1()1,(+∞-∞= fD（3）RDf= （4）},,01|),{(R y R x y x y x Df∈∈>++= 5．（1）2010+-=h T （2）斜率10-=k （3）C ︒-5 6．（1）有界，]3,1[=fR ； （2）有界，]56,25.0[-=fR；（3）无界，),0(+∞=fR； （4）有界，)1,0(=fR。
7．（1）非奇非偶函数；（2）偶函数；（3）偶函数；（4）偶函数。
8．（1）周期函数，周期为π2；（2）不是周期函数；（3）周期函数，周期为π； 9．（1）1；（2）2。
10．（1）);,(,15))(()(23+∞-∞=-+=++g f R x xx g f);,(,1))(()(23+∞-∞=+-=--g f R x x x g f );,(,263))(()(2345+∞-∞=+-+=fg R x x x x x fg),33()33,33()33,(,132))(/()/(223+∞---∞=-+= g f R x x x x g f（2）]1,1[,11))(()(-=-++=++g f R x x x g f]1,1[,11))(()(-=--+=--g f R x x x g f]1,1[,1))(()(2-=-=fg R x x fg)1,1[,11))(/()/(-=-+=g f R xxx g f11．（1）),(,62118))(()(2+∞-∞=++=g f R x xx g f),(,236))(()(2+∞-∞=+-=f g R x x x f g),(,88))(()(234+∞-∞=+--=f f R x x x x x f f),(,89))(()(+∞-∞=+=g g R x x g g（2）),0()0,(,21))(()(3+∞-∞=+= g f R xxx g f),0()0,(,21))(()(3+∞-∞=+=f g R x xx f g),0()0,(,))(()(+∞-∞== f f R x x f f),(,410126))(()(3579+∞-∞=++++=g g R x x x x x x g g12．（1）9,)(5-==x u uu F （2）xu u u F ==,sin )(（3）1,ln )(2+==x u u u F （4）3,1)(+==x u u u F13．（1）xx x f2351)(1+-=-； （2）2)(11-=--x e x f； （3）xx x f -=-1log )(21；（4）⎩⎨⎧<≤--≤≤--=-.01,01,1)(1时当时当x x ；x x x f14．（1）由ue y =，x u arctan =复合而成； （2）由x v v u u y ln ,ln ,ln ===复合而成； （3）由x v v u u y sin ,,ln 3===复合而成。
第一章信息与计算机1.1 什么是信息？信息与数据的区别和联系在何处？信息定义之一：信息是现实世界中存在的客观实体、现象、关系进行描述的数据。
信息定义之二：信息是经过加工后并对实体的行为产生影响的数据。
与数据的区别和联系：数据定义：数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。
我们把这些数据收集起来，经过处理后，即得到人们需要的信息。
信息和数据的关系可以归结为： 1. 信息是有一定含义的数据。
2. 信息是经过加工（处理）后的数据。
3. 信息是对决策有价值的数据。
1.2 信息有哪些基本属性？信息的基本属性有： 1. 事实性。
2. 等级性。
3. 可压缩性。
4. 可扩散性。
5. 可传输性。
6. 共享性。
7. 增值性和再生性。
8. 转换性。
1.3 计算机的主要特点是什么？计算机最主要的特点是： 1. 高速自动的操作功能。
2. 具有记忆的能力。
3. 可以进行各种逻辑判断。
4. 精确高速的计算能力。
1.5 完整的计算机系统应该包括哪几部分？目前最完整的计算机系统学说认为由五部分组成： 1. 人员 2. 数据 3. 设备 4. 程序 5. 规程1.6 什么是计算机硬件？什么是计算机软件？硬件：泛指实际存在的物理设备，包括计算机本身及其外围设备。
微型计算机的硬件系统：主机、外存储器、输入设备、输出设备、微机的系统总线。
软件：是指计算机程序、方法、规则的文档以及在计算机上运行它时所必须的数据。
计算机软件一般分为系统软件和应用软件。
1.8 软件技术发展的几个阶段各有什么特点？它与硬件的关系如何？第一阶段：高级语言阶段特点：这一时期，编译技术代表了整个软件技术，软件工作者追求的主要目的是设计和实现在控制结构和数据结构方面表现能力强的高级语言。
但在这一时期内，编译系统主要是靠手工编制，自动化程度很低。
硬件关系：此时期计算机的硬件要求仅能用机器指令来编制可运行的程序。
第二阶段：结构程序设计阶段特点：在程序的正确性方面，提出了结构化程序设计思想使程序的可靠性提高了。
精心整理计算机导论课后习题答案汇编第一章一、简答题1、什么是计算机？计算机系统是一种能够按照事先存储的程序，自动、高速的对数据进行输入、处理、输出和存储的系统。
一个计算机系统包括硬件和软件两大部分。
2、解释冯·诺依曼所提出的\存储程序\概念。
运算速度快`精度高4、计算机有哪些主要的用途？（1）科学计算（2）数据处理(3)实时控制（4）人工智能（5）计算机辅助工程和辅助教育（6）娱乐和游戏5、计算机发展中各个阶段的主要特点是什么？第一代计算机特征是采用电子管作为主要元器件第二代计算机特征是采用晶体管作为主要器件第三代计算机特征是半导体中小规模集成电路第四代计算机特征是大规模和超大规模集成电路6信息化社会的主要特点是什么？1·建立完善的信息基础设施2·采用现金的信息技术3·建立广泛的信息产业4·拥有高素质的信息人才5·构建良好的信息环境7、信息化社会对计算机人才的素质和知识结构有哪些要求？在信息化社会中所需要的计算机人才是多方位的，不仅需要研究型、设计型的人才，而且需要应用型的人才；不仅需要开发型人才而且需要维护型、服务型、操作型的人才。
要求计算机人才具有较高的综合素质和创新能力，8、9计算机科学的研究范畴主要包括哪些？第二章一简答题1什么是数制？3个特点？按进位的原则进行计数称为（2）最大的数字比基数小1（2（1乘法运算法则0*0=00*1=01*0=01*1=13十进制整数转换为非十进制证书的规则是什么？（1）十进制整数转换为非十进制整数除基取余，先余为低，后余为高。
（2）乘基取整，先整为高，后整为低。
4将下列的十进制数转换成二进制数：5如何采用\位权法\将非十进制数转换为十进制数？把各非十进制数按权展开，然后求和，便可得到转换的结果。
6、将下列各数用位权法展开：（5678.123）10，（321.8）10，（1100.0101）2，（100111.0001）2答：（5678.123）=5×10+6×10+7×10+8×10+1×10+2×10+3×10103210?1?2?3（321.810=3×10+2×10+1×10+8×10）2101(1100.0101)2=1×2+1×2+1×2+1×232521224(100111.0001)=1×2+1×2+1×2+1×2+1×2047将下列二进制数转换成十进制数：8二进制与八进制之间如何转换？左向右分别按每3位为一组（不足3为对应的1位八进制数，只要把每194位为一组，不足44位二进制数转换为对应的1位十六进制数，即得1位十六进制数转换为对应的4位二进制数即可。
第1章电脑系统基础选择题1.电脑的发展经历了机械式电脑、〔 B 〕式电脑和电子电脑三个阶段。
〔A〕电子管〔B〕机电〔C〕晶体管〔D〕集成电路2.英国数学家巴贝奇1822年设计了一种程序控制的通用〔 D 〕。
〔A〕加法器〔B〕微机〔C〕大型电脑〔D〕分析机3.美国宾夕法尼亚大学1946年研制成功了一台大型通用数字电子电脑〔 A 〕。
〔A〕ENIAC 〔B〕Z3 〔C〕IBM PC 〔D〕Pentium4.爱德华·罗伯茨1975年发明了第一台微机〔 C 〕。
〔A〕Apple II 〔B〕IBM PC/XT 〔C〕牛郎星〔D〕织女星5.1981年IBM公司推出了第一台〔 B〕位个人电脑IBM PC 5150。
〔A〕8 〔B〕16 〔C〕32 〔D〕646.中国大陆1985年自行研制成功了第一台PC兼容机〔 C 〕0520微机。
〔A〕联想〔B〕方正〔C〕长城〔D〕银河7.摩尔定律指出，微芯片上集成的晶体管数目每〔 C 〕个月翻一番。
〔A〕6 〔B〕12 〔C〕18 〔D〕248.第四代电脑采用大规模和超大规模〔 B 〕作为主要电子元件。
〔A〕微处理器〔B〕集成电路〔C〕存储器〔D〕晶体管9.电脑朝着大型化和〔 C〕化两个方向发展。
〔A〕科学〔B〕商业〔C〕微机〔D〕实用10.电脑中最重要的核心部件是〔A 〕。
〔A〕CPU 〔B〕DRAM 〔C〕CD-ROM 〔D〕CRT11.电脑类型大致可以分为：大型电脑、〔 A 〕、嵌入式系统三类。
〔A〕微机〔B〕服务器〔C〕工业PC 〔D〕笔记本微机12.大型集群电脑技术是利用许多台单独的〔 D 〕组成一个电脑群。
〔A〕CPU 〔B〕DRAM 〔C〕PC 〔D〕电脑13.〔 C〕系统是将微机或微机核心部件安装在某个专用设备之内。
〔A〕大型电脑〔B〕网络〔C〕嵌入式〔D〕服务器14.冯结构电脑包括：输入设备、输出设备、存储器、控制器、〔 B 〕五大组成部分。
作业一学号：_____ 姓名：_____说明：1、正文用宋体小四号，1.5倍行距。
2、报告中的图片、表格中的文字均用宋体五号，单倍行距。
3、图片、表格均需要有图片编号和标题，均用宋体五号加粗。
4、参考文献用宋体、五号、单倍行距，请参照参考文献格式国家标准（GB/T 7714-2005）。
5、公式请使用公式编辑器。
P144.用伪代码写一个算法来求方程ax2+bx+c=0的实根，a，b，c 是任意实系数。
（可以假设sqrt(x)是求平方根的函数。
）算法：Equate(a,b,c)//实现二元一次方程求解实数根//输入：任意系数a，b，c//输出：方程的实数根x1，x2或无解If a≠0p←b2−4acIf p>0x1←−b+sqrt(p)2ax2←−b−sqrt(p)2areturn x1，x2else if p=0return −b2aelsereturn “no real roots”elseif b≠0return −cbelseif c≠0return “no real numbers”elsereturn “no real roots”5.写出将十进制正整数转换为二进制整数的标准算法。
a.用文字描述。
b.用伪代码描述。
a.解：输入：一个正整数n输出：正整数n相应的二进制数第一步：用n 除以2，余数赋给K[i](i=0,1,2...)，商赋给n第二步：如果n=0 ，则到第三步，否则重复第一步第三步：将K[i]按照i从高到低的顺序输出b.解：算法：DecToBin(n)//实现正整数十进制转二进制//输入：一个正整数n//输出：正整数n对应的二进制数组K[0..i]i ←1while n≠0 doK[i]←n%2n←(int)n/2i ++while i≠0doprint K[i]i - -p462.请用O，Ω 和θ的非正式定义来判断下列断言是真还是假。
a. n(n+1)/2∈O(n3)b. n(n+1)/2∈O(n2)c. n(n+1)/2∈θ(n3)d. n(n+1)/2∈Ω(n)解：断言为真：a，b，d断言为假：cP535.考虑下面的算法。
计算机网络基础（第三版）第1章习题答案一、选择题1. A 2. C 3. D 4. C 5. D 6．A 7．B 8．B 9．B 10．B11．A 12．A 13．D 14．A 15．A 16．C 17．A 18．B 二、填空题1．环型，星型2．局域网（或LAN），广域网（或MAN）3．通信4．网际层5．逻辑链路控制（或LLC），介质访问控制（或MAC）6．UDP，TCP 7．频带（宽带）三、问答题1．计算机网络发展过程可分为四个阶段，分别是：面向终端的计算机网络阶段、具有通信功能的多机系统阶段、以共享资源为主的计算机网络阶段、广泛应用和发展阶段。
1）面向终端的计算机网络面向终端的计算机网络是将一台主计算机（Host）经通信线路与若干个地理上分散的终端Terminal相连。
主计算机一般称为主机，它具有独立处理数据的能力，而所有的终端设备均无独立处理数据的能力。
在通信软件的控制下，每个用户在自己的终端上分时轮流地使用主机系统的资源。
这种系统存在两个方面的问题。
第一，随着所连远程终端数目的增加，主机的负荷加重，系统效率下降。
第二，线路利用率低，费用也较高。
2）具有通信功能的多机系统具有通信功能的多机系统把数据处理和数据通信分开的工作方式，主机专门进行数据处理，而在主机和通信线路之间设置一台功能简单的计算机，专门负责处理网络中数据通信、传输和控制。
它一方面作为资源子网的主机和终端的接口节点，另一方面又担负通信子网中的报文分组的接收、校验、存储、转发等任务，从而将源主机的报文准确地发送到目的主机。
3）计算机网络第二代计算机网络是将若干个联机系统中的主机互联，为用户提供服务，以达到资源共享的目的，它和第一代网络的区别在于多个主机都具有自主处理能力，它们之间不存在主从关系，第二代计算机网络的典型代表是Internet 的前身ARPA 网。
2．计算机网络种类很多，性能各有差异，可以从不同的角度对计算机网络进行分类，主要有以下几种分类方法：．按覆盖范围可分为广域网（远程网），城域网（市域网），局域网（本地网）；. 根据通信子网的信道类型可分为点到点式网络和广播式网络；．按传输速率可分为低速网、中速网、高速网；．按信息交换方式可分为电路交换网、分组交换网、报文交换网和综合业务数字网等；．按网络的拓扑结构又可分为总线型、星型、树型、环形型、网状型网络、混合型、全连型和不规则型网络；．创浣橹史治氏摺⑼岬缋隆⒐庀恕⑽尴吆臀佬峭龋?. 按照带宽分为基带网络和宽带网络；．按配置可分为同类网、单服务器网和混合网；．按对数据的组织方式可分为分布式、集中式网络系统；．按使用范围可分为公用网和专用网；. 按网络使用环境可分成校园网、内部网、外部网和全球网等；．按网络组件的关系可分为对等网络、基于服务器的网络。
