《c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)》自測(cè)題試卷

PAGE1PAGE1第一章概論自測(cè)題姓名班級(jí)題號(hào)一二三四五六總分題分3315982015100得分一、填空題（每空1分，共33分）1.一個(gè)計(jì)算機(jī)系統(tǒng)包括和兩大部分。2.一臺(tái)計(jì)算機(jī)中全部程序的集合，稱為這臺(tái)計(jì)算機(jī)的。3.計(jì)算機(jī)軟件可以分為軟件和軟件兩大類?？茖W(xué)計(jì)算程序包屬于，診斷程序?qū)儆凇?.一種用助憶符號(hào)來(lái)表示機(jī)器指令的操作符和操作數(shù)的語(yǔ)言是。5.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的以及它們之間的和運(yùn)算等的學(xué)科。6.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是的有限集合，R是D上的有限集合。7.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的、數(shù)據(jù)的和數(shù)據(jù)的這三個(gè)方面的內(nèi)容。8.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是和。9.線性結(jié)構(gòu)中元素之間存在關(guān)系，樹形結(jié)構(gòu)中元素之間存在關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系。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)沒(méi)有結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以。12.在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以。13．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是。14.數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是。15.一個(gè)算法的效率可分為效率和效率。16.任何一個(gè)C程序都由和若干個(gè)被調(diào)用的其它函數(shù)組成。17.變量一經(jīng)說(shuō)明，就確定該變量的取值范圍及。二、單項(xiàng)選擇題（每小題1分，共15分）（）1.通常所說(shuō)的主機(jī)是指∶A)CPU B)CPU和內(nèi)存 C)CPU、內(nèi)存與外存 D)CPU、內(nèi)存與硬盤（）2.在計(jì)算機(jī)內(nèi)部，一切信息的存取、處理和傳送的形式是∶A)ACSII碼 B)BCD碼 C)二進(jìn)制 D)十六進(jìn)制（）3.軟件與程序的區(qū)別是∶程序價(jià)格便宜、軟件價(jià)格昂貴； 程序是用戶自己編寫的，而軟件是由廠家提供的；C)程序是用高級(jí)語(yǔ)言編寫的，而軟件是由機(jī)器語(yǔ)言編寫的；D)軟件是程序以及開發(fā)、使用和維護(hù)所需要的所有文檔的總稱，而程序只是軟件的一部分。（）4.所謂“裸機(jī)”是指∶A)單片機(jī) B)單板機(jī) C)不裝備任何軟件的計(jì)算機(jī) D)只裝備操作系統(tǒng)的計(jì)算機(jī)（）5.應(yīng)用軟件是指∶A)所有能夠使用的軟件 B)能被各應(yīng)用單位共同使用的某種軟件C)所有微機(jī)上都應(yīng)使用的基本軟件 D)專門為某一應(yīng)用目的而編制的軟件（）6.C語(yǔ)言中的常量可分為整型常量、實(shí)型常量、字符型常量及四種。符號(hào)常量（B）長(zhǎng)整型常量（C）邏輯常量（D）二進(jìn)制整數(shù)（）7.編譯程序的功能是∶A)發(fā)現(xiàn)源程序中的語(yǔ)法錯(cuò)誤 B)改正源程序中的語(yǔ)法錯(cuò)誤C)將源程序編譯成目標(biāo)程序 D)將某一高級(jí)語(yǔ)言程序翻譯成另一種高級(jí)語(yǔ)言程序（）8.系統(tǒng)軟件中最重要的是∶A)操作系統(tǒng) B)語(yǔ)言處理系統(tǒng) C)工具軟件 D)數(shù)據(jù)庫(kù)管理系統(tǒng)（）9.可移植性最好的計(jì)算機(jī)語(yǔ)言是∶A)機(jī)器語(yǔ)言 B)匯編語(yǔ)言 C)高級(jí)語(yǔ)言 D)自然語(yǔ)言（）10.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對(duì)多關(guān)系B）多對(duì)多關(guān)系C）多對(duì)一關(guān)系D）一對(duì)一關(guān)系（）11.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的結(jié)構(gòu)；A)存儲(chǔ)B)物理C)邏輯D)物理和存儲(chǔ)（）12.算法分析的目的是：A)找出數(shù)據(jù)結(jié)構(gòu)的合理性B)研究算法中的輸入和輸出的關(guān)系C)分析算法的效率以求改進(jìn)D)分析算法的易懂性和文檔性（）13.算法分析的兩個(gè)主要方面是：A)空間復(fù)雜性和時(shí)間復(fù)雜性B)正確性和簡(jiǎn)明性C)可讀性和文檔性D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（）14.計(jì)算機(jī)算法指的是：A)計(jì)算方法B)排序方法C)解決問(wèn)題的有限運(yùn)算序列D)調(diào)度方法（）15.計(jì)算機(jī)算法必須具備輸入、輸出和等5個(gè)特性。A)可行性、可移植性和可擴(kuò)充性B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性三、簡(jiǎn)答題（每小題3分,共9分）1．我們知道計(jì)算機(jī)只能執(zhí)行機(jī)器指令，為什么它能運(yùn)行用匯編語(yǔ)言和高級(jí)語(yǔ)言編寫的程序？2.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？3.簡(jiǎn)述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。四、閱讀下列C程序段，寫出相應(yīng)的執(zhí)行結(jié)果（每小題4分，共8分）2.longintfact(n)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);}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)x分別為18，8時(shí)的執(zhí)行結(jié)果。

