計算機導(dǎo)論課后習(xí)題答案1

問題與練習(xí)答案

第1章

1.1節(jié)

1.上面的兩個輸入中有且只有一個必須為1,且最下面的輸入必須為1。

2.下面的輸入1被NOT門取反為0,使得AND門的輸出變?yōu)?。因此，OR門的2個輸入均為0（記

住，觸發(fā)器上面的輸入保持為0）,因此OR門的輸出變成0。這就意味著，當(dāng)觸發(fā)器下面的輸

入變回0,AND門的輸出仍將保持0。

3.上面的OR門的輸出將變?yōu)?,使得上面的NOT門得到一個輸出0。這會使得下面的OR門得到

一個輸出0,并使得下面的NOT門得到一個輸出1。這個1被看作是觸發(fā)器的輸出，同時反饋

給了上面的OR門，這時，它將該門的輸出保持為1,即使在觸發(fā)器的輸入已經(jīng)變回0。

4.當(dāng)時鐘為0時，觸發(fā)器將屏蔽掉電路的輸入值。當(dāng)時鐘為1時，觸發(fā)器將響應(yīng)電路的輸入值。

5.a.整個電路等同于單個XOR門。

b.這個電路也等同于單個XOR門。

6.a.6AF2b.E85517c.48

7.a.01011111110110010111

b.0110000100001010

c.1010101111001101

d.0000000100000000

1.2節(jié)

1.在第一種情況下，地址為6的存儲單元最后結(jié)果為值5。在第二種情況下，它的最后結(jié)果值為

8。

2.在步驟1當(dāng)新值寫入3號存儲單元時，該單元的原始值被擦去了。因此，步驟2并沒有將3號存

儲單元中原始值存入2號存儲單元中。結(jié)果是：兩個存儲單元最后的值都是最初2號存儲單元

中的值。正確的步驟如下：

步驟1,將2號存儲單元中的內(nèi)容移到1號存儲單元。

步驟2,將3號存儲單元中的內(nèi)容移到2號存儲單元。

步驟3,將1號存儲單元中的內(nèi)容移到3號存儲單元。

3.32768位。

382問題與練習(xí)答案

1.3節(jié)

1.有較快的數(shù)據(jù)檢索速度以及較高的傳輸速率。

2.這里要記住的一點是，與計算機內(nèi)部運作速度相比較，機械動作的緩慢表明：我們應(yīng)該把必

須移動讀/寫磁頭的次數(shù)減到最少。如果我們要在寫滿磁盤的?面后再開始下?面，那么當(dāng)

我們在寫滿一個道時都必須移動一次讀/寫磁頭。因此磁頭移動的次數(shù)就大約等于磁盤兩個

盤面所有道的總和。不過，如果我們通過電子方式在磁盤表面之間切換讀/寫磁頭，我們就

只需要在每個柱面寫滿時才移動一次讀/寫磁頭了。

3.在這個應(yīng)用中，必須從海量存儲系統(tǒng)中隨機地檢索信息，而對于CD和DVD等設(shè)備中使用的

螺旋系統(tǒng)，這種方法是很耗時的。（而且，現(xiàn)在的技術(shù)還無法使CD和DVD設(shè)備中的某部分?jǐn)?shù)

據(jù)進(jìn)行更新。）

4.存儲空間是以物理扇區(qū)為單元分配的（事實上，在大多數(shù)情況下是以扇區(qū)組為單元）。如果

最后一個物理扇區(qū)沒有被寫滿，可以再填加新的文本，而不需要增加此文檔的存儲空間。如

果最后一個物理扇區(qū)已經(jīng)被寫滿，那么無論要給該文檔填加什么內(nèi)容，都需要分配額外的物

理扇區(qū)。

5.閃存駁動器不需要物理運動，因此所需要的響應(yīng)時間比較短，而且不會有物理損耗。

6.緩沖區(qū)是一個臨時的數(shù)據(jù)存儲區(qū)域，通常用作解決數(shù)據(jù)源與最終目的地不一致性的手段。

1.4節(jié)

1.Computerscience。

2.除了從低端數(shù)第6位對應(yīng)的大寫字母和小寫字母分別是0和1外，兩個位模式是相同的。

3.a.01010111011010000110010101110010

01100101001000000110000101110010

01100101001000000111100101101111

0111010100111111

b.00100010010010000110111101110111

00111111001000100010000001000011

01101000011001010111001001111001

01101100001000000110000101110011

01101011011001010110010000101110

c.00110010001010110011001100111101

0011010100101110

4.

