算法设计与分析习题解答(第2版)

第1章算法引论11.1 算法与程序1

1.2 表达算法的抽象机制1

1.3 描述算法3

1.4 算法复杂性分析13

小结16

习题17

第2章递归与分治策略19

2.1 递归的概念19

2.2 分治法的基本思想26

2.3 二分搜索技术27

2.4 大整数的乘法28

2.5 Strassen矩阵乘法30

2.6 棋盘覆盖32

2.7 合并排序34

2.8 快速排序37

2.9 线性时间选择39

2.10 最接近点对问题43

2.11 循环赛日程表53

小结54

习题54

第3章动态规划61

3.1 矩阵连乘问题62

目录算法设计与分析(第2版)3.2 动态规划算法的基本要素67 3.3 最长公共子序列71

3.4 凸多边形最优三角剖分75

3.5 多边形游戏79

3.6 图像压缩82

3.7 电路布线85

3.8 流水作业调度88

3.9 0-1背包问题92

3.10 最优二叉搜索树98

小结101

习题102

第4章贪心算法107

4.1 活动安排问题107

4.2 贪心算法的基本要素110

4.2.1 贪心选择性质111

4.2.2 最优子结构性质111

4.2.3 贪心算法与动态规划算法的差异111

4.3 最优装载114

4.4 哈夫曼编码116

4.4.1 前缀码117

4.4.2 构造哈夫曼编码117

4.4.3 哈夫曼算法的正确性119

4.5 单源最短路径121

4.5.1 算法基本思想121

4.5.2 算法的正确性和计算复杂性123 4.6 最小生成树125

4.6.1 最小生成树性质125

4.6.2 Prim算法126

4.6.3 Kruskal算法128

4.7 多机调度问题130

4.8 贪心算法的理论基础133

4.8.1 拟阵133

4.8.2 带权拟阵的贪心算法134

4.8.3 任务时间表问题137

小结141

习题141

第5章回溯法146

5.1 回溯法的算法框架146

5.1.1 问题的解空间146

5.1.2 回溯法的基本思想147

5.1.3 递归回溯149

5.1.4 迭代回溯150

5.1.5 子集树与排列树151

5.2 装载问题152

5.3 批处理作业调度160

5.4 符号三角形问题162

5.5 n后问题165

5.6 0\|1背包问题168

5.7 最大团问题171

5.8 图的m着色问题174

5.9 旅行售货员问题177

5.10 圆排列问题179

5.11 电路板排列问题181

5.12 连续邮资问题185

5.13 回溯法的效率分析187

小结190

习题191

第6章分支限界法195

6.1 分支限界法的基本思想195

6.2 单源最短路径问题198

6.3 装载问题202

6.4 布线问题211

6.5 0\|1背包问题216

6.6 最大团问题222

6.7 旅行售货员问题225

6.8 电路板排列问题229

6.9 批处理作业调度232

小结237

习题238

第7章概率算法240

7.1 随机数241

7.2 数值概率算法244

7.2.1 用随机投点法计算π值244

7.2.2 计算定积分245

7.2.3 解非线性方程组247

7.3 舍伍德算法250

7.3.1 线性时间选择算法250

7.3.2 跳跃表252

7.4 拉斯维加斯算法259

7.4.1 n 后问题260

7.4.2 整数因子分解264

7.5 蒙特卡罗算法266

7.5.1 蒙特卡罗算法的基本思想266

7.5.2 主元素问题268

7.5.3 素数测试270

小结273

习题273

第8章 NP完全性理论278

8.1 计算模型279

8.1.1 随机存取机RAM279

8.1.2 随机存取存储程序机RASP287

8.1.3 RAM模型的变形与简化291

8.1.4 图灵机295

8.1.5 图灵机模型与RAM模型的关系297 8.1.6 问题变换与计算复杂性归约299 8.2 P类与NP类问题301

8.2.1 非确定性图灵机301

8.2.2 P类与NP类语言302

8.2.3 多项式时间验证304

8.3 NP完全问题305

8.3.1 多项式时间变换305

8.3.2 Cook定理307

8.4 一些典型的NP完全问题310

8.4.1 合取范式的可满足性问题311

8.4.2 3元合取范式的可满足性问题312 8.4.3 团问题313

8.4.4 顶点覆盖问题314

8.4.5 子集和问题315

8.4.6 哈密顿回路问题317

8.4.7 旅行售货员问题322

小结323

习题323

第9章近似算法326

9.1 近似算法的性能327

9.2 顶点覆盖问题的近似算法328

9.3 旅行售货员问题近似算法329

9.3.1 具有三角不等式性质的旅行售货员问题330 9.3.2 一般的旅行售货员问题331

9.4 集合覆盖问题的近似算法333

9.5 子集和问题的近似算法336

9.5.1 子集和问题的指数时间算法336

9.5.2 子集和问题的完全多项式时间近似格式337 小结340

习题340

第10章算法优化策略345

10.1 算法设计策略的比较与选择345

10.1.1 最大子段和问题的简单算法345

10.1.2 最大子段和问题的分治算法346

10.1.3 最大子段和问题的动态规划算法348

10.1.4 最大子段和问题与动态规划算法的推广349 10.2 动态规划加速原理352

10.2.1 货物储运问题352

10.2.2 算法及其优化353

10.3 问题的算法特征357

10.3.1 贪心策略357

10.3.2 对贪心策略的改进357

10.3.3 算法三部曲359

10.3.4 算法实现360

10.3.5 算法复杂性366

10.4 优化数据结构366

10.4.1 带权区间最短路问题366

10.4.2 算法设计思想367

10.4.3 算法实现方案369

10.4.4 并查集373

10.4.5 可并优先队列376

10.5 优化搜索策略380

小结388

习题388

第11章在线算法设计391

11.1 在线算法设计的基本概念391

11.2 页调度问题393

11.3 势函数分析395

11.4 k 服务问题397

11.4.1 竞争比的下界397

11.4.2 平衡算法399

11.4.3 对称移动算法399

11.5 Steiner树问题403

11.6 在线任务调度405

11.7 负载平衡406

小结407

习题407

词汇索引409

参考文献415

习题1-1 实参交换1

习题1-2 方法头签名1

习题1-3 数组排序判定1

习题1-4 函数的渐近表达式2

习题1-5 O(1) 和 O(2) 的区别2

习题1-7 按渐近阶排列表达式2

习题1-8 算法效率2

习题1-9 硬件效率3

习题1-10 函数渐近阶3

习题1-11 n !的阶4

习题1-12 平均情况下的计算时间复杂性4

算法实现题1-1 统计数字问题4

算法实现题1-2 字典序问题5

