- 博客(14)
- 收藏
- 关注
RSS订阅原创 《操作系统——精髓与设计原理（第八版）》复习题抄录
手敲一遍，便于记忆；记录下来，便于复习。第一部分 背景知识第1章 计算机系统概述1.1 列出并简要定义计算机的4个主要组成部分。答：处理器（Processor）：控制计算机的操作，执行数据处理功能。内存（Main Memory）：存储数据和程序。输入/输出模块（I/O modules）：在计算机和外部环境之间移动数据。系统总线（System bus）：在处理器、内存和输入/输出模块...
2019-07-10 21:36:42
75613
3
原创 《算法导论》第三版第13章 红黑树 练习&思考题 个人答案
13.1 红黑树的性质13.1-1解：完全二叉搜索树：黑高为2的红黑树：黑高为3的红黑树：黑高为4的红黑树：13.1-2解：如果标红，不满足性质4，因为35是36的父结点，也是红色；如果标黑，不满足性质5，该条路径黑高超过其他路径。13.1-3解：可以验证所得到的树仍然满足5个条件，所以是红黑树。13.1-4解：（1）如果“吸收”前两个子结点都已经是黑色了，度为2...
2019-03-11 10:26:05
5173
2
原创 《算法导论》第三版第12章 二叉搜索树 练习&思考题 个人答案
12.1 什么是二叉搜索树12.1-1高度为 2:高度为3：高度为4：高度为5：高度为6：12.1-2解：最小堆的结点值总不大于孩子结点的值，而二叉搜索树的结点值不小于左子树元素结点的值，不大于右子树元素结点的值；最小堆性质无法在O(n)时间内按序输出一棵有n个结点树的关键字，因为堆（以最小堆为例）无法告知大于当前结点的最小元素是在左子树还是在右子树。换一个角度考虑，如果...
2019-03-05 11:07:50
3108
2
原创 《算法导论》第三版第31章 数论算法 练习&思考题 个人答案
31.1 基础数论概念31.1-1证明：cmod  a=(a+b)mod&a
2019-01-22 17:13:38
4130
原创 《算法导论》第三版第11章 散列表 练习&思考题 个人答案
11.1 直接寻址表11.1-1解：DIRECT-ADDRESS-FINDMAX(T)for i = T.length - 1 to 0 if T[i] != NIL return T[i]最坏情况O(m)O(m)O(m)。11.1-2思路：1代表存在，0代表不存在；插入置位，删除复位。11.1-3思路：可以将寻址表的每一个元素指向包含相同关键字的一个双...
2019-01-15 16:47:00
3767
原创 《算法导论》第三版第9章 中位数和顺序统计量 练习&思考题 个人答案
9.1 最小值和最大值9.1-1解：两两比较，直至找到最小值（共需n−1n-1n−1次），将曾与最小值比较过的值进行比较（共需⌈lgn⌉−1\lceil lgn\rceil -1⌈lgn⌉−1次）。n−1+⌈lgn⌉−1=n+⌈lgn⌉−2n-1+\lceil lgn\rceil -1=n+\lceil lgn\rceil -2n−1+⌈lgn⌉−1=n+⌈lgn⌉−29.1-2解：先...
2019-01-04 16:46:58
2238
原创 《算法导论》第三版第8章 线性时间排序 练习&思考题 个人答案
8.1 排序算法的下界8.2 计数排序8.2-1解：中间过程略，最后B是{0, 0, 1, 1, 2, 2, 3, 3, 4, 6, 6}，C是{0, 2, 4, 6, 8, 8, 9}8.2-28.2-3解：证明略，明显不稳定。8.2-4解：COUNTING-INTERVAL(A, a, b)let C[0..k] be a new arraycount = 0for i...
2019-01-04 11:25:28
1391
原创 《算法导论》第三版第7章 快速排序 练习&思考题 个人答案
7.1 快速排序的描述7.1-1解：13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 119, 19, 13, 5, 12, 8, 7, 4, 21, 2, 6, 119, 5, 13, 19, 12, 8, 7, 4, 21, 2, 6, 119, 5, 8, 19, 12, 13, 7, 4, 21, 2, 6, 119, 5, 8, 7, 12, 13,...
2019-01-03 16:13:05
1537
原创 《算法导论》第三版第6章 堆排序 练习&思考题 个人答案
思考题6-1 （用插入的方法建堆）a.解：否；假设输入数据为1，2，3……b.证明思路：MAX_HEAP_INSERT是一个Θ(lgn)的操作，并需要调用Θ(n)次。6-2 （对d叉堆的分析）a.解：PARENT(i) = ⌊i/d⌋，当i mod d = 0, 1PARENT(i) = ⌈i/d⌉，当i mod d = 2, … , d-1CHILD(i) = di-d+2...
2019-01-03 11:28:53
2401
原创 《算法导论》第三版第5章 概率分析和随机算法 练习&思考题 个人答案
注：本章内容需要一定的《概率论与随机过程》课程基础。思考题5-1 （概率计数）a.E[Xj] = o(1 - 1/(ni+1-ni)) + 1 · ((ni+1-ni) · 1/(ni+1-ni))=1nE[Xj] = nb.Var[Xj] = E[Xj2] - E2[Xj] = 99nVar[Xj] = 99n5-2 （查找一个无序数组）a.解：RANDOM-SEARCH...
2019-01-03 10:40:32
1240
原创 《算法导论》第三版第4章 分治策略 练习&思考题 个人答案
4.1 最大子数组问题4.1-1解：最大值。4.1-2解：VIOLENTLY-FIND-MAXIMUM-SUBARRAY(A)max_sum = -∞left = 0right = 0for i = 1 to A.length sum = A[i] if sum > max_sum max_sum = sum left = i...
2019-01-02 16:46:45
4007
1
原创 《算法导论》第三版第3章 函数的增长 练习&思考题 个人答案
注：由于本章主要是数学知识，要求一定的高等数学基础，且习题大多数为证明题（输入有一定困难。。），因此本章答案主要以证明思路为主。3.1 渐近记号3.1-1思路：首先仿照Θ记号的基本定义表出本题的定义，然后取c1和c2分别为1/2和1即可证明。3.1-2思路：对n+a和n+|a|的大小关系进行分类，可证明出当n足够大时，n/2≤n+a≤2n，之后取c1和c2分别为2-b和2b,n0=2|a...
2019-01-02 11:31:27
1935
1
原创 《算法导论》第三版第10章 基本数据结构 练习&思考题 个人答案
10.1 栈和队列10.1-1 仿照图10-1，画图表示依次执行操作PUSH(S, 4)、PUSH(S, 1)、PUSH(S, 3)、POP(S)、PUSH(S, 8)和POP(S)每一步的结果，栈S初始为空，存储于数组S[1…6]中。解：4→41→413→41→418→4110.1-2 说明如何在一个数组A[1…n]中实现两个栈，使得当两个栈的元素个数之和不为n时，两者都不会发生上溢。要...
2018-12-28 15:29:33
1972
1
原创 《算法导论》第三版第2章 算法基础 练习&思考题 个人答案
第2章 算法基础2.1 插入排序2.1-1 以图2-2为模型，说明INSERTION-SORT在数组A=<31, 41, 59, 26, 41, 58>上的执行过程。思路：仔细研究插入排序代码即可，无需思路，注意A中先后存在两个41，在排序过程中及排序后这两个41的先后顺序仍然不变，即插入排序具
2018-12-27 16:22:47
5938
5
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人