湖南工程学院 计算机算法设计与分析 期末考试复习题

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. 回溯法解旅行售货员问题时的解空间树是（ 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、下列随机算法中运行时有时候成功有时候失败的是（C ）

A 数值概率算法

B 舍伍德算法

C 拉斯维加斯算法

D 蒙特卡罗算法

11．下面不是分支界限法搜索方式的是（ D ）。

A、广度优先

B、最小耗费优先

C、最大效益优先

D、深度优先

12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。

A、备忘录法

B、动态规划法

C、贪心法

D、回溯法

13.备忘录方法是那种算法的变形。（ B ）

A、分治法

B、动态规划法

C、贪心法

D、回溯法

14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。

A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）

15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。

A、最小堆

B、最大堆

C、栈

D、数组

16．最长公共子序列算法利用的算法是（ B ）。

A、分支界限法

B、动态规划法

C、贪心法

D、回溯法

17．实现棋盘覆盖算法利用的算法是（ A ）。

A、分治法

B、动态规划法

C、贪心法

D、回溯法

18.下面是贪心算法的基本要素的是（ C ）。

A、重叠子问题

B、构造最优解

C、贪心选择性质

D、定义最优解

19.回溯法的效率不依赖于下列哪些因素（ D ）

A.满足显约束的值的个数

B. 计算约束函数的时间

C. 计算限界函数的时间

D. 确定解空间的时间

20.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ）

A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数

21、下面关于NP问题说法正确的是（B ）

A NP问题都是不可能解决的问题

B P类问题包含在NP类问题中

C NP完全问题是P类问题的子集

D NP类问题包含在P类问题中

22、蒙特卡罗算法是（ B ）的一种。

A、分支界限算法

B、概率算法

C、贪心算法

D、回溯算法

23.下列哪一种算法不是随机化算法（ C ）

A. 蒙特卡罗算法

B. 拉斯维加斯算法

C.动态规划算法

D.舍伍德算法

24. （ D ）是贪心算法与动态规划算法的共同点。

A、重叠子问题

B、构造最优解

C、贪心选择性质

D、最优子结构性质

25. 矩阵连乘问题的算法可由（ B）设计实现。

A、分支界限算法

B、动态规划算法

C、贪心算法

D、回溯算法

26. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。

A、最小堆

B、最大堆

C、栈

D、数组

27、Strassen矩阵乘法是利用（ A ）实现的算法。

A、分治策略

B、动态规划法

C、贪心法

D、回溯法

29、使用分治法求解不需要满足的条件是（A ）。

A 子问题必须是一样的

B 子问题不能够重复

C 子问题的解可以合并

D 原问题和子问题使用相同的方法解

30、下面问题（B ）不能使用贪心法解决。

A 单源最短路径问题

B N皇后问题

C 最小花费生成树问题

D 背包问题

31、下列算法中不能解决0/1背包问题的是（A ）

A 贪心法

B 动态规划

C 回溯法

D 分支限界法

32、回溯法搜索状态空间树是按照（C ）的顺序。

A 中序遍历

B 广度优先遍历

C 深度优先遍历

D 层次优先遍历

33、下列随机算法中运行时有时候成功有时候失败的是（C ）

A 数值概率算法

B 舍伍德算法

C 拉斯维加斯算法

D 蒙特卡罗算法

34．实现合并排序利用的算法是（ A ）。

A、分治策略

B、动态规划法

C、贪心法

D、回溯法

35．下列是动态规划算法基本要素的是（ D ）。

A、定义最优解

B、构造最优解

C、算出最优解

D、子问题重叠性质

36．下列算法中通常以自底向下的方式求解最优解的是（ B ）。

A、分治法

B、动态规划法

C、贪心法

D、回溯法

37．采用广度优先策略搜索的算法是（ A ）。

A、分支界限法

B、动态规划法

C、贪心法

D、回溯法

38、合并排序算法是利用（ A ）实现的算法。

A、分治策略

B、动态规划法

C、贪心法

D、回溯法

39、在下列算法中得到的解未必正确的是（ B ）。

A、蒙特卡罗算法

B、拉斯维加斯算法

C、舍伍德算法

D、数值概率算法

40、背包问题的贪心算法所需的计算时间为（ B ）

A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）

41．实现大整数的乘法是利用的算法（ C ）。

A、贪心法

B、动态规划法

C、分治策略

D、回溯法

42．0-1背包问题的回溯算法所需的计算时间为（ A ）

A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）

43．采用最大效益优先搜索方式的算法是（ A ）。

A、分支界限法

B、动态规划法

C、贪心法

D、回溯法

44．贪心算法与动态规划算法的主要区别是（ B ）。

A、最优子结构

B、贪心选择性质

C、构造最优解

D、定义最优解

45. 实现最大子段和利用的算法是（ B ）。

A、分治策略

B、动态规划法

C、贪心法

D、回溯法

46.优先队列式分支限界法选取扩展结点的原则是（ C ）。

A、先进先出

B、后进先出

C、结点的优先级

D、随机

47.背包问题的贪心算法所需的计算时间为（ B ）。

A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）

48、广度优先是（ A ）的一搜索方式。

A、分支界限法

B、动态规划法

C、贪心法

D、回溯法

49、舍伍德算法是（ B ）的一种。

A、分支界限算法

B、概率算法

C、贪心算法

D、回溯算法

50、在下列算法中有时找不到问题解的是（ B ）。

A、蒙特卡罗算法

B、拉斯维加斯算法

C、舍伍德算法

D、数值概率算法

51下列哪一种算法是随机化算法（ D ）

A. 贪心算法

B. 回溯法

C.动态规划算法

D.舍伍德算法

52. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。

A、重叠子问题

B、最优子结构性质

C、贪心选择性质

D、定义最优解

53．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为( B ) 。

A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）

54. 以深度优先方式系统搜索问题解的算法称为 ( D ) 。

A、分支界限算法

B、概率算法

C、贪心算法

D、回溯算法

55. 实现最长公共子序列利用的算法是（ B ）。

A、分治策略

B、动态规划法

C、贪心法

D、回溯法

1.算法的复杂性有时间复杂性和空间复杂性之分。

2、程序是算法用某种程序设计语言的具体实现。

3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。

4.矩阵连乘问题的算法可由动态规划设计实现。

5、拉斯维加斯算法找到的解一定是正确解。

6、算法是指解决问题的一种方法或一个过程。

7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。

8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

9、以深度优先方式系统搜索问题解的算法称为回溯法。

10、数值概率算法常用于数值问题的求解。

11、计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步。

12、利用概率的性质计算近似值的随机算法是数值概率算法，运行时以一定的概率得到正确解的随机算法是__蒙特卡罗算法_____________________。

14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法，分支限界法。

15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题，只使用约束条件进行裁剪的是 N皇后问题。

17、矩阵连乘问题的算法可由动态规划设计实现。

18、拉斯维加斯算法找到的解一定是正确解。

19.贪心算法的基本要素是贪心选择质和最优子结构性质。

21. 动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

算法是由若干条指令组成的有穷序列，且要满足输入，输出、确定性和有限性四条性质。

23、大整数乘积算法是用分治法来设计的。

24、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。

25、舍伍德算法总能求得问题的一个解。

贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。

27.快速排序算法是基于分治策略的一种排序算法。

28.动态规划算法的两个基本要素是. 最优子结构性质和重叠子问题性质。

30.回溯法是一种既带有系统性又带有跳跃性的搜索算法。

31.分支限界法主要有队列式（FIFO）分支限界法和优先队列式分支限界法。

32．分支限界法是一种既带有系统性又带有跳跃性的搜索算法。

33．回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。

34.任何可用计算机求解的问题所需的时间都与其规模有关。

35.快速排序算法的性能取决于划分的对称性。

1分治法的基本思想时将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