算法实现题1-3 最多约数问题6

算法实现题1-4 金币阵列问题8

算法实现题1-5 最大间隙问题11第2章递归与分治策略14 习题2-1 Hanoi 塔问题的非递归算法14

习题2-2 7个二分搜索算法15

习题2-3 改写二分搜索算法18

习题2-4 大整数乘法的 O(nm log(3/2))算法19

习题2-5 5次 n /3位整数的乘法19

习题2-6 矩阵乘法21

习题2-7 多项式乘积21

习题2-8 不动点问题的 O( log n) 时间算法22

习题2-9 主元素问题的线性时间算法22

习题2-10 无序集主元素问题的线性时间算法22

习题2-11 O (1)空间子数组换位算法23

习题2-12 O (1)空间合并算法25

习题2-13 n 段合并排序算法32

习题2-14 自然合并排序算法32

习题2-15 最大值和最小值问题的最优算法35

习题2-16 最大值和次大值问题的最优算法35

习题2-17 整数集合排序35

习题2-18 第 k 小元素问题的计算时间下界36

习题2-19 非增序快速排序算法37

习题2-20 随机化算法37

习题2-21 随机化快速排序算法38

习题2-22 随机排列算法38

习题2-23 算法qSort中的尾递归38

习题2-24 用栈模拟递归38

习题2-25 算法select中的元素划分39

习题2-26 O(n log n) 时间快速排序算法40

习题2-27 最接近中位数的 k 个数40

习题2-28 X和Y 的中位数40

习题2-29 网络开关设计41

习题2-32 带权中位数问题42

习题2-34 构造Gray码的分治算法43

习题2-35 网球循环赛日程表44目录算法设计与分析习题解答（第2版）算法实现题2-1 输油管道问题（习题2-30) 49

算法实现题2-2 众数问题（习题2-31) 50

算法实现题2-3 邮局选址问题（习题2-32) 51

算法实现题2-4 马的Hamilton周游路线问题（习题2-33) 51

算法实现题2-5 半数集问题60

算法实现题2-6 半数单集问题62

算法实现题2-7 士兵站队问题63

算法实现题2-8 有重复元素的排列问题63

算法实现题2-9 排列的字典序问题65

算法实现题2-10 集合划分问题（一）67

算法实现题2-11 集合划分问题（二）68

算法实现题2-12 双色Hanoi塔问题69

算法实现题2-13 标准二维表问题71

算法实现题2-14 整数因子分解问题72

算法实现题2-15 有向直线2中值问题72第3章动态规划76

习题3-1 最长单调递增子序列76

习题3-2 最长单调递增子序列的 O(n log n) 算法77

习题3-7 漂亮打印78

习题3-11 整数线性规划问题79

习题3-12 二维背包问题80

习题3-14 Ackermann函数81

习题3-17 最短行驶路线83

习题3-19 最优旅行路线83

算法实现题3-1 独立任务最优调度问题（习题3-3) 83

算法实现题3-2 最少硬币问题（习题3-4) 85

算法实现题3-3 序关系计数问题（习题3-5) 86

算法实现题3-4 多重幂计数问题（习题3-6) 87

算法实现题3-5 编辑距离问题（习题3-8) 87

算法实现题3-6 石子合并问题（习题3-9) 89

算法实现题3-7 数字三角形问题（习题3-10) 91

算法实现题3-8 乘法表问题（习题3-13) 92

算法实现题3-9 租用游艇问题（习题3-15) 93

算法实现题3-10 汽车加油行驶问题（习题3-16) 95

算法实现题3-11 圈乘运算问题（习题3-18) 96

算法实现题3-12 最少费用购物（习题3-20) 102

算法实现题3-13 最大长方体问题（习题3-21) 104

算法实现题3-14 正则表达式匹配问题（习题3-22) 105

算法实现题3-15 双调旅行售货员问题（习题3-23) 110

算法实现题3-16 最大 k 乘积问题（习题5-24) 111

算法实现题3-17 最小 m 段和问题113

算法实现题3-18 红黑树的红色内结点问题115第4章贪心算法123 习题4-2 活动安排问题的贪心选择123

习题4-3 背包问题的贪心选择性质123

习题4-4 特殊的0-1背包问题124

习题4-10 程序最优存储问题124

习题4-13 最优装载问题的贪心算法125

习题4-18 Fibonacci序列的Huffman编码125

习题4-19 最优前缀码的编码序列125

习题4-21 任务集独立性问题126

习题4-22 矩阵拟阵126

习题4-23 最小权最大独立子集拟阵126

习题4-27 整数边权Prim算法126

习题4-28 最大权最小生成树127

习题4-29 最短路径的负边权127

习题4-30 整数边权Dijkstra算法127

算法实现题4-1 会场安排问题（习题4-1) 128

算法实现题4-2 最优合并问题（习题4-5) 129

算法实现题4-3 磁带最优存储问题（习题4-6) 130

算法实现题4-4 磁盘文件最优存储问题（习题4-7) 131

算法实现题4-5 程序存储问题（习题4-8) 132

算法实现题4-6 最优服务次序问题（习题4-11) 133

算法实现题4-7 多处最优服务次序问题（习题4-12) 134

算法实现题4-8 d 森林问题（习题4-14) 135

算法实现题4-9 汽车加油问题（习题4-16) 137

算法实现题4-10 区间覆盖问题（习题4-17) 138

算法实现题4-11 硬币找钱问题（习题4-24) 138

算法实现题4-12 删数问题（习题4-25) 139

算法实现题4-13 数列极差问题（习题4-26) 140

算法实现题4-14 嵌套箱问题（习题4-31) 140

算法实现题4-15 套汇问题（习题4-32) 142

算法实现题4-16 信号增强装置问题（习题5-17) 143

算法实现题4-17 磁带最大利用率问题（习题4-9) 144

算法实现题4-18 非单位时间任务安排问题（习题4-15) 145

算法实现题4-19 多元Huffman编码问题（习题4-20) 147

算法实现题4-20 多元Huffman编码变形149

算法实现题4-21 区间相交问题151

算法实现题4-22 任务时间表问题151第5章回溯法153

习题5\|1 装载问题改进回溯法（一）153

习题5\|2 装载问题改进回溯法（二）154

习题5\|4 0-1背包问题的最优解155

习题5\|5 最大团问题的迭代回溯法156

习题5\|7 旅行售货员问题的费用上界157

习题5\|8 旅行售货员问题的上界函数158

算法实现题5-1 子集和问题（习题5-3) 159

算法实现题5-2 最小长度电路板排列问题（习题5-9) 160

算法实现题5-3 最小重量机器设计问题（习题5-10) 163

