數(shù)據(jù)結(jié)構(gòu)各章自測(cè)題與答案

第一章概論

自測(cè)題答案、填空題數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的 操作對(duì)象 以及它們之間的關(guān)系 和運(yùn)算等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是數(shù)據(jù)元素 的有限集合,R是D上的關(guān)系 有限集合。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的一邏輯結(jié)構(gòu)_、數(shù)據(jù)的一存儲(chǔ)結(jié)構(gòu)—和數(shù)據(jù)的—運(yùn)算_這三個(gè)方面的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi)，它們分別是 —線性結(jié)構(gòu)—和—非線性結(jié)構(gòu)_。線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。6.在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)—沒(méi)有一前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)—沒(méi)有_后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有一前驅(qū)—結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有_1_個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有_后續(xù)—結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)_。在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以—任意多個(gè)_。9?數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是一順序、鏈?zhǔn)?、索引和散列。?shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入、刪除、修改、查找、排序。一個(gè)算法的效率可分為一時(shí)間效率和_空間—效率。、單項(xiàng)選擇題非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對(duì)多關(guān)系 B）多對(duì)多關(guān)系 C）多對(duì)一關(guān)系 D）一對(duì)一關(guān)系數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的結(jié)構(gòu)；A）存儲(chǔ)B）物理 C）邏輯 D）物理和存儲(chǔ)算法分析的目的是：A算法分析的目的是：A）找出數(shù)據(jù)結(jié)構(gòu)的合理性C）分析算法的效率以求改進(jìn)算法分析的兩個(gè)主要方面是：A）空間復(fù)雜性和時(shí)間復(fù)雜性C）可讀性和文檔性計(jì)算機(jī)算法指的是：A）計(jì)算方法 B）排序方法計(jì)算機(jī)算法必須具備輸入、輸出和A）可行性、可移植性和可擴(kuò)充性C）確定性、有窮性和穩(wěn)定性三、簡(jiǎn)答題B）研究算法中的輸入和輸出的關(guān)系D）分析算法的易懂性和文檔性B）正確性和簡(jiǎn)明性D）數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C）解決問(wèn)題的有限運(yùn)算序列 等D）調(diào)度方法5個(gè)特性。B）可行性、確定性和有窮性D）易讀性、穩(wěn)定性和安全性2.s=0;2.s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;答：O(n2)【嚴(yán)題集1.2②】數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型兩個(gè)概念之間有區(qū)別嗎?答：簡(jiǎn)單地說(shuō)，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類(lèi)型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。簡(jiǎn)述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對(duì)一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的四、【嚴(yán)題集1.8④】分析下面各程序段的時(shí)間復(fù)雜度1.for（i=0;i<n;i++）for（j=0;j<m;j++）A[i][j]=0；答：0（m*n）x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;

解：因?yàn)閤++共執(zhí)行了n-1+n-2+ +仁n(n-1)/2，所以執(zhí)行時(shí)間為O(n2)五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=(D,R)，試按各小題所給條件畫(huà)出這些邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系 R,哪些結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？【嚴(yán)蔚敏習(xí)題集P71.3②】D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4)}答：di-d2-d3-d4 di一無(wú)直接前驅(qū)，是首結(jié)點(diǎn) d4一無(wú)直接后繼是尾結(jié)點(diǎn)2。 D={d1,d2,…,d9}R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}答：此圖為樹(shù)形結(jié)構(gòu) di一無(wú)直接前驅(qū)，是根結(jié)點(diǎn) d2,d5,d7,d9一無(wú)直接后繼是葉子結(jié)點(diǎn)3.D={d1,d2,…,d9}R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),(d4,d6)}答：此圖為圖形結(jié)構(gòu) d1,d2無(wú)直接前驅(qū)，是開(kāi)始結(jié)點(diǎn) d6,d7 無(wú)直接后繼是終端結(jié)點(diǎn)第2章自測(cè)卷答案、填空【嚴(yán)題集2.2①】在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) —表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與一表長(zhǎng)和該元素在表中的位置—有關(guān)。線性表中結(jié)點(diǎn)的集合是一有限—的，結(jié)點(diǎn)間的關(guān)系是—一對(duì)一—的。3.向一個(gè)長(zhǎng)度為n的向量的第3.向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素(1<i<n+1)之前插入一個(gè)元素時(shí)需向后移動(dòng)n-i+1 元素。向一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素(1<i<n)時(shí)，需向前移動(dòng)_n-i一個(gè)元素。在順序表中訪問(wèn)任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 0(1)_，因此，順序表也稱(chēng)為—隨機(jī)存取—的數(shù)據(jù)結(jié)構(gòu)?！緡?yán)題集2.2①】順序表中邏輯上相鄰的元素的物理位置 —必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定相鄰?！緡?yán)題集2.2①】在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由 —其直接前驅(qū)結(jié)點(diǎn)的鏈域的值—指示。8.在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn) *p，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為0(n)。二、判斷正誤(在正確的說(shuō)法后面打勾，反之打又)(x)1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分另U存放多個(gè)指針。例如，雙向鏈表中的結(jié)點(diǎn)可以含有兩個(gè)指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。i=1;while(i<=n)i=i*3;答：O(Iog3n)

