中科院陈玉福计算机算法设计与分析期末简答题答案

1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？

共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解

区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的

最优解，而上一部之前的最优解则不作保留。

动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解

动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。

贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编

码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。

2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？

二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深

度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。

3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什

么问题的什么特性提高效率的？

一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。

动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率

4. 什么是多项式时间算法？

若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。

时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。

一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并

将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。

5. 多项式时间确定性算法与多项式时间非确定性算法的主要区别是什么？

在算法计算复杂性的研究中，一个算法如果存在图灵机可计算的多项式时间计算复杂性算法，就将这个算法归入P类，如果存在非确定性图灵机可计算的多项式时间计算复杂性算法，就将其归入NP类

6. 陈述算法在最坏情况下的时间复杂度和平均时间复杂度；这两种评估算法复杂性的方法各自有什么实际意义？

最坏时间复杂度式算法在最差情况下的时间复杂度，也就是花费时间最多的情况。平均时间复杂度是因为它是期望的运行时间。它更有意义，现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算而来的。而最坏运行时间是一种保证，那就是运行时间不会再坏了。在应用中，这是最重要的需求，通常我们提到的运行时间都是最坏情况下的运行时间，时间复杂度是最坏情况下的时间复杂度。

7. 在对算法进行复杂性分析时，强调渐进复杂性的意义是什么？

当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍。使用渐进表达式可以略去低阶项所留下的主项，更加简单。P11

8. 在对算法进行复杂性分析时，时间复杂度用什么量反映的？其间做了什么假定？复杂性函数的渐进上界反映了复杂性函数的什么性质？

通常我们提到的运行时间都是最坏情况下的运行时间，时间复杂度是最坏情况下的时间复杂度

我们假定N充分大，渐近上界也反映了复杂性函数在N充分大的情况下复杂性的上界

9. 什么是NPC问题？证明一个问题是NPC问题一般采用哪几个步骤？

第一，证明该问题是NP问题

第二，选取一个已知的NPC问题

第三，构造一个从二中的问题到题目中问题的变换

第四，证明这个变换是多项式变换

10. 已知求解问题的两个算法的时间复杂性函数分别为和。现在有两台计算机，它们的速度比为64。如果采用算法，计算机求解问题的一个实例所用的时间为，那么，采用算法时，计算机能够在时间内求解问题的多大输入规模的实例？

解决这类问题，只要列出式子即可

11.在连通图无向图的宽度优先搜索树和深度优先搜索树中，哪棵树的最长路径可能会更长些？试说明你的理由。

宽度优先搜索树可能会长些

12.确定性图灵机模型与非确定性图灵机模型的主要区别在那里？确定性图灵机模型下算法的时间复杂度和空间复杂度指的是什么？

二者的区别就在于，确定性的每一步只有一种选择，而非有多种选择，由些可见，非的计算能力比确定性强得多。

时间复杂性即从开妈直至进入停机状态所运行的步数，同理空间复杂度

13.归并排序算法和快速排序算法各自强调了那个方面？各自提高效率的策略是什么？

归并由分解与合并两部分组成。提高的话一个是当元素比较少时，可以直接进行排序，比如插入排序。这比分解合并要快得多。二是尽量采用链表结构，因链表结构的移动要快于数组

快排也是利用分治法排序。主要过程为划分。一些改进的方法在确定第K小元素时，就是将r个元素分为一段这种方法复杂性可达到O（n）

二．（20分）试用Prim算法求解下面无向赋权图的最小生成树，指出最小生成树及该树中各边被选中的先后次序；写出算法的基本步骤。

解：根据Prim算法，从V1开始，选择10 V1和V4加入集合

找出集合中顶点相邻的最小权值点V7加入集合

依次为V 1 V4 V7 V8 V3V5 V2 V6

基本步骤：从第一个结点开始，加入集合A

每次选择A中顶点与A外的顶点权值最小的顶点，加入集合A

直到集合A包含所有顶点

三．（20分）用LC－分枝限界算法求解0/1背包问题：，物品重量和价值分别是：

w=(2,3,4,6,9) p=(8,9,10,12,18)

