第四章算法基础

第四章算法基础

单项选择题（请在（）内填写答案）

（）1. 算法可以没有__A_。

A: 输入B: 输出C: 输入和输出D:结束

（）2. 用于处理重复动作的结构是__C____。

A:顺序B: 判断C: 循环D: 逻辑

（）3. 将一组数据按照从小到大的顺序进行排列的算法称为__B____。

A: 查找B: 排序C: 递归D: 迭代

（）4. 要从一组数据中找到其中一个数据的算法称为___D___。

A: 迭代B: 排序C: 递归D: 查找

（）5. 流程图中的矩形框用于表示___C___。

A: 输入或输出B: 判断C: 计算或赋值D: 起止

（）6. 从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果的算法是___B___。

A: 列举B: 迭代C: 递归D: 查找

（）7. 将待排序的数据依次进行相邻两个数据的比较，如不符合排列顺序要求就交换的排序方法称为__A____。

A: 冒泡排序B: 选择排序C: 插入排序D: 二分排序

（）8. 对于有序列表使用的查找算法是__B____。

A: 顺序查找B: 折半查找C: 冒泡查找D: 排序查找

（）9. 算法的时间复杂度是指___A___。

A: 执行算法程序所需的时间B: 算法执行过程中的所需要的基本运算次数

C: 算法程序中的指令条数D: 算法程序的长度

（）10. 算法执行过程中所需的存储空间称为算法的__B____。

A: 时间复杂度B: 空间复杂度C: 计算工作量D: 工作空间

（）11. 下面叙述正确的是___C___。

A: 算法的执行效率与数据的存储结构无关

B: 算法的空间复杂度是指算法程序中的指令的条数

C: 算法的无穷性是指算法必须在执行有限步后终止

D: 以上3种描述都不对

1

习题答案第四章 算法设计与分析 吕国英

算法设计与分析（第二版）主编：吕国英 习题答案 第四章 1. #include int main(void) { int buf[100]; int n; int i,j,k; scanf("%d",&n); for(i=0;i=10) { buf[j+1]+=buf[j]/10; buf[j]=buf[j]%10; } } for(i=n-1;i>=0;i--) printf("%d",buf[i]); printf("\n"); return 0; } 2. #include int main(void) { int n=2; int i;

for(i=1;i<=9;i++) { n=(n+2)*2; } printf("%d\n",n); return 0; } 3. #include int main(void) { int a=54; int n; int m; printf("计算机先拿3张牌\n"); a=a-3; while(a>=0) { printf("还剩%d张牌\n",a); printf("你拿几张？请输入："); scanf("%d",&n); if(n>4||n<1||n>a) { printf("错误！重新拿牌\n"); continue; } a=a-n; printf("还剩%d张牌\n",a); if(a==0) break; m=5-n; printf("计算机拿%d\n",m); a=a-m; } return 0; } 4. #include int d; int a1,a2; int fun(int n); int main(void) { int n;

第4章 数据结构与算法 习题与答案

第四章习题（P111-113） 一、复习题 1、试述数据和数据结构的概念及其区别。 数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。（P93） 2、列出算法的五个重要特征并对其进行说明。 算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须有确切的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。（P95） 3、算法的优劣用什么来衡量？试述如何设计出优秀的算法。 时间复杂度空间复杂度（P97-98） 4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？ 线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。（P99-105） 5、简述树与二叉树的区别；简述树与图的区别。 树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。（P102-P104） 6、请举出遍历算法在实际中使用的例子。 提示：根据实际生活中需要逐个访问处理的情况举例。 7、编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。 提示：根据查找算法和串中求子串的算法，查找输入串中以单个字符形式的子串。 8、若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同? (1) 搜索失败； (2) 搜索成功，且表中只有一个关键码等于给定值k的对象； (3) 搜索成功，且表中有若干个关键码等于给定值k的对象，要求一次搜索找出所有对象。

式算法设计基础(第四章)路由算法