算法实现题5-4 运动员最佳匹配问题（习题5-11) 164

算法实现题5-5 无分隔符字典问题（习题5-12) 165

算法实现题5-6 无和集问题（习题5-13) 167

算法实现题5-7 n 色方柱问题（习题5-14) 168

算法实现题5-8 整数变换问题（习题5-15) 173

算法实现题5-9 拉丁矩阵问题（习题5-16) 175

算法实现题5-10 排列宝石问题（习题5-16) 176

算法实现题5-11 重复拉丁矩阵问题（习题5-16) 179

算法实现题5-12 罗密欧与朱丽叶的迷宫问题181

算法实现题5-13 工作分配问题（习题5-18) 183

算法实现题5-14 独立钻石跳棋问题（习题5-19) 184

算法实现题5-15 智力拼图问题（习题5-20) 191

算法实现题5-16 布线问题（习题5-21) 198

算法实现题5-17 最佳调度问题（习题5-22) 200

算法实现题5-18 无优先级运算问题（习题5-23) 201

算法实现题5-19 世界名画陈列馆问题（习题5-25) 203

算法实现题5-20 世界名画陈列馆问题（不重复监视）（习题5-26) 207 算法实现题5-21 部落卫队问题（习题5-6) 209

算法实现题5-22 虫蚀算式问题211

算法实现题5-23 完备环序列问题214

算法实现题5-24 离散01串问题217

算法实现题5-25 喷漆机器人问题218

算法实现题5-26 n 2-1谜问题221第6章分支限界法229

习题6-1 0-1背包问题的栈式分支限界法229

习题6-2 用最大堆存储活结点的优先队列式分支限界法231

习题6-3 团顶点数的上界234

习题6-4 团顶点数改进的上界235

习题6-5 修改解旅行售货员问题的分支限界法235

习题6-6 解旅行售货员问题的分支限界法中保存已产生的排列树237 习题6-7 电路板排列问题的队列式分支限界法239

算法实现题6-1 最小长度电路板排列问题一（习题6-8) 241

算法实现题6-2 最小长度电路板排列问题二（习题6-9) 244

算法实现题6-3 最小权顶点覆盖问题（习题6-10) 247

算法实现题6-4 无向图的最大割问题（习题6-11) 250

算法实现题6-5 最小重量机器设计问题（习题6-12) 253

算法实现题6-6 运动员最佳匹配问题（习题6-13) 256

算法实现题6-7 n 后问题（习题6-15) 259

算法实现题6-8 圆排列问题（习题6-16) 260

算法实现题6-9 布线问题（习题6-17) 263

算法实现题6-10 最佳调度问题（习题6-18) 265

算法实现题6-11 无优先级运算问题（习题6-19) 268

算法实现题6-12 世界名画陈列馆问题（习题6-21) 271

算法实现题6-13 骑士征途问题274

算法实现题6-14 推箱子问题275

算法实现题6-15 图形变换问题281

算法实现题6-16 行列变换问题284

算法实现题6-17 重排 n 2宫问题285

算法实现题6-18 最长距离问题290第7章概率算法296

习题7-1 模拟正态分布随机变量296

习题7-2 随机抽样算法297

习题7-3 随机产生 m 个整数297

习题7-4 集合大小的概率算法298

习题7-5 生日问题299

习题7-6 易验证问题的拉斯维加斯算法300

习题7-7 用数组模拟有序链表300

习题7-8 O(n 3/2)舍伍德型排序算法300

习题7-9 n 后问题解的存在性301

习题7-11 整数因子分解算法302

习题7-12 非蒙特卡罗算法的例子302

习题7-13 重复3次的蒙特卡罗算法303

习题7-14 集合随机元素算法304

习题7-15 由蒙特卡罗算法构造拉斯维加斯算法305

习题7-16 产生素数算法306

习题7-18 矩阵方程问题306

算法实现题7-1 模平方根问题（习题7-10) 307

算法实现题7-2 集合相等问题（习题7-17) 309

算法实现题7-3 逆矩阵问题（习题7-19) 309

算法实现题7-4 多项式乘积问题（习题7-20) 310

算法实现题7-5 皇后控制问题311

算法实现题7-6 3-SAT问题314

算法实现题7-7 战车问题315

算法实现题7-8 圆排列问题317

算法实现题7-9 骑士控制问题319

算法实现题7-10 骑士对攻问题320第8章NP完全性理论322 习题8-1 RAM和RASP程序322

习题8-2 RAM和RASP程序的复杂性322

习题8-3 计算 n n 的RAM程序322

习题8-4 没有MULT和DIV指令的RAM程序324

习题8-5 MULT和DIV指令的计算能力324

习题8-6 RAM和RASP的空间复杂性325

习题8-7 行列式的直线式程序325

习题8-8 求和的3带图灵机325

习题8-9 模拟RAM指令325

习题8-10 计算2 2 n 的RAM程序325

习题8-11 计算 g(m,n)的程序 326

习题8-12 图灵机模拟RAM的时间上界326

习题8-13 图的同构问题326

习题8-14 哈密顿回路327

习题8-15 P类语言的封闭性327

习题8-16 NP类语言的封闭性328

习题8-17 语言的2 O (n k) 时间判定算法328

习题8-18 P CO -NP329

习题8-19 NP≠CO -NP329

习题8-20 重言布尔表达式329

习题8-21 关系∝ p的传递性329

习题8-22 L ∝ p 330

习题8-23 语言的完全性330

习题8-24 的CO-NP完全性330

习题8-25 判定重言式的CO-NP完全性331

习题8-26 析取范式的可满足性331

习题8-27 2-SAT问题的线性时间算法331

习题8-28 整数规划问题332

习题8-29 划分问题333

习题8-30 最长简单回路问题334第9章近似算法336

习题9-1 平面图着色问题的绝对近似算法336

习题9-2 最优程序存储问题336

习题9-4 树的最优顶点覆盖337

习题9-5 顶点覆盖算法的性能比339

习题9-6 团的常数性能比近似算法339

习题9-9 售货员问题的常数性能比近似算法340

习题9-10 瓶颈旅行售货员问题340

习题9-11 最优旅行售货员回路不自相交342

习题9-14 集合覆盖问题的实例342

习题9-16 多机调度问题的近似算法343

习题9-17 LPT算法的最坏情况实例345

习题9-18 多机调度问题的多项式时间近似算法345

算法实现题9-1 旅行售货员问题的近似算法（习题9-9) 346 算法实现题9-2 可满足问题的近似算法（习题9-20) 348

算法实现题9-3 最大可满足问题的近似算法（习题9-21) 349 算法实现题9-4 子集和问题的近似算法（习题9-15) 351