1.画出由算法生成的状态空间树，并标明各节点的优先级的值；

2.给出各节点被选作当前扩展节点的先后次序；

3.给出最优解。

解：30

具体步骤就不写了

四．（20分）已知一组数满足，且被搜索的对象的概率分布是：

其中a表示被搜索对象在区间内的概率，b表示被搜索对象为的概率，

使用动态规划算法求该搜索问题的最优二叉搜索树。

解：各子树的根：

1 1 1 4 4

0 2 3 4 4

0 0 3 4 4

0 0 0 4 4

0 0 0 0 5

最优二叉树结构：

k4是根

k1是k4的左孩子

d0是k1的左孩子

k3是k1的右孩子

k2是k3的左孩子

d1是k2的左孩子

d2是k2的右孩子

d3是k3的右孩子

k5是k4的右孩子

d4是k5的左孩子

d5是k5的右孩子

0.1 0.37 0.54 0.89 1.645 2.425

0 0.01 0.11 0.345 0.85 1.63

0 0 0.02 0.195 0.64 1.42

0 0 0 0.04 0.39 1.17

0 0 0 0 0.03 0.535

0 0 0 0 0 0.2

五．(20分) 假定已知“无向图的Hamilton回路”问题是NPC问题，证明“旅行商判定问题”也是NPC问题。

解：首先，旅行商问题是NP的，因为对其解的任一猜想，要检验它是否是最优的，需要同所有其它的环游戏比较，这样的环游会有指数个，因而不可能在多项式时间内完成

考虑图的哈密顿回路问题，已知无向图G |V|=n,构造其对应的旅行商问题为

Dij={1,if（vi,vj）属于边，2，否则}

显然，这一变换可以在多项式时间内完成，而且，G有哈回路的充分必要条件是上述构建的旅行商问题有解，且解对应的路长度为N，因为，若G中不含哈回路，则路长至少为n+1 因为已知哈回路问题是NPC问题，并且上述变换为多项式变换，所以旅行商问题也为NPC 问题

大学计算机习题参考答案

《大学计算机基础与计算思维》习题参考答案 第一章计算机引论 一、简答题 (1)什么是数据？什么是信息？二者有什么关系？ 答：数据是记录下来的可以鉴别的符号，它可以通过语言、文字、符号、图形、声音、光、电等来记录客观事物的状态。数据是对客观事物的一种符号描述，而信息是经过加工后的数据，是可以用来通信的知识。信息是用来消除随机不确定性的东西。二者关系为：数据是信息的原材料，而信息则是数据加工后的产品。 (2)支撑人类社会文明的三要素是什么？如何理解三者在不同历史时期的地位和作用？ 答：三要素为：信息、物质、能源。不同历史时期三种要素的利用比例不同。 (3)什么是数字化？在计算机领域内又如何理解？ 答：数字化分为广义和狭义二种，广义的数字化：指信息经过数字化处理的广泛应用。狭义的数字化：是指由数字信号（数码）取代模拟信号来表征、处理、存储、传输各种信息的过程。在计算机领域内，我们可以将数字化理解为将许多复杂的信息转变为可以度量的数字、数据，再以这些数字、数据建立起适当的数字化模型，把它们转变成一系列二进制代码，引入计算机内部，进行统一处理。 (4)简述计算机的发展阶段。 答：1932年英国数学家亚伦.图灵(Alan Turing)提出一人计算模型，称图灵机，现在的计算机在本质上与图灵机是一样的。 1936年，Konrad Zuse建造了一台可编程的数字化计算机，它引入了二进制系统和电子管的使用。 第一代计算机：1946至1956年，世界上第一台计算机ENIAC，电子管元件。宾夕法尼亚大学的美籍匈牙利数学家冯.诺依曼改进了ENIAC研制出了世界上第二台计算机EDVAC，作了重要改进：一是采用了二进制，二是程序和数据存入计算机内部。冯.诺依曼为现代计算机在体系结构和工作原理奠定了基础。当今的计算机依然遵循的是冯.诺依曼提出的计算机体系结构。 第二代计算机： (5) 简述计算机的特点。 运算速度快、计算精度高、存储容量大、具有逻辑判断功能、可靠性高、自动化程度高、通用性强等。 (6)简述计算机的应用领域。 科学计算、数据处理、过程控制、计算机辅助工程、办公自动化、数据通信、人工智能等。(7)什么是计算思维？ 计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人尖行为理解等涵盖计算机领域的一系列思维活动。 (8) 计算思维主要包含哪些思维内容？ 计算思维主要包括科学思维、逻辑思维、效率思维、创新思维和伦理思维等内容。

