第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 第9章 习题9-1 1． 判定下列级数的收敛性： (1) 11 5n n a ∞ =?∑（a ＞0）； (2) ∑∞ =-+1 )1(n n n ; (3) ∑∞ =+13 1 n n ; (4) ∑∞ =-+12)1(2n n n ; (5) ∑∞ =+11ln n n n ; (6) ∑∞ =-12)1(n n ; (7) ∑∞ =+11 n n n ; (8) 0(1)21n n n n ∞ =-?+∑． 解：（1）该级数为等比级数，公比为 1a ,且0a >,故当1 ||1a <,即1a >时，级数收敛，当1 | |1a ≥即01a <≤时，级数发散. （2） Q n S =+++L 1= lim n n S →∞ =∞ ∴ 1 n ∞ =∑发散. （3）113 n n ∞ =+∑是调和级数11n n ∞=∑去掉前3项得到的级数，而调和级数11 n n ∞ =∑发散，故原 级数 11 3 n n ∞ =+∑发散. （4）Q 1112(1)1(1)22 2n n n n n n n ∞ ∞-==?? +--=+ ???∑∑ 而11 12n n ∞ -=∑,1(1)2m n n ∞ =-∑是公比分别为1 2的收敛的等比级数，所以由数项级数的基本性质 知111(1)2 2n n n n ∞ -=??-+ ???∑收敛，即原级数收敛. （5）Q ln ln ln(1)1 n n n n =-++ 于是(ln1ln 2)(ln 2ln 3)[ln ln(1)]n S n n =-+-+-+L ln1ln(1)ln(1)n n =-+=-+ 故lim n n S →∞ =-∞,所以级数 1 ln 1 n n n ∞ =+∑发散. （6）Q 2210,2n n S S +==- ∴ lim n n S →∞ 不存在，从而级数 1 (1) 2n n ∞ =-∑发散. （7）Q 1 lim lim 10n n n n U n →∞ →∞+==≠ ∴ 级数 1 1 n n n ∞ =+∑发散. （8）Q (1)(1)1 , lim 21212 n n n n n n U n n →∞--==++ ∴ lim 0n x U →∞≠，故级数1 (1)21n n n n ∞ =-+∑发散. 2． 判别下列级数的收敛性，若收敛则求其和： (1) ∑∞ =??? ??+13121n n n ； (2) ※ ∑∞ =++1)2)(1(1n n n n ; (3) ∑∞ =?1 2sin n n n π ; (4) 0πcos 2n n ∞ =∑． 解：Q （1）1111, 23n n n n ∞ ∞==∑∑都收敛，且其和分别为1和12，则1112 3n n n ∞ =?? + ???∑收敛，且其 和为1+ 12=3 2 . （2）Q 11121(1)(2)212n n n n n n ?? =-+ ?++++?? 第一章 误差 1. 试举例,说明什么是模型误差,什么是方法误差. 解: 例如,把地球近似看为一个标准球体,利用公式2 4A r π=计算其表面积,这个近似看为球体的过程产生 的误差即为模型误差. 在计算过程中,要用到π,我们利用无穷乘积公式计算π的值: 12 222...q q π=? ?? 其中 11 2,3,... n q q n +?=?? ==?? 我们取前9项的乘积作为π的近似值,得 3.141587725...π≈ 这个去掉π的无穷乘积公式中第9项后的部分产生的误差就是方法误差,也成为截断误差. 2. 按照四舍五入的原则,将下列各数舍成五位有效数字: 816.956 7 6.000 015 17.322 50 1.235 651 93.182 13 0.015 236 23 解: 816.96 6.000 0 17.323 1.235 7 93.182 0.015 236 3. 下列各数是按照四舍五入原则得到的近似数,它们各有几位有效数字? 81.897 0.008 13 6.320 05 0.180 0 解: 五位 三位 六位 四位 4. 若1/4用0.25表示,问有多少位有效数字? 解: 两位 5. 若 1.1062,0.947a b ==,是经过舍入后得到的近似值,问:,a b a b +?各有几位有效数字? 解: 已知4311 d 10,d 1022 a b -- 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=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" voidmain() { intn,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 计算方法第3版习题答案 习题1解答 1.1 解：直接根据定义得 *411()102x δ-≤?*411()102r x δ-≤?*3*12211 ()10,()1026 r x x δδ--≤?≤?*2*5331()10,()102r x x δδ--≤?≤ 1.2 解：取4位有效数字 1.3解：433 5124124124 ()()() 101010() 1.810257.563 r a a a a a a a a a δδδδ----++++++≤≤=?++? 123()r a a a δ≤ 123132231123 ()()() a a a a a a a a a a a a δδδ++0.016= 1.4 解：由于'1(),()n n f x x f x nx -==，故***1*(())()()()n n n f x x x n x x x δ-=-≈- 故** * ***(()) (())()0.02()r r n f x x x f x n n x n x x δδδ-= ≈== 1.5 解： 设长、宽和高分别为 ***50,20,10l l h h εεωωεεεε=±=±=±=±=±=± 2()l lh h ωωA =++，*************()2[()()()()()()]l l l h h l h h εδωωδδδωδδωA =+++++ ***4[]320l h εωε=++= 令3201ε<，解得0.0031ε≤， 1.6 解：设边长为x 时，其面积为S ，则有2()S f x x ==，故 '()()()2()S f x x x x δδδ≈= 现100,()1x S δ=≤，从而得() 1 ()0.00522100 S x x δδ≈ ≤ =? 1.7 解：因S ld =，故 S d l ?=?，S l d ?=?，*****()()()()()S S S l d l d δδδ??≈+?? * 2 ()(3.12 4.32)0.010.0744S m δ=+?=, *** ** * () () 0.0744 ()0.55%13.4784 r S S S l d S δδδ= = = ≈ 1.8 解：（1）4.472 （2）4.47 1.9 解：(1) （B ）避免相近数相减 (2)（C ）避免小除数和相近数相减 (3)（A ）避免相近数相减 (3)（C ）避免小除数和相近数相减，且节省对数运算 1.10 解 （1）357sin ...3!5!7!x x x x x =-+-+ 故有357 sin ..3!5!7! x x x x x -=-+-， （2） 1 (1)(1)1lnxdx ln ln ln N+N =N N +-N N +N +-? 1 (1)1ln ln N +=N +N +-N 1.11 解：0.00548。 1.12解：21 16 27 3102 ()()() -? 1.13解：0.000021 《数据结构与算法》课后习题 答案 2.3 课后习题解答 2．3.2 判断题 1.线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√） 3.顺序表的插入和删除操作不需要付出很大的时间代价,因为每次操作平均只有近一半的元素需要移动。（×） 4.线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）...文档交流仅供参考... 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×) ６.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√) 7.线性表的链式存储结构优于顺序存储结构。（×) 8．在线性表的顺序存储结构中,插入和删除时移动元素的个数与该元素的位置有关。（√） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√） 10．在单链表中，要取得某个元素,只要知道该元素的指针即可，因此,单链表是随机存取的存储结构。(×)１１.静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与ｉ无关。(×） 12.线性表的特点是每个元素都有一个前驱和一个后继。（×) 2．3．3 算法设计题 1．设线性表存放在向量A[arｒｓize]的前eleｎum个分量中，且递增有序。试写一算法,将x 插入到线性表的适当位置上,以保持线性表的有序性，并且分析算法的时间复杂度。...文档交流仅供参考... 【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻,不一定将向量和表示线性表长度的变量封装成一个结构体),因为是顺序存储，分配的存储空间是固定大小的,所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性,来确定插入元素的插入位置,后面的元素为它让出位置,（也可以从高下标端开始一边比较,一边移位)然后插入ｘ，最后修改表示表长的变量。...文档交流仅供参考... int iｎsert （datａtypｅＡ[］，iｎt *eｌｅnｕm，dataｔypｅ x)???/*设eｌenum为表的最大下标＊/...文档交流仅供参考... 作者：李庆扬，王能超，易大义编 出版社：清华大学出版社 出版时间：2008年12月 本书是为理工科大学各专业普遍开设 的“数值分析”课程编写的教材。其内容包 括插值与逼近，数值微分与数值积分，非 线性方程与线性方程组的数值解法，矩阵 的特征值与特征向量计算，常微分方程数 值解法。每章附有习题并在书末给出了部 分答案，每章还附有复习与思考题和计算 实习题。全书阐述严谨，脉络分明，深入 浅出，便于教学。 本书也可作为理工科大学各专业研究 生学位课程的教材，并可供从事科学计算 的科技工作者参考。 作者：徐萃薇，孙绳武编著 出版社：高等教育出版社 本书为普通高等教育“十一五”国家 级规划教材。本书从服务于多层次、多 专业、多学科的教学需要出发，在选材 上考虑普适性，涉及现代数字电子计算 机上适用的各类数学问题的数值解法以 及必要的基础理论，在材料组织安排上 给讲授者根据教学要求和学生情况适当 剪裁的自由，一些内容还可作为阅读材 料。 新版全书经过整理、润色，多处内容有 所修改，乃至重写。考虑到代数计算在 应用中所占份额较大，是比较活跃的领 域，六至十章改动较大；新增共轭斜量 法、预善共轭斜量法、拟Newton法等；改进了例题设置，增加数量，加强例题间联系；新 增习题参考答案；参考文献收集了国内外内容结构与本书相近的、有影响的、包括新近面世 的一些书籍，并按大学生教材和研究生教材或专著分列，可供读者加深理解和进一步提高使 用。有些对研究工作亦不无裨益。 本书算法描述不拘一格，或用自然语言，或用某种形式语言(以描述某些细节)，便于理解， 也便于编程。本书可作为工科非计算数学专业本科生学习“计算方法”课程的教材。 第二章 插值法 知识点：拉格朗日插值法，牛顿插值法，余项，分段插值。 实际问题中，时常不能给出f （x ）的解析表达式或f （x ）解析表达式过于复杂而难于计算，能采集的只是一些f （x ）的离散点值{xi,f(xi)}(i=0,1,2,…n )。因之，考虑近似方法成为自然之选。 定义：设f （x ）为定义在区间[a ，b]上的函数，x0,x1,…,xn 为[a ，b]上的互异点，yi=f （xi ）。若存在一个简单函数?（x ），满足 （插值条件）?（xi ）=f （xi ），i=0，1，…，n 。 则称 ?（x ）为f （x ）插值函数，f （x ）为被插函数,点x0,x1,…,xn 为插值节点,点{xi,f(xi)},i=0,1,2,…n 为插值点。 于是计算f （x ）的问题就转换为计算 ?（x ）。 构造插值函数需要解决：插值函数是否存在唯一；插值函数如何构造(L 插值)；插值函数与被插函数的误差估计和收敛性。 对插值函数 ?（x ）类型有多种不同的选择，代数多项式常被选作插值函数。 P23(2.18)和(2.19)指出，存在唯一的满足插值条件的n 次插值多项式p n (x )。但是需要计算范德蒙行列式，构造插值多项式工作量过大，简单表达式不易得到，实际中不采用这类方法。 插值法是一种古老的数学方法，拉格朗日（Lagrange ）、牛顿（Newton ）等分别给出了不同的解决方法。 拉格朗日插值 拉格朗日（Lagrange ）插值的基本思想：把插值多项式p n (x )的构造问题转化为n+1个插值基函数l i (x)(i=0,1,…,n)的构造。 (1)线性插值 ①构造插值函数 已知函数y =f (x )的两个插值点(x 0,y 0)，(x 1,y 1)，构造多项式y =p 1(x )，使p 1(x 0)=y 0,p 1(x 1)=y 1。 p n (x )≈f (x ) 第3章栈和队列 一、基础知识题 3.1有五个数依次进栈：1，2，3，4，5。在各种出栈的序列中，以3，4先出 的序列有哪几个。（３在４之前出栈）。 【解答】34215 ，34251， 34521 3.2铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序 为：1，2，3，4，5，6，那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出"进栈"或"出栈"的序列)。 【解答】输入序列为123456，不能得出435612和154623。不能得到435612的理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。 得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。 3.3若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别 为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？ 【解答】2和 4 3.4设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通 过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量至少应该是多少？ 【解答】 4 3.5循环队列的优点是什么，如何判断“空”和“满”。 【解答】循环队列解决了常规用0--m-1的数组表示队列时出现的“假溢出”（即队列未满但不能入队）。在循环队列中我们仍用队头指针等于队尾指针表示队空，而用牺牲一个单元的办法表示队满，即当队尾指针加1（求模）等于队头指针时，表示队列满。也有通过设标记以及用一个队头或队尾指针加上队中元素个数来区分队列的“空”和“满”的。 3.6设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队的 时间如何？若只设尾指针呢？ 【解答】若只设头指针，则入队的时间为O(n），出队的时间为O(1)。若只设尾指针，则入队和出队的时间均为O(1)。 3.7指出下面程序段的功能是什么？ (1)void demo1(SeqStack S) {int i，arr[64]，n=0; while(!StackEmpty(S)) arr[n++]=Pop(S); 高等数学一第6章课后习题详解 课后习题全解 习题6-2 ★ 1．求由曲线 x y =与直线 x y =所围图形的面积。 知识点：平面图形的面积 思路：由于所围图形无论表达为X-型还是Y-型，解法都较简单，所以选其一做即可 解： 见图6-2-1 ∵所围区域D 表达为X-型：?? ?<<< ∵所围区域D 表达为X-型：?????<<< <1 sin 2 0y x x π， （或D 表达为Y-型：???<<< ∴所围区域D 表达为Y-型：?? ?-<<<<-2 2 422y x y y ， ∴23 16 )32 4()4(2 2 32 222= -=--=- - ? y y dy y y S D （由于图形关于X 轴对称，所以也可以解为： 2316 )324(2)4(22 32 22=-=--=? y y dy y y S D ） ★★4．求由曲线 2x y =、24x y =、及直线1=y 所围图形的面积 知识点：平面图形面积 思路：所围图形关于Y 轴对称，而且在第一象限内的图形表达为Y-型时，解法较简单 解：见图6-2-4 ∵第一象限所围区域1D 表达为Y-型：? ??<<< 《数据结构简明教程》练习题及参考答案 练习题1 1. 单项选择题 （1）线性结构中数据元素之间是（）关系。 A.一对多 B.多对多 C.多对一 D.一对一 答：D （2）数据结构中与所使用的计算机无关的是数据的（）结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答：C （3）算法分析的目的是（）。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答：C （4）算法分析的两个主要方面是（）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答：A （5）计算机算法指的是（）。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法 答：C （6）计算机算法必须具备输入、输出和（）等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答：B 2. 填空题 （1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。 答：①逻辑结构②存储结构③运算 （2）数据结构按逻辑结构可分为两大类，它们分别是①和②。 答：①线性结构②非线性结构 （3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。 答：①数据元素 ②关系 （4）在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 ② 后继结点，其余每个结点有且只有1个后继结点。 答：①没有 ②没有 （5）在树形结构中，树根结点没有 ① 结点，其余每个结点有且只有 ② 个前驱结点；叶子结点没有 ③ 结点，其余每个结点的后继结点数可以是 ④ 。 答：①前驱 ②1 ③后继 ④任意多个 （6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ）。 答：任意多个 （7）数据的存储结构主要有四种，它们分别是 ① 、 ② 、 ③ 和 ④ 存储结构。 答：①顺序 ②链式 ③索引 ④哈希 （8）一个算法的效率可分为 ① 效率和 ② 效率。 答：①时间 ②空间 3. 简答题 （1）数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。 （2）简述线性结构、树形结构和图形结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。 （3）设有采用二元组表示的数据逻辑结构S=(D,R)，其中D={a ,b ,…,i }，R={(a ,b ),(a ,c ),(c ,d ),(c ,f ),(f ,h ),(d ,e ),(f ,g ),(h ,i )}，问相对于关系R ，哪些结点是开始结点，哪些结点是终端结点？ 答：该逻辑结构为树形结构，其中a 结点没有前驱结点，称为根结点，b 、e 、g 、i 结点没有后继结点，是终端结点，也称为叶子结点。 （4）以下各函数是算法中语句的执行频度，n 为问题规模，给出对应的时间复杂度： T 1(n )=n log 2n -1000log 2n T 2(n )=3log 2n -1000log 2n T 3(n )=n 2 -1000log 2n T 4(n )=2n log 2n -1000log 2n 答：T 1(n )=O(n log 2n )，T 2(n )=O( )，T 3(n )=O(n 2 )，T 4(n )=O(n log 2n )。 （5）分析下面程序段中循环语句的执行次数。 int j=0,s=0,n=100; do { j=j+1; s=s+10*j; } while (j 283 高等数学上（修订版）（复旦出版社） 习题六 无穷数级 答案详解 1．写出下列级数的一般项： (1)111135 7 ++++ ； (2)2 2242462468x x x x x ++++?????? ； (3)3579 3579 a a a a -+-+ ； 解：(1)1 21 n U n =-； (2)()2 !! 2n n x U n = ； (3)() 21 1 121 n n n a U n ++=-+； 2．求下列级数的和： (1)()()() 11 11n x n x n x n ∞ =+-+++∑ ； (2) ( )1 221n n n n ∞ =+-++∑； (3)23 111 5 55+ ++ ； 解：(1)()()() ()()()()1 11111211n u x n x n x n x n x n x n x n = +-+++?? -= ?+-++++?? 284 从而()()()()()()() ()()()()()()()1111 1211212231111111211n S x x x x x x x x x n x n x n x n x x x n x n ?-+-= +++++++?? ++ - ?+-++++? ?? -= ?++++?? 因此() 1lim 21n n S x x →∞ =+，故级数的和为 () 121x x + (2)因为()()211n U n n n n =-+-++- 从而()()()() ()()()()3243322154432112112 1 12 21 n S n n n n n n n n =-+-----+-++---+-++-=+-++-=+-+++ 所以lim 12n n S →∞ =-，即级数的和为12-． (3)因为2111 5551115511511145n n n n S =+ ++????-?? ???? ?=-????=-?? ????? 从而1lim 4 n n S →∞ =，即级数的和为14 ． 3．判定下列级数的敛散性： (1) ( )1 1n n n ∞ =+-∑； (2) ()() 11111661111165451n n +++++???-+ ； (3) ()23133222213333 n n n --+-++- ； 1.绪论 1．将下列复杂度由小到大重新排序： A．2n B．n! C．n5D．10 000 E．n*log2 (n) 【答】10 000< n*log2(n)< n5< 2n < n! 2．将下列复杂度由小到大重新排序： A．n*log2(n) B．n + n2 + n3C．24D．n0.5 【答】24< n0.5< n*log2 (n) < n + n2 + n3 3．用大“O”表示法描述下列复杂度： A．5n5/2 + n2/5 B．6*log2(n) + 9n C．3n4+ n* log2(n) D．5n2 + n3/2 【答】A：O (n5/2) B：O (n) C：O (n4) D：O (n2) 4．按照增长率从低到高的顺序排列以下表达式：4n2 , log3n, 3n , 20n , 2000 , log2n , n2/3。又n！应排在第几位？ 【答】按照增长率从低到高依次为：2000, log3n, log2n , n2/3 , 20n , 4n2 , 3n。 n！的增长率比它们中的每一个都要大，应排在最后一位。 5. 计算下列程序片断的时间代价： int i=1; while(i<=n) { printf(“i=%d\n”,i); i=i+1; } 【答】循环控制变量i从1增加到n，循环体执行n次，第一句i的初始化执行次数为1，第二句执行n次，循环体中第一句printf执行n次，第二句i从1循环到n，共执行n次。所以该程序段总的时间代价为： T(n) = 1 + n + 2n = 3n+ 1 = O(n) 6. 计算下列程序片断的时间代价： int i=1; while(i<=n) { int j=1; while(j<=n) { int k=1; 《计算方法》课程教学大纲 课程编号： 学时：54 学分：3 适用对象：教育技术学专业 先修课程：高等数学、线性代数 考核方式：本课程考试以笔试为主70%，兼顾学生的平时成绩30%。 使用教材及主要参考书： 使用教材： 李庆扬.《数值分析(第四版)》, 清华大学出版,2014年。 主要参考书： 1.朱建新,李有法.《高等学校教材:数值计算方法(第3版)》,高等教育出版社,2012。 2.徐萃薇,孙绳武.《计算方法引论(第4版)》,高等教育出版社,2015。 一课程的性质和任务 计算方法是教育技术学专业学生的一门专业选修课。作为计算数学的一个重要分支，它是数学科学与计算机技术结合的一门应用性很强的学科，本课程重点介绍计算机上常用的基本计算方法的原理和使用；同时对计算方法作适当的分析。 教学任务：通过本课程的学习，要使学生具有现代数学的观点和方法，并初步掌握处理计算机常用数值分析的构造思想和计算方法。同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识分析和解决实际问题的能力。 二教学目的与要求 教学目的：通过学习使学生了解数值计算方法的基本原理。了解计算机与数学结合的作用及课程的应用性。为今后使用计算机解决实际问题中的数值计算问题打下基础。 通过理论教学达到如下基本要求。 1．了解误差的概念 2．掌握常用的解非线性方程根的方法 3．熟练掌握线性代数方法组的解法 4．熟练掌握插值与拟合的常用方法 5．掌握数值积分方法 6．了解常微分方程初值问题的数值方法 三学时分配 四教学中应注意的问题 本课程是一门理论性较强、内容较抽象的综合课程，因此面授辅导或自学，将是不可缺少的辅助教学手段，教师在教学的过程中一定要注意理论结合实际，课堂教学并辅助上机实验，必须通过做练习题和上机实践来加深对概念的理解和掌握，熟悉公式的运用，从而达到消化、掌握所学知识的目的。同时应注重面授辅导或答疑，及时解答学生的疑难问题。 五教学内容 第一章绪论（误差） 基本内容: 第一节数值分析研究的对象和特点 第二节数值计算的误差 1.误差的来源与分类 2.误差与有效数字 3.数值运算的误差估计 第三节误差的定性分析与避免误差的危害 1.病态问题与条件数 2.算法的数值稳定性 3.避免误差危害的若干原则 教学重点难点: 重点：数值运算的误差估计。 难点：误差的定性分析与避免误差的危害。 第五章 7.试比较缺页中断机构与一般的中断，他们之间有何明显的区别？ 答：缺页中断作为中断，同样需要经历保护CPU现场、分析中断原因、转缺页中断处理程序进行处理、恢复CPU现场等步骤。但缺页中断又是一种特殊的中断，它与一般中断的主要区别是： （ 1）在指令执行期间产生和处理中断信号。通常，CPU都是在一条指令执行完后去检查是否有中断请求到达。若有便去响应中断；否则继续执行下一条指令。而缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时产生和处理的。 (2)一条指令在执行期间可能产生多次缺页中断。例如，对于一条读取数据的多字节指令，指令本身跨越两个页面，假定指令后一部分所在页面和数据所在页面均不在内存，则该指令的执行至少产生两次缺页中断。 8.试说明请求分页系统中的页面调入过程。 答：请求分页系统中的缺页从何处调入内存分三种情况： （1）系统拥有足够对换区空间时，可以全部从对换区调入所需页面，提高调页速度。在进程运行前将与该进程有关的文件从文件区拷贝到对换区。 （2）系统缺少足够对换区空间时，不被修改的文件直接从文件区调入；当换出这些页面时，未被修改的不必换出，再调入时，仍从文件区直接调入。对于可能修改的，在换出时便调到对换区，以后需要时再从对换区调入。 （3）UNIX 方式。未运行页面从文件区调入。曾经运行过但被换出页面，下次从对换区调入。UNIX 系统允许页面共享，某进程请求的页面有可能已调入内存，直接使用不再调入。 19.何谓工作集？它是基于什么原理确定的？ 答：工作集：在某段时间间隔里，进程实际所要访问页面的集合。 原理：用程序的过去某段时间内的行为作为程序在将来某段时间内行为的近似。 24.说明请求分段式系统中的缺页中断处理过程。 答：在请求分段系统中，每当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段中断信号，进入操作系统后由缺段中断处理程序将所需的段调入内存。缺段中断机构与缺页中断机构类似，它同样需要在一条指令的执行期间，产生和处理中断，以及在一条指令执行期间，可能产生多次缺段中断。 算法与数据结构习题答案.txt机会就像秃子头上一根毛，你抓住就抓住了，抓不住就没了。我和你说了10分钟的话，但却没有和你产生任何争论。那么，我们之间一定有个人变得虚伪无比！过错是短暂的遗憾，错过是永远的遗憾。相遇是缘，相知是份，相爱是约定，相守才是真爱。3.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答： 在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 3.12 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 解： 要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。 算法如下： //设已建立三个带头结点的空循环链表A,B,C且A、B、C分别是尾指针. void DivideList( LinkList L, LinkList A, LinkList B, LinkList C) { ListNode *p=L->next, *q; while ( p ) { if ( p->data>='a' &&p->data<='z'|| p->data>='A' &&p->data<='Z') { q=p->next; p=p->next;//指向下一结点 q->next=A->next;//将字母结点链到A表中 A->next=q;A=q; } else if( p->data>='0' && p->data<='9') { // 分出数字结点 q=p->next; p=p->next;//指向下一结点 q->next=B->next;//将数字结点链到B表中 B->next=q;B=q; } else { //分出其他字符结点 q=p->next; p=p->next;//指向下一结点 q->next=C->next;//将其他结点链到C表中 C->next=q;C=q; } } }//结束 计算方法引论： 微分方程数值解法 ?常微分方程初值问题的数值解法?双曲型方程的差分解法 ?抛物型方程的差分解法 ?橢圆型方程的差分解法 ?有限元方法 第十三章抛物型方程差分解法?初值问题和初边值混合问题 ?微分方程的差分近似 ?边界条件的差分近似 ?几种常用的差分格式 ?差分格式的稳定性 ?二维热传导方程的交替方向法 热传导方程定解问题 ?热传导方程 ?初值问题 ?初边值问题 –u (x ,0)=?(x ), 0≤x ≤1 –Ⅰu (0,t )=g 1(t ), Ⅲu (1,t )=g 2(t ), 2 20, 0, 0≤??(,0)(), u x x x ?=<+∞110 221()() 0()()x x u t u g t x t T u t u g t x λλ==? ??? -=? ?????≤≤? ????+= ?????? 一些数值微分公式 ?一阶差商 ?二阶差商 1(,)(,1)(,)(,)2tt k j u u k j u k j u k t t τ τ?+-''=-?2(,)(,)(,1)(,)2 tt k j u u k j u k j u k t t τ τ?--''=+?2 3(,)(,1)(,1)(,)26 ttt k j u u k j u k j u k t t τ τ?+--''=-?2 2 (4) 22 (,)(1,)2(,)(1,)(,)12xxxx k j u u k j u k j u k j h u x j x h ?+-+-=-? 微分方程的差分近似 ?差商代微商h =1/N ?近似解满足差分方程 –形式1 –形式2 s =τ/h 2 ?截断误差 ,2 (,1)(,) (1,)2(,)(1,)0h u k j u k j u k j u k j u k j b R h ττ+-+-+---=2 (4) 2,1(,)(,)() 212 h tt xxxx bh R u"k t u x j O h τττ=-=+ 0 22 ,1,,1,1,=+----++h u u u b u u j k j k j k j k j k τ 2 (4)2 ,1(,)(,)()212 h tt xxxx bh R u"k t u x j O h ττ τ=-=+,1,1,,1,(2)k j k j k j k j k j u u bs u u u ++-=+-+ 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};微积分课后题答案第九章习题详解
计算方法引论课后答案.
算法设计与分析课后部分习题答案
计算方法习题答案
《数据结构与算法》课后习题答案(课件)
数值分析丛书
《徐翠微计算方法引论》
算法和数据结构C语言版课后习题集答案解析(机械工业出版社)第34章习题集参考答案解析
中国人民大学出版社第四版高等数学一第6章课后习题详解
数据结构课程 课后习题答案
高等数学上复旦第三版 课后习题答案
最新算法与数据结构C语言习题参考答案1-5章讲解学习
计算方法课程教学大纲
计算机操作系统(第四版)课后习题答案第五章
算法与数据结构习题答案
计算方法引论-第十三章
数据结构与算法分析习题与参考答案
相关主题
文本预览