当前位置：文档库 › 算法分析期末试题集答案

算法分析期末试题集答案

1.应用Johnson法则的流水作业调度采用的算法是（D）

A. 贪心算法

B. 分支限界法

C.分治法

D. 动态规划算法

2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B）

Hanoi塔

3. 动态规划算法的基本要素为（C）

A. 最优子结构性质与贪心选择性质

B．重叠子问题性质与贪心选择性质

C．最优子结构性质与重叠子问题性质

D. 预排序与递归调用

4. 算法分析中，记号O表示（B），记号Ω表示（A），记号Θ表示（D）。

A.渐进下界

B.渐进上界

C.非紧上界

D.紧渐进界

E.非紧下界

5. 以下关于渐进记号的性质是正确的有：（A）

A.f(n)(g(n)),g(n)(h(n))f(n)(h(n))

=Θ=Θ?=Θ

B. f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))

==?=

C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})

D. f(n)O(g(n))g(n)O(f(n))

=?=

6.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）

A. 最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质

C．最优子结构性质与重叠子问题性质D. 预排序与递归调用

7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。

A．广度优先B. 活结点优先 C.扩展结点优先 D. 深度优先

8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。

A．广度优先B. 活结点优先 C.扩展结点优先 D. 深度优先

9. 程序块（A）是回溯法中遍历排列树的算法框架程序。

10. 回溯法的效率不依赖于以下哪一个因素？（C ）

A.产生x[k]的时间；

B.满足显约束的x[k]值的个数；

C.问题的解空间的形式；

D.计算上界函数bound的时间；

E.满足约束函数和上界函数约束的所有x[k]的个数。

F.计算约束函数constraint的时间；

11. 常见的两种分支限界法为（D）

A. 广度优先分支限界法与深度优先分支限界法；

B. 队列式（FIFO）分支限界法与堆栈式分支限界法；

C. 排列树法与子集树法；

D. 队列式（FIFO）分支限界法与优先队列式分支限界法；

12. k带图灵机的空间复杂性S(n)是指（B）

A.k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数。

B.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总

和。

C.k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数。

D.k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数。

13. N P类语言在图灵机下的定义为（D）

A.NP={L|L是一个能在非多项式时间内被一台NDTM所接受的语言}；

B.NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；

C.NP={L|L是一个能在多项式时间内被一台DTM所接受的语言}；

D.NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；

14. 记号O的定义正确的是（A）。

A.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤

cg(n) }；

B.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤

f(n) }；

>0使得对所有n≥n0 C.O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n

有：0 ≤f(n)

>0使得对所有D.O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n

n≥n0有：0 ≤cg(n) < f(n) }；

15. 记号Ω的定义正确的是（B）。

A.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤

cg(n) }；

B.O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤

f(n) }；