算法实现题9-5 子集和问题的完全多项式时间近似算法352

算法实现题9-6 实现算法greedySetCover（习题9-13) 352

算法实现题9-7 装箱问题的近似算法First Fit（习题9-19) 356

算法实现题9-8 装箱问题的近似算法Best Fit（习题9-19) 358

算法实现题9-9 装箱问题的近似算法First Fit Decreasing（习题9-19) 360

算法实现题9-10 装箱问题的近似算法Best Fit Decreasing（习题9-19) 361

算法实现题9-11 装箱问题的近似算法Next Fit361第10章算法优化策略365 习题10-1 算法obst的正确性365

习题10-2 矩阵连乘问题的 O(n 2) 时间算法365

习题10-6 货物储运问题的费用371

习题10-7 Garsia算法371

算法实现题10-1 货物储运问题（习题10-3) 374

算法实现题10-2 石子合并问题（习题10-4) 374

算法实现题10-3 最大运输费用货物储运问题（习题10-5) 375

算法实现题10-4 五边形问题377

算法实现题10-5 区间图最短路问题（习题10-8) 381

算法实现题10-6 圆弧区间最短路问题（习题10-9) 381

算法实现题10-7 双机调度问题（习题10-10) 382

算法实现题10-8 离线最小值问题（习题10-11) 390

算法实现题10-9 最近公共祖先问题（习题10-12) 393

算法实现题10-10 达尔文芯片问题395

算法实现题10-11 多柱Hanoi塔问题397

算法实现题10-12 线性时间Huffman算法400

算法实现题10-13 单机调度问题402

算法实现题10-14 最大费用单机调度问题405

算法实现题10-15 飞机加油问题408

第11章在线算法设计410

习题11-1 在线算法LFU的竞争性410

习题11-4 多读写头磁盘问题的在线算法410

习题11-6 带权页调度问题410

算法实现题11-1 最优页调度问题（习题11-2) 411

算法实现题11-2 在线LRU页调度（习题11-3) 414

算法实现题11-3 k 服务问题（习题11-5) 416

参考文献422

新编基础物理学第二版第二章习题解答

9习题二 2-1.两质量分别为m和M (M m)的物体并排放在光滑的水平桌面上，现有一水平力F作用在物体m上，使两物体一起向右运动，如题图2-1所示，求两物体间的相互作用力。若水平力F作用在M上, 使两物体一起向左运动，则两物体间相互作用力的大小是否发生变化？ 解：以m、M整体为研究对象, F 以m为研究对象，如解图2-1 有 (m M )a…①(a),有 F Mm ma…② 由①、②两式，得相互作用力大小 l MF F Mm . “ m M 若F作用在M上，以m为研究对象，如题图2-1 (b)有 F Mm ma 由①、③两式，得相互作用力大小解图2-1 F Mm 讦发生变化。 m M 2-2.在一条跨过轻滑轮的细绳的两端各系一物体，两物体的质量分别为 M2，在M2上再放一质量为m的小物体，如题图2-2所示，若M1=M2= 4m,求m和M2之间的相互作用 力，若M1=5m, M2=3m,则m与M2之间的作用力是否发生变化？ M1和 解：受力图如解图2-2，分别以M1、M2和m为研究对象，有题图2-2 又T1T2，则当M1 当M1 T1 M1g M1a (M2 m)g T2 (M 2 m)a mg F M 2m ma C O F M 2m 2M 〔mg m M1 M2 M 2 4m 时 解图2-2 F M2m8mg 5m, M 2 3m 时 F M 2m10mg 9 发生变化。 题图2-1

2-3?质量为M的气球以加速度v匀加速上升，突然一只质量为m的小鸟飞到气球上，并停留在气球上。若气球仍能向上加速，求气球的加速度减少了多少？ r 解：设f为空气对气球的浮力，取向上为正。 分别由解图2-3(a)、(b)可得 f M g Ma mag a a a1 m M 2-4.如题图2-4所示，人的质量为60kg，底板的质量为在底板上静 止不动，则必须以多大的力拉住绳子？ 解:设底板和人的质量分别为M , m,以向上为正方向， (a)、(b)所示，分别以底板、人为研究对象，则有 T| T2 F Mg 0 T3 F ' mg 0 F为人对底板的压力， F '为底板对人的弹力。有 F F 又因为 f (M m) g (M m)a1 由此解得 a i Ma mg m M ?0 (a) ⑹ 解图2-3 则 T 2 T 3 也严 245N 40 kg。人若想站 受力图如解图2-4 解图2-12

操作系统习题及答案四

四、计算题 1某虚拟存储器的用户编程空间共32个页面，每页为1KB,内存为16KBo假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下： 则逻辑地址0A5C（H）所对应的物理地址是什么？要求：写出主要计算过程。 1. 解：页式存储管理的逻辑地址分为两部分：页号和页内地址。由已知条件用户编程空间共32个页面”可知页号部分占5位；由每页为1KB” 1K=210,可知内页地址占10位。由内存为16KB'，可知有16块，块号为4位。 逻辑地址0A5C（ H）所对应的二进制表示形式是：000 1010 0101 1100 ，根据上面的 分析，下划线部分为页内地址，编码000 10 ”为页号，表示该逻辑地址对应的页号为2o 查页表，得到物理块号是11（十进制），即物理块地址为：10 11,拼接块内地址10 0101 1100, 得10 1110 0101 1100 ，即2E5C（ H）o 2、对于如下的页面访问序列： 1, 2 , 3 , 4 , 1 , 2 , 5 , 1 , 2 , 3 , 4 , 5 当内存块数量为3时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？写出依次产生缺页中断后应淘汰的页。（所有内存开始时都是空的，凡第一次用到的页面都产生一 次缺页中断。要求写出计算步骤。） 2. 解： 采用先进先出（FIFO ）调度算法，页面调度过程如下： 共产生缺页中断9次。依次淘汰的页是1、2、3、4、1、2 共产生缺页中断10次。依次淘汰的页是1、2、3、4、5、1、2o 3、下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、 20K、200K o若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？ 空闲分区表

仪器分析习题解答第二版化学工业出版社

北京化工大学 仪器分析习题解答 董慧茹编 2010年6月

