算法第四版习题答案

第5章算法与复杂性习题一、选择题1. B2. D3. C4. A5. B6. B7. D8.B9.C 10.A11.A 12.C 13.A 14.A二、简答题1．什么是算法，算法的特性有哪些？答：“算法(Algorithm)是一组明确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果”。

算法的特性有：(1) 有穷性(可终止性)：一个算法必须在有限个操作步骤内以及合理的有限时间内执行完成。

(2) 确定性：算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。

(3) 有效性(可执行性)：算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。

(4) 输入及输出：一个算法应该有零个或多个输入数据、有1个或多个输出数据。

2．什么是算法的时间复杂度和空间复杂度，如何表示？答：时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花费的时间。

记为，T(n)，其中，n代表求解问题的规模。

算法的空间复杂度(Space complexity)度量算法的空间复杂性、即执行算法的程序在计算机中运行所占用空间的大小。

简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。

记为，S(n)，其中，n代表求解问题的规模。

时间复杂度和空间复杂度同样，引入符号“O”来表示T(n)、S(n)与求解问题规模n之间的数量级关系。

3．用图示法表示语言处理的过程。

答：语言处理的过程如图所示：4．简述算法设计的策略。

答：作为实现计算机程序实现时解决问题的方法，算法研究的内容是解决问题的方法，而不是计算机程序的本身。

一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中，算法设计往往处于核心地位。

要想充分理解算法并有效地应用于实际问题，关键是对算法的分析。

通常可以利用实验对比分析、数学方法来分析算法。

实验对比分析很简单，两个算法相互比较，它们都能解决同一问题，在相同环境下，一般就会认为哪个算法的速度快这个算法性能更好。

算法（第四版）C#习题题解——1.3.49⽤6个栈实现⼀个O（1）队列因为这个解法有点复杂，因此单独开⼀贴介绍。

那么这⾥就使⽤六个栈来解决这个问题。

这个算法来⾃于。

原⽂⾥⽤的是 Pure Lisp，不过语法很简单，还是很容易看懂的。

先导知识——⽤两个栈模拟⼀个队列如何使⽤两个栈来模拟⼀个队列操作？这是⼀道很经典的题⽬，答案也有很多种，这⾥只介绍之后会⽤到的⼀种⽅法。

⾸先我们有两个栈，H 和 T，分别⽤作出队和⼊队⽤。

这样，⼊队操作等同于向 T 添加元素，T 的⼊栈操作只需要 O(1) 时间。

如果 H 不为空，出队操作等同于 H 弹栈，H 的弹栈操作也只需要 O(1) 时间。

但如果 H 为空，则需要将 T 中的元素依次弹出并压⼊到 H 中，这是⼀个 O(n) 的操作。

显然，这种⽅式中，出队操作的最坏时间复杂度是 O(n)，并不满⾜题⽬要求。

分摊 O(n)那么，怎么解决这个问题呢？⼀个很⾃然的想法是，如果在栈 H 变为空之前，我们就能逐步将栈 T 的内容弹出并压⼊到另⼀个栈 H' 中，等到栈 H 为空时，直接交换 H 和 H' 即可。

假设⽬前的队列状态是这样，有三个元素等待出队，还有三个元素等待⼊队。

现在依次让三个元素出队，与此同时我们让栈 T 中的元素依次进⼊ H' 中。

每⼀次出队都执⾏两个操作，元素出队和元素复制（Pop & Push），时间复杂度 O(1) + O(1) + O(1) = O(1)。

第⼀次操作（出队）第⼆次操作（出队）第三次操作（出队）现在栈 H 和栈 T 都为空，下⼀次出队操作时，我们直接交换栈 H 和栈 H'（由于是交换引⽤，因此时间复杂度仍为 O(1)）。

之后再进⾏出队操作。

这就是这个算法基本想法，在栈 H 变为空之前，分步将栈 T 中的内容分步复制到另⼀个栈中。

