內(nèi)存按字節(jié)編址,地址區(qū)間為[90000H,CFFFFH],若用32K*8bit的存儲(chǔ)器芯片構(gòu)成該內(nèi)存,需要__塊???

（1）首先根據(jù)地址區(qū)間[90000H,CFFFFH]，可以計(jì)算地址空間為：CFFFFH - 90000H + 1 = 40000H?
因?yàn)?0000H = 2^16B 那么 40000H = 4 * (2^16)B?
(2)32K = 32*(2^10)B?
那么內(nèi)存所需芯片數(shù)為： （ 4 * (2^16) ）/ 32*(2^10 ) = 8;

上面這題是一樣的，現(xiàn)在看第二題。每個(gè)存儲(chǔ)單元可以存儲(chǔ)16位二進(jìn)制數(shù)，所以排除了B和D。

400H = 4*2^16; x = 4*2^16 / 16*4 ===> x = 256 , 所以這個(gè)芯片的容量是256層樓，每一樓的寬度為16bit.

棧

波蘭式、逆波蘭式是《數(shù)據(jù)結(jié)構(gòu)》課程中講解關(guān)于棧的時(shí)候提到的，棧是很簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。但是這些理論的提出卻是計(jì)算機(jī)早期發(fā)展領(lǐng)域的重大突破，值得仔細(xì)回味。

中綴表達(dá)式? 我們?cè)跀?shù)學(xué)中學(xué)到的表達(dá)式被稱為中綴表達(dá)式，操作符號(hào)在操作數(shù)中間，比如 2 + 3 * (5 - 1)。對(duì)人類而言，這種表達(dá)方式顯而易見，求值也很直接，先算乘除再算加減，先算括號(hào)內(nèi)再算括號(hào)外。

然而，這個(gè)表達(dá)式對(duì)于計(jì)算機(jī)而言卻很費(fèi)解。你可能會(huì)有疑問：這有什么難理解的嘛，在JavaScript、Python或者Ruby，甚至是Java里面都可以通過eval(“2 + 3 * (5 - 1)”)來計(jì)算這個(gè)表達(dá)式。當(dāng)然，這里的計(jì)算機(jī)并不是指現(xiàn)而今強(qiáng)大的計(jì)算機(jī)和高級(jí)編程語言，而是指上個(gè)世紀(jì)中頁還處于發(fā)展初期的計(jì)算機(jī)。

前綴表達(dá)式? 早在1920年，波蘭科學(xué)家揚(yáng)·武卡謝維奇就發(fā)明了一種不需要括號(hào)的表示法，可以用來表示一個(gè)計(jì)算表達(dá)式。即將操作符號(hào)寫在操作數(shù)之前，也就是前綴表達(dá)式，即波蘭式（Polish Notation, PN）。這種表達(dá)式直到1960年計(jì)算機(jī)出現(xiàn)后才發(fā)揮出其威力。

比如2 + 3 * (5 - 1)這個(gè)表達(dá)式的前綴表達(dá)式為+ 2 * 3 - 5 1來表示。

閱讀這個(gè)表達(dá)式需要從左至右讀入表達(dá)式，如果一個(gè)操作符后面跟著兩個(gè)操作數(shù)時(shí)，則計(jì)算，然后將結(jié)果作為操作數(shù)替換這個(gè)操作符和兩個(gè)操作數(shù)，重復(fù)此步驟，直至所有操作符處理完畢。從左往右依次讀取，直到遇到- 5 1，做計(jì)算后，將表達(dá)式替換為+ 2 * 3 4，然后從左往右再次讀取，直到遇到* 3 4，做計(jì)算后將表達(dá)式替換為+ 2 12，然后從左往右依次讀取，讀到+ 2 12，計(jì)算得到14，到此結(jié)束。

可以看到，這種計(jì)算過程也相當(dāng)復(fù)雜，需要多次遍歷表達(dá)式，而且需要識(shí)別一個(gè)操作符后面跟著兩個(gè)操作數(shù)這種模式，相比而言，下文中的逆波蘭式要更為直接和簡(jiǎn)單。

如果你熟悉各種編程語言的話，這很像Lisp語言中的表達(dá)式（如下代碼）。需要注意的是，Lisp語言中的括號(hào)并不是數(shù)學(xué)意義上的的括號(hào)，Lisp中的函數(shù)是可以攜帶多個(gè)參數(shù)的，比如(+ 1 2 3)，因此需要使用括號(hào)來標(biāo)明函數(shù)參數(shù)。

Clojure1.5.1? user=>(+2(*3(-51)))14? 3. 后綴表達(dá)式? 后綴表達(dá)式也稱為逆波蘭式（Reverse Polish Notation, RPN），更加廣為人知一些，和前綴表達(dá)式剛好相反，是將操作符號(hào)放置于操作數(shù)之后，比如2 + 3 * (5 - 1)用逆波蘭式來表示則是：2 3 5 1 - * +。

