數(shù)據(jù)結(jié)構(gòu)c語言版測(cè)試題答案

第一章概論 自測(cè)題答案 姓名班級(jí)題號(hào)一二三四五六總分題分3315982015100得分一、填空題（每空1分，共33分）.一個(gè)計(jì)算機(jī)系統(tǒng)包括硬件系統(tǒng) 和 軟件系統(tǒng) 兩大部分。.一臺(tái)計(jì)算機(jī)中全部程序的集合，稱為這臺(tái)計(jì)算機(jī)的軟件資源/（系統(tǒng)） 。.計(jì)算機(jī)軟件可以分為一系統(tǒng)—軟件和應(yīng)用—軟件兩大類?？茖W(xué)計(jì)算程序包屬于應(yīng)用軟件，診斷程序?qū)儆赺系統(tǒng)軟件（工具）一。.一種用助憶符號(hào)來表示機(jī)器指令的操作符和操作數(shù)的語言是―匯編語言 。.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象 以及它們之間的關(guān)系 和運(yùn)算等的學(xué)科。.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中口是數(shù)據(jù)元素 的有限集合，區(qū)是口上的3系有限集合。.數(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)可分為兩大類，它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu).線性結(jié)構(gòu)中元素之間存在二對(duì)二關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。.在線性結(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)。.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(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ù)可以逐意多2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序一.鏈?zhǔn)?索引和散列。.數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入,刪除、修改、查找、排序。.一個(gè)算法的效率可分為時(shí)間—效率和_空間 效率。.〖00年省統(tǒng)考〗任何一個(gè)C程序都由一二個(gè)主函數(shù)—和若干個(gè)被調(diào)用的其它函數(shù)組成。.【00年省統(tǒng)考題】變量一經(jīng)說明，就確定該變量的取值范圍（即存儲(chǔ)單元）及—確定變量所允許的運(yùn)算 。二、單項(xiàng)選擇題（每小題1分，共15分）（B）1.通常所說的主機(jī)是指：A）CPUB）CPU和內(nèi)存C）CPU、內(nèi)存與外存D）CPU、內(nèi)存與硬盤（C）2.在計(jì)算機(jī)內(nèi)部，一切信息的存取、處理和傳送的形式是：A）ACSII碼B）BCD碼C）二進(jìn)制D）十六進(jìn)制（D）3.軟件與程序的區(qū)別是：程序價(jià)格便宜、軟件價(jià)格昂貴；程序是用戶自己編寫的，而軟件是由廠家提供的；C）程序是用高級(jí)語言編寫的，而軟件是由機(jī)器語言編寫的；D）軟件是程序以及開發(fā)、使用和維護(hù)所需要的所有文檔的總稱，而程序只是軟件的一部分。（C）4.所謂“裸機(jī)”是指：A）單片機(jī)B）單板機(jī)C）不裝備任何軟件的計(jì)算機(jī) D）只裝備操作系統(tǒng)的計(jì)算機(jī)（D）5.應(yīng)用軟件是指：A）所有能夠使用的軟件 B）能被各應(yīng)用單位共同使用的某種軟件C）所有微機(jī)上都應(yīng)使用的基本軟件 D）專門為某一應(yīng)用目的而編制的軟件（*A）6.〖00年省統(tǒng)考〗C語言中的常量可分為整型常量、實(shí)型常量、字符型常量及」枚舉）—四種。（A）符號(hào)常量（B）長整型常量（C）邏輯常量（D）二進(jìn)制整數(shù)（*（*C）7.編譯程序的功能是：A）發(fā)現(xiàn)源程序中的語法錯(cuò)誤C）將源程序編譯成目標(biāo)程序（A）8.系統(tǒng)軟件中最重要的是：A）操作系統(tǒng)B）語言處理系統(tǒng)（C）9.可移植性最好的計(jì)算機(jī)語言是：A）機(jī)器語言 B）匯編語言B）改正源程序中的語法錯(cuò)誤力將某一高級(jí)語言程序翻譯成另一種高級(jí)語言程序C）工具軟件 D）數(shù)據(jù)庫管理系統(tǒng)C）高級(jí)語言 D）自然語言（B）10.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種:A）一對(duì)多關(guān)系B）多對(duì)多關(guān)系C）（B）10.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種:A）一對(duì)多關(guān)系B）多對(duì)多關(guān)系C）多對(duì)一關(guān)系 D）一對(duì)一關(guān)系（C）11.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的A）存儲(chǔ)B）物理 C）邏輯 結(jié)構(gòu)；D）物理和存儲(chǔ)（C）12.算法分析的目的是：A）找出數(shù)據(jù)結(jié)構(gòu)的合理性C）分析算法的效率以求改進(jìn)（A）13.算法分析的兩個(gè)主要方面是：A）空間復(fù)雜性和時(shí)間復(fù)雜性B）研究算法中的輸入和輸出的關(guān)系D）分析算法的易懂性和文檔性B）正確性和簡明性C）可讀性和文檔性D）數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（CC）可讀性和文檔性D）數(shù)據(jù)復(fù)雜性和程序復(fù)雜性A）計(jì)算方法 B）排序方法C）解決問題的有限運(yùn)算序列 D）調(diào)度方法（B）15.計(jì)算機(jī)算法必須具備輸入、輸出和等5個(gè)特性。A）可行性、可移植性和可擴(kuò)充性 B）可行性、確定性和有窮性C）確定性、有窮性和穩(wěn)定性 D）易讀性、穩(wěn)定性和安全性三、簡答題（每小題3分，共9分）.我們知道計(jì)算機(jī)只能執(zhí)行機(jī)器指令，為什么它能運(yùn)行用匯編語言和高級(jí)語言編寫的程序?答：靠匯編程序?qū)R編語言或高級(jí)語言翻譯轉(zhuǎn)換為目標(biāo)程序（即機(jī)器語言）。.【嚴(yán)題集1.2②】數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？答：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。.簡述線性結(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ì)多的。四〖00年統(tǒng)考題〗閱讀下列C程序段，寫出相應(yīng)的執(zhí)行結(jié)果（每小題4分，共8分）1.printf(“Inputx”)；scanf(“%d”,&x)；if(x<=30)if(x>20)y=x；elseif(x>10)y=2*x;if(x>0&&x<30)printf("x=%d,y=%d”，x,y)；elseprintf("輸入數(shù)據(jù)錯(cuò)！”)；試寫出當(dāng)*分別為18,8時(shí)的執(zhí)行結(jié)果。答：運(yùn)行結(jié)果為：x=18,y=36x=8,丫=運(yùn)行前的值， 且從x=30開始為數(shù)據(jù)錯(cuò)2.longintfact(n)intn;{longf;if(n>1)f=n*fact(n-1);elsef=1;return(f);2.longintfact(n)intn;{longf;if(n>1)f=n*fact(n-1);elsef=1;return(f);}main(){intn;longy;n=5;y=fact(n);printf(“％d,%ld\n”,n,y)}五【嚴(yán)題集1.8④】分析下面各程序段的時(shí)間復(fù)雜度(每小題5分，共20分)for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;答：O(m*n)s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;答：O(n2)x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++; 4.i=1;解：因?yàn)閤++共執(zhí)行了n-1+n-2+……+1= while(i<=n)n(n-1)/2,所以執(zhí)行時(shí)間為O(n2) 仁】*3；答：O(log3n)“IM"I理5—1)貨17=3+1 7六、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S二(D,R)，試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系R，哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？(每小題5分，共15分)【嚴(yán)蔚敏習(xí)題集P71.3②】D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4)}答：d1-d2fd3fd4 d1一無直接前驅(qū)，是首結(jié)點(diǎn) d4一無直接后繼是尾結(jié)點(diǎn)D={d1,d2,…,d9}R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}答：此圖為樹形結(jié)構(gòu) d1一無直接前驅(qū)，是根結(jié)點(diǎn) d2,d5,d7,d9一無直接后繼是葉子結(jié)點(diǎn)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一無直接前驅(qū)，是開始結(jié)點(diǎn) d6,d7一無直接后繼是終端結(jié)點(diǎn)圓MM程用R⑵第2章自測(cè)卷答案 姓名班級(jí)題號(hào)一二三四五六七總分題分1310101071040100得分一、填空(每空1分，共13分).【嚴(yán)題集2.2①】在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與表長和該元素在表中的位置有關(guān)。.線性表中結(jié)點(diǎn)的集合是有限—的,結(jié)點(diǎn)間的關(guān)系是一對(duì)—一的。.向一個(gè)長度為9的向量的第1個(gè)元素(1Wi〈n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)叱1±1一個(gè)元素。.向一個(gè)長度為9的向量中刪除第1個(gè)元素(1<i〈n)時(shí)，需向前移動(dòng)n-i一個(gè)元素。.在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為0(1).因此,順序表也稱為隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。.【嚴(yán)題集2.2①】順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置且二定相鄰。7.1嚴(yán)題集2.2①】在單鏈表中,除了首元結(jié)點(diǎn)外.任一結(jié)點(diǎn)的存儲(chǔ)位置由其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指示。8.在9個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p,需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為0(n)二、判斷正誤(在正確的說法后面打勾，反之打叉)(每小題1分，共10分)(x)1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分別存放多個(gè)指針。例如，雙向鏈表中的結(jié)點(diǎn)可以含有兩個(gè)指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。(X)2.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。錯(cuò)，鏈表的存儲(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ù)雜類型。錯(cuò)，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(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ǔ)的物理位置次序上相鄰。錯(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é)介紹)