C.(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n

>0使得对所有n≥n0

有：0 ≤f(n)

D.(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0>0使得对所有n≥n0

有：0 ≤cg(n) < f(n) }；

1. 程序段的所需要的计算时间为（ 2

O (n ) ）。

2. 有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果

以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动（ {1，4，8，11} ）。

3. 所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最

优的选择，即贪心选择来达到）

。

4. 所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。

5. 回溯法是指（具有限界函数的深度优先生成法）。

6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为（O(h(n))）。

7. 回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排列树）算法框架。

f[i]

12 2 8 8 6 5 3 5 0 3 1 S[i] 11 10 9 8 7 6 5 4 3 2 1 i

8. 用回溯法解0/1背包问题时，该问题的解空间结构为（子集树）结构。 9.用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结构。

10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：

11. 用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为

n m 的方格阵列，扩展每个结点需O(1)的时间，L 为最短布线路径的长度，则算法共耗时 ( O(mn) )，构造相应的最短距离需要（O(L)）时间。

12. 每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O （mn ））。

13. 旅行售货员问题的解空间树是（排列树）。二、

解答题

1. 机器调度问题。

问题描述：现在有n 件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为s i ，完成时间为f i ，s i

问题实例：若任务占用的时间范围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法）

画出工作在对应的机器上的分配情况。

2. 已知非齐次递归方程：f (n)bf (n 1)g(n)

f (0)c =-+??=?

，其中，b 、c 是常数，

g(n)是n 的某一个函数。则f(n)的非递归表达式为：n

n i i 1

f (n)cb b g(i)-==+∑。

现有Hanoi 塔问题的递归方程为：h(n)2h(n 1)1

h(1)1=-+??=?

，求h(n)的非递归表

达式。

解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n 递推到1，有：

n 1

n 1i i 1

n 1n 22n h(n)cb

b g(i)

22 (22121)

----=--=+=+++++=-∑ 3. 单源最短路径的求解。问题的描述：给定带权有向图（如下图所示）G

=(V,E)，其中每条边的权是非负实数。另外，还给定V 中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

解法：现采用Dijkstra 算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。

4. 请写出用回溯法解装载问题的函数。

装载问题：有一批共n 个集装箱要装上2艘载重量分别为c1和c2的轮船，

其中集装箱i 的重量为wi ，且

i i w c

c =≤+∑。装载问题要求确定是否有一个合理

的装载方案可将这n 个集装箱装上这2艘轮船。如果有，找出一种装载方案。

解：void backtrack (int i)

{// 搜索第i 层结点

if (i > n) // 到达叶结点

更新最优解bestx,bestw;return; r -= w[i];

if (cw + w[i] <= c) {// 搜索左子树 x[i] = 1; cw += w[i];

backtrack (i + 1); cw -= w[i]; }

3 2 1 100 30 maxint

10 - {1} 初始 dist[5] dist[4] dist[3] dist[2] u S 迭代

if (cw + r > bestw) {

x[i] = 0; // 搜索右子树 backtrack (i + 1); } r += w[i]; }

5. 用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。

解答：斜线标识的部分完成的功能为：提前更新bestw 值；

这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading 初始时将bestw 设置为0，直到搜索到第一个叶结点时才更新bestw 。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw 总是成立。也就是说，此时右子树测试不起作用。

为了使上述右子树测试尽早生效，应提早更新bestw 。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw 的值。

7. 最长公共子序列问题：给定2个序列X={x 1,x2,…,xm }和Y={y 1,y2,…,yn }，找出X 和Y 的最长公共子序列。

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列Xi 和Yj 的最长公共子序列的长度。其中，

Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi 和

的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立

递归关系如下：

00,0 [][][1][1]1,0;

max{[][1],[1][]},0;

i j

c i j c i j i j x y

?==

=--+>=

?-->≠

在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。

写程序中的空格，以使函数LCS完成构造最长公共子序列的功能（请

将b[i][j]的取值与（1）中您填写的取值对应，否则视为错误）。

8.对下面的递归算法，写出调用f(4)的执行结果。

一、简要回答下列问题：

1. 算法重要特性是什么？

2. 算法分析的目的是什么？

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

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

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

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

7. 背包问题的目标函数和贪心算法最优化量度相同吗？ 8. 采用回溯法求解的问题，其解如何表示？有什么规定？ 9. 回溯法的搜索特点是什么？

10. n 皇后问题回溯算法的判别函数place 的基本流程是什么？ 11. 为什么用分治法设计的算法一般有递归调用？ 12. 为什么要分析最坏情况下的算法时间复杂性？ 13. 简述渐进时间复杂性上界的定义。 14. 二分检索算法最多的比较次数？

15. 快速排序算法最坏情况下需要多少次比较运算？ 16. 贪心算法的基本思想？

17. 回溯法的解（x 1,x 2,……x n ）的隐约束一般指什么？ 18. 阐述归并排序的分治思路。

19. 快速排序的基本思想是什么。

20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？ 21. 什么是哈密顿环问题？

22. 用回溯法求解哈密顿环，如何定义判定函数？ 23. 请写出prim 算法的基本思想。

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

2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。

3. 算法的时间复杂性与问题的规模相关，是问题大小n 的函数。

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

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

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

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

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

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

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

回溯法的搜索特点是什么

7. 不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。

8. 问题的解可以表示为n元组：（x1,x2,……x n），x i∈S i, S i为有穷集合，x i∈S i, （x1,x2,……x n）具备完备性，即（x1,x2,……x n）是合理的，则（x1,x2,……x i）(i

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

10. 将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。

11 . 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。

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

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

14 .二分检索算法的最多的比较次数为 log n 。

15．.最坏情况下快速排序退化成冒泡排序，需要比较n2次。

16. 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。

17．回溯法的解（x1,x2,……x n）的隐约束一般指个元素之间应满足的某种关系。

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

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

20.在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。

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

22.当前选择的节点X[k]是从未到过的节点,即X[k]≠X[i](i=1,2,…,k-1)，且C(X[k-1], X[k])≠∞，如果k=-1，则C(X[k], X[1]) ≠∞。

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

二、复杂性分析

1、MERGESORT(low，high)

if low

then mid ←(low ，high)/2； MERGESORT(low ，mid)； MERGESORT(mid+1，high)； MERGE(low ，mid ，high)；

endif

end MERGESORT

答: 1、递归方程

设n=2k

解递归方程：

2、 procedure S1(P ，W ，M ，X ，n) i ←1; a ←0

while i ≤ n do

if W(i)>M then return endif a ←a+i i ←i+1 ; repeat end

解： i ←1 ;s ←0 时间为：O(1) while i ≤ n do 循环n 次循环体内所用时间为 O(1) 所以总时间为:

T(n)=O(1)+ nO(1)= O(n) 3.procedure PARTITION(m,p)

Integer m,p,i;global A(m:p-1) v ←A(m);i ←m

loop

loop i ←i+1 until A(i) ≥v repeat loop p ←p-1 until A(p) ≤v repeat

if i

then call INTERCHANGE(A(i),A(p)) else exit endif repeat

A(m) ←A(p);A(p) ←v End PARTITION

解：最多的查找次数是p-m+1次

4.procedure F1(n)

if n<2 then return(1)

else return(F2(2,n,1,1)) endif

???

>+==1)2/(21)(n cn n T n a n T n

cn an kcn

T cn

n T cn cn n T n T k log )1(22)4/(4)2/)4/(2(2)(+=+=+=++=

end F1

procedure F2(i,n,x,y)

if i≤n

then call F2(i+1,n,y,x+y)

endif

return(y)

end F2

解：F2（2，n,1,1）的时间复杂度为：

T(n)=O(n-2); 因为i≤n时要递归调用F2，一共是n-2次

当n＝1时F1(n)的时间为 O(1)

当n>1时F1(n)的时间复杂度与F2(2,n,1,1)的时间复杂度相同即为为 O(n) 5.procedure MAX(A,n,j)

xmax←A(1);j←1

for i←2 to n do

if A(i)>xmax then xmax←A(i); j←i;endif

repeat

end MAX

解：xmax←A(1);j←1 时间为：O(1)

for i←2 to n do 循环最多n-1次

所以总时间为:

T(n)=O(1)+ (n-1)O(1)= O(n)

6.procedure BINSRCH(A,n,x,j)

integer low,high,mid,j,n;

low←1;high←n

while low≤high do

mid←|_(low+high)/2_|

case

:x>A(mid):low←mid+1

:else:j←mid; return

endcase

repeat j←0

end BINSRCH解：log2n+1

三、算法理解

1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。

各边的代价如下：

C(1,2)=3， C(1,3)=5 ，C(1,4)=2

C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1

C(5,8)=4， C(6,8)=5 ，C(7,8)=6

解：Cost(4,8)=0

Cost(3,7)= C(7,8)+0=6 ，D[5]=8

Cost(3,6)= C(6，8)+0=5, D[6]=8

Cost(3,5)= C(5，8)+0=4 D[7]=8

Cost(2,4)= min{C(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)}

= min{1+ 5, 2+4}=6 D[4]=6

Cost(2,3)= min{C(3，6)+ Cost(3,6) }

= min{4+5}=9 D[3]=5

Cost(2,2)= min{C(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)}

= min{8+5, 4+6}=10 D[2]=7

Cost(1,1)= min{C(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)}

= min{3+10, 5+9,2+6}= 8

D[1]=4

1→4→6→8

2、写出maxmin算法对下列实例中找最大数和最小数的过程。

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

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

数组 A=()

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

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

3、快速排序算法对下列实例排序，算法执行过程中，写出数组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

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

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

5、写出图着色问题的回溯算法的判断X[k]是否合理的过程。

解：i←0

while i

if G[k,i]=1 and X[k]= X[i] then

return false

i←i+1

repeat

if i= k then return true

6、对于下图，写出图着色算法得出一种着色方案的过程。

解：K←1

X[1] ←1 , 返回 true

X[2]←1,返回false; X[2]←X[2]+1=2, 返回 true

X[3]←1 ,返回false; X[3]←X[3]+1=2, 返回false;X[3]←X[3]+1=3, 返回 true X[4]←1, 返回false; X[4]←X[4]+1=2, 返回false;X[4]←X[4]+1=3, 返回 true 找到一个解（1，2，3，3）

7、写出第7题的状态空间树。

解：

8、写出归并排序算法对下列实例排序的过程。

(6,2,9,3,5,1,8,7)

解：调用第一层次 6,2,9,3 5,1,8,7 分成两个子问题调用第二层次 6,2 9,3 5,1 8,7 分成四个子问题

调用第三层次 6 2 9 3 5 1 8 7 分成八个子问题

调用第四层次只有一个元素返回上一层

第三层归并 2 ,6 3, 9 1,5 7,8 返回上一层

第二层归并 2 ,3,6, 9 1,5,7,8 返回上一层

第一层归并 1, 2 ,3, 5 ,6, 7, 8,9 排序结束，返回主函数

9、写出用背包问题贪心算法解决下列实例的过程。

P=(18,12,4,1)

W=(12,10,8,3)

M=25

解:实例符合P(i)/W(i)≥P(i+1)/W(i+1)的顺序。

CU←25,X←0

W[1]< CU: x[1]←1; CU←CU-W[1]=13;

W[2]< CU: x[2]←1; CU←CU-W[2]=3;

W[3]>CU: x[3]←CU/ W[3]=3/8;

实例的解为：（1，1，3/8，0）

1、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。

解：有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。

一共要要执行四次才能找到值为82的数。

12、使用prim算法构造出如下图G的一棵最小生成树。

dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;

dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6

解：使用普里姆算法构造出如下图G的一棵最小生成树。

dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6

13、有如下函数说明 int f(int x,int y) {

f=x Mod y +1; }

已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k 的值是多少并写出详细过程。解：有如下函数说明 int f(int x,int y) {

f=x Mod y +1; }

已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k 的值是多少并写出详细过程。

} K 的值是5

14、McCathy 函数定义如下：当x>100时 m(x)=x-10;

当x<=100时 m(x)=m(m(x+11));

编写一个递归函数计算给定x 的m(x)值。解：McCathy 函数定义如下：当x>100时 m(x)=x-10;

当x<=100时 m(x)=m(m(x+11));

编写一个递归函数计算给定x 的m(x)值。 int m(int x) {

int y;

if(x>100) return(x-100);

else

{

y=m(x+11);

return (m(y));

}

15、设计一个算法在一个向量A中找出最大数和最小数的元素。

解：设计一个算法在一个向量A中找出最大数和最小数的元素。

Void maxmin(A,n)

Vector A;

int n;

{

int max,min,i;

max=A[1];min=A[1];

for(i=2;i<=n;i++)

if(A[i]>max)max=A[i];

else if(A[i]

printf(“max=%d,min=%d\n”,max,min);

}

四、设计算法

1.设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为t i。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。

多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。

解：对于处理机j，用S[j] 表示处理机j已有的作业数，用P[j,k]表示处理机j的第k个作业的序号。

1）将作业按照t[1]≥t[2]≥……≥t[n]排序

2）S[1:m]清零 j←0 //从第一个处理机开始安排

3) for i←1 to n do //安排n个作业

j←j mod m +1 //选下一个处理机

S[j]←S[j]+1;

P[j,S[j]]←i ；

Repeat

2. 设有n种面值为:

d1≥d2≥……≥d n的钱币，需要找零钱M，如何选择钱币d k，的数目X k，满足d1×X i＋……d n×X n M ，使得

X i＋……X n 最小

请选择贪心策略，并设计贪心算法。

解：贪心原则：每次选择最大面值硬币。

CU←M;i←1;X←0 // X为解向量

While CU≠0 do

X[i]←CU div d[i] // X[i]为第i中硬币数

CU←CU-d[i]*X[i]

i←i+1;

repeat

3.有n个物品，已知n=7, 利润为P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获最优解。

解：定义结构体数组G，将物品编号、利润、重量作为一个结构体：例如G[k]={1,10,2} 求最优解，按利润/重量的递减序，有

{5,6,1,6} {1,10,2,5}{6,18,4,9/2} {3,15,5,3} {7,3,1,3}{2,5,3,5/3} {4,7,7,1} 算法

procedure KNAPSACK(P，W，M，X，n)

//P(1：n)和W(1；n)分别含有按

P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值

和重量。M是背包的容量大小，而x(1：n)是解向量//

real P(1：n)，W(1：n)，X(1：n)，M，cu；

integer i，n；

X←0 //将解向量初始化为零//

cu←M //cu是背包剩余容量//

for i←1 to n do

if W(i)>cu then exit endif

X(i) ←1

cu←cu-W(i)

repeat

end GREEDY-KNAPSACK

根据算法得出的解：

X=（1,1,1,1,1,0,0）获利润52，而解

（1,1,1,1, 0, 1,0）可获利润54

因此贪心法不一定获得最优解。

4. 设计只求一个哈密顿环的回溯算法。

解：Hamiltonian(n)

{k←1; x[k] ←0;

While k>0 do

x[k] ← x[k]+1;

while B(k)=false and x[k]≤n do

x[k] ← x[k]+1; repeat

If x[k]≤n then

if k=n then {print x; return}

else {k← k+1; x[k]←0;} endif

else k← k-1

endif

repeat

end

procedure B(k)

{ G[x[k-1],x[k] ]≠1 then return false;

for i←1 to k-1 do

if x[i]=x[k] then return false;endif repeat

return true; }

5．利用对称性设计算法，求n 为偶数的皇后问题所有解。解：利用对称性设计算法，求n 为偶数的皇后问题所有解。 procedure NQUEENS1(n)

a ←0 //计数器清零

X(1)←0；k ←1 //k 是当前行；X(k)是当前列// While k>0 do //对所有的行执行以下语句// 1) { X(k)←X(k)+1 //移到下一列// While X(k)≤n and not PLACE(k) do 2) X(k)←X(k)十l if X(k)≤n then if k=n / then

{print (X)，a ←a+1 //找到一个解计数器a 加1//

if a=n/2 then return // 找到n/2个解算法结束 3) else {k ←k+1；X(k)←0；} 4) else k ←k －1 //回溯// }

end NQUEENS

1、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或))(()(n g n f Ω=或

))(()(n g n f θ=，并简述理由。

（12分） (1) ;5log )(;log )(2+==n n g n n f

(2) ;100)(;2)(2n n g n f n == (3) ;3)(;2)(n n n g n f ==

解：简答如下：

（1）)5(log log 2

+=n n θ，（2）)100(22

n n

Ω=，（3）)3(2n

ο=

2、试用分治法实现有重复元素的排列问题：设),...,,{21n r r r R =是要进行排列的n 个元素，其中元素n r r r ,...,,21可能相同，试计算R 的所有不同排列。（13分）

解：解答如下：

Template

void Perm(Type list[],int k,int m) {

if(k= =m){

for(int i=0;i<=m;i++) cout<

else for(int i=k;i<=m;i++) if(ok(list,k,i)){

swap(list[k],list[i]);

线性代数期末试题及答案

工程学院2011年度（线性代数）期末考试试卷样卷一、填空题（每小题2分，共20分） 1.如果行列式233 32 31 232221 131211 =a a a a a a a a a ，则=---------33 32 31 232221 13 1211222222222a a a a a a a a a 。 2.设2 3 2 6219321862 131-= D ，则=+++42322212A A A A 。 3.设1 ,,4321,0121-=??? ? ??=???? ??=A E ABC C B 则且有= 。 4.设齐次线性方程组??? ?? ??=????? ??????? ??000111111321x x x a a a 的基础解系含有2个解向量，则 =a 。、B 均为5阶矩阵，2,2 1 == B A ，则=--1A B T 。 6.设T )1,2,1(-=α,设T A αα=，则=6A 。 7.设A 为n 阶可逆矩阵，*A 为A 的伴随矩阵，若λ是矩阵A 的一个特征值，则*A 的一个特征值可表示为。 8.若31212322 212232x x x tx x x x f -+++=为正定二次型，则t 的范围是。

9.设向量T T )1,2,2,1(,)2,3,1,2(-=β=α，则α与β的夹角=θ 。 10. 若3阶矩阵A 的特征值分别为1，2，3，则=+E A 。

二、单项选择（每小题2分，共10分） 1.若齐次线性方程组??? ??=λ++=+λ+=++λ0 00321 321321x x x x x x x x x 有非零解,则=λ（） A .1或2 B . －1或－2 C .1或－2 D .－1或2. 2.已知4阶矩阵A 的第三列的元素依次为2,2,3,1-，它们的余子式的值分别为 1,1,2,3-，则=A （） A .5 B .-5 C .-3 D .3 3.设A 、B 均为n 阶矩阵，满足O AB =，则必有（） A .0=+ B A B .））B r A r ((= C .O A =或O B = D .0=A 或0=B 4. 设21β,β是非齐次线性方程组b X A =的两个解向量，则下列向量中仍为该方程组解的是（） A ．21+ββ B ． ()21235 1 ββ+ C ．()21221ββ+ D ．21ββ- 5. 若二次型3231212 3222166255x x x x x x kx x x f -+-++=的秩为2，则=k （） A . 1 B .2 C . 3 D . 4 三、计算题 (每题9分，共63分) 1.计算n 阶行列式a b b b a b b b a D n Λ ΛΛΛΛΛΛ=

计算机操作系统3套期末考试题及答案

计算机专业计算机操作系统试题 2003年7月一、选择题(选择一个正确的答案的代号填入括号中，共38分) 1．操作系统核心部分的主要特点是( )。 A．一个程序模块B．主机不断电时常驻内存 C．有头有尾的程序D．串行顺序执行 2．操作系统中用得最多的数据结构是( )。 A．堆栈B．队列 C．表格D．树 3. 索引式(随机)文件组织的一个主要优点是( )o A．不需要链接指针B．能实现物理块的动态分配 C．回收实现比较简单D．用户存取方便 4．文件目录的主要作用是( )。 A．按名存取B．提高速度 C．节省空间D．提高外存利用率 5．在操作系统管理中，面向用户的管理组织机构称为( )。 A．用户结构B．实际结构 C．物理结构D．逻辑结构 6．单机操作系统的共享资源主要是指( )。 A．内存、CPU和基本软件B．键盘、鼠标、显示器 C．打印机、扫描仪D．软盘、硬盘、光盘 7．为方便用户，操作系统负责管理和控制计算机系统的( )。 A．软件资源B．硬件和软件资源 C．用户有用资源D．硬件资源 8．设备I／O方式有如下三种：( )、( )和( )。 A．假脱机B．询问 C．联机D．中断 E．通道F．脱机 9．操作系统五大功能中作业管理包含( )和( )；文件管理又称( )；存储管理主要讲解( )；设备管理是最原始的( )；进程管理实质上是( )。 A．CPU的执行调度管理B．用户任务管理 C. 信息管理D．监控程序管理 E．人机交互界面管理F．内存管理 10．计算机在接受用户请求后处理数据以及在数据处理结束时，将结果送到终端显示器。例如，导弹控制系统应选择安装( )；计算机订票系统应选择安装( )；计算机语言学习系统应选择安装( )。A．批处理操作系统B．分时操作系统 C．实时操作系统D．网络操作系统 E．分布式操作系统二、是非题(正确的划√，错的划×，其它符号按错论。共20分) ( )1．系统调用是操作系统和用户进程的接口，库函数也是操作系统和用户的接口。 ( )2．UNIX的i节点(内码)是文件系统的主要数据结构(表格)部分。 ( )3．虚地址即程序执行时所要访问的内存地址。

2015年算法分析与设计期末考试试卷B卷

西南交通大学2015 — 2016学年第(一)学期考试试卷课程代码 3244152课程名称算法分析与设计考试时间 120分钟阅卷教师签字： __________________________________ 填空题(每空1分，共15分) 1、程序是 (1) 用某种程序设计语言的具体实现。 2、矩阵连乘问题的算法可由 (2) 设计实现。 3、从分治法的一般设计模式可以看出，用它设计出的程序一般是 (3) 4、大整数乘积算法是用 (4) 来设计的。 5、贪心算法总是做出在当前看来 (5) 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 (6) o 6、回溯法是一种既带有 (7) 又带有 (8) 的搜索算法。 7、平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 (9) 类型 8、在忽略常数因子的情况下，0、门和0三个符号中， (10) 提供了算法运行时间的一个上界。 9、算法的“确定性”指的是组成算法的每条 (11) 是清晰的，无歧义的。 10、冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。 11、算法就是一组有穷 (13)，它们规定了解决某一特定类型问题的 (14) o 12、变治思想有三种主要的类型：实例化简，改变表现， (15) o 、 ___________________________________________________________________________________ L 线订装封密线订装封密、 __________________ 二线订装封密级班选择题(每题2分，共20 分)

北京大学操作系统期末试题有答案

操作系统原理试题一. 名词解释题 1. 中断—— 2. 进程控制块(PCB)――它是进程实体的一部分，是操作系统最重要的记录型数据结构, 是进程存在的唯一标识 3. 虚时钟 4. 段式管理 5. 文件控制块(FCB) 6. 对换(SWAPPING) 7. 系统调用 8. 绝对路径名 9. 特别文件 10.虚设备技术 11.管道 12.中断接收 13.恢复现场 14.页式管理 15.作业步 16.字符流文件 17.通道 18.页面淘汰 19.多道程序设计 20.死锁 21.当前目录 22.快表 23.作业调度 24.原语 25.中断屏蔽 26.地址映射 27.文件目录 28.死锁避免 29.原语 31. CPU 状态 32.虚存

二 . 填空题 1. 分时系统追求的目标是 __及时响应 ___. 2. 用户进程从目态（常态）转换为管态（特态）的唯一途径是 ___ 中断 ________ . 3. 从静态的观点看 , 操作系统中的进程是由程序段、数据和 __ 作业控制块 PCB__ 三部分组成 . 4. 在系统内核中必须包括的处理模块有进程调度、原语管理和 __中断处理 __. 5. 批处理操作系统中 , 作业存在的唯一标志是 _作业控制块 PCB ___. 6. 操作系统中的一种同步机制 , 由共享资源的数据及其在该数据上的一组操作组成 , 该同步机制称为 _管程 ______________ . 7. 在可变分区存储管理中 , 为实现地址映射 , 一般由硬件提供两个寄存器 , 一个是基址寄存器 , 另一个是 _限长寄存器 ___. 8. 联想寄存器（相联存储器）的最重要、最独到的特点是 _按内容并行查找 ___. 9. 在虚拟段式存储管理中 , 若逻辑地址的段内地址大于段表中该段的段长 , 则发生 __ 地址越界 __中断 . 10. 文件系统中若文件的物理结构采用顺序结构 , 则文件控制快 FCB 中关于文件的物理位置应包括 ___ 首块地址和文件长度 _. 11. 在操作系统设计时确定资源分配算法 , 以消除发生死锁的任何可能性 , 这种解决死锁的方法是 __死锁预防 __. 12. 选择对资源需求不同的作业进行合理搭配 , 并投入运行是由 _作业调度算法 ___来完成的. 13. 实时系统应具有两个基本特征 : 及时性和 ___可靠性 ___. 14. 磁带上的文件只能采用 _顺序 ______ 存取方式 . 15. 不让死锁发生的策略可以分成静态和动态的两种 , 死锁避免属于 __动态的 ___. 16. 在 UNIX 系统中 , 文件分成三类 , 即普通文件 , 目录文件和 ___特殊文件 __. 17. 在磁盘调度策略中有可能使 I/O 请求无限期等待的调度算法是 __最短寻道时间优先 18. 进程获得了除CPU 外的所有资源,一旦获得CPU 即可执行,这时进程处于—就绪 _ 状态 . 19. ______________________________________________________ 为实现CPU 与外部设备的并行工作，系统必须引入一通道 ____________________________________ 硬件基础. 20. 操作系统为保证不经文件拥有者授权 , 任何其它用户不能使用该文件所提出的解决措施是 ___文件保密 __. 21. 两个或两个以上程序在计算机系统中同处于开始和结束之间的状态 , 这就称为 __ 并发 ___. 33. 磁盘调度 34. 缓冲技术 36. 进程调度 37. 虚设备 39. 死锁预防 40. 临界资源 — 42. 交换技术 43. 互斥区段时间内只允许一个进程访问的资源，也称为独立资源

操作系统期末试题及答案

操作系统期末试题及答案文件编码（008-TTIG-UTITD-GKBTT-PUUTI-WYTUI-8256）

（答案在后面）一、填空题(每空1分,共10分) 1. 常见的I/O 控制方式有程序I/O 方式、中断 I/O 控制方式、 DMA I/O 控制方式和通道 I/O 控制方式四种。 2. 操作系统向用户提供的两个基本接口是程序接口和用户接口。 3. 若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024 字节，逻辑地址(3082)10转化得到的物理地址是 6154 。 4. 具有多路性、独立性、及时性和交互性特征的操作系统是分时操作系统。 5. 通道用于控制设备控制器与内存之间的信息交换。 6. 事务的最基本特性是。 7. 若盘块大小为4KB ，每个盘块号占4字节，在采用两级索引时允许的最大文件长度为 4GB 。二、单选题(每题2分,共20分) 1. 用磁带作为文件存贮介质时，文件只能组织成 ( )。 A. 顺序文件 B. 链接文件 C. 索引文件 D. 目录文件 2. 一作业8：00到达系统，估计运行时间为1小时，若10：00开始执行该作业，则其响应比是( C )。 A. 2 B. 1 C. 3 D. 3. 文件系统采用多级目录结构后，对于不同用户的文件，其文件名( C )。

A. 应该相同 B. 应该不同 C. 可以相同，也可以不同 D. 受系统约束 4.死锁预防是保证系统不进入死锁状态的静态策略，其解决方法是破坏产生死锁的四个必要条件之一。下列方法中破坏了“循环等待”条件的是（ D ）。 A. 银行家算法 B. 一次性分配策略 C. 剥夺资源法 D. 资源有序分配法 5.进程状态从就绪态到运行态的转化工作是由（ B ）完成的。 A. 作业调度 B. 进程调度 C. 页面调度 D. 设备调度 6.采用缓冲技术的主要目的是（ C ）。 A. 改善用户编程环境 B. 提高CPU的处理速度 C. 提高CPU和设备间的并行程度 D. 实现与设备无关性 7.目录文件所存放的信息是（ D ）。 A. 该目录中所有数据文件目录 B. 某一文件存放的数据信息 C. 某一个文件的文件目录 D. 该目录中所有文件的目录 8.最容易形成很多小碎片的可变分区分配算法是（ D ）。 A. 首次适应算法 B. 循环首次适应算法 C. 最坏适应算法 D. 最佳适应算法 9.用户程序与实际使用的物理设备无关是由（ A ）功能实现的。 A. 设备独立性 B. 设备驱动 C. 虚拟设备 D. 设备分配 10.下面关于顺序文件、链接文件和索引文件的论述中不正确的是（ A ）。 A. 显示链接文件是在每个盘块中设置一个链接指针，用于将该文件所属的所有盘块链接起来 B. 顺序文件必须采用连续分配方式，而链接文件和索引文件则都可采取离散分配方式 C. 顺序文件适用于对诸记录进行批量存取时

算法分析与设计试卷

《算法分析与设计》试卷(A) （时间90分钟满分100分）一、填空题（30分,每题2分）。 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4．.广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5．衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6．Strassen矩阵乘法是利用（ A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是（ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题，最好用（ B ）算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14．下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、输出、确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。

计算机操作系统期末试题及答案西南大学原题

操作系统期末试题一、单项选择题（本大题共20小题，每小题1分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．在配置多道批处理操作系统的计算机系统中(D) A．用户可联机、调试自己的程序B．允许用户直接干预作业的执行 C．能对外部事件实时响应D．允许多个作业同时使用不同的外围设备 2．UNIX操作系统是一个(A) A．交互式分时操作系统B．多道批处理操作系统C．实时操作系统D．分布式操作系统 3．若操作系统管理的某用户程序当前正占有中央处理器，该用户程序欲读磁盘上的文件信息，那么用户程序中相应的指令应该是(D) 1 全国2010年4月自学考试操作系统概论试题

A．启动I/O指令B．等待I/O指令 C．转移指令D．访管指令 4．当一次系统调用功能完成后，中央处理器的工作状态应(C) A．保持管态B．保持目态 C．从管态转换成目态D．从目态转换成管态5．分布式操作系统的特点是(C) A．资源共享B．资源地理位置分散C．资源位置透明D．多个用户的程序并行运行 6．引入进程的原因是(B) A．提高资源的利用率和控制程序的执行 B．提高资源的利用率和正确描述程序的执行情况C．提高程序的执行速度和控制程序的执行 D．提高程序的执行速度和正确描述程序的执行情况7．进程有三种基本状态，可能的状态转换是(A) A．就绪态到运行态、等待态到就绪态、运行态到等待态 B．就绪态到运行态、就绪态到等待态、等待态到运 2 全国2010年4月自学考试操作系统概论试题

全国2010年4月自学考试操作系统概论试题 3 行态 C ．就绪态到运行态、等待态到就绪态、等待态到运行态 D ．运行态到就绪态、就绪态到等待态、等待态到运行态 8．处理器不能．．直接访问的存储器是( D ) A ．寄存器 B ．高速缓冲存储器 C ．主存储器 D ．辅助存储器 9．断电停机后，存储信息随之消失的存储器是( C ) A ．磁盘 B ．磁带 C ．主存储器 D ．U 盘 10．处于运行状态的操作系统程序应放在( C ) A ．寄存器中 B ．高速缓冲存储器中 C ．主存储器中 D ．辅助存储器中 11．对操作系统的文件系统而言，一个源程序、一批数据、一篇文章或一张图片等都可以被称为文件，只要它是( C ) A ．连续分布在一片磁盘区域中的信息集合

操作系统期末考试试题和标准答案及评分标准汇编

《操作系统》试题（A卷）（考试时间：90分钟）一、选择题（共20分，每小题1分） 1．（）不是基本的操作系统。 A.批处理操作系统 B.分时操作系统 C.实时操作系统 D.网络操作系统 2．现代OS具有并发性和共享性，是（）的引入导致的。 A.单道程序 B. 磁盘 C. 对象 D.多道程序 3．一般来说，为了实现多道程序设计，计算机最需要（）。 A.更大的内存 B.更多的外设 C.更快的 CPU D.更先进的终端 4．在下面的I/O控制方式中，需要CPU干预最少的方式是（）。 A.程序I/O方式 B.中断驱动I/O控制方式 C.直接存储器访问DMA控制方式 D.I/O通道控制方式 5．在进程状态转换时，下列（）转换是不可能发生的。 A.就绪态→运行态 B.运行态→就绪态 C.运行态→阻塞态 D.阻塞态→运行态 6．一个进程执行过程中不可能对应( )。 A.一个PCB B.一个JCB C.多个PCB D.一个程序 7．进程调度又称为低级调度，其主要功能是( )。 A.选择一个作业调入内存 B.选择一个主存中的进程调出到外存 C.选择一个外存中的进程调入到主存 D.将一个就绪的进程投入运行 8．如果允许不同用户的文件可以具有相同的文件名，通常采用（）来保证按名存取的安全。 A.重名翻译机构 B.建立索引表 C.建立指针 D.多级目录结构 9．文件控制块不包括（）。 A.文件名 B.文件访问权限说明 C.文件物理位置信息 D.磁盘坏块信息10．为了提高设备分配的灵活性，用户申请设备时应指定（）号。 A.设备类相对 B.设备类绝对 C.相对 D.绝对 11．若进程P一旦被唤醒就能够投入运行，系统可能为( )。 A.在分时系统中，进程P的优先级最高。

算法设计与分析试卷(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 为3阶方阵，数 = 3，|A | =2，则 | A | =（）. A ．54； B ．-54； C ．6； D ．-6. 解. .54227)3(33-=?-=-==A A A λλ 所以填: B. 2、设A 为n 阶方阵，λ为实数，则|λA |=（） A 、λ|A |； B 、|λ||A |； C 、λn |A |； D 、|λ|n |A |. 解. |λA |=λn |A |.所以填: C. 3.设矩阵()1,2,12A B ?? ==- ??? 则AB =（）. 解. ().24121,221???? ??--=-???? ??=AB 所以填: D. A. 0； B. ()2,2-； C. 22?? ?-??； D. 2142-?? ?-?? . 4、123,,a a a 是3维列向量，矩阵123(,,)A a a a =.若|A |=4，则|-2A |=（）. A 、-32； B 、-4； C 、4； D 、32. 解. |-2A |=(-2)3A =-8?4=-32. 所以填: D. 5.以下结论正确的是（）. A .一个零向量一定线性无关； B .一个非零向量一定线性相关； C .含有零向量的向量组一定线性相关； D .不含零向量的向量组一定线性无关. 解. A .一个零向量一定线性无关；不对,应该是线性相关. B .一个非零向量一定线性相关；不对,应该是线性无关. C .含有零向量的向量组一定线性相关；对. D .不含零向量的向量组一定线性无关. 不对, 应该是:不能判断. 所以填: C. 6、 1234(1,1,0,0),(0,0,1,1),(1,0,1,0),(1,1,1,1),αααα====设则它的极大无关组为( ) A 、 12,; αα B 、 123,, ;ααα C 、 124,, ;ααα D 、1234,, ,αααα

(完整版)操作系统期末试卷(含答案)

一、选择题 1、在现代操作系统中引入了（），从而使并发和共享成为可能。 A.单道程序 B. 磁盘 C. 对象 D.多道程序 2、( )操作系统允许在一台主机上同时连接多台终端，多个用户可以通过各自的终端同时交互地使用计算机。 A.网络 B.分布式 C.分时 D.实时 3、从用户的观点看，操作系统是（）。 A. 用户与计算机硬件之间的接口 B.控制和管理计算机资源的软件 C. 合理组织计算机工作流程的软件 D.计算机资源的的管理者 4、当CPU处于管态时，它可以执行的指令是（）。 A. 计算机系统中的全部指令 B. 仅限于非特权指令 C. 仅限于访管指令 D. 仅限于特权指令 5、用户在程序中试图读取某文件的第100个逻辑块时，使用操作系统提供的（）接口。 A. 系统调用 B.图形用户接口 C.原语 D.键盘命令 6、下列几种关于进程的叙述，（）最不符合操作系统对进程的理解？ A.进程是在多程序并行环境中的完整的程序。 B.进程可以由程序、数据和进程控制块描述。 C.线程是一种特殊的进程。 D.进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。 7、当一个进程处于（）状态时，称其为等待（或阻塞）状态。 A. 它正等待中央处理机 B. 它正等待合作进程的一个消息 C. 它正等待分给它一个时间片 D. 它正等待进入内存 8、一个进程释放一种资源将有可能导致一个或几个进程（）。 A.由就绪变运行 B.由运行变就绪 C.由阻塞变运行 D.由阻塞变就绪 9、下面关于线程的叙述中，正确的是（）。 A.不论是系统支持线程还是用户级线程，其切换都需要内核的支持。 B.线程是资源的分配单位，进程是调度和分配的单位。 C.不管系统中是否有线程，进程都是拥有资源的独立单位。 D.在引入线程的系统中，进程仍是资源分配和调度分派的基本单位。 10、设有3个作业，它们同时到达，运行时间分别为T1、T2和T3,且T1≤T2≤T3，若它们在单处理机系统中按单道运行，采用短作业优先调度算法，则平均周转时间为（）。 A. T1+T2+T3 B. (T1+T2+T3)/3 C. T1+T2/3+2*T3/3 D.T3/3+2*T2/3+T1 11、在下面的I/O控制方式中，需要CPU干预最少的方式是（）。 A．程序I/O方式B．中断驱动I/O控制方式C．直接存储器访问DMA控制方式D．I/O通道控制方式 12、有m个进程共享同一临界资源，若使用信号量机制实现对一临界资源的互斥访问，则

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

湖南科技学院二○年学期期末考试信息与计算科学专业年级《算法设计与分析》试题考试类型:开卷试卷类型: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

北京邮电大学2009年操作系统期末试卷

北京邮电大学2008——2009学年第一学期《操作系统》期末考试试题（A） 1.FILL IN BLANKS (10 points) 1.1 A _trap___ is a software-generated interrupt caused either by an error or by a specific request from a user program that an operating-system services be performed. 1.2 A ______ is used in Unix systems to notify a process that a particular event has occurred. 1.3 To manage the process executing, OS records the state and other information (e.g. the priority) of the process in . 1.4 The scheduling criteria include CPU utilization, throughput, turnaround time, waiting time, and response time .

1.5 For n concurrent processes that mutual exclusively use some resources, the code segmentations, in which the processes access the resources, are called deadlock . 1.6. The ___visual memory___ scheme enables users to run programs that are larger than actual physical memory, this allows the execution of a process that is not completely in memory. 1.7. The __FIFO___ page replacement algorithm associates with each page the time when that page was brought into memory. When a page must be replaced, the oldest page is chosen. 1.8The file system resides permanently on , which is designed to hold a large amount of data permanently. 1.9The file system itself is generally composed of many different levels, including the logical file system, the file-organization module, the and the I/O control. 1.10 T he kernel’s I/O subsystem provides numero us services. Among these are I/O scheduling, , caching, spooling, device reservation, and error handling, and name translation. 2.CHOICE ( 10 points ) 2.1 _____ operating systems have well defined, fixed time constraints. Processing must be done within the defined constrains, or the system will fail. A. Multimedia B. Real-time C. Clustered D. Network 2.2 Which one of the following OS is implemented based on microkernel structure? _____

操作系统期末测试题2套带答案

中央广播电视大学第二学期“开放本科”期末考试计算机专业计算机操作系统试题、选择题(选择一个正确的答案的代号填入括号中。每空 2 分，共50 分) 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 .在动态分E存储管理中的紧凑(移动)技术可以()。 A .集中空闲区 B .增加主存容量 C. 缩短访问周期 D .加速地址转换 7. 在请求分页存储管理中，若采用FIFO 页面替换算法，则当分配的页面数增加时，缺页中断次数( )。 A. 减少 B.增加 C.无影响 D ?可能增加也可能减少 8. 用V 操作唤醒一个等待进程时，被唤醒进程的状态转换为( )。 A. 等待 B. 就绪 C. 运行 D .完成 9. 下面对进程的描述中，错误的是( )。 A.进程是动态的概念 B.进程执行需要处理饥 C.进程是有生命期的 D ?进程是指令的集合 10. 作业执行中要不断启动外部设备，通常把存储介质上的信息读入主存或者把主存中的信息送到存储介质上的操作称为( )操作。 A. 输入输出 B. 启动外设 C.访问主存 D .作业执行 11 . CPU 与通道可以并行执行，并能通过( )实现彼此之间的通信。 A. I／O 指令 B. I／O 中断 C. 操作员 D. I／O 指令和I／O 中断 12 .分布式操作系统与网络操作系统本质上的不同在于( )。

线性代数期末考试试卷+答案合集

×××大学线性代数期末考试题一、填空题（将正确答案填在题中横线上。每小题2分，共10分） 1. 若02 2 1 50 1 31 =---x ，则=χ__________。 2．若齐次线性方程组??? ??=++=++=++0 00321 321321x x x x x x x x x λλ只有零解，则λ应满足。 3．已知矩阵n s ij c C B A ?=)(，，，满足CB AC =，则A 与B 分别是阶矩阵。 4．矩阵??? ? ? ??=32312221 1211 a a a a a a A 的行向量组线性。 5．n 阶方阵A 满足032 =--E A A ，则=-1A 。二、判断正误（正确的在括号内填“√”，错误的在括号内填“×”。每小题2分，共10分） 1. 若行列式D 中每个元素都大于零，则0?D 。（） 2. 零向量一定可以表示成任意一组向量的线性组合。（） 3. 向量组m a a a ，，， 21中，如果1a 与m a 对应的分量成比例，则向量组s a a a ，，， 21线性相关。（） 4. ? ? ??? ???? ???=010********* 0010 A ，则A A =-1。（） 5. 若λ为可逆矩阵A 的特征值，则1 -A 的特征值为λ。 ( ) 三、单项选择题 (每小题仅有一个正确答案，将正确答案题号填入括号内。每小题2分，共10分) 1. 设A 为n 阶矩阵，且2=A ，则=T A A （）。 ① n 2 ② 1 2 -n ③ 1 2 +n ④ 4 2. n 维向量组 s ααα，，， 21（3 ≤ s ≤ n ）线性无关的充要条件是（）。 ① s ααα，，， 21中任意两个向量都线性无关 ② s ααα，，， 21中存在一个向量不能用其余向量线性表示 ③ s ααα，，， 21中任一个向量都不能用其余向量线性表示

中山大学操作系统原理A卷试题答案

2008操作系统A卷参考答案班级 __________ 姓名____________ 学号________ 成绩_________ 一、术语解释（5个，共20分） 1、内核：实现操作系统的最基本功能、常驻内容并要求CPU在核心态方式下运行的代码和相关数据结构。 2、信号量：操作系统内容定义和管理的一种特殊数据结构，提供了初始化、增值和减值等操作供进程调用，以实现进程互斥或同步。 3、临界区：两个或多个进程中，对应的程序中各存在一段访问共享数据的代码块，设为CS1、CS2、。。。，这些代码块中，若有某个进程执行其中一个（设CSi）,则其它进程执行其它相应代码块只能在CSi完成后才能开妈执行。具有这种要求的代码块称为临界区 4、线程：进程中的一个独立的调度执行单位。多线程技术中，同一进程中可以有多个独立的调度执行单位，并且可以并发执行。 5、逻辑地址：程序设计员在程序中使用的地址。二、简答题（5题，共30分） 6、系统调用的过程中，控制的转移步骤如何？答：CPU控制权在用户态的进程中，进程执行陷入或软中断指令硬件执行中断响应动作进入内核，CPU控制权在核心态的操作系统内核代码中，执行系统调用服务程序,并可能进行进程调度，选择下一个可运行的进程恢复可运行进程的上下文CPU 控制权又交给在用户态的进程， 7、与层次结构比较，微内核结构的主要优缺点是什么？答：优点有接口一致性、系统安全性高、功能扩展灵活性、可移植性高、适用于分布式环境。缺点是效率较低。 8、与多进程技术相比，多线程技术有哪些优点？答：同一进程的多个线程共享进程的资源，因此与进程相比，线程占用的资源极少；创建/撤消线程更快；同一进程的多个线程同属一个地址空间，可以使用共享变量直接通信；用户级线程还不需内核管理，减少了内核的开销。 9、用Test_And_Set指令如何实现互斥？ 10、文件打开过程主要工作及步骤答：1搜索文件目录，以获取该文件控制信息；2检查操作权限；3分配活动文件表的表项和打开文件表的表项，填入相应的文件控制信息；分配必要的缓冲区；4返回打开文件表的表项指针（文件句柄），供进程以后读写文件。三、应用分析题（共4题，共40分） 11、（10分）k读者-写者问题：有一个文件F被多个进程读取或修改，其中一批进程只读取F，另一些进程只修改F。为了保证系统响应时间，规定最多只能有k个进程同时操作F。试用信号量及P、V操作实现读者与写者的同步。答: Semaphore wr=1;

算法分析期末试题集答案

线性代数期末试题及答案

计算机操作系统3套期末考试题及答案

最新计算机操作系统期末考试题及答案

2015年算法分析与设计期末考试试卷B卷

北京大学操作系统期末试题有答案

操作系统期末试题及答案

算法分析与设计试卷

计算机操作系统期末试题及答案西南大学原题

操作系统期末考试试题和标准答案及评分标准汇编

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

线性代数期末考试试题

(完整版)操作系统期末试卷(含答案)

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

北京邮电大学2009年操作系统期末试卷

操作系统期末测试题2套带答案

线性代数期末考试试卷+答案合集

中山大学操作系统原理A卷试题答案