第二章 电化学分析法习题解答 25. 解： pHs = 4.00 , Es = 0.209V pHx = pHs ＋059 .0Es Ex - (1) pHx 1 = 4.00 + 059.0209 .0312.0- = 5.75 (2) pHx 2 = 4.00 ＋059 .0209 .0088.0- = 1.95 (3) pHx 3 = 4.00 ＋059 .0209 .0017.0-- = 0.17 26. 解： [HA] = 0.01mol/L , E = 0.518V [A -] = 0.01mol/L , ΦSCE = 0.2438V E = ΦSCE － Φ2H+/H2 0.518 = 0.2438 － 0.059 lg[H +] [H +] = k a ][] [- A HA = 01.001.0k a 0.518 = 0.2438 － 0.059 lg 01 .001 .0k a lg k a = - 4.647 k a = 2.25×10-5 27. 解： 2Ag + + CrO - 24 = Ag 2CrO 4 [Ag +]2 = ] [24- CrO Ksp

Ag CrO Ag SCE E /42φφ-= - 0.285 = 0.2438 - [0.799 + 2 24)] [lg(2059.0-CrO Ksp ] ][lg 24-CrO Ksp = - 9.16 , ] [24- CrO Ksp = 6.93×10-10 [CrO - 24 ] = 10 1210 93.6101.1--?? = 1.59×10-3 (mol/L) 28. 解：pBr = 3 , a Br- = 10-3mol/L pCl = 1 , a Cl- = 10-1mol/L 百分误差 = - - --?Br Cl Cl Br a a K ,×100 = 3 1 31010106---??×100 = 60 因为干扰离子Cl -的存在，使测定的a Br- 变为： a -Br = a -Br ＋K --Cl Br .×a -Cl = 10-3＋6×10-3×10-1=1.6×10-3 即a -Br 由10-3mol/L 变为1.6×10-3mol/L 相差3.0 - 2.8 = 0.2 pBr 单位 29. 解：

梁小民《西方经济学-第二版》第二章课后习题答案知识分享

第二章供求、供给、价格 1、为什么欲望不同于需求？ 答：欲望是一种缺乏的感受和需要满足的愿望，其基本特点是无限性，即人的欲望永远没有完全得到满足的时候。 需求是指消费者（家庭）在某一特定时期内，在每一价格水平时愿意而且能够购买的某种商品量。需求是购买欲望和购买能力的统一，缺少任何一个条件都不能成为需求。 欲望是永无止境的，没有限制条件，而需求受到购买欲望和购买能力的制约，二者缺一不可，所以欲望不同于需求。 1、有些企业在广告宣传中声称自己的产品是为“工薪阶级服务的”。从经济学角度看，这种说法对不对？为什么？ 答：从经济学角度看，这种说法是不对的。 企业宣传自己的产品是为工薪阶层服务，主要是指在价格上给予工薪阶层方便，通过降低价格，提供经济实惠又保质的产品，吸引消费者，让消费者有经济能力来购买产品。 需求是购买欲望和购买能力的的统一，二者缺一不可。产品为工薪阶层服务，旨在强调消费者的购买能力，却忽略了其购买欲望。所以，从经济学角度看，这种说法是不正确的。 2、出租车行业越发达，服务越好，价格越低，买汽车的人越少，为什么? 答：替代品是指可以互相替代来满足同一种欲望的商品。出租车和汽车，皆可为人们提供出行便利服务，它们之间可以相互替代，是

替代关系。 对于有替代关系的商品，当一种商品价格下降时，人们对其需求增加，导致另一种商品需求下降。当出租车行业发达，价格低廉，服务良好时，人们会增加对出租车的消费需求，从而减少对汽车的购买需求。 4、旅游业的发展可以带动旅馆、餐饮、交通、娱乐等行业的发展，为什么？ 答：互补品是指共同满足一种欲望的两种商品，他们是相互补充的，旅游业与旅馆、餐饮、交通、娱乐等行业就是一种互补关系。两种互补品价格与需求呈反向变动，当旅游业发展，价格降低，消费者而对其互补的旅馆、餐饮、交通、娱乐等的需求就增加，从而带动其发展。 5、我国加入世贸组织对汽车市场的需求有什么影响？为什么？ 答：总体上来说会扩大对汽车市场的需求。首先，我国加入世贸组织后，经济发展，人民收入增加，消费者对汽车有了一定的购买力，其次，加入世贸组织使得汽车价格下架昂，对汽车的购买需求增多。再次，加入世贸组织使得发达国家的消费方式影响发展中国家，购买汽车会成为人们的偏好与心理欲望。最后，加入世贸组织，消费者对自己未来的收入与商品价格走势有所预期，这种预期也影响了购车的意愿和需求。综上，我国加入世贸组织会扩大汽车市场的需求。

第四章部分习题答案

习题四 3、何谓静态链接？何谓装入时动态链接和运行时的动态链接？ 答：(1) 静态链接。在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。 (2) 装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。 (3) 运行时动态链接。这是指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。 6、为什么要引入动态重定位？如何实现？ 答：（1）在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。这种不能被利用的小分区称为“零头”或“碎片”。为了消除零头所以要引入动态重定位。 （2）在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态重定位。 14、较详细地说明引入分段存储管理是为了满足用户哪几方面的需要。 答：1) 方便编程 通常，用户把自己的作业按照逻辑关系划分为若干个段，每个段都是从0 开始编址，并有自己的名字和长度。因此，希望要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的。

习题7及其解答第二版

第7章继承 习题7 7.1 选择题 1．在c++中，类之间的继承关系具有( c )。 (a) 自反性 (b) 对称性 (c) 传递性 (d) 反对称性 2．下列关于类的继承描述中，( d )是正确的。 (a) 派生类公有继承基类时，可以访问基类的所有数据成员，调用所有成员函数 (b) 派生类也是基类，所以它们是等价的 (c) 派生类对象不会建立基类的私有数据成员，所以不能访问基类的私有数据成员 (d) 一个基类可以有多个派生类，一个派生类可以有多个基类 3．当一个派生类公有继承一个基类时，基类中的所有公有成员成为派生类的( a )。 (a) public成员(b)private成员(c) protected成员(d)友员 4．当一个派生类私有继承一个基类时，基类中的所有公有成员和保护成员成为派生类的( b )。 (a) public成员(b)private成员(c) protected成员(d)友员 5．当一个派生类保护继承一个基类时，基类中的所有公有成员和保护成员成为派生类的( c )。 (a) public成员(b)private成员(c) protected成员(d)友员 6．不论派生类以何种方式继承基类，都不能直接使用基类的( b )。 (a) public 成员(b)private成员 (c) protected成员(d)public 成员和protected成员 7．下面描述中，错误的是( d )。 (a) 在基类定义的public成员在公有继承的派生类中可见，也能在类外被访问 (b) 在基类定义的protected成员在私有继承的派生类中可见 (c) 在基类定义的静态成员在私有继承的派生类中可见 (d) 访问声明可以在公有继承派生类中把基类的public成员声明为private成员 8．在c++中，可以被派生类继承的函数是( a )。 (a) 成员函数(b)构造函数(c) 析构函数(d)友员函数 9．在创建派生类对象时，构造函数的执行顺序是( d )。 (a) 对象成员构造函数、基类构造函数、派生类本身的构造函数 (b) 派生类本身的构造函数、基类构造函数、对象成员构造函数 (c) 基类构造函数、派生类本身的构造函数、对象成员构造函数 (d) 基类构造函数、对象成员构造函数、派生类本身的构造函数 10．当不同的类具有相同的间接基类时，有特点( c )。 (a) 各派生类对无法按继承路线产生自己的基类版本 (b) 为了建立惟一的间接基类版本，应该声明间接基类为虚类 (c) 为了建立惟一的间接基类版本，应该声明派生类虚继承基类 (d) 一旦声明虚继承，基类的性质就改变了，不能再定义新的派生类 7.2 阅读下列程序，写出执行结果 1．#include

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