(義)10.線性表的邏輯順序與存儲(chǔ)順序總是一致的。錯(cuò)，理由同7。鏈?zhǔn)酱鎯?chǔ)就無需一致。三、單項(xiàng)選擇題(每小題1分，共10分)C)1.數(shù)據(jù)在計(jì)算機(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)2.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長度為2,則第5個(gè)元素的地址是 (A)110 (B)108 (C)100 (D)120A)3.在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是：訪問第i個(gè)結(jié)點(diǎn)(1WiWn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2WiWn)在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1WiWn)刪除第i個(gè)結(jié)點(diǎn)(1WiWn)將n個(gè)結(jié)點(diǎn)從小到大排序B)4.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)一個(gè)元素(A)8 (B)63.5 (C)63 (D)7(A)5.鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間：分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針只有一部分，存放結(jié)點(diǎn)值(C)只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針(D)分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)B)6.鏈表是一種采用存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表；(A)順序(B)鏈?zhǔn)?(C)星式(D)網(wǎng)狀D)7.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址:(A)必須是連續(xù)的 (B)部分地址必須是連續(xù)的一定是不連續(xù)的 (D)連續(xù)或不連續(xù)都可以B)8.線性表L在情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。(A)需經(jīng)常修改L中的結(jié)點(diǎn)值 (B)需不斷對(duì)1進(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è)(B)10.設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn)，整數(shù)P0,3,4代表地址，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為a13a2a13a24A30(A)循環(huán)鏈表(A)循環(huán)鏈表(B)單鏈表 (。)雙向循環(huán)鏈表(口)雙向鏈表四、簡答題(每小題5分，共10分).【嚴(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ǔ)密度?。ǎ?）,存儲(chǔ)空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。.【嚴(yán)題集2.1①】描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：―是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素2的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(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)的問題。datalinkhead頭結(jié)點(diǎn)head頭指針 首元結(jié)點(diǎ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)志和表長等信息（內(nèi)放頭指針？那還得另配一個(gè)頭指針?。。。┦自亟Y(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素%的結(jié)點(diǎn)。五【軟考題】線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式。現(xiàn)有一個(gè)具有五個(gè)元素的線性表1={23,17,47,05,31},若它以鏈接方式存儲(chǔ)在下列100?119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占2個(gè)字節(jié)）和指針（占2個(gè)字節(jié)）組成，如下所示：05U17X23V31Y47Z100 120其中指針X,Y,Z的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？（10分）答：X=116Y=0Z=100― 首址二答8 末址二112六、閱讀分析題(10分)【嚴(yán)題集2.10②】指出以下算法中的錯(cuò)誤和低效(即費(fèi)時(shí))之處，并將它改寫為一個(gè)既正確又高效的算法。StatusDeleteK(SqList&a,inti,intk){〃本過程從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素if(i<1IIk<0IIi+k>a.length)returnINFEASIBLE; 〃參數(shù)不合法else{for(count=1;count<k;count++){〃刪除一個(gè)元素for(j=a.length;j>=i+1;j--)a.elem[j-1]=a.elem[j];a.length--;)returnOK;}//DeleteK注：上題涉及的類型定義如下:#defineLISTINITSIZE100#defineLISTINCREMENT10typedefstruct{ElemTypeIntInt*elem; 〃存儲(chǔ)空間基址length; 〃當(dāng)前長度listsize; 〃當(dāng)前分配的存儲(chǔ)容量}SqList;答：錯(cuò)誤有兩處：①參數(shù)不合法的判別條件不完整。例如表長為10，若從第一位置(i=1)刪除10個(gè)元素(k=10)，要求合理但會(huì)被判為非法。合法的入口參數(shù)條件為(0<iWa.length)-(0WkWa.length-i)應(yīng)將if(i<1||k<0||i+k>a.length)returnINFEASIBLE改為：if(!((0<iWa.length)-(oWkWa.length-i)))returnINFEASIBLE第二個(gè)FOR語句中，元素前移的次序錯(cuò)誤。應(yīng)將for(j=a.length；j>=i+1；j--)a.elem[j-1]=a.elem[j]；七、編程題(每題10分，共40分)1.七、編程題(每題10分，共40分)1.【徐士良題集，2002年1月省統(tǒng)考題】寫出在順線性表逆轉(zhuǎn)的算法，要求使用最少的附加空間。解：輸入：長度為n的線性表數(shù)組A(1：n)輸出：逆轉(zhuǎn)后的長度為n的線性表數(shù)組A(1：n)。序存儲(chǔ)結(jié)構(gòu)下將invsl(n,a)intn;ETa[];{intk;ETt;for(k=1;k<=n/2;k++){t=a[k-1];a[k-1]=a[n-k];a[n-k]=t;}return;}

C語言描述如下(其中ET為數(shù)據(jù)元素的類型)：2.【嚴(yán)題集2.6②】已知1是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，請(qǐng)寫出在P結(jié)點(diǎn)后插入5結(jié)點(diǎn)的核心語句序列。答：此題答案不唯一，但若從已給定序列中挑選，則限制頗多。Q=P;已知P結(jié)點(diǎn)，則不必“順藤摸瓜”，直接鏈接即可。已知P結(jié)點(diǎn)，則不必“順藤摸瓜”，直接鏈接即可。(4)S->next=P->next;(1)P->next=S;while(P->next!=Q)P=P->next;(10)P=Q;(4)S->next=P->next;P->next=S;3.編寫程序，將若干整數(shù)從鍵盤輸入，以單鏈表形式存儲(chǔ)起來，然后計(jì)算單鏈表中結(jié)點(diǎn)的個(gè)數(shù)(其中指針指向該鏈表的第一個(gè)結(jié)點(diǎn))。注：統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)是【省統(tǒng)考樣題】的要求，也是教材P604-6計(jì)算鏈表長度的要求，編程又簡單，很容易作為考題。解：編寫C程序如下(已上機(jī)通過)：全局變量及函數(shù)提前說明：#include<stdio.h>#include<stdlib.h>typedefstructliuyu{intdata;structliuyu*link;}test;liuyu*p,*q,*r,*head;intm=sizeof(test);voidmain() /*第一步，從鍵盤輸入整數(shù)，不斷添加到鏈表*/{inti;head=(test*)malloc(m);/*m=sizeof(test);*/p=head;i=0;while(i!=-9999){printf("/ninputaninteger[stopby'-9999']:");scanf("%d",&i);p->data=i; /*inputdataissaved*/p->link=(test*)malloc(m);/*m=sizeof(test));*/q=p;p=p->link;}q->link=NULL; /*原先用p->link=NULL似乎太晚！*/p=head;i=0; /*統(tǒng)計(jì)鏈表結(jié)點(diǎn)的個(gè)數(shù)并打印出來*/while(p->link!=NULL){printf("%d",p->data);p=p->link;i++;

}printf（"\nnodenumber=%d\n",i-1）；/*結(jié)點(diǎn)的個(gè)數(shù)不包括-9999*/}0301陳建武：3.程序中統(tǒng)計(jì)結(jié)點(diǎn)數(shù)應(yīng)是i個(gè),而不是i-1.假設(shè)鏈表表長為n,i從0開始,則在統(tǒng)計(jì)某一結(jié)點(diǎn)后i加一，此時(shí)p已指向下一個(gè)結(jié)點(diǎn)，第一結(jié)點(diǎn)統(tǒng)計(jì)結(jié)束,i為1,p指向第二結(jié)點(diǎn)即當(dāng)p指向尾結(jié)點(diǎn)（第n個(gè)結(jié)點(diǎn)）時(shí)i的值為n-1,while循環(huán)條件不符（指針域?yàn)閚ull）,退出循環(huán)，即得統(tǒng)計(jì)的結(jié)點(diǎn)數(shù)，為n-1.所以i的值就是結(jié)點(diǎn)數(shù)，不必再減一4,請(qǐng)編寫26個(gè)字母按特定字母值插入或刪除的完整程序，可自行選用順序存儲(chǔ)或鏈表結(jié)構(gòu)。答：#include<stdio.h>/*#include<stdio.h>/*全局變量及函數(shù)提前說明：*/#include<stdlib.h>typedefstructliuyu{chardata；structliuyu*link；}test；liuyu*p,*q,*r,*head；intL； /*元素的個(gè)數(shù)*/intm=sizeof(test)；voidbuild()； /*主函數(shù)中會(huì)被調(diào)用的函數(shù)應(yīng)當(dāng)預(yù)先說明*/voiddisplay。；intinsert_char(char,char)； /*插入一個(gè)字母，在第字母Y之前，若無字母則加到末尾*/intdelet_char(char)； /*刪除元素X,注意保存X的前趨元素指針！*//**/voidbuild()/*字母鏈表的生成*/{inti；head=(test*)malloc(m)；/*m=sizeof(test)；*/p=head；for(i=1；i<L；i++){p->data=i+'a'-1；/*'a'也可用其ASCII碼97來表示 */p->link=(test*)malloc(m)；/*m=sizeof(test))；*/p=p->link；}p->data=i+'a'-1；p->link=NULL；}/* */voiddisplay() /*字母鏈表的輸出*/{p=head；while(p->link!=NULL){printf("%c",p->data)；p=p->link；}printf("%c\n",p->data)；}/* */intinsert_char(charX,charY) /*插入一個(gè)字母X在某個(gè)字母丫之前，若找不到丫字母則加到末尾*/{p=head；r=(test*)malloc(m)；r->data=X；if(head->data==Y){head=r；r->link=p；}else{while((p->data!=Y)&&(p->link!=NULL)){q=p；p=p->link；}if(p->data==Y){q->link=r；r->link=p；}else{p->link=r；r->link=NULL；}}L++；return(0)；)/* */intdelet_char(charX)/*刪除元素乂，注意保存乂的前趨元素指針！*/{p=head;if(head->data==X){head=head->link;free(p);}else{while((p->data!=X)&&(p->link!=NULL)){q=p;p=p->link;}if(p->data==X){q->link=p->link;free(p);}elsereturn(-1);}L--;return(0);}/* */voidmain(void) /*字母線性表的生成和輸出*/{L=26;build();display();printf("insertreturnvalue=%d\n”,insert_char('L','W'));display();printf("deletereturnvalue=%d\n",delet_char('z'));display();}附：屏幕上顯示的執(zhí)行結(jié)果是：abcdefghijklmnopqrstuvwxyzinsertreturnvalue=0abcd9efghijklmnopqrstuvwxyzLdeletereturnvalue=0abcdefghijklmnopqrstuvwxyL0301陳建武修改意見：一.display。函數(shù)代碼可優(yōu)化為四行voiddisplay() /*字母鏈表的輸出*/{p=head;while(p->link!=NULL)//改為while(p),因?yàn)楫?dāng)p指向尾結(jié)點(diǎn)時(shí),p不為null,條件成立循環(huán)，//printf(),然后p被賦值為null,此時(shí)循環(huán)條件不符退出，正好.{printf("%c”,p->data);p=p->link;}printf("%c\n",p->data);//用亞1^如"此行可刪}二.對(duì)intinsert_char(charX,charY)，若用帶頭結(jié)點(diǎn)的鏈表，代碼可減為10彳亍我的程序如下(若參數(shù)沒有slistp,代碼要多一行，讓q指向頭指針)voidInsertFind(slistp,charinsertchar,charinsertpos)//字母insertpos前插入字母insertchar{slistpprior,newnode;//newnode新結(jié)點(diǎn)，pprior為插入位置結(jié)點(diǎn)的直接前驅(qū)newnode=newliuyu;//為新結(jié)點(diǎn)分配內(nèi)存newnode->data=insertchar; 〃對(duì)結(jié)點(diǎn)數(shù)據(jù)域初始化while(p) 〃當(dāng)p指向尾結(jié)點(diǎn)時(shí)最后一次循環(huán){pprior=p; 〃pprior從頭指針開始，指向p的直接前驅(qū)p=p->next; //「從首元結(jié)點(diǎn)開始，不斷前移，直至最后,p為nullif(p&&(p->data==insertpos))//當(dāng)p為null或者結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)樗迦氲淖帜?break;〃則退出循環(huán)}newnode->next=pprior->next;〃在找到的位置前插入pprior->next=newnode;}對(duì)刪除結(jié)點(diǎn)的操作，若有頭結(jié)點(diǎn)，同樣可以減少代碼，由此可見創(chuàng)建一個(gè)頭結(jié)點(diǎn)對(duì)簡化程序有很大的幫助.上面的觀點(diǎn)，僅供參考，不對(duì)之處，請(qǐng)指教！第3章棧和隊(duì)列自測(cè)卷答案 姓名班級(jí)題號(hào)一二三四五六總分題分151020202015100得分一、填空題(每空1分，共15分).【李春葆】向量、棧和隊(duì)列都是澧性—結(jié)構(gòu)，可以在向量的任何 位置插入和刪除元素；對(duì)于棧只能在一棧頂—插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入和隊(duì)首刪除元素。.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂—。不允許插入和刪除運(yùn)算的一端稱為 棧底。. 隊(duì)列—是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的前一個(gè)—位置。.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有一Q-1個(gè)元素。.向棧中壓入元素的操作是先移動(dòng)棧頂指針，后存入元素—.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先移動(dòng)隊(duì)首指針,后取出元素。.〖00年統(tǒng)考題〗帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長度等于_0_。解：head|L=head|頭結(jié)點(diǎn)~RR=head二、判斷正誤(判斷下列概念的正確性，并作出簡要的說明。)(每小題1分，共10分)x)1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無關(guān)。x)2.在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊(duì)列。)3.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。)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)概念，二者不是同類項(xiàng)。X)6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。)7.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。)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.?？談t進(jìn)D.棧滿則出(C)2.〖李春葆〗若已知一個(gè)棧的入棧序列是1,2,3,…，n,其輸出序列為p1,p2,p3,…，pn,若p1=n,則pi為A.iB.n=iC.n-i+1D.不確定