五、分析下面各程序段的時(shí)間復(fù)雜度（每小題5分，共20分）2.2.s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;1.1.for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;3.x=0;3.x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;4.i=1;while(i<=n)i=i*3;六、設(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分）1.D={d1,d2,d3,d4}R={(d1,d2),(d2,d3),(d3,d4)}D={d1,d2,…,d9}R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}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)}第2章線性表自測(cè)卷姓名班級(jí)題號(hào)一二三四五六七總分題分1310101071040100得分一、填空（每空1分，共13分）1.在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)元素，具體移動(dòng)的元素個(gè)數(shù)與有關(guān)。2.線性表中結(jié)點(diǎn)的集合是的，結(jié)點(diǎn)間的關(guān)系是的。3.向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)個(gè)元素。4.向一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素(1≤i≤n)時(shí)，需向前移動(dòng)個(gè)元素。5.在順序表中訪問(wèn)任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為，因此，順序表也稱為的數(shù)據(jù)結(jié)構(gòu)。6.順序表中邏輯上相鄰的元素的物理位置相鄰。單鏈表中邏輯上相鄰的元素的物理位置相鄰。7.在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由指示。8．在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的，其時(shí)間復(fù)雜度為。二、判斷正誤（在正確的說(shuō)法后面打勾，反之打叉）（每小題1分，共10分）（）1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。（）2.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。（）3.鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)將后續(xù)各個(gè)單元向前移動(dòng)。（）4.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。（）5.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。（）6.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）7.線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。（）8.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。（）9.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（）10.線性表的邏輯順序與存儲(chǔ)順序總是一致的。三、單項(xiàng)選擇題（每小題1分，共7分）（）1．?dāng)?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)（）2.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（A）110（B）108（C）100（D）120（）3.在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（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）（D）將n個(gè)結(jié)點(diǎn)從小到大排序（）4.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)個(gè)元素（A）8（B）63.5（C）63（D）7（）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ù)（）6.鏈表是一種采用存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表；（A）順序（B）鏈?zhǔn)剑–）星式（D）網(wǎng)狀（）7.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址:（A）必須是連續(xù)的（B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的（D）連續(xù)或不連續(xù)都可以（）8．線性表Ｌ在情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。（Ａ）需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值（Ｂ）需不斷對(duì)Ｌ進(jìn)行刪除插入（Ｃ）Ｌ中含有大量的結(jié)點(diǎn)（Ｄ）Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜（）9．單鏈表的存儲(chǔ)密度（Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能確定（）10．設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn)，整數(shù)P0，3，4代表地址，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為P034P0a13a24A30（Ａ）循環(huán)鏈表（Ｂ）單鏈表（Ｃ）雙向循環(huán)鏈表（Ｄ）雙向鏈表四、簡(jiǎn)答題（每小題5分，共10分）1.試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？2.描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？