（A______、，一、(A~~[A)[A1%1

**

**???***

▼舊____________JJLJ

I_____vjLyJ1._____VJI___L

5b.9c.11d.6c.16f.18

6.a.110b.1101c.1011d.10010e.11011f.100

7.在24位中,我們利用ASCII碼可以存儲3個符號。因此，可存儲的值最大能夠達(dá)到999。不過,

如果我們將這些位用作二進(jìn)制數(shù)字，那么可存儲的值則最大可達(dá)16777215。

問題與練習(xí)答案383

8.a.15.15b.51.0.128c.10.160

9.如文中強調(diào)的，矢量技術(shù)在改變圖像大小上比位圖技術(shù)更有益處。對于簡單的線性圖形，矢

量技術(shù)也較緊湊。不過，矢量技術(shù)提供的攝影質(zhì)量不及位圖技術(shù)產(chǎn)生的。

10.以每秒44100樣本的采樣頻率，一小時的立體聲音樂需要63504000個字節(jié)的存儲空間。這

也就差不多寫滿了一張容量略大于600MB的CD。

1.5節(jié)

La.42b.33c.23d.6e.31

2.a.100000b.1000000c.1100000d.1111e.11011

3-a-3-b.75c.12d.36-e.5

48288

4.a.100.1b.10.11c.1.001d.0.0101e.101.101

5.a.100111b.1011.110c.100000d.1000.00

1.6節(jié)

La.3b.15c.-4d.-6e.0f.-16

2.a.00000110b.11111010c.11101111

d.00001101e.11111111f.00000000

3.a.11111111b.10101011c.00000100

d.00000010e.00000000f.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.0111b.1011(溢出)c.0100(溢出)

d.0001e.1000(溢出)

7.a.0110b.0011c.0100d.0010e.0001

乜皿L+1110包3+0100+1011_____

01110001111001101100

8.不會。如果一個數(shù)對于使用中的系統(tǒng)過大時，那么試圖存儲這個數(shù)則會產(chǎn)生溢出現(xiàn)象。當(dāng)一

個正值與一個負(fù)值相加時，結(jié)果一定在這2個數(shù)值之間。于是，如果原始數(shù)值能夠被存儲，

那么結(jié)果也是可以被存儲的。

9.a.6,因為610Tl4-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—1101

b.0011,因為-5+8=3-0011

c.1011,因為3+8=1111011

384問題與練習(xí)答案

d.1000,因為0+8=8-1000

e.1111,因為7+8=15—1111

f.0000,因為-8+8=0-0000

11.不可以。余8記數(shù)法可以存儲的最大值是7,表示為1111。如果要表示更大的值，至少需要余

16記數(shù)法（這個記數(shù)法采用5位模式）。類似地，6也無法用余4記數(shù)法表示。（能夠用余4記數(shù)

法表示的最大值是3。）

1.7節(jié)

1

b.4a.264

o32

2.a.01101011b.01111010（截斷誤差）

c.01001100.d.IIIOIUDe.11111000（截斷誤差）

a17

3.01001001比00111101大。下面是確定哪個位模式表示更大值的一個簡單方法。

1632

第種情況：如果符號位不同，那么符號位為0的更大。

第二種情況：如果兩個符號位都是0,那么從左至右掃描這兩個位模式的其余部分，一直到

發(fā)現(xiàn)某一個二進(jìn)制位，其位置上的位模式不同。在這個位置上包含1的位模式表示較大的值。

第三種情況：如果兩個符號位都是1,那么從左至右掃描這兩個位模式的其余部分，一直到

發(fā)現(xiàn)某一個二進(jìn)制位，其位置上的位模式不同。在這個位置上包含0的位模式表示較大的值。

這個比較過程的簡單性是采用余碼記數(shù)法（而不是二進(jìn)制補碼）表示浮點系統(tǒng)指數(shù)的?個原

因。一

4.最大的數(shù)值是7：表示為位模式01111111。關(guān)于最小的正值，你們可以認(rèn)為有2個“正確”

2

答案。首先，如果你堅持文中所描述的編碼過程，它耍求尾數(shù)的最高有效位必須為1（稱為

規(guī)格化格式），答案則為'，表示為位模式00001000。不過大多數(shù)機器并不對接近0的值施

32

加這樣的限制，因此這時候的正確答案是?,表示為位模式00000001。

256

1.8節(jié)

1.行程長度編碼、頻率相關(guān)編碼、相對編碼和字典編碼。

2.121321112343535

3.彩色卡通是由邊框清晰的單色塊構(gòu)成的而且所包含的顏色數(shù)目是有限的。

4.不是，GIF和JPEG都是有損壓縮系統(tǒng)，也就是說，圖像中的細(xì)節(jié)可能會丟失。

5.JPEG基準(zhǔn)標(biāo)準(zhǔn)利用了人眼的一個事實：人眼對于顏色變化不如對光線的變化敏感。因此，

減少表示顏色信息的位數(shù)，而沒有明顯地影響圖像質(zhì)量。

6.暫時模糊和頻率模糊。

7.對信息編碼時都要取近似值。對于數(shù)字?jǐn)?shù)據(jù)，這些近似值在計算過程中會積累，這可能導(dǎo)致

錯誤的結(jié)果。而對于圖像和聲音，近似值就沒有那么嚴(yán)重，因為這些被編碼的數(shù)據(jù)只是進(jìn)行

存儲、傳輸以及再現(xiàn)。不過如果圖像和聲音反復(fù)地再現(xiàn)、存儲，然后再編碼，那么這些近似

值就會積累，因此最終導(dǎo)致無用的數(shù)據(jù)。

問題與練習(xí)答案385

1.9節(jié)

1.b、c和e。

2.有。如果在一個字節(jié)中出現(xiàn)了偶數(shù)個錯誤，那么奇偶校驗技術(shù)就無法檢測到它們。

3.在這種情況下，問題1中的a和b字節(jié)中出現(xiàn)了錯誤。問題2的答案是一樣的。

4.a.001010111001101000101100101

101110010101100101000100000

001100001101110010101100101

000100000001111001101101111

001110101100111111

b.100100010101001000101101111

101110111100111111100100010

000100000001000011001101000

101100101101110010001111001

101101100000100000001100001

001110011001101011101100101

001100100100101110

c.000110010100101011100110011

000111101100110101100101110

5.a.BEDb.CABc.HEAD

6.一個解如下：

A00000

B11100

CO1111

D10011

第2章

2.1節(jié)

1.對于一些機器，這個過程包含2步：首先是從第一個單元讀取內(nèi)容到寄存器，然后將內(nèi)容從

寄存器寫入目標(biāo)單元。對于大多數(shù)機器，這個過程只是當(dāng)作一個活動被實現(xiàn)的，而不需要中

間寄存器。

2.要寫入的值、要寫入的單元的地址以及要寫入的命令。

3.通用寄存器用于存儲操作中馬上用到的數(shù)據(jù)，主存儲器用于存儲不久就要用到的數(shù)據(jù)，海量

存儲器用于存儲暫時不會用到的數(shù)據(jù)。

2.2節(jié)

1.move這個術(shù)語常用來表示從一個位置移到另外一個位置，因此后面留卜一個空位。不過，

在?個機器中大多數(shù)情況下是不會發(fā)生這種移動的。相反，被移動的目標(biāo)通常是被復(fù)制到新

的位置。

2.稱為相對尋址的常用技術(shù)指的是跳多遠(yuǎn)而不是跳到哪里。例如，一條指令可能向前跳3條指

令，或者向后跳2條指令。不過，你應(yīng)該知道，如果后來在轉(zhuǎn)移(JUMP)指令的起點及目的

386問題與練習(xí)答案

地之間加入了額外的指令，那么就要改變這些指令了。

3.從兩方面講都可以。這條指令是以條件轉(zhuǎn)移的形式表述的。不過，由于0等于0這樣的條件總

是可以滿足的，所以這個轉(zhuǎn)移一定會發(fā)生，就好像根本沒有提到條件。你經(jīng)常會遇到帶有這

種指令的機器，因為這樣的設(shè)計有效。例如，如果一臺機器設(shè)計成可以執(zhí)行帶有“if…jump

to…”這條指令，那么這個指令就既可以用于表示條件轉(zhuǎn)移，也可以表示無條件轉(zhuǎn)移。

4.156C=0001010101101100

166D=0001011001101101

5056=0101000001010110

306E=0011000001101110

C000=1100000000000000

5.a.將寄存器6的內(nèi)容存入（STORE）地址為8A的存儲單元。

b.如果寄存器A的內(nèi)容與寄存器0的內(nèi)容相同，轉(zhuǎn)移（JUMP）到位置DE。

c.將寄存器3和寄存器C的內(nèi)容進(jìn)行與（AND）,并將結(jié)果存入寄存器0。

d.將寄存器F的內(nèi)容移動（MOVE）至寄存器4。

6.指令15AB要求CPU查詢存儲電路，查找地址為AB的存儲單元的內(nèi)容。當(dāng)這個值從存儲器中

獲得時，要存入寄存器5。指令25AB并沒有這樣的存儲器要求，而是將值A(chǔ)B存入寄存器5。