算法设计与分析考试题及答案

算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】

一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj

中科院陈玉福计算机算法设计与分析期末简答题答案

1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。

计算机基础知识简答题(第一章)

第一章计算机基础知识（一） 1、简述计算机的发展情况？ 答：1946年2月，美国的宾夕法尼亚大学研制成功了世界上第一台计算机——ENIAC至今，按计算机所采用的电子元件的变化来划分计算机的发展阶段，大致辞可分为四代： 第一代为电子管计算机（1946——1958）计算机所采用的主要电子元件是电子管。第二代为晶体管计算机（1959——1964）计算机所采用的主要电子元件是晶体管，这一时期了出现了管理程序及某些高级语言。 第三代为集成电路计算机（1965——1970）计算机所采用的主要电子元件是中小规模集成电路，出现操作系统，出现了分时操作系统和实时操作系统等。 第四代为大规模、超大规模集成电路计算机（1971至今）计算机所采用的主要电子元件是大规模、超大规模集成电路，出现了微型计算机及巨型计算机等多种类型的计算机，并向微型化、巨型化、智能化和多媒体化方向发展。 2、计算机的特点包括哪些？ 答：计算机的特点有：（1）运算速度快；（2）精确度高；（3）具有“记忆”功能和逻辑判断功能；（4）具有自动运行能力。 3、计算机性能指标有哪些？ 答：计算机的性能指标有：字长、主频、运行速度和内存储容量。MIPs 4、简述计算机的应用领域。

答：计算机的应用领域有：科学计算、数据处理、过程控制、计算机辅助系统、人工智能和网络应用。 5、简述微型计算机系统的组成。 答：一个完整的计算机系统由硬件系统和软件系统两大部分组成。计算机硬件主要由五大部分组成：运算器、控制器、存储器、输入设备和输出设备；硬件提供计算机系统的物质介质。计算机软件包括系统软件和应用软件两大类。软件主要是指让计算机完成各种任务所需的程序。 6、什么是计算机病毒？计算机病毒有什么特点？ 答：计算机病毒是一种人为制造的隐藏在计算机系统内部的能够自我复制进行传播的破坏计算机功能或者破坏数据，影响计算机使用的程序或指令代码。 计算机病毒的特点有传染性、破坏性、隐蔽性、潜伏性、激发性。 7、计算机病毒有哪些传播途径？如何预防计算机病毒？ 计算机病毒传播途径有移动存储设备包括软磁盘、优盘、移动硬盘等和计算机网络。 计算机病毒防治应采用“主动预防为主，被动处理结合”的方法。 （1）不使用来历不明和无法确定是否带有病毒的磁盘和优盘等。 （2）慎用公用软件和共享软件。 （3）不做非法复制。 （4）尽量做到专机专用，专盘专用。

计算机导论简答题参考答案