2设计动态规划算法的主要步骤为：（1）找出最优解的性质，并刻划其结构特征（2）递归地定义最优值（3）以自底向上的方式计算出最优值（4）根据计算最优值时得到的信息，构造最优解。

3. 分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。

4. 分支限界法与回溯法的相同点是：都是一种在问题的解空间树T 中搜索问题解的算法。

不同点：（1）求解目标不同；（2）搜索方式不同； （3）对扩展结点的扩展方式不同；（4）存储空间的要求不同。 5用回溯法搜索子集树的算法为：

6. 分治法所能解决的问题一般具有的几个特征是：

（1）该问题的规模缩小到一定的程度就可以容易地解决；

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; （3）利用该问题分解出的子问题的解可以合并为该问题的解；

（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

7. 用分支限界法设计算法的步骤是：

(1)针对所给问题，定义问题的解空间（对解进行编码）；分 (2)确定易于搜索的解空间结构（按树或图组织解） ；

(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 8. 常见的两种分支限界法的算法框架

（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO ）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 9. 回溯法中常见的两类典型的解空间树是子集树和排列树。

当所给的问题是从n 个元素的集合S 中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n 个叶结点，遍历子集树需O(2n)计算时间 。

当所给的问题是确定n 个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。 10. 分支限界法的搜索策略是：

在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。

计算机算法设计与分析复习题

一、填空题

1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有 时间 复杂性和空间复杂性之分。

2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 相同 。

3、使用二分搜索算法在n 个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O （1），在最坏情况下，搜索的时间复杂性为O （ logn ）。

4、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程：

??

?≥+<=2

2221n n O n T n O n T )()/()()( 解得此递归方可得T(n)= O （ log n n ）。

5、动态规划算法有一个变形方法 备忘录方法 。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同

样也可避免相同子问题的重复求解。

6．递归的二分查找算法在divide阶段所花的时间是O(1) ，conquer阶段所花的时间是T(n/2) ，算法的时间复杂度是O( log n) 。

7．Prim算法利用贪心策略求解最小生成树问题，其时间复杂度是O(n2) 。

8．背包问题可用贪心法，回溯法等策略求解。

9．用动态规划算法计算矩阵连乘问题的最优值所花的时间是O(n3) ，子问题空间大小是O(n2) 。

10．图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是m n，解空间树中每个内结点的孩子数是m 。

11．单源最短路径问题可用贪心法、分支限界等策略求解。

12、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。

13、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。

14、直接或间接地调用自身的算法称为（递归算法）。

15、 记号在算法复杂性的表示法中表示（渐进确界或紧致界）。

16、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题）的思想。

17、动态规划算法适用于解（具有某种最优性质）问题。

18、贪心算法做出的选择只是（在某种意义上的局部）最优选择。

19、最优子结构性质的含义是（问题的最优解包含其子问题的最优解）。

20、回溯法按（深度优先）策略从根结点出发搜索解空间树。

21、拉斯维加斯算法找到的解一定是（正确解）。

22、按照符号O的定义O(f)+O(g)等于O(max{f(n),g(n)})。

23、二分搜索技术是运用（分治）策略的典型例子。

24、动态规划算法中，通常不同子问题的个数随问题规模呈（多项式）级增长。

25、（最优子结构性质）和（子问题重叠性质）是采用动态规划算法的两个基本要素。

26、（最优子结构性质）和（贪心选择性质）是贪心算法的基本要素。

27、（选择能产生最优解的贪心准则）是设计贪心算法的核心问题。

28、分支限界法常以（广度优先）或（以最小耗费(最大效益)优先）的方式搜索问题的解空间树。

29、贪心选择性质是指所求问题的整体最优解可以通过一系列（局部最优）的选择，即贪心选择达到。

30、按照活结点表的组织方式的不同，分支限界法包括（队列式(FIFO)分支限界法）和（优先队列式分支限界法）两种形式。

31、如果对于同一实例，蒙特卡洛算法不会给出两个不同的正确解答，则称该蒙特卡洛算法是（一致的）。

32、哈夫曼编码可利用（贪心法）算法实现。

33概率算法有数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法

34以自顶向下的方式求解最优解的有（贪心算法）

35、下列算法中通常以自顶向下的方式求解最优解的是（贪心法）。

36、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是（回溯法）

37、旅行售货员问题不能用（）解决可以用回溯法解决，分支限界法，NP完全性理论与近似算法

38、贪心算法不能解决（0-1背包问题 N 皇后问题）。可以解决背包问题 39、投点法是（概率算法）的一种。

40、若线性规划问题存在最优解，它一定不在（可行域内部）

二、简答题

1、（8分）写出下列复杂性函数的偏序关系（即按照渐进阶从低到高排序）：

2

323log !log 10n n n n n n n n n 参考解答：3

2

10log log 23!n

n

n n n n

n n n

2、（8分）现在有8位运动员要进行网球循环赛，要设计一个满足以下要求的比赛日程表： （1） 每个选手必须与其他选手各赛一次； （2） 每个选手一天只能赛一次； （3） 循环赛一共进行n – 1天。

请利用分治法的思想，给这8位运动员设计一个合理的比赛日程。 参考解答：

3、（8分）某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s(i)表示开始租用时刻，f(i)表示结束租用时刻，10个客户的申请如下表所示：

同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用安排方案，在这10位客户里面，使得体育馆能尽可能满足多位客户的需求，并算出针对上表的10个客户申请，最多可以安排几位客户申请。

参考解答：将这10位客户的申请按照结束时间f(i)递增排序，如下表：

⑴选择申请1（1,4）

⑵依次检查后续客户申请，只要与已选择的申请相容不冲突，则选择该申请。直到所有申请检查完毕。申请4（5,7）、申请8（8,11）、申请10（11,13）

⑶最后，可以满足：申请1（1,4）、申请4（5,7）、申请8（8,11）、申请10（11,13）共4个客户申请。这已经是可以满足的最大客户人数。

4、（8分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为：

1i k j

0[,]min{[,][1,]}i k j i j m i j m i k m k j p p p i j -≤<=??

=?

+++

请根据以上的递归关系，计算出矩阵连乘积A 1A 2A 3A 4所需要的最少数乘次数。

参考解答：

014024034[1][1][2][4]080005010510500

[1][4]min [1][2][3][4]2000060005040536000

[1][3][4][4]270000503053450010500

m m p p p m m m p p p m m p p p ++=++??=??

=++=++??=??++=++??=?

=

5、（8分）有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。

n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。

其中n 为物品个数，c 为背包载重量，P 表示物品的价值，W 表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？

参考解答：因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33，为最大值。

6.请用英文写出三种以上能求解0-1背包问题的设计算法策略。 参考解答：

Dynamic Programming

Backtrack Branch-and-Bound （每答对一条给一分）

7.请说明动态规划方法为什么需要最优子结构性质。

参考解答：最优子结构性质是指大问题的最优解包含子问题的最优解。

动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构

8.请说明：(1)优先队列可用什么数据结构实现？(2)优先队列插入算法基本思想？(3)优先队列插入

算法时间复杂度？

参考解答：（1）堆。(1分)

（2）在小根堆中，将元素x插入到堆的末尾，

然后将元素x的关键字与其双亲的关键字比较，

若元素x的关键字小于其双亲的关键字，

则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键

字大于双亲的关键字，或元素x到根为止。(4分)

（3）O( log n)（1分）

9..设计动态规划算法的主要步骤是怎么的？请简述。

参考解答：（1）找出最优解的性质，并刻划其结构特征。(6分)

（2）递归地定义最优值。

（3）以自底向上的方式计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解。

10.分治法所能解决的问题一般具有哪几个特征？请简述。

参考解答：（1）该问题的规模缩小到一定的程度就可以容易地解决；(6分)

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;

（3）利用该问题分解出的子问题的解可以合并为该问题的解；

（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

11.分支限界法的搜索策略是什么？

参考解答：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。(6分)

12算法的要特性是什么？

参考解答：确定性、可实现性、输入、输出、有穷性

13算法分析的目的是什么？

参考解答：分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。

14算法的时间复杂性与问题的什么因素相关？

参考解答：算法的时间复杂性与问题的规模相关，是问题大小n的函数。

15算法的渐进时间复杂性的含义？

参考解答：当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。

16最坏情况下的时间复杂性和平均时间复杂性有什么不同？

参考解答：最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：

W(n) = max{ T(n，I) } , I∈Dn

平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：

A(n) =∑P(I)T(n，I) I∈Dn

17简述二分检索（折半查找）算法的基本过程。

参考解答：设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果

A[(i+j)/2]=x ，则返回(i+j)/2，如果A[(i+j)/2]

18 背包问题的目标函数和贪心算法最优化量度相同吗？

参考解答：不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。

19 采用回溯法求解的问题，其解如何表示？有什么规定？ 参考解答：问题的解可以表示为n 元组：（x 1,x 2,……x n ），x i ∈S i , S i 为有穷集合，x i ∈S i , （x 1,x 2,……x n ）具备完备性，即（x 1,x 2,……x n ）是合理的，则（x 1,x 2,……x i ）(i

参考解答：在解空间树上跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。

21 n 皇后问题回溯算法的判别函数place 的基本流程是什么？ 参考解答：将第K 行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false ，测试完毕则返回true 。

22 为什么用分治法设计的算法一般有递归调用？

参考解答：子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归. 23 为什么要分析最坏情况下的算法时间复杂性？

参考解答：最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。

24 简述渐进时间复杂性上界的定义。

参考解答：T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No 和C ，n 〉No ，有T(n)

参考解答：二分检索算法的最多的比较次数为 log n 。 26 快速排序算法最坏情况下需要多少次比较运算？

参考解答：最坏情况下快速排序退化成冒泡排序，需要比较n 2次。 27 贪心算法的基本思想？

参考解答：是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n 个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中 28 回溯法的解（x 1,x 2,……x n ）的隐约束一般指什么？

参考解答：回溯法的解（x 1,x 2,……x n ）的隐约束一般指个元素之间应满足的某种关系。 29 阐述归并排序的分治思路。

参考解答：讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n 个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。

30 快速排序的基本思想是什么。 参考解答：快速排序的基本思想是在待排序的N 个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。

31 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？

参考解答：在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，

这称为直接递归。如果过程或者函数P 调用过程或者函数Q ，Q 又调用P ，这个称为间接递归。消除递归一般要用到栈这种数据结构。 32 什么是哈密顿环问题？

参考解答：哈密顿环是指一条沿着图G 的N 条边环行的路径，它的访问每个节点一次并且返回它的开始位置。

33 用回溯法求解哈密顿环，如何定义判定函数？

参考解答：当前选择的节点X[k]是从未到过的节点,即X[k]≠X[i](i=1,2,…,k-1)，且C(X[k-1], X[k])≠∞，如果k=-1，则C(X[k], X[1]) ≠∞。 34 请写出prim 算法的基本思想。

参考解答：思路是：最初生成树T 为空，依次向内加入与树有最小邻接边的n-1条边。处理过程：首先加入最小代价的一条边到T ，根据各节点到T 的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。

三、算法设计题

1.【最长上升子序列问题】（8分）—— 提示：此题可采用动态规划算法实现

对于给定的一个序列12(,,

,)N a a a ，11000N ≤≤。我们可以得到一些递增上升的子序列12(,,,)i i iK a a a ，这里121K i i i N ≤<<

<≤。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上

升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。你的任务：就是对于给定的序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公式表达。.

参考解答：设()f i 表示：从左向右扫描过来直到以[]a i 元素结尾的序列，获得的最长上升子序列的长度，且子序列包含[]a i 元素（1i n ≤≤）。

11()max{()1:[][];1}111;(1)[][]i f i f j a i a j j i i i j j i a i a j =?

?

=+>≤<>??>?≤<<=?

当,都有

即，()f i 是从(1)f ，(2)f ……到(1)f i -中找最大的一个值，再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。

最后，所要求的整个序列的最长公共子序列长度为max{f(i): 1<=i<=n} 例如，对于序列：4 2 6 3 1 5 2

评分准则：

1) 答到使用动态规划算法，并且推导出动态规划算法的递推函数公式表达，边界设定清晰，本

题即可得满分；（阅卷时仔细看递推公式表达，公式表达含义正确即可，因其表达形式可能不唯一）

2) 说明使用动态规划算法，但对递推函数表达错误或含糊，扣2分以上； 3) 其它情况酌情考虑。

