1、第一章緒論填空題（每空1分，共33分）1. 一個(gè)計(jì)算機(jī)系統(tǒng)包括硬性系統(tǒng)和軟件系統(tǒng)兩大部分2. 一臺(tái)計(jì)算機(jī)中全部程序的集合，稱為這臺(tái)計(jì)算機(jī)的軟件資源（系統(tǒng)）3. 計(jì)算機(jī)軟件可以分為系統(tǒng)軟件和應(yīng)用軟件兩大類?？茖W(xué)計(jì)算程序包屬于應(yīng)用軟性二3斷程序?qū)儆谙到y(tǒng)軟件（工具）4. 一種用助憶符號(hào)來表示機(jī)器指令的操作符和操作數(shù)的語言是二£編語宜5-數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)皺以及它們之間的尖系和運(yùn)算等的學(xué)科。6 ?數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R）,其中D是數(shù)據(jù)元素的有限集合，R是D上的去系 有限集合。7 .數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個(gè)方面

2、的內(nèi)容。8 .數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類,它們分別是二線性結(jié)構(gòu)和非線性結(jié)構(gòu)9?線性結(jié)構(gòu)中元素之間存在一對(duì)二關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多云邕圖形結(jié)構(gòu)中元素之間存在多對(duì) 多矢系。10?在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)？其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)、其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。11在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。12在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)o13數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是撅序、鏈?zhǔn)?、索引和散列。?shù)

3、據(jù)的運(yùn)算最常14用的有5種，它忙J分別是插入、刪除 ？修改查找.排序315 一個(gè)算法的效率可分為 亟 效率和 空間 效率。16?任何一個(gè)C程序都由一個(gè)主函數(shù)和若干個(gè)被調(diào)用的其它函數(shù)組成 。.單項(xiàng)選擇題（每小題1分，共15分）（B ） 1 ?通常所說的主機(jī)是指：A） CPUB） CPU和內(nèi)存C） CPU?內(nèi)存與外存 D） CPUx內(nèi)存與硬盤（c ） 2?在計(jì)算機(jī)內(nèi)部，一切信息的存??？處理和傳送的形式是：A） ACSII碼B） BCD碼C）二進(jìn)制D）十六進(jìn)制（D） 3 ?軟件與程序的區(qū)別是：A）程序價(jià)格便宜.軟件價(jià)格昂貴；B） 程序是用戶自己編寫的，而軟件是由廠家提供的；c）程序是用高級(jí)語言編寫的

4、，而軟件是由機(jī)器語言編寫的；D）軟件是程序以及開發(fā).使用和維護(hù)所需要的所有文檔的總稱，而程序只是軟件的一部分。（C ）1 4?所謂“裸機(jī)”是指：A）單片機(jī)B）單板機(jī)C）不裝備任何軟件的計(jì)算機(jī) D）只裝備操作系統(tǒng)的計(jì)算（0） 5?應(yīng)用軟件是A）所有能夠使用的軟件B）能被各應(yīng)用單位共同使用的某種軟件C）所有微機(jī)上都應(yīng)使用的基本軟件 D）專門為某一應(yīng)用目的而編制的軟件*A ） 6.C語言中的常量可分為整型常量、實(shí)型常量（A）符號(hào)常量（B）長整型常量.字符型常量及（枚舉）四種。（C）邏輯常量（D）二進(jìn)制整數(shù)）7.編譯程序的功能是：A）發(fā)現(xiàn)源程序中的語法錯(cuò)誤B）改正源程序中的語法錯(cuò)誤D）將某一高級(jí)語言程

5、序翻譯成另一種高級(jí)語言程序）8.系統(tǒng)軟件中最重要的是：A）操作系統(tǒng)B）語言處理系統(tǒng)）9 .可移植性最好的計(jì)算機(jī)語言是：A）機(jī)器語言B）匯編語言C）10 .非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A） 一對(duì)多尖系B）多對(duì)多矢系C）工具軟件高級(jí)語言D）自然語言C）多對(duì)一矢系D）數(shù)據(jù)庫管理系統(tǒng)D） 一對(duì)一尖系11 .數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無尖的是數(shù)據(jù)的 C）邏輯A）存儲(chǔ)B）物理12 .算法分析的目的是：A）找出數(shù)據(jù)結(jié)構(gòu)的合理性C）分析算法的效率以求改進(jìn)13 .算法分析的兩個(gè)主要方面是A）空間復(fù)雜性和時(shí)間復(fù)雜性C）可讀性和文檔性14?計(jì)算機(jī)算法指的是：A）計(jì)算方法B）排序方法15 .計(jì)算機(jī)算法必須具備