7.a.2356b.A503c.80A5

2.3節(jié)

1.十六進(jìn)制值34。

2.a.OFb.C3

3.a.00b.01c.4次

4.它停機了。這是-一個通常稱為自修改代碼的例子。也就是說，程序可以自我修改。需要注意

的是，前2條指令將十六進(jìn)制C0存入存儲單元F8,接下來的2條指令將00存入存儲單元F9。

因此，當(dāng)機器達(dá)到地址為F8的指令時「停止指令（C000）已經(jīng)在那里了。

2.4節(jié)

1.a.00001011b.10000000c.00101101

d.11101011e.11101111f.11111111

g.11100000h.01101111i.11010010

2.00111100,AND運算

3.00111100,XOR運算

4.a.如果該串包含偶數(shù)個1,最后結(jié)果就為0；否則為1。

b.結(jié)果是偶校驗的校驗位的值。

5.邏輯XOR運算類似于加法，除了2個操作數(shù)都為1的情況，這時XOR運算的結(jié)果為0,而加法

為10。（于是XOR運算可以被看作是沒有進(jìn)位的加法運算。）

6.用掩碼11011111進(jìn)行AND運算，可以將小寫改成大寫。用00100000進(jìn)行OR運算，可以將大

寫改成小寫。

7.a.01001101b.11100001c.11101111

8.a.57b.B8c.6Fd.6A

9.5

問題與練習(xí)答案387

10.用二進(jìn)制補碼為00110110,用浮點記數(shù)法為0101110。關(guān)鍵點是：由于位模式表示的不同，

用于值相加的過程也就不同。

11.一個解如下：

12A7（將地址為7的存儲單元的內(nèi)容加載（LOAD）寄存器2。）

2380（將值80加載（LOAD）寄存器3。）

7023（將寄存器2和寄存器3進(jìn)行OR運算，并將結(jié)果存入寄存器0。）

30A7（將寄存器0的內(nèi)容存入（STORE）地址為A7的存儲單元。）

C000（停止。）

12.一個解如下：

15E0（將地址為E0的內(nèi)容加載（LOAD）寄存器5。）

A502（將寄存器5的內(nèi)容向右循環(huán)移動（ROTATE）2位。）

260F（將值0F加載（LOAD）寄存器6。）

8056（將寄存器5和寄存器6進(jìn)行AND運算，并將結(jié)果存入寄存器0。）

30E1（將寄存器0的內(nèi)容存入地址為E1的存儲單元。）

C000（停止。）

2.5節(jié)

l.a.37B5

b.100萬次

c.不能。一個典型的文本頁包含不超過4000個字符。因此，每分鐘打印5頁文本的能力表示，

其打印速率不超過每分鐘20000個字符，這是遠(yuǎn)遠(yuǎn)低于每秒鐘100萬個字符的速率。（關(guān)鍵

點是，機器傳輸給打印機字符的速度要遠(yuǎn)遠(yuǎn)快于打印機能夠打印的速度，因此，打印機

需要一種告知機器等待的方式。）

2.該磁盤每秒鐘要轉(zhuǎn)50轉(zhuǎn)，這就意味著在一秒鐘之內(nèi)，有800個扇區(qū)要通過讀/寫磁頭。因為每

個扇區(qū)包含1024個字節(jié)，所以通過讀/寫磁頭的二進(jìn)制位速度大約為6.5Mbit/s。因此，如果

控制器打算與磁盤中讀取到的數(shù)據(jù)同步，那么控制器與磁盤驅(qū)動器之間的通信速度至少要這

么快。

3.用ASCII碼表示的300頁小說大概有IMB,即8000000位。因此，如果要以57600bit/s的速度

傳輸整部小說，大約需要139s或即2'min。

3

2.6節(jié)

1.該管道會包含指令B1B0（正在執(zhí)行）、5002甚至B0AA。如果寄存器1中的值與寄存器0中的

值相等，那么就會執(zhí)行向地址B0轉(zhuǎn)移的指令。那么對于流水線中指令所做的努力則白費了。

另一方面，并沒有浪費時間，因為對于這些指令所做的努力并沒有花費額外的時間。

2.如果不采取任何預(yù)防措施，那么在該程序的前面部分有機會對存儲單元F8和F9進(jìn)行修改之

前，這兩個單元的信息已經(jīng)作為指令被讀取出來了。

3.a.試圖給該單元加1的CPU可以在該單元中首先讀取值。接著，另外一個CPU讀取該單元的

值。（需要注意的是：在這個時候，兩個CPU檢索到的是相同的值。）如果在第一個CPU

完成它的加法并將其結(jié)果寫入該單元之后，第二個CPU才完成它的減法，并記下結(jié)果，那

么單元中最后的值只是反映了第二個CPU的活動。

388問題與練習(xí)答案

b.兩個CPUM能還像以前一樣從存儲單元中讀取數(shù)據(jù)，但是，第二個CPU這次可能會在第一

個CPU之前寫下結(jié)果。因此，該單元的最后值就只反映了第一個CPU的活動。

第3章

3.1節(jié)

1.一個傳統(tǒng)的例子是，人們?yōu)橘徺I比賽的門票而排的隊列。在這種情況中，可能存在著某些人

想“插隊”，這就破壞了FIFO結(jié)構(gòu)。

2.選項（b）和（c）。

3.實時處理是指：程序的執(zhí)行要與機器環(huán)境中的活動相協(xié)調(diào)。交互式處理是指：程序在執(zhí)行時，

人要與其進(jìn)行交互。成功的交互式處理需要良好的實時特性。

4.分時是在單處理器的機器上實現(xiàn)多任務(wù)處理的一種技術(shù)。

3.2節(jié)

1.外殼（shell）：與機器環(huán)境進(jìn)行通信。

文件管理程序：協(xié)調(diào)機器的海量存儲器的使用。

設(shè)備驅(qū)動程序：處理與機器的外圍設(shè)備的通信。

內(nèi)存管理程序：協(xié)調(diào)機器的主存的使用。

調(diào)度程序：協(xié)調(diào)系統(tǒng)中的進(jìn)程。

分派程序：控制進(jìn)程的CPU時間的分配。

2.它們之間的界線比較模糊，其差別通常在于持有者的觀點。粗略來說，實用軟件完成的是基

本的、通用的任務(wù)，而應(yīng)用軟件則通常只完成針對機器某一特定應(yīng)用的任務(wù)。

3.虛擬存儲器是虛構(gòu)的存儲空間，其表面上的存在是通過這樣的過程創(chuàng)建的，即數(shù)據(jù)和程序在

主存和海量存儲器之間來回交換數(shù)據(jù)。

4.當(dāng)機器接通電源時，CPU就開始執(zhí)行駐留在ROM中的引導(dǎo)程序。這個引導(dǎo)程序引導(dǎo)CPU完成