2．（10分）对下图所示的连通网络G ，用克鲁斯卡尔(Kruskal)算法求G 的最小生成树T,请写出在算法执行过程中，依次加入T 的边集TE 中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。

参考解答

TE={(3,4), (2,3),(1,5),（4,6）（4,5）} （5分）

贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。

基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。（4分） 时间复杂度为：O(eloge) （1分） 3.（15分）考虑n=3的批处理作业调度实例：

其中t ji 是作业J i 需要在机器j 上处理的时间。对于给定的3个作业，制定一个最佳作业调度方案，使其完成时间和达到最小。 要求：

（1）画出该问题的解空间树； （5分） （2）写出该问题的剪枝策略(即限界条件),要求只保留第一个最优解;(2

分)

（3）按优先队列式分支限界法搜索解空间树，并用剪枝策略对解空间树中该剪枝的位置打 ；

（5分）

（4）给出最优解及最优值。 （3分） 参考解答（1）5分

（2）若当前代价f >= 当前最优解代价bestf，则剪枝。2分

（3）见（1）中所画的图。5分

（4）最优解为{3，1，2}，最优值为25。3分

4.【Gray码构造问题】（8分）——提示：此题可采用分治递归算法实现

问题描述：“格雷码”是一个长度为n2的序列，满足：

（a）每个元素都是长度为n比特的串

（b）序列中无相同元素

（c）连续的两个元素恰好只有1个比特不同

例如：n=2时，格雷码为{00，01，11，10}。

Gray码是一种编码，这种编码可以避免在读取时，因各数据位时序上的差异造成的误读。格雷码在工程上有广泛应用。但格雷码不便于运算，请你设计一种构造方法，输入长度序列n，输出格雷码（你只要做出一种构造方案即可，格雷码并不唯一）。

参考解答：此题可用分治法解决。

当n＝1时，输出格雷码{0, 1}

当n>1时，格雷码的长度为n2，即共有n2个码序列。此时，将问题一分为二，即上半部分和下半部分。上半部分最高位设为0，下半部分最高位设为1。剩下n-1位的格雷码的构造采用递归的思路。

评分准则：

1)答到使用分治算法，并且推导出分治算法的过程，边界设定清晰（即当仅输出1位的格雷码

如何处理），本题即可得满分；

2)说明使用分治算法，但漏边界条件，扣2分以上；

其它情况酌情考虑。

5.（13分）给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V 中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。

参考解答：（13分）

6.（13分）有0-1背包问题如下：

n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。

其中n 为物品个数，c 为背包载重量，P 表示物品的价值，W 表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。

P=(15，8，6，4，3，1) W=(2，3，4，5，8，10)，单位重量物品价值（7.5，2.67，1.5,0.8,0.375,0.1）

参考解答：（13分）

可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。

1.先把重量为2的物品放进背包，此时剩余载重量为17，P 为15。

2.把重量为3的物品放进背包，此时剩余载重量为14，P 为23；

3.把重量为4的物品放进背包，此时剩余载重量为10，P 为29；

4.把重量为5的物品放进背包，此时剩余载重量为5，P 为33. 由于8>5，所以不能再放进背包。

结果是把重量为2，3，4，5的物品装进背包，总价值最大为33.

7、将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有哪三种情形？(10分)

参考解答：（1）a[1:n]的最大子段和与a[1:n/2]的最大子段和相同。 （2）a[1:n]的最大子段和与的最大子段a[n/2+1:n]和相同。