6、輸入？輸出和A）可行性.可移植性和可擴(kuò)充性C）確定燼.有窮燼和穩(wěn)定燼一結(jié)構(gòu)；D）物理和存儲(chǔ)B）研究算法中的輸入和輸出的矢系D）分析算法的易懂性和文檔性B）正確性和簡明性D）數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C）解決問題的有限運(yùn)算序列 D）調(diào)度方法 等5個(gè)特性。B）可行性.確定性和有窮性D）易讀性、穩(wěn)定性和安全性第2章線性表填空（每空1分，共13分）1.【嚴(yán)題集2.2】在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表蟲二生元素，具體移動(dòng)的元素個(gè)數(shù)與表長和該元素在表中的位置有矢。2.線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的矢系是一對(duì)一的3 .向一個(gè)長度為n的向量的第i個(gè)元素（lWiWn+1 ）之前插入一個(gè)元素時(shí)，需向

7、后移動(dòng)n? i+1個(gè)元素。4 .向一個(gè)長度為n的向量中刪除第i個(gè)元素（IWiWn ）時(shí)，需向前移動(dòng)垃一個(gè)元素。5 .在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為Q_CLL,因此，順序表也稱為隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。6 .【嚴(yán)題集2.2】順序表中邏輯上相鄰的元素的物理位置衛(wèi)生相鄰。單鏈表中邏輯：上相鄰的元素的物 理位置不淀相鄰。7 .【嚴(yán)題集2.2】在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指示?其時(shí)間復(fù)雜度O （n）8 ?在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn),需找到它的前驅(qū)結(jié)點(diǎn)的地價(jià)判斷正誤（在正確的說法后面打勾，反之打叉）（每小題I分，共10分）（X ） 1.鏈表的每個(gè)結(jié)

8、點(diǎn)中都恰好包含一個(gè)指針。答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含箏個(gè)捋針域 .分別存放蓼個(gè)指針。例如，雙向鏈表中的結(jié)點(diǎn)可以含有 兩個(gè)指針域 . 分別存放抬向其直接前趨和直接后繼結(jié)點(diǎn)的指針。（ X ） 2. 鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。斷鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無序，而鏈表的示意圖有序。（ X ） 3. 鏈表的刪除算法很簡單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后 ， 計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。錯(cuò) . 鏈表的結(jié)點(diǎn)不會(huì)移動(dòng)?只是抬針內(nèi)容改變。（ X ） 4. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型 ， 而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錨，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放

9、記錄型數(shù)據(jù)。（ X ） 5. 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。錯(cuò)，正好說反了。順序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜”（X ） 6.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。錯(cuò)，前一半正確 . 但后一半說法錯(cuò)誤. 那是鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)。順序存儲(chǔ)方式插入、刪除運(yùn)算效率較低，在表長為 n 的順序表中 . 插入和刪除一個(gè)數(shù)據(jù)元素，平均需移動(dòng)表長一半個(gè)數(shù)的數(shù) 據(jù) 元素。（ X ） 7. 線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。錯(cuò)，線性表有兩種存儲(chǔ)方式 ? 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。后者不要求連續(xù)存放。（ X ） 8. 線性表在順序存儲(chǔ)時(shí)，邏借上相鄰的元素未必在存儲(chǔ)的物

10、理位置次序上相鄰。錯(cuò)誤。線性表有兩種存儲(chǔ)方式，在順序存儲(chǔ)時(shí). 邏輯上相鄰的元素在存儲(chǔ)的物理位宜次序上 也相鄰。（ X ） 9. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。錯(cuò)謀。順序存儲(chǔ)方式不僅能用于存儲(chǔ)線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二叉樹是屬于非線性結(jié)構(gòu)，但其最佳存儲(chǔ)方式是順序存儲(chǔ)方式。（后一節(jié)介紹）（ X ）10.線性表的邏借順序與存儲(chǔ)順序總是一致的。錯(cuò)，理由同 7。鏈?zhǔn)酱鎯?chǔ)就無需一致。. 單項(xiàng)選擇題（每小題 1 分，共 10 分）（C ） 1. 數(shù)拯在訃算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲(chǔ)結(jié)構(gòu)（B）邏借結(jié)構(gòu)（C）順序存儲(chǔ)結(jié)構(gòu)（D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（B