解釋：當(dāng)p1=n，即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的，那么輸入順序必定是1,2,3,…，n,則出棧的序列是n,…，3，2，1。B)3.〖李春葆〗判定一個(gè)棧ST(最多元素為m0)為空的條件是A.ST->top<>0B.ST->top=0C.ST->top<>m0D.ST->top=m0B)4.〖李春葆〗判定一個(gè)隊(duì)列QU(最多元素為m0)為滿隊(duì)列的條件是A.QU->rear一QU->front==m0B.QU->rear一QU->front-1==m0C.QU->front==QU->rear D.QU->front==QU->rear+1D)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；(C)n+r—f； (D)(n+r—f)%n6.198初程P71】從供選擇的答案中，選出應(yīng)填入下面敘圣內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。設(shè)有4個(gè)數(shù)據(jù)元素a1、a2、a3和a4,對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)棧或進(jìn)隊(duì)操作時(shí)，按a1、a2、a3、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。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有E個(gè)。供選擇的答案：A?D：①a1②a2 ③a3④a4E：①1 ②2 ③3 ④0答：ABCDE=2,4,1,2, 27.194初程P75】從供選擇的答案中，選出應(yīng)填入下面敘述？內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。c,經(jīng)過PUSH,POP,PUSH,PUSH,POP操作后，從棧中彈出棧是一種線性表，它的特點(diǎn)是」一。設(shè)用一維數(shù)組A[1,…,n]來表示一個(gè)棧，A[n]為棧底，用整型變量T指示當(dāng)前棧頂位置，A[T]為棧頂元素。往棧中推入(PUSH)一個(gè)新元素時(shí)，變量T的值」—；c,經(jīng)過PUSH,POP,PUSH,PUSH,POP操作后，從棧中彈出A：①先進(jìn)先出②后進(jìn)先出③進(jìn)優(yōu)于出B,C：①加1②減1③不變D：①a,b②b,c③c,a④b,a ⑤c,bE：①n+1 ②n+2 ③n答案：ABCDE=2,2,1,6,4④n-1 ⑤n-2素時(shí)，變量T的值_C—。設(shè)?？諘r(shí)，有輸入序列a,b,的元素的序列是」—,變量丁的值是E。供選擇的答案：④出優(yōu)于進(jìn)⑤隨機(jī)進(jìn)出④清0⑤加2⑥減2⑥a,c注意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆棧，本題中底部為n,向地址的低端遞減生成，稱為向下生成堆棧。8.191初程P77】從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(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ā)生上溢，則說明該棧的最大容量為_C—。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的_」_分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng)一L時(shí)，才產(chǎn)生上溢。供選擇的答案：A，B：①空 ②滿③上溢④下溢C： ①n-1 ②n③n+1④n/2D：①長度②深度③棧頂④棧底E：①兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn)②其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)③兩個(gè)棧的棧頂在達(dá)?？臻g的某一位置相遇④兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答案：ABCDE=2,1,2,4,3四、簡答題（每小題4分，共20分）.【嚴(yán)題集3.2①和3.11①】說明線性表、棧與隊(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)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表？1中。。②用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。.【統(tǒng)考書P604-11，難于嚴(yán)題集3.1①】設(shè)有編號(hào)為1，2,3,4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。①全進(jìn)之后再出情況，只有1種：4,3,2,1②進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,13,2,4,13,2,1,4③進(jìn)2個(gè)之后再出的情況，有5種，2,4,3,1 2,3,4,12,1,3,42,1,4,32,1,3,4④進(jìn)1個(gè)之后再出的情況，有5種，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3.【劉自編】假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和，13州2’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量（j--）從表尾開始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機(jī)內(nèi)已是順序存儲(chǔ)，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動(dòng)作實(shí)現(xiàn)。（但堆棧是先減后壓還是……）若正文是單鏈表形式存儲(chǔ)，則等同于隊(duì)列，需開輔助空間，可以從鏈?zhǔn)组_始入棧，全部壓入后再依次輸出。.【統(tǒng)考書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ì)列長度）。我們常采用法②，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲?，而另一個(gè)指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是：f=rear隊(duì)滿標(biāo)志是：f=（r+1）%N5.【統(tǒng)考書P604-14］設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)從0到39），現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)運(yùn)算后，有①front=11，rear=19；②front=19，rear=11；問在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？答：用隊(duì)列長度計(jì)算公式：（N+r—f）%N①L=（40+19—11）%40=8 ②L=（40+11—19）%40=32五、閱讀理解（每小題5分，共20分。至少要寫出思路）