這樣一個過程，即把操作系統(tǒng)從海量存儲器傳送到主存的易失存儲區(qū)內(nèi)。當(dāng)這個傳送操作完

成時，引導(dǎo)程序就指引CPU跳轉(zhuǎn)至操作系統(tǒng)。

3.3節(jié)

1.程序是指令的集合，而進(jìn)程是遵循這些指令的操作。

2.CPU完成它的當(dāng)前機器周期，保存當(dāng)前進(jìn)程的狀態(tài)，并把它的程序計數(shù)器設(shè)為?個預(yù)定的值

（即中斷處理程序的位置）。這樣一來，將要執(zhí)行的下一條指令就是中斷處理程序中的第一條

指令。

3.--種方法是給它們較高的優(yōu)先權(quán)，使它們可以被分派程序引用。另種方法是給優(yōu)先權(quán)較高

的進(jìn)程以較長的時間片。

4.如果每個進(jìn)程都用完它的整個時間片，那么機器每秒鐘可以給至多20個進(jìn)程提供完整的時間

片。如果一些進(jìn)程沒有用完它們的時間片，那么這個進(jìn)程數(shù)目的值可能還會大些，但是花在

實現(xiàn)進(jìn)程上下文切換所需的時間可能會更多（見第5題）。

5?總共50nl的機器時間將實際花在進(jìn)程執(zhí)行中。然而，當(dāng)一個進(jìn)程請求一個I/O活動時，它的

5000

時間片在控制器完成這個請求時就終止了。這樣?來，如果每個進(jìn)程都在它的時間片只用了

問題與練習(xí)答案389

時就作出這樣的請求，那么機器的效率將降至‘。也就是說，機器用于執(zhí)行進(jìn)程上下文

2

切換和用于進(jìn)程的執(zhí)行的時間樣多。

3.4節(jié)

1.這個系統(tǒng)保證，該資源一次不會被多于一個進(jìn)程使用；然而，它表明了該資源是嚴(yán)格按照交

替方式分配的。一旦一個進(jìn)程已經(jīng)用完并放棄了這個資源，那么如果該進(jìn)程要再次訪問這個

資源時，它就必須得等待其他進(jìn)程使用這個資源。即使是第?個進(jìn)程馬上需要這個資源，而

其他進(jìn)程在一段時間內(nèi)不需要這個資源時，情況依然如此。

2.如果兩輛汽車同時進(jìn)入這個隧道的兩端，那么它們將都不知道對方的存在。汽車進(jìn)入和燈的

打開過程是臨界區(qū)的另一個例子，或者說，在這種情況下，我們可以稱它為臨界過程。在這

個術(shù)語中，我們可以概括出這個系統(tǒng)的缺點，即隧道兩端的汽車能夠同時執(zhí)行臨界過程。

3.a.這保證了不可共享的資源不能被部分地請求和分配；也就是說，要么將整個橋梁給?輛汽

車，要么就什么也不給。

b.這就意味著：不可共享的資源可以被強制收回。

c.這就使得不可共享資源成為可共享的，這樣就消除了競爭。

4.箭頭序列在這個有向圖中形成了?個閉環(huán)。根據(jù)這個觀察的結(jié)果，已經(jīng)開發(fā)出了些技術(shù)，

使得某些操作系統(tǒng)能夠識別出死鎖的存在，并據(jù)此采取適當(dāng)?shù)母恼胧?/p>

3.5節(jié)

1.姓名和日期被認(rèn)為是不好的候選對象，這是因為它們是常用的選擇，所以容易成為密碼猜測

者的目標(biāo)。使用完整的單詞也被認(rèn)為不好，這是因為密碼猜測者能夠很容易編寫一個程序，

用來嘗試字典里的所有單詞。而且，只包含字符的密碼也是不鼓勵的，這是因為它們是從有

限的字符集中構(gòu)成的。

2.利用兩位構(gòu)成的不同位模式的數(shù)目是4。如果需要更多的特權(quán)級別，那么設(shè)計者至少需要三

位來表示不同的級別，這樣一來，總共就有8個級別可供選擇。按照同樣的方式，對于少于4

個特權(quán)級別的自然選擇就會是2,它是用?位可表示的位模式的數(shù)目。

3.這個進(jìn)程可以更改操作系統(tǒng)程序，使得分派程序把每個時間片都分配給該進(jìn)程。

第4章

4.1節(jié)

1.開放式網(wǎng)絡(luò)是這樣的一種網(wǎng)絡(luò)：它的規(guī)格說明以及協(xié)議是公開的，于是不同的廠商可以生產(chǎn)

相互兼容的產(chǎn)品。

2.兩者都是通過連接兩個總線以形成一個更大的總線網(wǎng)絡(luò)。不過，中繼器傳輸所有的信息，但

是網(wǎng)橋只傳輸那些目的地是該網(wǎng)橋另一端的信息。

3.路由器是一臺連接兩個網(wǎng)絡(luò)以形成?個因特網(wǎng)的機器。術(shù)語網(wǎng)關(guān)（gateway）通常用于指將

一個域與因特網(wǎng)其他部分相連的路由器。

4.郵購業(yè)務(wù)以及它的客戶，銀行出納員以及銀行的客戶，或者藥劑師以及他的顧客。

5.在交通流量、口頭電話通信以及禮儀上有許多的協(xié)議。

390問題與練習(xí)答案

4.2節(jié)

1.一個網(wǎng)絡(luò)標(biāo)識符標(biāo)識一個域。一個主機地址標(biāo)識一個域內(nèi)的一臺機器。這兩者組成了IP地址。

2.一臺主機完整的因特網(wǎng)地址包括其網(wǎng)絡(luò)標(biāo)識符以及該主機的地址。

3.3.4.5表示3個字節(jié)的位模式000000110000010000000101?位模式0001001100010000用點分十

進(jìn)制法表示為19.16。

4.這個問題可能有幾個答案。其中一個就是，它們都是從特殊到一般。助記形式的因特網(wǎng)地址

都是以一臺特定機器的名字開始，然后是TLD的名字。郵政地址是從個人的名字開始，然后

逐漸到比較大的區(qū)域，例如城市、州、國家。這個順序與IP地址是相反的，它最開始是標(biāo)識

域的位模式。

5.名字服務(wù)器有助于將助記地址翻譯成IP地址。郵件服務(wù)器傳輸、接收以及存儲郵件信息。FTP

服務(wù)器提供文檔傳輸服務(wù)。

6.SSH提供加密以及認(rèn)證。

4.3節(jié)

1.URL本質(zhì)上是一個文檔在萬維網(wǎng)上的地址。瀏覽器是幫助用戶訪問超文本的程序。

2.標(biāo)記語言是在文檔中加入解釋信息的一個系統(tǒng)。

