算法设计与分析考试复习题(北京邮电大学,北京地区适用)

《算法设计与分析》实验与复习题

第一章引论

习题1 写一个通用方法用于判定给定数组是否已排好序。

算法实例：

Algorithm compare(a,n)

Begin

J=1;

While (j

If j=n then return true

Else

While (j=a[j+1]) do j=j+1;

If j=n then return true else return false end if

End if

end

习题1 写一个算法交换两个变量的值不使用第三个变量。

算法实例：x=x+y; y=x-y; x=x-y;

习题1-3 已知m,n为自然数，其上限为k（由键盘输入，1<=k<=109）,找出满足条件(n2-mn-m2)2=1 且使n2+m2达到最大的m、n。

算法实例：

m:=k; flag:=0;

repeat

n:=m;

repeat

l:=n*n-m*n-m*n;

if (l*l=1) then flag:=1 else n:=n-1;

until (flag=1) or (n=0)

if n=0 then m:=m-1

until (flag=1) or (m=0);

第二章基础知识

习题2-1 求下列函数的渐进表达式：

3n 2+10n ; n 2/10+2n ; 21+1/n ; log n 3; 10 log3n 。

解答： 3n 2+10n=O （n 2）， n 2/10+2n =O （2n ）， 21+1/n=O （1）， log n 3=O （log n ），10 log3n =O （n ）。

习题2-2 说明O (1)和 O (2)的区别。

习题2-3 照渐进阶从低到高的顺序排列以下表达式：!n ，

3/22,2,20,3,log ,4n n n n n 。

解答：照渐进阶从低到高的顺序为：!n 、 3n

、 24n 、23

n 、20n 、log n 、2

习题2-4

（1） 假设某算法在输入规模为n 时的计算时间为n n T 23)(?=。在某台计算机

上实现并完成该算法的时间为t 秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t 秒内能解输入规模为多大的问题？

（2） 若上述算法的计算时间改进为2)(n n T =，其余条件不变，则在新机器上用

t 秒时间能解输入规模多大的问题？

（3） 若上述算法的计算时间进一步改进为8)(=n T ,其余条件不变，那么在新机

器上用t 秒时间能解输入规模多大的问题？

解答：

（1） 设新机器用同一算法在t 秒内能解输入规模为1n 的问题。因此有

64/23231n n t ?=?=，解得61+=n n 。

（2） n n n n 8641221==>=。

（3） 由于=)(n T 常数，因此算法可解任意规模的问题。

习题2-5 XYZ 公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC 公司同类产品的100倍。对于计算复杂性分别为n ，2n ，3n 和!n 的各算法，

若用ABC 公司的计算机能在1小时内能解输入规模为n 的问题，那么用XYZ 公司的计算机在1小时内分别能解输入规模为多大的问题？ 解答：

n n 100='。

n n n n 1010022='=>='。 n n n n 64.41001003

33==>

='。

64.6100log !100!+=+<'=>='n n n n n 。

习题2-6对于下列各组函数)(n f 和)(n g ，确定))(()(n g O n f =或

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

（1）5log )(;log )(2+==n n g n n f 。 （2）n n g n n f ==)(;log )(2。 （3）n n g n n f 2log )(;)(==。 （4）n n g n n n n f log )(;log )(=+=。 （5）10log )(;10)(==n g n f 。 （6）n n g n n f log )(;log )(2==。 （7）2100)(;2)(n n g n f n ==。 （8）n n n g n f 3)(;2)(==。

解答：

（1）)5(log log 2

+=n n θ。 （2）)(log 2n O n =。 （3）)(log 2

n n Ω=。 （4）)(log log n n n n Ω=+。 （5）)10(log 10θ=。 （6）)(log log 2

n n Ω=。

（7）)100(22n n Ω=。 （8）)3(2n n O =。

习题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为))((n f θ，则该算法在最坏情况下所需的计算时间为))((n f Ω。

证明：

)

(),()(),()

,(max )(),()()(max **N T I N T I P I N T I N T I P I N T I P N T N

N

N N

D I D I D I D I avg ==='≤

=

∑∑∑∈∈∈'∈

因此，))(()))((())(()(max n f n f N T N T avg Ω=Ω=Ω=θ。

习题2-7 求解下列递归方程: s 0=0

s n =2s n -1+2n -1 解答：

步骤: 1应用零化子化为齐次方程，

2解此齐次方程的特征方程， 3由特征根构造一般解，

4再由初始条件确定待定系数，得到解为：

习题2-8 求解下列递归方程:

01122844n

n n h h h h h

--=??

=?

?=-? 解 h n =2n +1(n +1)

第三章 递归与分治策略

(1)21

n n s n =-+

习题3-1 下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明。

public static int binarySearch1(int []a,int x,int n)

{

int left=0; int right =n-1;

while (left<=right) {

int middle = ( left + right )/2;

if ( x == a[middle]) return middle;

if ( x> a[middle]) left = middle;

else right = middle;

return -1;

}

public static int binarySearch2(int []a, int x, int n)

{

int left = 0; int right = n-1;

while ( left < right-1 ) {

int middle = ( left + right )/2;

if ( x < a[middle]) right = middle;

else left = middle;

}

if (x == a[left]) return left;

else return -1

}

public static int binarySearch3(int []a, int x, int n)

{

int left = 0; int right = n-1;

while ( left +1 != right) {

int middle = ( left + right)/2;

if ( x>= a[middle]) left = middle;

else right = middle;

}

if ( x == a[left]) return left ;

else return -1;

}

public static int binarySearch4(int []a, int x, int n)

{

if (n>0 && x>= a[0]) {

int left = 0; int right = n-1;

while (left < right ) {

int middle = (left + right )/2;

if ( x < a[middle]) right = middle -1 ;

else left = middle;

}

if ( x == a[left]) return left;

}

return -1;

}

public static int binarySearch5(int []a, int x, int n) {

if ( n>0 && x >= a[0] ) {

int left = 0; int right = n-1;

while (left < right ) {

int middle = ( left + right +1)/2;

if ( x < a[middle]) right = middle -1;

else left = middle ;

}

if ( x == a[left]) return left;

}

return -1;

}

public static int binarySearch6(int []a, int x, int n) {

if ( n>0 && x>= a[0]) {

int left = 0; int right = n-1;

while ( left < right) {

int middle = (left + right +1)/2;

if (x < a[middle]) right = middle – 1;

else left = middle + 1;

}

if ( x == a[left]) return left ;

}

return -1;

}

public static int binarySearch7(int []a, int x, int n) {

if ( n>0 && x>=a[0]) {

int left = 0; int right = n-1;

while ( left < right) {

int middle = ( left + right + 1)/2;

if ( x < a[middle]) right = middle;

else left = middle;

}

if ( x == a[left]) return left;

}

return -1;

}

分析与解答：

算法binarySearch1数组段左右游标left和right的调整不正确，导致陷入死循环。

算法binarySearch2数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。

算法binarySearch3数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。

算法binarySearch4数组段左右游标left和right的调整不正确，导致陷入死循环。

算法binarySearch5正确，且当数组中有重复元素时，返回满足条件的最右元素。

算法binarySearch6数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。

算法binarySearch7数组段左右游标left和right的调整不正确，导致当x=a[n-1]时陷入死循环。

习题3-2 设]1

a是已排好序的数组。请改写二分搜索算法，使得当搜

:0[

n

索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

分析与解答：

改写二分搜索算法如下：

public static boolean binarySearch(int []a, int x, int left, int right, int []ind)

{

int middle;

while ( left <= right ) {

middle = (left + right)/2;

if (x == a[middle]) { ind[0]=ind[1]=middle; return true;}

if (x > a[middle]) left = middle + 1;

else right = middle -1;

}

ind[0] = right; ind[1]=left;

return false;

}

返回的ind[1]是小于x的最大元素位置，ind[0]是大于x的最小元素的位置。

习题3-3 设]1:0[-n a 是有n 个元素的数组，)11(-≤≤n k k 是非负整数。试设计一个算法讲子数组]1:0[-k a 与]1:[-n k a 换位。要求算法在最坏情况下耗时为

)(n O ，且只用到)1(O 的辅助空间。

分析与解答：

算法： 三次求反法

Algorithm exchange(a, k, n); Begin

Inverse(n,0,k-1); inverse(n,k,n-1)； inverse （n,0,n-1） End.

Algorithm inverse(a, i, j); Begin

h=12j i -+??

????

; For k=0 to h-1 do

Begin x=a[i+k]; a[i+k]=a[j-k]; a[j-k]= x end ; end

习题3-4 如果在合并排序算法的分割步中，讲数组]1:0[-n a 划分为

??n 个

子数组，每个子数组中有)(n O 个元素。然后递归地对分割后的子数组进行排序，最后将所得到的

??n 个排好序的子数组合并成所要求的排好序的数组

]1:0[-n a 。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。

分析与解答：

实现上述策略的合并排序算法如下：

public static void mergesort(int []a, int left ,int right) {

if (left < right ) { int j = (int) Math.sqrt(right –left+1); if (j>1) { for (int i=0; i

}

其中，算法mergeall 合并n 个排好序的数组段。在最坏情况下，算法mergeall 需要)log (n n O 时间。因此上述算法所需的计算时间)(n T 满足：

??

?>≤=1

)

(1)

1()(n n T n n O n T

此递归式的解为：)log ()(n n O n T =。

习题3-5 设k S S S ,...,21是整数集合，其中每个集合)1(k i S i ≤≤中整数取值范围是n ~1，且n S k

i i =∑=1，试设计一个算法，在)(n O 时间内将k S S S ,...,21分别

排序。

分析与解答：

用桶排序或基数排序算法思想可以实现整数集合排序。

习题6 设]1:0[-n X 和]1:0[-n Y 为两个数组，每个数组中还有n 个已排好序的数。试设计一个)(log n O 时间的算法，找出X 和Y 的2n 个数的中位数。 分析与解答：

（1） 算法设计思想

考虑稍一般的问题：设]:[11j i X 和]:[22j i Y 是X 和Y 的排序好的子数组，且长度相同，即2211i j i j -=-。找出这两个数组中)1(211+-j i 个数的中位数。

首先注意到，若][][21j Y i X ≤，则中位数

median

满足

][][21j Y m e d i a n i X ≤≤。同理若][][21j Y i X ≥，则][][12i X median j Y ≤≤。 设

2

/)(111j i m +=，

2

/)(222j i m +=，则

2

/)(2/)()(2/)(2/)(2/)(221121222111221121i j i j i i i j i i j i j i j i m m -+-++=-++-+=+++=+

由于2211i j i j -=-，故221122112/)(2/)(i j i j i j i j -=-=-+-。 因此21222112112121j i i j i i j i i j i i m m +=-++=+==++=+。

当][][21m Y m X =时，][][21m Y m X median ==。

当][][21m Y m X <时，设1m edia n 是]:[11j m X 和]:[22m j Y 的中位数，则

1median median =。

当][][21m Y m X >时，设2m edian 是]:[11m i X 和]:[22j m Y 的中位数，类似地有2median median =。

通过以上讨论，可以设计出找出两个子数组]:[11j i X 和]:[22j i Y 的中位数median 的算法。

（2） 设在最坏情况下，算法所需的计算时间为)2(n T 。由算法中1m 和2m 的选

取策略可知，在递归调用时，数组X 和Y 的大小都减少了一半。因此，

)2(n T 满足递归式：

??

?≥+<=c

n O n T c

n O n T )

1()()

1()2( 解此递归方程可得：)(log )2(n O n T =。

习题3-6 Gray 码是一个长度为n 2的序列。序列中无相同元素，每个元素都是长度为n 位的（0，1）串，相邻元素恰好只有1位不同。用分治策略设计一个算法，对任意的n 构造相应的Gray 码。

分析与解答：

考察3,2,1=n 的简单情形。

设n 位Gray 码序列为)(n G 以相反顺序排列的序列为)(1n G -。从上面的简单情形可以看出)(n G 的构造规律：)(1)(0)1(1n G n G n G -=+。

注意到)(n G 的最后一个n 位串与)(1n G -的第1个n 位串相同，可用数学归纳法证明)(n G 的上述构造规律。由此规律容易设计构造)(n G 的分治法如下。 public static void Gray(int n) {

if ( n == 1) { a[1] = 0; a[2] = 1; return; } Gray(n-1);

for ( int k = 1<< ( n - 1), i = k; i > 0; i--) a[2*k-i+1]=a[i] + k; }

上述算法中将n 位（0，1）串看做是二进制整数，第i 个串存储在][i a 中。 完成计算之后，由out 输出Gray 码序列。 public static void out(int n) {

int m=1<

for (int i=1; i<=m; i++) { String str=Integer.toBinaryString(a[i]); int s=str.length(); for ( int j=0; j

System.out.println(); }

第四章 动态规划

习题4-1 设计一个)(2n O 时间的算法，找出由n 个数组成的序列的最长单调递增子序列。 分析与解答：

用数组]1:0[-n b 记录以n i i a <≤0],[为结尾元素的最长递增子序列的长度。序列a 的最长递增子序列的长度为]}[{max 0i b n

i <≤。易知，][i b 满足最优子结构性

质，可以递归地定义为：

1]}[{max ][,

1]0[]

[][0+==≤<≤k b i b b i a k a i k

据此将计算][i b 转化为i 个规模更小的子问题。

按此思想设计的动态规划算法描述如下： public static int LISdyna() {

int i, j, k;

for ( i=1, b[0]=1; i

return maxL(n); }

static int maxL(int n) {

int temp=0;

for ( int i= 0; i temp) temp=b[i]; return temp; }

上述算法LISdyna 按照递归式计算出]1:0[-n b 的值，然后由maxL 计算出序列a 的最长递增子序列的长度。从算法LISdyna 的二重循环容易看出，算法所需的计算时间为)(2n O 。

习题4-2 考虑下面的整数线性规划问题：

b

x

a x c n

i i

i n

i i

i ≤∑∑==1

1

max i x 为非负整数，n i ≤≤1

试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。

分析与解答：

该问题是一般情况下的背包问题，具有最优子结构性质。 设所给背包问题的子问题：

j

x a

x c i

k k k

i

k k

k ≤∑∑==1

1

max

的最优值为),(j i m ，即),(j i m 是背包容量为j ，可选择物品为1，2，…，i 时背包问题的最优值。由背包问题的最优子结构性质，可以建立计算),(j i m 的递归式

如下：

??

?<≤-≥+--=i

i i i a j j i m a j c a j i m j i m j i m 0)

,1(}

),(),,1(max{),(

0,),();0,(),0(<-∞==j j i m i m j m 。

按此递归式计算出的),(b n m 为最优值。算法所需的计算时间为)(nb O 。

习题4-3 给定一个由n 行数字组成的数字三角形如图3-2所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

分析与解答：

记f(u ij )为至ij 元素的最大路径值, a ij ：元素(i,j)之值。 递归式: F(u ij )=max{f(u i-1,j )+a ij , f(u i-1,j+1)+a ij } (i=1,…n ， j=1,…i)

经过一次顺推，便可求出从顶至底n 个数的n 条路径（这n 条路径为至底上n 个数的n 个最大总和的路径），求出这n 个总和的最大值，即为正确答案。 数据结构:

a[i,j].val: 三角形上的数字，

a[i,j].f: 由（1，1）至该点的最大总和路径的总和值。

type node=record val, f: integer; end;

var a:array [1.. maxn, 1..maxn] of node; procedure findmax; begin

a [1,1]. f :=a[1,1].val; for i:=2 to n do for j:=1 to i do begin

a[i,j]. f:=-1;

if (j<>1) and (a [i-1,j-1].f+a[i,j].val > a [i,j].f)

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 数字三角形

then a[i,j]. f:=a [i-1,j-1]. f+a[i,j].val;

if (j<>i) and(a [i-1,j].f+a[i,j].val > a[i,j].f) then a[i,j]. f:=a[i-1,j]. f+a[i,j]. val end;

max:=1;

for i:=2 to n do

if a[n,i]. f> a[n, max] .f then

max:=i;

writeln (a [n, max]. f)

end;

第五章 贪心算法

习题5-1 特殊的0-1背包问题

若在0-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列。对这个特殊的0-1背包问题，设计一个有效算法找出最优解，并说明算法的正确性。 分析与解答：

设所给的输入为n i W i i ≤≤>>>1,0,0,0νω。不妨设n ωωω≤≤≤<...021。由题意知

0...21>≥≥≥n ννν。由此可知

1

1

++≥

i i i i ωνων，11-≤≤n i 贪心选择性质： 当W >1ω时问题无解。

当W ≤1ω时，存在0-1背包问题的一个最优解},...,2,1{n S ?使得S ∈1。

事实上，设},...,2,1{n S ?使0-1背包问题的一个最优解，且S ?1。对任意S i ∈，取

}{}1{i S S i -?=，则i S 满足贪心选择性质的最优解。

习题5-2 Fibonacci 序列的Huffman 编码

试证明：若n 个字符的频率恰好是前n 个Fibonacci 数，用贪心法得到它们的Huffman 编码树一定为一棵“偏斜树”。

分析与解答： 频率恰好是前8个Fibonacci 数的哈夫曼编码树如图所示。

图 哈夫曼编码树

证明：n 个字符的频率恰好是前n 个Fibonacci 数，则相应的哈夫曼编码树自底向上第

i 个内结点中的数为

∑=i

k k

f

。用数学归纳法容易证明

20

+=<∑i i

k k

f f

。

因f 1=1,f 2=1,f 3=2,可知i =1时，上述结论成立。 设对i+2上述结论成立，即有

20

+=<∑i i

k k

f f

， 因

1

32111

1

i

i i i i k i k k k f f f f f f +++++===+>+=∑∑，

说明对i+3上述结论成立.

该性质保证了频率恰好是前n 个Fibonacci 数的哈夫曼编码树具有“偏斜树”形状。

习题5-3 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。

分析与解答：

设所给的n 个活动为1，2，…，n ，它们的开始时间和结束时间分别为][i s 和][i f ，

n i ~1=，且][...]2[]1[n f f f <<<。

可以将n 个活动1，2，…，n 看作实直线上的n 个半闭活动区间n i i f i s ~1]),[],[[=。所讨论的问题实际上是求这n 个半闭区间的最大重叠数。因为重叠的活动区间所相应的活动是互不相容的。若这n 个活动区间的最大重叠数为m ，则这m 个重叠区间所对应的活动互不相容，因此至少安排m 个会场来容纳这m 个活动。

为了有效地对这n 个活动进行安排，首先将n 个活动区间的2n 个端点排序。然后，用扫描算法，从左到右扫描整个实直线。在每个事件点处（即活动的开始时刻或结束时刻）作会场安排。当遇到一个开始时刻][i s ，就将活动i 安排在一个空闲的会场中。遇到一个结束时候][i f ，就将活动i 占用的会场释放到空闲会场栈中，以备使用。经过这样一遍扫描后，最多安排了m 个会场（m 是最大重叠区间数）。因此所作的会场安排是最优的。上述算法所需的计算时间主要用于对2n 个区间端点的排序，这需要)log (n n O 计算时间。

具体算法描述如下。

public static int greedy(point []x)

int sum=0, curr=0, n=x.length;

MergeSort.mergeSort(x);

for (int i=0; i

if (x[i].leftend()) curr++;

else curr--;

//处理x[i]=x[i+1]的情况

if (( i == n-1∣∣x[i].compareTo(x[i+1])<0)&& curr>sum) sum=curr;

}

return sum;

}

习题5-4 假设要在m个会场里安排一批活动，并希望使用尽可能多地安排活动。设计一个有效的贪心算法进行安排。

Algorithm greedy(s,f,m,n);

Input s[1:n], f[1:n];

Output x[1:m, 1:n];

Begin

对数组s和f中的2n个元素排序存入数组y[1:2n]中；

空闲栈清空；d数组所有元素置初值0；

For i=1 to 2n do

Begin

If 元素y[i] 原属于s then

If 空闲栈不空then

取出栈顶场地j; d[j]=d[j]+1; y[i] 存入x[j, d[j] ];

If 元素y[i] 原属于f then

设其相应的s 存于x[j,k] 中，将j存入空闲栈中；

End

For i= 1 to m do

For j=1 to d[j] do

Output x[i,j];

End

习题5-5 删数问题

问题描述

k 个数字后，剩下的数字按原次序排列组成一个新的给定n位正整数a，去掉其中任意n

正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。

分析与解答：

贪心策略：最近下降点优先。 public static void delek(String a) { int i,m=a.length(); if ( k>= m) {System.out.println(0); return;} while (k>0) { for (i=0; (i1 && a.charAt(0)==’0’) a=a.Remove(0,1); System.out.println(a); }

第六章 回溯法

习题6-1 子集和问题

子集和问题的一个实例,A sum <>。其中，12{,,...,}n A a a a =是一个正整数的集合，sum 是一个正整数。子集和问题判定是否存在A 的一个子集A 1，使得1

a A a sum ∈=∑。

试设计一个解子集和问题的回溯法。

分析与解答：

设计解子集和问题的回溯法如下。

Algorithm subset-sum begin

For j=1 to n do Begin

sp=0; t=sum; i=j; finish=false; repeat

if t>=a[i] then

begin

sp=sp+1；s[sp]=i; t=t-a[i]; if t=0 then i=n; end; i=i+1;

while i>n do if sp>1 then begin

if t=0 then out; t=t+a[s[sp]]; i=s[sp]+1; sp=sp-1 end

else

begin finish=true; i=1 end

until finish

end

end

习题6-2 中国象棋的半个棋盘如图所示，马自左下角往右上角跳。规定只许向右跳，不许向左跳，计算所有的行走路线。

Algorithm chess

Begin

top=0; y0=0; x0=0; di=1; r=0;

push;

repeat

pop;

while di<=4 do

begin

g=x0+x[di]; h=y0+y[di];

if (g=8) and (h=4) then out

else begin di=di+1；push; x0=g; y0=h; di=1 end

end

until empty

end

algorithm push

begin

top=top+1；sx[top]=x0; sy[top]=y0; d[top]=di;

end

algorithm pop

begin

x0=sx[top]; y0=sy[top]; di =d[top]; top=top－1；

end

习题6-3. 在n个连成排的方格内填入R或B，但相邻连个方格内不能都填R。计算所有可能的填法。

Algorithm Red-Black;

Begin

For i=1 to n do b[i]=0;

T=1;

Repeat

b[t]=b[t]+1 ;

if b[t]>2 then {回溯}

begin b[t]=0 ; t=t-1 ; end

else begin

if b[t]=2 then a[t]= ‘B’

else if a[t-1]=’R’ then t=t-1

else a[t]=‘R’;

if t=n then output a else t=t+1

end

until t=0

第七章分支限界法

习题7-1. 试写出采用分支界限法求解下面的0、1背包问题实例的过程：物品的个数n=4, 背包的重量m=15, 各个物品的重量依次为2，4，6，9，各个物品的价值依次为10，10，12，18。

对于第i层上的每个节点x，其价值的上界定义为有贪心法所求出的一般背包问题的解S u(x)，下界为S l(x)为S u(x)中减去最后放入背包的x i≠1的物品的相应部分价值。

解答：

(0000)(0001)(0010)(0011)(0100)(0101)(0110)(0111)(1000)(1001)(1010)(1011)(1100)(1101)(1110)(1111)

算法设计与分析复习资料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．动态规划法要求将大问题分解成规模较小的子问题，经分解得到的各个子问题往往不是相互独立的。在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。采

北邮管理学基础第一阶段作业

年北邮管理学基础第一阶段作业

————————————————————————————————作者：————————————————————————————————日期：

2015年北邮管理基础学第一阶段作业 一、判断题（共10道小题，共50.0分） 1.在企业面临外部机遇并且明显处于劣势的时候，企业应选择的战略方案是扭转型战 略。 A.正确 B.错误 知识点: 第一次阶段作业 学生答 案: [A;] 得分: [5] 试题分 值: 5.0 提示: 2.“田忌赛马”是一个流传了几千年的脍炙人口的故事，内中的道理体现了扬长避短 战略原则。 A.正确 B.错误 知识点: 第一次阶段作业 学生答 案: [A;] 得分: [5] 试题分 值: 5.0 提示: 3.目标管理的目的之一是让下属在目标的制定过程中参与进来，共同达成各项工作目 标。 A.正确 B.错误 知识点: 第一次阶段作业 学生答 案: [A;] 得分: [5] 试题分 值: 5.0 提示:

4.根据计划灵活性原理，计划的制定和执行都应有灵活性。 A.正确 B.错误 知识点: 第一次阶段作业 学生答 案: [B;] 得分: [5] 试题分 值: 5.0 提示: 5.Y理论认为人们有消极的工作源动力，而X理论则认为人们有积极的工作源动力。 A.正确 B.错误 知识点: 第一次阶段作业 学生答 案: [B;] 得分: [5] 试题分 值: 5.0 提示: 6.在霍桑实验的基础上，梅奥提出了职工是“经济人”而不是“社会人”的观点。 A.正确 B.错误 知识点: 第一次阶段作业 学生答 案: [B;] 得分: [5] 试题分 值: 5.0 提示: 7.法约尔认为，管理就是计划、组织、指挥、协调和控制。 A.正确 B.错误 知识点: 第一次阶段作业

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

算法设计与分析考试题 及答案 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分，共20分） 1、对公文主题的要求要做到正确、新颖、鲜明、集中。 2、对公务文书的语言要求应做到：准确、简要、庄重、规范。 3、公文的发文字号，简称文号，由发文机关代字、发文年份和发文顺序号组成。 4、签发公文一般要用钢笔或毛笔，不能用圆珠笔或彩色笔。 5、公文的密级一般分为机密、绝密和秘密三个等级。 6、公文的规范性标题又称三项式标题（又叫三要素标题），应包括发文机关、事由（即主题）、和文种名称三个要素。 7、函按主动和被动划分为两种，即去（来）函函和复（答）函函。 8、合同书的标的指的是合同当事人权利义务指向的对象，价款或报酬（又称酬金）指的是取得标的方向对方提提供的代价。9、会议纪要有两种，一种叫办公会议纪要，一种叫重要专题会议纪要。 10、公告和通告在使用范围上不一样，公告的范围要广（或大）,通告的范围要窄（或小）。二、单项选择判断题（每题1分，共10分，把正确答案的符号写在括号内）。

1、公文的成文日期指的是：（C） A、撰稿者完成稿件时间 B、印刷厂印刷的时间 C、主管领导签批的时间 D、公文公布发出的时间 2、下列公文属于平行文文种的是（D） A、命令（令） B、请示 C、通告 D、函 3、公文中附件的作用是（B） A、讲清理由 B、补充、解释、说明正件 C、公布重要内容 D、对公文的正件作一定润色加工 4、公文的规范性标题指的是（A） A、三要素标题 B、只写文种名称的标题 C、两要素标题 D、新式标题 5、简报的三部分结构是指（D） A、报头、主送机关、正文 B、文头、标题、正文 C、报头、报文、日期 D、报头、报文、报尾 6、写好调查报告的前提是（B） A、要做到胸中有数 B、做好调查研究 C、虚心踏实的工作态度 D、扎扎实实的工作作风

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

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

北邮网校远程2018年度管理学基础复习题附答案内容

《管理学基础》复习题版 (答案参见教材、实时授课课件等) 一、单项选择题：（在下列四个选项中选择一个正确的选项。） 1. 营销人员的营销策划能力属于管理者的（ A ）。 A.技术技能 B.人际技能 C.概念技能 D.分析技能 2. 古人所说的“运筹帷幄”是对管理（ B ）职能的最形象的概括。 A.决策 B.计划 C.控制 D.指挥 3.“弹性计划”体现了计划工作的（C ）。 A.限定因素原理 B.许诺原理 C.灵活性原理 D.改变航道原理 4.某项目网络图如下，且该项目的活动关系与时间耗费如图所示（单位：天），该项目的关键路线是（D）。如果将活动A改为3天完工，那么这时该项目的关键路线是（ C ）。 —D—J —F—H—J —E—H—J —I—J 5.某项目网络图如下，且该项目的活动关系与时间耗费如图所示（单位：天），该项目的关键路线是（C）。 6. 企业在环境分析的基础上，针对存在的机遇和威胁、优势和劣势来确定战略选择的分析方法是（ C）。 A．PEST分析法 B.波特五力模型分析法 D.波士顿矩阵法

7.当企业处于明显劣势且面临外部机会时，企业应选择的战略方案是（C ）。 A. 增长型战略。 B.多种经营战略 C. 扭转型战略 D. 防御型战略 8.直线型结构的优点是（A）。 A.结构简单，权力集中，责任分明，命令统一，联系简捷 B.分工较细，能够适应现代组织技术比较复杂和管理分工较细的特点 C.实行了集权与分权的较优结合 D.集中决策，分散经营 9. 最适用于在大型企业的各个事业部之间进行共同的科技研发的组织结构是（C）。 A.直线型 B.直线职能参谋型 C.超事业部制 D.矩阵型 10. 事业部制组织结构的缺点之一是（ D ）。 A.管理无专业分工，各级管理者必须是全能管理者 B.妨碍组织必要的集中领导和统一指挥，形成了多头领导 C.下级部门的主动性和积极性发挥受到限制 D.由于机构重复，造成管理人员的浪费 11．实行集中控制与分散经营的组织结构形式是（D）。 A.直线制 B.职能制 C.矩阵制 D.事业部制 12.下列最适宜采用矩阵式组织结构的是（ C ）。 A.汽车制造厂 B.医院 C.电视剧制作中心 D.学校 13.某贸易进出口公司设有：市场开发部、人力资源部、公关部、质检部、财务部等，该公司是采用（B）来设置部门的。 A.地区部门化 B.职能部门化 C.顾客部门化 D.过程部门化 14．一家超级市场分为以下几个部门：日用杂物、肉类、冷冻食品、瓜果蔬菜、乳制品。该超市是按照（B）来划分部门的。 A.职能 B.产品 C.地区 D.顾客 15. 某公司销售经理被批评为“控制的太多，而领导的太少”。据此，你认为该经理在工作中存在的主要问题最有可能是（C）。 A.对下属销售人员的疾苦没有给予足够的关心 B.对销售目标任务的完成没有给予充分的关注 C.事无巨细，过分亲力亲为，没有做好授权工作 D.没有为下属销售人员制定明确的奋斗目标 16.将直线人员原来属于自己行使的直线权力委托给参谋人员去行使的那部分权力称为（C）。 A.直线职权 B.参谋职权 C.职能职权 D.辅助职权

算法设计与分析试卷

算法设计与分析试卷(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.适用于报告写作的事项有（ACE）。 A.向上级汇报工作，反映情况 B.向下级或有关方面介绍工作情况 C.向上级提出工作建议 D.答复群众的查询、提问 E.答复上级机关的查询、提问 2.工作报告的内容包括（ ACDE）。 A.经常性的工作情况 B.偶发性的特殊情况 C.向上级汇报今后工作的打算 D.对上级机关的查问做出答复 E.向上级汇报的工作经验 3.适合作报告结尾的习惯用语有（AC）。 A.“特此报告” B.“以上报告，请批复” C.“以上报告，请审示” D.“请批准” E.“如无不妥，请批准” 4.适合请示的事项有（ BCDE）。 A.向上级汇报工作情况，请求上级指导 B.下级无权解决的问题，请求上级机关作出指示 C.下级无力解决的问题，请求上级机关帮助解决 D.按规定不能自行处理，应经上级批准的事项 E.工作中出现的一些涉及面广而下级无法独立解决必须请求上级机关协调和帮助的问题 5.下列事项中，应该用请示行文的有（ACD）。 A.××县教育局拟行文请求上级拨款修复台风刮毁的学校 B.××县政府拟行文向上级汇报本县灾情 C.××集团公司拟行文请求上级批准引进肉食品加工自动化生产线 D.××海关拟行文请求上级明确车辆养路费缴纳标准 E.××市政府拟行文向上级反映农民负担增加的情况 6.“请示”应当（AC）。 A.一文一事 B.抄送下级机关 C.一般只写一个主送机关 D.不考虑上级机关的审批权限和承受能力 7.下列标题中正确的有（BDE）。 A.××分公司关于请求批准开发新产品的报告 B.××县人民政府关于解决我县高寒山区贫困户移民搬迁经费的请示 C.××县人民政府关于请求将××风景区列为省级自然保护区的请示报告 D.××公司关于解决生产用地的请示 E.××省移民办公室关于对移民区域作适当调整的请示

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

一。选择题 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 ）

北邮网院《管理学基础》复习题(1)

《管理学基础》复习题 （答案参见实时授课课件、教材等相关教学资源） 一、单项选择题：（在下列四个选项中选择一个正确的选项。） 1. 被誉为科学管理之父的是（ A ）。 A. 泰勒 B. 法约尔 C. 韦伯 D. 梅奥 2. 营销人员的营销策划能力属于管理者的（ A ）。 A. 技术技能 B. 人际技能 C. 概念技能 D. 分析技能 3. 管理具有与生产关系、社会制度相联系的一面，这指的是管理的（ B ）。 A. 自然属性 B. 社会属性 C. 科学性 D. 艺术性 4.“弹性计划”体现了计划工作的（ C ）。 A.限定因素原理 B.许诺原理 C.灵活性原理 D.改变航道原理 5. 某公司在2012年年初的工作会议上提出，力争在本年度实现利润2亿元。如果从计划工作的表现形式看，此计划属于（ D ）。 A. 战略 B. 宗旨 C. 规划 D. 目标 6. 某项目网络图如下，且该项目的活动关系与时间耗费如图所示（单位：天），该项目的关键路线是（ D ）。 A．A—D—J B．B—F—H—J C．A—E—H—J D．C—I—J 7. 企业进行环境分析时，常用的分析方法是（ A ）。 A．PEST分析法 B. 波特五力模型 C. SWOT分析法 D. 波士顿矩阵法

8. 直线型结构的优点是（ A ）。 A. 结构简单，权力集中，责任分明，命令统一，联系简捷 B. 分工较细，能够适应现代组织技术比较复杂和管理分工较细的特点 C. 实行了集权与分权的较优结合 D. 集中决策，分散经营 9. 下列最适宜采用矩阵式组织结构的是（ C ）。 A. 汽车制造厂 B. 医院 C. 电视剧制作中心 D. 学校 10.某贸易进出口公司设有：市场开发部、人力资源部、公关部、质检部、财务部等，该公司是采用（ B ）来设置部门的。 A.地区部门化 B.职能部门化 C.顾客部门化 D.过程部门化 11．一家超级市场分为以下几个部门：日用杂物、肉类、冷冻食品、瓜果蔬菜、乳制品。该超市是按照（ B ）来划分部门的。 A．职能 B．产品 C．地区 D．顾客 12.将直线人员原来属于自己行使的直线权力委托给参谋人员去行使的那部分权力称为（ B ）。 A. 直线职权 B. 参谋职权 C. 职能职权 D. 辅助职权 13．根据领导寿命周期理论，适用于下属低成熟度的情况，由领导者告诉下属应该干什么、怎么干以及何时何地干的领导风格是（ A ）。 A．命令型领导 B．说服型领导 C．参与型领导 D．授权型领导 14. 按照费德勒模型，当组织内上下级关系好、任务结构明确、职位权力强时，应选择的领导者类型是（ A ）。 A. 任务取向型 B. 关系取向型 C. 工作与人际关系并重型 D. 以领导者为中心型 15. 通过人格魅力来影响和改变下属的做法，利用的是（ 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背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进

北邮远程 质量管理学基础 第一次作业

一、判断题（共10道小题，共100.0分） 1. 产品质量的好坏，最终要通过用户的使用来评价。 2. 1.正确 2.错误 知识点:第一次阶段作业第一组 学生答案:[A;] 标准答 案: A; 得分:[10]试题分 值: 10.0 提示: 3. QC小组活动是日本式质量管理的基础和重要支柱。 4. 1.正确 2.错误 知识点:第一次阶段作业第一组 学生答案:[A;] 标准答 案: A; 得分:[10]试题分 值: 10.0 提示: 1. 质量特征值是以数值表示的数量化的质量特征。 2. 1.正确

2.错误 知识点:第一次阶段作业第二组 学生答案:[A;] 标准答 案: A; 得分:[10]试题分 值: 10.0 提示: 1. 适宜的质量体系应能满足现实质量目标的需要，同时也是经济而有效的。 2. 1.正确 2.错误 知识点:第一次阶段作业第二组 学生答案:[A;] 标准答 案: A; 得分:[10]试题分 值: 10.0 提示: 1. 用以分析质量特性与原因关系的图叫因果图。 2. 1.正确 2.错误 知识点:第一次阶段作业第三组 学生答案:[A;] 标准答 案: A; 得分:[10]试题分 值: 10.0 提示:

1. (错误)标准偏差表示数据与质量标准的差异程度。 2. 1.正确 2.错误 知识点:第一次阶段作业第三组 学生答案:[A;] 标准答 案: B; 得分:[0]试题分 值: 10.0 提示: 1. (错误)偶然因素是指对产品质量偶然起作用的因素。 2. 1.正确 2.错误 知识点:第一次阶段作业第四组 学生答案:[A;] 标准答 案: B; 得分:[0]试题分 值: 10.0 提示: 1. 排列图的主要作用是用来抓质量的关键性问题。 2. 1.正确

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

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

《应用文写作》模拟试题AB卷

班级：学号：姓名：李贞伟 河南工业职业技术学院继续教育学院试卷 应用文写作试题（A） 一、名词解释题（每小题5分，共20分） 1．公文的主送机关 是指公文的主要受理机关，即对公文负主办或答复责任的机关，应当使用全称或者规范化简称、统称。 2．请示 是下级机关向上级机关请求对某项工作、问题作出指示，对某项政策界限给予明确，对某事予以审核批准时使用的一种请求性公文，是应用写作实践中的一种常用文体。 3．批复 是“答复下级机关的请示事项”时使用的文种。批复是用于答复下级机关请示事项的公文.它是机关应用写作活动中的一种常用公务文书。 4．民事诉状 是公民、法人或其他组织作为民事原告在自己的民事权益受到侵害或者与他人发生争议时，为维护自身的民事权益，依据事实和法律，向人民法院提起诉讼，要求依法裁判时所提出的书面请求。 二、简答题（每小题6分，共30分） 1．应用文的特点是什么？ 应用文的特点主要是广泛性、实用性、程式性、针对性、时效性 2．报告与请示有哪些不同？ 1．内容要求不同。请示的内容要求一文一事；报告的内容可一文一事也可一文数事。 2．侧重点不同。请示属于请示性公文，侧重于提出司题和请求指示、批准；报告属于陈述性公文，侧重于汇报工作，陈述意见或者建议。 3．行文目的不同。请示的目的是请求上级机关批准某项工作或者解决某个问题；报告的目的是让上级机关了解下情，掌握情况，便于及时指导。 4．行文时间不同。请示必须事前行文；报告可以在事后或者事情发展过程中行文。 5．报送要求不同。请示一般只写一个主送机关；受双重领导的单位报其上级机关的请示，应根据请示的内容注明主报机关和抄报机关，主报机关负责答复请示事项；报告可以报送一个或多个上级机关。 6．篇幅不同。请示一般都比较简短；报告的内容涉及面较为广泛，篇幅一般较长。 7．标题写作不同。一般来讲请示的标题中不写报告二字，就是x x x关于x x x x x x 的请示；报告的标题中不写请示二字，就是x x”x关于x x x xx x的报告。 8．结束用语不同。请示的结尾一般用“妥否，请批示”或“特此请示，请予批准”等形式，请示的结束用语必须明确表明需要上级机关回复的迫切要求；报告的结尾多用“特此报告”等形式，一般不写需要上级必须予以答复的词语。

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、动态规划算法适用于解（具有

北邮《管理学基础》期末考试完美答案!

北邮《管理学基础》期末考试完美答案! 复习题 1管理基础选择题:(从以下四个选项中选择正确的一个) 1。被称为科学管理之父的是(一) A泰勒(罗)法·尤尔·韦伯·梅奥2。营销人员的营销策划能力属于经理(一) a。技术技能b .人际交往技能c .概念技能d .分析技能3。管理有一个与生产关系和社会制度联系在一起的方面，即管理(b)A.自然属性b .社会属性c .科学属性d .艺术品质4。古人说“运筹帷幄”是对管理职能最生动的概括(b)A.决策b .计划c .控制d .命令 5。王某是一家建筑工地的承包商，他对农民工采取了“软硬兼施”的管理方式。他通常的口头禅是“如果你做得不好，就回家，如果你做得好，下个月给你奖金”可以说，王某把他的民工看作是(b)A.社会的人，经济的人，复杂的人，自我实现的人。弹性计划体现了计划工作的(c) A。限制因素原则b .承诺原则c .灵活性原则d .渠道变更原则 7。一家公司在XXXX早些时候的工作会议上提议今年争取2亿元的利润。如果我们看计划工作的表现，这个计划属于(d) A。战略b .目的c .规划d .目标 8。项目的网络图如下，图中显示了项目的活动关系和时间消耗(单位:天)。该项目的关键路线是(d)

a . a-d-JB . b-f-h-JC . a-e-h-JD . c-I-j 9。项目的网络图如下，图中显示了项目的活动关系和时间消耗(单位:天)。该项目的关键路线是(c) a . a-c-g-JB . a-c-f-IC . a-c-f-h-JD . a-b-e-h-j 1 10。当企业进行环境分析时，常用的分析方法是(a) a。五种力量模型；优势分析；优势分析；波士顿矩阵法； 11。在环境分析的基础上，企业根据现有的机会和威胁、优势和劣势来确定战略选择的分析方法是(c)A.五种力量模型。线性结构的优点是(a) a。结构简单，权力集中，职责明确，命令统一，连接简单 b。精细分工，能够适应现代组织技术更复杂的特点，管理分工更精细c .集权与分权的更好结合已经实现d .集中决策，分权管理 13。最适合于大型企业不同部门的共同科学技术研究和发展的组织结构是(d)A.直线b .直线函数顾问c .超级除法d .矩阵14。银行设立的商业信贷部门属于(一) a。职能部门b .客户部门c .区域部门d .流程部门15。集中控制和分散运作的组织结构是(d) A。直线系统b .功能系统c .矩阵系统d .除法系统16。以下是最合适的矩阵组织结构(c) a。汽车厂b医院c电视剧制作中心d学校

算法设计与分析课程期末试卷-A卷(自测 )

华南农业大学期末考试试卷（A卷） 2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log2n C．2n2D．3nlog3n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog2n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨 牌的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法 对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同

6. 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。 A ．（4.5，0） B ．（4.5，4.5） C ．（5，5） D ．（5，0） 7. n 个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下 说法不正确？ A ．让水桶大的人先打水，可以使得每个人排队时间之和最小 B ．让水桶小的人先打水，可以使得每个人排队时间之和最小 C ．让水桶小的人先打水，在某个确定的时间t 内，可以让尽可能多的人打上水 D ．若要在尽可能短的时间内，n 个人都打完水，按照什么顺序其实都一样 8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分 别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。 A ．问题规模相同，问题性质相同 B ．问题规模相同，问题性质不同 C ．问题规模不同，问题性质相同 D ．问题规模不同，问题性质不同 9. 对布线问题，以下 是不正确描述。 A ．布线问题的解空间是一个图 B ．可以对方格阵列四周设置围墙，即增设标记的附加方格的预处理，使得算法简化对边界的判定 C ．采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的 D ．采用先入先出的队列作为活结点表，以终点b 为扩展结点或活结点队列为空作为算法结束条件 10. 对于含有n 个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。 A ．n! B ．2n C ．2n+1-1 D ． ∑=n i i n 1 !/! 答案：DACAD CACCB

应用文写作复习模拟题及答案

应用文写作复习模拟题及 答案 Revised by Liu Jing on January 12, 2021

应用写作试题四写作题 1 根据下面提供的材料，拟写一份会议通知。写作时，材料中的“××”替代的内容可以虚拟。 ××省教育厅厅准备于2001年4月16日至19日，在××市××大学学术交流中心报告厅召开全省高校校（院）长办公室工作会议。4月15日持本通知到学术交流中心接待室报到。参加会议人员有本省各高新校校（院）长办公室主任（或副主任），每校1——2人。本次会议的目的是为了进一步加强高校校（院）长办公室工作，促进全省各高校校（院）长办公室工作的协作与交流。 联系电话：×××——××××××××，联系人：××大学校长办公室×××老师，传真：×××——××××××××，邮编：××××××。会议的注意事项有四点：请参加会议人员将到达时间、车次和返程时间及车次提前电告会务组，以便安排接待和代办购票；请填写所附《与会表》，加盖单位公章，于4月10日前邮寄给会务组（设在××大学校长办公室），以便统计与会人数，安排住宿；请各校将拟提交的会议交流的经验材料自行打印80份，在报到时交会务组；往返路费和住宿费自理，回单位报销，会议伙食标准每天××元。 答：关于召开全省高校校（院）长办公室工作会议的通知 各高校（院）： 为了进一步加强高校校（院）长办公室工作，促进全省各高校校（院）长办公室工作的协作与交流，经省教育厅研究决定，召开全省高校校（院）长办公室工作会议。现将有关事宜通知如下： 一、会议时间：4月16日至19日，会期4天。

二、报到时间：4月15日。 三、会议地点：沈阳市辽宁大学学术交流中心报告厅。 四、报到地点：沈阳市辽宁大学学术交流中心接待室。 五、参加人员：各高校校（院）长办公室主任（或副主任），每校1——2 人。 六、会议内容：研究各高校校（院）长办公室工作的协作与交流。 七、注意事项： 1、请参加会议人员将到达时间、车次和返程时间及车次提前电告会务组，以便安排接待和代办购票； 2、请填写所附《与会表》，加盖单位公章，于4月10日前邮寄给会务组（设在辽宁大学校长办公室），以便统计与会人数，安排住宿； 3、请各校将拟提交的会议交流的经验材料自行打印80份，在报到时交会务组； 4、往返路费和住宿费自理，回单位报销，会议伙食标准每天40元。 八、联系方式：电话：024——公室王老师 传真：024—— 特此通知。 附件：与会表 辽宁省教育厅（公章） 二OO一年四月一日 2 根据下面的材料，代××县地税局拟写一份通报。 （1）原××镇农贸市场协税员刘柳，男，29岁。