简答题 1.计算机有哪些主要的特点？答：运算速度快计算精度高存储功能强具有逻辑判断能力具有自 动运行能力。 2.CPU包括哪几个部件？它们又是如何协调工作的？答：CPU主要包括运算器、控制器两个部件。运算器主要完成各种算术运算和逻辑运算；控制器是指挥中心，控制运算器及其他部件工作，它能对指令进行分析，做出相应的控制；控制器从存储器中按顺序取出指令，并对指令进行分析，然后向运算器发出相应控制信号，使各部件协调工作，完成指令所规定的操作。 3.控制器的主要功能是什么？答：控制器是指挥和控制计算机各个部件进行工作的指挥中心，功能主要包括取指令、分析指令、执行指令、控制程序和数据的输入与结果的输出、随机事件和某些特殊请求的处理。 4.什么是操作系统？从资源管理的角度看，其主要功能是什么？答：操作系统是管理计算机硬件资源，控制其他程序运行并为用户提供交互操作界面的系统软件的集合；从资源管理的角度看操作系统要对计算机的硬件和软件资源进行管理，以提高各资源的利用率其功能主要分为处理机管理、存储器管理、设备管理、文件的管理和接口的管理等 5.什么是软件工程？简述软件生存周期的一般阶段。答：软件工程是指运用现代科学技术知识来设计并构 造计算机程序及为开发、运行、和维护这些程序所必需的相关文件资料；生命周期：问题定义、可行性的研究、需求分析、总体设计、详细设计、编码和单元测试、综合测试、软件维护。 6.简述计算机网络的定义？网络的拓扑结构有哪些? 答：计算机网络，是指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路连接起来，在网络操作系统，网络管理软件及网络通信协议的管理和协调下，实现资源共享和信息传递的计算机系统；网络拓扑结构包括：①星行拓扑结构②环行拓扑结构③总线型拓扑结构。 7.结构化程序设计的思想是什么？

算法设计与分析考试题及答案

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。

算法设计与分析试卷(2010)

算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

计算机简答题总结

计算机信息技术教程简答题 1.什么是信息技术，它包括哪些方面？现代信息技术的主要特征有哪些？ Key：<一>信息技术指的是用来扩展人们信息器官功能、协助人们更有效进行信息处理的一类技术。 <二>①扩展感觉器官的感测（获取）与识别技术 ②扩展神经系统功能的通讯技术。 ③扩展大脑功能的计算与存储技术。 ④扩展效应器官功能的控制与显示技术。 <三> 以数字技术为基础、以计算机及其软件为核心、采用电子技术（包括激光技术）进行信息的收集、传递、加工、存储、显示与控制。 2.什么是信息化?我国信息化建设的道路有什么特点？ Key：〈一〉信息化，就是利用现代信息技术对人类社会的信息和知识的生产与传播进行全面的改造，使人类社会生产体系的组织结构和经济结构发生全面变革的一个过程，是一个推动人类社会从工业社会向信息社会转变的社会转型的过程。 〈二〉特点：①目前我国正处于工业化中期阶段，技术落后。大量高科技尖端技术并没有完全为我国所掌握，须走适合我国国情的信息化建设道路。 ②充分发挥工业化对信息化的基础和推动作用。 ③促使信息化成为带动工业化升级的强大动力。 3.从通常意义上说，什么是信息？信息处理包含那些行为和活动？ 答：从客观的立场来看，信息是指：“事物运动的状态及状态变化的方式”。 从认识主体立场来看，信息是指：“认识主体所感知或所表述的事物运动及其变化方式的形式、内容和效用”。 信息处理指的是与下列内容相关的行为和活动：信息的收集、信息的加工、信息的存储、信息的施用。 4.二进制数与十进制数、八进制数、十六进制数如何相互转换？ Key：二进制转化为十进制：将二进制数的每一位乘上对应的权值，然后累加 十进制转化为二进制（整数）：除以2逆序取余 十进制转化为二进制（小数）：乘以2顺序取整 二进制转化为八进制：整数部分从低位向高位方向每3位用一个等值的八进制数替换，最后不足3位时在高位补0凑满3位；小数部分从高位向低位方向每3位用一个等值的八进制数来替换，最后不足3位时，在低位补0凑满3位。 八进制转化为二进制：把每个八进制数字改写成等值的二进制数，保持高、低位的次序不变。（二进制与十六进制的相互转化同八进制。相关二进制数与八进制、十六进制数字的对应，详见课本） 5 .什么是ASCII字符集？ASCII字符是怎样表示和存储的？ Key：〈一〉①ASCII字符集（西文字符集）和ASCII码，即美国标准信息交换码，已被ISO批准为国际标准，在全世界通用。

计算机应用基础简答题(附答案)