五、（7分）線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五個(gè)元素的線性表L={23，17，47，05，31}，若它以鏈接方式存儲(chǔ)在下列100～119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占2個(gè)字節(jié)）和指針（占2個(gè)字節(jié)）組成，如下所示：05U17X23V31Y47Z^^100120其中指針X，Y，Z的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？六、閱讀分析題（10分）指出以下算法中的錯(cuò)誤和低效（即費(fèi)時(shí)）之處，并將它改寫為一個(gè)既正確又高效的算法。注：上題涉及的類型定義如下：#defineLISTINITSIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;//存儲(chǔ)空間基址Intlength;//注：上題涉及的類型定義如下：#defineLISTINITSIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;//存儲(chǔ)空間基址Intlength;//當(dāng)前長(zhǎng)度Intlistsize;//當(dāng)前分配的存儲(chǔ)容量}SqList;StatusDeleteK(SqList&a,inti,intk){//本過(guò)程從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素if(i<1||k<0||i+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;}//DeleteK1.寫出在順序存儲(chǔ)結(jié)構(gòu)下將線性表逆轉(zhuǎn)的算法，要求使用最少的附加空間。2.已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，請(qǐng)寫出在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的核心語(yǔ)句序列。3.編寫程序，將若干整數(shù)從鍵盤輸入，以單鏈表形式存儲(chǔ)起來(lái)，然后計(jì)算單鏈表中結(jié)點(diǎn)的個(gè)數(shù)（其中指針P指向該鏈表的第一個(gè)結(jié)點(diǎn)）。4.請(qǐng)編寫26個(gè)字母按特定字母值插入或刪除的完整程序，可自行選用順序存儲(chǔ)或鏈表結(jié)構(gòu)。附：第一次上機(jī)安排內(nèi)容要求時(shí)間線性表的插入與刪除用鏈表存儲(chǔ)方式制作福利彩票（36選7）和體育彩票（10選7）的選號(hào)器。第4周二晚6:30-9:50兩點(diǎn)說(shuō)明：福利彩票（36選7）的7個(gè)號(hào)不能重復(fù)，而體育彩票（10選7）的7個(gè)號(hào)可以重復(fù)；建議用首尾相連的鏈?zhǔn)浇Y(jié)構(gòu)，這樣可以更逼真地模擬“搖獎(jiǎng)”過(guò)程；而每個(gè)號(hào)的“搖動(dòng)”次數(shù)可用隨機(jī)數(shù)來(lái)確定。怎樣產(chǎn)生隨機(jī)數(shù)？可以利用C語(yǔ)言中的種子函數(shù)srand()和偽隨機(jī)函數(shù)rand()來(lái)實(shí)現(xiàn)。首先，給srand(m)提供一個(gè)“種子”m，它的取值范圍是從0～65535。然后，調(diào)用rand()，是偽隨機(jī)數(shù)，它會(huì)根據(jù)提供給srand()的“種子”值返回一個(gè)隨機(jī)數(shù)（在0～32767之間）。根據(jù)需要多次調(diào)用rand()，從而不斷地得到新的隨機(jī)數(shù)。無(wú)論何時(shí)，你都可以給srand()提供一個(gè)新的“種子”，從而進(jìn)一步“隨機(jī)化”rand()的輸出結(jié)果。例如，取m=17，則執(zhí)行了srand(17)之后，再執(zhí)行rand()函數(shù)，將得到輸出值94；第二次調(diào)用rand()，會(huì)得到26,……反復(fù)調(diào)用rand()就能產(chǎn)生一系列的隨機(jī)數(shù)。注意：若m不變，則rand()的輸出系列也不變，總是94,26,602,……等等。所以，建議搖號(hào)的“種子”選為當(dāng)前日期或時(shí)間，以保證每天的搖號(hào)值都不相同。第3章棧和隊(duì)列自測(cè)卷姓名班級(jí)題號(hào)一二三四五六總分題分151020202015100得分一、填空題（每空1分，共15分）1.向量、棧和隊(duì)列都是結(jié)構(gòu)，可以在向量的位置插入和刪除元素；對(duì)于棧只能在插入和刪除元素；對(duì)于隊(duì)列只能在插入和刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為。不允許插入和刪除運(yùn)算的一端稱為。3.是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。4.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的位置。5.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有個(gè)元素。6.向棧中壓入元素的操作是先，后。7.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先，后。8.帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于。二、判斷正誤（判斷下列概念的正確性，并作出簡(jiǎn)要的說(shuō)明。）（每小題1分，共10分）（）1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。（）2.在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。（）3.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。（）4.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。（）5.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。（）6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。（）7.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。（）8.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（）9.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。 （）10.一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。三、單項(xiàng)選擇題（每小題1分，共20分）（）1.棧中元素的進(jìn)出原則是Ａ．先進(jìn)先出Ｂ．后進(jìn)先出Ｃ．棧空則進(jìn)Ｄ．棧滿則出