3.HTML是一種特殊的標(biāo)記語言。XML是產(chǎn)生標(biāo)記語言的標(biāo)準(zhǔn)。

4.a.<html>表明個HTML文檔的開始。

b.<head>表明一個文檔首部的開始。

C.</body〉表明一個文檔主體的結(jié)束。

d.</a>表明鏈接到另一個文檔的項目的結(jié)束。

5.客戶端與服務(wù)器端是兩個用于標(biāo)識一個活動是在客戶的機器上實現(xiàn)的，還是在服務(wù)器的機器

上實現(xiàn)的術(shù)語。

4.4節(jié)

1.鏈路層接收報文，并將其傳送至網(wǎng)絡(luò)層。網(wǎng)絡(luò)層注意到這個報文是傳輸給另外一個主機的，

于是給該報文寫入了另外?個中間目的地址，然后將該報文送回鏈路層。

2.不同于TCP,UDP是一個無連接協(xié)議，它不能保證報文會在目的地被接收到。

3.每個報文都被賦予了一個跳數(shù)值，它決定了報文被中繼傳播的最大次數(shù)。

4.實際上沒有辦法。任何主機上的程序員都可以修改該主機的軟件，以保存這些記錄。這就是

給敏感數(shù)據(jù)加密的原因所在。

4.5節(jié)

1.惡意軟件進(jìn)入計算機系統(tǒng)最常用的方式是通過郵件附件或者是隱藏在受害者下載的軟件中。

然而，間諜軟件則通常放在不被受害者懷疑而訪問的萬維網(wǎng)服務(wù)器中。

2.一個域的網(wǎng)關(guān)是一個路由器，它只是將通過它的分組（報文的一部分）繼續(xù)轉(zhuǎn)發(fā)。因此，網(wǎng)

關(guān)上的防火墻不能通過它的內(nèi)容而只能通過它的地址信息過濾通信流。

3.使用口令可以保護數(shù)據(jù)（當(dāng)然也包括信息）。加密的使用可以保護信息。

4.對于公鑰加密系統(tǒng)，知道報文如何被加密并不能夠?qū)笪倪M(jìn)行解密。

5.這些問題是國際化的，因此不隸屬于某一個政府的法律。不過，法律修正只是給那些受傷害

人一些幫助，并不能真正防止傷害。

問題與練習(xí)答案391

第5章

5.1節(jié)

1.進(jìn)程是執(zhí)行算法的活動。程序是算法的表示。

2.在緒論里，我們引證了演奏音樂、操作洗衣機、構(gòu)造模型、表演魔術(shù)以及歐兒里得算法等算法。

我們在日常生活中遇到的許多“算法”按照我們的正式定義都不能算是算法。本書引證的長除

算法就是一個例子。另一個例子是時鐘執(zhí)行的算法：它的指針日復(fù)一日地走動，奏鳴鐘聲。

3.非正式定義沒有要求步驟是有序的和無歧義的，它只在要求里暗示，步驟是可執(zhí)行的且能終

止的。

4.這里存在兩點。一是這些指令定義了?個不可終止的過程。但是事實上，這個過程最終到達(dá)

這樣的狀態(tài)：你的口袋里沒有硬幣。實際上，這可能是個初始狀態(tài)。二是算法是有歧義的。

這個算法正:像所表示的，它沒有告訴我們在這個情況下該怎么做。

5.2節(jié)

1.以物質(zhì)的組成為例。在一個層面上，原語被認(rèn)為是分子，而分子實際是由原子組成的，原子

又是由電子、質(zhì)子和中子組成的。今天，我們知道，這些“原語”甚至也是合成物。

2.一旦一個過程被正確地構(gòu)建，那么它就可以用作較大程序結(jié)構(gòu)的構(gòu)件塊，不必再重新考慮該

過程的內(nèi)部構(gòu)成。

3.X<-較大的輸入；

Y一較小的輸入；

while（Y不是0）do

（Remainder<-X被Y除后的余數(shù)；

X-Y;

YRemainder）;

GCD—X

4.光的所有其他顏色都可由紅、藍(lán)和綠組合產(chǎn)生。所以，電視機的顯像管被設(shè)計成能產(chǎn)生這三

種基色。

5.3節(jié)

1.a.if（n=1orn=2）

then（答案是含有一個值n的列表）

else（n除以3,得到商q和余數(shù)r

if（r=O）

then（答案是含有q個3的列表）

if（r=l）

then（答案是含有（q-1）個3和2個2的列表）

if（r=2）

then（答案是含有q個3和1個2的列表）

）

b.結(jié)果是含有667個3的列表。

c.用小的輸入值來試驗，直到看出一個模式。

392問題與練習(xí)答案

2.a.可以。提示：把第一個棋子放在中心，這樣使得其他各個象限覆蓋一個正方形時它能避

免該象限含有那個洞。每個象限是原來問題的較小版本。

b.有一個洞的棋盤含有2)1個正方形，而每個棋子實際覆蓋3個正方形。

c.對于知道一個問題的解如何能夠幫助解決其他問題，問題a和b提供了極好的例子。見Ploya

的第4階段。

3.Thisisthecorrectanswer.

4.簡單地設(shè)法去拼裝圖片是一個白底向上的方法。然而，通過觀察拼圖盒來看圖形是什么樣子

為你的方法增加了自頂向下的成分。

5.4節(jié)

1.把while語句的測試修改為“目標(biāo)值不等于當(dāng)前表項并且還有表項耍檢查”。

2.Z<-0;

X—1;

repeat(Z<—Z+X;

X-X+1)

until(X=6)

3.這是C語言中的一個問題。當(dāng)關(guān)鍵字do和while分隔開若干行時，讀程序的人常常會在對while

語句的正常解釋上遇到障礙。特別是，一個do語句結(jié)尾處的while常常被解釋為一個while語

句的開始。所以，最好使用不同的關(guān)鍵字來表示先測試循環(huán)結(jié)構(gòu)和后測試循環(huán)結(jié)構(gòu)。

4.CherylAliceAlice

GeneCherylBrenda

AliceGeneCheryl

BrendaBrendaGene

5.堅持把主元放到列表里一個相同表項的上面是浪費時間。例如，按建議進(jìn)行修改，然后對所

有表項都相同的列表嘗試這個修改后的新程序。

6.proceduresort(List)

Ni1;

while(N小JList的長度)do

(J-N+1;

whilc(J不大JList的長度)do

(if(位置J里的表項小于位置N里的表項)

then(交換兩個表項)

J1J+1)

N-N+1)

7.下面這個解決方案的效率不是很高，你能使其效率更高嗎？

proceduresort(List)

N-List的長度；

While(N大于l)do

(J-List的長度；

while(J大于1)do

(if(位置J里的表項小于位置J-l里的表項)

問題與練習(xí)答案393

then(交換兩個表項)

J—J-1)

N—N-1)

5.5節(jié)