畫出.【嚴(yán)題集3.7①】按照四則運(yùn)算加、減、乘、除和冪運(yùn)算（T）優(yōu)先關(guān)系的慣例，并仿照教椒3-2的格式，對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程：畫出A-BXC/D+EfF 序號(hào)OPTR核OPND棧當(dāng)前字符符注f操作）A一cpD+E一F1■puihCOPWD/A^2A■piish(OPTR/^^3A.puflliCOPNDJff)1#—AB*pushfOPTRO5ABpnshfOPND.'C)6tt一美ABC■V歸的，令T產(chǎn)理*C7AT】*pushCOPTR//H)S#—AT,■puahtOFNDjm9群一/AT3D歸約*令T?=T/D10#-/ATS■桿均*令T±=A—1\】1Ts■pushCDPTR/+r)12#+T」■push(OPND；Er)13壯+T」E?■pushWJPTR/f)14TjE■fpusiMOPNlJJF')15*十中REF■歸為.令T,=E/FL6tf+TE歸約，令+T*答：」一ftRV.【嚴(yán)題集3.3②】寫出下列程序段的輸出結(jié)果(棧的元素類型5￡良川Type為char)。voidmain(){StackS；Charx,y；InitStack(S)；X='c'；y='k'；Push(S,x)；Push(S,"a')；Push(S,y)；Pop(S,x)；Push(S,'t')；Push(S,x)；Pop(S,x)；Push(S,'s')；while(!StackEmpty(S)){Pop(S,y)；printf(y)；)；Printf(x)；}答：輸出為“stack”。.【嚴(yán)題集3.12②】寫出下列程序段的輸出結(jié)果(隊(duì)列中的元素類型QElemType為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’)；while(!QueueEmpty(Q)){DeQueue(Q,y)；printf(y)；)；Printf(x)；}答：輸出為“char”。.【嚴(yán)題集3.13②】簡述以下算法的功能(棧和隊(duì)列的元素類型均為int)。voidalgo3(Queue&Q){StackS；intd；InitStack(S)；while(!QueueEmpty(Q)){DeQueue(Q,d)；Push(S,d)；);while(!StackEmpty(S)){Pop(S,d)；EnQueue(Q,d)；}}答：該算法的功能是：利用堆棧做輔助，將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置。六、算法設(shè)計(jì)(每小題5分，共15分。至少要寫出思路).【李春葆及嚴(yán)題集3.19④】假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧，編寫一個(gè)判別表達(dá)式中括弧是否正確配對(duì)的函數(shù)correct(exp,tag)；其中：exp為字符串類型的變量(可理解為每個(gè)字符占用一個(gè)數(shù)組元素)，表示被判別的表達(dá)式，tag為布爾型變量。答：用堆棧$七進(jìn)行判定，將口、工或切入棧，當(dāng)遇到工、口1或工時(shí)，檢查當(dāng)前棧頂元素是否是對(duì)應(yīng)的口、[或{，若是則退棧，否則返回表示不配對(duì)。當(dāng)整個(gè)算術(shù)表達(dá)式檢查完畢時(shí)，若棧為空表示括號(hào)正確配對(duì)，否則不配對(duì)。編程后的整個(gè)函數(shù)如下(李書P31—32)#definem0100 /*m0為算術(shù)表達(dá)式中最多字符個(gè)數(shù)*/correct(exp,tag)charexp[m0]；inttag；{charst[m0]；inttop=0,i=1；tag=1；while(i<=m0&&tag){if(exp[i]=='('||exp[i]=='['||exp[i]=='{') /*遇到‘('、'['或'{',則將其入棧*/{top++；st[top]=exp[i]；}if(exp[i]==')') /*遇到')'，若棧頂是'('，則繼續(xù)處理，否則以不配對(duì)返回*/if(st[top]==,(,)top--；elsetag=0；if(exp[i]==’)’) /*遇到']'，若棧頂是'[',則繼續(xù)處理，否則以不配對(duì)返回*/if(st[top]=='[']top--；elsetag=0；if(exp[i]==’)’)/*遇到’}’，若棧頂是“‘，則繼續(xù)處理，否則以不配對(duì)返回*/if(st[top]=='{′top--;elsetag=0;i++;}if(top>0)tag=0;/*若棧不空，則不配對(duì)*/}嚴(yán)題集對(duì)應(yīng)答案：3.19StatusAllBrackets_Test(char*str)//判別表達(dá)式中三種括號(hào)是否匹配{InitStack(s);for(p=str;*p;p++){if(*p=='('||*p=='['||*p=='{')push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'&&c!='[')returnERROR;if(*p=='}'&&c!='{')returnERROR;//必須與當(dāng)前棧頂括號(hào)匹配}}//forif(!StackEmpty(s))returnERROR;returnOK;}//AllBrackets_Test.【統(tǒng)考書P604-15］假設(shè)一個(gè)數(shù)組squ［m］存放循環(huán)隊(duì)列的元素。若要使這m個(gè)分量都得到利用，則需另一個(gè)標(biāo)志tag，以tag為0或1來區(qū)分尾指針和頭指針值相同時(shí)隊(duì)列的狀態(tài)是“空”還是“滿”。試編寫相應(yīng)的入隊(duì)和出隊(duì)的算法。解：這就是解決隊(duì)滿隊(duì)空的三種辦法之①設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空(其他兩種見簡答題)；思路：一開始隊(duì)空，設(shè)tag=0,若從rear一端加到與front指針相同時(shí)，表示入隊(duì)已滿，則令tag=1；若從front一端加到與rear指針相同時(shí)，則令tag=0,表示出隊(duì)已空。.【嚴(yán)題集3.31③］試寫一個(gè)算法判別讀入的一個(gè)以響'為結(jié)束符的字符序列是否是“回文”。答：編程如下：intPalindrome_Test()//判別輸入的字符串是否回文序列，是則返回1,否則返回0{InitStack(S);InitQueue(Q);while((c=getchar())!='@'){Push(S,c);EnQueue(Q,c);//同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu)}while(!StackEmpty(S)){Pop(S,a)；DeQueue(Q,b))；if(a!=b)returnERROR；}returnOK；}//Palindrome_Test第4?5章串和數(shù)組自測(cè)卷答案 姓名班級(jí)題號(hào)一二三四五總分題分2015201530100得分一、填空題(每空1分，共20分).不包含任何字符(長度為0)的串稱為空串: 由一個(gè)或多個(gè)空格(僅由空格符)組成的串稱為空白串。(對(duì)應(yīng)嚴(yán)題集4.1①，簡答題：簡述空串和空格串的區(qū)別).設(shè)5="；分℃皿6成加@可"℃"，則strlen(s)= 20,“/”的字符定位的位置為. 3.子串的定位運(yùn)算稱為串的模式匹配：被匹配的主串—稱為目標(biāo)串，.壬串—稱為模式。.設(shè)目標(biāo)丁="@6"血血2@@"，模式P="cdcc”，則第6—次匹配成功。.若n為主串長，m為子串長，則串的古典(樸素)匹配算法最壞的情況下需要比較字符的總次數(shù)為(n-m+1)*m.假設(shè)有二維數(shù)組A，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知慶的起始存儲(chǔ)位置(基地址)為1000,則數(shù)組A的體箱(存儲(chǔ)量)為288B:末尾元素%的第一個(gè)字節(jié)地址為1282:若按行存儲(chǔ)時(shí).元素A14的第一個(gè)字節(jié)地址為(8+4)X6+1000=1192；若按列存儲(chǔ)時(shí),元素人斗的第一個(gè)字節(jié)地址為(6義7+4)義6+1000)=1276 。 47.〖00年計(jì)算機(jī)系考研題〗設(shè)數(shù)組a[1…60,1…70]的基地址為2048,每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為-9188。答：考慮0行0列，(58列X61行+32行)X2字節(jié)+基址2048=9188??.三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的.行下標(biāo) 、列下標(biāo)和元素值。.求下列廣義表操作的結(jié)果：GetHead【((a,b),(c,d))]===(a,b)； 〃頭元素不必加括號(hào)GetHead【GetTail【((a,b),(c,d))】】===(c,d) —；GetHead【GetTail【GetHead【((a,b),(c,d))】】】===b；GetTail【GetHead【GetTail【((a,b),(c,d))】】]=== (d)；二、單選題(每小題1分，共15分)B)1.〖李〗串是一種特殊的線性表，其特殊性體現(xiàn)在：A.可以順序存儲(chǔ) B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈?zhǔn)酱鎯?chǔ) D.數(shù)據(jù)元素可以是多個(gè)字符B)2.〖李〗設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作：A.連接B.模式匹配C.求子串D.求串長(D)3.〖李〗設(shè)串s1='ABCDEFG',s2='PQRST',函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i開始的j個(gè)字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是：A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEFA.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF解：con(x,y)返回x和y串的連接串，即con(x,y)=‘ABCDEFGPQRST’；subs(s,i,j)返回串s的從序號(hào)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’)之連接，即BCDEFEF(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ǔ)地址為。(無第0行第0列元素)A.16902B.16904C.14454D.答案A,B,C均不對(duì)答：(57列義60行+31行)X2字節(jié)+10000=16902(A)(B)5.設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分(如下圖所示)按行序存放在一維數(shù)組B［1,n(n-1)/2］中，對(duì)下三角部分中任一元素ajjiWj),在一維數(shù)組B中下標(biāo)k的值是：a11a11aaA= 2,1 2,2解：注意B的下標(biāo)要求從1開始。先用第一個(gè)元素去套用，可能有B和C；再用第二個(gè)元素去套用B和C，B=2而C=3(不符);所以選B6.191初程P78】從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。有一個(gè)二維數(shù)組慶，行下標(biāo)的范圍是0到8,列下標(biāo)的范圍是1到5,每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址。假設(shè)存儲(chǔ)數(shù)組元素A［0,1］的第一個(gè)字節(jié)的地址是0。存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是^^。若按行存儲(chǔ)，則A［3,5］和A［5,3］的第一個(gè)字節(jié)的地址分別是B和C。若按列存儲(chǔ).則A［7,1］和慶［2,4］的第一個(gè)字節(jié)的地址分別是D和E。供選擇的答案A?E：①28 ②44 ③76 ④92 ⑤108⑥116 ⑦132 ⑧176 ⑨184 ⑩188答案：ABCDE=8,3,5,1,67.194程P12］ 從供選擇的答案中，選出應(yīng)填入下面敘內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。有一個(gè)二維數(shù)組慶，行下標(biāo)的范圍是1到6,列下標(biāo)的范圍是0到7,每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是A個(gè)字節(jié)。假設(shè)存儲(chǔ)數(shù)組元素A［1,0］的第一個(gè)字節(jié)的地址是0,則存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是B。若按行存儲(chǔ),則人12,4］的第一個(gè)字節(jié)的地址是C。若按列存儲(chǔ)，則A［5.7］的第一個(gè)字節(jié)的地址是D。供選擇的答案A?D：①12 ②66 ③72 ④96 ⑤114 ⑥120⑦156 ⑧234 ⑨276 ⑩282 (11)283 (12)288答案：ABCD=12,10, 3,9三、簡答題(每小題5分，共15分)1.KMP算法的設(shè)計(jì)思想是什么？它有什么優(yōu)點(diǎn)?