分布式算法设计基础 第四章路由算法（Routing Algorithms） 一般地，一个进程并不直接用一个其他每一个结点联结，一个结点能够直接发送信息邮包的结点集合称之为该结点的邻居。所谓路由是一个刻画决策过程的术语，根据这个决策过程，一个结点选择其邻居结点中的一个（或一个以上），使这条路上的邮包最终到达目的地。设计路由算法的目的是对每个结点产生一个决策过程，以便执行该功能并确保每个邮包的投递。 显然，每个结点都要保留网络拓扑结构的一些信息作为（局部）决策的工作基础，我们把这些信息与路由表联系在一起，根据这些表的引导，路由问题可以很自然地分成两部分： （1）表计算在网络初始化的时候计算路由表，且当网络拓扑结构发生改变时，该表必须重新计算更新； （2）邮包转递通常，我们从以下几个方面来判断和评价一个“好”的路由方法： （3）正确性算法必须把递交给网络的每一个邮包投递到它的最终目的地； （4）复杂性路由表的计算算法应该尽可能地使用极少的信息、时间和存储； （5）有效性算法必须经过“好”的路径发送邮包，例如，路径只承受小的时间延迟，并且保证整个网络高度流畅（通畅）。若一个路由算法使用“最佳”路径，则该算法称为最优的，令人满意的； （6）健壮性在拓扑结构被改变的情况下（如增加或删除一个结点和通道），算法能自动更新路由表，以便在修改后的网络中执行路由选择功能； （7）适应性算法应能调整路由表以便平衡通道和结点负载，以免这些要经过的结点和通道过于忙碌； （8）公平性算法应该以相同的优先级公平地为每个用户提供服务。 这些标准并不一定都能达到，其中一些有时候是相互冲突的，大多数算法只能针对其中的一部分是比较好的。 一般地，网络的拓扑结构抽象地用一个图来表示，于是，算法的最优性依赖于图中什么是“最佳”路径。有几种“最佳”的概念，每一种都与

计算机算法基础实验报告

课程实验报告题目：计算机算法基础课程实验 课程名称：计算机算法基础 专业班级：计算机科学与技术班 学号： 姓名： 指导教师： 报告日期：2012年11月5日 计算机科学与技术学院

题目1、比较快速分类算法和归并分类算法时间效率 一、方案设计 本实验要求比较快速分类算法和归并分类算法的效率，于是我们很容易联想到通过对比两种算法在处理相同数据所使用的时间来比较两种算法的时间效率。 因此先定义一个函数random（）来生成设定个数个随机数，并以文件形式输出。 快速分类算法和归并分类算法均使用文件形式读入数据并以文件形式输出 分类结果，中间过程没有人工参与，这就保证了程序运行时间基本和分类时间一致，因此算法所用时间根据调试窗口所给出程序运行时间为准。试验中快速分类算法和归并分类算法分别在不同的工程文件中实现，对于不同个数的数据分次测试。 为了使两种算法更具有可比性，两种算法都使用递归方法实现。 已知快速分类算法和归并分类算法的平均情况时间都是O(nlogn)，但是最坏情况下快速分类算法算法时间复杂度为O(n2)，而归并分类算法的时间下界为 Ω(nlogn)，因此在比较了两种算法在一般情况下的时间效率之后还要比较两种算法在最坏情况下的时间效率。快速分类算法的最坏情况为被分类数据有序。二、方案实现 随机数据生成： #include #include #include #define MAX 40000 //生成数据个数，根据不同要求改变 int main() { int a[MAX]; //整形数组a[MAX]存放生成的随机数 long i; memset(a,0,sizeof(a)); FILE *fp; fp = fopen("example.txt","wt"); srand((int)time(0)); for(i=0; i

《计算机算法基础》课后答案

计算机算法分析—习题课 第四章：2 、3、5、6、10、11、23 P99-2 在下列情况下求解4.1节的递归关系式T(n)= ()2(/2) () gnnTnfn???足够小＋否则当①g(n)=O(1)和f(n)=O(n)；②g(n)=O(1)和f(n)=O(1)。P99-2递推表达式 设n=2k则: T(n)=T(2k)=2T(2k-1)+f(2k) =2(2 T(2k-2)+f(2k-1)) +f(2k) =22T(2k-2)+21f(2k-1)+ f(2k) =………… =2kT(1)+2k-1f(2)+2k-2f(22)+…+20f(2k) =2kg(n)+ 2k-1f(2)+2k-2f(22)+…+20f(2k) g(n)=O(1)和f(n)=O(n) 当g(n)=O(1)和f(n)=O(n)时 不妨设g(n)=a，f(n)=bn，则： T(n)=T(2k) = 2ka+ 2k-1*2b+2k-2*22b+…+20*2kb =2ka+kb2k =an+bnlog2n=O(nlog2n) g(n)=O(1)和f(n)=O(1)

当g(n)=O(1)和f(n)=O(1)时， 不妨设g(n)=c，f(n)=d，则： T(n)=T(2k) =c2k+2k-1d+2k-2d+ (20) =c2k+d(2k-1) =(c+d) n-d=O(n) P99-3 根据2.2节开始所给出的二分检索策略，写一个二分检索的递归过程。Procedure BINSRCH(A, low, high, x, j) integer mid if low≤highthen mid←?(low+high)/2 ? if x=A(mid) then j←mid; endif if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x

第四章算法基础

