参考答案
第1章
一、填空题
1. 有穷性、确定性、输入、输出、可行性
2. 时间复杂性、空间复杂性
3. 数据的逻辑结构、存储结构和数据的运算
4. 算法的复杂性
5. 递归技术、分治法、模拟法、贪心算法、状态空间搜索法、随机算法、动态规划
6. 抽象的操作
7. 将某种程序设计语言的基本结构与非形式的英文或中文叙述语句相结合产物
8. 问题的陈述、模型的选择、算法的设计、算法的程序实现、算法分析
9. 指算法在计算机内执行时所需存储空间的度量
10. 指令空间和数据空间
二、选择题
1. C
2. A
3. C
4. B
5. A
6. C
7. CAB
8. D
9. D 10. C 11. B 12. B 13. B 14. D 15. B
三、简答题
1. 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。
2. 一个算法应该具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束；确切性：算法的每一步骤必须有确切的定义；输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；输出：一个算法有一个或多个输出，以反映对输入数据加工后
2 算法分析与设计
的结果。没有输出的算法是毫无意义的；可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
3. 关于算法的复杂性，有两个问题要弄清楚：
（1）用怎样的一个量来表达一个算法的复杂性。
（2）对于给定的一个算法，怎样具体计算它的复杂性。算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。
4. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
5. 算法与数据结构是一个整体，算法总是离不开数据结构，算法含有对数据结构的访问，算法只能适用于特定的数据结构。因此设计一个算法适合于访问多个数据结构是不明智的，而且数据结构由多个算法来对其进行同种操作也多余的。这是面向对象程序设计的基础，在面向对象中，算法与数据结构被捆绑成一个类，从这样的角度问题，就不用为如何实现通盘的程序功能而费尽心机了。现实世界，任何对象都具有一定的属性与操作，也就总能用数据结构与算法两者合一地来描述。
6. 2^100, (2/3)^n，(3/2)^n，n^n , , n!，2^n，lgn ,n^lgn, n^(3/2)
7. 函数源程序清单如下：
void Josephus(int A[ ], int n, s, m )
{
int i, j, k, tmp;
if ( m == 0 ) {
cout << "m = 0是无效的参数！" << endl;
return;
}
for ( i = 0;i < n;i++) A[i] = i + 1; /*初始化，执行n次*/
i = s – 1; /*报名起始位置*/
for ( k = n; k > 1; i-- ) { /*逐个出局，执行n-1次*/
if ( i == k ) i = 0;
i = ( i + m - 1 ) % k; /*寻找出局位置*/
if ( i != k-1 ) {
参考答案 3
tmp = A[i]; /*出局者交换到第k-1位置*/
for ( j = I; j < k-1; j++ ) A[j] = A[j+1];
A[k-1] = tmp;
}
}
for ( k = 0; k < n / 2; k++ ) { /*全部逆置, 得到出局序列*/
tmp = A[k]; A[k] = A[n-k+1]; A[n-k+1] = tmp;
}
}
例：n = 9, s = 1, m = 5
第5人出局, i = 4
第1人出局, i = 0
第7人出局, i = 4
第4人出局, i = 2
第3人出局, i = 1
第6人出局, i = 1
第9人出局, i = 2
第2人出局, i = 0
第8人出局, i = 0
最终出局顺序
例：n = 9, s = 1, m = 0
报错信息m = 0是无效的参数！
例：n = 9, s = 1, m = 10
第1人出局, i = 0
第3人出局, i = 1
第6人出局, i = 3
第2人出局, i = 0
第9人出局, i = 4
第5人出局, i = 1
第7人出局, i = 1
第4人出局, i = 0
第8人出局, i = 0
最终出局顺序
当m = 1时，时间代价最大。达到( n-1 ) + ( n-2 ) + ?????? + 1 = n(n-1)/2 O(n2)。
8. 统计算法：
include
4 算法分析与设计
include "string.h"
void frequency( String& s, char& A[ ], int& C[ ], int &k ) {
// s是输入字符串，数组A[ ]中记录字符串中有多少种不同的字符，C[ ]中记录每
//一种字符的出现次数。这两个数组都应在调用程序中定义。k返回不同字符数。
int i, j, len = s.length( );
if ( !len ) { cout << "The string is empty. " << endl; k = 0; return; }
else { A[0] = s[0]; C[0] = 1; k = 1; /*语句s[i]是串的重载操作*/
for ( i = 1; i < len; i++ ) C[i] = 0; /*初始化*/
for ( i = 1; i < len; i++ ) { /*检测串中所有字符*/
j = 0;
while ( j < k && A[j] != s[i] ) j++; /*检查s[i]是否已在A[ ]中*/
if ( j == k ) { A[k] = s[i]; C[k]++; k++ } /*s[i]从未检测过*/
else C[j]++; /*s[i]已经检测过*/
}
}
}
测试数据s = "cast cast sat at a tasa\0"
测试结果：
A c a s t b
C 2 7 4 5 5
第2章
一、填空题
1. 栈
2. 迭代法差分方程法套用公式法生成函数求和法
3. 数据的定义形式是按递归定义的问题解法按递归算法实现数据的结构形式是按递归定义的
二、选择题
1. B
2. D
3. C
三、简答题
1. 这是一个递归过程，n执行一次就减2，当n≤0时该过程执行结束。因此，当n＝5 时，其输出结果为1、3、5;当n＝6时，其输出结果为2、4、6。
2.
（1）递归方式。
void inorder_recursive(Bitree T)
{ /* 中序遍历二叉树的递归算法 */
if (T)
{ inorder_recursive(T->lchild); /* 访问左子树 */
visit(T); /* 访问当前结点 */
参考答案
5
inorder_recursive(T->rchild); /* 访问右子树 */ } }
（2）非递归方式。
void inorder_nonrecursive(Bitree T) { initstack(S); /* 初始化栈 */ push(S, T); /* 根指针入栈 */ while (!stackempty(S)) {
while (gettop(S, p) && p) /* 向左走到尽头 */ push(S, p->lchild); pop(S, p); /* 空指针退栈 */ if (!stackempty(S)) { pop(S, p);
visit(p); /* 访问当前结点 */
push(S, p->rchild); /* 向右走一步 */
} } }
3. a=2,b=2,c=1,d(n)=logn
1
l o g 0()()
b
k a
j
k j
j T n C n a d b --
==?+∑
21
l o g
2
12
l o g 2k j
k j
j n
--
==?+∑
1
2()l o g
2k j
j n k j -==+-∑ 1
l o g 2
2()
k j
j n k j -==+-∑
1
2
1
l o g 2((1)2(2)2
2)
k n k k k -
=++-+-
++
12
1
1
l o g 2(12
2212
2121)
k k n --
=+++++
++
+++++ 2
1
log 2(1222122121)
k k n -
-=++++++
++++++
1
1
log 2((21)(2
1)(21))k
k n -=+-+-++-
1
l o g 2(22
)
k n k +=+-
-
1
2
l o g 22l o g 2
l o g
2
k n k +=+--
2(12l o g 2)
l o g 2l o g
2
l o g 2
n n =+-?-? 第3章
一、填空题 1. 2h －1 2. cedba 3. t2
4. t2
5. gbdehfca
6. 错误的
6
算法分析与设计
7. 5 8. 31
9. 分支层次关系 10. 前序，中序，后序 11. 右子树 12. 三叉链表 13. wuvts 14. 15 15. 物理 二、选择题 1. A 2. A 3. D 4. C 5. B 6. A 7. C 8. A
9. C 10. A 11. A
12. A
13. B 14. A
三、简答题
1. 一棵度为二的有序树与一棵二叉树的区别在于，有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。
2.
（1）设层号为l 的结点数目为m=k^(l-1)。
（2）编号为i 的结点的双亲结点的编号是：|_(i+k-2)/k_|(不大于(i+k-2)/k 的最大整数。也就是(i+k-2)与k 整除的结果.以下/表示整除。
（3）编号为i 的结点的第j 个孩子结点编号是：k×(i-1)+1+j 。
（4）编号为i 的结点有右兄弟的条件是(i+1)/k==(i+2)/k (整除) 并且i!=1 3.
（1）第i 层的结点个数为k i 。
（2）编号为i 的结点的双亲结点的编号是2i k k
+-?????
?
。
（3）编号为i 的结点的第m 个孩子结点的编号是k(i-1)+m+1。 （4）编号为i 的结点有右兄弟的条件是：(i-1) MOD m ≠ 0。
参考答案7 其右兄弟结点的编号是i+1。
4. 证明：n=1成立
设n=k成立，E k=I k+2k
n=k+1时，设增加结点的深度为D k
I k+1=I k+D k
E k+1=E k-D k+2(D k+1)
=E k+D k+2=I k+2k+D k+2
=I k+1+2(k+1)=I k+1+2n
所以当n=k+1时也成立。
结论成立。
根据二叉树性质：度为0的结点数n0=度为2的结点数n2+1
所以：外结点数n+1
s=（查找成功总的比较次数）/（内结点数）=I/n （1）
u=（查找失败总的比较次数）/（外结点数）=（E-n）/（n+1）=（I+n）/（n+1）（2）
由（1）、（2）可得I=ns=(n+1)u-n
s=(1+1/n)u-1
第4章
一、填空题
1. 数目
2. 简单路径
3. 回路或环
4. 连通图
5. 连通分量
6. 强连通图
7. 深度优先、广度优先
8 算法分析与设计
8. 3、4、2
9. 一个结点可能有若干个前驱，也可能有若干个后继 10. V i 所在行和列的非零元素之和 11. 1534276、1354276 12. n-1个非零元素 13. 5
14. 对每个顶点查找其邻接点的过程、O(e),e 是图中边的条数、O(e),e 是图中边的条数、遍历图的顺序不同、DFS 采用栈存储访问过的结点，BFS 采用队列存储访问过的结点
15.
（1）拓扑的序列为：V 1V 2V 3V 4，V 1V 3V 2V 4，V 2V 1V 3V 4 （2）添加从结点V 3到结点V 2的弧 二、选择题 1. D 2. B 3. A 4. A 5. D 6. D 7. C 8. B 9. D
10. D
11. A 12. C
13. B 14. A 15. A
三、简答题 1. 邻接矩阵：
011
00000000110
00??????
????
?????
?
邻接表如图A-1所示： 逆邻接表如图A-2所示：
图A-1 图A-2
十字链表如图A-3所示：
参考答案
9
图A-3
2. 填入时间后的表1。
填入时间后的表2。
关键路径：v1 v2 v5 v7
v1 v4 v5 v7
关键活动：a1 a2 a4 a8 a9
3. 对于n个顶点的无向图和有向图，用邻接矩阵表示时：
（1）设m为矩阵中非零元素的个数。
无向图的边数=m/2
有向图的边数=m
（2）无论是有向图还是无向图，在矩阵中第I行,第j列的元素若为非零值，则该两顶点有边相连。
（3）对于无向图，任一顶点I的度为第I行中非零元素的个数。
对于有向图，任一顶点I的入度为第I列中非零元素的个数，出度为第I行中非零元素的个数，度为入度出度之和。
4. 当用邻接表表示时：
（1）对于无向图，图中的边数=边表中结点总数的一半。对于有向图，图中的边数=边表中结点总数。
10 算法分析与设计
（2）对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的adjvex域有另一顶点位置的结点，则表示有边相连。
对于有向图，则表示有出边相连。
（3）对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。对于有向图，任意一个顶点的出度由该顶点的边表中结点的个数来决定。
5.
（1）有n个顶点的有向强连通图最多不n(n-1)条边，最少有n条边。
（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有10002个矩阵元素，不一定是稀疏矩阵，因为它可能是特殊矩阵。
（3）对有向图进行深度优先遍历。如果从有向图上某个顶点v出发的遍历，在dfs(v)结束之前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图中必定存在包含顶点v和顶点u的环。
第5章
一、填空题
1. O(log2n)
2. 有向图
3. O(eloge)、稀疏
4. 边稠密、边稀疏
5. G中每个结点的入度＝出度
6. 大于或等于n
二、选择题
1. B
2. B
3. B
4. D
5. B
6. A
7. B
8. D
9. C 10 B
三、简答题
1. 当候选轻边集中的轻边数始终等于1条时，其最小生成树是唯一的。用Prim和Kruskal求最小生成树的时间复杂度分别为O(n^2)和O(eloge)，前者适合于稠密图，后者适合于稀疏图。
2.
参考答案11
1 5
2
3 6 4
1 5
2 6
3 4
1 5 6
2
3 4
5 6 1 2 3 4
5 1
6 2 3 4
5 1 2
6 3 4
5 1 2 3
6 4
3.
ve(l)=0
ve(2)=max{a1,a2+a3}=3+3=6
ve(3)=3
ve(4)=max{6+a4,3+a5}=3+9=12
ve(5)=12+6=18
ve(6)=18+3=21
vl(6)=ve(6)=21
vl(5)=21-3=18
vl(4)=18-6=12
vl(3)=12-9=3
vl(2)=12-5=7
vl(1)=3-3=0
a(a1)=ve(1)=0
e(a2)=0
e(a3)=ve(3)=3
e(a4)=ve(2)=6
e(a5)=ve(3)=3
e(a6)=3
e(a7)=ve(4)=12
e(a8)=12
e(a9)=ve(5)=18
l(a9)=vl(6)-a9=21-3=18
l(a8)=21-2=19
l(a7)=vl(5)-a7=18-6=12
l(a6)=vl(5)-a6=18-4=14
l(a5)=vl(4)-a5=12-9=3
l(a4)=vl(4)-a4=12-5=7
l(a3)=vl(2)-a3=7-3=4
l(a2)=vl(3)-a2=3-3=0
l(a1)=vl(2)-a1=7-2=5
所以，图中关键路径为a2,a5,a7,a9，即(v1,v3,v4,v5,v6)。
4.
（1）以顶点1为根的深度优先生成树如图A-4所示。
12 算法分析与设计
图A-4 深度优先生成树
（2）图中的关结点是：1、2、3、7、8。
5. 各活动的最早开始时间和允许的最晚完成时间见下表。 各活动的最早开始时间和允许的最晚完成时间表
关键活动：a 1 a 3 a 4 a 5
6. 由于V 1的每一个结点与V 2的每一个结点仅有一条边相关联，所以V 1的每一个结点与关联m
V
=2
条
边。而V 1中有n 个结点，因此K n,m 共有nm 条边。有n+m 个结点。
第6章
一、填空题 1. 线索化
2. （2），（1），（7）
3. 16，17，8，21
4. 1+/21log (
)
2
m n ????+
5. （2）、（6）、（9）
6. 直接定址法；数字分析法；平方取中法；折叠法；除留余数法；随机数法
7. 开放定址法；再散列法；链地址法；建立一个公共溢出区。
8. l i -1次
9. [log 2n]+1
10. 顺序存储且有序，有序 11. 30，31.5
12. m-1个关键字，[m/2]-1 13.
（1）字符串
参考答案13 （2）16，16，21
（3）索引表
14. (n+1)/2
二、选择题
1. B
2. D
3. A
4. C
5. C
6. B
7. C
8. A
9. B 10. D 11. C 12. A 13. C 14. B 15. D
三、简答题
1. 一棵二叉排序树（又称二叉查找树）或者是一棵空树，或者是一棵同时满足下列条件的二叉树：
（1）若它的左子树不空，则左子树上所有结点的键值均小于它根结点键值。
（2）若它的右子树不空，则右子树上所有结点的键值均大于它根结点键值。
（3）它的左、右子树也分别为二叉排序树。
2. 衡量算法的标准有很多，时间复杂度只是其中之一。尽管有些算法时间性能很好，但是其他方面可能就存在着不足。比如散列查找的时间性能很优越，但是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象，为了解决冲突，还得采用其他方法。
折半查找也是有代价的，因为事先必须对整个查找区间进行排序，而排序也是费时的，所以常应用于频繁查找的场合。对于顺序查找，尽管效率不高，但却比较简单，常用于查找范围较小或偶而进行查找的情况。
3. 此法要求设立多个散列函数H i, i= 1 , …, k 。当给定值K与闭散列表中的某个键值是相对于某个散列函数H i的同义词因而发生冲突时，继续计算该给定值K在下一个散列函数H i+1下的散列地址，直到不再产生冲突为止。
4.
（1）查找（18）待插入的结点，需要走一条由根结点到叶子结点的路径，也就是进行读结点的操作3次。插入（18）后的3阶B-树的须进行调整，分裂结点由插入的叶子结点向上至根结点，共分裂了3个结点，因此进行了3次写结点的操作。
插入（18）调整后的B-树如图A-5所示。
（2）再删除（78）后的3阶B-树如图A-6所示。
14 算法分析与设计
图A-5 图A-6
第7章
一、填空题
1. O(1)、O(nlog2n)
2. 稳定
3. 3
4. (15，20，50，40)
5. O(log2n)
6. O(n2)
7. 冒泡排序、快速排序
8. 插入排序、快速排序
9. 完全二叉树、n/2
10. 稳定、不稳定
11. O(nlog2n)、O(n2)
12. 插入排序、选择排序、交换排序、归并排序、分配排序。
13. 直接插入
14. i+1
15. L2
二、选择题
1. C
2. C
3. D
4. D
5. C
6. D
7. C
8. B
9. B 10. D 11. C 12. C 13. D 14. C 15. B
三、简答题
1. 在排序过程中，每次比较会有两种情况出现，若整个排序过程至少需作t次比较，则显然会有2∧t 个情况，由于n个结点总共有n!种不同的排列，因而必须有n!种不同的比较路径，于是：2t≥n!
即t≥log2n!
参考答案15 因为log2n!=nlog2n-n／ln2+log2n／2+O(1)
故有log2n!≈nlog2n
从而t≥nlog2n得证。
2. 内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移动次数。外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁盘次数和在内存中总的记录对象的归并次数。
不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排序方法往往是按一定的间隔移动或交换记录对象的位置，从而可能导致具有相等排序码的不同对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换，只是在相邻的数据对象间比较排序码，如果发生逆序（与最终排序的顺序相反的次序）才交换，因此具有相等排序码的不同对象的前后相对位置在排序前后不会颠倒，是稳定的排序方法。但如果把算法中判断逆序的比较“>（或<）”改写成“≥（或≤）”，也可能造成不稳定。
3. 若待排序的n个对象的序列已经按排序码非递减次序有序排列，且设排序的时间代价为T(n)。当以第一个对象作为基准对象时，应用一次划分算法Partition，通过n-1次排序码比较，把只能把整个序列划分为：基准对象的左子序列为空序列，右子序列为有n-1个对象的非递减有序序列。
对于这样的递归QuickSort( )算法，其时间代价为：
T(n) = (n-1) + T(n-1)
= (n-1) + {( n-2) + T(n-2) }
= (n-1) + (n-2) + {(n-3) + T(n-3) }
= ……
= (n-1) + (n-2) + (n-3) + … + { 2 + T(1) }
= (n-1) + (n-2) + (n-3) + … + 2 + 1
= n(n-1)/2 = O(n2)
4.
（1）插入排序的每趟的结果。
初始值键值序列[12] 5 9 20 6 31 24
i=2 [5 12] 9 20 6 31 24
i=3 [5 9 12] 20 6 31 24
i=4 [5 9 12 20] 6 31 24
i=5 [5 6 9 12 20] 31 24
16 算法分析与设计
i=6 [5 6 9 12 20 31] 24
i=7 [5 6 9 12 20 24 31]
（2）冒泡排序的每趟的结果。
初始键值序列[12 5 9 20 6 31 24]
第一趟之后[5 9 12 6 20 24] 31
第二趟之后[5 9 6 12 20] 24 31
第三趟之后[5 6 9 12] 20 24 31
第四趟之后 5 6 9 12 20 24 31
5. 由快速排序的算法可知，所需递归工作栈的深度取决于所需划分的最大次数。如果在排序过程中每次划分都能把整个待排序序列根据基准对象划分为左、右两个子序列。假定这两个子序列的长度相等，则所需栈的深度为：
S(n) = 1 + S(n/2)
= 1 + { 1 + S(n/4) } = 2 + S(n/4)
= 2 + { 1 + S(n/8) } = 3 + S(n/8)
= ……
= log2n + S(1) = log2n (假设1个对象的序列所用递归栈的深度为0)
如果每次递归左、右子序列的长度不等，并且先将较长的子序列的左、右端点保存在递归栈中，再对较短的子序列进行排序，可用表示最坏情况的大O表示法表示。此时其递归栈的深度不一定正好是log2n，其最坏情况为O(log2n)。
6. 稳定排序有直接插入、冒泡排序、归并排序。
不稳定排序有快速排序、直接选择排序、堆排序。
举例如下：
（1）快速排序。
初始状态4065384997651360
排序后1338404960656597
（65表示记录初始位置在65记录位置之后）
（2）堆排序。
初始状态6538759780132765
排序后1327386565758097
（3）直接排序。
初始状态4065384997651360
排序后1338404960656597
7. 初始序列对应的完全二叉树如图A-7所示。
初始序列不是堆，调整为小顶堆如图A-8所示。
参考答案17
图A-7 图A-8
调整后得到小顶堆为（12，24，33，65，33，56，48，92，86，70）
8.
（1）希尔排序{ 512 275 275* 061 } 增量为2
{ 275* 061 512 275 } 增量为1
{ 061 275* 275 512 }
（2）直接选择排序{ 275 275* 512 061 } i = 1
{ 061 275* 512 275 } i = 2
{ 061 275* 512 275 } i = 3
{ 061 275* 275 512 }
（3）快速排序{ 512 275 275* }
{ 275* 275 512 }
（4）堆排序{ 275 275* 061 170 } 已经是最大堆，交换275与170
{ 170 275* 061 275 } 对前3个调整
{ 275* 170 061 275 } 前3个最大堆，交换275*与061
{ 061 170 275* 275 } 对前2个调整
{ 170 061 275* 275 } 前2个最大堆，交换170与061
{ 061 170 275* 275 }
9.
（1）归并排序。
（18，29）（25，47）（12，58）（10，51）
18 算法分析与设计
（18，25，29，47）（10，12，51，58）
（10，12，18，25，29，47，51，58）
（2）快速排序。
（10，18，25，12，29，58，51，47）
（10，18，25，12，29，47，51，58）
（10，12，18，25，29，47，51，58）
（3）堆排序。
初始堆（大顶堆）：（58，47，51，29，18，12，25，10）
第一次调整：（51，47，25，29，18，12，10）（58）
第二次调整：（47，29，25，10，18，12）（51，58）
第三次调整：（29，18，25，10，12）（47，51，58）
第四次调整：（25，18，12，10）（29，47，51，58）
第五次调整：（18，10，12）（25，29，47，51，58）
第六次调整：（12，10）（18，25，29，47，51，58）
第七次调整：（10，12，18，25，29，47，51，58）
10.
（1）直接插入排序。
序号123456789101112 关键字83 4063 13 84 35 96 57 39 79 61 15
i = 2 40 83 [63 13 84 35 96 57 39 79 61 15]
i = 3 40 63 83 [13 84 35 96 57 39 79 61 15]
i = 4 13 40 63 83 [84 35 96 57 39 79 61 15]
i = 5 13 40 63 83 84 [35 96 57 39 79 61 15]
i = 6 13 35 40 63 83 84 [96 57 39 79 61 15]
i = 7 13 35 40 63 83 84 96 [57 39 79 61 15]
i = 8 13 35 40 57 63 83 84 96 [39 79 61 15]
i = 9 13 35 39 40 57 63 83 84 96 [79 61 15]
i = 10 13 35 39 40 57 63 79 83 84 96 [61 15]
i = 11 13 35 39 40 57 61 63 79 83 84 96 [15]
参考答案19 i = 12 13 15 35 39 40 57 61 63 79 83 84 96
（2）直接选择排序。
序号123456789101112
关键字83 4063 13 84 35 96 57 39 79 61 15
i = 1 13 [40 63 83 84 35 96 57 39 79 61 15]
i = 2 13 15 [63 83 84 35 96 57 39 79 61 40]
i = 3 13 15 35 [83 84 63 96 57 39 79 61 40]
i = 4 13 15 35 39 [84 63 96 57 83 79 61 40]
i = 5 13 15 35 39 40 [63 96 57 83 79 61 84]
i = 6 13 15 35 39 40 57 [96 63 83 79 61 84]
i = 7 13 15 35 39 40 57 61 [63 83 79 96 84]
i = 8 13 15 35 39 40 57 61 63 [83 79 96 84]
i = 9 13 15 35 39 40 57 61 63 79 [83 96 84]
i = 10 13 15 35 39 40 57 61 63 79 83 [96 84]
i = 11 13 15 35 39 40 57 61 63 79 83 84 [96]
（3）快速排序。
关键字83 4063 13 84 35 96 57 39 79 61 15
第一趟排序后[15 40 63 13 61 35 79 57 39] 83 [96 84]
第二趟排序后[13] 15 [63 40 61 35 79 57 39] 83 84 [96]
第三趟排序后13 15 [39 40 61 35 57] 63 [79] 83 84 96
第四趟排序后13 15 [35] 39 [61 40 57] 63 79 83 84 96
第五趟排序后13 15 35 39 [57 40] 61 63 79 83 84 96
第六趟排序后13 15 35 39 40 [57] 61 63 79 83 84 96
第七趟排序后13 15 35 39 40 57 61 63 79 83 84 96
（4）堆排序。
关键字：834063138435965739796115
排序成功的序列：968483796361574039351513
（5）归并排序。
关键字83 4063 13 84 35 96 57 39 79 61 15
第一趟排序后[40 83] [13 63] [35 84] [57 96] [39 79] [15 61]
第二趟排序后[13 40 63 83] [35 57 84 96] [15 39 61 79]
第三趟排序后[13 35 40 57 63 83 84 96] [15 39 61 79]
第四趟排序后13 15 35 39 40 57 61 63 79 83 84 96
20 算法分析与设计
第8章
一、填空题
1. 一些确定的对象的整体
2.()()
=
A B C A B C
A B C A B C
=
，()()
3. 中序
4. 哈希函数装填因子
5. A B C
?
6. A=B
7. {a,b}
二、选择题
1. C
2. D
3. B
4. B
5. D
三、简答题
1. 文氏图如图A-9所示：
图A-9
2. 证明：对任意x，
x A B
∈-
?∈∧?
x A x B
?∈∧∈
x A x B
?∈
x A B
故A B A B
-= 。
3.
（1）
status contrary(HL){
// 使HL单链表中的所有结点按相反次序链接
p＝HL; //p指向未被逆序的第一个结点，初始指向原表头结点 HL＝nil; //HL指向逆序后的表头结点，初始值为空
while (p!=nil ){
q＝p; //q指向将被逆序链接的结点
p＝p＾.next;
q＾.next＝HL;
HL＝q;
}
}
（2）
status delete(HL,i){
多选题：第一章 1、工作分析要遵循的基本原则是（ABCD ） A系统原则B能级原则C标准化原则D最优化原则E经济原则 2、一个岗位能级的是由它在企业中的（BCDE ）等因素决定的 A工作时间B工作性质C任务繁简难易D承担责任大小E劳动强度 3、对任职者的资格条件分析包括（ABCDE ） A经验B技能C教育D培训E心理及生理因素 4、工作分析的内容有（ABCDE ） A工作职责分析B工作流程分析C工作权限分析D工作关系分析E工作环境条件分析 5、最常见的工作分析技术系统方法主要有（ABDE ） A工作分析问卷B任务清单分析系统C访谈法D能力需求分析系统E关键事件法 第二章 1、面谈法的具体形式有（ABE ） A与员工个别面谈B与员工集体面谈C与客户面谈D与供应商面谈E与主管领导面谈 2、工作分析的方法有（ABD ） A面谈法B问卷法C抽样调查D观察法E典型调查 3、问卷法中问卷的形式有（BCD ） A顺序式B开放式C封闭式D混合式E倒置式 4、问卷法的缺点是（ABCE ） A问卷编制的技术要求较高，成本费用较高B不同任职者对同样问题理解有偏差 C问卷回收率通常偏低D调查范围广E只适用于有文字理解和书面表达能力的人 5、明确编写关键事件的标准有（BC DE ） A能够说明工作的难度B特定而明确C能够简单描述行为发生的背景 D能够集中描述工作所展现出来的可观察到的行为E能够说明行为的结果 6、问卷法适用于（CD ） A任何人群B对文字理解有困难的人群C有文字理解能力的人群 D有书面表达能力的人群E对文字表达有困难的人群 7、观察法的种类有（ACD ） A直接观察法B间接观察法C阶段观察法D工作表演法E全程观察法 8、工作日志的填写要求有（ACE ） A工作日志随身携带，每天按工作活动发生的顺序及时填写 B针对特定对象的作业活动进行观察，记录有关工作信息
第三章作业及答案 一、单项选择题 1. 标志着以慈禧太后为首的清政府彻底放弃抵抗外国侵略者的事件是（） A ．《南京条约》的签订 B ．《天津条约》的签订 C ．《北京条约》的签订 D ．《辛丑条约》的签订 2 ．清末“预备立宪”的根本目的在于（） A ．仿效欧美政体 B ．发展资本主义 C ．延续反动统治 D ．缓和阶级矛盾 3.1903年6月，（）在上海《苏报》发表《驳康有为论革命书》，批驳康有为所谓“中国之可立宪，不可革命”的谬论 A.陈天华 B.邹容 C.章炳麟 D.梁启超 4.1903年邹容写的（）是中国近代史上第一部宣传革命和资产阶级共和国思想的着作 A.《猛回头》 B.《警世钟》 C.《革命军》 D.《驳康有为论革命书》 5.中国近代第一个资产阶级革命的全国性政党是( ) A.强学会 B.兴中会 C.同盟会 D.国民党 6. 孙中山民权主义思想的主张是( ) A.驱除鞑虏 B.恢复中华 C.创立民国 D.平均地权 7.1905年11月，孙中山在《民报》发刊词中将中国同盟会的政治纲领概括为（） A.创立民国、平均地权 B.驱除鞑虏、恢复中华、创立合众政府 C.民族主义、民权主义、民生主义 D.联俄、联共、扶助农工 8.武昌起义前同盟会领导的影响最大的武装起义是( )
A.浙皖起义 B.萍浏醴起义 C.镇南关起义 D.黄花岗起义 9.中国历史上第一部具有资产阶级共和国宪法性质的法典是（） A.《钦定宪法大纲》 B.《中华民国临时约法》 C.《中华民国约法》 D.《试训政纲领》 10.南京临时政府中占领导和主体地位的派别是（） A ．资产阶级维新派 B ．资产阶级保皇派 C ．资产阶级立宪派 D ．资产阶级革命派 11. 辛亥革命取得的最大成就是（） A.推翻了封建帝制 B.促进了资本主义的发展 C.使人民获得了一些民主自由权利 D.打击了帝国主义的殖民势力 12.清帝被迫退位，在中国延续两千多年的封建帝制终于覆灭的时间是（）。 A、1911年10月10日 B、1912年1月1日 C、1912年2月12日 D、1912年4月1日 13.中国第一次比较完全意义上的资产阶级民主革命是指（）。 A、辛亥革命 B、国民革命 C、北伐战争 D、抗日战争 14.1915年，（）在云南率先举起反袁护国的旗帜，发动护国战争 A.黄兴 B.段祺瑞 C.蔡锷 D.孙中山 15.资产阶级革命派开展护国运动的主要原因是 ( ) A.袁世凯指使刺杀宋教仁 B.袁世凯强迫国会选举他为正式大总统 C.袁世凯解散国会 D.袁世凯复辟帝制 16.袁世凯为复辟帝制不惜出卖主权，与日本签订了卖国的（） 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.下列关于工作分析作用陈述不正确的是( )。（P94） Ａ、工作分析即通过系统分析的方法来确定工作的职责及所需的知识和技能的过程 Ｂ、工作分析作用主要体现人力资源管理上 Ｃ、工作分析通过实现组织结构优化与职位体系的再设计，有效地支持企业战略 Ｄ、从优化组织结构角度讲工作分析有助于企业战略的稳定 Ｅ、工作分析可以明确工作在流程中的角色与权限，理顺与上下游环节之间的关系，提效率 2.下列关于工作分析在人力资源管理中作用陈述不正确的是( )。（P94-95） Ａ、当战略转移时，工作分析在明确职位设置、确定职位职责与任职者要求等方面给人力资源规划以支持 Ｂ、工作分析形成的工作规范规定了具体职位的工作性质、内容和要求,可以为员工职位培训提供信息支持和指导 Ｃ、工作分析直接支持薪酬体系的设计，优化企业内部的薪酬结构 Ｄ、工作分析形成的职位说明书与任职资格体系可成为制定绩效考核指标的书面依据 Ｅ、工作分析确立科学且具激励性的职业上升路线，有利于实现员工的职业生涯规划 3. 下列关于工作分析在人力资源管理中作用不包括( )方面。（P94-95） Ａ、优化工作流程 Ｂ、绩效管理 Ｃ、工作评价 Ｄ、薪酬管理 4. 下列关于工作分析流程顺序陈述正确的是( )。（P95） Ａ、调查工作相关的背景信息→确定工作分析目的→运用工作分析技术收集工作相关信息→整理和分析工作相关信息→形成工作分析结果→核对与应用工作分析结果 Ｂ、确定工作分析目的→调查工作相关的背景信息→运用工作分析技术收集工作相关信息→整理和分析工作相关信息→形成工作分析结果→核对与应用工作分析结果 Ｃ、确定工作分析目的→运用工作分析技术收集工作相关信息→调查工作相关的背景信息→整理和分析工作相关信息→形成工作分析结果→核对与应用工作分析结果 Ｄ、调查工作相关的背景信息→运用工作分析技术收集工作相关信息→确定工作分析目的→整理和分析工作相关信息→形成工作分析结果→核对与应用工作分析结果 5.下列关于工作分析流程陈述不正确的是( )。（P95） Ａ、工作分析首先要明确调查目的 Ｂ、应根据企业、职位性质选择适当的工作分析方法 Ｃ、工作分析结果是职位说明书 Ｄ、工作分析过程中调查工作相关的背景信息是基础性工作 Ｅ、要动态应用工作分析结果 6. 下列属于通用的工作分析方法的是( )。（P96） Ａ、访谈法 Ｂ、文献分析法
最全工作分析试题及答案 《工作分析》(课程代码06092) 第一大题：单项选择题1、以下不属于问卷调查法的优点是：A.规范，有利于计算机信息处理B.收集信息速度快，成本低C.方便，可随时安排调查D.调查深入2、关于轮换、工作扩大化和工作丰富化有以下几种说法，你认为哪种提法是正确的： A.工作轮换和工作扩大化没有区别，工作丰富化是增加职务的深度，例如一线职工可以参加某些管理活动。 B.工作轮换指在纵向和水平方向上使员工的业务活动多样化，而工作扩大化是指使员工的工作范围原有的基础上不断增加。 C.工作扩大化是意味着允许员工有更大的自主权、独立性责任感去完成一项完整的活动。+C 3、在工作分析的实践中，根据不同的调查目的，调查问卷采用的形式最好是： A.结构性问卷
B.封闭式问卷 C.开放性问卷 D.结构性和开放性结合4、工作分析的成果是：A.工作说明书 B.工作分析报告 C.工作评价 D.工作说明书和工作分析报告5、工作分析的核心和基础工作是： 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、以下不属于访谈法的优点是： A.对生理特征的分析非常有效 B.成本低 C.能发现新的工作信息 D.双向沟通，对任职者的了解较深入11、
1、怎样理解鸦片战争是中国近代史的起点？ 鸦片战争是中国近代史的开端，原因有四： 第一，战争后中国的社会性质发生了根本性变化，由一个落后封闭但独立自主的封建国家沦为一个半殖民地半封建社会。 第二，中国的发展方向发生变化，战前中国是一个没落的封建大国，封建制度已经腐朽，在缓慢地向资本主义社会发展；而鸦片战争后中国的民族资本主义不可能获得正常发展，中国也就不可能发展为成熟的资本主义社会，而最终选择了社会主义道路。 第三，社会主要矛盾发生变化，战前中国的主要矛盾是农民阶级与封建地主阶级的矛盾，而战后主要矛盾则包括农民阶级和地主阶级的矛盾及中华民族与外国殖民侵略者的矛盾，也就是社会主要矛盾复杂化。 第四，是革命任务发生变化，原先的革命任务是反对本国封建势力，战后则增加了反对外国殖民侵略的任务，革命的性质也由传统的农民战争转为旧民族主义革命。 2、怎样认识近代中国的主要矛盾、社会性质及其基本特征？ （1）近代中国的主要矛盾 帝国主义和中华民族的矛盾；封建主义和人民大众的矛盾是近代中国的主要矛盾。 （2）社会性质：半殖民地半封建的性质。 中国社会的半殖民地半封建社会，是近代以来中国在外国资本主义势力的入侵及其与中国封建主义势力相结合的条件下，逐步形成的一种从属于资本主义世界体系的畸形的社会形态。（3）基本特征 第一，资本——帝国主义侵略势力日益成为支配中国的决定性力量。 第二，中国的封建势力日益衰败并同外国侵略势力相勾结，成为资本——帝国主义压迫、奴役中国人民的社会基础和统治支柱。 第三，中国的自然经济基础虽然遭到破坏，但是封建剥削制度的根基——封建地主的土地所有制成为中国走向近代化和民主化的严重障碍。 第四，中国新兴的民族资本主义经济虽然已经产生，但是发展很缓慢，力量很软弱，且大部分与外国资本——帝国主义和本国封建主义都有或多或少的联系。 第五，由于近代中国处于资本——帝国主义列强的争夺和间接统治之下，近代中国各地区经济、政治和文化的发展是极不平衡的，中国长期处于不统一状态。 第六，在资本——帝国主义和封建主义的双重压迫下，中国的广大人民特别是农民日益贫困化以致大批破产，过着饥寒交迫和毫无政治权力的生活。 3、如何理解近代中国的两大历史任务及其相互关系？ （1）近代中国的两大历史任务： 第一，争取民族独立，人民解放；第二，实现国家富强，人民富裕。 （2）近代中国的两大历史任务的相互关系： 争取民族独立，人民解放和实现国家富强，人民富裕这两个历史任务，是互相区别又互相紧密联系的。 第一，由于腐朽的社会制度束缚着生产力的发展，阻碍着经济技术的进步，必须首先改变这种制度，争取民族独立和人民解放，才能为实现国家富强和人民富裕创造前提，开辟道路。第二，实现国家富强和人民富裕是民族独立，人民解放的最终目的和必然要求。 第一章 1、资本－帝国主义侵略给中国带来了什么？
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.以深度优先方式系统搜索问题解的算法称为__回溯法__。 背包问题的回溯算法所需的计算时间为__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 4.使用回溯法解0/1背包问题：n=3（3种物品），C=9（背包的容量
2017年10月高等教育自学考试 工作分析 (课程代码06092) 1. 本试卷分为两部分，第一部分为选择题，第二部分为非选择题。 2. 应考者必须按;i式题顺序在答题卡（纸）指定位置上作答，答在试卷上无效。 3. 涂写部分、画图部分必须使用2B铅笔，书写部分必须使用黑色字迹签字笔。 第一部分选择题?；n 单项选择题：本大题共25小题，每小题1分，共25分。在每小题列出的备选项中 只有一项是最符合题目要求的，请将其选出。 1. 被称为“科学管理之父”的是 A.狄德罗 B.泰勒 C.苏格拉底 D.闽斯特伯格 2. 职位分析问卷的提出者是 A.托纳 B.麦考密克 C.平托 D.赫茨伯格 3. 工作中为了达到某种目的而进行的一系列活动是 A.工作要素 B.任务 C.职责细分 D.职责 4. 某组织做工作分析，想把预算降到最低，应选择 A.访谈法 B.专家法 C.观察法 D.问卷调查法 5. 功能性职务分析法（FJA)认为所有的工作都涉及到 A. 工作执行者与数据、人、事的关系 B. 工作执行者与数据、组织、事的关系 C. 工作执行者与组织、人、事的关系 D. 工作执行者与数据、人、组织的关系 工作分析试题第1页（共5页) 6.和有关人员审查和确认信息属于工作分析基本流程中的 A.准备阶段 B.实施阶段 C.结果形成阶段 D.应用修订阶段 7.工作分析的目的是为了空缺职位的招聘，则侧重点在 A.薪酬 B.任职资格 C.工作关系 D.工作权限 8.在横向上增加工作任务，改善原来狭窄的工作范围，是工作多样化的工作设计方法 A.工作扩大化 B.工作轮换
C.工作专业化 D.工作丰富化 9. 职位评价是评估岗位的相对价值大小，评价结果是为了确定 a.绩效 b.薪酬 C.职责 D.任职资格 10. 工作分析的发展趋势是 A.工作分析系统化 B.对客户进行调查研究C.工作分析技术信息化D.职位说明书标准化 11. 工作中不能继续分解的最小动作单位，我们称为 A.工作要素 B.任务C.职责D.职组 12. 冰山素质模型中不可见素质是 A.知识与技能B.感知 C.动机 D.认知过程 13. 取得高层的支持和认可，一般需要在编写职位说明书的 A.准备时期 B.调查时期 C.分析和编写时期 D.正式运用时期 14. 职位分析问卷的缺点是 A. 应用时需要针对不同的组织进行调整 B. 不能为薪酬标准提供依据 C. 只考虑了工作，没有考虑员工 D. 时间成本大，且繁琐 15. 工作设计的客体是 A.各级管理者 B.有关员工 C.人力资源管理专家 D.组织的整体工作 16. 编制职务说明书的基本原则
第一章练习测试题 （一）填空 1、从分析的切入点划分，工作分析有（）、（）、（）三种类型。 2、工作分析的流程包括（）、（）、（）、（）、（）五个环节。 3、工作分析的表现形式有（）、（）、（）等。 4、在四种工作分析的结果中，（）是最直接、最原始、最基础的形式。 5、一般而言，任何复杂的工作系统都是从（）、（）、（）、（）四个层面进行分析的。 6、信息分析的内容一般包括五个方面，即（）、（）、（）、（）、（）。（二）单项选择 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、在工作分析中，关于隶属关系的描述应置于（）中。 A、工作名称 B、工作概要 C、工作识别 D、工作环境 （三）多项选择 1、下面关于工作分析的描述，哪些是正确的（） A、工作分析是人力资源开发与管理的基础 B、工作分析就是分析工作的过程，并对工作过程提出建议和指导 C、工作分析有助于量化管理 D、工作分析有助于人员测评、工作评价、定员、定额、人员招聘、职业发展与设计指导、薪酬管理及人员培训的科学化、规范化和标准化 2、下面关于工作描述的说法，哪些是正确的（） A、工作描述就是对工作自身结构概要的描述 B、工作描述就是工作说明书 C、工作描述是工作分析的直接结果形式 D、工作描述表现为工作说明书、资格说明书与职位说明书等 3、工作识别包括（） A、工作名称 B、其他识别标志 C、工作地 D、隶属关系 E、工作概要 4、关于工作说明书的用法，下面表述正确的是（） A、工作分析就是工作描述 B、是一个工作族中各种工作的划分 C、对一个类或子类中个人的工作的描述 D、指从事某一工作的员工的预期效果和其他收益 5、资格说明书可包括哪些内容（）
1.怎样认识近代中国的主要矛盾、社会性质及其基本特征？ （1）近代中国的主要矛盾 帝国主义和中华民族的矛盾；封建主义和人民大众的矛盾是近代中国的主要矛盾。中国近代社会的两对主要矛盾是互相交织在一起的，而帝国主义和中华民族的矛盾，是最主要的矛盾。 （2）社会性质：半殖民地半封建的性质。 中国社会的半殖民地半封建社会，是近代以来中国在外国资本主义势力的入侵及其与中国封建主义势力相结合的条件下，逐步形成的一种从属于资本主义世界体系的畸形的社会形态。 鸦片战争前的中国社会是封建社会。鸦片战争以后，随着外国资本-帝国主义的入侵，中国社会性质发生了根本性变化：独立的中国逐步变成半殖民地的中国；封建的中国逐步变成半封建的中国。 （3）基本特征 第一，资本--帝国主义侵略势力不但逐步操纵了中国的财政和经济命脉，而且逐步控制了中国的政治，日益成为支配中国的决定性力量。 第二，中国的封建势力日益衰败并同外国侵略势力相勾结，成为资本--帝国主义压迫、奴役中国人民的社会基础和统治支柱。 第三，中国的自然经济基础虽然遭到破坏，但是封建剥削制度的根基--封建地主的土地所有制依然在广大地区内保持着，成为中国走向近代化和民主化的严重障碍。 第四，中国新兴的民族资本主义经济虽然已经产生，并在政治、文化生活中起了一定作用，但是在帝国主义封建主义的压迫下，他的发展很缓慢，力量很软弱，而且大部分与外国资本--帝国主义和本国封建主义都有或多或少的联系。 第五，由于近代中国处于资本--帝国主义列强的争夺和间接统治之下，近代中国各地区经济、政治和文化的发展是极不平衡的，中国长期处于不统一状态。 第六，在资本--帝国主义和封建主义的双重压迫下，中国的广大人民特别是农民日益贫困化以致大批破产，过着饥寒交迫和毫无政治权力的生活。 中国半殖民地半封建社会及其特征，是随着帝国主义侵略的扩大，帝国主义与中国封建势力结合的加深而逐渐形成的。 2.如何理解近代中国的两大历史任务及其相互关系？ （1）近代中国的两大历史任务： 第一，争取民族独立，人民解放；第二，实现国家富强，人民富裕。 （2）近代中国的两大历史任务的相互关系： 争取民族独立，人民解放和实现国家富强，人民富裕这两个历史任务，是互相区别又互相紧
2018年10月高等教育自学考试 工作分析 (课程代码06092) 注意事项 1.本试卷分为两部分,第一部分为选择题,第二部分为非选择题。 2.应考者必须按试题顺序在答题卡(纸)指定位置上作答,答在试卷上无效。 3.涂写部分、画图部分必须使用2B铅笔,书写部分必须使用黑色字迹签字笔。 第一部分选择题 一、单项选择题:本大题共20小题,每小题1分,共20分。在每小题列出的备选项中 只有一项是最符合题目要求的,请将其选出 1.在职位说明书中,如“处理客户的电话咨询与投诉”,属于任职者的(B) A.任务 B.职责细分 C.职务 D.职责 2.某公司成立之初人力资源部门将组织内的所有工作纳入大类、中类、小类和等级所 构成的体系中,这一工作被称为(D) A.工作描述 B.工作规范 C.职位评价 D工作分类 3.春秋时期把分工称为“曲辨”的学者是(C) A.孔子 B.孟子 C.荀子 D.管仲 4.在历史上被认为是首次进行大规模工作分析的人是（A） A.丹尼斯·狄德罗 B.芒斯特伯格 C.泰勒 D.吉尔布雷斯 5.将心理学运用到工业研究中,探索如何取得最大工作效率的人是（C） A.巴鲁什 B.斯科特 C.丽果·芒斯特伯格 D.弗兰克·吉尔布雷斯 6.被认为是斯科特对工作分析的首要贡献事件是（B） A.面谈考核科学方法的形成 B.制订了军衔资格标准 C.入伍新兵分类 D.编写了人事配置表 7.为工作分析提供了最真实、客观与定性资料,广泛应用于非结构化工作分析的方法是(D)
A.工作要素法 B.任务清单法 C.关健事件法 D.功能性工作分析法 8.对不识字或工作繁忙没时间提笔回答问卷的人较为适用的工作分析方法是(D) A.工作日写实法 B.观察法 C.问卷法 D.访谈法 9.对某工人一工序进行测时记录为:1.2秒、1.3秒、1.5秒、1.6秒、1.4秒,按中位 值法计算,该工人在这道工序的标准时间是(A) A.1.4秒 B.1.5秒 C.1.6秒 D.1.7秒 10.在招聘和选拔人员时,当求职者不被期望在进入工作门槛时便拥有特定技能的情况下,选拔人员的最好方法是(C) A.主题专家会议法 B.关健事件分析法 C.能力要求法 D.观察法 11.在工作分析信息收集中,以下属于外部组织或人员渠道的是(C) A.职业数据 B.职业信息网 C.组织的上游供应商 D.职位的任职者 12.在职位描述中,对某职位主要做什么的内容,这部分常常被称为(B) A.工作规范 B.工作职责 C.工作描述 D.职务说明书 13.将被试者的得分与常模进行比较,得到被试者在常模人群中的位置,从而判断其是 否达到该职位的要求,这种能力要素的等级界定方法是(C) A.人群百分位法 B.等级行为描述法 C.利克特量表法 D.比较法 4.在分层分类能力要素体系中,公司所有职位的任职者都必须具备的能力要素属于(A) A.共用要素 B.通用要素 C.特殊要素 D.选择要素 15,将职位与特定的级别标准进行比较,且对职位要素进行量化评价的职位评价方法是(C) A.职位排序法
精心整理《工作分析》(课程代码06092) 第一大题：单项选择题 1、以下不属于问卷调查法的优点是：（D） A.规范，有利于计算机信息处理 B.收集信息速度快，成本低 C.方便，可随时安排调查 D.调查深入 2、关于轮换、工作扩大化和工作丰富化有以下几种说法，你认为哪种提法是正确的：（B） A. B. C. D.B+C 3 A. 4 A. B. C. D. 5 A. B.工作信息分析 C.明确工作分析的目的 D.编写工作说明书 6、工作的特点是简单、外显、不断重复，则对该项工作的分析适合用：（C） A.访谈分析法
B.工作日志法 C.观察法 D.问卷调查法 7、一份完整的工作说明书包括：（D） A.工作描述 B.工作规范 C.工作分析报告 D.工作描述和工作规范 8、下面哪种方法不适合对教师的工作分析：（B） A. B. C. D. 9 A. B. C.观察法 D. 10 A. B.成本低 C. D.双向沟通，对任职者的了解较深入 11、工作分析的方法主要指：（A） A.工作信息收集的方法 B.工作信息处理的方法 C.工作说明书的编写方法 D.工作评价的方法
12、工作分析思想溯源可追溯自：（C）. A.泰勒 B.狄德罗 C.苏格拉底 D.明斯特伯格 13、工作分析方法的选择依据是：（D） A.工作分析的目的 B.工作分析的内容 C.经济原则 D.A+B+C 14、以下属于隐性任职资格的有：（D） A.工作技能 B.工作经验 C.教育程度 D.任职者的内在能力和素质要求 15 A. B. C. D. 16 A.排列法 B.分类法 C.评分法 D. 17 A. B. C.外部专家由于对工作业务缺乏了解，某种程度上会影响工作分析进程 D.外部专家经验更丰富 18、记录和观察在某些工作领域内，员工在完成工作任务过程中有效或无效的工作行为导致的成功或失败的结果的工作分析方法是指（A） A.关键事件法 B.行为观察法
1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座B 上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi 塔问题的移动规则。由此设计出解Hanoi 塔问题的递归算确的为：（B ） 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. 深度优先 Hanoi 塔 B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); }
欢迎阅读 第一章 二、单项选择 1、办公室主任是（A） A、职位 B、职责 C、职务 D、职业 2、在四种工作分析的结果中，（D）涉及范围最广，最全面。 A、工作描述 B、工作说明书 C、资格说明书 D、职务说明书 3、工作活动中不能再继续分解的最小单位是（A） A、要素 B、任务 C、职责 D、职位 4、不同联系之间，职责的繁简难易、轻重大小及任职条件要求相似的所有职位的集合称为（D） A、职系 5、（D A 6 A 7 A、泰勒 1 A B C D 2 A B C D 3 A 4 A C D 5、资格说明书可包括哪些内容？（BCD） A、职位上下级关系 B、资格条件 C、考核项目 D、健康状况 E、心理素质 6、资格说明书的表现形式有（ACD） A、计分法 B、图表法 C、表格法 D、文字表达法 7、关于工作分析研究的发展趋向，以下表述正确的是（BCD） A、从描述性工作分析研究到预测性工作分析研究 B、从准确性工作分析研究转向战略性工作分析研究 C、从具体的任职要求工作分析研究到与胜任特征分析相结合的研究 D、从工具性的工作分析研究到工作分析影响因素研究 第二章
（二）单项选择 1. 下列关于岗位责任分析的原则，错误的是（A） A、用被动性的功能动词来描述?????? B、用专业术语 C、记录任务??????????????? D、注意任务的先后顺序 2.在工作姿势分析指标中，“站姿”、“坐姿”、“难适应的姿势”属于下列哪个要素？（B）?A、名称????B、标志???C、标度???D、解释 3、鱼刺图因素分解法主要用于（A） ?A、指标要素拟定和指标选择???????B、指标要素和标志定义 ?C、标度的划分与规定??????????D、标准的试用与评价 4.下列不属于子要素标志定义的一项是（C） ??A、设备责任????B、知识要求???C、工作流程???D、体力强度 5. ? A C 6. ?A 1 A C D 2 A 3 A C 4 A 5 A 6 A、 7 A C 8 A、目的 B、成本 C、工作性质 D、工作样本数量 9、下列关于分析工作经验要考虑的因素，正确的说法是（BCD） A．根据工作时间作出决定的性质 B、工作人员理论经验的深度和广度 C、工作中是否需要机器维修，装卸设备方面的知识 D、工作人员是否懂得其下属的工作 第三章 （二）单项选择 1、适用于外显行为的分析，不适用于隐蔽的心理素质的分析以及没有时间规律与表现规律
第一章工作分析概述 工作分析的概念: —种活动或者过程，是分析者采用科学的手段与技术，直接搜集、比较、综合有关的工作的信息，就工作岗位的状况、基本职责、资格要求等，做出规范性的描述与说明，为组织特定的发展战略、组织规划，为人力资源管理以及其他管理行为提供基本依据的一种管理活动。 工作分析的流程 设计计划信息分析结果表述运用指导 工作分析的相关术语（职位和职务） 要素：最小单位 任务：要素的集合 职责：任务的集合， 职位：工作的描述 职务：职责和职位的表述 职业： 职业生涯： 职系： 职组： 职门： 职级： 职等： 工作分析的性质和作用 Is是整个人力资源开发与管理科学化的基础 2、是提高现代社会生产力得需要 3、是组织现代化管理的客观需要 4、有助于实行量化管理 5、有助于工作评价、人员测评、人员招聘、薪酬管理以及人员培训、定员、定额、职业发展设计与指导的科学化、规范化和标准化 6、对于人力资源管理研究者也是不可缺少的 工作分析结果表述的四种形式: 1）工作描述： 内容：工作识别【内容：名称、工作地隶属关系、职业代码、职位等级、分析人名/单位、分析时间】工作概要、工作手段、工作材料、技术和方法、任务行为、环境、补充信息等。 2）工作说明书 3）资格说明书 4）职位说明书 四种工作分析结果的关系 工作描述是最原始、最直接、最基础的形式，其他三种形式都是在工作描述的基础上再生出来的和开发出来
的。
工作描述:最直接、最基础 工作说明书：事为中心，具体岗位、人员 资格说明书：任职资格条件 职务说明书:最全面、相对复杂 【课后习题】 -）填空 1、从分析的切入点划分，工作分析有（岗位导向型）、（人员导向型）、（过程导向型）三种类型。 2、 工作分析的流程包括（计划）、（设计）、（信息分析）、 3、 工作分析的表现形式有（工作说明书）、（资格说明书）、 5、一般而言，任何复杂的工作系统都是从（产出）、（投入）、（过程） 分析的。 6、 几乎所有的工作描述格式都包括（工作识别）和（工作概要）。 7、 信息分析的内容一般包括五个方面，即（工作名称分析）、（工作内容分析）、（工作环境分析）、 （工作条件分析）、（工作过程分析）。 8、 工作分析的思想与活动最早起源于（社会分工）。 二）单项选择 1、 办公室主任是（）。A A 职位 B 职责 C 职务 D 职业 2、 在四种工作分析的结果中，（）涉及范围最广、最全面。D A ?工作描述 B ?工作说明书 C ?职责 D ?职位 3、 工作活动中不能再继续分解的最小单位是（）。A A ?要素 B 任务 G 职责 D 职位 4、 不同职系之间，职责的繁简难易、轻重大小及任职条件要求相似的所有职位的集合称为（）。D A 职系 B ?职门 G 职级 D 职等 5、 （）是人力资源开发和管理科学化的基础。D A ?岗位设计 B ?薪酬设计 C ?培训考核 D ?工作分析 6、 在工作分析中，关于隶属关系的描述应置于（）中。C A ?工作名称 B ?工作概要 C ?工作识别 D ?工作环境 7、 将工程师的效率目标和心理学的研究目标结合起来，应用于工作分析的是（）。A A 、泰勒 B 、汤普森 C 、芒斯特伯格 D 、吉尔布雷思夫妇 三）多项选择 1、 下面关于工作分析的描述，哪些是正确的？ （ABCD ） A 、 工作分析是人力资源开发与管理的基础 B 、 工作分析就是分析工作的过程，并对工作过程提出建议和指导 C 、 工作分析有助于量化管理 D 、 工作分析有助于人员评测、工作评价、定员、定额、人员招聘、职业发展与设计指导、薪酬管理及人 员培训的科学化、规范化与标准化。 2、 下面关于工作描述的说法，哪些是正确的？ （ACD ） A 、 工作描述就是对工作自身结构概要的描述 B 、 工作描述就是工作说明书 C 、 工作描述是工作分析的直接结果形式 （结果表述）、（运用指导）五个环节。 （职务说明书）等。 4、在四种工作分析的结果中, （工作描述）是最直接、最原始、最基础的形式。 （关联因素）四个层面进行
上篇综述作业及答案 一、单项选择题 1.中国封建社会的基本生产结构是：（） A．手工业 B.农业经济 C.工业 D.小农经济 2.19世纪初，大肆向中国走私鸦片的国家是( ) A.美国 B.英国 C.日本 D.俄国 3.中国近代史上的第一个不平等条约是：（） A．《望厦条约》B．《南京条约》C．《辛丑条约》 D．《马关条约》 4.《南京条约》中割让的中国领土是：（） A.香港岛 B.九龙 C.新界 D.台湾 5.第一次鸦片战争中，美国强迫清政府签订的不平等条约是（） A.《黄埔条约》 B.《虎门条约》 C.《望厦条约》 D.《瑷珲条约》 6.中国近代史的起点是：（） A. 第一次鸦片战争 B. 第二次鸦片战争 C. 中日甲午战争 D. 八国联军侵华战争 7. 第一次鸦片战争后，中国逐步演变为：（） A. 封建主义性质的国家 B. 半殖民地半资本主义性质的国家 C. 资本主义性质的国家 D. 半殖民地半封建性质的国家 8.标志着中国半殖民地半封建社会起点的事件是（） A.英国的鸦片走私 B. 林则徐的虎门禁烟 C.1840年第一次鸦片战争 D.第二次鸦片战争 9.鸦片战争后，中国社会最主要的矛盾是:（） A．地主阶级和农民阶级的矛盾B．资本—帝国主义和中华民族的矛盾C．封建主义和人民大众的矛盾D．清朝统治和汉族的矛盾 10.鸦片战争前，中国社会经济中占统治地位的是:（） A．商品经济B．封建经济C．半殖民地经济D．资本主义经济 11.近代中国的历史表明，要争取争得民族独立和人民解放必须首先进行：（） A. 反对帝国主义侵略的斗争 B. 反帝反封建的资产阶级民主革命 C. 反对封建主义压迫的斗争 D. 反对资产阶级的社会主义革命 12.在近代中国，实现国家富强和人民富裕的前提条件是:（） A. 反对帝国主义的侵略 B. 争得民族独立和人民解放 C. 推翻封建主义的统治 D. 建立资本主义制度 13.中国工人阶级最早出现于：（） A.十九世纪四、五十年代 B.十九世纪六十年代 C.十九世纪六、七十年代 D.十九世纪七十年代 14.近代中国产生的新的被压迫阶级是：（） A农民阶级B工人阶级C资产阶级 D民族资产阶级 15.中国的资产阶级出现于：（） A.十九世纪四、五十年代 B.十九世纪六十年代 C.十九世纪六、七十年代 D.十九世纪七十年代 单项答案1. D 2.B 3. B 4. A 5. C 6. A 7.D 8. C 9. B 10. B 11.B 12. B 13. A 14. B 15. C
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x =