（）2.若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不確定（）3.判定一個(gè)棧ST（最多元素為m0）為空的條件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0（）4.判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是Ａ．QU->rear－QU->front==m0Ｂ．QU->rear－QU->front－1==m0Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1（）5．?dāng)?shù)組Ｑ［ｎ］用來(lái)表示一個(gè)循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ?yàn)殛?duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素的公式為（Ａ）r－f;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%n6.設(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í)，第一次出棧得到的元素是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答：A、B、C、D、E分別為、、、、7.棧是一種線性表，它的特點(diǎn)是A。設(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答：A、B、C、D、E分別為、、、、8.在做進(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á)棧空間的中心點(diǎn)②其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)③兩個(gè)棧的棧頂在達(dá)?？臻g的某一位置相遇④兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答：A、B、C、D、E分別為、、、、四、簡(jiǎn)答題（每小題4分，共20分）1.說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。2.設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。3.假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？4.順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？5.設(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è)？五、閱讀理解（每小題5分，共20分）按照四則運(yùn)算加、減、乘、除和冪運(yùn)算（↑）優(yōu)先關(guān)系的慣例，并仿照教材例3-2的格式，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程：A－B×C/D+E↑F寫出下列程序段的輸出結(jié)果（棧的元素類型SElemType為char）。Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);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);}StackS;Charx,y;InitStack(S);X=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);寫出下列程序段的輸出結(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);}簡(jiǎn)述以下算法的功能（棧和隊(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);}}六、算法設(shè)計(jì)（每小題5分，共15分。至少要寫出思路）假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧，編寫一個(gè)判別表達(dá)式中括弧是否正確配對(duì)的函數(shù)correct(exp,tag)；其中：exp為字符串類型的變量（可理解為每個(gè)字符占用一個(gè)數(shù)組元素），表示被判別的表達(dá)式，tag為布爾型變量。2.假設(shè)一個(gè)數(shù)組squ[m]存放循環(huán)隊(duì)列的元素。若要使這m個(gè)分量都得到利用，則需另一個(gè)標(biāo)志tag，以tag為0或1來(lái)區(qū)分尾指針和頭指針值相同時(shí)隊(duì)列的狀態(tài)是“空”還是“滿”。試編寫相應(yīng)的入隊(duì)和出隊(duì)的算法。3.試寫一個(gè)算法，判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是“回文”。第4～5章串和數(shù)組自測(cè)卷姓名班級(jí)題號(hào)一二三四五總分題分2015201530100得分一、填空題（每空1分，共20分）1.稱為空串；稱為空白串。2.設(shè)S=“A;/document/Mary.doc”，則strlen(s)=,“/”的字符定位的位置為。4.子串的定位運(yùn)算稱為串的模式匹配；稱為目標(biāo)串，稱為模式。5.設(shè)目標(biāo)T=”abccdcdccbaa”，模式P=“cdcc”，則第次匹配成功。6.若n為主串長(zhǎng)，m為子串長(zhǎng)，則串的古典匹配算法最壞的情況下需要比較字符的總次數(shù)為。7.假設(shè)有二維數(shù)組A6×8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A的體積（存儲(chǔ)量）為；末尾元素A57的第一個(gè)字節(jié)地址為；若按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為；若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為。8.設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為。9.三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的、和。10.求下列廣義表操作的結(jié)果：（1）GetHead【((a,b),(c,d))】===;（2）GetHead【GetTail【((a,b),(c,d))】】===;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】===;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】===;二、單選題（每小題1分，共15分）（）1.串是一種特殊的線性表，其特殊性體現(xiàn)在：Ａ．可以順序存儲(chǔ)Ｂ．?dāng)?shù)據(jù)元素是一個(gè)字符Ｃ．可以鏈?zhǔn)酱鎯?chǔ)Ｄ．?dāng)?shù)據(jù)元素可以是多個(gè)字符（）2.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作：Ａ．連接Ｂ．模式匹配Ｃ．求子串Ｄ．求串長(zhǎng)（）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的長(zhǎng)度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是：Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEF（）4.假設(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行第0列元素）Ａ．16902Ｂ．16904Ｃ．14454Ｄ．答案A,B,C均不對(duì)()5.設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分（如右圖所示）按行序存放在一維數(shù)組B[1,n(n-1)/2]中，對(duì)下三角部分中任一元素ai,j(i≤j),在一維數(shù)組B中下標(biāo)k的值是：Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j6.從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。有一個(gè)二維數(shù)組A，行下標(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é)的地址是A。若按行存儲(chǔ)，則A[3,5]和A[5,3]的第一個(gè)字節(jié)的地址分別是B和C。若按列存儲(chǔ)，則A[7,1]和A[2,4]的第一個(gè)字節(jié)的地址分別是D和E。供選擇的答案A～E：①28②44③76④92⑤108⑥116⑦132⑧176⑨184⑩188答案：A＝B＝C＝D＝E=7.從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。有一個(gè)二維數(shù)組A，行下標(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ǔ)，則A[2,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答案：A＝B＝C＝D＝E=三、簡(jiǎn)答題（每小題5分，共15分）1.KMP算法的設(shè)計(jì)思想是什么？它有什么優(yōu)點(diǎn)？2.已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個(gè)元素占K個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址為L(zhǎng)oc(a11)，請(qǐng)寫出求Loc(aij)的計(jì)算公式。如果采用列優(yōu)先順序存放呢？3.遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間，對(duì)嗎？為什么？

四、計(jì)算題（每題5分，共20分）【嚴(yán)題集4.3①】設(shè)s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’,求Replace(s,’STUDENT’,q)和Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))。2.【嚴(yán)題集4.8②】已知主串s=’ADBADABBAABADABBADADA’,模式串pat=’ADABBADADA’。寫出模式串的nextval函數(shù)值，并由此畫出KMP算法匹配的全過(guò)程。3.用三元組表表示下列稀疏矩陣：4.下列各三元組表分別表示一個(gè)稀疏矩陣，試寫出它們的稀疏矩陣。五、算法設(shè)計(jì)題（每題10分，共30分）【嚴(yán)題集4.12③】編寫一個(gè)實(shí)現(xiàn)串的置換操作Replace(&S,T,V)的算法?！緡?yán)題集4.10③】寫出將字符串反序的遞推或遞歸算法，例如字符串為“abcsxw”，反序?yàn)椤皐xscba”【嚴(yán)題集5.18⑤】試設(shè)計(jì)一個(gè)算法，將數(shù)組An中的元素A[0]至A[n-1]循環(huán)右移k位，并要求只用一個(gè)元素大小的附加存儲(chǔ)，元素移動(dòng)或交換次數(shù)為O(n)附加題：利用C的庫(kù)函數(shù)strlen,strcpy（或strncpy）寫一個(gè)算法voidStrDelete(char*S,intt,intm)，刪除串S中從位置i開始的連續(xù)的m個(gè)字符。若i≥strlen(S)，則沒(méi)有字符被刪除；若i+m≥strlen(S)，則將S中從位置i開始直至末尾的字符均被刪去。提示：strlen是求串長(zhǎng)(length)函數(shù)：intstrlen(chars);//求串的長(zhǎng)度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分）（）1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n—1個(gè)非空指針域。（）2.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。（）3.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。（）4.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。（）5.二叉樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。（）6.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹的深度。（）7.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。（）8.對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i－1個(gè)結(jié)點(diǎn)。（）9.用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（）10.具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。二、填空（每空1分，共15分）1．由３個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有種形態(tài)。2.一棵深度為6的滿二叉樹有個(gè)分支結(jié)點(diǎn)和個(gè)葉子。3．一棵具有２５７個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為。設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有個(gè)葉子結(jié)點(diǎn)。5.設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有個(gè)葉子結(jié)點(diǎn)，有個(gè)度為2的結(jié)點(diǎn)，有個(gè)結(jié)點(diǎn)只有非空左子樹，有個(gè)結(jié)點(diǎn)只有非空右子樹。6.【嚴(yán)題集6.7③】一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度為，最小深度為。7.二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按NLR次序），后序法（即按次序）和中序法（也稱對(duì)稱序法，即按LNR次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是。