计算机应用基础简答题 1.什么是操作系统？操作系统的作用是什么？ 答：操作系统在计算机结构中处于硬件裸机与软件系统之间的层次上，它不仅管理位于内层的硬件资源，而且管理和协调外层各种软件资源，为用户提供一种高效便捷的应用环境。 操作系统是最基础的软件，它架起了互用和其他软件与计算机硬件裸机之间的桥梁，它统一管理计算机系统资源，合理地组织计算机的工作流程，协调系统各部分之间、系统与使用者之间以及使用者与使用者之间的关系。 从用户的角度看，操作系统将硬件细节与程序员或普通用户隔离 开来，给用户提供一个高度抽象而简洁的编程或操作界面；从系统角度看，操作系统管理着计算机这个复杂系统的所有资源。 2.简述在桌面上创建应用程序快捷方式图标的方法。 答：在对象上单击鼠标右键，执行“发送到—桌面快捷方式”命令即可。 或：在对象上单击鼠标右键，选择“创建快捷方式” ，再右击这个快捷方式，在快捷菜单中选择“剪切” ，到桌面上空白处右击鼠标，选择“粘贴”即可。 3.Windows 窗口一般由哪些部分组成？它们各有什么功能？ 答：（1）标题栏。显示窗口名称；右侧有最小化、最大化/ 还原和关闭按钮；鼠标点击标题栏可以拖动窗口。 （2）菜单栏。提供各项操作命令的集合。

（3）工具栏。根据窗口不同功能排列的一些按钮形式的常用命令，简化用户的操作。（4）滚动条。当窗口无法显示全部信息时，可以实现窗口的上下或左右滚动。 （5）常见任务区。显示出于当前窗口操作相关的一些任务及链接。 （6）状态栏。显示当前的操作状态。 4.屏幕保护程序的作用是什么？如何设置屏幕保护程序？ 答：在用户在预定的时间内没有操作计算机，程序会自动执行，通常是亮度较低的静止图像或动画，目的是减少显示器受损害的程度。 设置：在桌面空白处右击鼠标，选择“属性” ，在弹出的“显示属性”对话框中，单击“屏幕保护程序”标签，在打开的对话框中设置等待时间、程序图像等，单击“设置”按钮还可以对屏幕保护程序的运行速度、形状、颜色、密度以及是否使用密码保护等参数进行设置。 5.Windows 中的菜单有几种？分别简述执行这些菜单命令的操作方法。 答：（1）快捷菜单；（2）下拉菜单；（3）级联菜单。 所有快捷菜单都可以通过鼠标右键调出，快捷菜单中的命令会动态地随用户工作环境的不同而变化；当用户单击菜单栏中地某个菜单名后，会弹出相应的下拉菜单，下拉菜单中的黑色文字表示

算法设计与分析试卷(2010)

内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

计算机算法设计与分析期末考试复习题

1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。

大学计算机基础简答题

《大学计算机基础》简答题 1、计算机的发展经历了哪几个阶段？各阶段的主要特点是什么？ 答：电子计算机的发展已经历了四代，正向第五代智能化的计算机发展。前四代计算机是： 第一代为电子管计算机;第二代机是晶体管计算机;第三代机是由中小规模集成电路组成的计算机;第四代机是由大规模或超大规模集成电路组成的计算机. 各代电子计算机的特点是: (1)电子管计算机的主要特点是：体积庞大，运算速度低，成本高。 (2)晶体管计算机的主要特点是：体积小，寿命长，速度快，能耗少，可靠性高。 (3)中小规模集成电路计算机的主要特点是：体积更小、速度更快、能耗更小、可靠 性更高。 (4)大规模和超大规模集成电路计算机的主要特点是：网络普及与应用。 2、什么是计算机病毒？计算机病毒的主要特点是什么？ 答：计算机病毒是具有破坏性作用的程序。特点：传染性、潜伏性、破坏性和寄生性。 3、计算机硬件系统由哪几部份组成？简述各组成部分部份的基本功能？ 答：电子计算机硬件由运算器、控制器、存储器、输入设备和输出设备组成，运算器和控制器集成在一起统称为中央处理器（CPU）。计算机各部件通过总线连接形成有机整体，微机总线有三种：地址总线、控制总线和数据总线。 （1）、运算器的主要功能是：完成算术运算和逻辑运算； （2）、控制器的功能是：协调指挥计算机各部件工作； （3）、存储器的主要作用是：存储程序和数据，实现记忆的功能。 （4）、输入设备的功能是：输入数据并转换为机内信息存储； （5）、输出设备的作用是：将机内信息转换为便于识别、处理和使用的字符、图形，并输出显示。 4、什么是硬件？什么是软件？它们有何关系？ 答：计算机硬件是构成机器的电子、光电、电磁、机械等物理设备。软件即是计算机中使用的各种各样的程序及其说明文档。 硬件与软件的关系是：硬件是软件运行的基础，软件扩充了硬件的功能。 5、什么是指令？计算机的指令由哪两部份组成？什么是程序？ 答：指令是计算机能实现的基本操作，指令均为二进制数形式，指令由操作码和地址码组成，操作码告诉计算机执行什么操作，地址码告诉计算机到哪个存储单元地址中读取参与操作的数据。程序是若干指令或命令的集合。 6、简述计算机的工作原理。 答：电子计算机基本的工作原理是：事先存储程序并在程序控制下协调工作，即计算机的工作过程就是一个不断读取指令、对指令加以解释并执行指令的过程。这个工作原理是由冯·诺依曼首先提出的，所以按此原理生产的计算机称为冯氏计算机，前四代电子计算机都是冯氏计算机。 冯氏计算机应具备的条件是： （1）、机内信息采用二进制数表示；