11、） 2 個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長度為2,則第5個(gè)元素的地址是（A）110（B） 108（C）100 （D） 120（ A ） 3. 在 n 個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O （ 1 ）的操作是：（ A ） 訪問第 1 個(gè)結(jié)點(diǎn)（ 1 WiWn ）和求第 i 個(gè)結(jié)點(diǎn)的直接前驅(qū)（ 25）（ B ） 在第 1 個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（ lWiWa ）（ C） 刪除第 1 個(gè)結(jié)點(diǎn) （ lWiWn ）（ D ） 將 n 個(gè)結(jié)點(diǎn)從小到大排序（ B ） 4. 向一個(gè)有 127 個(gè)元素的順序表中插入一個(gè)新元素并保持原來顧序不變， 平均要移動(dòng)個(gè)元素（A） 8（ B） 63.5（C）

12、63（ D） 7（ A ） 5. 鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間：（ A ）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間尖系的指針（ B ）只有一部分，存放結(jié)點(diǎn)值（ C ） 只有一部分， 存儲(chǔ)表示結(jié)點(diǎn)間矢系的指針（ D ） 分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)（ B ） 6. 鏈表是一種采用 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表；（A）順序（B）鏈?zhǔn)剑–）星式（D）網(wǎng)狀（ D ） 7. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址：(A)必須是連續(xù)的(B)部分地址必須是連續(xù)的(C)一定是不連續(xù)的(D連續(xù)或不連續(xù)都可以(B ) 8 ?線性表L在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。

13、(A)需經(jīng)常修改L中的結(jié)點(diǎn)值(B)需不斷對(duì)L進(jìn)行刪除插入(C) L中含有大量的結(jié)點(diǎn)(D) L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜(C ) 9.單鏈表的存儲(chǔ)密度(A)大于1:( B )等于1:(C)小于1:(D)不能確泄(B ) 10.設(shè)aH a2 > a3為3個(gè)結(jié)點(diǎn)，整數(shù)Po, 3, 4代表地址，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為Po34PoS P .> ra2P| 今 A3 0(A)循環(huán)鏈表 (B)單鏈表(C)雙向循環(huán)鏈表(D)雙向鏈表第3章棧和隊(duì)列一?填空題(每空1分，共15分)1?棧和隊(duì)列都是一線性結(jié)構(gòu)，可以在向量的任何位置插入和刪除元素:對(duì)于棧只能在棧頂插入和刪除元素；對(duì)于隊(duì)列只能在M插入和？刪除元素。2

14、 .棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂一不允許插入和刪除運(yùn)算的一端稱為棧底3 . 叢列 是被限泄為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。4 .在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。5 .在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有工個(gè)元素。6 .向棧中壓入元素的操作是先移動(dòng)棧頂指針 ,后存入元素一7 .從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先移動(dòng)隊(duì)首指針.后取出元素。二判斷正誤(判斷下列概念的正確性，并作出簡要的說明。)(每小題 1分，共10分)(X ) 1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型 ？而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò).線性表是

15、邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無矢。(X) 2.在表結(jié)構(gòu)中最常用的是線性表 ，棧和隊(duì)列不太常用。錯(cuò).不一定吧？調(diào)用子程序或函數(shù)常用 CPU中也用隊(duì)列。(V ) 3.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。(V ) 4.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表？對(duì)運(yùn)算的定義略有不同而已。(X ) 5.棧和鏈表是兩種不同的數(shù)拯結(jié)構(gòu)。錯(cuò)?棧是邏輯結(jié)構(gòu)的概念.是特殊殊線性表.而鏈表是存儲(chǔ)結(jié)構(gòu)概念，二者不是同類項(xiàng)。(X) 6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯(cuò)?他們都

16、是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。(V ) 7.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。(X) 8.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。錯(cuò).后半句不 對(duì)c(X ) 9.一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是 12345。錯(cuò)？有可能。三.單項(xiàng)選擇題(每小題1分，共20分)(B ) 1 ?棧中元素的進(jìn)出原則是A.先進(jìn)先出B.后進(jìn)先出C.?？談t進(jìn)D.棧滿則出(C ) 2 .若已知一個(gè)棧的入棧序列是1,2, 3,，n,其輸出序列為pl, p2, p3,，pn,若pl=n,則pi為A. i B. n=i C.