1.考慮的第一個名字是Henry,接下來是Larry,最后是Joe。

2.8,17

3.1,2,3,3,2,1

4.終止條件是“N大于等于3”(或“N不小于3”)。該條件的前提是沒有額外的激活被創(chuàng)建。

5.6節(jié)

1.如果該機器1s可以排序100個名字，那么它1s可以進(jìn)行」(10000.100)次比較。這意味著，每

4

次比較所花費的時間近似于0.0004s。因此，排序1000個名字平均需要1(1000_000」000)次

4

比較，大概需要100s或12min。

3

2.二分搜索法屬于。(1g")、順序搜索法屬于。(〃)，而插入排序法屬于

3.0(lgn)類是效率最高的，接著是。(〃)、。(心和。("工

4.回答是不正確的，盡管聽起來可能是對的。事實是3張卡片中有兩張兩面是一樣的。干是，

取得這樣一張牌的概率是2/3。

5.不正確。如果被除數(shù)小于除數(shù)，如3/7,給出的答案是1,盡管正確結(jié)果應(yīng)該是0。

6.不正確。如果X的值是0,而丫的值不是0,那么所給出的回答是不正確的。

7.每次構(gòu)建終止測試時，語句"Sum=l+2+…+K并且K小于等于為真。把這與終止條件“K

大于等于V'合并產(chǎn)生所希望的結(jié)論“Sum=l+2+…+M，。因為K初始化為0,并且每通過詼

循環(huán)增加1,所以它的值最終一定到達(dá)N。

8.不能保證。超出硬件和軟件所能控制的問題，如機械故障和電氣問題等，都會影響計算。

第6章

6.1節(jié)

1.一個用第三代語言編寫的程序，從某種意義上說它是獨立于機器的，因為它的運行步驟不是

按照諸如寄存器和存儲單元地址這樣的機器特征來描述的。在另一方面，從某種意義上說，

它又是依賴于機器的，因為算數(shù)溢出和截斷誤差還是會出現(xiàn)。

2.主要差別是，匯編器把源程序里的每條指令只翻譯為一條機器指令，而編譯器往往要產(chǎn)生許

多條機器語言指令才能等價于一條源程序指令。

3.說明性范型在于開發(fā)所要解決的問題的描述。函數(shù)式范型使程序員集中于把問題的解決用較

小的問題的解來描述。面向?qū)ο蠓缎蛣t強調(diào)描述問題的環(huán)境里的成分。

4.與前幾代語言相比，第三代語言使得程序比較多地用問題的環(huán)境來表達(dá)，比較少地用計算機

細(xì)節(jié)來表達(dá)。

394問題與練習(xí)答案

6.2節(jié)

1.使用描述性常量可以改進(jìn)程序的可理解性。

2.聲明語句描述術(shù)語，命令語句描述算法中的步驟。

3.整型、實型、字符型和布爾型。

4.if-then-else和while循環(huán)結(jié)構(gòu)很常見。

5.同構(gòu)數(shù)組所有的成分有同樣的類型。

6.3節(jié)

1.局部變量僅在像過程這樣的程序單元內(nèi)是可訪問的，全局變量在整個程序中都是可訪問的。

2.函數(shù)是這樣的一個過程，它返回一個與函數(shù)名相關(guān)聯(lián)的值。

3.因為它們就是這樣的。I/O運算實際上是調(diào)用該機器的操作系統(tǒng)內(nèi)的例程。

4.形參是過程內(nèi)的標(biāo)識符。它是實參這個值的占位符號，在該過程被調(diào)用時，實參才傳遞給該

過程。

5.過程用于執(zhí)行一個動作，而函數(shù)用于產(chǎn)生一個值。于是，如果過程的名字反映它所執(zhí)行的動

作，函數(shù)名反映它所產(chǎn)生的值，那么這個程序就更可讀。

6.4節(jié)

1.詞法分析：識別標(biāo)記的過程。

語法分析：識別程序的文法結(jié)構(gòu)的過程。

代碼生成：產(chǎn)生目標(biāo)程序指令的過程。

2.符號表是語法分析程序從程序的聲明語句得到的信息的記錄。

4.它們是一個或幾個下述子串的實例:

forwardbackwardchachacha

backwardforwardchachacha

swingrightchachacha

問題與練習(xí)答案395

swingleftchachacha

6.5節(jié)

1.類是對象的描述。

2.大概是Meteorclass,由它可構(gòu)造各種流星。在類Meteorclass內(nèi)，可以找

到名為

AimDirection的實例變量，它指示激光瞄準(zhǔn)的方向。這個變量大概會用在

fire、

turnRight和turnLeft等方法中。

3.類Employee可以包含與雇員的姓名、住址、服務(wù)年限等有關(guān)的特性。類FullTimeEmployee

可以包含與退休津貼有關(guān)的特性。類PartTimeEmployee可以包含與每周工作小時數(shù)利每小

時傭金等有關(guān)的特性。

4.構(gòu)造器是類里的一個特殊方法，它在創(chuàng)建該類的?個實例時執(zhí)行。

5.一個類里的某些項指定為私有，以防止其他程序單元直接訪問這些項。如果一個項是私有的，

那么修改這個項的影響應(yīng)該限于這個類的內(nèi)部。

6.6節(jié)

1.包含初始化執(zhí)行并發(fā)進(jìn)程的技術(shù)以及實現(xiàn)進(jìn)程間通信的技術(shù)。

2.?個方法是把負(fù)擔(dān)放在進(jìn)程上，另一個方法是把負(fù)擔(dān)放在數(shù)據(jù)上。后者的好處是把任務(wù)集中

在該程序的一個點上。

3.這包括天氣預(yù)報、空中交通管制、復(fù)雜系統(tǒng)（從核反應(yīng)到行人交通）的模擬、計算機網(wǎng)絡(luò)以

及數(shù)據(jù)庫維護。

6.7節(jié)

1.R、T和乙例如，我們可以證明，R是將「/?加到這個集合的結(jié)果，并且能夠證明這個解可以

得到空語句，證明如下:

空

3.a.thriftier(sue,carol)

thriftier(sue,john)

396問題與練習(xí)答案

b.thriftier(sue,carol)

thriftier(bill,carol)

c.thriftier(carol,john)

thriftier(bill,sue)

thriftier(sue,carol)

thriftier(bill,carol)

thriftier(billzjohn)

thriftier(sue,john)

4.mother(X,Y):-parent(X,Y),female(X)

father(XzY)：-parent(X,Y),male(X)

第7章

7.1節(jié)

1.一長串賦值語句序列并不比設(shè)計成幾句嵌套的if語句復(fù)雜。

2.在使用了一段固定時間后，發(fā)現(xiàn)錯誤的數(shù)目為多少？這里的一個問題就是不能預(yù)先估算出這

個值。

3.這里的關(guān)鍵問題就是要考慮如何能對軟件的屬性進(jìn)行度量。用于估算一段軟件中錯誤數(shù)目的

一種方法是，在這個軟件設(shè)計時故意放進(jìn)一些錯誤。然后，在認(rèn)為軟件已調(diào)試后，檢查一下,

看原先的錯誤還存在多少。例如，如果你在軟件中故意放入7個錯誤，在調(diào)試后消除了5個錯

誤，那么你就可以推測，軟件中錯誤的總數(shù)只有丁油母於

7做.料F除。

5

4.教育或許就是這樣一種領(lǐng)域。早在研究人員開始試圖弄明白人類是怎樣學(xué)習(xí)的之前，人類就

已經(jīng)成功地相互教導(dǎo)。因此，在教育領(lǐng)域，實踐家及其開發(fā)的技術(shù)占主導(dǎo)地位。在今天，許

多人都這么認(rèn)為：理論學(xué)家只會把事情弄糟。

7.2節(jié)

1.系統(tǒng)需求是從應(yīng)用環(huán)境的角度來表述的，而系統(tǒng)規(guī)格說明則是從技術(shù)術(shù)語的角度來表述的，

并確定如何滿足系統(tǒng)需求。

2.分析階段的注意力集中在預(yù)期系統(tǒng)必須完成的工作。設(shè)計階段集中討論系統(tǒng)是如何實現(xiàn)其目

標(biāo)的。實現(xiàn)階段集中在系統(tǒng)的實際構(gòu)成。測試階段則集中在確保系統(tǒng)做它應(yīng)該要做的事情。

3.軟件需求文檔的作用是：為客戶和軟件工程公司之間，在所要開發(fā)軟件的需求和規(guī)格說明問

題上達(dá)成一致而編寫的文檔。

7.3節(jié)

1.傳統(tǒng)的瀑布方法要求分析、設(shè)計、實現(xiàn)和測試階段按照線性方式實現(xiàn)，而原型開發(fā)模型則是

一種更為寬松的反復(fù)試驗、不斷探索的方法。

2.傳統(tǒng)的演化式原型開發(fā)是開發(fā)軟件的組織所實現(xiàn)的，而開放源碼開發(fā)的方法并不限制在

?個組織內(nèi)。在開放源碼開發(fā)的情況中，管理軟件開發(fā)過程的人沒有必要決定宣告呱些

增強，而在傳統(tǒng)的演化式原型開發(fā)中，管理軟件開發(fā)的人員要為員工分配明確的增強軟

件的任務(wù)。

3.對你而言，這是你要考慮的。如果你是軟件開發(fā)公司的管理者，你能夠?qū)δ愕墓疽N售的

軟件采用開放源碼的方法進(jìn)行開發(fā)嗎？

問題與練習(xí)答案397

7.4節(jié)

1.?部小說的各章之間相互依存，而一部百科全書各個章節(jié)之間很大程度上是相互獨立的。所

以，小說的章節(jié)之間比百科全書的章節(jié)之間有更大的耦合度。然而，百科全書中的章節(jié)可能

比小說里的章節(jié)有更高的內(nèi)聚度。

2.累計積分可能是數(shù)據(jù)耦合的一個例子。其他可能存在的“耦合”包括疲勞、沖力、對對手策

略的了解，可能還有自信心。在許多體育運動項目中，因一局比賽的結(jié)束而重新開始下一局,

局的內(nèi)聚度會增加。例如，在棒球運動中，一個隊即使以滿壘結(jié)束了上輪擊球，每次輪到擊

球也都以沒有跑壘選手開始。在其他有些運動中，各單元分別記分，如網(wǎng)球比賽中，每局的

輸贏與其他局無關(guān)。

3.這是一個難題。從一種觀點來看，我們可以從把每件事情放在單一模塊中開始。這就造成了

較低的內(nèi)聚度而根本沒有耦合。然后，如果我們開始把單一模塊分割成一些較小的模塊，結(jié)

果就會使得耦合度增加。所以我們可能會得出結(jié)論：內(nèi)聚度的增加易于導(dǎo)致耦合度的增加。

從另一方面講，假設(shè)手頭上的問題自然地分割成3個內(nèi)聚度較高的模塊，稱為A、B和C。如

果原始的設(shè)計沒有注意到這種自然的分割（例如，A的泮任務(wù)可能與8的一半任務(wù)放在了

一起，等等），我們希望內(nèi)聚度低而耦合度高。在這種情況下，重新設(shè)計系統(tǒng)，將任務(wù)A、B

和C分離至不同的模塊中，這就極有可能在增加模塊內(nèi)的內(nèi)聚度的同時降低了模塊間的耦合

度。

4.你可以添加一個箭頭，用來說明ControlGatne模塊必須告知UpdateScore模塊，誰贏得了

比賽。然后，再在其另外一個方向上添加一個箭頭，用來說明當(dāng)UpdateScore模塊把控制

權(quán)移交到ControlGame模塊時，它就將報告當(dāng)前的狀態(tài)（諸如“局結(jié)束”或“比賽結(jié)束”

等）。

5.你可以添加一些箭頭，用來說明控制權(quán)從Judge傳到PlayerA,且在Judge把控制權(quán)傳給

Score之前傳回到Judge。

6.傳統(tǒng)的程序員是在語句的基礎(chǔ)上寫程序，如第6章所介紹的；而構(gòu)件裝配員則是通過連接稱

為構(gòu)件的預(yù)制塊來構(gòu)建程序。

7.5節(jié)

1.首先確定的是，你的圖處理的是數(shù)據(jù)（不是書本的流動）。下面的圖就表明：書ID（來源于

讀者）和讀者記錄（來源于圖書館文件）結(jié)合成借書記錄，并存放在圖書館文件中。

讀者記錄

圖書

館文件

航空公司

乘客

398問題與練習(xí)答案

3.

入住

5.設(shè)計模式為實現(xiàn)反復(fù)出現(xiàn)的軟件主題提供了標(biāo)準(zhǔn)的、成熟的方法。

7.6節(jié)

1.軟件測試的目的是為了找出錯誤。那么，從這個意義上講，沒有發(fā)現(xiàn)錯誤的測試就是失

敗的。

2.辦法之就是考慮模塊中的分支數(shù)。例如，一個過程模塊，它包含

了大量的循環(huán)和

if-then-else語句，那么它很可能比一個帶有簡單的邏輯結(jié)構(gòu)的模塊更容易出錯。

3.邊界值分析會建議你用一個有100個數(shù)據(jù)項的表和一個沒有數(shù)據(jù)項的表對這個軟件進(jìn)行測

試。你還可以用一個已經(jīng)排好序的表進(jìn)行測試。

7.7節(jié)

1.文檔采用的形式有用戶文檔、系統(tǒng)文檔和技術(shù)文檔。通常是伴隨著手冊一起出現(xiàn)的，有注釋

和精心編寫代碼的源程序，程序本身顯示在終端上的交互式消息，有數(shù)據(jù)字典，以及文檔的

設(shè)計格式，如結(jié)構(gòu)圖、類圖、數(shù)據(jù)流圖和實體-聯(lián)系圖等。

2.在開發(fā)階段和修改階段。問題在于，修改必須要像原始程序一樣完全文檔化。（同樣，軟件

在其使用階段也要文檔化。例如，系統(tǒng)的一個用戶可能會發(fā)現(xiàn)問題，這個問題不是確定的，

而僅僅會在系統(tǒng)的用戶手冊的以后版本中得到反映。而且，有時候，有關(guān)軟件使用文檔的書

籍是在該軟件已經(jīng)使用了一段時間并開始流行后寫的。）

3.不同的人對此有不同的觀點。有些人認(rèn)為程序是整個項目的關(guān)鍵，所以自然更重要。而另一

部分人則認(rèn)為，如果程序沒有文檔，則它什么也不是，因為如果你不能理解一個程序，你就

不會使用和修改它。而且，如果有良好的文檔，創(chuàng)建程序的任務(wù)就“容易”被再創(chuàng)造。

7.8節(jié)

1.有時候，法院對實質(zhì)上的雷同解釋得相當(dāng)廣泛，考慮雷同遠(yuǎn)不止程序在文字成分上類似。一

些“非文字”成分已經(jīng)考慮在內(nèi)，如程序結(jié)構(gòu)、設(shè)計記錄、軟件產(chǎn)生的感觀等。

問題與練習(xí)答案399

2.版權(quán)法和專利法有益于社會，是因為它們鼓勵新產(chǎn)品的創(chuàng)造者使他們的產(chǎn)品為公眾所用。行

業(yè)保密法有益于社會，是因為它們允許公司保護其產(chǎn)品開發(fā)的步驟免受競爭對手的侵犯。如

果沒有這種保護，公司會在新產(chǎn)品的大量投資上猶豫不決。

3.不承擔(dān)責(zé)任聲明不能成為公司玩忽職守的保護傘。

第8章

8.1節(jié)

1.表：運動隊隊員的名單。

棧：自助餐廳一疊盤子。

隊列：食堂里排的隊。

樹：許多政府部門的組織圖。

2.D和C是葉子(或終端)結(jié)點。B?定是根結(jié)點，因為所有其他結(jié)點都有父結(jié)點。

3.如果你想編寫一個下跳棋的游戲程序，那么表示棋盤的數(shù)據(jù)結(jié)構(gòu)將會是一個靜態(tài)數(shù)據(jù)結(jié)構(gòu)，

這是因為棋盤的大小在游戲過程中是不會改變的。然而，如果你要編寫--個玩多米諾游戲的

程序，那么表示構(gòu)成臺上多米諾模式的數(shù)據(jù)結(jié)構(gòu)將會是一個動態(tài)數(shù)據(jù)結(jié)構(gòu)，這是因為這個模

式的大小是可變的，而且不能預(yù)先確定。

4.電話簿實質(zhì)上是一個用來指向人的指針(電話號碼)集合。犯罪現(xiàn)場留下來的線索是(可能

加密過了)指向罪犯的指針。

8.2節(jié)

1.537428196

2.如果R為矩陣的行數(shù)，那么公式就為H(J-l)+(/-I)

3.(ex,)+j

4.頭指針包含NIL值。

5.Last要打印的最后?個名字

Finishedfalse

(CurrentPointer頭指針；

while(CurrentPointer非NILandFinished=false)do

打印CurrentPointer指向的項,

if(正在打印的名字=last)

then(Finishedtme)

CurrentPointerthevalueinthepointerCellintheentrypointedtobyCurrenPointer指向的項中的指

針單元的值)

6.棧指針指向與棧底直接相鄰的那個單元。

7.把棧表示為一個一維數(shù)組，并把棧指針表示為一個整型變量。然后利用這個棧指針來保持棧

頂在數(shù)組中位置的一個記錄，而不是實際的存儲器地址。

8.空和滿這兩種情況都是由頭指針和尾指針相等來指示。這樣一來，需要一些附加信息來區(qū)分

這兩種情況。

400問題與練習(xí)答案

9.

根指針

8.3節(jié)

1.

2.當(dāng)查找J時:

當(dāng)查找P時:

3.

proceHurePrintTreefTree)pfocedurcTrlntTree(Tree)