⑶a[1:n]的最大子段和为∑ak(i=

8 写出maxmin 算法对下列实例中找最大数和最小数的过程。 数组 A=(48,12,61,3,5,19,32,7)

参考解答：写出maxmin 算法对下列实例中找最大数和最小数的过程。

数组 A=()

1、 48,12,61,3, 5,19,32,7

4

3 2 1 {1} 初始 dist[5]

dist[4] dist[3] dist[2] u S 迭代

60

30

50

10

5

{1，2，3，4，5}

4

60 30 50 10 3 {1，2，4，3} 3 90 30 50 10 4 {1，2，4} 2 100 30 60 10 2 {1，2} 1 100 30 10 - {1} 初始 dist[5] dist[4] dist[3]

dist[2] u S 迭代

2、 48,12 61,3 5,19 32,7

3、 48～61, 12～3 19～32，5～7

4、 61～32 3～5

5、 61 3

9 速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。

A=(65,70,75,80,85,55,50,2)

参考解答：第一个分割元素为65

(1) (2) (3) (4) (5) (6) (7) (8) i p

65 70 75 80 85 55 50 2 2 8

65 2 75 80 85 55 50 70 3 7

65 2 50 80 85 55 75 70 4 6

65 2 50 55 85 80 75 70 4 6

55 70 75 80 85 65 50 2

10 归并排序算法对下列实例排序，写出算法执行过程。

A=(48,12,61,3,5,19,32,7)

参考解答： 48,12,61,3 5,19,32,7

48,12 61,3 5,19 32,7

12,48 3,61 5,19 7,32

3, 12, 48, 61 5, 7, 19，32

3,5, 7,12，19，32，48,61

算法设计与分析复习资料1

一 1.循环赛日程表问题的相关叙述。 2.算法运行时所需要占用的存储空间有？ 3.动态规划法的求解步骤 4.解空间树是排列树的问题有。 5.分治法的步骤 6.就会场安排问题，贪心法的最佳贪心策略 7.快速排序法基准元素的选取方法 8.满足满m叉树的问题有？ 9.分支限界法的解题步骤 10.事前分析法相关的影响因素有 11.用分治法求解的问题一般需要具备一些特征，主要有？ 二 1．给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数，另外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度，这里的路径长度是指路径上经过的所有边上的权值之和，这个问题通常称为单源最短路径问题。 2．采用回溯法可以求解0-1背包问题，其解空间的形式为：（x1,x2,…,xn）或n 元组。 3．当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时，相应的解空间树称为排列树。 4．一个正在生成孩子的结点称为扩展结点。 5．子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。 6．当所给问题的n个元素中每一个元素均有m种选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质，即寻找满足某种特性的n个元素取值的一种组合，这类问题的解空间树称为满m叉树。 7．一个自身已生成但其孩子还没有全部生成的结点称为活结点 8．回溯法中，对于问题的一个实例，解向量满足显约束的所有n元组构成了该实例的一个解空间 9．分支限界法有两种：队列式分支限界法和优先队列式分支限界法。 10．分支限界法采用的是宽度优先搜索。 11．时间复杂性的度量方法通常有两种：事后统计法和事前分析估算法 12．一个所有孩子已经生成的结点称做死结点 13．在最小生成树的生成方法中，Kruskal算法从边的角度出发，每一次将图中的权值最小的边取出来，在不构成环的情况下，将该边加入最小生成树。 三 1．分治法字面上的解释是分而治之，就是把一个复杂的问题分成两个或更多的相同子问题，子问题相互独立，如果子问题还是不容易解决，再把子问题分成更小的子问题…，直到最后各个子问题可以简单地直接求解，对各个子问题递归求解，将子问题的解进行合并即得原问题的解。 2．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采

大学计算机基础期末考试题

一、选择题 1.第一台电子计算机诞生于（B ）年 A.1945 B.1946 C.1971 D.1972 2. 第一代计算机的主要元器件采用的是（ C ）。 （A）晶体管 (B)小规模集成电路 (C) 电子管 (D)大规模和超大规模集成电路3. 存储容量的基本单位是（B ）。 （A）位 (B) 字节(C)字 (D)ASCII码 4．利用计算机对指纹进行识别、对图像和声音进行处理属于的应用领域是（ D）。（A）科学计算 (B) 自动控制 (C)辅助设计 (D)信息处理 5．微型计算机中运算器的主要功能是进行（C）。 （A）算术运算 (B)逻辑运算 (C) 算术和逻辑运算 (D)初等函数运算 6．中文Windows XP的“桌面”指的是（C ）。 （A）整个屏幕（B）某个窗口（C）全部窗口（D）活动窗口 7.决定微型计算机性能的核心硬件是（ D ） A CD-ROM B UPS C BBS D CPU 8. 一台微机的型号中含有486、586等内容时，其含义是__A_ __。 A. 运算控制单元的档次 B.软盘容量大小 C. 主存储器容量大小 D.硬盘容量大小 9.计算机硬件的五大基本构件包括：运算器、存储器、输入设备、输出设备和( B ) A. 显示器 B. 控制器 C. 磁盘驱动器 D. 鼠标器 10.在计算机内部，所有信息的表示法都是采用（ C ） A 十进制 B 八进制 C 二进制 D 十六进制 11.第四代计算机的主要逻辑元件采用的是(D ) A.晶体管 B.小规模集成电路 C.电子管 D. 大规模和超大规模集成电路

12.一个完整的计算机系统包括：(A) A、硬件系统和软件系统 B、主机、键盘、显示器 C、系统软件和应用软件 D、计算机及其外部设备 13."计算机辅助设计"的英文缩写是：(A) A、CAD B、CAM C、CAE D、CAT 14.微型计算机中，ROM的中文名字是:(B) A、随机存储器 B、只读存储器 C、高速缓冲存储器 D、可编程只读存储 15.计算机能够直接执行的程序是( B) A、应用软件 B、机器语言程序 C、源程序 D、汇编语言程序 16.存储器分为内存储器和外存储器两类 ( A) A、它们中的数据均可被CPU直接调用 B、只有外存储器中的数据可被CPU调用 C、它们中的数据均不能被CPU直接调用 D、其中只有内存储器中的数据可被CPU直接调用 17.当已选定文件后，下列操作中不能删除该文件的是（ D ） A.在键盘上按Delete键 B.用鼠标右击该文件，打开快捷菜单，然后选择删除命令 C.在文件菜单中选择“删除”命令 D.用鼠标双击该文件夹 18.在WindowsXP操作系统中一个文件的属性包括（B ） A.只读、存档 B.只读、隐藏 C.只读、隐藏、系统 D. 只读、隐藏、系统、存档19．Windows XP操作系统属于（ C ） A. 单用户单任务操作系统

计算机应用基础期末考试复习题-答案

计算机应用基础期末考试复习题 一、基本知识与Windows D 1. 计算机不能正常工作时，与以下无关。 A. 硬件配置达不到要求 B. 软件中含有错误 C. 使用者操作不当 D. 环境噪声太大 B 2. 缺少，计算机就无法工作。 A. 汉字系统 B. 操作系统 C. 编辑程序 D. 文字处理系统D 3. 显示器的越高，显示的图像越清晰。 A. 对比度 B. 亮度 C. 对比度和亮度 D. 分辨率 D 4. 下面不是系统软件。 A. Dos、Unix B. Windows NT、Windows 95 C. Linux D. Word、Excel B 5. 是中央处理器的简称。 A. RAM B. CPU C. 控制器 D. 运算器 C 6. 在计算机内部，传送、存储、加工处理的数据或指令都是以的形式进行的。 A. 五笔字型码 B. 八进制吗 C. 二进制码 D. 拼音简码C 7. 用计算机进行语言翻译和语言识别，按计算机应用的分类，它应属于。 A. 科学计算 B. 辅助设计 C.人工智能 D. 实时控制 C 8. 个人计算机属于。 A. 小巨型机 B. 小型计算机 C. 微型计算机 D. 中型计算机

D 9. 计算机网络最突出的优点是。 A. 精度高 B. 运算速度快 C. 存储容量大 D. 共享资源D 10. 英文字符“E”的ASCII码是。 A. 66 B. 67 C. 68 D. 69 B 11.计算机能与网络连接需要配置。 A. MODEM B. 网卡 C. 电话线 D. 解压卡 D 12. E-mail的中文含义是。 A. 远程查询 B. 文件传输 C. 远程登录 D. 电子邮件C 13. 要浏览网页，必须知道该网页的。 A. E-mail地址 B. 电话号码 C. 网址 D. 邮政编码 B 14. TCP/IP是。 A. 网络名 B. 网络协议 C. 网络应用 D. 网络系统A 15. 微型计算机必不可少的输入和输出设备是。 A. 键盘和显示器 B. 键盘和鼠标 C. 显示器和打印机 D. 鼠标器和打印机 D 16. CUP是由组成的。 A. 内存储器和控制器 B. 控制器和运算器 C. 高速缓存和运算器 D. 运算器、控制器和内存储器B 17. 光盘是一种。 A. 内存储器 B. 外存储器 C. 中央处理器 D. 通讯设备 D 18. 下面设备不属于输入设备的是。

算法设计与分析报告考试题(自测)

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_有穷性__,_确定性_,_可行性_,_ （0个或多个）输入__,_ （1个或多个）_输出_。 2.算法的复杂性有__时间复杂性__和__空间复杂性__之分，衡量一个 算法好坏的标准是__时间复杂度高低___。 3.某一问题可用动态规划算法求解的显著特征是___该问题具有最优 子结构性质___。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_{A,B,C,D}_。{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含_问题的一个（最优）解_。 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题_，先求解_子问题__，然后从这些_子问题_的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为__回溯法__。 8.0-1背包问题的回溯算法所需的计算时间为__O（n2n）__,用动态规划算法所需的计算时间为_O（n）__。o(min{nc,2n}) 9.动态规划算法的两个基本要素是_最优子结构_和_重叠子问题 ___。 10.二分搜索算法是利用__动态规划法__实现的算法。

二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 1、解：（1）找出最优解的性质，并刻画其结构特征； （2）递归地定义最优值； （3）以自底向上的方式计算出最优值； （4）根据计算最优值时得到的信息，构造最优解。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解 2.流水作业调度问题的johnson算法的思想。 2、解：①令N1={i|a i=b i}；②将N1中作业按a i 的非减序排序得到N1’，将N2中作业按b i的非增序排序得到N2’； ③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 3、解：步骤为：N1={1，3}，N2={2，4}； N1’={1，3}， N2’={4，2}； 最优值为：38

级《计算机应用基础》期末试题

5. 依据[ ]可以识别文件的类型。 A．文件的大小 B．文件的路径 C．文件的扩展名 D．文件的修改日期 6. 在Windows 7资源管理器中[ ]菜单提供了文件夹设置功能。 A、文件 B、编辑 C、工具D：查看 7. Windows 7中，显示3D桌面效果的快捷键是[ ]。 A．Alt+Tal B．Win+Shift C. Ctrl+Tab D. Win+Tab 8. 计算的主机由( )构成。 A、CPU、内存储器及辅助存储器 B、CPU和内存储器 C、存放在主机箱内部的全部器件 D、计算机主板上的全部器件 9. 计算机中数据的表现形式是( )。 A、八进制 B、十进制 C、二进制 D、十六进制 10. 下列( )文件是压缩文件 A、财务.doc B、财务.exe C、财务.zip D、财务.txt 11. 外存储器中的信息，必须首先调入( )，然后才能供CPU使用 A、ROM B、运算器 C、控制器 D、RAM 12下列“不合法”的文件名是( )。 A、.txt B、 C、 D、 二、填空题（本题共12个空，每空2分，共24分）

是由（）公司开发的操作系统。 14. PDP是指( )显示器。 15. 二进制数1110转换成十进制数为（）。 16．磁盘碎片主要是在对硬盘的频繁写入和删除中产生的，可以用（）来整理。 17. 计算机软件系统中最重要、最基本的系统软件是（）。 18. 为了减少文件传送时间和节省磁盘空间，可使用（）软件对文件“瘦身”。 19. 初次安装系统后，可以使用WIN7的（）功能为该系统创建一个系统映象，以便系统被破坏后恢复。 20．批量搜索文件时所用的通配符有（）和（）。 操作系统中，Ctrl+X是（）命令快捷键。 22.文件或文件夹通常有只读、（）和（）三种属性。 三、判断题（本题共12个小题，每小题2分，共24分） 23.睡眠状态是一种省电状态。（） 24. WIN7属于多用户、桌面操作系统。（） 25.计算机辅助教学的缩写是CAD。（） 26. 所有被删除的文件都是放在回收站中。（） 27. 一个完整的计算机系统由硬件系统和软件系统构成。（） 28.“库”只是“包含”不同文件夹的位置。 ( )29. 在Windows 7中，菜单命令的前面带有符号√，表示该命令当前无效 ( ) 30. 安装杀毒软件是保障缉计算机安全的唯一措施。（）。 31. 避免文件和文件夹丢失或被破坏，可以对重要的文件和文件夹进行备份。 ( ) 32.按下shift键的同时按下字母键，输入大写字母（） 33. 对话框是系统提供给用户输入信息或选择内容的界面（） 34. 语言栏可以浮动显示在屏幕上，也可以显示在任务栏上。（） 四、解答题（本题共5小题，其中35题5分，36题5分， 37题6分，38题6分，39题6分，共28分） 35.简述WIN7操作系统的特点。 36.列举CPU的性能指标。 37.把下面4个数按照从小到大的顺序排列。 B (275)8 191D 1F3H 38简述计算机病毒有什么特征 39.简述窗口切换的方法(两种以上)。

计算机网络期末考试试题及答案

计算机网络试题及答案（一） 一、.填空题 1.所谓计算机网络，会议是利用通信设备和线路将地理位置不同的、功能独立的多个计算机系统互连起来，以功能完善的网络软件实现网络中资源共享和数据通讯的系统。 2.计算机网络如果按作用范围进行分类，可分为广域网（WAN）、局域网（LAN）和城域网（MAN）。 3.网络协议通常采用分层思想进行设计，OSI RM中的协议分为7层，而TCP/IP RM中协议分为4层。 4.在TCP/IP RM中，用于互联层的协议主要有：ARP、IP、RARP、ICMP和IGMP 协议。 5.用于计算机网络的传输媒体有两类：有导线媒体和无导线媒体；光纤可分为两种：单模光纤和多模光纤（MMF）。 6.构成计算机网络的拓扑结构有很多种，通常有星形、总线型、环型、树型、和网状型等。 7.CSMA/CD技术是一种随机接入（所有的用户根据自已的意愿随机地发送数据），冲突不可避免；令牌技术是一种受控接入（各个用户不能任意接入信道而必须服从一定的控制），冲突避免。 8.10BASE-T局域网的数据速率是10mbps，100BASE-TX局域网的数据速率是100mbps。 9.在用双绞线时行组网时，连接计算机和计算机应采用交叉UTP电缆，连接计算机和集线器用直通UTP电缆。 10.在将计算机与10BASE-T集线器进行连接时，UTP电缆的长度不能大于100米。 11.在将计算机与100BASE-TX集线器进行连接时，UTP电缆的长度不能长于100米。 12.以太网交换机和数据交换和转发方式可以分为：直接交换、存储转发交换和改进的直接交换。 13.VLAN的组网方式有两种：静态根据以太网交换机端口进行划分VLAN，动态根据MAC地址、逻辑地址或数据包的协议类型进行划分VLAN。 14.在Internet中，运行IP的互联层可以为其高层用户提供的服务有三个特点：不可靠的数据投递服务、面向无连接的传输服务和尽最大努力投递服务。 15.IP地址由网络号和主机号两部分组成，其中网络号表示互联网中的一个特定网络，主机号表示该网络中主机的一个特定连接。 16.主机的IP地址为202.93.120.77，主机B的IP地址为150.23.55.200。若主机A要向主机B所在的网络进行广播，则直播广播地址为150.23.255.255；若主机A要在本网络中进行广播，则有限广播地址为255.255.255.255。 二、选择题 1.计算机网络是计算机技术和__________相结合的产物。->B A) 网络技术 B) 通信技术 C) 人工智能技术