第四章算法基础 单项选择题（请在（）内填写答案） （）1. 算法可以没有__A_。 A: 输入B: 输出C: 输入和输出D:结束 （）2. 用于处理重复动作的结构是__C____。 A:顺序B: 判断C: 循环D: 逻辑 （）3. 将一组数据按照从小到大的顺序进行排列的算法称为__B____。 A: 查找B: 排序C: 递归D: 迭代 （）4. 要从一组数据中找到其中一个数据的算法称为___D___。 A: 迭代B: 排序C: 递归D: 查找 （）5. 流程图中的矩形框用于表示___C___。 A: 输入或输出B: 判断C: 计算或赋值D: 起止 （）6. 从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果的算法是___B___。 A: 列举B: 迭代C: 递归D: 查找 （）7. 将待排序的数据依次进行相邻两个数据的比较，如不符合排列顺序要求就交换的排序方法称为__A____。 A: 冒泡排序B: 选择排序C: 插入排序D: 二分排序 （）8. 对于有序列表使用的查找算法是__B____。 A: 顺序查找B: 折半查找C: 冒泡查找D: 排序查找 （）9. 算法的时间复杂度是指___A___。 A: 执行算法程序所需的时间B: 算法执行过程中的所需要的基本运算次数 C: 算法程序中的指令条数D: 算法程序的长度 （）10. 算法执行过程中所需的存储空间称为算法的__B____。 A: 时间复杂度B: 空间复杂度C: 计算工作量D: 工作空间 （）11. 下面叙述正确的是___C___。 A: 算法的执行效率与数据的存储结构无关 B: 算法的空间复杂度是指算法程序中的指令的条数 C: 算法的无穷性是指算法必须在执行有限步后终止 D: 以上3种描述都不对 1

算法设计与分析(简略版)

中国地质大学研究生课程论文封面 课程名称算法设计与分析 教师姓名 XXXXXX 研究生姓名侉哥 研究生学号 1201666666 研究生专业 XXXXXXXXXXXXX 所在院系计算机学院 类别: A.博士 B.硕士√ C.进修生 日期: 2016.1.12

《算法设计与分析》课程报告 本学期，我选修了XXX教授的《算法分析与算法设计》这门课程。课堂上，戴老师条理清晰、深入浅出地为我们讲解了算法复杂度、分支算法、贪心算法、动态规划算法、基本检索与周游方法、回溯算法和分支-限界法等知识内容。此外，还为我们介绍了NP-难度和NP-完全的问题。 第一章导引与基本数据结构 老师首先引入编程实现两矩阵相乘和编程实现求证平行四边形两个例子，举例说明现阶段计算机算法可以解决的问题（计算问题）和不可以解决（几何证明）的问题。 接着老师指出算法是指计算的方法，而计算是基于规则的变换，物理角度可以理解为是基于规则的物理状态的变换，也可以理解为是基于规则的信息的变换。接着老师讲解了算法的三个重要特性：无二义性、能解性、有限性。当然算法的特性还包括输入和输出。 之后老师讲解了算法设计与分析的含义，讲了计算模型的假设和两个重要的量：问题的规模和频率计数。也就是空间复杂度和时间复杂度的分析方法，根据时间复杂度，算法一般可以分为多项式时间复杂度（P算法）和指数时间复杂度（NP算法）。 多项式时间内可以执行完成的算法是P算法，例如时间复杂度为： O(1)

第四章答案

一、填空题 1、13 14 14 12 2、段号、段在内存的起始地址、段长度 3、静态重定位在_____时进行；而动态重定位在_____进行.。 答案：程序装入内存 程序执行时 4、在页式存储管理系统中,常用的页面淘汰算法有：_____，选择淘汰不再使用或最远的将来才使用的页；_____，选择淘汰在主存驻留时间最长的页；_____，选择淘汰离当前时刻最近的一段时间内使用最少的页 。 答案：最佳算法 先进先出算法 最近最少使用 二、计算题 1、假定某页式管理系统中，主存为128KB ，分成32块，块号为0、1、 2、 3、…、31；某作业有5块，其页号为0、1、2、3、4，被分别装入主存的3、8、 4、6、9块中。有一逻辑地址为[3，70]。试求出相应的物理地址（其中方括号中的第一个元素为页号，第二个元素为页内地址，按十进制计算），并画图说明地址变换过程。 答：128KB ，分成32块，页面大小为217/25=212=4K 根据题意，页号为3的这一页装入内存第6块中，逻辑地址[3，70]对应的物理地址=6*4096+70=24646（6046H ） 2、在某段式存储管理系统中，有一作业共4段，段号为0、1、2、3，段表如下表所示。 某系统段表 试计算逻辑地址[0，45]，[1，50]，[2，60]，[3，90]相应的主存地址。当无法进行地址变换时，应说明产生何种中断（方括号内分别为段号和段内地址，按十进制）。 答： 380 85 3 1 - 120 2 0 2600 400 1 0 1500 500 0 状态 主存起始地址 段长 段号