17、 n-i+1D ?不確定解釋：當(dāng)pl=n,即n是最先出棧的，根據(jù)棧的原理，n必泄是最后入棧的(事實(shí)上題目已經(jīng)表明了 )，那么輸入 順序必泄是1,2, 3,，n,則出棧的序列是 m., 3, 2, E(若不要求順序出棧，則輸出序列不確泄)(B ) 3. K李春葆)1判定一個(gè)棧ST (最多元素為mO)為空的條件是A. ST->top<>0 B ? ST->top=0C. ST->topomOD. ST->top=mO(A)4.K李春葆判定一個(gè)隊(duì)列 QU (最多元素為mO)為滿隊(duì)列的條件是A. QU->rear QU->front = = mOB. Q

18、U->rear QU->front 1= = mOC . QU->front = = QU->rearD ? QU->front = = QU->rear+l解：隊(duì)滿條件是元素個(gè)數(shù)為由于約立滿隊(duì)時(shí)隊(duì)首指針與隊(duì)尾指針相差1,所以不必再減1 了 ？應(yīng)當(dāng)選An當(dāng)然，更正確的答案應(yīng)該取模'即：QU->front = = (QU->rear+l)% mO(D)5 ?數(shù)組Q n用來表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的 位宜，假定隊(duì)列 中元素的個(gè)數(shù)小于”，計(jì)算隊(duì)列中元素的公式為(A )r-f;( B ) (n+f-r) %n:

19、(C) n+r-f;( D ) (n+r-f) %n6.198初程P71從供選擇的答案中，選出應(yīng)填入下而敘述二A內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫 在答卷的 對(duì)應(yīng)欄內(nèi)。設(shè)有4個(gè)數(shù)據(jù)元素al、a2. a3和a4,對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按al、a2 a4次序每次進(jìn)入一個(gè)元素。假設(shè)?；蜿?duì)的初始狀態(tài)都是空。 現(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是A，第 二次出棧得到的元素是二 B是：類似地考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩 次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次：這時(shí)，第一次出隊(duì)得到的元素是一C,第二次出隊(duì)得到的元素是D

20、76;經(jīng)操作后，最后在棧中或隊(duì)中的元素還有E個(gè)。供選擇的答案：A? D: (Dal a2a3a4E: ?1230答：ABCDE=2. 4.1 > 2,27 . 從供選擇的答案中，選出應(yīng)填入下面敘述一內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。棧是一種線性表，它的特點(diǎn)是一 Ao設(shè)用一維數(shù)組 A l,衛(wèi)來表示一個(gè)棧，A n為棧底，用整型變量T指示當(dāng)前棧 頂位宜， A T為棧頂元素。往棧中推入(PUSH)-個(gè)新元素時(shí)，變量T的值一：從棧中彈出(POP)一個(gè)元素時(shí)，變量T的值 C。設(shè)棧空時(shí),有輸入序列a, b, c,經(jīng)過PUSH, POP. PUSH, PUSH, POP操作后，從棧中彈出的

21、元素的序列是P ?變量T的值是一。供選擇的答案：A:先進(jìn)先出B,C:加1D: ?a.bE:n+1b,ca+2后進(jìn)先出減1c,an進(jìn)優(yōu)于出不變b,ac,bn? 2出優(yōu)于進(jìn) 清0加2a,c隨機(jī)進(jìn)出減2n,向地址的低端答案：ABCDE=2. 2, 1.6.4注總？向地址的商端生長.稱為向上生成堆棧：向地址低端生長叫向下生成堆棧，木題中底部為遞減生成，稱為向下生成堆棧n8 .從供選擇的答案中，選出應(yīng)填入下而敘述一內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否4 :在做退棧運(yùn)算時(shí)，應(yīng)先判別棧是否_c當(dāng)棧中元素為n個(gè)，做進(jìn)棧運(yùn) 算時(shí)發(fā)生上溢，則說明該棧的最大容量為一匚為了增

22、加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的D分別設(shè)在這片內(nèi)存空間的兩端，這樣/只有當(dāng)E時(shí)，才產(chǎn)生上溢。供選擇的答案：A,B:空滿上溢 下溢C(Dn-1 n n+1 n/2D長度深度棧頂棧底E ： 兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn)兩個(gè)棧的棧頂在達(dá)?？臻g的某一位置相遇其中一個(gè)棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn)兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答案：ABCDE-Z1.2. 4,3第6章樹和二叉樹自測(cè)卷解答一.下面是有尖二叉樹的敘述，請(qǐng)判斷正誤（每小題1分，共10分）（V ） 1 ?若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在11個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有口個(gè)非空指針

23、域。（X） 2.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。（V） 3.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。（X ） 4.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。（X） 5.二叉樹中每個(gè)結(jié)點(diǎn)的矢鍵字值大于其左非空子樹（若存在的話）所有結(jié)點(diǎn)的矢鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的尖鍵字值。（應(yīng)當(dāng)是二叉排序樹的特點(diǎn)）（X） 6.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是 2基】一其中k是樹的深度。（應(yīng)25）（X） 7二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。（X） 8.對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有21個(gè)結(jié)點(diǎn)。（應(yīng)2卜1）（/） 9?用二叉鏈表法（

24、Unk-rlink ）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2ii個(gè)指針區(qū)域中有n+1個(gè)為宇指針。（正確。用二叉鏈表存儲(chǔ)包含 n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)共有 2n個(gè)鏈域。由于二叉樹中，除根結(jié)點(diǎn)外，每一 個(gè) 結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有ml個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針，還有n+1個(gè)空指針J即有 后繼鏈接的指針僅ml個(gè)。（J ） 10.具有12個(gè)結(jié)點(diǎn)的完全二叉樹有 5個(gè)度為2的結(jié)點(diǎn)。最快方法：用葉子數(shù)二皿2=6,再求112=21=5二、填空（每空1分，共15分）1 .由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有 5種形態(tài)。2 . 一棵深度為 6的滿二叉樹有it】+n2二0+而二2*31個(gè)分支名占和 2八二32個(gè)葉