算法设计与分析复习题目及答案

一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 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、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ）

计算机基础期末考试卷

2017—2018学年度计算机期末考试卷班级姓名学号 一、填空题（12*2分） 1．微型计算机通常由______和______组成。 2．字长是计算机______次能处理的______进制位数。 3．1KB=______B；1GB=______B。 4．计算机中，中央处理器CPU由______和______两部分组成。 5．计算计的软件系统通常分成______软件和______软件。 6．在断电后，能继续为计算机系统供电的电源称为_______。 7．一个2G的U盘能存放500M的电影最多为________几部。 二．选择题（18*2分） 1．第一台电子计算机诞生于（ C ）。 A．德国 B.日本 C.美国 D.英国 2．计算机技术在半个世纪中虽有很大的进步，但至今其运行仍遵循着一位科学家提出的基本原理，他就是（ C ）。 A．牛顿 B.爱因斯坦 C. 冯．诺依曼 D.爱迪生 3．断电后会使数据丢失的存储器是（B ）。 A．ROM B.RAM C.磁盘 D.光盘 4．在windows中，欲剪切当前文件夹，可以使用的组合键是（ C ）。 A．ctrl+v B.ctrl+a C.ctrl+x D.ctrl+d 6．在windows中，关闭程序的方法有许多，下列不正确的是（ B ）。 A 在键盘上，按alt+f4 B.在键盘上按esc键 C.用鼠标单击程序屏幕右上角的“关闭”按钮 D.打开程序的“文件”菜单，选择退出 7．在windows中，欲全选当前文件夹，可以使用的组合键是 B A．ctrl+v B.ctrl+a C.ctrl+x D.ctrl+d 8．下列存储器中，存取速度最快的是（ B ）。 A．硬盘 B.缓存 C.光盘 D.U盘 9．下列不可能出现在Windows资源管理器窗口左部的是（ A ）。 A．文件 B.桌面 C.我的电脑 D.（C：） 10．在计算机系统中，指挥．协调计算机工作的设备是___B__。 A显示器, B.CPU, C内存, D打印机,