(x)2.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。 錯(cuò)，鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無(wú)序， 而鏈表的示意圖有序。(X)3.鏈表的刪除算法很簡(jiǎn)單，因?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è)簡(jiǎn)單類(lèi)型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類(lèi)型。錯(cuò)，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。(x)5.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。錯(cuò)，正好說(shuō)反了。順序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜”(x)6.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。錯(cuò)，前一半正確，但后一半說(shuō)法錯(cuò)誤，那是鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)。順序存儲(chǔ)方式插入、刪除運(yùn)算效率較低，在表長(zhǎng)為n的順序表中，插入和刪除一個(gè)數(shù)據(jù)元素，平均需移動(dòng)表長(zhǎng)一半個(gè)數(shù)的數(shù)據(jù)元素。(x)7.線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。錯(cuò)，線性表有兩種存儲(chǔ)方式，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。后者不要求連續(xù)存放。(x)8.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。錯(cuò)誤。線性表有兩種存儲(chǔ)方式，在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素在存儲(chǔ)的物理位置次序上也相鄰。(x)9.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。錯(cuò)誤。順序存儲(chǔ)方式不僅能用于存儲(chǔ)線性結(jié)構(gòu)，還可以用來(lái)存放非線性結(jié)構(gòu)，例如完全二叉樹(shù)是屬于非線性結(jié)構(gòu)，但其最佳存儲(chǔ)方式是順序存儲(chǔ)方式。 (后一節(jié)介紹)(x)10.線性表的邏輯順序與存儲(chǔ)順序總是一致的。錯(cuò)，理由同7。鏈?zhǔn)酱鎯?chǔ)就無(wú)需一致。三、單項(xiàng)選擇題(C)(B)(A)1?數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱(chēng)之為：((C)(B)(A)1?數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱(chēng)之為：(A)存儲(chǔ)結(jié)構(gòu) (B)邏輯結(jié)構(gòu) (C)順序存儲(chǔ)結(jié)構(gòu) (D)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是 100，每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的地址是(A)110 (B)108 (C)100 (D)120在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是 0(1)的操作是：訪問(wèn)第i個(gè)結(jié)點(diǎn)(1<i<n)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2<i<n)在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1<i<n)刪除第i個(gè)結(jié)點(diǎn)(1<i<n)將n個(gè)結(jié)點(diǎn)從小到大排序(A)(B)(C)(D)(B)(A)向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)(A)8 (B)63.5 (C)63 (D)7鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間：個(gè)元素(B)6.鏈表是一種采用(A)順序(B)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表;(C)(B)6.鏈表是一種采用(A)順序(B)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表;(C)星式(D)網(wǎng)狀(D)7.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)(A)必須是連續(xù)的(C)一定是不連續(xù)的)8?線性表L在(A)需經(jīng)常修改L中的結(jié)點(diǎn)值(C)L中含有大量的結(jié)點(diǎn))9? 單鏈表的存儲(chǔ)密度要求內(nèi)存中可用存儲(chǔ)單元的地址(B)部分地址必須是連續(xù)的(D)連續(xù)或不連續(xù)都可以情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。(E)需不斷對(duì)L進(jìn)行刪除插入(D)L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜(A)大于1; (E)等于1;)10?設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn)，P0(C)小于1;整數(shù)P0，3(D)不能確定4代表地址，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為3 4Poala2A3(A)分兩部分，一-部分存放結(jié)點(diǎn)值，另部分存放表示結(jié)點(diǎn)間關(guān)系的指針(B)只有一部分，存放結(jié)點(diǎn)值(C)只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針(D)分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)（A）循環(huán)鏈表 （E）單鏈表（C）雙向循環(huán)鏈表 （D）雙向鏈表四、簡(jiǎn)答題【嚴(yán)題集2.3②】試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？答：①順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一） ；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)密度大（=1?），存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。②鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度?。?<1），存儲(chǔ)空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性表的長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表；若線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。2.【嚴(yán)題集2.1①】描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)） 。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素 a1的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱(chēng)為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個(gè)概念對(duì)單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點(diǎn)，是不同的存儲(chǔ)結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問(wèn)題。頭結(jié)點(diǎn)headdatalink頭指針 首元結(jié)點(diǎn)簡(jiǎn)而言之，頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)； 數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息 （內(nèi)放頭指針？那還得另配一個(gè)頭指針?。。。┦自亟Y(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素 a1的結(jié)點(diǎn)。第3章棧和隊(duì)列自測(cè)卷答案一、填空題（每空1分，共15分）【李春葆】向量、棧和隊(duì)列都是一線性一結(jié)構(gòu)，可以在向量的—任何位置插入和刪除元素；對(duì)于棧只能在—棧頂插入和刪除元素；對(duì)于隊(duì)列只能在—隊(duì)尾—插入和—隊(duì)首—?jiǎng)h除元素。棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱(chēng)為 —棧頂。不允許插入和刪除運(yùn)算的一端稱(chēng)為棧底?！?duì)列—是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的 —前一個(gè)位置。在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 n-1個(gè)元素。向棧中壓入元素的操作是先 移動(dòng)棧頂指針，后_存入元素。從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是 先—移動(dòng)隊(duì)首指針 ，后取出元素?！?0年統(tǒng)考題〗帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于 _0。解：head ] |R=head二、判斷正誤（判斷下列概念的正確性，并作出簡(jiǎn)要的說(shuō)明。 ）（每小題1分，共10分）（x）1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類(lèi)型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類(lèi)型。錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類(lèi)型無(wú)關(guān)。（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ù)據(jù)結(jié)構(gòu)。錯(cuò)，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲(chǔ)結(jié)構(gòu)概念，二者不是同類(lèi)項(xiàng)。(X)6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。(V)7.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。(V)8.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。(X)9.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。錯(cuò)，后半句不對(duì)。(X)10.一個(gè)棧的輸入序列是12345,則棧的輸出序列不可能是 12345。錯(cuò)，有可能。三、單項(xiàng)選擇題(每小題1分，共20分)(B)1. 〖00年元月統(tǒng)考題〗棧中元素的進(jìn)出原則是A.先進(jìn)先出 B.后進(jìn)先出C.棧空則進(jìn) D.棧滿則出(C)2.〖李春葆〗若已知一個(gè)棧的入棧序列是1,2,3，…，n，其輸出序列為p1，p2，p3，…，pn，若p仁n則pi為A.i B.n=i C.n-i+1D.不確定解釋?zhuān)寒?dāng)p1=n，即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的(事實(shí)上題目已經(jīng)表明了)，那么輸入順序必定是1，3，…，n，則出棧的序列是 n，…，3，2，1。若不要求順序出棧，則輸出序列不確定)B)3.〖李春葆〗判定一個(gè)棧ST(最多元素為mO)為空的條件是A.ST->topv>0B.ST->top=0 C.ST->top<>m0 D.ST->top=m0(A)4.〖李春葆〗判定一個(gè)隊(duì)列QU(最多元素為 m0)為滿隊(duì)列的條件是A.QU->rear—QU->front==mO B.QU->rear—QU->front—1==m0C.QU->front==QU->rear D.QU->front==QU->rea葉1解：隊(duì)滿條件是元素個(gè)數(shù)為m0。由于約定滿隊(duì)時(shí)隊(duì)首指針與隊(duì)尾指針相差 1,所以不必再減1了，應(yīng)當(dāng)選A。當(dāng)然，更正確的答案應(yīng)該取模，即：QU->front==(QU->rear+1)%m0(D)5?數(shù)組Q[n]用來(lái)表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于n，計(jì)算隊(duì)列中元素的公式為(A)r—f;(B)(n+f—r)%n;(C)n+r—f; (D)(n+r—f)%n【98初程P71】 從供選擇的答案中，選出應(yīng)填入下面敘述?內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。設(shè)有4個(gè)數(shù)據(jù)元素a1、a2、a3和a4，對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按 a1、a2、a3、a4次序每次進(jìn)入一個(gè)元素。假設(shè)?；蜿?duì)的初始狀態(tài)都是空?，F(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是 4，第二次出棧得到的元素是 B是；類(lèi)似地，考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是 C ，第二次出隊(duì)得到的元素是 D 。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有E個(gè)。供選擇的答案：AD:?a1②a2③a3④a4E:①1 ②2 ③3 ④0答：ABCDE=2, 4, 1,2, 2【94初程P75】從供選擇的答案中，選出應(yīng)填入下面敘述? 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。棧是一種線性表，它的特點(diǎn)是 4。設(shè)用一維數(shù)組A[1,…,n]來(lái)表示一個(gè)棧，A[n]為棧底，用整型變量T指示當(dāng)前棧頂位置，A[T]為棧頂元素。往棧中推入(PUSH)一個(gè)新元素時(shí)，變量T的值B;從棧中彈出(POP)一個(gè)元素時(shí)，變量T的值C。設(shè)?？諘r(shí)，有輸入序列a，b，c,經(jīng)過(guò)PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的

元素的序列是 D，變量T的值是E。供選擇的答案：A:①先進(jìn)先出②后進(jìn)先出③進(jìn)優(yōu)于出④出優(yōu)于進(jìn)⑤隨機(jī)進(jìn)出B，C:? 加1②減1③不變④清0⑤加2⑥減2D:①a,b ②b,c③c,a④b,a ⑤c,b⑥a,cE：①n+1 ②n+2 ③n④n-1⑤n-2答案：ABCDE=2,2,1,6, 4注意，向地址的高端生長(zhǎng)，稱(chēng)為向上生成堆棧；向地址低端生長(zhǎng)叫向下生成堆棧，本題中底部為n,向地址的低端遞減生成，稱(chēng)為向下生成堆棧?！?1初程P77】從供選擇的答案中，選出應(yīng)填入下面敘述 ? 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否 A_;在做退棧運(yùn)算時(shí)，應(yīng)先判別棧是否 B。當(dāng)棧中元素為n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為 C。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的 D分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng)E時(shí)，才產(chǎn)生上溢。供選擇的答案：A，B:①空②滿③上溢④下溢C: ①n-1②n③n+1④n/2D: ①長(zhǎng)度②深度③棧頂④棧底E:①兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn) ②其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)③兩個(gè)棧的棧頂在達(dá)棧空間的某一位置相遇 ④兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答案：ABCDE=2, 1,2,4,3四、簡(jiǎn)答題（每小題4分，共20分）【嚴(yán)題集3.2①和3.11①】說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。劉答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：①運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表是只允許在4IFO;隊(duì)列端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表 FIFO。②用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于 多道作業(yè)處理、指令寄存及其他運(yùn)算等等。2.【統(tǒng)考書(shū)2.【統(tǒng)考書(shū)P604-11，難于嚴(yán)題集3.1①】設(shè)有編號(hào)為1,2,3,4的四輛列車(chē)，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車(chē)站，具體寫(xiě)劉答：至少有14種。①全進(jìn)之后再出情況，只有劉答：至少有14種。①全進(jìn)之后再出情況，只有1種：4,3,2,②進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,1③進(jìn)2個(gè)之后再出的情況，有5種，2,4,3」④進(jìn)1個(gè)之后再出的情況，有5種，1,4,3,2出這四輛列車(chē)開(kāi)出車(chē)站的所有可能的順序。3.【劉自編】假設(shè)正讀和反讀都相同的字符序列為“回3,2,4,13,2,1,42,3,4,12,1,3,42,1,4,32,3,1,41,3,2,41,3,4,21,2,3,41,2,4,3，例如，’abba'和’abcba'是回文，’abcde'和’ababab則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用文”生表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量（ j--）從表尾開(kāi)始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機(jī)內(nèi)已是順序存儲(chǔ)，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_(kāi)到數(shù)組末尾，然后直接用POP動(dòng)作實(shí)現(xiàn)。（但堆棧是先減后壓還是……）若正文是單鏈表形式存儲(chǔ)，則等同于隊(duì)列，需開(kāi)輔助空間，可以從鏈?zhǔn)组_(kāi)始入棧，全部壓入后再依次輸出。4.【統(tǒng)考書(shū)P604-13】順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿?答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決隊(duì)滿隊(duì)空的辦法有三：①設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空;②浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空

