PDF《第5章》

while(N小于List的长度) do (J ← N + 1;

while( J不大于List的长度) do ( if (位置J里的表项小于位置N里的表项) then(交换两个表项) J ← J + 1) N ← N + 1) 7. 下面这个解决方案的效率不是很高,你能使其效率更高吗? procedure sort (List) N ← List的长度;

While (N大于1) do 问题与练习答案

13 (J ← List的长度;

while(J大于1) do ( if (位置J里的表项小于位置J-1里的表项) then(交换两个表项) J ← J C 1) N ← N - 1) 5.5 节1. 考虑的第一个名字是Henry,接下来是Larry,最后是Joe. 2. 8,17 3. 1,2,3,3,2,1 4. 终止条件是 N大于等于3 (或 N不小于3 ) .该条件的前提是没有创建额外的激活. 5.6 节1. 如果该机器1 s可以排序100个名字,那么它1 s可以进行

4 1 (10 000-100)次比较.这意味着,每 次比较所花费的时间近似于0.0004 s.因此,排序1000个名字平均需要

4 1 (1

000 000-1 000)次 比较,大概需要100 s或1

3 2 min. 2. 二分搜索法属于 ? (lgn)、顺序搜索法属于 ? (n),而插入排序法属于 ? (n2 ). 3. ? (lgn) 类是效率最高的,接着是 ? (n)、 ? (n2 )和?(n3 ). 4. 回答是不正确的,尽管听起来似乎是对的.事实是3张卡片中有两张两面是一样的.于是, 取得这样一张牌的概率是2/3. 5. 不正确.如果被除数小于除数,如3/7,给出的答案是1,尽管正确结果应该是0. 6. 不正确.如果X的值是0,而Y的值不是0,那么所给出的答案是不正确的. 7. 每次构建终止测试时,语句 Sum=1+2+…+K并且K小于等于N 为真.把它与终止条件 K 大于等于N 合并产生所预期的结论 Sum=1+2+…+N .因为K被初始化为0,并且每进行一 次循环K的值就增加1,所以它的值最终一定达到N. 8. 不能保证. 不是硬件和软件设计所能控制的问题, 如机械故障和电气问题等, 都会影响计算. 第6章6.1 节1. 一个用第三代语言编写的程序,从某种意义上说它是独立于机器的,因为它的运行步骤不是 按照寄存器和存储单元地址这样的机器特征来描述的.在另一方面,从某种意义上说,它又 是依赖于机器的,因为算数溢出和截断误差还是会出现. 2. 主要差别是,汇编程序把源程序里的每条指令只翻译为一条机器指令,而编译器往往要产生 多条机器语言指令才能等价于一条源程序指令. 3. 说明性范型基于开发所要解决的问题的描述. 函数式范型使程序员根据较小问题的解决方案 来描述待解决问题的解决方案.面向对象范型则强调描述问题的环境里的成分. 4. 与前几代语言相比,第三代语言更多是用问题的环境来表达程序,很少用计算机细节来表达.

14 问题与练习答案 6.2 节1. 使用描述性常量可以改进程序的可理解性. 2. 声明语句描述术语,命令语句描述算法中的步骤. 3. 整型、实型、字符型和布尔型. 4. if-then-else和while循环结构很常见. 5. 同构数组所有的成分有同样的类型. 6.3 节1. 变量的作用域是指变量在程序中可使用的范围. 2. 函数是这样的一个过程,它返回一个与函数名相关联的值. 3. 因为它们就是这样的.I/O操作实际上是对该机器操作系统内例程的调用. 4. 形参是过程内的标识符.它是实参这个值的占位符,在该过程被调用时,实参才传递给该过程. 5. 过程用于执行一个操作,而函数用于产生一个值.于是,如果过程的名字反映它所执行的操 作,函数名反映它所产生的值,那么这个程序就更可读. 6.4 节1. 词法分析:识别标记的过程. 语法分析:识别程序的语法结构的过程. 代码生成:产生目标程序指令的过程. 2. 符号表是语法分析程序从程序的声明语句中得到的信息的记录. 3. 4. 符合Chacha结构的字符串由一个或几个下述子串构成: forward backward cha cha cha backward forward cha cha cha swing right cha cha cha swing left cha cha cha 表达式 表达式 表达式 项项项项因子 因子 因子 因子 问题与练习答案