计算机网络与通信期末考试复习题及答案范文

《计算机网络与通信》复习题 一、选择题：（每小题1.5分，共21分） 1、在OSI参考模型中，物理层的基本数据单元是（）。 （A）分组（B）报文（C）帧（D）比特流 2、网络用户可以通过Internet给全世界的因特网用户发电子邮件，电子邮件的传递可由下面的（）协议完成。 （A）POP3和ISP （B）POP3和ICP （C）POP3和SMTP （D）POP3和TCP / IP 3、在互联网络中，（）是在物理层实现网络互联的设备。 （A）网关（B）网桥（C）中继器（D）路由器 4、我们将文件从FTP服务器传输到客户机的过程称为（）。 （A）浏览（B）下载（C）上传（D）通信 5、一座建筑物内的几个办公室要实现连网，应该选择方案是（） （A）PAN （B）LAN （C）MAN （D）W AN 6、IPv4地址的表达方式通常是（） （A）32位二进制（B）点分十进制（C）16进制（D）128位二进制 7、Internet网络的主要协议是（）。 （A）TCP/IP （B）ISO11801 （C）IEEE802 （D）RFC2281 8、当前因特网IP协议的主要版本是（） （A）IPv2 （B）IPv6 （C）IPv4 （D）IGMP 9、在一个C类网中，最多可管理（）台主机。 （A）256 （B）255 （C）128 （D）254 10、在常用的传输介质中，带宽最宽、信号传输衰减最小、抗干扰能力最强的一类传输介质是（）。（A）双绞线（B）光纤（C）同轴电缆（D）电话线 11、在以太网络上，双绞线的连接口采用（）。 （A）RJ-11 （B）ST头（C）RJ-45 （D）2312 12、以数据帧的形成是在OSI的（）层。 （A）物理（B）网络（C）数据链路（D）传输 13、计算机网络共享的资源主要是指（） （A）主机、程序、通信信道和数据（B）主机、外设、通信信道和数据 （C）软件、外设和数据（D）软件、硬件、数据和通信信道 14、无线局域网的标准是（）。 （A）IEEE802.2 （B）IEEE802.3 （C）IEEE802.11 （D）IEEE802.5 二、填空题（每空1分，共20分） 1、计算机网络按其覆盖范围来分，计算机网络可分为、和。 2、电话系统由、和三个部件组成。 3、网络互连的类型有、、和等四种。 4、局域网的基本拓朴结构有、和。 5、某个IP地址的十六进制表示为，将其转换为点分十进制形式为， 它属于类地址。 6、如果将一个C类网络划分为30个子网，那么它最多可管理个主机。 7、IP地址中，如果32位全为0，则表示 8、数据交换的三种方式有、和。 第 1 页共6 页

计算机专业期末试题