计算机简答题答案

计算机基础知识 四、简答题 1、冯·诺依曼设计思想可以简要概括为三点？ 1)计算机硬件由运算器、控制器、存储器、输入设备和输出设备组成 2)计算机内部采用二进制表示数据和指令。、 3)存储程序和程序控制 2、简述计算机基本工作过程，并举例说明。 1)将程序和数据通过输入设备输入到内存 2)控制器从内存读出指令译码分析后予以处理 3)将结果通过输出设备输出 例如：对1+2=3计算过程的分析。 3、简述微型计算机中的三种总线及其作用。 1）三总线：地址总线、数据总线和控制总线 2）地址总线：用于存储器或I/O接口的地址信号传送 3）数据总线：用于CPU与内存、内存与I/O接口之间传送数据 4）控制总线：用于传送控制器的各种控制信号 4、简述解释程序与编译程序的作用与区别。 作用：1）解释程序是将高级语言源程序的指令逐条解释执行 2) 编译程序是将高级语言源程序编译成机器语言的目标程序后被CPU执行 区别：1) 解释程序不产生目标程序，逐条解释执行，效率低，便于调试 2) 编译程序生成目标成绩，执行效率高。 5、简述冯·诺依曼计算机结构及工作原理。 1）结构：计算机硬件有运算器、控制器、存储器、输入设备和输出设备组成 2）工作原理：存储程序和程序控制 6、什么叫指令？它由哪两部分组成？请简述计算机执行指令的过程。 指令：是指使计算机完成某种基本操作的命令 指令是由操作码和操作数（地址码）组成 计算机执行一条指令分三个步骤：CPU从内存取出指令→译码分析→执行指令7、列出当前常用的外存储器（4种以上）。 软盘、硬盘、光盘、U盘（移动硬盘，存储卡，磁带亦可） 8、简述操作系统的功能，列出微机上常用的操作系统。（4种以上） 功能：作业管理、文件管理、微处理器管理、设备管理、存储管理 操作系统：Windows，Dos，Unix，Linux 9、分别列举四种常用的输入设备和输出设备。 输入设备：鼠标，键盘，扫描仪，光笔，麦克风，触摸屏 输出设备：显示器，打印机，绘图仪，音箱

算法设计与分析试卷及答案

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14

计算机20个简答题