.(軟件技術(shù)？)已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個(gè)元素占K個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址為Loc(a11),請(qǐng)寫出求Loc(aij)的計(jì)算公式。如果采用列優(yōu)先順序存放呢？解：公式教材已給出，此處雖是方陣，但行列公式仍不相同；按行存儲(chǔ)的元素地址公式是：Loc(aij)=Loc(a11)+[(iT)*m+(jT)]*K按列存儲(chǔ)的元素地址公式是：Loc(aij)=Loc(a11)+[(jT)*m+(iT)]*K.【全國專升本資格考試】遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間，對(duì)嗎？為什么？答：不一定。時(shí)間復(fù)雜度與樣本個(gè)數(shù)n有關(guān)，是指最深層的執(zhí)行語句耗費(fèi)時(shí)間，而遞歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數(shù)也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來顯示循環(huán)次數(shù)而已。四、計(jì)算題(每題5分，共20分)設(shè)5=’1AMASTUDENT',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)='A'；SubString(s,7,8)=’STUDENT'Concat(t,SubString(s,7,8))='GOODSTUDENT'所以Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))='AGOODSTUDENT'2.【嚴(yán)題集4.8②】已知主串s='ADBADABBAABADABBADADA’,模式串pat二'ADABBADADA’。寫出模式串的nextval函數(shù)值，并由此畫出KMP算法匹配的全過程。解：(由演示程序得知)nextval函數(shù)值為0102101040在第12個(gè)字符處發(fā)現(xiàn)匹配！s='ADBADABBAABADABBADADA’pat='ADABBADADA'3.(P604-18)用三元組表表示下列稀疏矩陣:-00000000-00000000-00000-2一0300080000009000000000000000⑴00060000(2)005000000000000000000000000500003020000000它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元解：參見填空題4.三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，素的行下標(biāo)、列下標(biāo)和元素值。它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元所以(1)可列表為:66所以(1)可列表為:66416-2259435653(2)可列表為:4.(P604-19)下列各三元組表分別表示一個(gè)稀疏矩陣，試寫出它們的稀疏矩陣。一646-4551221111?212249⑴313⑵3283284443565364376116解：(1)為6義4矩陣，非零元素有6個(gè)，但其中一數(shù)下標(biāo)有誤？(2)為4X5矩陣，非零元素有5個(gè)02020012000改為2,1,123000000400601600010000000900800600700五、算法設(shè)計(jì)題(每題10分，共30分).【嚴(yán)題集4.12③】編寫一個(gè)實(shí)現(xiàn)串的置換操作Replace(&S,T,V)的算法。解：intReplace(Stringtype&S,StringtypeT,Stringtype丫)"/將串5中所有子串丁替換為V,并返回置換次數(shù)(for(n=0,i=1；i<=Strlen(S)-Strlen(T)+1；i++)//注意i的取值范圍if(!StrCompare(SubString(S,i,Strlen(T)),T))//找到了與丁匹配的子串{〃分別把T的前面和后面部分保存為head和tailStrAssign(head,SubString(S,1,i-1))；StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1))；StrAssign(S,Concat(head,V))；StrAssign(S,Concat(S,tail))；//把head,V,tail連接為新串i十二Strlen(V)；//當(dāng)前指針跳到插入串以后n++；n++；}//ifreturnn；}//Replace分析：i+=Strlen(V)；這一句是必需的，也是容易忽略的.如省掉這一句，則在某些情況下，會(huì)引起不希望的后果，雖然在大多數(shù)情況下沒有影響.請(qǐng)思考:設(shè)S='place',T='ace',V='face',則省掉i+=Strlen(V)；運(yùn)行時(shí)會(huì)出現(xiàn)什么結(jié)果?.【全國專升本資格考試】寫出將字符串反序的遞歸或遞推算法，例如字符串為"abcsxw"，反序?yàn)椤皐xscba"(注:這也是嚴(yán)題集4.10③編寫對(duì)串求逆的遞推算法)算法思路：①假定用單鏈表結(jié)構(gòu)存儲(chǔ)字符串；