12级计算机专业《计算机网络》期末考试试题 一、单项选择题(每题2分，共计70分，请把答案填入答卷处） 1. 计算机网络可分为三类，它们是( ) A. Internet、Intranet、Extranet B. 广播式网络、移动网络、点——点式网络 C. X.25、ATM、B—ISDN D. LAN、MAN、WAN 2．组建计算机网络的目的是实现连网计算机系统的（） A. 硬件共享 B. 软件共享 C. 数据共享 D. 资源共享 3.在OSI的( )使用的互联设备是路由器。 A. 物理层 B. 数据链路层 C. 网络层 D. 传输层 4.以下IP地址中，属于c类地址的是（） A．112.213.12.23 B．210.123.23.12 C．23.123.213.23 D．156.123.32.12 5.下列给出的协议中,属于TCP/IP协议结构的应用层协议是( ) A. UDP B. IP C. TCP D. Telnet 6. Windows2000网络操作系统在客户机配置网络时应该遵循的基本顺序为 ( ) A．配置网络标识→安装网卡驱动程序→安装与配置TCP/IP协议 B．安装与配置TCP/IP协议→安装网卡驱动程序→配置网络标识 C．安装网卡驱动程序→安装与配置TCP/IP协议→配置网络标识 D．配置网络标识→安装与配置TCP/IP协议→安装网卡驱动程序 7．在星型局域网结构中，连接文件服务器与工作站的设备是（）A. 调制解调器 B. 交换机

C. 路由器 D. 集线器 8.在Internet上浏览时，浏览器和WWW服务器之间传输网页使用的协议是（） A、IP B、Telnet C、FTP D、HTTP 9．对局域网来说，网络控制的核心是（） A. 工作站 B. 网卡 C. 网络服务器 D. 网络互连设备 10．管理计算机通信的规则称为（） A.协议 B.介质 C.服务 D. 网络操作系统 11．常见的网络协议有（） A. TCP/IP B. TELNET C. IPX/SPX D. NETBEUI 12.下列那一种陈述是真实的？（） A. 对应于系统上的每一个网络接口都有一个IP地址 B. IP地址中有16位描述内容 C. 位于美国的NIC提供具唯一性的32位IP地址 D. D类地址仅用于多投点传送 13.以下IP地址中，属于A类地址的是（） A．52.213.12.23 B．210.123.23.12 C．223.123.213.23 D．156.123.32.12 14.利用各种通信手段，把地理上分散的计算机有机的连在一起，达到相互通信而且共享硬件、软件和数据等系统属于（）。 A. 计算机网络 B. 终端分时系统 C. 分布式计算机系统 D. 多机系统 15.（）因素在整个网络的设计、功能、可靠性和费用等方面有着重要影响。 A. 网络距离 B. 拓扑结构

《算法设计与分析》复习题(汇编)

填空 1．直接或间接地调用自身的算法称为 递归 。 2．算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 3．以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。 5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题 6．算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。 7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8．快速排序算法的性能取决于 划分的对称性 。 9．计算机的资源最重要的是 内存 和 运算 资源。因而，算法的复杂性有时间 和 空间 之分。 10．贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 局部最优解 。 11．许多可以用贪心算法求解的问题一般具有2个重要的性质： 最优子结构的 性质和 贪心选择的 性质。 12．常见的两种分支限界法为 队列式 和 优先队列式 。 13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 动态规划和分支限界法 。 14．f ( n ) = 6 × 2n + n 2，f(n)的渐进性态f ( n ) = O ( 2^n )。 15．对于含有n 个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。 16．在忽略常数因子的情况下，O 、Ω和Θ三个符号中， Θ 提供了算法运行时间的一个上界。 17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。 18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。 19．多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。 21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进

《计算机应用基础》期末考试试题

《计算机应用基础》期末考试试题 班级：_______学号：姓名：成绩： 一、选择题（每题1.5分，共30分） 1、世界上第一台计算机诞生于（）。 A：1946年B：1949年C：1956年D：1959年 2、关于电子计算机的特点，以下论述错误的是（）。 A：运算速度快B：运算精神高 C：具有记忆和逻辑判断能力 D：运行过程不能自动、连续，需人工干预。 3、在微机的硬件设备中，既可以做输出设备，又可以做输入设备的是（）。 A、绘图仪B：扫描仪C：手写笔D：磁盘驱动器 4、计算机病毒是一种（）。 A：微生物感染B：化学感染C：程序D：幻觉 5、计算机病毒不具有（）。 A：寄生性和传染性B：潜伏性和隐蔽性 C：自我复制性和破坏性D：自行消失性和易防范性 6、下列关于存储容量大小换算正确的是（）。 A：1KB=1024MB B：1GB=1024KB C：1TB=1024GB D：1TB=1024MB 7、计算机采用的逻辑元件的发展顺序是（）。 A、晶体管、电子管、集成电路、大规模集成电路 B、电子管、晶体管、集成电路、大规模集成电路 C、晶体管、电子管、集成电路、芯片 D、电子管、晶体管、集成电路、芯片 8、Excel所生的文件扩展名是（）。 A： .txt B: .doc C: .ppt D: .xls 9、Excel单元格中输入公式必须以（）开头。 A：等号B：加号C：单元格地址D：减号 10、在Excel单元格中显示以“0”开头的数字，如学号“01”，则在输入数学 前加（）符号。 A：加号B：双引号C：单引号D：等号 11、如果要中止幻灯片的放映可以按（）。 A：END键B：ESC键C：回车键D：Ctrl+END键 12、下列4项中，合法的IP地址是（）。 A：180.220.5 B：202.53.0.78 C：206.53.392.76 D：202.53.282.22 13、下列域名中，代表教育机构域名的是（）。 A: gov B:net C:edu D:com 14、下面E-mail地址中，（）是无效的。 A：We@https://www.wendangku.net/doc/629662071.html, B：wang@qun@https://www.wendangku.net/doc/629662071.html, C：zhanghao@https://www.wendangku.net/doc/629662071.html, D：wangqun_77@https://www.wendangku.net/doc/629662071.html, 15、二进制数11110001转换为十进制数是( )。 A：241 B：242 C：240 D：244 16、计算机的三大应用领域是（）。 A、科学计算、信息处理和过程控制 B、计算、打字和家教 C、科学计算、辅助设计和辅助教学 D、信息处理、办公自动化和家教

计算机原理期末考试复习题

机密★启用前 大连理工大学网络教育学院 2016年秋《计算机原理》 期末考试复习题 ☆注意事项：本复习题满分共：400分。 一、单项选择题 1、从器件角度看，计算机经历了四代变化。但从系统结构看，至今绝大多数计算机仍属于（）。 A．并行型计算机C．冯?诺依曼型计算机B．智能型计算机D．实时处理型计算机 2、至今为止，计算机中的所有信息仍以二进制方式表示，其主要理由是（）。 A．节约元件 C．物理上容易实现B．运算速度快D．信息处理方便 3、对计算机的软、硬件资源进行管理，是（）的功能。 A．操作系统C．语言处理程序B．数据库管理系统D．用户程序 4、通常把组成一个字的二进制位数称为（）。 A．位B．字节C．字长D．字 5、若x的补码为10000110，则x的原码为（）。 A．11111011 B．11111010 C．10111011 D．10111010 6、浮点数的表示范围和精度取决于（）。 A．阶码的位数和尾数的位数 B．阶码采用的编码和尾数的位数 C．阶码采用的编码和尾数采用的编码 D．阶码的位数和尾数采用的编码 7、ROM和RAM的主要区别是（）。 A．断电后，ROM内保存的信息会丢失，RAM则可长期保存而不会丢失 B．断电后，RAM内保存的信息会丢失，ROM则可长期保存而不会丢失 C．ROM是外存储器，RAM是内存储器

D．ROM是内存储器，RAM是外存储器 8、假设主存储器的容量为1GB，则表示其容量为（）。 A．1000KB B．1024KB C．1000MB D．1024MB 9、能发现两位错误并能纠正一位错误的编码为（）。 A．CRC码B．海明码C．偶校验码D．奇校验码10、ALU属于（）部件。 A．运算器B．控制器C．寄存器D．存储器11、运算器的主要功能是进行（）。 A．逻辑运算 C．算术运算和逻辑运算B．算术运算D．只作加法 12、在主存和CPU之间增加cache的目的是（）。 A．增加内存容量C．提高内存的可靠性B．解决CPU与内存之间的速度匹配问题D．增加内存容量，同时加快存取速度 13、计算机的存储器系统是指（）。 A．RAM C．ROM B．主存储器 D．cache、主存储器和外存储器 14、和外存储器相比，内存储器的特点是（）。 A．容量大，速度快，成本低C．容量大，速度慢，成本高B．容量小，速度快，成本高D．容量小，速度快，成本低 15、计算机的存储器采用分级存储体系的主要目的是（）。 A．便于读写数据B．减少机箱的体积 C．便于系统升级D．解决存储容量、价格和存取速度之间的矛盾16、第一代计算机的主要器件是（）。 A．电子管B．小规模集成电路C．大规模集成电路D．晶体管 17、微型计算机的发展是以（）技术为标志。 A．操作系统B．微处理器C．磁盘D．软件 18、“只读存储器”的英文缩写是（）。 A．ROM B．RAM C．PLA D．REM 19、若十进制数据为6，则二进制数是（）。 A．0110 B．0111 C．1000 D．1001

计算机期末考试模拟试题及答案

多媒体应用技术及上机实践理论作业1 专业班级：商务英语二班学生姓名：屈美玲学号： 2011128520201 一、单选题（本大题共20小题，每小题1分，共20分） 1.在计算机内，多媒体数据最终是以____A____形式存在。 A、二进制代码 B、特殊的压缩码 C、模拟数据 D、图形图像、文字、声音 2.下列选项中， D 不属于存储媒体。 A、纸张 B、磁带 C、光盘 D、光纤 3.最基本的多媒体计算机是指安装了____B____部件的计算机。 A、高速CPU和高速缓存 B、光盘驱动器和声卡 C、光盘驱动器和视频卡 D、光盘驱动器和TV卡 4.下列选项中， C 不属于数码相机的技术指标。 A、分辨率 B、光学镜头和性能 C、存储器 D、扫描幅面 5.JPEG代表的含义 B 。 A、一种视频格式 B、一种图形格式 C、一种网络协议 D、软件的名称 6.量化是指 C 。 A、对模拟信号的放大或缩小 B、对数字信号的放大或缩小 C、模拟信号到数字信号的映射 D、数字信号到模拟信号的映射 7.CD-ROM是指 B 。 A、数字音频 B、只读存储光盘 C、交互光盘 D、可写光盘 8.波形声音文件是A文件。 A、WA V B、MIDI C、MP3 D、AIF 9.下列采集的波形声音质量最好的是 D 。 A、单声道、8位量化、22.05kHz采样频率

B、双声道、8位量化、22.05kHz采样频率 C、单声道、16位量化、22.05kHz采样频率 D、双声道、16位量化、44.1kHz采样频率 10.在Photoshop中， B 内容不随文件而存储。 A、通道 B、历史记录 C、图层 D、ICC色彩描述文件 11.Photoshop里的什么工具可以用作抠图： C 。 A、画笔工具 B、渐变工具 C、磁性套索工具 D、喷枪工具 12.PhotoShop默认的文件类型是 D 。 A、JPEG B、BMP C、PPT D、PSD 13.在Photoshop中对选区的羽化描述正确的是 C 。 A、使选取范围扩大 B、使选取范围缩小 C、使选取边缘柔软 D、使选取范围锐化 14.A是数字音乐合成器的统一国际标准，它规定计算机音乐程序、电子合成 器和其他电子设备之间交换信息与控制信号的方法。 A、MIDI B、AIF C、MP3 D、RA 15.MP3代表的含义是 B 。 A、一种视频格式 B、一种音频格式 C、一种网络协议 D、软件的名称 16.下列文件格式中， C 是网络动画的类型格式。 A、MOV B、A VI C、SWF D、MP3 17.Flash MX 中，形变动画的对象是A。 A、矢量对象 B、文本对象 C、位图对象 D、以上都可以 18.Authorware是一种____ C ____。 A、多媒体演播软件 B、多媒体素材编辑软件 C、多媒体制作工具 D、不属于以上三种 19.Authorware中的运动图标提供了 C 种运动方式。 A、3 B、4 C、5 D、6

2015算法设计与分析考试复习刚要习题

计算机算法设计与分析复习题一、填空题1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上，因此算法的复杂性有时间复杂性和空间复杂性之分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O （1），在最坏情况下，搜索的时间复杂性为O（logn）。4、已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程： n2O(1) T(n)2T(n/2)O(n)n2解得此递归方可得T(n)= O（）。 nlogn5、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。递归的二分查找算法在divide阶段所花的时间是 O(1) ，conquer阶段6．所花的时间是 T(n/2) ，算法的时间复杂度是 O( log n) 。7．Prim算法利用贪心策略求解最小生成树问题，其时间复杂度是 2O(n) 。8．背包问题可用贪心法，回溯法等策略求解。39．用动态规划算法计算矩阵连乘问题的最优值所花的时间是 O(n) ，子2问题空间大小是 O(n) 。10．图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是nm ，解空间树中每个内结点的孩子数是 m 。11．单源最短路径问题可用贪心法、分支限界等策略求解。12、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。 13、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。 14、直接或间接地调用自身的算法称为（递归算法）。 15、记号在算法复杂性的表示法中表示（渐进确界或紧致界）。 16、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题）的思想。 17、动态规划算法适用于解（具有

2010(2)计算机基础期末考试试卷(A卷) 2

华南农业大学期末考试试卷（A 卷） 2010学年第2学期 考试科目： 大学计算机基础 考试类型：（闭卷） 考试时间： 120 分 钟 学号 姓名 年级专业 考生注意： 1、 答案必须分别写在“机读卡”和“答题卷”上，写在试卷上不得分。 2、 必须在机读卡和答题卷上正确填写班级、学号、姓名等内 容，否则没有考试成绩。 3、 在机读卡的学生代号区只填写学号后10位。 4、 考试不能使用计算器等电子设备。 一、 判断题（本大题共 50小题，每小题0.5分，共（在机读卡上答题，正确选A ，错误选B ） 1. 英国数学家图灵在1936年提出了对数字计算机具有深远影

响的“存储理论”模型。 2.当数据以某种形式被处理、描述或与其它数据比较时，它才 成为信息。 3.设备驱动程序属于支撑软件。F 4.在计算机中，一个浮点数由阶码和尾数两部分组成。 5.现代信息技术以计算机技术、微电子技术和多媒体技术为特 征。 6.最早的计算机程序设计是由冯?诺依曼编写的。 7.在计算机内部用于存储、加工处理汉字的编码称为汉字内 码。T 8.嵌入式计算机是指作为一个信息处理部件嵌入到应用系统 中的计算机。T 9.一台普通的微机只要安装了网络操作系统、网络协议和服务 软件就可以充当服务器。 10.字长是存储信息的基本单位。 11.24×24汉字点阵字库中，表示一个汉字字模需要2字节。 12.外存上的信息可直接进入CPU被处理。 13.在计算机中，8位原码能表示数的范围为0~255。F 14.4位二进制数可表示1位十六进制数。 15.我们将CPU和系统总线之间频率相差的倍数称CPU的倍 率。T 16.PCI总线是现代总线的标准。

计算机应用基础期末考试复习题答案

计算机应用基础期末考 试复习题答案 Standardization of sany group #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#

计算机应用基础期末考试复习题 一、基本知识与Windows D 1. 计算机不能正常工作时，与以下无关。 A. 硬件配置达不到要求 B. 软件中含有错误 C. 使用者操作不当 D. 环境噪声太大 B 2. 缺少，计算机就无法工作。 A. 汉字系统 B. 操作系统 C. 编辑程序 D. 文字处理系统 D 3. 显示器的越高，显示的图像越清晰。 A. 对比度 B. 亮度 C. 对比度和亮度 D. 分辨率 D 4. 下面不是系统软件。 A. Dos、Unix B. Windows NT、Windows 95 C. Linux D. Word、Excel B 5. 是中央处理器的简称。 A. RAM B. CPU C. 控制器 D. 运算器 C 6. 在计算机内部，传送、存储、加工处理的数据或指令都是以的形式进行的。 A. 五笔字型码 B. 八进制吗 C. 二进制码 D. 拼音简码 C 7. 用计算机进行语言翻译和语言识别，按计算机应用的分类，它应属 于。 A. 科学计算 B. 辅助设计 C.人工智能 D. 实时控制 C 8. 个人计算机属于。 A. 小巨型机 B. 小型计算机 C. 微型计算机 D. 中型计算机

D 9. 计算机网络最突出的优点是。 A. 精度高 B. 运算速度快 C. 存储容量大 D. 共享资源D 10. 英文字符“E” 的ASCII码是。 A. 66 B. 67 C. 68 D. 69 B 11.计算机能与网络连接需要配置。 A. MODEM B. 网卡 C. 电话线 D. 解压卡 D 12. E-mail的中文含义是。 A. 远程查询 B. 文件传输 C. 远程登录 D. 电子邮件 C 13. 要浏览网页，必须知道该网页的。 A. E-mail地址 B. 电话号码 C. 网址 D. 邮政编码 B 14. TCP/IP是。 A. 网络名 B. 网络协议 C. 网络应用 D. 网络系统 A 15. 微型计算机必不可少的输入和输出设备是。 A. 键盘和显示器 B. 键盘和鼠标 C. 显示器和打印机 D. 鼠标器和打印机 D 16. CUP是由组成的。 A. 内存储器和控制器 B. 控制器和运算器 C. 高速缓存和运算器 D. 运算器、控制器和内存储器B 17. 光盘是一种。 A. 内存储器 B. 外存储器 C. 中央处理器 D. 通讯设备 D 18. 下面设备不属于输入设备的是。