计算机科学概论--问题与答案

问题与练习答案 第 1 章 1.1 节 1. 上面的两个输入中有且只有一个必须为1，且最下面的输入必须为1。 2. 下面的输入1被NOT门取反为0，使得AND门的输出变为0。因此，OR门的2个输入均为0（记 住，触发器上面的输入保持为0），因此OR门的输出变成0。这就意味着，当触发器下面的输 入变回0，AND门的输出仍将保持0。 3. 上面的OR门的输出将变为1，使得上面的NOT门得到一个输出0。这会使得下面的OR门得 到一个输出0，并使得下面的NOT门得到一个输出1。这个1被看作是触发器的输出，同时 反馈给了上面的OR门，这时，它将该门的输出保持为1，即使在触发器的输入已经变回0。 4. 当时钟为0时，触发器将屏蔽掉电路的输入值。当时钟为1时，触发器将响应电路的输入值。 5. a. 整个电路等同于单个XOR门。 b. 这个电路也等同于单个XOR门。 6. a. 6AF2 b. E85517 c. 48 7. a. 01011111110110010111 b. 0110000100001010 c. 1010101111001101 d. 0000000100000000 1.2 节 1. 在第一种情况下，地址为6的存储单元最后结果为值5。在第二种情况下，它的最后结果值为8。 2. 在步骤1当新值写入3号存储单元时，该单元的原始值被擦去了。因此，步骤2并没有将3号存 储单元中原始值存入2号存储单元中。结果是：两个存储单元最后的值都是最初2号存储单元 中的值。正确的步骤如下： 步骤1，将2号存储单元中的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 移到1号存储单元。 步骤2，将3号存储单元中的内容移到2号存储单元。 步骤3，将1号存储单元中的内容移到3号存储单元。 3. 32768位。 问题与练习答案 413 1.3 节 1. 有较快的数据检索速度以及较高的传输速率。 2. 这里要记住的一点是，与计算机内部运作速度相比较，机械动作的缓慢表明：我们应该把必 须移动读/写磁头的次数减到最少。如果我们要在写满磁盘的一面后再开始下一面，那么当 我们在写满一个道时都必须移动一次读/写磁头。因此磁头移动的次数就大约等于磁盘两个 盘面所有道的总和。不过，如果我们通过电子方式在磁盘表面之间切换读/写磁头，我们就 只需要在每个柱面写满时才移动一次读/写磁头了。 3. 在这个应用中，必须从海量存储系统中随机地检索信息，而对于CD和DVD等设备中使用的 螺旋系统，这种方法是很耗时的。（而且，现在的技术还无法使CD和DVD设备中的某部分数 据进行更新。） 4. 存储空间是以物理扇区为单元分配的（事实上，在大多数情况下是以扇区组为单元）。如果 最后一个物理扇区没有被写满，可以再填加新的文本，而不需要增加此文档的存储空间。如 果最后一个物理扇区已经被写满，那么无论要给该文档填加什么内容，都需要分配额外的物 理扇区。 5. 闪存驱动器不需要物理运动，因此所需要的响应时间比较短，而且不会有物理损耗。 6. 缓冲区是一个临时的数据存储区域，通常用作解决数据源与最终目的地不一致性的手段。 1.4 节 1. Computer science。 2. 除了从低端数第6位对应的大写字母和小写字母分别是0和1外，两个位模式是相同的。 3. a. 01010111 01101000 01100101 01110010 01100101 00100000 01100001 01110010 01100101 00100000 01111001 01101111 01110101 00111111 b. 00100010 01001000 01101111 01110111 00111111 00100010 00100000 01000011 01101000 01100101 01110010 01111001 01101100 00100000 01100001 01110011 01101011 01100101 01100100 00101110 c. 00110010 00101011 00110011 00111101 00110101 00101110 4. 5. a. 5 b. 9 c. 11 d. 6 e. 16 f. 18 6. a. 110 b. 1101 c. 1011 d. 10010 e. 11011 f. 100 7. 在24位中，我们利用ASCII码可以存储3个符号。因此，可存储的值最大能够达到999。不过， 414 问题与练习答案 如果我们将这些位用作二进制数字，那么可存储的值则最大可达16 777 215。 8. a. 15.15 b. 51.0.128 c. 10.160 9. 几何表示法与位图编码的图像相比，更利于改变其尺寸。然而，几何表示法在图像的质量方 面没有位图好。正如在1.8节所说的，JPEG位图表示方式在相片中很常见。 10. 以每秒44 100样本的采样频率，一小时的立体声音乐需要635 040 00个字节的存储空间。这 也就差不多写满了一张容量略大于600 MB的CD。 1.5 节 1. a. 42 b. 33 c. 23 d. 6 e. 31 2. a. 100000 b. 1000000 c. 1100000 d. 1111 e. 11011 3. a. 4 1 3 b. 8 7 5 c. 2 1 2 d. 8 3 6 e. 8 5 4. a. 100.1 b. 10.11 c. 1.001 d. 0.0101 e. 101.101 5. a. 100111 b. 1011.110 c. 100000 d. 1000.00 1.6 节 1. a. 3 b. 15 c. -4 d. -6 e. 0 f. -16 2. a. 00000110 b. 11111010 c. 11101111 d. 00001101 e. 11111111 f. 00000000 3. a. 11111111 b. 10101011 c. 00000100 d. 00000010 e. 00000000 f. 10000001 4. a. 4位时，最大值是7，最小值是-8。 b. 6位时，最大值是31，最小值是-32。 c. 8位时，最大值是127，最小值是-128。 5. a. 0111(5+2=7) b. 0100(3+1=4) c. 1111(5+(-6)=-1) d. 0001(-2+3=1) e. 1000(-6+(-2)=-8) 6. a. 0111 b. 1011（溢出） c. 0100（溢出） d. 0001 e. 1000（溢出） 7. a. 0110 b. 0011 c. 0100 d. 0010 e. 0001 +0001 +1110 +1010 +0100 +1011 0111 0001 1110 0110 1100 8. 不会。如果一个数对于使用中的系统过大时，那么试图存储这个数则会产生溢出现象。当一 个正值与一个负值相加时，结果一定在这2个数值之间。于是，如果原始数值能够被存储， 那么结果也是可以被存储的。 9. a. 6，因为1110→14-8 b. -1，因为0111→7-8 c. 0，因为1000→8-8 d. -6，因为0010→2-8 e. -8，因为0000→0-8 f. 1，因为1001→9-8 10. a. 1101，因为5+8=13→1 101 问题与练习答案 415 b. 0011，因为-5+8=3→0 011 c. 1 011，因为3+8=11→1 011 d. 1 000，因为0+8=8→1 000 e. 1 111，因为7+8=15→1 111 f. 0 000，因为-8+8=0→0 000 11. 不可以。余8记数法可以存储的最大值是7，表示为1111。如果要表示更大的值，至少需要余 16记数法（这个记数法采用5位模式）。类似地，6也无法用余4记数法表示。（能够用余4记数 法表示的最大值是3。） 1.7 节 1. a. 5 8 b. 1 3 4 c. 9 32 d. 1 1 2  e. 11 64  2. a. 01101011 b. 01111010（截断误差） c. 01001100 d. 11101110 e. 11111000（截断误差） 3. 01001001 9 16 比00111101 12 32 大。下面是确定哪个位模式表示更大值的一个简单方法。 第一种情况：如果符号位不同，那么符号位为0的更大。 第二种情况：如果两个符号位都是0，那么从左至右扫描这两个位模式的其余部分，一直 到发现某一个二进制位，其位置上的位模式不同。在这个位置上包含1的位模式表示较大 的值。 第三种情况：如果两个符号位都是1，那么从左至右扫描这两个位模式的其余部分，一直到 发现某一个二进制位，其位置上的位模式不同。在这个位置上包含0的位模式表示较大的值。 这个比较过程的简单性是采用余码记数法（而不是二进制补码）表示浮点系统指数的一个 原因。 4. 最大的数值是 1 7 2 ，表示为位模式01111111。关于最小的正值，你们可以认为有2个“正确” 答案。首先，如果你坚持文中所描述的编码过程，它要求尾数的最高有效位必须为1（称为 规格化格式），答案则为 1 32 ，表示为位模式00001000。不过大多数机器并不对接近0的值施 加这样的限制，因此这时候的正确答案是 1 256 ，表示为位模式00000001。 1.8 节 1. 行程长度编码、频率相关编码、相对编码和字典编码。 2. 121321112343535 3. 彩色卡通是由边框清晰的单色块构成的而且所包含的颜色数目是有限的。 4. 不是，GIF和JPEG都是有损压缩系统，也就是说，图像中的细节可能会丢失。 5. JPEG基准标准利用了人眼的一个事实：人眼对于颜色变化不如对光线的变化敏感。因此， 减少表示颜色信息的位数，而没有明显地影响图像质量。 6. 暂时模糊和频率模糊。 7. 对信息编码时都要取近似值。对于数字数据，这些近似值在计算过程中会积累，这可能导致 416 问题与练习答案 错误的结果。而对于图像和声音，近似值就没有那么严重，因为这些被编码的数据只是进行 存储、传输以及再现。不过如果图像和声音反复地再现、存储，然后再编码，那么这些近似 值就会积累，因此最终导致无用的数据。 1.9 节 1. b、c和e。 2. 有。如果在一个字节中出现了偶数个错误，那么奇偶校验技术就无法检测到它们。 3. 在这种情况下，问题1中的a和b字节中出现了错误。问题2的答案是一样的。 4. a. 001010111 001101000 101100101 101110010 101100101 000100000 001100001 101110010 101100101 000100000 001111001 101101111 001110101 100111111 b. 100100010 101001000 101101111 101110111 100111111 100100010 000100000 001000011 001101000 101100101 101110010 001111001 101101100 000100000 001100001 001110011 001101011 101100101 001100100 100101110 c. 000110010 100101011 100110011 000111101 100110101 100101110 5. a. BED b. CAB c. HEAD 6. 一个解如下: A 0 0 0 0 0 B 1 1 1 0 0 C 0 1 1 1 1 D 1 0 0 1 1 第 2 章 2.1 节 1. 对于一些机器，这个过程包含2步：首先是从第一个单元读取内容到寄存器，然后将内容从 寄存器写入目标单元。对于大多数机器，这个过程只是当作一个活动被实现的，而不需要中 间寄存器。 2. 要写入的值、要写入的单元的地址以及要写入的命令。 3. 通用寄存器用于存储操作中马上用到的数据，主存储器用于存储不久就要用到的数据，海量 存储器用于存储暂时不会用到的数据。 2.2 节 问题与练习答案 417 1. move这个术语常用来表示从一个位置移到另外一个位置，因此后面留下一个空位。不过， 在一个机器中大多数情况下是不会发生这种移动的。相反，被移动的目标通常是被复制到新 的位置。 2. 称为相对寻址的常用技术指的是跳多远而不是跳到哪里。例如，一条指令可能向前跳3条指 令，或者向后跳2条指令。不过，你应该知道，如果后来在转移（JUMP）指令的起点及目的 地之间加入了额外的指令，那么就要改变这些指令了。 3. 从两方面讲都可以。这条指令是以条件转移的形式表述的。不过，由于0等于0这样的条件总 是可以满足的，所以这个转移一定会发生，就好像根本没有提到条件。你经常会遇到带有这 种指令的机器，因为这样的设计有效。例如，如果一台机器设计成可以执行带有“if…jump to…”这条指令，那么这个指令就既可以用于表示条件转移，也可以表示无条件转移。 4. 156C=0001010101101100 166D=0001011001101101 5056=0101000001010110 306E=0011000001101110 C000=1100000000000000 5. a. 将寄存器6的内容存入（STORE）地址为8A的存储单元。 b. 如果寄存器A的内容与寄存器0的内容相同，转移（JUMP）到位置DE。 c. 将寄存器3和寄存器C的内容进行与（AND），并将结果存入寄存器0。 d. 将寄存器F的内容移动（MOVE）至寄存器4。 6. 指令15AB要求CPU查询存储电路，查找地址为AB的存储单元的内容。当这个值从存储器 中获得时，要存入寄存器5。指令25AB并没有这样的存储器要求，而是将值AB存入寄存 器5。 7. a. 2356 b. A503 c. 80A5 2.3 节 1. 十六进制值34。 2. a. 0F b. C3 3. a. 00 b. 01 c. 4次 4. 它停机了。这是一个通常称为自修改代码的例子。也就是说，程序可以自我修改。需要注意 的是，前2条指令将十六进制C0存入存储单元F8，接下来的2条指令将00存入存储单元F9。 因此，当机器达到地址为F8的指令时，停止指令（C000）已经在那里了。 2.4 节 1. a. 00001011 b. 10000000 c. 00101101 d. 11101011 e. 11101111 f. 11111111 g. 11100000 h. 01101111 i. 11010010 2. 00111100，AND运算 3. 00111100，XOR运算 4. a. 如果该串包含偶数个1，最后结果就为0；否则为1。 b. 结果是偶校验的校验位的值。 5. 逻辑XOR运算类似于加法，除了2个操作数都为1的情况，这时XOR运算的结果为0，而加法 418 问题与练习答案 为10。（于是XOR运算可以被看作是没有进位的加法运算。） 6. 用掩码11011111进行AND运算，可以将小写改成大写。用00100000进行OR运算，可以将大 写改成小写。 7. a. 01001101 b. 11100001 c. 11101111 8. a. 57 b. B8 c. 6F d. 6A 9. 5 10. 用二进制补码为00110110，用浮点记数法为0101110。关键点是：由于位模式表示的不同， 用于值相加的过程也就不同。 11. 一个解如下： 12A7（将地址为7的存储单元的内容加载（LOAD）寄存器2。） 2380（将值80加载（LOAD）寄存器3。） 7023（将寄存器2和寄存器3进行OR运算，并将结果存入寄存器0。） 30A7（将寄存器0的内容存入（STORE）地址为A7的存储单元。） C000（停止。） 12. 一个解如下： 15E0（将地址为E0的内容加载（LOAD）寄存器5。） A502（将寄存器5的内容向右循环移动（ROTATE）2位。） 260F（将值0F加载（LOAD）寄存器6。） 8056（将寄存器5和寄存器6进行AND运算，并将结果存入寄存器0。） 30E1（将寄存器0的内容存入地址为E1的存储单元。） C000（停止。） 2.5 节 1. a. 37B5 b. 100万次 c. 不能。一个典型的文本页包含不超过4000个字符。因此，每分钟打印5页文本的能力表示， 其打印速率不超过每分钟20000个字符，这是远远低于每秒钟100万个字符的速率。（关键 点是，机器传输给打印机字符的速度要远远快于打印机能够打印的速度，因此，打印机 需要一种告知机器等待的方式。） 2. 该磁盘每秒钟要转50转，这就意味着在一秒钟之内，有800个扇区要通过读/写磁头。因为每 个扇区包含1024个字节，所以通过读/写磁头的二进制位速度大约为6.5 Mbit/s。因此，如果 控制器打算与磁盘中读取到的数据同步，那么控制器与磁盘驱动器之间的通信速度至少要这 么快。 3. 用ASCII码表示的300页的小说大概有2 MB，即16 000 000位。因此，如果要以54 Mbit/s的速 度传输整部小说，大约需要0.3 s。 2.6 节 1. 该管道会包含指令B1B0（正在执行）、5002甚至B0AA。如果寄存器1中的值与寄存器0 中的值相等，那么就会执行向地址B0转移的指令。那么对于流水线中指令所做的努力 则白费了。另一方面，并没有浪费时间，因为对于这些指令所做的努力并没有花费额 外的时间。 问题与练习答案 419 2. 如果不采取任何预防 措施 《全国民用建筑工程设计技术措施》规划•建筑•景观全国民用建筑工程设计技术措施》规划•建筑•景观软件质量保证措施下载工地伤害及预防措施下载关于贯彻落实的具体措施 ，那么在该程序的前面部分有机会对存储单元F8和F9进行修改之 前，这两个单元的信息已经作为指令被读取出来了。 3. a. 试图给该单元加1的CPU可以在该单元中首先读取值。接着，另外一个CPU读取该单元的 值。（需要注意的是：在这个时候，两个CPU检索到的是相同的值。）如果在第一个CPU 完成它的加法并将其结果写入该单元之后，第二个CPU才完成它的减法，并记下结果，那 么单元中最后的值只是反映了第二个CPU的活动。 b. 两个CPU可能还像以前一样从存储单元中读取数据，但是，第二个CPU这次可能会在第一 个CPU之前写下结果。因此，该单元的最后值就只反映了第一个CPU的活动。 第 3 章 3.1 节 1. 一个传统的例子是，人们为购买比赛的门票而排的队列。在这种情况中，可能存在着某些人 想“插队”，这就破坏了FIFO结构。 2. 选项（b）、（c）。和（e） 3. 实时处理是指：程序的执行要与机器环境中的活动相协调。交互式处理是指：程序在执行时， 人要与其进行交互。成功的交互式处理需要良好的实时特性。 4. 分时是指多个用户同时访问一台机器，多任务是指一个用户同时完成多项任务。 3.2 节 1. 外壳（shell）：与机器环境进行通信。 文件管理程序：协调机器的海量存储器的使用。 设备驱动程序：处理与机器的外围设备的通信。 内存管理程序：协调机器的主存的使用。 调度程序：协调系统中的进程。 分派程序：控制进程的CPU时间的分配。 2. 它们之间的界线比较模糊，其差别通常在于持有者的观点。粗略来说，实用软件完成的是基 本的、通用的任务，而应用软件则通常只完成针对机器某一特定应用的任务。 3. 虚拟存储器是虚构的存储空间，其表面上的存在是通过这样的过程创建的，即数据和程序在 主存和海量存储器之间来回交换数据。 4. 当机器接通电源时，CPU就开始执行驻留在ROM中的引导程序。这个引导程序引导CPU完成 这样一个过程，即把操作系统从海量存储器传送到主存的易失存储区内。当这个传送操作完 成时，引导程序就指引CPU跳转至操作系统。 3.3 节 1. 程序是指令的集合，而进程是遵循这些指令的操作。 2. CPU完成它的当前机器周期，保存当前进程的状态，并把它的程序计数器设为一个预定的值 （即中断处理程序的位置）。这样一来，将要执行的下一条指令就是中断处理程序中的第一条 指令。 420 问题与练习答案 3. 一种方法是给它们较高的优先权，使它们可以被分派程序引用。另一种方法是给优先权较高 的进程以较长的时间片。 4. 如果每个进程都用完它的整个时间片，那么机器每秒钟可以给至多20个进程提供完整的时间 片。如果一些进程没有用完它们的时间片，那么这个进程数目的值可能还会大些，但是花在 实现进程上下文切换所需的时间可能会更多（见第5题）。 5. 总共 5000 5001 的机器时间将实际花在进程执行中。然而，当一个进程请求一个I/O活动时，它的 时间片在控制器完成这个请求时就终止了。这样一来，如果每个进程都在它的时间片只用了 1µs时就作出这样的请求，那么机器的效率将降至 1 2 。也就是说，机器用于执行进程上下文 切换和用于进程的执行的时间一样多。 3.4 节 1. 这个系统保证，该资源一次不会被多于一个进程使用；然而，它表明了该资源是严格按照交 替方式分配的。一旦一个进程已经用完并放弃了这个资源，那么如果该进程要再次访问这个 资源时，它就必须得等待其他进程使用这个资源。即使是第一个进程马上需要这个资源，而 其他进程在一段时间内不需要这个资源时，情况依然如此。 2. 如果两辆汽车同时进入这个隧道的两端，那么它们将都不知道对方的存在。汽车进入和 灯的打开过程是临界区的另一个例子，或者说，在这种情况下，我们可以称它为临界过 程。在这个术语中，我们可以概括出这个系统的缺点，即隧道两端的汽车能够同时执行 临界过程。 3. a. 这保证了不可共享的资源不能被部分地请求和分配；也就是说，要么将整个桥梁给一辆汽 车，要么就什么也不给。 b. 这就意味着：不可共享的资源可以被强制收回。 c. 这就使得不可共享资源成为可共享的，这样就消除了竞争。 4. 箭头序列在这个有向图中形成了一个闭环。根据这个观察的结果，已经开发出了一些技术， 使得某些操作系统能够识别出死锁的存在，并据此采取适当的改正措施。 3.5 节 1. 姓名和日期被认为是不好的候选对象，这是因为它们是常用的选择，所以容易成为密码猜测 者的目标。使用完整的单词也被认为不好，这是因为密码猜测者能够很容易编写一个程序， 用来尝试字典里的所有单词。而且，只包含字符的密码也是不鼓励的，这是因为它们是从有 限的字符集中构成的。 2. 利用两位构成的不同位模式的数目是4。如果需要更多的特权级别，那么设计者至少需要三 位来表示不同的级别，这样一来，总共就有8个级别可供选择。按照同样的方式，对于少于4 个特权级别的自然选择就会是2，它是用一位可表示的位模式的数目。 3. 这个进程可以更改操作系统程序，使得分派程序把每个时间片都分配给该进程。 问题与练习答案 421 第 4 章 4.1 节 1. 开放式网络是这样的一种网络：它的规格说明以及 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 是公开的，于是不同的厂商可以生产 相互兼容的产品。 2. 两者都是通过连接两个总线以形成一个更大的总线网络。不过，中继器传输所有的信息，但 是网桥只传输那些目的地是该网桥另一端的信息。 3. 路由器是一台把网络连结起来，用来传送消息的设备。 4. 邮购业务以及它的客户，银行出纳员以及银行的客户，或者药剂师以及他的顾客。 5. 在交通流量、口头电话通信以及礼仪上有许多的协议。 4.2 节 1. 第一层ISP和第二层ISP提供因特网通信的核心设备，而因特网接入服务提供商则为客户提供 到核心设备的接入服务。 2. DNS(域名系统)收集因特网上的域名服务器的信息，以此来把助记网址转换成IP地址（也可 以由IP地址转换成助记网址）。 3. 3.4.5表示3个字节的位模式000000110000010000000101。位模式0001001100010000用点分十 进制法表示为19.16。 4. 这个问题可能有几个答案。其中一个就是，它们都是从特殊到一般。助记形式的因特网地址 都是以一台特定机器的名字开始，然后是TLD的名字。邮政地址是从个人的名字开始，然后 逐渐到比较大的区域，例如城市、州、国家。这个顺序与IP地址是相反的，它最开始是标识 域的位模式。 5. 名字服务器有助于将助记地址翻译成IP地址。邮件服务器传输、接收以及存储邮件信息。FTP 服务器提供文档传输服务。 6. SSH提供加密以及认证。 7. 它们使得初始服务器从向每个客户端发送单个消息的负担中解脱出来，P2P方法把这个负担 转移给客户(端)，而多点传送则把这个负担转移给因特网中的路由器。 4.3 节 1. URL本质上是一个文档在万维网上的地址。浏览器是帮助用户访问超文本的程序。 2. 标记语言是在文档中加入解释信息的一个系统。 3. HTML是一种特殊的标记语言。XML是产生标记语言的标准。 4. a. 表明一个HTML文档的开始。 b. 表明一个文档首部的开始。 c. 表明一个文档主体的结束。 d. 表明链接到另一个文档的项目的结束。 5. 客户端与服务器端是两个用于标识一个活动是在客户的机器上实现的，还是在服务器的机器 上实现的术语。 422 问题与练习答案 4.4 节 1. 只有链路层与网络层。链路层接收报文并将其传给网络层。网络层决定报文的转发方向，并 将报文传送回链路层再进行新的转发。 2. 不同于TCP，UDP是一个无连接协议，它不能保证报文会在目的地被接收到。 3. 每个报文都被赋予了一个跳数值，它决定了报文被中继传播的最大次数。 4. 实际上没有办法。任何主机上的程序员都可以修改该主机的软件，以保存这些记录。这就是 给敏感数据加密的原因所在。 4.5 节 1. 恶意软件进入计算机系统最常用的方式是通过邮件附件或者是隐藏在受害者下载的软件中。 然而，间谍软件则通常放在不被受害者怀疑而访问的万维网服务器中。 2. 一个区域的网关是一个路由器，它只是将通过它的分组（报文的一部分）继续转发。因此， 网关上的防火墙不能通过它的内容而只能通过它的地址信息过滤通信流。 3. 使用口令可以保护数据（当然也包括信息）。加密的使用可以保护信息。 4. 对于公钥加密系统，知道报文如何被加密并不能够对报文进行解密。 5. 这些问题是国际化的，因此不隶属于某一个政府的法律。不过，法律修正只是给那些受伤害 人一些帮助，并不能真正防止伤害。 第 5 章 5.1 节 1. 进程是执行算法的活动。程序是算法的表示。 2. 在绪论里，我们引证了演奏音乐、操作洗衣机、构造模型、表演魔术以及欧几里得算法等 算法。我们在日常生活中遇到的许多“算法”按照我们的正式定义都不能算是算法。本书 引证的长除算法就是一个例子。另一个例子是时钟执行的算法：它的指针日复一日地走动， 奏鸣钟声。 3. 非正式定义没有要求步骤是有序的和无歧义的，它只在要求里暗示，步骤是可执行的且能终 止的。 4. 这里存在两点。一是这些指令定义了一个不可终止的过程。但是事实上，这个过程最终到达 这样的状态：你的口袋里没有硬币。实际上，这可能是个初始状态。二是算法是有歧义的。 这个算法正像所表示的，它没有告诉我们在这个情况下该怎么做。 5.2 节 1. 以物质的组成为例。在一个层面上，原语被认为是分子，而分子实际是由原子组成的，原子 又是由电子、质子和中子组成的。今天，我们知道，这些“原语”甚至也是合成物。 2. 一旦一个过程被正确地构建，那么它就可以用作较大程序结构的构件块，不必再重新考虑该 过程的内部构成。 3. X ← 较大的输入; 问题与练习答案 423 Y ← 较小的输入; while(Y不是0) do （Remainder ← X被Y除后的余数; X ← Y; Y ← Remainder); GCD ← X 4. 光的所有其他颜色都可由红、蓝和绿组合产生。所以，电视机的显像管被设计成能产生这三 种基色。 5.3 节 1. a. if (n = 1 or n=2) then (答案是含有一个值n的列表) else (n除以3，得到商q和余数r. if (r=0) then (答案是含有q个3的列表) if (r=1) then (答案是含有（q-1）个3和2个2的列表) if (r=2) then (答案是含有q个3和1个2的列表) ) b. 结果是含有667个3的列表。 c. 用小的输入值来试验，直到看出一个模式。 2. a．可以。提示：把第一个棋子放在中心，这样使得其他各个象限覆盖一个正方形时它能避 免该象限含有那个洞。每个象限是原来问题的较小版本。 b. 有一个洞的棋盘含有22n-1个正方形，而每个棋子实际覆盖3个正方形。 c. 对于知道一个问题的解如何能够帮助解决其他问题，问题a和b提供了极好的例子。见Ploya 的第4阶段。 3. This is the correct answer. 4. 简单地设法去拼装图片是一个自底向上的方法。然而，通过观察拼图盒来看图形是什么样子 为你的方法增加了自顶向下的成分。 5.4 节 1. 把while语句的测试修改为“目标值不等于当前表项并且还有表项要检查”。 2. Z ← 0; X ← 1; repeat ( Z ← Z + X; X ← X + 1) until (X = 6) 3. 这是C语言中的一个问题。当关键字do和while分隔开若干行时，读程序的人常常会在对while 语句的正常解释上遇到障碍。特别是，一个do语句结尾处的while常常被解释为一个while语 句的开始。所以，最好使用不同的关键字来表示先测试循环结构和后测试循环结构。 424 问题与练习答案 4. Chery1 Alice Alice Gene Chery1 Brenda Alice Gene Chery1 Brenda Brenda Gene 5. 坚持把主元放到列表里一个相同表项的上面是浪费时间。例如，按建议进行修改，然后对所 有表项都相同的列表尝试这个修改后的新程序。 6. procedure sort(List) N ← 1; while(N小于List的长度) do (J ← N + 1; while( J不大于List的长度) do ( if (位置J里的表项小于位置N里的表项) then(交换两个表项) J ← J + 1) N ← N + 1) 7. 下面这个解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 的效率不是很高，你能使其效率更高吗？ procedure sort(List) N ← List的长度; While (N大于1) do (J ← List的长度; while(J大于1) do ( if (位置J里的表项小于位置J-1里的表项) then(交换两个表项) J ← J – 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 (10000-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张卡片中有两张两面是一样的。于是， 问题与练习答案 425 取得这样一张牌的概率是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，并且每通过一次 循环增加1，所以它的值最终一定到达N。 8. 不能保证。超出硬件和软件所能控制的问题，如机械故障和电气问题等，都会影响计算。 第 6 章 6.1 节 1. 一个用第三代语言编写的程序，从某种意义上说它是独立于机器的，因为它的运行步骤不是 按照诸如寄存器和存储单元地址这样的机器特征来描述的。在另一方面，从某种意义上说， 它又是依赖于机器的，因为算数溢出和截断误差还是会出现。 2. 主要差别是，汇编器把源程序里的每条指令只翻译为一条机器指令，而编译器往往要产生许 多条机器语言指令才能等价于一条源程序指令。 3. 说明性范型在于开发所要解决的问题的描述。函数式范型使程序员集中于把问题的解决用较 小的问题的解来描述。面向对象范型则强调描述问题的环境里的成分。 4. 与前几代语言相比，第三代语言使得程序比较多地用问题的环境来表达，比较少地用计算机 细节来表达。 6.2 节 1. 使用描述性常量可以改进程序的可理解性。 2. 声明语句描述术语，命令语句描述算法中的步骤。 3. 整型、实型、字符型和布尔型。 4. if-then-else和while循环结构很常见。 5. 同构数组所有的成分有同样的类型。 6.3 节 1. 局部变量仅在像过程这样的程序单元内是可访问的，全局变量在整个程序中都是可访问的。 2. 函数是这样的一个过程，它返回一个与函数名相关联的值。 3. 因为它们就是这样的。I/O运算实际上是调用该机器的操作系统内的例程。 4. 形参是过程内的标识符。它是实参这个值的占位符号，在该过程被调用时，实参才传递给该过程。 5. 过程用于执行一个动作，而函数用于产生一个值。于是，如果过程的名字反映它所执行的动 作，函数名反映它所产生的值，那么这个程序就更可读。 6.4 节 1. 词法 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ：识别标记的过程。 语法分析：识别程序的文法结构的过程。 426 问题与练习答案 代码生成：产生目标程序指令的过程。 2. 符号表是语法分析程序从程序的声明语句得到的信息的记录。 3. 4. 它们是一个或几个下述子串的实例： forward backward cha cha cha backward forward cha cha cha swing right cha cha cha swing left cha cha cha 6.5 节 1. 类是对象的描述。 2. 大概是MeteorClass，由它可构造各种流星。在类MeteorClass内，可以找到名为AimDirection 的实例变量，它指示激光瞄准的方向。这个变量大概会用在fire、turnRight和turnLeft 等方法中。 3. 类Employee可以包含与雇员的姓名、住址、服务年限等有关的特性。类FullTimeEmployee 可以包含与退休津贴有关的特性。类PartTimeEmployee可以包含与每周工作小时数和每小 时佣金等有关的特性。 4. 构造器是类里的一个特殊方法，它在创建该类的一个实例时执行。 5. 一个类里的某些项指定为私有，以防止其他程序单元直接访问这些项。如果一个项是私有的， 那么修改这个项的影响应该限于这个类的内部。 6.6 节 1. 包含初始化执行并发进程的技术以及实现进程间通信的技术。 2. 一个方法是把负担放在进程上，另一个方法是把负担放在数据上。后者的好处是把任务集中 在该程序的一个点上。 3. 这包括天气预报、空中交通管制、复杂系统（从核反应到行人交通）的模拟、计算机网络以 表达式 表达式 表达式 项 项 项 项 因子 因子 因子 因子 问题与练习答案 427 及数据库维护。 6.7 节 1. R、T和V。例如，我们可以证明，R是将﹁R加到这个集合的结果，并且能够证明这个解可以 得到空语句，证明如下： 2. 不是。这个集合是不相容的，因为消解可以得到空语句，证明如下： 3. mother(X, Y) :- parent(X, Y), female(X) father(X, Y) :- parent(X, Y), male(X) 4. Prolog将得出结论：carol是她的同胞。为了解决这个问题，规则需要包括x不能等于y这样 的事实，在Prolog中写成x\=y。这样规则的改进版本是： sibling(x,y) :- x\=y, parent(z,x), parent(z,y) 意思是：如果x和y不相同且有相同的父母，那x就是y的同胞。下面的版本则坚持认为只有 当x和y都有相同的父母，那他们才是同胞： sibling(x,y) :- x\=y, z\=w parent(z,x), parent(z,x) parent(w,x), parent(w,y) 第 7 章 7.1 节 1. 一长串赋值语句序列并不比设计成几句嵌套的if语句复杂。 2. 在使用了一段固定时间后，发现错误的数目为多少？这里的一个问题就是不能预先估算出这 个值。 3. 这里的关键问题就是要考虑如何能对软件的属性进行度量。用于估算一段软件中错误数目的 空 空 428 问题与练习答案 一种方法是，在这个软件设计时故意放进一些错误。然后，在认为软件已调试后，检查一下， 看原先的错误还存在多少。例如，如果你在软件中故意放入7个错误，在调试后消除了5个错 误，那么你就可以推测，软件中错误的总数只有 5 7 被排除。 4. 可能的答案包括：度量标准的发现、预制构件的开发、CASE工具的开发以及向标准靠近。另 一个是（在第7.5节的后面涉及它）建模开发和像UML的符号系统。 7.2 节 1. 在开发阶段稍作努力就能为将来的维护工作带来很多便利。 2. 需求分析阶段专注于提议系统将实现哪些功能，设计阶段专注于系统完成这些目标的方式， 实施阶段专注于系统的实际建设，而测试阶段则专注于保证建成的系统遵循原定的目标。 3. 软件需求规格说明文档的作用是：为客户和软件工程公司之间，在所要开发软件的需求和规 格说明问题上达成一致而编写的文档。 7.3 节 1. 传统的瀑布方法要求需求分析、设计、实现和测试阶段按照线性方式实现，而较新的模型则 是一种更为宽松的反复试验、不断探索的方法。 2. 增量模型、迭代模型和XP。 3. 传统的演化式原型开发是开发软件的组织所实现的，而开放源码开发的方法并不限制在 一个组织内。在开放源码开发的情况中，管理软件开发过程的人没有必要决定宣告哪些 增强，而在传统的演化式原型开发中，管理软件开发的人员要为员工分配明确的增强软 件的任务。 4. 对你而言，这是你要考虑的。如果你是软件开发公司的管理者，你能够对你的公司要销售的 软件采用开放源码的方法进行开发吗？ 7.4 节 1. 一部小说的各章之间相互依存，而一部百科全书各个章节之间很大程度上是相互独立的。所 以，小说的章节之间比百科全书的章节之间有更大的耦合度。然而，百科全书中的章节可能 比小说里的章节有更高的内聚度。 2. 累计积分可能是数据耦合的一个例子。其他可能存在的“耦合”包括疲劳、冲力、对对手策 略的了解，可能还有自信心。在许多体育运动项目中，因一局比赛的结束而重新开始下一局， 局的内聚度会增加。例如，在棒球运动中，一个队即使以满垒结束了上轮击球，每次轮到击 球也都以没有跑垒选手开始。在其他有些运动中，各单元分别记分，如网球比赛中，每局的 输赢与其他局无关。 3. 这是一个难题。从一种观点来看，我们可以从把每件事情放在单一模块中开始。这就造成了 较低的内聚度而根本没有耦合。然后，如果我们开始把单一模块分割成一些较小的模块，结 果就会使得耦合度增加。所以我们可能会得出结论：内聚度的增加易于导致耦合度的增加。 从另一方面讲，假设手头上的问题自然地分割成3个内聚度较高的模块，称为A、B和C。如果 原始的设计没有注意到这种自然的分割（例如，A的一半任务可能与B的一半任务放在了一起， 等等），我们希望内聚度低而耦合度高。在这种情况下，重新设计系统，将任务A、B和C分离 至不同的模块中，这就极有可能在增加模块内的内聚度的同时降低了模块间的耦合度。 问题与练习答案 429 4. 耦合是模块之间的链接，内聚则是模块内部的连接关系。信息隐藏是共享信息的约束。 5. 你可以添加一个箭头，用来说明ControlGame模块必须告知UpdateScore模块，谁赢得了比 赛。然后，再在其另外一个方向上添加一个箭头，用来说明当UpdateScore模块把控制权移 交到ControlGame模块时，它就将报告当前的状态（诸如“局结束”或“比赛结束”等）。 6. 删除图7-5中除第一个和最后一个以外的所有水平箭头。也就是说，裁判应该评判PlayerA 的发球，并且直接将updateScore消息发送给Score。（当然，这也就忽视了第二发球的机 会。考虑到双误时，应该如何修改程序设计呢？） 7. 传统的程序员是在语句的基础上写程序，如第6章所介绍的；而构件装配员则是通过连接称 为构件的预制块来构建程序。 7.5 节 1. 首先确定的是，你的图处理的是数据（不是书本的流动）。下面的图就表明：书ID（来源于 读者）和读者记录（来源于图书馆文件）结合成借书记录，并存放在图书馆文件中。 2. 3. 这个联系是多对多联系，所以其类图如下： 4. 读者 图书 馆文件 借书过程 读者记录 借书记录 读者 图书管理员 图书馆系统 借书 还书 更新藏书记录 入住 接待 旅客 酒店 书ID PersonClass name address EmployeeClass employee ID seniorityLevel 430 问题与练习答案 5. 如图7-13，在图的周围画一个矩形，并且在左上角加上“sd”标识。 6. 设计模式为实现反复出现的软件主题提供了标准的、成熟的方法。 7.6 节 1. SQA（软件质量保证）小组负责监督和实施组织所采用的质量控制系统。 2. 人们一般不会记录他们在一个项目中所采取的步骤措施（如决定、行动等）。（这里还存在性 格冲突、嫉妒、自我中心等问题） 3. 记录保存和评审。 4. 软件测试的目的是为了找出错误。那么，从这个意义上讲，没有发现错误的测试就是失 败的。 5. 办法之一就是考虑模块中的分支数。例如，一个过程模块，它包含了大量的循环和if-then- else语句，那么它很可能比一个带有简单的逻辑结构的模块更容易出错。 6. 边界值分析会建议你用一个有100个数据项的表和一个没有数据项的表对这个软件进行测 试。你还可以用一个已经排好序的表进行测试。 7.7 节 1. 文档采用的形式有用户文档、系统文档和技术文档。通常是伴随着手册一起出现的，有注释 和精心编写代码的源程序，程序本身显示在终端上的交互式消息，有数据字典，以及文档的 设计格式，如结构图、类图、数据流图和实体-联系图等。 2. 在开发阶段和修改阶段。问题在于，修改必须要像原始程序一样完全文档化。（同样，软件 在其使用阶段也要文档化。例如，系统的一个用户可能会发现问题，这个问题不是确定的， 而仅仅会在系统的用户手册的以后版本中得到反映。而且，有时候，有关软件使用文档的书 籍是在该软件已经使用了一段时间并开始流行后写的。） 3. 不同的人对此有不同的观点。有些人认为程序是整个项目的关键，所以自然更重要。而 另一部分人则认为，如果程序