当栈 H 为空时直接⽤准备好的栈 H' 替代 H，保证时间复杂度为常数。

1.1.1 给出以下表达式的值：a. ( 0 + 15 ) / 2b. 2.0e-6 * 100000000.1c. true && false || true && true答案：a.7,b.200.0000002 c.ture1.1.2 给出以下表达式的类型和值：a. (1 + 2.236)/2b. 1 + 2 + 3 + 4.0c. 4.1 >= 4d. 1 + 2 + "3"答案：a.1.618 b. 10.0 c.true d.331.1.3 编写一个程序，从命令行得到三个整数参数。

如果它们都相等则打印equal，否则打印not equal。

public class TestUqual{public static void main(String[] args){int a,b,c;a=b=c=0;StdOut.println("Please enter three numbers");a =StdIn.readInt();b=StdIn.readInt();c=StdIn.readInt();if(equals(a,b,c)==1){StdOut.print("equal");}else{StdOut.print("not equal");}}public static int equals(int a ,int b , int c){if(a==b&&b==c){return 1;}else{return 0;}}}1.1.4 下列语句各有什么问题（如果有的话）？a. if (a > b) then c = 0;b. if a > b { c = 0; }c. if (a > b) c = 0;d. if (a > b) c = 0 else b = 0;答案：a. if (a > b) c = 0; b. if (a > b) { c = 0; }1.1.5 编写一段程序，如果double 类型的变量x 和y 都严格位于0 和1 之间则打印true，否则打印false。

第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。

若f=Ο(g)，则必然存在常数c1>0和n0，使得∀n≥n0，有f≤c1*g(n)。

由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。

必要性。

同理，若g=Ω(f)，则必然存在c2>0和n0，使得∀n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。

2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得∀n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。

由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。

3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。

证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得∀n≥n1，有F(n) ≤ c1 (f(n)+g(n))= c1 f(n) + c1g(n)≤ c1*max{f,g}+ c1*max{f,g}=2 c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g))对于Ω和Θ同理证明可以成立。

4）log(n!)= Θ(nlogn)证明：∙由于log(n!)=∑=n i i 1log ≤∑=ni n 1log =nlogn ，所以可得log(n!)= Ο(nlogn)。

∙由于对所有的偶数n 有，log(n!)= ∑=n i i 1log ≥∑=n n i i 2/log ≥∑=nn i n 2/2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。

当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得∀n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。