(1) 对于逻辑地址[0,45]，因45<500，其逻辑地址合法，对应的主存地址为1500+45=1545。 (2) 对于逻辑地址[1,50]，因50<400，其逻辑地址合法，对应的主存地址为2600+50=2650。 (3) 对于逻辑地址[2,60]，虽60<120，但状态为1、该段不在内存中，产生缺段中断。 (4) 对于逻辑地址[3,90]，因90>85，其逻辑地址非法，所以产生地址越界中断。 3、某请求页式存储管理，允许用户编程空间为32个页面（每页1KB ），主存为16KB 。如有一个用户程序有10页长，且某时刻该用户页面映射表如下表所示。如果程序执行时遇到以下两个虚地址：0AC5H 、1AC5H ，试计算它们对应的物理地址。 页面映射表 答：根据题意，逻辑地址为15位， 答：由题设条件可知，分页存储管理系统的逻辑地址结构为： 逻辑地址0AC5H 的二进制表示如下： 逻辑地址0AC5H 的页号为2，从上表所示可知该页对应的物理块号B 为4。所以，将二进制表示中的页号换为块号得： 用16进制表示即为12C5H （4805）。 逻辑地址1AC5H 的二进制表示如下： 即，逻辑地址1AC5H 的页号为6 4、设正在处理器上执行的一个进程的页表如下表所示。表中的虚页号和物理块号是十进制数，起始页号（块号）均为0。所有的地址均是存储器字节地址。页的大小为1024字节。 （1）详述在设有快表的请求分页存储器管理系统中，一个虚假地址转换成物理内存地 8 7 4 10 0 1 2 3 物理块号 虚页号

第4章ADAMS软件算法基本理论-(陈立平)机械系统动力学分析及ADAMS应用

第4章ADAMS软件基本算法 本章主要介绍ADAMS软件的基本算法，包括ADAMS建模中的一些基本概念、运动学分析算法、动力学分析算法、静力学分析及线性化分析算法以及ADAMS软件积分器介绍。通过本章的学习可以对ADAMS软件的基本算法有较深入的了解，为今后合理选择积分器进行仿真分析提供理论基础，为更好地使用ADAMS打下良好的理论基础。 4.1 ADAMS建模基础 ADAMS利用带拉格朗日乘子的第一类拉格朗日方程导出――最大数量坐标的微分－代数方程（DAE）。它选取系统内每个刚体质心在惯性参考系中的三个直角坐标和确定刚体方位的三个欧拉角作为笛卡尔广义坐标，用带乘子的拉格朗日第一类方程处理具有多余坐标的完整约束系统或非完整约束系统，导出以笛卡尔广义坐标为变量的动力学方程。 4.1.1 参考标架 在计算系统中构件的速度和加速度时，需要指定参考标架，作为该构件速度和加速度的参考坐标系。在机械系统的运动分析过程中，有两种类型的参考标架——地面参考标架和构件参考标架。地面参考标架是一个惯性参考系，它固定在一个“绝对静止”的空间中。通过地面参考标架建立机械系统的“绝对静止”参考体系，属于地面标架上的任何一点的速度和加速度均为零。对于大多数问题，可以将地球近似为惯性参考标架，虽然地球是绕着太阳旋转而且地球还有自转。对于每一个刚性体都有一个与之固定的参考标架，称为构件参考标架，刚性体上的各点相对于该构件参考标架是静止的。 4.1.2 坐标系的选择 机械系统的坐标系广泛采用直角坐标系，常用的笛卡尔坐标系就是一个采用右手规则的直角坐标系。运动学和动力学的所有矢量均可以用沿3个单位坐标矢量的分量来表示。坐标系可以固定在一个参考标架上，也可以相对于参考框架而运动。合理地设置坐标系可以简化机械系统的运动分析。在机械系统运动分析过程中，经常使用3种坐标系：（1）地面坐标系（Ground Coordinate System）。地面坐标系又称为静坐标系，是固定在地面标架上的坐标系。ADAMS中，所有构件的位置、方向和速度都用地面坐标系表示。 （2）局部构件参考坐标系（Local Part Reference Frame，LPRF）。这个坐标系固定在构件上并随构件运动。每个构件都有一个局部构件参考坐标系，可以通过确定局部构件参考坐标系在地面坐标系的位置和方向，来确定一个构件的位置和方向。在ADAMS中，局部构件参考坐标系缺省与地面坐标系重合。 （3）标架坐标系（Marker System）。标架坐标系又称为标架，是为了简化建模和分析在构件上设立的辅助坐标系，有两种类型的标架坐标系：固定标架和浮动标架。固定标架