25、干。注：滿二叉樹沒有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。3 .一棵具有2 5 7個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為 9。（注：用 Llog2 （n） J+l= L 8.xx J+l=94 .設(shè)一棵完全二叉樹有 700個(gè)結(jié)點(diǎn)，則共有迪個(gè)葉子結(jié)點(diǎn) 0答：最快方法：用葉子數(shù) =n/2 = 350 5 設(shè)一棵完全二叉樹具有 1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有 500個(gè)葉子 結(jié)點(diǎn).有499個(gè)度為2的結(jié) 點(diǎn)，有個(gè)結(jié) 點(diǎn)只有非空左子樹，有一個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)二n/2 = 500 , n2=no-l=499a另外，最后一結(jié)點(diǎn)為21屬于左葉子，右葉子是空的，所以 有1個(gè)非空左子樹。完

26、全二叉樹的特點(diǎn)決宦不可能有左空右不空的情況，所以非空右子樹數(shù)二0?6. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度為 11,最小深度為2。答：當(dāng)k=l （單叉樹）時(shí)應(yīng)該最深深度5 （層人當(dāng)k=n-l （nJ叉樹）時(shí)應(yīng)該最淺深度二 2 （層人但 不包括n=0或1時(shí)的特例情況。教材答案是“完全 k叉樹"，未定量。）7. 二叉樹的基本組成部分是：根（N人左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按 NLR次序），后序法（即按次序）和中序法（也稱對(duì)稱序法'即按LNR次序）這三種方法相互之間有尖聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH,中

27、序序列是FEBGCHD,則它的后序序列必是 o 解：法先由已知條件畫圖，再后序遍歷得到結(jié)果；法2:不畫圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定root,由中序先確左左子樹。例如)前序遍歷BEFCGDH中，根結(jié)點(diǎn)在最前面)是B;則后序遍歷中B 一定 在最后面。法3:遞歸計(jì)算。如B在前序序列中第一，中序中在中間(可知左右子樹上有哪些元素人則在后序中必為最后。如法對(duì)B的左右子樹同樣處理，則問題得解。8. 中序遍歷的遞歸算法平均空間復(fù)雜度為0) °答：即遞歸最大快套層數(shù)，即棧的占用單元數(shù)。精確值應(yīng)為樹的深度k十1,包括葉子的空域也遞歸了一次。9?用5個(gè)權(quán)值3,2,4,5,1

