算法分析课后习题
- 格式：pdf
- 大小：226.28 KB
- 文档页数：18
算法分析课后习题
参考答案
第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 ) {
参考答案 3tmp = 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 -
=++-+-
++
121
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章