③使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）。我們常采用法②，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲?，而另一個(gè)指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是：f=rear隊(duì)滿標(biāo)志是：f=（r+1）%N5.【統(tǒng)考書(shū)P604-14】設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)從0到39），現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后，有①front=11，rear=19;②front=19，rear=11；問(wèn)在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？答：用隊(duì)列長(zhǎng)度計(jì)算公式：（N+r-f）%N①L=（40+19-11）%40=8 ②L=（40+11-19）%40=32寫(xiě)出下列程序段的輸出結(jié)果（棧的元素類(lèi)型 SElemType為char）a'P);ush(S,y);t');Push(S,x);s');1.嚴(yán)題集寫(xiě)出下列程序段的輸出結(jié)果（棧的元素類(lèi)型 SElemType為char）a'P);ush(S,y);t');Push(S,x);s');}答：輸出為“stack”。2. 【嚴(yán)題集3.12②】寫(xiě)出下列程序段的輸出結(jié)果(隊(duì)列中的元素類(lèi)型QEIemType為char)voidmain(){QueueQ;InitQueue(Q);Charx='e';y='c'；EnQueue(Q, 'h');EnQueue(Q, 'r');EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q, 'a');whiIe(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);}答：輸出為“char”?！緡?yán)題集3.13②】簡(jiǎn)述以下算法的功能(棧和隊(duì)列的元素類(lèi)型均為int)。voidaIgo3(Queue&Q){StackS;intd;InitStack(S);whiIe(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);};whiIe(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}答：該算法的功能是：利用堆棧做輔助，將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置。第45章串和數(shù)組一、填空題（每空1分，共20分）—不包含任何字符（長(zhǎng)度為0）的串—稱(chēng)為空串；—由一個(gè)或多個(gè)空格（僅由空格符）組成的串稱(chēng)為空白串。（對(duì)應(yīng)嚴(yán)題集4.1①，簡(jiǎn)答題：簡(jiǎn)述空串和空格串的區(qū)別）一 一設(shè)S="A;/document/Mary.doc ”，貝Ustrlen（s）=20 , “/”的字符定位的位置為3 。子串的定位運(yùn)算稱(chēng)為串的模式匹配； —被匹配的主串稱(chēng)為目標(biāo)串，—子串稱(chēng)為模式。設(shè)目標(biāo)T=”abccdcdccbaa”，模式P=“cdcc”，則第6次匹配成功。若n為主串長(zhǎng)，m為子串長(zhǎng)，則串的古典(樸素)匹配算法最壞的情況下需要比較字符的總次數(shù)為 _(n-m+1)*m_。假設(shè)有二維數(shù)組A6X8,每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置(基地址)為1000，則數(shù)組A的體積(存儲(chǔ)量)為288B;末尾元素A57的第一個(gè)字節(jié)地址為 1282 ;若按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為(8+4)X6+1000=1072 ;若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為(6X7+4)X6+1000)=1276 。(注：數(shù)組是從。行0列還是從1行1列計(jì)算起呢？由末單元為 A57可知，是從0行0列開(kāi)始！)〖00年計(jì)算機(jī)系考研題〗 設(shè)數(shù)組a[1???60,1-70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為_(kāi)8950。答：不考慮0行0列，利用列優(yōu)先公式： LOC(aj)=LOC(a，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2 =8950三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的行下標(biāo)、列下標(biāo)和元素值。求下列廣義表操作的結(jié)果：GetHead【((a,b),(c,d)) 頭元素不必加括號(hào)GetHead【GetTail【((a,b),(c,d))】】===(c,d) ;GetHead[GetTail【GetHea 【((a,b),(c, GetTail[GetHeadd[GetTail【((a，b),(c,d)】]]=== (d) ；二、單選題(每小題1分， 共15分))(B)1.〖李〗串是一種特殊的線性表，其特殊性體現(xiàn)在：A.可以順序存儲(chǔ) E.數(shù)據(jù)元素是一個(gè)字符C.可以鏈?zhǔn)酱鎯?chǔ) D.數(shù)據(jù)元素可以是多個(gè)字符(B)2.〖李〗設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)作：A.連接 E.模式匹配C.求子串 D.求串長(zhǎng)(D)3.〖李〗設(shè)串s1='ABCDEFG， s2='PQRST，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i開(kāi)始的[個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，貝Ucon(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是：A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF解：con(x,y)返回x和y串的連接串，即con(x,y)=’ABCDEFGPQRSTsubs(s,i,j)返回串s的從序號(hào)i開(kāi)始的j個(gè)字符組成的子串，則subs(s1,2,len(s2))=subs(s1,2,5)= 'BCDEF;subs(s1,len(s2),2)=subs(s1,5,2)= 'EF'；所以con(subs(s1,2,len(s2)),subs(s1,len(s2),2)) =con('BCDEF', 'EF')之連接，即CDEFEF(A)4.〖01年計(jì)算機(jī)系考研題〗假設(shè)有60行70列的二維數(shù)組a[1?60,1-70]以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a[32,58]的存儲(chǔ)地址為。(無(wú)第。行第0列元素)A.16902B.16904 C.14454 D.答案A,B,C均不對(duì)答：此題與填空題第8小題相似。(57列X60行+31行)X2字節(jié)+10000=16902(B)5.設(shè)矩陣A是一個(gè)對(duì)稱(chēng)矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分(如下圖所示)按行序存放在一維數(shù)組B[1,n(n-1)/2]中，對(duì)下三角部分中任一元素 ai；j(i<j),在一維數(shù)組B中下標(biāo)k的值是：A.i(i-1)/2+j-1 B.i(i-1)/2+j C.i(i+1)/2+j-1 D.i(i+1)/2+ja1,1a2,1a2,2an,nan,1aan,n和C。若按列存儲(chǔ)，則 A[7,1]和A[2,4]的第一個(gè)字節(jié)的地址分別是供選擇的答案:TOC\o"1-5"\h\zA?E:①28 ②44 ③76 ④92 ⑤108⑥116⑦ 132 ⑧176 ⑨184 ⑩188答案：ABCDE=8,3,5, 1,6解91注意P78的下標(biāo)供選擇的答案開(kāi)始選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。先用第一個(gè)元素去套用，可能有B和C;存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是再用第二個(gè)元素去套用r下標(biāo)的范圍是B=2而8C咧(標(biāo)的范圍1到5,每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器是按字節(jié)以選。假設(shè)存儲(chǔ)數(shù)組元素A[0,1]的第一個(gè)字節(jié)的地址是存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是A。若按行彳 儲(chǔ)，貝UA[3,5]和A[5,3]的第一個(gè)字節(jié)的地址分別是7.【94程P12】7.【94程P12】有一個(gè)二維數(shù)組A,行下標(biāo)的范圍是1到6字節(jié)編址。那么，這個(gè)數(shù)組的體積是則存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是按列存儲(chǔ)，則A[5,7]的第一個(gè)字節(jié)的地址是D。供選擇的答案A?D:①12 ②66⑦156 ⑧234答案：ABCD=12,10,列下標(biāo)的范圍是0到7,每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按A個(gè)字節(jié)。假設(shè)存儲(chǔ)數(shù)組元素A[1,0]的第一個(gè)字節(jié)的地址是0，B。若按行存儲(chǔ)，則A[2,4]的第一個(gè)字節(jié)的地址是 C。若③72⑨3,④96 ⑤114276 ⑩2829⑥12011)283(12)288三、 簡(jiǎn)答題(每小題5分，共15分)【其他教材】已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個(gè)元素占 K個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址為L(zhǎng)oc(a11)，請(qǐng)寫(xiě)出求Loc(aij)的計(jì)算公式。如果采用列優(yōu)先順序存放呢？解：公式教材已給出，此處雖是方陣，但行列公式仍不相同；按行存儲(chǔ)的元素地址公式是： Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K按列存儲(chǔ)的元素地址公式是： Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K【全國(guó)專(zhuān)升本資格考試】遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間，對(duì)嗎？為什么？答：不一定。時(shí)間復(fù)雜度與樣本個(gè)數(shù) n有關(guān)，是指最深層的執(zhí)行語(yǔ)句耗費(fèi)時(shí)間，而遞歸算法與非遞歸算法在最深層的語(yǔ)句執(zhí)行上是沒(méi)有區(qū)別的，循環(huán)的次數(shù)也沒(méi)有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來(lái)顯示循環(huán)次數(shù)而已。四、 計(jì)算題(每題5分，共20分)1, 設(shè)s='IAMASTUDENT',t='GOOD,q='WORKER,求Replace(s,'STUDENT',q)和Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))。解：①Replace(s,'STUDENT',q)='IAMAWORKER'②因?yàn)镾ubString(s,6,2)='ASubString(s,7,8)='STUDENT'Concat(t,SubString(s,7,8))='GOODSTUDENT'所以Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))) ='AGOODSTUDENT'第六章樹(shù)和二叉樹(shù)第6第6章面是有關(guān)二叉樹(shù)的敘述，請(qǐng)判斷正誤(每小題1分，共10分)(V)(V)1,若二叉樹(shù)用二叉鏈表作存貯結(jié)構(gòu)，則在x)2.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于V)3.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)是有序的。n個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈表中只有 n—1個(gè)非空指針域1o(x)4.二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩棵非空子樹(shù)或有兩棵空子樹(shù)。（X）5.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(shù)（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹(shù)（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。 （應(yīng)當(dāng)是二叉排序樹(shù)的特點(diǎn)）（X）6.二叉樹(shù)中所有結(jié)點(diǎn)個(gè)數(shù)是 2k-i-1,其中k是樹(shù)的深度。（應(yīng)2i-1）x）7.二叉樹(shù)中所有結(jié)點(diǎn)，如果不存在非空左子樹(shù)，則不存在非空右子樹(shù)。x）8.對(duì)于一棵非空二叉樹(shù)，它的根結(jié)點(diǎn)作為第一層，則它的第 i層上最多能有2i—1個(gè)結(jié)點(diǎn)。（應(yīng)2i-i）V）9.用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（正確。用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)共有2n個(gè)鏈域。由于二叉樹(shù)中，除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有n-1個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針，還有 n+1個(gè)空指針。）即有后繼鏈接的指針僅 n-1個(gè)。（V）10.〖01年計(jì)算機(jī)系研題〗具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)。最快方法：用葉子數(shù)=[n/2]=6,再求n2=n0-仁5二、填空（每空1分，共15分）1.由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有 _5_種形態(tài)。2.【計(jì)算機(jī)研2000】一棵深度為6的滿二叉樹(shù)有_n1+n2=0+n2=no-1=31_個(gè)分支結(jié)點(diǎn)和_26-1=32—個(gè)葉子。注：滿二叉樹(shù)沒(méi)有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。 〃 一一3.一棵具有257個(gè)結(jié)點(diǎn)的完全二又樹(shù)，它的深度為 _9。（注：用 log2（n）+1=8.xx+1=9【全國(guó)專(zhuān)升本統(tǒng)考題】設(shè)一棵完全二又樹(shù)有700個(gè)結(jié)點(diǎn)，則共有一350_個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)=[n/2]=350設(shè)一棵完全二又樹(shù)具有1000個(gè)結(jié)點(diǎn)，則此完全二又樹(shù)有_500_個(gè)葉子結(jié)點(diǎn)，有_499_個(gè)度為2的結(jié)點(diǎn)，有—1_個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有_0個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。答：最快方法：用葉子數(shù)=[n/2]=500，n2=n0-1=499。另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左子樹(shù)。完全二又樹(shù)的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹(shù)數(shù)二 0.【嚴(yán)題集6.7③】一棵含有n個(gè)結(jié)點(diǎn)的k又樹(shù)，可能達(dá)到的最大深度為 n，最小深度為2。答：當(dāng)k=1（單又樹(shù)）時(shí)應(yīng)該最深，深度二n（層）；當(dāng)k=n-1（n-1又樹(shù)）時(shí)應(yīng)該最淺，深度二2（層），但不包括n=0或1時(shí)的特例情況。教材答案是“完全 k又樹(shù)”，未定量。）【96程試題1】二又樹(shù)的基本組成部分是：根（N）、左子樹(shù)（L）和右子樹(shù)（R）。因而二又樹(shù)的遍歷次序有六種。最常用的是三種：前序法（即按NLR次序），后序法（即按LRN 次序）和中序法（也稱(chēng)對(duì)稱(chēng)序法，即按 LNR次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二又樹(shù)的前序序列是 BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是FEGHDCB。解：法1:先由已知條件畫(huà)圖，再后序遍歷得到結(jié)果；法2:不畫(huà)圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定root，由中序先確定左子樹(shù)。例如，前序遍歷 BEFCGDH中，根結(jié)點(diǎn)在最前面，是B;則后序遍歷中B一定在最后面。法3:遞歸計(jì)算。如B在前序序列中第一，中序中在中間（可知左右子樹(shù)上有哪些元素），則在后序中必為最后。如法對(duì)B的左右子樹(shù)同樣處理，則問(wèn)題得解?！救珖?guó)專(zhuān)升本統(tǒng)考題】 中序遍歷的遞歸算法平均空間復(fù)雜度為 —O（n）_。答：即遞歸最大嵌套層數(shù)，即棧的占用單元數(shù)。精確值應(yīng)為樹(shù)的深度 k+1，包括葉子的空域也遞歸了一次。9.【計(jì)算機(jī)研2001】用5個(gè)權(quán)值｛3,2,4,5,1｝構(gòu)造的哈夫曼（Huffman）樹(shù)的帶權(quán)路徑長(zhǎng)度是 33解：先構(gòu)造哈夫曼樹(shù)，得到各葉子的路徑長(zhǎng)度之后便可求出 WPL=（4+5+3）x2+（1+2）x3=33）5）（9）- "（6） （注：兩個(gè)合并值先后不同會(huì)導(dǎo)致編碼不同，即哈夫曼編碼不唯一）4 5 3 （3）-- （注：合并值應(yīng)排在葉子值之后）（注：原題為選擇題：A.32 B.33 C.34 D.15）三、單項(xiàng)選擇題(每小題1分，共11分)(C)1.不含任何結(jié)點(diǎn)的空樹(shù)。(A)是一棵樹(shù)； (E)是一棵二叉樹(shù)；(C)是一棵樹(shù)也是一棵二叉樹(shù)； (D)既不是樹(shù)也不是二叉樹(shù)答：以前的標(biāo)答是B，因?yàn)槟菚r(shí)樹(shù)的定義是n>1(C)2?二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，所以。(A)它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ) ； (E)它不能用鏈?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.〖01年計(jì)算機(jī)研題〗 具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為。(A) log2(n) (B)log2(n) (C) log2(n)+1 (D)log2(n)+1注1:x表示不小于x的最小整數(shù)； x表示不大于x的最大整數(shù)，它們與□含義不同！注2:選(A)是錯(cuò)誤的。例如當(dāng)n為2的整數(shù)冪時(shí)就會(huì)少算一層。 似乎log2(n)+1是對(duì)的？(A)4.把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是。(A)唯一的 (B)有多種(C)有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子 (D)有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子【94程P11】從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。樹(shù)是結(jié)點(diǎn)的有限集合，它A—根結(jié)點(diǎn)，記為T(mén)。其余的結(jié)點(diǎn)分成為m(m>0)個(gè)旦的集合T1,T2，…，Tm，每個(gè)集合乂都是樹(shù)，此時(shí)結(jié)點(diǎn) T稱(chēng)為［的父結(jié)點(diǎn)，T.稱(chēng)為T(mén)的子結(jié)點(diǎn)(1<i<m)一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的 C。供選擇的答案②有0個(gè)或多個(gè)③有且只有1個(gè)④有1個(gè)或1個(gè)以上A:①有0個(gè)或1個(gè)B:①互不相交②允許相交③允許葉結(jié)點(diǎn)相交④允許樹(shù)枝結(jié)點(diǎn)相交C:①權(quán)②維數(shù)③次數(shù)(或度)④序答:ABC=1，1:,3變： 【95程P13】從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。二叉樹(shù)_A_。在完全的二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有 B ，則它必定是葉結(jié)點(diǎn)。每棵樹(shù)都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù)。由樹(shù)轉(zhuǎn)換成的二叉樹(shù)里，一個(gè)結(jié)點(diǎn)N的左子女是N在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的 C，而N的右子女是它在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的D。供選擇的答案A:①是特殊的樹(shù) ②不是樹(shù)的特殊形式 ③是兩棵樹(shù)的總稱(chēng) ④有是只有二個(gè)根結(jié)點(diǎn)的樹(shù)形結(jié)構(gòu)B:①左子結(jié)點(diǎn) ②右子結(jié)點(diǎn)③左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn) ④兄弟CD:①最左子結(jié)點(diǎn)②最右子結(jié)點(diǎn)③最鄰近的右兄弟④最鄰近的左兄弟⑤最左的兄弟⑥最右的兄弟答案：A= B=C=D=答案：ABCDE=2，1，1，3四、簡(jiǎn)答題(每小題4分，共20分)1.【嚴(yán)題集6.2①】一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別？答：度為2的樹(shù)從形式上看與二叉樹(shù)很相似，但它的子樹(shù)是無(wú)序的，而二叉樹(shù)是有序的。即，在一般樹(shù)中若某結(jié)點(diǎn)只有一個(gè)孩子，就無(wú)需區(qū)分其左右次序，而在二叉樹(shù)中 即使是一個(gè)孩子也有左右之分。第7章圖-、單選題(每題1分，共16分) 前兩大題全部來(lái)自于全國(guó)自考參考書(shū)！(C)1.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍。A. 1/2 B.1 C.2 D.4(B)2.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍A. 1/2 B.1 C.2 D.4(B)3.有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有條邊。A.14 B.28 C.56 D.112(C)4?有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有條邊。TOC\o"1-5"\h\zA.5 B.6 C.7 D.8(C)5?有8個(gè)結(jié)點(diǎn)的有向完全圖有條邊。A.14 B.28 C.56 D.112(B)6.用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用 來(lái)實(shí)現(xiàn)算法A.棧 B.隊(duì)列 C.樹(shù) 的。(A)7.用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用 來(lái)實(shí)現(xiàn)算法的A.棧 B.隊(duì)列 C.樹(shù) D.圖1.2.3.4.5.6.、填空題(每空1分，共20分)圖有—鄰接矩陣_、—鄰接表—等存儲(chǔ)結(jié)構(gòu)，遍歷圖有—深度優(yōu)先遍歷有向圖 廣度優(yōu)先遍歷—等方法。G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)如果n個(gè)頂點(diǎn)的的—出度_。圖是一個(gè)環(huán)，則它有n棵生成樹(shù)。1.2.3.4.5.6.、填空題(每空1分，共20分)圖有—鄰接矩陣_、—鄰接表—等存儲(chǔ)結(jié)構(gòu)，遍歷圖有—深度優(yōu)先遍歷有向圖 廣度優(yōu)先遍歷—等方