算法第四版习题答案1.2/** 1.2.1 编写一个Point2D的用例，从命令行接受一个整数N。

在单位正方形内生成N个随机点，然后计算两点之间的最近距离*/public class testPoint2D {public testPoint2D() {// TODO Auto-generated constructor stub}public static void drawbox(double bw, double bh){StdDraw.setPenRadius(0.005);StdDraw.setPenColor(StdDraw.RED);Interval1D xinterval = new Interval1D(0, bw);Interval1D yinterval = new Interval1D(0, bh);Interval2D box = new Interval2D(xinterval, yinterval);box.draw();}public static Point2D[] drawpoint(int N){Point2D[] p=new Point2D[N];for(int i=0;i<N;i++){double x=Math.random();double y=Math.random();p[i]=new Point2D(x, y) ;p[i].draw();}return p;}public static double findmindist(Point2D[] p){Point2D p1=p[0];Point2D p2=p[1];double mindist =p[0].distanceTo(p[1]);StdDraw.setPenRadius(0.002);StdDraw.setPenColor(StdDraw.RED);int n=p.length ;for(int i=1;i<n-1;i++)for(int j=i+1;j<n;j++){double temp=p[i].distanceTo(p[j]);if(temp<mindist){ mindist=temp;p1=p[i];p2=p[j];}}p1.drawTo(p2);StdOut.print("min dist="+mindist +p1.toString()+p2.toString());return mindist;}public static void main(String[] args) {int N=StdIn.readInt();//读取画点的数量//StdDraw.setXscale(0,1 );//StdDraw.setYscale(0,1);drawbox(1,1);//画出一个单位大小的正方形StdDraw.setPenRadius(0.01);StdDraw.setPenColor(StdDraw.BLACK);//drawpoint(N);//画出N个点double min=findmindist(drawpoint(N));}}/** 编写一个Interval1D的用例，从命令行接受一个整数N。

C程序设计(第四版)(谭浩强)第一章课后习题答案P006 1.1 向屏幕输出文字.#include<stdio.h>//预编译. 代码均调试成功,若有失误大多不是代码问题.自已找找.int main(){printf("Welcome to \n");return 0; //与int main对应,为了程序可移植性,建议全用int main + return 0;.}P008 1.2 求两个数的和.#include<stdio.h>int main(){int a,b,sum;a=5;b=4;sum=a+b;printf("The sum is %d .\n",sum);return 0;}P008 1.3 调用函数比较两个数的大小.#include<stdio.h>int main(){int max(int x,int y); //被调用函数在主函数后面,用前先声明.int a,b,c;scanf("%d,%d",&a,&b); //输入时要按格式来,此处的逗号,用空格会发生错误.c=max(a,b); //a,b作为实参传入被调用函数中.printf("The max is %d .\n",c);return 0;}int max(int x,int y) //定义了两个形参.{int z; //z属于局部变量,可与主函数中相同名字.if (x>y)z=x;elsez=y;return(z); //z作为整个程序的出口值,赋给主函数中的c.}P015 0.6 三个数的大小.(数字0表示课后练习题)#include<stdio.h>int main(){int a,b,c,d; //d是用于存储最大值的.int max(int x , int y , int z); //测试可知,在VS2008中,可以不预先声明.printf("Please input 3 numbers :\n");scanf("%d %d %d",&a,&b,&c);d=max(a,b,c); //调用函数中有三个形参,这里需要传入三个实参,才可运算.printf("The max is :%d .\n",d); // d可以换成max(a,b,c).}int max(int x , int y , int z){int m;if (x>y && x>z) //求三者之大的一种方法.m=x;if (y>x && y>z)m=y;if (z>y && z>x)m=z;return (m); //返回值m给主函数中的d.}C程序设计(第四版)(谭浩强)第2章课后习题答案算法——程序的灵魂P017 2.1 计算机1-5相乘的积.#include<stdio.h>int main(){int i,s=1; //在执行数值操作前一定要先有个初值.for(i=1;i<6;i++) //这里是到6.{s=s*i; //相乘}printf("The sum is %d .\n",s);return 0;}#include<stdio.h> //作出要求:换成1到11间奇数相乘.int main(){int i,s=1; //在执行数值操作前一定要先有个初值.for(i=1;i<12;i++) //这里是到,但题目要求的是取单数.也可以是i=i+2{if(i%2!=0) //i对取模,值为非为奇数;为则为偶数.s=s*i;elsecontinue; //跳过这个for循环的这一次,执行下一次.}printf("The sum is %d .\n",s);return 0;}P019 2.2 按要求输出80分以上的学生信息.暂时没法做.年的概念是地球围绕太阳一周的时间（所谓公转周期）称为一年，这个周期是相当稳定的，很长时间也不会变动1秒，但是真正的一年是365.2423天（目前）。

计算机算法设计与分析第四版课后答案【篇一：计算机算法分析与设计(第四版)习题算法分析部分详解(实验六)】//6-1、6-6项目vc++6.0测试通过//6-15项目vc2005测试通过//6-1 最小长度电路板排列问题//头文件stdafx.h// stdafx.h : include file for standard system include files,// or project specific include files that are used frequently, but // are changed infrequently//#pragma once#define win32_lean_and_mean // exclude rarely-used stuff from windows headers #include stdio.h#include tchar.h// todo: reference additional headers your program requires here// sy61.cpp : defines the entry point for the console application.////description://分支限界法 6_1 最小长度电路板排列问题//#include my.h#include stdafx.h#include iostream#include queueusing namespace std;int n,m;//#include outofbounds.h//定义节点类class boardnode{friend int fifoboards(int **,int ,int,int *);//非类成员，可以访问私有成员的函数，最优序列查找public:operator int() const{return cd;}//返回常数 cdint len();public:int *x,s,cd,*low,*high;//x表示当前节点的电路板排列，s表示当前节点排列好的电路板的数//表示当前节点的最大长度，low，high分别表当前节点表示每一个连接块的第一个，和最后一个电路板//的位置};//编写类的len()函数,求出当前节点的连接块长度的最大值int boardnode::len(){int tmp=0;for(int k=1;k=m;k++)if(low[k]=n high[k]0 tmphigh[k]-low[k])tmp=high[k]-low[k];return tmp;}int fifioboards(int **b,int n,int m,int *bestx)//n为电路板的数量，m为连接块的数量 {// int bestd;queueboardnode q;//声明boardnode类的节点队列qboardnode e;e.x=new int[n+1];//为数组指针x分配n+1个动态空间，存储当前的排列e.s=0;//最初时，排列好的电路板的数目为0e.cd=0;e.low=new int[m+1];//存储每个连接块的第一个电路板的位置e.high=new int[m+1];//存储每个连接块的最后一个电路板的位置 for(int i=1;i=m;i++){e.high[i]=0;//初始化开始时的每个连接块的最后一个电路板的位置为0，表示连接块i还没有电路板放入e.x的排列中e.low[i]=n+1;//初始化开始时的每个连接块的第一个电路板的位置为n+1，表示连接块i还没有电路板放入e.x的排列中}for(i=1;i=n;i++)e.x[i]=i;//初始化e.x的排列为1，2,3.....nint bestd=n+1;//最优距离bestx=0;//记录当前最优排列do{if(e.s==n-1)//当已排列了n-1个时{//判断是否改变每个连接块的最后一个电路板的位置for(int j=1;j=m;j++)if(b[e.x[n]][j] ne.high[j])e.high[j]=n;int ld=e.len();//存储当前节点的各连接块长度中的最大长度//如果当前的最大长度小于了n+1if(ldbestd){delete[] bestx;bestx=e.x;bestd=ld;//最优距离}else delete[] e.x;//删除分配给e.x的数组空间delete[] e.low;//删除分配给e.low的数组空间delete[] e.high;//删除分配给e.high的数组空间}else{int curr=e.s+1;//rr记录现在应该排列第几个电路板for(int i=e.s+1;i=n;i++)//处理扩展节点下一层所有子节点{boardnode n;n.low=new int[m+1];//与if中的意思相同n.high=new int[m+1];for(int j=1;j=m;j++){n.low[j]=e.low[j];//将e.low[]中的值赋给n.low[]n.high[j]=e.high[j];if(b[e.x[i]][j]){if(currn.low[j])n.low[j]=curr;//若当前节点连接块j的第一个电路板的位置比现在正在排列的电路板的位置还小if(currn.high[j])n.high[j]=curr;}}n.cd=n.len();//如果，当前节点的最大长度小于了最优长度则：if(n.cdbestd){n.x=new int[n+1];n.s=e.s+1;for(int j=1;j=n;j++)n.x[j]=e.x[j];n.x[n.s]=e.x[i];//交换位置n.x[i]=e.x[n.s];//交换位置q.push(n);//将节点n加入队列中}else{delete[] n.low;delete[] n.high;}//printf(%d,bestd);}delete[] e.x;//当前扩展节点所有子节点均考虑，变成死结点} //try{if(!q.empty()){e=q.front(); //取队列首节点作为扩展节点q.pop();}else return bestd;//}//catch(outofbounds)//{//return bestd;//}//printf(finish);}while(!q.empty());return bestd;return 1;}//测试void main(){//scanf(%d%d,n,m);cinnm;int **b=new int*[n+1];for (int t=0; t=n; t++)b[t] = new int[m+1];for(int i=1;i=n;i++)for(int j=1;j=m;j++)cinb[i][j];//scanf(%d,b[i][j]);int *bestx=new int[n+1];int bestd=0;bestd=fifioboards(b,n,m,bestx);printf(%d\n,bestd);for(i=1;i=n;i++){coutbestx[i] ;}coutendl;}//6-6 经典n皇后问题//description:经典n皇后问题广度优先建议n=14解空间为子集树 //参考答案说排列树是不正确的，本例打印n*n棋盘的所有解，即放置方法 #include iostream#include fstream#include algorithm#include functional#include queueusing namespace std;//本例子直接输入棋盘大小，不用文件//ifstream in(input.txt); //请在项目文件夹下新建一个input.txt//ofstream out(output.txt);class node{public:node(int n){t = 0;this-n = n;loc = new int[n + 1];for (int i = 0; i= n; ++i){loc[i] = 0;}}node(const node other){this-t = other.t;this-n = other.n;this-loc = new int [n + 1];for (int i = 0; i = n; ++i){this-loc[i] = other.loc[i];}}int t;//已放置t个皇后【篇二：计算机算法分析与设计(第四版)习题算法分析部分详解(实验二)】>实验内容：算法实现问题2-1、2-5、2-7//2-1 众数问题思路1：先排序，然后再统计，时间复杂度较高。

第8章扩展应用举例练习题一、简答题1．请举出在数据结构课程中讲过的算法里用到穷举思想的算法。

【参考答案】穷举思想是将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有的对象，问题将最终得以解决。

例如在数据结构课程中讲到的朴素的字符串匹配算法。

2．请举出在数据结构课程中讲过的算法里用到分治思想的算法。

【参考答案】分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。

可以采用递归的方式求解这些子问题，然后将各子问题的解合并得到原问题的解。

在数据结构课程中使用了分治算法的例子有快速排序和归并排序等。

3．请举出在数据结构课程中讲过的算法里用到贪心思想的算法。

【参考答案】贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。

因此能够使用贪心算法的问题必须满足下面的两个性质：1.整体的最优解可以通过局部的最优解来求出；2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。

在数据结构课程中使用贪心算法的例子有：哈夫曼编码；单源最短路径；最小生成树的Prim算法和Kruskal 算法等。

4．请举出在数据结构课程中讲过的算法里用到搜索思想的算法。

【参考答案】搜索算法的实现类似于图或树的遍历，通常可以有两种不同的实现方法，即深度优先搜索(DFS--Depth First search)和广度优先搜索(BFS--Breadth First Search)。

深度优先搜索：深度优先搜索所遵循的搜索策略是尽可能"深"地搜索树。

它的基本思想是:为了求得问题的解，先选择某一种可能情况向前(子结点)探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。

深度优先搜索的实现方式可以采用递归或者栈来实现。

算法（第四版）C#习题题解——2.3写在前⾯习题&题解2.3.1解答2.3.2解答2.3.3解答N / 2在快速排序中，⼀个元素要被交换，有以下两种情况1.该元素是枢轴，在切分的最后⼀步被交换2.该元素位于枢轴错误的⼀侧，需要被交换到另⼀侧去注意，以上两种情况在⼀次切分中只会出现⼀次⾸先来看第⼀种情况，如果⼀个元素变成了枢轴那么在之后的切分中该元素会被排除，不存在后续的交换。

因此我们的⽬标应该是：最⼤的元素总是出现在错误的⼀侧，同时切分的次数尽可能多。

接下来我们来思考如何构造这样的数组由于我们针对的是最⼤的元素，因此「错误的⼀侧」就是枢轴的左侧。

为了使切分的次数尽可能多，我们需要保持最⼤值移动的距离尽量短。

但如果每次只移动⼀位的话，下⼀次切分时最⼤值就会变成枢轴例如 4 10 3 5 6，枢轴为 4，交换后数组变为：4 3 105 6随后 4 和 3 交换3 4 10 5 6下⼀次切分时 10 会变成枢轴，不再参与后续的切分。

因此我们需要让最⼤值每次移动两个元素。

考虑下⾯的数组：2 10 4 1 63 8 5 7 9第⼀次切分的时候，枢轴为 2，10 和 1 进⾏交换数组变为：2 1 4 10 63 8 5 7 9随后枢轴交换，数组变为：1 2 4 10 6 3 8 5 7 9第⼆次切分，枢轴为 4，10 和 3 进⾏交换。

1 2 4 3 6 10 8 5 7 9随后枢轴交换数组变为：1 2 3 4 6 10 8 5 7 9第三次切分，枢轴为 6，10 和 5 交换1 2 3 4 6 5 8 10 7 9随后枢轴交换，数组变为：1 2 3 4 5 6 8 10 7 9第四次切分，枢轴为 8，10 和 7 交换1 2 3 4 5 6 8 7 10 9枢轴交换，数组变为1 2 3 4 5 6 7 8 10 9最后⼀次切分，枢轴为 10，直接交换1 2 3 4 5 6 7 8 9 10我们可以总结出要构造这样的数组的模板a2 max a3 a1其中 a1 < a2 < a3 < maxmax 每轮切分移动两格，总共切分 N/ 2 次。

《C语言程序设计》课后习题答案（第四版）谭浩强第1章程序设计和c语言11.1什么是计算机程序11.2什么是计算机语言11.3c语言的发展及其特点31.4最简单的c语言程序51.4.1最简单的c语言程序示例61.4.2c语言程序结构101.5运行c程序的步骤与方法121.6程序设计的任务141-5#includeintmain（）{printf(\printf(\verygood!\\n\\n\printf（\return0；}1-6#includeintmain(){inta,b,c,max;printf（\scanf（\max=a；if（maxprintf(\return0;}第2章算法——程序的灵魂162.1算法是什么162.2简单算法示例172.3算法的特点212.4怎样表示一个算法222.4.1用自然语言表示算法222.4.2用流程图表示算法222.4.3三种基本结构和改进的流程图262.4.4用NS流程图表示算法282.4.5用伪码312表示算法。

4.6用计算机语言32表示算法2.5结构化程序设计方法34习题36第三章最简单的c语言编程-顺序编程373.1顺序编程的例子373.2数据的表现形式及其运算393.2.1常量和变量393.2.2数据类型423.2.3整型数据443.2.4字符型数据473.2.5浮点型数据493.2.6如何确定常数的类型513.2.7运算符和表达式523.3c语句573.3.1c语句的作用和分类573.3.2最基本的语句-赋值语句593.4数据输入和输出653.4.1输入和输出示例653.4.2有关数据输入输出的概念673.4.3用printf函数输出数据683.4.4用scanf函数输入数据753.4.5字符数据的输入输出78习题823-1#include#includeintmain（）{floatp，r，n；r=0.1；n=10；p=pow(1+r,n);printf(\return0;}3-2-1#include#includeintmain(){r5，r3，r2，r1，r0，p，p1，p2，p3，p4，p5；p=1000；r5=0.0585;r3=0.054;r2=0.0468;r1=0.0414;r0=0.0072;p1=p*（（1+r5）*5）；//5年一次定期存款p2=p*(1+2*r2)*(1+3*r3);//先存2年期，到期后将本息再存3年期p3=p*(1+3*r3)*(1+2*r2);//先存3年期，到期后将本息再存2年期p4=p*pow（1+r1,5）；//存1年，到期后再存1年本息，连续存5次P5=P*pow（1+R0/4,4*5）//存款存续期。

编译原理教程第四版答案【篇一：编译原理教程课后习题答案——第三章】.1 完成下列选择题：(1) 文法g：s→xsx|y所识别的语言是a. xyxb. (xyx)*c. xnyxn(n≥0)d. x*yx*a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同(3) 采用自上而下分析，必须。

a. 消除左递 a. 必有ac归b. 消除右递归c. 消除回溯d. 提取公共左因子(4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，则。

b. 必有cac. 必有bad. a～c都不一定成立(5) 在规范归约中，用a. 直接短语b. 句柄c. 最左素短语d. 素短语a. 归约b. 移进c. 接受d. 待约a. lalr文法b. lr(0)文法c. lr(1)文法d. slr(1)文法(8) 同心集合并有可能产生新的冲突。

a. 归约b. “移进”/“移进”c.“移进”/“归约”d. “归约”/“归约”【解答】 (1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d3.2 令文法g[n]为g[n]: n→d|ndd→0|1|2|3|4|5|6|7|8|9(1) g[n]的语言l(g[n])是什么?(2) 给出句子0127、34和568的最左推导和最右推导。

【解答】(1) g[n]的语言l(g[n])是非负整数。

(2) 最左推导： nndnddnddddddd0ddd01dd012d0127nnddd3d34nndnddddd5dd56d568最右推导： nndn7nd7n27nd27n127d1270127nndn4d434nndn8nd8n68d685683.3 已知文法g[s]为s→asb|sb|b，试证明文法g[s]为二义文法。

【解答】由文法g[s]：s→asb|sb|b，对句子aabbbb可对应如图3-1所示的两棵语法树。

算法第四版课后答案【篇一：计算机操作系统(第四版)课后习题答案第三章】t>1，高级调度与低级调度的主要任务是什么？为什么要引入中级调度？【解】（1）高级调度主要任务是用于决定把外存上处于后备队列中的那些作业调入内存，并为它们创建进程，分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。

（2）低级调度主要任务是决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。

（3）引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。

为此，应使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调至外存上去等待，称此时的进程状态为就绪驻外存状态或挂起状态。

当这些进程重又具备运行条件，且内存又稍有空闲时，由中级调度决定，将外存上的那些重又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上，等待进程调度。

3、何谓作业、作业步和作业流？【解】作业包含通常的程序和数据，还配有作业说明书。

系统根据该说明书对程序的运行进行控制。

批处理系统中是以作业为基本单位从外存调入内存。

作业步是指每个作业运行期间都必须经过若干个相对独立相互关联的顺序加工的步骤。

作业流是指若干个作业进入系统后依次存放在外存上形成的输入作业流；在操作系统的控制下，逐个作业进程处理，于是形成了处理作业流。

4、在什么情冴下需要使用作业控制块jcb？其中包含了哪些内容？【解】每当作业进入系统时，系统便为每个作业建立一个作业控制块jcb，根据作业类型将它插入到相应的后备队列中。

jcb 包含的内容通常有：1) 作业标识2)用户名称3)用户账户4)作业类型（cpu繁忙型、i/o芳名型、批量型、终端型）5)作业状态6)调度信息（优先级、作业已运行）7)资源要求8)进入系统时间9) 开始处理时间10) 作业完成时间11) 作业退出时间12) 资源使用情况等5．在作业调度中应如何确定接纳多少个作业和接纳哪些作业？【解】作业调度每次接纳进入内存的作业数，取决于多道程序度。

第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。

若f=Ο(g)，则必然存在常数c1>0和n0，使得∀n≥n0，有f≤c1*g(n)。

由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。

必要性。

同理，若g=Ω(f)，则必然存在c2>0和n0，使得∀n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。

2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得∀n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。

由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。

3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。

证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得∀n≥n1，有F(n) ≤ c1 (f(n)+g(n))= c1 f(n) + c1g(n)≤ c1*max{f,g}+ c1*max{f,g}=2 c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g))对于Ω和Θ同理证明可以成立。

4）log(n!)= Θ(nlogn)证明：∙由于log(n!)=∑=n i i 1log ≤∑=ni n 1log =nlogn ，所以可得log(n!)= Ο(nlogn)。

∙由于对所有的偶数n 有，log(n!)= ∑=n i i 1log ≥∑=n n i i 2/log ≥∑=nn i n 2/2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。

当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得∀n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。