简答题 1．简述冯.诺依曼计算机原理及其要点。 计算机基本工作原理都采用“存储程序”和“程序控制”为基础 的设计思想。 要点：1.用二进制形式表示数据和指令 2.采用存储程序方式 3.计算机由运算器、控制器、存储器、输入设备和输出设备5部 分组成 2．在Word 中文本的格式化包括哪几个方面具体内容是什么？ 设置字体格式：包括字体、字号、加粗、倾斜，下划线、字体颜 色，字体效果等等。你选择文字点击右键—字体，在字体对话框 中所有的设置都是。选择整个段落，点击右键—段落，在段落对话框中所有的设置都 是段落格式。最好的办法是使用样式，可批量一次设置好字体和段落格式，如： 标题1、标题2、正文、题注等等。 3．在 Word 中什么是对象（图片）的版式，请解释嵌入版式和文本 环绕版式的页面效果。版式是指对象在文档页面的编排形式，即与文档中的正文文本之间 的关系。嵌入型版式：这是Word 对象的默认版式，它是将对象一个、管路敷设技术通过管线不仅可以解决吊顶层配置不规范高中资料试卷问题，而且可保障各类管路习题到位。在管路敷设过程中，要加强看护关于管路高中资料试卷连接管口处理高中资料试卷弯扁度固定盒位置保护层防腐跨接地线弯曲半径标等，要求技术交底。管线敷设技术中包含线槽、管架等多项方式，为解决高中语文电气课件中管壁薄、接口不严等问、电气课件中调试中资料试卷电气设备，在安装过程中以及安装结束后进行 高中资料试卷调整试验；通电检查所有设备高中资料试卷相互作用与相互关系，根据生产工艺高中资料试卷要求，对电气设备进行空载与带负荷下高中资料试卷调控试验；对设备进行调整使其在正常工况下与过度工作下都可以正常工作；对于继电保护进行整核对定值，审核与校对图纸，编写复杂设备与装置高中资料试卷调试方案，编写重要设备高中资料试卷试验方案以及系统启动方案；对整套启动过程中高中资料试卷电气设备进行调试工作、电气设备调试高中资料试卷技术电力保护装置调试技术，电力保护高中资料试卷配置技术是指机组在进行继电保护高中资料试卷总体配置时，需要在最大限度内来确保机组高中资料试卷安全，并且尽可能地缩小故障高中资料试卷破坏范围，或者对某些异常高中资料试卷工况进行自动处理，尤其要避免错误高中资料试卷保护装置动作，并且拒绝动作，来避免不必要高中资料试卷突然停机。因此，电力高中资料试卷保护装置

计算机应用基础简答题答案

计算机应用基础》课后习题简答题答案 习题一 1、计算机的应用领域主要有哪些？ 答：1、科学计算；2、事务处理；3、过程控制；4、辅助工程；5、网络应用2、何谓指令？指令中的操作码、操作数何作用？ 答：指令是规定计算机执行一种操作的一组用二进制数表示的符号；操作码表示基本操作；操作数表示操作的对象。 3、高级语言与机器语言的主要区别是什么？ 答：1、用高级语言编写程序，程序简洁、易修改，且具有通用性，编程效率高；但高级语言需要翻译或解释才能执行； 2、用机器语言编写程序，难学、难记，且容易出错和难于修改还依赖于机器，但机 器语言可直接在机器上执行。 4、计算机系统主要有哪些特点？ 答：1、计算机系统通常由硬件系统和软件系统两大部分组成。其中，硬件系统是指实际的物理设备，是计算机工作的基础；软件系统是指计算机中各种程序和数据，是计算机的灵魂。 2、计算机的硬件和软件是相辅相成的，二者缺一不可。只有硬件和软件协调配合， 才能发挥出计算机的强大功能，为人们服务。 5、计算机系统中，为什么要使用二进制数？ 答：二进制数具有以下优越性：1、技术可行性；2、运算简单性；3、吻合逻辑性。 6、简要说明内存储器中RAM 和ROM 的主要区别。 答：RAM 是允许用户随时进行读写数据的存储器。开机后，计算机系统需要的程序和数据调入RAM 中，再由CPU 取出执行，用户输入的数据和计算的结果也存储在RAM 中。 关机断电后，RAM 中数据就全部丢失。 ROM 是只允许用户读取数据，不能定稿数据的存储器。ROM 常用来存放系统核心程