8.中序遍歷的遞歸算法平均空間復(fù)雜度為。9.用5個(gè)權(quán)值{3,2,4,5,1}構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長(zhǎng)度是。

三、選擇題（每小題1分，共11分）（）1．不含任何結(jié)點(diǎn)的空樹。（Ａ）是一棵樹;（Ｂ）是一棵二叉樹;（Ｃ）是一棵樹也是一棵二叉樹;（Ｄ）既不是樹也不是二叉樹（）2．二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以。（Ａ）它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ);（Ｂ）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ);（Ｃ）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ);（Ｄ）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用（）3.具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+1（）4．把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是。（Ａ）唯一的（Ｂ）有多種（Ｃ）有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子（Ｄ）有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子5.樹是結(jié)點(diǎn)的有限集合，它A根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m（m≥0）個(gè)B的集合T1，T2，…，Tm，每個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（1≤i≤m）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的C。供選擇的答案A：①有0個(gè)或1個(gè)②有0個(gè)或多個(gè)③有且只有1個(gè)④有1個(gè)或1個(gè)以上B:①互不相交 ②允許相交③允許葉結(jié)點(diǎn)相交④允許樹枝結(jié)點(diǎn)相交C：①權(quán) ②維數(shù)③次數(shù)④序答案：A=B=C=6.二叉樹A。在完全的二叉樹中，若一個(gè)結(jié)點(diǎn)沒(méi)有B，則它必定是葉結(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)的D。供選擇的答案A：①是特殊的樹②不是樹的特殊形式③是兩棵樹的總稱④有是只有二個(gè)根結(jié)點(diǎn)的樹形結(jié)構(gòu)B:①左子結(jié)點(diǎn)②右子結(jié)點(diǎn)③左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn)④兄弟C～D：①最左子結(jié)點(diǎn)②最右子結(jié)點(diǎn)③最鄰近的右兄弟④最鄰近的左兄弟⑤最左的兄弟⑥最右的兄弟答案：A=B=C=D＝四、簡(jiǎn)答題（每小題4分，共20分）【嚴(yán)題集6.2①】一棵度為2的樹與一棵二叉樹有何區(qū)別？