算法设计与分析第2版 王红梅 胡明 习题答案

精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low=prvotkey)

基础工程(第二版)第二章习题解答

习 题 【2-1】如图2-31所示地质土性和独立基础尺寸的资料，使用承载力公式计算持力层的承载力。若地下水位稳定由0.7m 下降1m ，降至1.7m 处，问承载力有何变化？ 图2-31 习题2-1图 解：由图2－31可知： 基底处取土的浮重度 3/2.88.90.18'm kN w sat =-=-=γγγ 基底以上土的加权平均重度 3/0.133 .16.02.8)6.03.1(2.17m kN m =?+-?＝γ 由020=k ?，查表2－6可得 66.5,06.3,51.0===c d b M M M 所以，持力层的承载力为 kPa c M d M b M f k c m d b a 9.64166.53.10.1306.38.12.851.0=?+??+??=++=γγ 若地下水下降1m 至1.7m ，则 基底以上土的重度为 3/2.17m kN m ＝γ 基底处土的重度为 3/0.18m kN m ＝γ 此时，持力层的承载力为 kPa c M d M b M f k c m d b a 0.86166.53.12.1706.38.10.1851.0=?+??+??=++=γγ

【2-2】某砖墙承重房屋，采用素混凝土(C10)条形基础，基础顶面处砌体宽度0b =490mm ，传到设计地面的荷载F k =220kN/m ，地基土承载力特征值f ak =144kPa ，试确定条形基础的宽度b 。 (1)按地基承载力要求初步确定基础宽度 假定基础埋深为d=1.2m ，不考虑地基承载力深度修正，即f a =f ak =144kPa m d f F b G a k 83.12 .120144220=?-=-≥γ，取b=1.9m 初步选定条形基础的宽度为1.9m 。 地基承载力验算： kPa f kPa b G F p a k k k 1448.1399 .12.19.120220=<=??+=+= 满足 无筋扩展基础尚需对基础的宽高比进行验算（其具体验算方法详见第三章），最后还需进行基础剖面设计。 (2)按台阶宽高比要求验算基础的宽度 初步选定基础的高度为H=300mm 基础采用C10素混凝土砌筑，基础的平均压力为kPa p k 8.139= 查表3－2，得允许宽高比0.12==H b tg α，则 m Htg b b 09.10.13.0249.020=???+=+≤α 不满足要求 m tg b b H 705.00 .1249.09.120=?-=-≥α 取H=0.8m m Htg b b 09.20.18.0249.020=??+=+≤α 此时地面离基础顶面为 1.2-0.8=0.4m>0.1m ，满足要求。

算法设计与分析第2版 王红梅 胡明 习题答案

习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Le ｏn ｈar ｄ Ｅul ｅr,１7０7 —17８3)提出并解决了该问题。七桥问题就是这样描述的:一个人就是否能在一次步行中穿越哥尼斯堡(现在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经 过一次,图1、７就是这条河以及河上的两个岛 与七座桥的草图。请将该问题的数据模型抽象 出来,并判断此问题就是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1， 一次步行 2， 经过七座桥,且每次只经历过一次 3， 回到起点 该问题无解:能一笔画的图形只有两类:一类就是所有的点都就是偶点。另一类就是只有二个奇点的图形。 2、在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不就是除法而就是减法。请用伪代码描述这个版本的欧几里德算法 １、r=m-n ２、循环直到r=0?2、１ m ＝n ２、２ n=r ２、3 ｒ=ｍ-n ?3 输出m ３.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码与C ++描述。 //采用分治法 /／对数组先进行快速排序 ／/在依次比较相邻的差 #inc ｌud ｅ ＜ｉostream> ｕsin ｇ n ａｍｅs ｐａc ｅ ｓｔd; in ｔ ｐa ｒｔion ｓ(int b[］,ｉnt l ｏw,ｉnt ｈi ｇｈ) { ｉｎt pr ｖｏtkey=b[lo ｗ]; b ［０］＝b[lo ｗ]; 图1、7 七桥问题

ｗｈile (lｏw<ｈigh) ｛ ｗhilｅ(lｏw＝ｐrvotkey) -－ｈigｈ; ｂ[low]=ｂ[ｈigｈ]; wｈile (low

操作系统复习题答案

操作系统复习题 一、单项选择题：在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．操作系统的主要功能是管理计算机系统中的（）。【D 】A．程序B．数据 C．文件D．资源 2．产生死锁的基本原因是（）和进程推进顺序非法。【 A 】A．资源分配不当B．系统资源不足 C．作业调度不当D．进程调度不当 3．动态重定位是在作业的（）中进行的。【D 】A．编译过程B．装入过程 C．连接过程D．执行过程 4．存放在磁盘上的文件，（）。【A 】A．既可随机访问又可顺序访问B．只能随机访问 C．只能顺序访问D．只能读写不能访问 5．对于硬盘上存放的信息，物理上读写的最小单位是一个（）。【C 】A．二进制（bit）B．字节(byte) C．物理块D．逻辑记录 6．操作系统中利用信号量和P、V操作，（）。【C 】A．只能实现进程的互斥B．只能实现进程的同步 C．可实现进程的互斥与同步D．可完成进程调度 7．SPOOLing技术可以实现设备的（）。【C 】A．独占B．共享 C．虚拟D．物理 8．在存储管理的各方案中，可扩充主存容量的方案是（）存储管理。【D 】A．固定分区B．可变分区 C．连续D．页式虚拟 9．磁盘是可共享的设备，每一时刻（）进程与它交换信息。【C 】A．允许有两个B．可以有任意多个 C．最多一个D．至少有一个 10．逻辑文件存放到存储介质上时，采用的组织形式是与（）有关。【B 】 ×××××试题答案及评分参考（×）第1页（共×页）

A．逻辑文件结构B．存储介质特性 C．主存管理方式D．分配外设方式 11．在操作系统中，（）是竞争和分配计算机系统资源的基本单位。【B 】A．程序B．进程 C．作业D．线程 12．作业调度的关键在于（）。【C 】A．选择恰当的进程管理程序B．用户作业准备充分 C．选择恰当的作业调度算法D．有一个较好的操作环境 13．文件的保密是指防止文件被（）。【C 】A．篡改B．破坏 C．窃取D．删除 14．系统抖动是指（）。【 D 】A．使用机器时，屏幕闪烁的现象 B．由于主存分配不当，偶然造成主存不够的现象 C．系统盘有问题，致使系统部稳定的现象 D．被调出的页面又立刻被调入所形成的频繁调入调出现象 15．避免死锁的一个著名的算法是（）。【C 】A．先入先出算法 B．优先级算法 C．银行家算法D．资源按序分配法 16．在多进程的并发系统中，肯定不会因竞争（）而产生死锁。【D 】A．打印机B．磁带机 C．磁盘D．CPU 17．用户程序中的输入、输出操作实际是由（）完成。【C 】A．程序设计语言B．编译系统 C．操作系统D．标准库程序 18．在分页存储管理系统中，从页号到物理块的地址映射是通过（）实现的。【B 】A．段表B．页表 C．PCB D．JCB 19．在操作系统中，进程的最基本特征是（）。【A 】A．动态性和并发性B．顺序性和可再现性 C．与程序的对应性D．执行过程的封闭性 20．一种既有利于短小作业又兼顾到长作业的作业调度算法是（）。【C 】A．先来先服务B．轮转 C．最高响应比优先D．均衡调度 ×××××试题答案及评分参考（×）第2页（共×页）

吴振顺《控制工程基础》王积伟 第二版 课后习题解答

第一章 3 解：1)工作原理：电压u2反映大门的实际位置，电压u1由开（关）门开关的指令状态决定，两电压之差△u＝u1－u2驱动伺服电动机，进而通过传动装置控制 大门的开启。当大门在打开位置，u2＝u 上：如合上开门开关，u1＝u 上 ，△u＝0， 大门不动作；如合上关门开关，u1＝u 下 ，△u<0，大门逐渐关闭，直至完全关闭， 使△u＝0。当大门在关闭位置，u2＝u 下：如合上开门开关，u1＝u 上 ，△u>0，大 门执行开门指令，直至完全打开，使△u＝0；如合上关门开关，u1＝u 下 ，△u＝0，大门不动作。 2)控制系统方框图 4 解：1)控制系统方框图