序和服务程序。开机后ROM 中就有数据，断电后ROM 中的数据也不丢失。 7、简要说明计算机中内存储器和外存储器的主要作用。 答：内存储器主要用来存放 CPU 工作时用到的程序和数据以及计算后得到的结果；外存 储器主要用来存放CPU 暂时不用的、需要长期保存的程序和数据。 8按照资源管理的观点，操作系统主要有哪些功能? 答：按照资源管理的观点，操作系统的功能可分为：1、处理器管理；2、存储器管理；3、 设备管理；4、文件管理；5、作业管理 9、计算机的硬件系统主要由哪些部分组成？分别说明各部分的主要作用。 答：计算机硬件系统主要由控制器、运算器、存储器、输入设备和输出设备 5部分组成。 其中: 1、控制器是计算机的指挥控制中心，它根据用户程序中的指令控制机器各部分协调 工作; 运算器是专门负责处理数据的部件，是对各种信息进行加工的工具; 5、输出设备是计算机向人们输出结果的一类设备。 10、什么是多媒体计算机？多媒体计算机主要有哪些基本特性? 答：多媒体计算机是指能够处理文字、声音、图形、图像、动画等多种媒体信息的计算 机系统。它运用多媒体技术，通过计算机以交互的方式，自主地获取、处理、传播、展 示丰富多彩的信息。多媒体计算机有三个基本特性: 1、处理信息形式的多样性； 2、多媒体技术的集成性； 3、人与多媒体计算机的交互 性。 习题三 1. Windows 操作系统具有哪些特点? 2、 3、 存储器是专门用来存放程序和数据的部件; 4、 输入设备是人们向计算机输入程序和数据的一类设备;

算法设计与分析期末试题答案解析

1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解；

健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一

计算机考试简答题

9、组装一台个人电脑，需要哪些部件？请给出一台组装电脑的部件清单。 答案：主板，显卡，网卡，内存条，硬盘，机箱，电源，键盘，鼠标，光驱，显示器，CPU。显卡和网卡有在主板上集成好的，也可以买独立的还有音响设备。 10、对于结构化程序设计语言可以分为三种基本程序结构，这三种基本程序结构是什么，请举例说明。 答案：顺序结构，选择结构，循环结构； 1.顺序结构：从上到下依次执行。 2.选择结构：有if的语句 3.循环结构：有for, while的语句 11。文件是存放在计算机外存上的相关数据的集合。文件命名规则是什么？操作系统以什么方式组织文件？这种组织方式的优点是什么？ 答案：一个文件的文件名包括主文件名和扩展名两部分。有扩展名时用.号隔开。 在同一文件夹中，不允许有文件名完全相同的文件， 组织方式：按层次组织文件 优点：会大大提高文件管理效率，特别是文件查找效率。 12、对于冯?诺依曼体系的计算机系统，要让计算机完成某一任务，大体上可分为哪几个步骤？ 答案：输入-》存储-》控制-》运算-》输出， 15、保障计算机系统安全的技术措施主要有哪些？ 答案：三方面技术安全，管理安全，法律安全。 反病毒技术，反黑客技术，防火墙技术，入侵检测技术，数据加密技术，安全认证技术 16、简述计算机的发展历程。 答案：ENIAC诞生后短短的几十年间，计算机的发展突飞猛进。主要电子器件相继使用了真空电子管，晶体管，中、小规模集成电路和大规模、超大规模集成电路，引起计算机的几次更新换代。 第一代（1946~1957年）是电子计算机，它的基本电子元件是电子管，内存储器采用水银延迟线，外存储器主要采用磁鼓、纸带、卡片、磁带等 第二代（1958~1970年）是晶体管计算机。内存储器大量使用磁性材料制成的磁芯存储器 第三代（1963~1970年）是集成电路计算机（小规模）第三代集成电路计算机的基本电子元件是小规模集成电路和中规模集成电路，磁芯存储器进一步发展，并开始采用性能更好的半导体存储器 第四代（1971年~日前）是大规模集成电路计算机 集成度很高的半导体存储器替代了磁芯存储器。 18、从使用者角度出发，一台个人电脑的硬件系统应包括哪些部件？ 答案：显示器，主机，键鼠，主机里面是由CPU，主板，电源，内存，显卡（看使用者情况，可用集成，也可用独显）光驱，机箱，硬盘8个部分组成。这是最基本的，还有音响设备.......等等