C的結(jié)點(diǎn)類型定義如下：C的結(jié)點(diǎn)類型定義如下：structnode{chardata;structnode*lchild,rchild;};C算法如下：voidtraversal(structnode*root){if(root){printf(“%c”,root->data);traversal(root->lchild);printf(“%c”,root->data);traversal(root->rchild);}}對(duì)下列二叉樹B，執(zhí)行下列算法traversal(root)，試指出其輸出結(jié)果；假定二叉樹B共有n個(gè)結(jié)點(diǎn)，試分析算法traversal(root)的時(shí)間復(fù)雜度。（每問(wèn)4分，兩問(wèn)共8分）AABDCFGE二叉樹B3.【類似嚴(yán)題集6.27③】給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹B，并簡(jiǎn)述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。283328334060085455五、閱讀分析題（每題5分，共20分）1.試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。2.把如圖所示的樹轉(zhuǎn)化成二叉樹。

BiTreeInSucc(BiTreeq){BiTreeInSucc(BiTreeq){//已知q是指向中序線索二叉樹上某個(gè)結(jié)點(diǎn)的指針，//本函數(shù)返回指向*q的后繼的指針。r=q->rchild;if(!r->rtag)while(!r->rtag)r=r->rchild;returnr;}//ISucc4.【嚴(yán)題集6.21②】畫出和下列二叉樹相應(yīng)的森林。六、算法設(shè)計(jì)題（前5題中任選2題，第6題必做，每題8分，共24分）1.【嚴(yán)題集6.42③】編寫遞歸算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。2.寫出求二叉樹深度的算法，先定義二叉樹的抽象數(shù)據(jù)類型。3．【嚴(yán)題集6.44④】編寫遞歸算法，求二叉樹中以元素值為x的結(jié)點(diǎn)為根的子樹的深度。4.【嚴(yán)題集6.47④】編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。5.【嚴(yán)題集6.49④】編寫算法判別給定二叉樹是否為完全二叉樹。6.【嚴(yán)題集6.26③】假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用0～7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。第7章圖自測(cè)卷姓名班級(jí)題號(hào)一二三四五總分題分1620241030100得分一、單選題（每題1分，共16分）（）1.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍。A．1/2B.1C.2D.4（）2.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。A．1/2B.1C.2D.4（）3.有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有條邊。A．14B.28C.56D.112（）4.有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有條邊。A．5B.6C.7D.8（）5.有8個(gè)結(jié)點(diǎn)的有向完全圖有條邊。A．14B.28C.56D.112（）6.用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用來(lái)實(shí)現(xiàn)算法的。A．棧B.隊(duì)列C.樹D.圖（）7.用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用來(lái)實(shí)現(xiàn)算法的。A．棧B.隊(duì)列C.樹D.圖（）8.已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）9.已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A．0243156B.0135642C.0423165D.0134256（）10.已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A．0243651B.0136425C.0423156D.0134256（）11.已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A．0243165B.0135642C.0123465D.0123456

（）12.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A．A．0132B.0231C.0321D.0123（）13.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是A．A．0321B.0123C.0132D.0312（）14.深度優(yōu)先遍歷類似于二叉樹的A．先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷（）15.廣度優(yōu)先遍歷類似于二叉樹的A．先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷（）16.任何一個(gè)無(wú)向連通圖的最小生成樹A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在二、填空題（每空1分，共20分）1.圖有、等存儲(chǔ)結(jié)構(gòu)，遍歷圖有、等方法。2.有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的。3.如果n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有棵生成樹。4.n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為。5.n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接表存儲(chǔ)，則空間復(fù)雜度為。6.設(shè)有一稀疏圖G，則G采用存儲(chǔ)較省空間。7.設(shè)有一稠密圖G，則G采用存儲(chǔ)較省空間。8.圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于圖。9.已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)的方法是。10.圖的深度優(yōu)先遍歷序列惟一的。11.n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為；若采用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間復(fù)雜度為。12.n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為；若采用鄰接表存儲(chǔ)，該算法的時(shí)間復(fù)雜度為。13.圖的BFS生成樹的樹高比DFS生成樹的樹高。14.用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹的時(shí)間復(fù)雜度為；用克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度是。15.若要求一個(gè)稀疏圖G的最小生成樹，最好用算法來(lái)求解。16.若要求一個(gè)稠密圖G的最小生成樹，最好用算法來(lái)求解。17.用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長(zhǎng)度的次序來(lái)得到最短路徑的。18.拓?fù)渑判蛩惴ㄊ峭ㄟ^(guò)重復(fù)選擇具有個(gè)前驅(qū)頂點(diǎn)的過(guò)程來(lái)完成的。三、簡(jiǎn)答題（每題6分，共24分）1.【嚴(yán)題集7.1①】已知如圖所示的有向圖，請(qǐng)給出該圖的:每個(gè)頂點(diǎn)的入/出度；鄰接矩陣；鄰接表；逆鄰接表。2.【嚴(yán)題集7.7②】請(qǐng)對(duì)下圖的無(wú)向帶權(quán)圖：寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。3.【嚴(yán)題集7.5②】已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。4.【嚴(yán)題集7.11②】試?yán)肈ijkstra算法求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過(guò)程中各步的狀態(tài)。四、給定下列網(wǎng)G:（10分）1試著找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu)圖；2用兩種不同的表示法畫出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖；3用C語(yǔ)言（或其他算法語(yǔ)言）定義其中一種表示法（存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。五、算法設(shè)計(jì)題（每題10分，共30分）1.【嚴(yán)題集7.14③】編寫算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表。解：StatusBuild_AdjList(ALGraph&G)//輸入有向圖的頂點(diǎn)數(shù),邊數(shù),頂點(diǎn)信息和邊的信息，以建立鄰接表{returnOK;}//Build_AdjList2.【嚴(yán)題集7.15③】試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。（如果要?jiǎng)h除所有從第i個(gè)頂點(diǎn)出發(fā)的邊呢？提示：將鄰接矩陣的第i行全部置0）解：//設(shè)本題中的圖G為有向無(wú)權(quán)圖StatusDeleteArc(MGraph&G,charv,charw)//在鄰接矩陣表示的圖G上刪除邊(v,w){}returnOK;}//Delete_Arc3.【嚴(yán)題集7.22③】試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑（i≠j）。附加題：【嚴(yán)題集7.27④】采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)判別無(wú)向圖中任意給定的兩個(gè)頂點(diǎn)之間是否存在一條長(zhǎng)度為k的簡(jiǎn)單路徑的算法。（注1：一條路徑為簡(jiǎn)單路徑指的是其頂點(diǎn)序列中不含有重現(xiàn)的頂點(diǎn)。注2：此題可參見嚴(yán)題集P207-208中有關(guān)按“路徑”遍歷的算法基本框架。）第8章查找自測(cè)卷姓名班級(jí)題號(hào)一二三四五總分題分1027162423100得分一、填空題（每空1分，共10分）1.在數(shù)據(jù)的存放無(wú)規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是。2.線性有序表（a1，a2，a3，…，a256）是從小到大排列的，對(duì)一個(gè)給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是。3.假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為；比較四次查找成功的結(jié)點(diǎn)數(shù)為；平均查找長(zhǎng)度為。4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素比較大小。5.在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是。6.散列法存儲(chǔ)的基本思想是由決定數(shù)據(jù)的存儲(chǔ)地址。7.有一個(gè)表長(zhǎng)為m的散列表，初始狀態(tài)為空，現(xiàn)將n（n<m）個(gè)不同的關(guān)鍵碼插入到散列表中，解決沖突的方法是用線性探測(cè)法。如果這n個(gè)關(guān)鍵碼的散列地址都相同，則探測(cè)的總次數(shù)是。二、單項(xiàng)選擇題（每小題1分，共27分）（）1．在表長(zhǎng)為ｎ的鏈表中進(jìn)行線性查找，它的平均查找長(zhǎng)度為Ａ.ＡＳＬ＝ｎ;Ｂ.ＡＳＬ＝（ｎ＋１）／２;Ｃ.ＡＳＬ＝＋１;Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中比較大小，查找結(jié)果是失敗。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50（）3．對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較次關(guān)鍵字。A．3B．4C．5D．6（）4.鏈表適用于查找A．順序B．二分法C．順序，也能二分法D．隨機(jī)（）5.折半搜索與二叉搜索樹的時(shí)間性能A.相同B.完全不同C.有時(shí)不相同D.數(shù)量級(jí)都是O（log2n）6．要進(jìn)行線性查找，則線性表A；要進(jìn)行二分查找，則線性表B；要進(jìn)行散列查找，則線性表C。某順序存儲(chǔ)的表格，其中有90000個(gè)元素，已按關(guān)鍵項(xiàng)的值的上升順序排列?，F(xiàn)假定對(duì)各個(gè)元素進(jìn)行查找的概率是相同的，并且各個(gè)元素的關(guān)鍵項(xiàng)的值皆不相同。當(dāng)用順序查找法查找時(shí)，平均比較次數(shù)約為D，最大比較次數(shù)為E。供選擇的答案：A~C：①必須以順序方式存儲(chǔ)②必須以鏈表方式存儲(chǔ)③必須以散列方式存儲(chǔ)④既可以以順序方式，也可以以鏈表方式存儲(chǔ)⑤必須以順序方式存儲(chǔ)且數(shù)據(jù)元素已按值遞增或遞減的次序排好⑥必須以鏈表方式存儲(chǔ)且數(shù)據(jù)元素已按值遞增或遞減的次序排好D，E：①25000②30000③45000④90000答案：A=B=C=D＝E＝7.數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。鏈表是一種A，它對(duì)于數(shù)據(jù)元素的插入和刪除B。通常查找線性表數(shù)據(jù)元素的方法有C和D兩種方法，其中C是一種只適合于順序存儲(chǔ)結(jié)構(gòu)但E的方法；而D是一種對(duì)順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)均適用的方法。供選擇的答案：A：①順序存儲(chǔ)線性表②非順序存儲(chǔ)非線性表 ③順序存儲(chǔ)非線性表 ④非順序存儲(chǔ)線性表B： ①不需要移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針②不需要移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針 ③只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 ④既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針C：①順序查找②循環(huán)查找 ③條件查找 ④二分法查找D：①順序查找②隨機(jī)查找 ③二分法查找 ④分塊查找E：①效率較低的線性查找②效率較低的非線性查找 ③效率較高的非線性查找④效率較高的線性查