《计算机算法基础》第三版,课后习题答案

4.2在下列情况下求解递归关系式 T(n)= () 2(/2)() g n T n f n ? ? + ?否则 足够小 n 当①n=2k g(n)= O(1)和f(n)= O(n)； ②n=2k g(n)= O(1)和f(n)= O(1)。 解: T(n)=T(2k)=2 T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1)) +f(2k) =22T(2k-2)+21 f(2k-1)+ f(2k) =…… =2k T(1)+2k-1f(2)+2k-2f(22)+…+20f(2k) =2k g(n)+ 2k-1f(2)+2k-2f(22)+…+20f(2k) ①当g(n)= O(1)和f(n)= O(n)时， 不妨设g(n)=a，f(n)=bn，a，b为正常数。则 T(n)=T(2k)= 2k a+ 2k-1*2b+2k-2*22b+…+20*2k b =2k a+kb2k =an+bnlog2n= O(nlog2n) ②当g(n)= O(1)和f(n)= O(1)时， 不妨设g(n)=c，f(n)=d，c，d为正常数。则 T(n)=T(2k)=c2k+ 2k-1d+2k-2d+…+20d=c2k+d(2k-1) =(c+d)n-d= O(n) 4.3根据教材中所给出的二分检索策略，写一个二分检索的递归过程。Procedure BINSRCH(A, low, high, x, j) integer mid if low≤high then mid←??2/) (high low+ if x=A(mid) then j←mid; endif if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x

《计算机算法基础》第三版_课后习题答案

上机实验书上121页 5。2 5。3 书上151 6。1 6。3 6。6 他说搞懂这几题和实验就没问题了 4.2在下列情况下求解递归关系式 T(n)= () 2(/2)() g n T n f n ? ? + ?否则 足够小 n 当①n=2k g(n)= O(1)和f(n)= O(n)； ②n=2k g(n)= O(1)和f(n)= O(1)。 解: T(n)=T(2k)=2 T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1)) +f(2k) =22T(2k-2)+21 f(2k-1)+ f(2k) =…… =2k T(1)+2k-1f(2)+2k-2f(22)+…+20f(2k) =2k g(n)+ 2k-1f(2)+2k-2f(22)+…+20f(2k) ①当g(n)= O(1)和f(n)= O(n)时， 不妨设g(n)=a，f(n)=bn，a，b为正常数。则 T(n)=T(2k)= 2k a+ 2k-1*2b+2k-2*22b+…+20*2k b =2k a+kb2k =an+bnlog2n= O(nlog2n) ②当g(n)= O(1)和f(n)= O(1)时， 不妨设g(n)=c，f(n)=d，c，d为正常数。则 T(n)=T(2k)=c2k+ 2k-1d+2k-2d+…+20d=c2k+d(2k-1) =(c+d)n-d= O(n) 4.3根据教材中所给出的二分检索策略，写一个二分检索的递归过程。Procedure BINSRCH(A, low, high, x, j) integer mid if low≤high then mid←??2/) (high low+ if x=A(mid) then j←mid; endif if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x

C++第四章习题解答.

第四章类与对象习题 一.基本概念与基础知识自测题 4.1 填空题 5.1.1 引入类定义的关键字是（1）。类的成员函数通常指定为（2），类的 数据成员通常指定为（3）。指定为（4）的类成员可以在类对象所在域中的任何位置访问它们。通常用类的（5）成员表示类的属性，用类的（6）成员表示类的操作。 答案： （1）class （2）公有的public （3）私有的private （4）公有的public （5）数据 （6）函数 4.1.2 类的访问限定符包括（1）、（2）和（3）。私有数据通常由 （4）函数来访问（读和写）。这些函数统称为（5）。 答案： （1）public（公有的） （2）private（私有的） （3）protected（保护的） （4）公有的成员函数 （5）类的接口 4.1.3 通常在逻辑上，同一类的每个对象都有（1）代码区，用以存储成员函数。而 在物理上通常只有（2）代码区。只有在（3）定义，并（4）的函数和加了关键字（5）的函数例外。 答案： （1）独立的 （2）共用的 （3）在类说明中 （4）不包括循环等复杂结构 （5）inline 4.1.4 C++中支持三种域：（1）、（2）、（3）。函数域被包括在 （4）中，全局域被包括在（5）中。using指示符以关键字using开头，后面是关键字（6），最后是（7）。这样表示以后在该名字空间中所有成员都（8）。如不使用using指示符则在使用时要加::，称为（9）运算符。 答案： （1）局部域（local scope） （2）名字空间域（namespace scope） （3）类域（class scope） （4）局部域 （5）名字空间域 （6）namespace （7）名字空间名

第四章习题及答案

第四章存储器管理 1．为什么要配置层次式存储器？ 答：设置多个存储器可以使存储器两端的硬件能并行工作；采用多级存储系统，特别是Cache 技术，是减轻存储器带宽对系统性能影响的最佳结构方案；在微处理机内部设置各种缓冲存储器，减轻对存储器存取的压力。增加CPU中寄存器数量大大缓解对存储器压力。 2．可采用哪几种方式将程序装入内存？它们分别适用于何种场合？ 答：（1）绝对装入方式，只适用于单道程序环境。 （2）可重定位装入方式，适用于多道程序环境。 （3）动态运行时装入方式，用于多道程序环境；不允许程序运行时在内存中移位置。 3．何谓静态链接？何谓装入时动态链接和运行时的动态链接？P120 答：静态链接是指在程序运行前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开的链接方式。 装入时动态链接是指将用户源程序编译后得到的一组目标模块，在装入内存时采用边装入边链接的链接方式。运行时动态链接是指对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行的链接。 4．在进行程序链接时，应完成哪些工作？ 答：由链接程序Linker将编译后形成的一组目标模块，以及它们需要的库函数链接在一起，形成一个完整的装入模块Load Module。主要工作是修改程序内的相对地址和修改目标程序中的外部调用标号。 5．在动态分区分配方式中，应如何将各空闲分区链接成空闲分区链？ 答：在每个分区的起始部分，设置一些控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部设置一个后向指针，通过前后向链接指针，将所有空闲分区链成一个双向链。当分区分配出去后，把状态位由“0”改为“1”。

《计算机算法基础》第三版_课后习题答案

上机实验 书上121页 5。2 5。3 书上151 6。1 6。3 6。6 他说搞懂这几题和实验就没问题了 4.2在下列情况下求解递归关系式 T(n)= ()2(/2)() g n T n f n ??+? 否则足够小n 当①n=2k g(n)= O (1)和f(n)= O (n)； ②n=2k g(n)= O (1)和f(n)= O (1)。 解: T(n)=T(2k )=2 T(2k-1)+f(2k )=2(2 T(2k-2)+f(2k-1)) +f(2k ) =22T(2k-2)+21 f(2k-1)+ f(2k ) =…… =2k T(1)+2k-1f(2)+2k-2f(22)+…+20f(2k ) =2k g(n)+ 2k-1f(2)+2k-2f(22)+…+20f(2k ) ①当g(n)= O (1)和f(n)= O (n)时， 不妨设g(n)=a ，f(n)=bn ，a ，b 为正常数。则 T(n)=T(2k )= 2k a+ 2k-1*2b+2k-2*22b+…+20*2k b =2k a+kb2k =an+bnlog 2n= O (nlog 2n) ②当g(n)= O (1)和f(n)= O (1)时， 不妨设g(n)=c ，f(n)=d ，c ，d 为正常数。则 T(n)=T(2k )=c2k + 2k-1d+2k-2d+…+20d=c2k +d(2k -1) =(c+d)n-d= O (n) 4.3根据教材中所给出的二分检索策略，写一个二分检索的递归过程。 Procedure BINSRCH(A, low, high, x, j) integer mid if low ≤high then mid ←??2/)(high low + if x=A(mid) then j ←mid; endif if x>A(mid) then BINSRCH(A, mid+1, high, x, j); endif if x

操作系统第四章答案汇编

第四章存储器管理 1. 为什么要配置层次式存储器？ 答：这是因为：a.设置多个存储器可以使存储器两端的硬件能并行工作。b.采用多级存储系统，特别是Cache 技术，这是一种减轻存储器带宽对系统性能影响的最佳结构方案。c.在微处理机内部设置各种缓冲存储器，以减轻对存储器存取的压力。增加CPU 中寄存器的数量，也可大大缓解对存储器的压力。 2、可采用哪几种方式将程序装入内存？它们分别适用于何种场合？P119 答：（1）绝对装入方式：绝对装入方式只能将目标模块装入到内存中事先指定的位置。在多道程序环境下，编译程序不可能预知所编译的目标模块应放在内存的何处，困此，绝对装入方式只适用于单道程序环境。 （2）可重定位装入方式：在多道程序环境下，所得到的目标模块的起始地址通常是从0 开始的，程序中的其它地址也都是相对于起始地址计算的。此时应采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。 （3）动态运行时装入方式：可重定位装入方式可将装入模块装入到内存中任何允许的位置，故可用于多道程序环境；但这种方式并不允许程序运行时在内存中移动位置。 3、何谓静态链接？何谓装入时动太链接和运行时的动态链接？P120 答：1、静态链接：在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开，我们把这种事先进行链接的方式称为静态链接方式.2、装入时动态链接：这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。3、运行时动态链接：这是指对某些目标模块的链接，是在程序执行中需要该（目标）模块时，才对它进行的链接。 4、在进行程序链接时，应完成哪些工作？p120 答：静态链接、装入时动态链接、运行时动态链接； 5、在动态分区分配方式中，应如何将各空闲分区链接成空闲分区链？P123 答：为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链，为了检索方便，在分区尾部重复设置状态位和分区大小表目。当分区被分配出去以后，把状态位由“0”改为“1”，此时，前、后向指针已无意义。 6、为什么要引入动态重定位？如何实现？P127 P128 答：a. 为了在程序执行过程中，每当访问指令或数据时，将要访问的程序或数据的逻辑地址转换成物理地址，引入了动态重定位. b. 可在系统中增加一个重定位寄存器，用它来装入(存放)程序在内存中的起始地址，程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的,从而实现动态重定位. 7、在采用首次适应算法回收内存时，可能出现哪几种情况？应怎样处理这些情况？P125 答：1、回收区与插入点的前一个空闲区相邻接，此时应将回收区与插入点的前一分区合并，不必为回收区分配新表项，而只需修改其前一分区的大小。 2、回收区与插入点的后一个空闲区相邻接，此时可将两分区合并，形成新的空闲区，但用回收区的首址作为新空闲区的首址，大小为两者之和。

第04章 算法基础及VB的基本语句

第四章算法基础及VB的基本语句的知识点 习题 考点详细分析 1、能写一些简单的算法，明白算法即是一解题步骤 2、赋值语句和input和msgbox函数 注意不同类型数据的赋值转换，俩函数的参数 3、分支结构与分支结构语句 if语句的三种转换形式 select-case-end select结构语句的使用 4、循环结构与循环结构语句 do-loop结构语句（当型与直到型在条件不满足时区别） for-next结构语句（注意循环控制参数） 循环嵌套（初值的位置、随机函数的使用） （关于算法） 明白算法就是给出解决问题的步骤 给出下列题目的算法： 1、给出一个求一元俩次方程根的算法（ax2+bx+c=0） 2、求一个圆的周长和面积 3、根据个人工资给出交税数目 4、设计一个判断某正整数是一个回文数的算法。（回文数： 该数的左右数字完全对称的自然数，如121、1551等）（关于赋值语句和俩函数） 1、赋值语句的一般形式_______________ 2.当系统执行一个赋值语句时，先求出“=”__右边表达式_____的值，然后再把该值保存到“=”____左边变量_______中，这就是“赋值” 分析：基本概念 答案：右边表达式左边变量 3、针对语句 If I=1 then J=1，下列说法正确的是__C__ (03春) A. I=1 和J=1均为赋值语句 B. 均为关系表达式 C. I=1为关系表达式，J=1为赋值语句

D. I=1为赋值语句，J=1为关系表达式 分析：基本结构语句 答案：C 4、运行下面的程序，单击命令按钮command1，则立即窗口上显示的结果是____(03春) private sub command1_click() dim A as integer,B as Boolean,C as Integer,D as integer A=20/3:B=true:C=B:D=A+C Debug. Print A, D,；A=A + C End sub A、7 6 False B、6 6 5.6 False C、7 6 A=6 D、7 8 A=8 分析：不同数据类型赋值问题 答案：A 5、在文本框Text1中输入数字12，Text2中输入数字34，执行以下语句，只有____B____可使文本框Text3中显示46。 (02秋) A、Text3.Text=Text1.Text & Text2.Text B、Text3.Text=val(Text1.Text) +val( Text2.Text) C、Text3.Text=Text1.Text + Text2.Text D、Text3.Text=val(Text1.Text) & val(Text2.Text) 分析：不同数据类型赋值问题 答案：B 6、据下图写出Inputbox函数中的参数 (00秋) inputbox(________,________,________) 分析：Inputbox函数中的参数 答案：“请输入半径”“输入对话框”10 注意10没有引号 7、如图所示信息框的MSGBOX函数

算法基础知识点复习

第一单元算法基础 1．算法的概念及特点。 （1）复述算法的概念； 答：答案1：书P6——算法是在有限步骤内求解某一问题所使用的具有精确定义的一系列操作规则。 答案2：——为解决某一问题而设计的确定的有限的步骤称为算法。 （2）解释算法的主要特点； 答：书P6 1、有穷性：指每一个算法都应该在一定的时间和步骤内完成。 2、确定性：指算法的每个步骤必须有确切的含义，而不应当是含糊的、模棱两可的。 3、可行性：指算法中的每一个步骤都必须是实际能做的，而且能在有限的时间内完成。 4、有0个或多个输入：指算法的执行需要从外界获取信息，为算法的某些阶段建立初试状态。如果建立初试状态所需要的信息已经包含在算法中，那就不再需要输人。 5、有1个或多个输出：指算法用来解决问题的结果应以一定的方式输出，即使问题“无”解答，也需要输出相关信息。 （3）描述用算法解决问题的一般过程。 答：书P3 答案1：1、分析问题→2、设计算法→3、编写程序→4、运行程序 答案2：1、需求分析→2、设计算法→3、编写程序→4、上机调试与维护 2．算法的描述方法；流程图的绘制方法；用流程图来描述算法。 （1）列举算法的描述方法（用自然语言描述、用流程图描述、用程序语言描述实现）；答：书P8，1、自然语言描述；2、流程图描述；3、伪代码或直接用计算机程序描述 （2）列举常用的流程图符号（起止框、输入输出框、处理框、判断框、流程线等）；答：书P 8—P 9 开始结束框（即：起止框）判断框 输入、输出框流程线 处理框连接框 （3）根据需要使用合适的流程图符号描述算法； 和） （4）描述绘制流程图的基本要求。

3．常量和变量的区别。 （1）复述常量和变量的概念； 答：书P57 常量——常量是在程序运行过程中值不变的数据或存储单元。 变量——变量用来表示数据的存数区，在程序运行过程中，这些存储区中的值是可以改变的。（2）比较常量与变量的不同； 答：在程序运行过程中，常量的值不变，变量的值可以改变 （3）列举数据的基本类型（整型、实数型、字符型、逻辑型等）。 答：书P58 表3.4 4．变量的作用和特点；设置和使用变量。 （1）描述变量的基本作用和特点； 答：在程序中，往往需要将某一个或某些数据暂时存放起来，以备后用，我们一般将这些数据暂存在变量中。变量指在程序运行过程中，取值可以改变的量，一般用字母表示。在计算机内部变量对应了一定的存储单元。 （2）列举变量命名的基本规则； 答：变量名只能由字母、数字和下划线三类字符组成，但第一个字符必须是字母。 字母大小写都可以，变量名长度适当。 （3）使用赋值语句对变量进行赋值； 答：赋值语句——将赋值号（=或←）右边常量的值或变量的值存放在左边变量名对应的存储单元中，成为左边变量的值。例如：a=3 （4）描述变量赋值的过程与特点。 答：赋值过程：例如a=3+a 读取变量a的值，在这个值得基础上加上2，将结果存放到变量a对应的存储单元中。

第四章 基本图形生成算法

10,,111<≤??=???+=+=++m x y m m y y x x i i i i 其中：第四章 基本图形生成算法 一、 直线的扫描转换 1． 数值微分算法 直接使用直线方程法、DDA 算法（增量算法） 优点：DDA 算法比直接用直线方程的方法快：没有浮点乘法； 缺点：求每个连续点时，需要浮点加法；加0.5舍尾取整，不利于硬件实现；表示长直线时，由于精度限制→累计误差； 2． 中点画线法 原理：1、确定与直线距离最近的点P ；2、利用点P 确定下一个点 3． Bresenham 画线算法 算法基本思想：每次迭代在增量最大方向上均走一步，其方向由增量的正负而定，另一方向上是否也走，取决于计算出来的点与直线上的点的误差，根据误差决定是否走一步。 例如取X 方向为最大增量方向，则有： 算法优点：-快速增量算法；-要获得准确的数学结果，只需通过整数的加、减法和乘2运算；计算机中乘2可以容易的通过算术移位实现。 给出使用Bresenham 算法画斜率介于0到45度之间的直线所需的步骤。 -解答： §1、计算初始值：dx=x2-x1; dy = y2 – y1; lnc1=2dy; lnc2 = 2(dy – dx)；d = lnc1-dx §2、设置左下方的端点坐标为（x,y ）,同时将Xend 设为x 的最大值。如果dx<0,则x=x2,y=y2,Xend=x1. 如果dx>0，则x=x1,y=y1,Xend=x2; §3、在当前（x ，y ）坐标画一个点； §4、判断整条线段是否已经画完，如果x=Xend ，则停止； §5、计算下一个象素的位置，如果d<0，那么d=d+lnc1，如果d>=0,则d=d+lnc2,且y=y+1; §6、增加x:x=x+1; §7、在当前的(x,y)坐标画一个点； §8、转到步骤4；