2)工作原理： a)水箱是控制对象，水箱的水位是被控量，水位的给定值h ’由浮球顶杆的长度给定，杠杆平衡时，进水阀位于某一开度，水位保持在给定值。当有扰动（水的使用流出量和给水压力的波动）时，水位发生降低（升高），浮球位置也随着降低（升高），通过杠杆机构是进水阀的开度增大（减小），进入水箱的水流量增加（减小），水位升高（降低），浮球也随之升高（降低），进水阀开度增大（减小）量减小，直至达到新的水位平衡。此为连续控制系统。 b) 水箱是控制对象，水箱的水位是被控量，水位的给定值h ’由浮球拉杆的长度给定。杠杆平衡时，进水阀位于某一开度，水位保持在给定值。当有扰动（水的使用流出量和给水压力的波动）时，水位发生降低（升高），浮球位置也随着降低（升高），到一定程度后，在浮球拉杆的带动下，电磁阀开关被闭合（断开），进水阀门完全打开（关闭），开始进水（断水），水位升高（降低），浮球也随之升高（降低），直至达到给定的水位高度。随后水位进一步发生升高（降低），到一定程度后，电磁阀又发生一次打开（闭合）。此系统是离散控制系统。 2-1解： （c ）确定输入输出变量（u1，u2） 22111R i R i u += 222R i u = ? -= -dt i i C u u )(1 1221 得到：11 21221222 )1(u R R dt du CR u R R dt du CR +=++ 一阶微分方程 （e ）确定输入输出变量（u1，u2） ?++=i d t C iR iR u 1 211 R u u i 2 1-=

算法设计与分析第2版王红梅胡明习题答案

算法设计与分析(第2版)-王红梅-胡明-习题 答案 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783） 提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图 1.7是这条河以及河上的两个岛和七座桥的 草图。请将该问题的数据模型抽象出来，并判 断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n 2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C ++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 图1.7 七桥问题

#include using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low=prvotkey) --high; b[low]=b[high]; while (low

第3章习题解答

第3章（大本）习题解答 一、填空 1．将作业相对地址空间的相对地址转换成内存中的绝对地址的过程称为 地址重定位 。 2．使用覆盖与对换技术的主要目的是 提高内存的利用率 。 3．存储管理中，对存储空间的浪费是以 内部碎片 和 外部碎片 两种形式表现出来的。 4．地址重定位可分为 静态重定位 和 动态重定位 两种。 5．在可变分区存储管理中采用最佳适应算法时，最好按 尺寸 法来组织空闲分区链表。 6．在分页式存储管理的页表里，主要应该包含 页号 和 块号 两个信息。 7．静态重定位在程序 装入 时进行，动态重定位在程序 执行 时进行。 8．在分页式存储管理中，如果页面置换算法选择不当，则会使系统出现 抖动 现象。 9．在请求分页式存储管理中采用先进先出（FIFO ）页面淘汰算法时，增加分配给作业的块数时， 缺页中断 的次数有可能会增加。 10．在请求分页式存储管理中，页面淘汰是由于 缺页 引起的。 11．在段页式存储管理中，每个用户作业有一个 段 表，每段都有一个 页 表。 二、选择 1．虚拟存储器的最大容量是由 B 决定的。 A ．内、外存容量之和 B ．计算机系统的地址结构 C ．作业的相对地址空间 D ．作业的绝对地址空间 2．采用先进先出页面淘汰算法的系统中，一进程在内存占3块（开始为空），页面访问序列为1、2、3、4、1、2、5、1、2、3、4、5、6。运行时会产生 D 次缺页中断。 A ．7 B ．8 C ．9 D ．10 从图3-1中的“缺页计数”栏里可以看出应该选择D 。 1 2 3 4 1 2 5 1 2 3 4 5 6 页面走向→ 3个内存块→缺页计数→ 图3-1 选择题2配图 3．系统出现“抖动”现象的主要原因是由于 A 引起的。 A ．置换算法选择不当 B ．交换的信息量太大 C ．内存容量不足 D ．采用页式存储管理策略 4．实现虚拟存储器的目的是 D 。 A ．进行存储保护 B ．允许程序浮动 C ．允许程序移动 D ．扩充主存容量

数据结构课后习题标准答案(第二版)

数据结构课后习题答案(第二版)

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

数据结构 （C 语言版）（第2 版） 习题解析 揭安全李云清杨庆红编著 江西师范大学计算机信息工程学院 联系方式：janquan@https://www.doczj.com/doc/e512000816.html, 2009 年12 月 2 第1章绪论 1.1 什么是数据结构？ 【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储 于计算机中，并在这些数据上定义了一个运算集合。 1.2 数据结构涉及哪几个方面？ 【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集 合。 1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不 一样，它们是否可以认作是同一个数据结构？为什么？ 【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不 一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样， 所以它们是两种不同的数据结构。 1.4 线性结构的特点是什么？非线性结构的特点是什么？ 【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结 点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元 素之间的关系可以是一对多的或多对多的。 1.5 数据结构的存储方式有哪几种？ 【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。1.6 算法有哪些特点？它和程序的主要区别是什么？ 【答】：算法具有（1）有穷性（2）确定性（3）0 个或多个输入（4）1 个或多个输出（5）

机械制造技术基础(第2版)第二章课后习题答案

《机械制造技术基础》部分习题参考解答第二章金属切削过程 2-1什么是切削用量三要素？在外圆车削中，它们与切削层参数有什么关系？答： 切削用量三要素是指切削速度v、进给量f、背吃刀量a p（切削xx）。 在外圆车削中，它们与切削层参数的关系是： 切削层公称厚度：hD fsin r切削层公称宽度：bD a p/sin r切削层公称横截面积：AD fap2-2确定外圆车刀切削部分几何形状最少需要几个基本角度？试画图标出这些基本角度。 答： 确定外圆车刀切削部分几何形状最少需要7个基本角度： 前角、后角、主偏角、副偏角、副前角、副后角和刃倾角，这些基本角度如下图所示（其中副前角、副后角不做要求）。 2-3试述刀具标注角度和工作角度的区别。为什么车刀作横向切削时，进给量取值不能过大？ 答： 刀具标注角度是在静态情况下在刀具标注角度参考系中测得的角度；而刀具工作角度是在刀具工作角度参考系中（考虑了刀具安装误差和进给运动影响等因素）确定的刀具角度。车刀作横向切削时，进给量取值过大会使切削速度、基面变化过大，导致刀具实际工作前角和工作后角变化过大，可能会使刀具工作后角变为负值，不能正常切削加工（P23）。 2-4刀具切削部分的材料必须具备哪些基本性能？

答： （P24） (1)高的硬度和耐磨性； (2)足够的强度和韧性； (3)高耐热性； (4)良好的导热性和耐热冲击性能； (5)良好的工艺性。 2-5常用的硬质合金有哪几类？如何选用？ 答： （P26）常用的硬质合金有三类： P类（我国钨钴钛类YT），主要用于切削钢等长屑材料；K类（我国钨钴类YG），主要用于切削铸铁、有色金属等材料；M类（我国通用类YW），可以加工铸铁、有色金属和钢及难加工材料。 2-6怎样划分切削变形区？第一变形区有哪些变形特点？ 答： 切削形成过程分为三个变形区。第一变形区切削层金属与工件分离的剪切滑移区域，第二变形区前刀面与切屑底部的摩擦区域；第三变形区刀具后刀面与已加工表面的摩擦区域。 第一变形区的变形特点主要是： 金属的晶粒在刀具前刀面推挤作用下沿滑移线剪切滑移，晶粒伸长，晶格位错，剪切应力达到了材料的屈服极限。 2-7什么是积屑瘤？它对加工过程有什么影响？如何控制积屑瘤的产生？答：

第7章习题解答

第七章习题解答 一、填空 1．一个操作系统的可扩展性，是指该系统能够跟上先进计算技术发展的能力。 2．在引入线程的操作系统中，线程是进程的一个实体，是进程中实施调度和处理机分派的基本单位。 3．一个线程除了有所属进程的基本优先级外，还有运行时的当前优先级。 4．在Windows 2000中，具有1~15优先级的线程称为可变型线程。它的优先级随着时间配额的用完，会被强制降低。 5．Windows 2000在创建一个进程时，在内存里分配给它一定数量的页帧，用于存放运行时所需要的页面。这些页面被称为是该进程的“工作集”。 6．Windows 2000采用的是请求调页法和集群法相结合的取页策略，把页面装入到内存的页帧里的。 7．分区是磁盘的基本组成部分，是一个能够被格式化和单独使用的逻辑单元。 8．MFT是一个数组，是一个以数组元素为记录构成的文件。 9．只要是存于NTFS卷上的文件，在MFT里都会有一个元素与之对应。 10．在Windows 2000的设备管理中，整个I/O处理过程都是通过I/O请求包（IRP）来驱动的。 二、选择 1．在引入线程概念之后，一个进程至少要拥有D 个线程。 A． 4 B．3 C．2 D．1 2．在Windows 2000中，只有A 状态的线程才能成为被切换成运行状态，占用处理器执行。 A．备用B．就绪C．等待D．转换 3．Windows 2000是采用C 来实现对线程的调度管理的。 A．线程调度器就绪队列表 B．线程调度器就绪队列表、就绪位图 C．线程调度器就绪队列表、就绪位图、空闲位图 D．线程调度器就绪队列表、空闲位图 4．在Windows 2000里，一个线程的优先级，会在A 时被系统降低。 A．时间配额用完B．请求I/O C．等待消息D．线程切换5．在单处理机系统，当要在进程工作集里替换一页时，Windows2000实施的是B 页面淘汰策略。 A． FIFO（先进先出）B．LRU（最近最久未用） C．LFU（最近最少用）D．OPT（最优） 6．在页帧数据库里，处于下面所列A 状态下的页帧才可以变为有效状态。 A．初始化B．备用C．空闲D．修改7．当属性值能够直接存放在MFT的元素里时，称其为B 。 A．非常驻属性B．常驻属性C．控制属性D．扩展属性8．在NTFS文件系统中，文件在磁盘上存储时的物理结构是采用C 的。 A．连续式B．链接式C．索引式D．组合式9．在Windows 2000的设备管理中，I/O请求包（IRP）是由D 建立的。 A．用户应用程序B．文件系统驱动程序 C．设备驱动程序D．I/O管理器

算法设计与分析课后习题

第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n; f(n) = 2log(n); g(n)= √n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10)

所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答： 因此，Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章 算法分析题