if（Tree的根結(jié)點不為NIL）iffTree的根結(jié)點不為NIL）

then（對以Tree的左分支出現(xiàn)的樹應(yīng)then（對以Tree的左分支出現(xiàn)的樹應(yīng)

用PrintTree過程;用PrintTree過程;

PrintTree的根結(jié)點;犬PrintTree的根結(jié)點；

對以Tree的右分支出現(xiàn)的樹、產(chǎn)以Tree的右分支出現(xiàn)的樹應(yīng)用

—----------

PrintTree過程。)

當(dāng)K被打印時，在這里

問題與練習(xí)答案401

4.在每個結(jié)點上，每個孩子指針可用來表示字母表中的一個字母。沿著表示一個單詞的拼寫次

序的指針序列遍歷樹的路徑，就可以表示一個單詞。如果一個結(jié)點表示的是一個拼寫正確的

單詞的結(jié)束，那么它就可以用一種特殊的方式進(jìn)行標(biāo)記。

8.4節(jié)

1.類型是一個模板；而這個類型的實例是從這個模板構(gòu)建出的一個真實的實體。打個比方，狗

是動物的一類，而Lassie和Rex則是該類型的一個實例。

2.用戶自定義數(shù)據(jù)類型是數(shù)據(jù)組織的一種描述，而抽象數(shù)據(jù)類型則包括了對數(shù)據(jù)進(jìn)行處理的操

作。

3.這里的問題在于，你是選擇用鄰接表還是用鏈表來實現(xiàn)。你的選擇會影響到插入新項、刪除

舊項以及找到感興趣的項這些操作過程的結(jié)構(gòu)。然而，該抽象數(shù)據(jù)類型的實例的用戶是看不

到這種選擇的。

4.這個抽象數(shù)據(jù)類型至少得包含一個數(shù)據(jù)結(jié)構(gòu)的描述，用來存儲賬戶余額，以及通過支票進(jìn)行

存取的過程。

8.5節(jié)

1.抽象數(shù)據(jù)類型和類都是構(gòu)建類型實例的模板。然而，類更為普遍，這就在于它與繼承性相關(guān)

聯(lián)，可以只描述一組過程的集合。

2.類是模板，通過它來構(gòu)建對象。

3.這個類可以包含一個循環(huán)隊列，以及用于添加項、刪除項、測試隊列為滿和測試隊列為空的

這些操作的過程。

8.6節(jié)