否則就打印當(dāng)前字符并返回。Invert(stringlistnode*p){if(!p)return(0);elseInvert(p->next);printf("％c”，p->data)否則就打印當(dāng)前字符并返回。Invert(stringlistnode*p){if(!p)return(0);elseInvert(p->next);printf("％c”，p->data)}DLR(x*root){if(!root)return(0);printf(“％d”->data);DLR(root->lchild);DLR(root->rchild);)遞歸算法的一般形式：(殷人凱題集P102)voidp(參數(shù)表){if(遞歸結(jié)束條件)可直接求解步驟； 基本項(xiàng)elsep(較小的參數(shù))； 歸納項(xiàng))如果當(dāng)前串長為0,則return(-1)否則開始遞歸：if串沒有到末尾，則P=P->next;再調(diào)用invert(s);elseprintf(p->data);return4.10voidString_Reverse(Stringtypes,Stringtype虹)〃求$的逆串r(StrAssign(r,'');〃初始化r為空串for(i=Strlen(s);i;i--)(StrAssign(c,SubString(s,i,1));StrAssign(r,Concat(r,c));//把s的字符從后往前添加到r中 /這是遞推算法?)}//String_Reverse3.【嚴(yán)題集5.18⑤】試設(shè)計(jì)一個(gè)算法，將數(shù)組An中的元素A[0]至A[n-1]循環(huán)右移k位，并要求只用一個(gè)元素大小的附加存儲(chǔ)，元素移動(dòng)或交換次數(shù)為O(n)解：5.18分析：要把A的元素循環(huán)右移k位，則A[0]移至A[k],A[k]移至A[2k] 直到最終回到A[0].然而這并沒有全部解決問題，因?yàn)橛锌赡苡械脑卦诖诉^程中始終沒有被訪問過，而是被跳了過去.分析可知，當(dāng)n和k的最大公約數(shù)為p時(shí),只要分別以A[0],A[1],...A[p-1]為起點(diǎn)執(zhí)行上述算法，就可以保證每一個(gè)元素都被且僅被右移一次，從而滿足題目要求.也就是說,A的所有元素分別處在p個(gè)"循環(huán)鏈"上面.舉例如下：n=15,k=6,則p=3.第一條鏈:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]./已“順便”移動(dòng)了A[6]、A[12]…第二條鏈:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].第三條鏈:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].恰好使所有元素都右移一次.雖然未經(jīng)數(shù)學(xué)證明，但作者相信上述規(guī)律應(yīng)該是正確的.程序如下：voidRSh(intA[n],intk)//把數(shù)組A的元素循環(huán)右移k位，只用一個(gè)輔助存儲(chǔ)空間{for(i=1;i<=k;i++)if(n%i==0&&k%i==0)p=i;//求n和k的最大公約數(shù)pfor(i=0;i<p;i++){j=i;l=(i+k)%n;temp=A[i];while(l!=i){A[j]=temp;temp=A[l];A[l]=A[j]；j=l；l=(j+k)%n；)//循環(huán)右移一步A[i]=temp；}//for}//RSh附加題：利用C的庫函數(shù)strlen,strcpy(或strncpy)寫一個(gè)算法voidStrDelete(char*S,intt,intm)，刪除串$中從位置i開始的連續(xù)的m個(gè)字符。若i，strlen(S),則沒有字符被刪除；若i+m2strlen(S),則將S中從位置i開始直至末尾的字符均被刪去。提示：strlen是求串長(length)函數(shù)：intstrlen(chars)；〃求串的長度strcpy是串復(fù)制(copy)函數(shù):char*strcpy(charto,charfrom)；〃該函數(shù)將串from復(fù)制到串to中，并且返回一個(gè)指向串to的開始處的指針。第6章 樹和二叉樹自測(cè)卷解答 姓名班級(jí)題號(hào)一二三四五六總分題分101511202024100得分一、下面是有關(guān)二叉樹的敘述，請(qǐng)判斷正誤（每小題1分，共10分）V）1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在門個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有0個(gè)非空指針域。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)的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。 （應(yīng)當(dāng)是二叉排序樹的特點(diǎn)）X）6.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2『1-1,其中卜是樹的深度。X）7.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。X）8.對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第1層上最多能有2i—1個(gè)結(jié)點(diǎn)（應(yīng)2i-1）V）9.用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2nj指針區(qū)域中有班1個(gè)為空指針。（正確。用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)共有2n個(gè)鏈域。由于二叉樹中，除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有n-1個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針，還有n+1個(gè)空指針。）即有后繼鏈接的指針僅nT個(gè)。（V）10.〖01年計(jì)算機(jī)系研題〗具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。最快方法：用葉子數(shù)=[n/2]=6,再求n2=n°-1=5二、填空（每空1分，共15分）1.由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有.5_種形態(tài)。計(jì)算機(jī)研20001一棵深度為6的滿二叉樹有\(zhòng)』=2卜1-1=31—個(gè)分支結(jié)點(diǎn)和26-1=32個(gè)葉子。注：滿二叉樹沒有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。.一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為—9 。（注：用[log2n]+1（257W2-1）.【全國專升本統(tǒng)考題】設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有350個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)=[n/2]=350.設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有500—個(gè)葉子結(jié)點(diǎn)，有39—個(gè)度為2的結(jié)點(diǎn)，有一1個(gè)結(jié)點(diǎn)只有非空左子樹，有0—個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)=[n/2]=500,n=n-1=499。另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左子樹。完全二叉樹的特點(diǎn)決定不2可能有左空右不空的情況，所以非空右子樹數(shù)=0..【嚴(yán)題集6.7③】一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度為_o_，最小深度為2_。答：當(dāng)k=1（單叉樹）時(shí)應(yīng)該最深，深度=門（層）當(dāng)k=n-1（k-1叉樹）時(shí)應(yīng)該最淺，深度=2（層）.（不可能只1層，那是只有根結(jié)點(diǎn)的情況。教材說是“完全k叉樹”，指的是k，n的情況。）.196程試題1】二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按NLR次序），后序法（即按_LRN 次序）和中序法（也

稱對(duì)稱序法，即按LNR次序)。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH,中序序列是?^86)口，則它的后序序列必是 FEGHDCB。解：求D之法1：畫圖(見右圖)，由前序先確定root，由中序先確定左邊的葉子，再慢慢推導(dǎo))，由圖知，后序序列為FEGH……。。求D之法2：其實(shí)不畫圖也能快速得出后序序列，只要找到根的位置特征。請(qǐng)看，前序遍加EFCGDH中，根結(jié)點(diǎn)在最前面，是B；則后序遍歷中B一定在最后面。小結(jié)：方法1：由前序先確定root，由中序先確定左子樹方法2：遞歸計(jì)算。如8在前序序列中第一，中序中在中間(可知左右子樹上有哪些元素)，則在后序中必為最后。如法對(duì)8的左右子樹同樣處理，則問題得解。.【全國專升本統(tǒng)考題】中序遍歷的遞歸算法平均空間復(fù)雜度為 O(樹的深度卜+1)或O(n).【計(jì)算機(jī)研2001】用5個(gè)權(quán)值｛3,2,4,5,1｝構(gòu)造的哈夫曼(Huffman)樹的帶權(quán)路徑長度是,_J3_r 解：先構(gòu)造哈夫曼樹，得到各葉子的路徑長度之后便可求出WPL=(4+5+3)X2+(1+2)X3=33TOC\o"1-5"\h\z““、 (15)/\9) (6)“4 5 3 (3)2(注：原題為選擇題：A.32 B.33 C.34D.15)三、單項(xiàng)選擇題(每小題1分，共11分C)1.不含任何結(jié)點(diǎn)的空樹 。(B)是一棵二叉樹；(B)是一棵二叉樹；(D)既不是樹也不是二叉樹(C)是一棵樹也是一棵二叉樹；C)2.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以。(人)它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)； (8)它不能用鏈?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)都不能使用A、C)3.〖01年計(jì)算機(jī)研題〗具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。(A)log(n) (B)log(n