逆波蘭式的計(jì)算也是從左往右依次讀取，當(dāng)讀到操作符時(shí)，將之前的兩個(gè)操作數(shù)做計(jì)算，然后替換這兩個(gè)操作數(shù)和操作符，接著讀取，重復(fù)此步驟。對(duì)于這個(gè)表達(dá)式，讀到5 1 -，得到4，然后讀取乘號(hào)，取出前面的3和上一步的計(jì)算結(jié)果4，并計(jì)算，到12，接著讀取加號(hào)+，計(jì)算2 12 +得到14，計(jì)算結(jié)束。

上面這個(gè)步驟可以很容易的用棧來實(shí)現(xiàn)：

從左往右依次讀取表達(dá)式，如果是數(shù)字則將該數(shù)字壓棧，如果是符號(hào)，則將之前的兩個(gè)數(shù)字出棧，做計(jì)算后，將計(jì)算結(jié)果壓棧，直到表達(dá)式讀取結(jié)束。棧中剩下的一個(gè)數(shù)就是計(jì)算結(jié)果。

逆波蘭式看起來像波蘭式反過來，比如5 + 1的波蘭式是+ 5 1，逆波蘭式為5 1 +或者1 5 +。也很明顯，逆波蘭式并不是簡(jiǎn)單的將波蘭式反過來，因?yàn)椋瑴p法和除法中減數(shù)和被減數(shù)、除數(shù)與被除數(shù)是不能交換的，即- 10 5和- 5 10就完全不一樣。

中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換? 因?yàn)橥ㄟ^后綴表達(dá)式來進(jìn)行計(jì)算只需要一個(gè)棧即可，從硬件和軟件上實(shí)現(xiàn)都是極為便利的，因此逆波蘭式在計(jì)算機(jī)領(lǐng)域的應(yīng)用更加廣泛，因此將中綴表達(dá)式轉(zhuǎn)換為逆波蘭式非常重要。

依然僅僅使用棧就可以將中綴表達(dá)式轉(zhuǎn)換成逆波蘭式，轉(zhuǎn)換過程如下：

從左往右遍歷中綴表達(dá)式中的每個(gè)數(shù)字和符號(hào)，弱是數(shù)字就輸出，成為逆波蘭式的一部分； 如果是右括號(hào)，或者是其他符號(hào)并且比當(dāng)前棧頂符號(hào)的優(yōu)先級(jí)低，則棧頂元素依次出棧并輸出； 然后將當(dāng)前符號(hào)進(jìn)棧，重復(fù)以上操作直到結(jié)束。

還是以2 + 3 * (5 - 1)為例：

首先讀入數(shù)字2，直接將其輸出，輸出為2，棧為空? 接著讀入加號(hào)+，由于棧為空，因此將其進(jìn)棧，輸出為2，棧為+? 接著讀入數(shù)字3，直接將其輸出，輸出為2 3，棧為+? 接著讀入乘號(hào)，比棧頂元素優(yōu)先級(jí)高，進(jìn)棧，輸出為2 3，棧為+? 讀入左括號(hào)(，直接進(jìn)棧，輸出2 3，棧為+ * (? 讀入數(shù)字5，直接將其輸出，輸出為2 3 5，棧為+ * (? 讀入減號(hào)-，棧頂元素為左括號(hào)，進(jìn)棧，輸出為2 3 5，棧為+ * ( -? 讀入數(shù)字1，直接將其輸出，輸出為2 3 5 1，棧為+ * ( -? 讀入右括號(hào)，依次輸出棧頂元素，直到左括號(hào)，括號(hào)不輸出，輸出2 3 5 1 -，棧為+ *? 已經(jīng)無元素可讀，依次輸出棧頂元素，直到棧為空，輸出2 3 5 1 - * +，棧為空? 這樣可以僅僅使用棧，首先將中綴表達(dá)式轉(zhuǎn)換為逆波蘭式，然后用本文第3節(jié)中的方法對(duì)后綴表達(dá)式進(jìn)行求值，整個(gè)過程使用棧來完成即可。

表達(dá)式樹與逆波蘭式? 還可以通過另外一種方法來將一個(gè)表達(dá)式轉(zhuǎn)換成波蘭式和逆波蘭式，這種方法依賴與樹，首先需要根據(jù)表達(dá)式構(gòu)建成樹，仍然以2 + 3 * (5 - 1)為例，下圖是其表達(dá)式樹。

我們發(fā)現(xiàn)這個(gè)樹的后序遍歷結(jié)果為2 3 5 1 - * +，剛好是其逆波蘭式；而其先序遍歷結(jié)果為+ 2 * 3 - 5 1剛好為其波蘭式；中序遍歷就不用說了，就是我們常見的中綴表達(dá)式。我們也可以通過這種特性來實(shí)現(xiàn)表達(dá)式的各種表示方法的轉(zhuǎn)換。