28、構(gòu)造的哈夫曼(Hufiiiiaii)樹的帶權(quán)路徑長度是33°解：先構(gòu)造哈夫曼樹,得到各葉子的路徑長度之后便可求出、VPL= (4+5+3) X2+(1+2) X3 二33>15)(9<、(6)(注：兩個(gè)合并值先后不同會(huì)導(dǎo)致編碼不同即哈夫曼編碼不唯45 3 /(3) (注：合并值應(yīng)排在葉子值之后)1 2(注：原題為選擇題： A. 32B. 33 C? 34 D. 15)三？單項(xiàng)選擇題(C ) 1 ?不含任何結(jié)點(diǎn)的空樹 (B )是一棵二叉樹；(D )既不是樹也不是二叉樹(A)是一棵樹；(C)是一棵樹也是一棵二叉樹；答：以前的標(biāo)答是 B,因?yàn)槟菚r(shí)樹的上義是1P1(C ) 2 ?

29、二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。(A )它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)；(B )它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)；(C)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)；(D)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用(C ) 3 .具 有n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 匚(A) rlog2 (n)l (B)L log2 (n)(C)L log2 (n) J+l (D) log2( n)+ll 注 1 : rxl 表示不小于 x 的最小整數(shù):LxJ表示不大于x的最大整數(shù)，它們與含義不同！注一層。似v log2(n) +1提對(duì)的？(A ) 4 ?把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是 (A)唯一的(C)有多種，但根

30、結(jié)點(diǎn)都沒有左孩子5 ?從供選擇的答案中，選出應(yīng)填入下面敘述±內(nèi)。樹是結(jié)點(diǎn)的有限集合，它，根結(jié)點(diǎn)，記為To其余2:選(A)是錯(cuò)誤的。例如當(dāng)n為2的整數(shù)幕時(shí)就會(huì)少 算o(B)有多種(D)有多種，但根結(jié)點(diǎn)都沒有右孩子內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄:吉點(diǎn)分成為 m (mNO)個(gè)B供選擇的答案A :有0個(gè)或1個(gè)B：互不相交C：權(quán) tic 7 a有。個(gè)或多個(gè)允許相交維數(shù)的集合Tl, T2, ?, Tin,每個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為T、的父結(jié)點(diǎn)，1;稱為T的子結(jié)點(diǎn)(10 Wm)個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的C有且只有1個(gè)有1個(gè)或1個(gè)以上允許葉結(jié)點(diǎn)相交允許樹枝結(jié)點(diǎn)相交次數(shù)(或度)序

31、6.從供選擇的答案中，選出應(yīng)填入下面敘述一內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。二叉樹_L。在完全的二叉樹中，若一個(gè)結(jié)點(diǎn)沒有魚，則它必定是葉結(jié)點(diǎn)。每棵樹都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里一個(gè)結(jié)點(diǎn)N的左子女是N在原樹里對(duì)應(yīng)結(jié)點(diǎn)的 C ,而N的右子女是它在原樹里對(duì)應(yīng)結(jié)點(diǎn)的供選擇的答案B：左子結(jié)點(diǎn)A :是特殊的樹不是樹的特殊形式是兩棵樹的總稱有是只有二個(gè)根結(jié)點(diǎn)的樹形結(jié)構(gòu)右子結(jié)點(diǎn)左子結(jié)點(diǎn)或者沒有右子結(jié)點(diǎn)兄弟c? D:最左子結(jié)點(diǎn)最右子結(jié)點(diǎn)最鄰近的右兄弟最左的兄弟最右的兄弟答案：A=B= C= D=答案:ABCDE=2, 1,最鄰近的左兄弟第7章圖1單選題(每題1分，共16分

32、)<C)L在一個(gè)圖中)所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。A. 1/2B ? 1C. 2D.4(B ) 2?在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。A. 1/2B ? 1C. 2D ? 4(B )3 ?有8個(gè)結(jié)點(diǎn)的無向圖最多有條邊。A. 14B?28C. 56D. 112(c ) 4 .有8個(gè)結(jié)點(diǎn)的無向連通圖最少有A 5B?6(C ) 5 ?有8個(gè)結(jié)點(diǎn)的有向完全圖有A. 14B. 28(B ) 6?用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，條邊。C/7條邊。C56通簾是采用(A ) 7 ?用鄰接表表不圖進(jìn)行深度優(yōu)先遍歷時(shí),A?棧B?隊(duì)列通常是采用C?樹D.8D ? 112來實(shí)現(xiàn)算法的。D?圖來實(shí)