《數(shù)據(jù)結(jié)構(gòu)》題庫章節(jié)練習(xí)題

《數(shù)據(jù)結(jié)構(gòu)》題庫章節(jié)練習(xí)題-第1章緒論////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、選擇題算法的時間復(fù)雜度取決于（）A．問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B計算機(jī)算法指的是（1），它必須具備（2）這三個特性。(1)A．計算方法B.排序方法C.解決問題的步驟序列D.調(diào)度方法(2)A．可執(zhí)行性、可移植性、可擴(kuò)充性B.可執(zhí)行性、確定性、有窮性C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性一個算法應(yīng)該是（）。A．程序B．問題求解步驟的描述C．要滿足五個基本特性D．A和C.4、以下的算法時間復(fù)雜度中，算法速度最快的是（）。A.O(N)B.O(Nlog2N)C.O(N2)D.O(2N)下面說法錯誤的是（）(1）算法原地工作的含義是指不需要任何額外的輔助空間（2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O(2n)的算法（3）所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界（4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。A．動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C．線性結(jié)構(gòu)、非線性結(jié)構(gòu)D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)8、如下程序算法的時間復(fù)雜度是（）。voidlink(intarr[N]){inti,j,k;for(i=0;i<N-1;i++)for(j=i+1;j<N;j++)if(arr[i]>arr[j]){k=arr[i];arr[i]=arr[j];arr[j]=k;}}A.O(N) B.O(N2) C.O(log2N) D.O(2N)以下數(shù)據(jù)結(jié)構(gòu)中，（

）是非線性數(shù)據(jù)結(jié)構(gòu)。

A．樹

B．字符串

C．隊

D．棧

連續(xù)存儲設(shè)計時，存儲單元的地址（

）。A．一定連續(xù)

B．一定不連續(xù)

C．不一定連續(xù)

D．部分連續(xù)，部分不連續(xù)二、填空題1、數(shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素的表示和數(shù)據(jù)元素間關(guān)系的表示。2、根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般可以構(gòu)造出四種邏輯結(jié)構(gòu)分別是：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀或網(wǎng)狀結(jié)構(gòu)。3、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”。4、一個數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中表示（又稱映像）稱為存儲結(jié)構(gòu)。5、如果一個算法的時間復(fù)雜度是(N3+4N2log2N+3N)/N，那么用數(shù)量級表示的時間復(fù)雜度應(yīng)該是O(N2)。6、抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性_，而與在計算機(jī)內(nèi)部如何表示和實現(xiàn)無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部使用。7、數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是算法的時間復(fù)雜度和空間復(fù)雜度。8、算法設(shè)計應(yīng)考慮4種質(zhì)量要求：正確性、可讀性、健壯性、高效率與低存儲量要求。9、數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)_，以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的操作（運算），設(shè)計出相應(yīng)的算法_。10、一個算法具有5個重要特性：有窮性、確定性、可行性、輸入、輸出。11、請分析如下程序代碼的時間復(fù)雜度，填寫其中的空格：

voiddeleteAll(intarray[],intN,inttarget)

{inti=0;while(i<N){if(array[i]!=target)i++;else{intj;for(j=i+1;j<N;j++){array[j-1]=array[j];}N--;}}

}函數(shù)deleteAll之中，作為關(guān)鍵操作的一個語句是：_array[j-1]=array[j]__函數(shù)deleteAll的算法時間復(fù)雜度是：___O(N2)___12、計算機(jī)執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為__(n+3)(n-2)/2_____。for(i=l；i<n-l；i++)for(j=n;j>=i;j--)s;13、下面程序段的時間復(fù)雜度為___O(n)_____。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;14、在有n個選手參加的單循環(huán)賽中，總共將進(jìn)行__n(n-1)/2__場比賽。15、將數(shù)據(jù)結(jié)構(gòu)可定義為一個二元組（D，R），其中D表示的是數(shù)據(jù)元素的有限集合，則S表示的是D上數(shù)據(jù)元素之間關(guān)系的有限集合。16、抽象數(shù)據(jù)類型的定義包括數(shù)據(jù)對象的定義、數(shù)據(jù)關(guān)系的定義和基本操作的定義。17、數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有時一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。三、簡答題1、數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科？數(shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計算的程序設(shè)計問題中，計算機(jī)的操作對象及對象間的關(guān)系和施加于對象的操作等的學(xué)科。2、順序存儲方式和鏈?zhǔn)酱鎯Ψ绞礁饔惺裁刺攸c？（1）順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作（如插入、刪除）效率較差。（2）鏈?zhǔn)酱鎯Ψ绞?。每個存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組（至少一個）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。3、數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？數(shù)據(jù)類型是程序設(shè)計語言中的一個概念，它是一個值的集合和操作的集合。如C語言中的整型、實型、字符型等。整型值的范圍（對具體機(jī)器都應(yīng)有整數(shù)范圍），其操作有加、減、乘、除、求余等。實際上數(shù)據(jù)類型是廠家提供給用戶的已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。“抽象數(shù)據(jù)類型（ADT）”指一個數(shù)學(xué)模型及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義包括：數(shù)據(jù)對象的定義、數(shù)據(jù)關(guān)系的定義和基本操作的定義。“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計算機(jī)內(nèi)部如何表示和實現(xiàn)無關(guān)。無論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不再局限于機(jī)器已定義和實現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計軟件系統(tǒng)時自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實現(xiàn)三部分，封裝在一起，對用戶透明（提供接口），而不必了解實現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計不再是“藝術(shù)”，而是向“科學(xué)”邁進(jìn)了一步。4、在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算之間存在著怎樣的關(guān)系？數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”），數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作，運算是定義在邏輯結(jié)構(gòu)上的，和存儲結(jié)構(gòu)無關(guān)，而運算的實現(xiàn)則是依賴于存儲結(jié)構(gòu)。5、若邏輯結(jié)構(gòu)相同但存儲結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對嗎？舉例說明之。邏輯結(jié)構(gòu)相同但存儲不同，可以是不同的數(shù)據(jù)結(jié)構(gòu)。例如，線性表的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，采用順序存儲結(jié)構(gòu)為順序表，而采用鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。6、在給定的邏輯結(jié)構(gòu)及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù)據(jù)結(jié)構(gòu)。這樣說法對嗎？舉例說明之。棧和隊列的邏輯結(jié)構(gòu)相同，其存儲表示也可相同（順序存儲和鏈?zhǔn)酱鎯Γ?，但由于其運算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。7、評價各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？數(shù)據(jù)結(jié)構(gòu)的評價非常復(fù)雜，可以考慮兩個方面，一是所選數(shù)據(jù)結(jié)構(gòu)是否準(zhǔn)確、完整的刻劃了問題的基本特征；二是是否容易實現(xiàn)（如對數(shù)據(jù)分解是否恰當(dāng)；邏輯結(jié)構(gòu)的選擇是否適合于運算的功能，是否有利于運算的實現(xiàn)；基本運算的選擇是否恰當(dāng)。）8、評價一個好的算法，您是從哪幾方面來考慮的？評價好的算法有四個方面。一是算法的正確性；二是算法的可讀性；三是算法的健壯性；四是算法的時空效率（高效率與低存儲量需求）。9、解釋：算法、算法的時間復(fù)雜度、頻度（1）算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有五個重要特性：有窮性、確定性、可行性、輸入和輸出。（2）算法的時間復(fù)雜度是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)?；騿栴}的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其它參數(shù)。有時考慮算法在最壞情況下的時間復(fù)雜度或平均時間復(fù)雜度。（3）在分析算法時間復(fù)雜度時，有時需要估算基本操作的原操作，它是執(zhí)行次數(shù)最多的一個操作，該操作重復(fù)執(zhí)行的次數(shù)稱為頻度。10、當(dāng)你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時，應(yīng)從哪些方面考慮？通?？紤]算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面：程序運行時所需輸入的數(shù)據(jù)總量，對源程序進(jìn)行編譯所需時間，計算機(jī)執(zhí)行每條指令所需時間和程序中指令重復(fù)執(zhí)行的次數(shù)。11、數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義，一是作為一門課程的名稱；二是作為一個科學(xué)的概念。作為科學(xué)概念，目前尚無公認(rèn)定義，一般認(rèn)為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個方面：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)，（2）數(shù)據(jù)的存儲結(jié)構(gòu)，（3）對數(shù)據(jù)進(jìn)行的操作（運算）。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。12、在編制管理通訊錄的程序時,什么樣的數(shù)據(jù)結(jié)構(gòu)合適?為什么?應(yīng)從兩方面進(jìn)行討論：如通訊錄較少變動（如城市私人電話號碼），主要用于查詢，以順序存儲較方便，既能順序查找也可隨機(jī)查找；若通訊錄經(jīng)常有增刪操作，用鏈?zhǔn)酱鎯Y(jié)構(gòu)較為合適，將每個人的情況作為一個元素（即一個結(jié)點存放一個人），設(shè)姓名作關(guān)鍵字，鏈表安排成有序表，這樣可提高查詢速度。13、算法的時間復(fù)雜度、算法的空間復(fù)雜度如何計算和表示？答案:（略）（請大家認(rèn)真看和分析教材P14-P17的內(nèi)容?。┧摹⑺惴ǚ治鲱}調(diào)用下列C函數(shù)f(n)回答下列問題:（1）試指出f(n)值的大小，并寫出f(n)值的推導(dǎo)過程;（2）假定n=5，試指出f(5)值的大小和執(zhí)行f(5)時的輸出結(jié)果。C函數(shù)：intf(intn){inti,j，k,sum=0;for(i=l;i<n+1;i++){for(j=n;j>i-1;j--)for(k=1;k<j+1;k++)sum++;printf("sum=%d\n",sum)；}return(sum);}參考答案：第一層for循環(huán)判斷n+1次，往下執(zhí)行n次，第二層for執(zhí)行次數(shù)為(n+(n-1)+(n-2)+?+1)，第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如下表：執(zhí)行次數(shù)為(1+2+。。。+n)+(2+3+。。。+n)+。。。+n=n*n(n+1)/2-n(n2-1)/6。在n=5時，f(5)=55，執(zhí)行過程中，輸出結(jié)果為：sum=15sum=29sum=41sum=50sum=55《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)題及參考答案-第2章線性表////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、選擇題1、下面關(guān)于線性表的敘述中，錯誤的是哪一個？（）A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B．線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。2、線性表是具有n個（）的有限序列（n>0）。A．表元素B．字符C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項E．信息項3、若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。A．順序表B．雙鏈表C．帶頭結(jié)點的雙循環(huán)鏈表D．單循環(huán)鏈表4、設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用()最節(jié)省時間。A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結(jié)點的雙循環(huán)鏈表5、長度為N的線性表，如果是順序存儲，則訪問、刪除某個結(jié)點的時間復(fù)雜度分別是（）和（）。A.O(N),O(1)B.O(N),O(1)C.O(1),O(1)D.O(1),O(N)6、鏈表不具有的特點是（）A．插入、刪除不需要移動元素B．可隨機(jī)訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正比7、長度為N的線性表，如果是鏈?zhǔn)酱鎯?，則訪問、刪除某個結(jié)點的時間復(fù)雜度分別是（）和（）。A.O(1),O(N)B.O(N),O(1)C.O(N),O(1)D.O(N),O(1)8、若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（）(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)9、對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)10、線性表（a1,a2,…,an）以鏈接方式存儲時，訪問第i位置元素的時間復(fù)雜性為（）A．O（i）B．O（1）C．O（n）D．O（i-1）11、在雙向鏈表指針p的結(jié)點前插入一個指針q的結(jié)點操作是（）。A.p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；B.p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C.q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;12、在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是：（）。A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;13、對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是（）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL二、填空題1、O(n)O(1)2、當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用___順序____存儲結(jié)構(gòu)。在長度為N的線性表中插入一個結(jié)點，對于順序存儲和鏈?zhǔn)酱鎯Φ木€性表，其插入操作的時間復(fù)雜度分別是O(N)和O(1)。3、線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是_____（n-1）/2___。在已有n個結(jié)點順序存儲的線性表中，插入一個新結(jié)點平均需要移動數(shù)據(jù)n/2次。4、設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點,若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行以下語句:py->next=px->next;px->next=py；5、在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向后移動___n-i+1___個元素。6、對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點*p后插入一個新結(jié)點的時間復(fù)雜度為___O(1)_____,在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為____O(n)____。7、根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成___單鏈表_____和___多重鏈表____；而又根據(jù)指針的連接方式，鏈表又可分成__（動態(tài)）鏈表______和___靜態(tài)鏈表_____。8、順序存儲結(jié)構(gòu)是通過___物理上相鄰_____表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過____指針____表示元素之間的關(guān)系的。9、一個順序存儲的線性表，第1、第2個元素的存儲地址分別是16進(jìn)制的16A、17A，那么第10個元素的存儲地址是16進(jìn)制的1FA。10、對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共___4___個，單鏈表為____2___個。11、循環(huán)單鏈表的最大優(yōu)點是：___從任一結(jié)點出發(fā)都可訪問到鏈表中每一個元素。_____。12、在單鏈表L中，指針p所指結(jié)點有后繼結(jié)點的條件是：__p->next!=NULL13、線性表的存儲結(jié)構(gòu)分為__順序存儲結(jié)構(gòu)____和__鏈?zhǔn)酱鎯Y(jié)構(gòu)____。14、采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，它根據(jù)實際需要申請內(nèi)存空間，而當(dāng)不需要時又可將不用結(jié)點空間返還給系統(tǒng)。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中插入和刪除操作不需要移動元素。15、設(shè)單鏈表結(jié)點指針域為next，則刪除鏈表中指針p所指結(jié)點的直接后繼的的操作是：q=p->next;p->next=q->next;free(q);16、設(shè)單鏈表的頭結(jié)點的頭指針為head,且pre=head，單鏈表中某指針p所指結(jié)點（即p結(jié)點）的數(shù)據(jù)域為data，鏈指針域為next，則在p結(jié)點之前插入s結(jié)點的操作是：while(pre->next!=p)pre=pre->next;s->next=p;pre->next=s;17、在單鏈表p結(jié)點之后插入s結(jié)點的操作是：s->next=p->next;p->next=s;三、簡答題1、已知順序表La和Lb中數(shù)據(jù)元素按值非遞減有序排列，歸并La和Lb得到新的順序表Lc，使Lc中的數(shù)據(jù)元素也按值非遞減有序排列-這種操作稱為順序表的歸并操作。請閱讀下列順序表的歸并操作算法代碼，分析該算法的時間復(fù)雜度，并作簡要解釋。voidMergeList(SqListLa,SqListLb,SqList&Lc){pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);//存儲分配失敗pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last){if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;//將La的剩余元素插入while(pb<=pb_last)*pc++=*pb++;//將Lb的剩余元素插入}參考答案：上述算法將歸并后的數(shù)據(jù)元素存放在新的順序表Lc中，順序表La和Lb不用變化，只是把順序表La和Lb中的數(shù)據(jù)元素一個個新插入到順序表Lc的末尾，最多有La.length+Lb.length個數(shù)據(jù)元素要插入到順序表Lc中，所以該算法的時間復(fù)雜度是O(La.length+Lb.length)。2、已知順序表La和Lb，現(xiàn)在將存在于順序表Lb中而不存在于順序表La中的數(shù)據(jù)元素插入到順序表La中去（如果發(fā)現(xiàn)順序表La的空間不夠，則需要擴(kuò)大順序表La）。具體做法是從順序表Lb中依次取得每個數(shù)據(jù)元素，并依值在順序表La中進(jìn)行查訪，若不存在，則插入之-這種操作稱為順序表的合并操作。請閱讀下列順序表的合并操作算法代碼，分析該算法的時間復(fù)雜度，并作簡要解釋。voidunion(List&La,ListLb){ElemTypee;intLa_len,Lb_len,i;La_len=ListLength(La);//求順序表的長度Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//依次取Lb中第i個數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal)//依值e在順序表La中進(jìn)行查訪ListInsert(La,++La_len,e);//La中不存在和e相同的數(shù)據(jù)元素，則在La的最后面插入}}參考答案：在順序表La中查訪是否存在和Lb中第i個數(shù)據(jù)元素（值為e）相同的數(shù)據(jù)元素的方法是:令e和La中的數(shù)據(jù)元素逐個比較。若La中存在和e相同的數(shù)據(jù)元素ai，則比較次數(shù)為i(1≤i≤La.length),否則為La.length，即算法LocateElem的時間復(fù)雜度為O(La.length)。而最多有Lb.length個數(shù)據(jù)元素要插入到順序表La中，由此，算法union的時間復(fù)雜度為:O(La.length×Lb.length)。3、線性表的順序存儲結(jié)構(gòu)具有三個弱點：其一，在作插入或刪除操作時，需移動大量元素；其二，由于難以估計，必須預(yù)先分配較大的空間，往往使存儲空間不能得到充分利用；其三，表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是否一定都能夠克服上述三個弱點，試討論之。參考答案：鏈?zhǔn)酱鎯Y(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個弱點。首先，插入、刪除不需移動元素，只修改指針，時間復(fù)雜度為O(1)；其次，不需要預(yù)先分配空間，可根據(jù)需要動態(tài)申請空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點是因為指針增加了空間開銷，當(dāng)空間不允許時，就不能克服順序存儲的缺點。4、對于單向鏈表、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表，在鏈表中或者鏈表的尾部插入或刪除元素的操作各有什么特點，相應(yīng)算法的時間復(fù)雜度各是怎樣的情況？參考答案:（略）（請大家認(rèn)真看和分析教材的相關(guān)內(nèi)容?。?、靜態(tài)鏈表是一種鏈?zhǔn)酱鎯Φ木€性表。靜態(tài)單鏈表是用一維數(shù)組來存儲線性鏈表的結(jié)點數(shù)據(jù)，并且用一維數(shù)組的下標(biāo)表示指針。已知一個靜態(tài)單鏈表SLinkList定義如下：#defineMAXSIZE200//靜態(tài)鏈表的最大長度typedefstruct{DataTypedata;//數(shù)據(jù)域intnext;//指針域}NodeType;//靜態(tài)單鏈表的結(jié)點類型NodeTypeSLinkList[MAXSIZE];//靜態(tài)單鏈表SLinkList，頭結(jié)點是SLinkList[0]上述靜態(tài)單鏈表的結(jié)點中的指針域next保存的是靜態(tài)單鏈表SLinkList的下標(biāo)值。請寫出插入結(jié)點、刪除結(jié)點的算法所對應(yīng)的函數(shù)的定義。參考答案:（略）（請大家認(rèn)真看和分析教材P31-P34相關(guān)內(nèi)容，并寫出相應(yīng)的函數(shù)以實現(xiàn)靜態(tài)單鏈表的插入、刪除結(jié)點的操作?。┳⒁猓滩闹?，SLinkList是被定義為一個一維數(shù)組類型，本題SLinkList則是一維數(shù)組名。四、算法分析題linklist_NULLq=p2、下面的結(jié)構(gòu)體定義了雙向鏈表的節(jié)點結(jié)構(gòu)。請分析如下程序代碼，填寫其中缺少的語句代碼：typedefstructnode{intdata；structnode*last;structnode*next;}Node;voiddeleteOne(Node*head,inttarget){Node*p=headnext;while(p!=NULL){if(pdata!=target)____p=pnext_____;else{if(pnext!=NULL)pnextlast=____plast_____;plastnext__=pnext;free(p);}}}3、說明在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針與頭結(jié)點之間的根本區(qū)別；頭結(jié)點與首結(jié)點的關(guān)系。參考答案：在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點則是鏈表的頭結(jié)點的指針，頭指針具有標(biāo)識作用，故常用頭指針冠以鏈表的名字。頭結(jié)點是為了使插入和刪除等操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點之前，其數(shù)據(jù)域一般無意義（當(dāng)然有些情況下也可存放鏈表的長度、用做監(jiān)視哨等等），有頭結(jié)點后，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與對其它結(jié)點的操作統(tǒng)一了。首結(jié)點也就是第一元素結(jié)點，它是頭結(jié)點后邊的第一個結(jié)點。五、算法描述題設(shè)有一帶頭結(jié)點的單鏈表,編程將鏈表顛倒過來。要求不用另外的數(shù)組或結(jié)點完成。參考答案：要實現(xiàn)帶頭結(jié)點的單鏈表的逆置，通常作法是：將工作指針指向第一個元素結(jié)點，將頭結(jié)點的指針域置空。然后將鏈表各結(jié)點從第一結(jié)點開始直至最后一個結(jié)點，依次前插至頭結(jié)點后，使最后插入的結(jié)點成為鏈表的第一結(jié)點，第一個插入的結(jié)點成為鏈表的最后結(jié)點。typedefstructnode{intdata；∥假定結(jié)點數(shù)據(jù)域為整型。structnode*next；}node,*LinkedList；LinkedListcreat（）{LinkedListhead，pintx；head=（LinkedList）malloc（sizeof（node））；head->next=null；/*設(shè)置頭結(jié)點*/scanf（“%d”，&x）；while（x!=9999）/*約定輸入9999時退出本函數(shù)*/{p=（LinkedList）malloc（sizeof（node））；p->data=x；p->next=head->next；/*將新結(jié)點鏈入鏈表*/head->next=p；scanf（“%d”，&x）；}return（head）；}∥結(jié)束creat函數(shù)。LinkedListinvert1（LinkedListhead）/*逆置單鏈表*/{LinkedListp=head->next;/*p為工作指針*/head->next=null；while（p!=null）{r=p->next；/*暫存p的后繼*/p->next=head->next；head->next=p；p=r；}return（head）；}/*結(jié)束invert1函數(shù)*/voidmain（）{LinkedListla；la=creat(）；/*生成單鏈表*/la=invert1（la）；/*逆置單鏈表*/}《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)題及參考答案-第3章棧和隊列////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、選擇題對于棧，操作數(shù)據(jù)的原則是（）。A.先進(jìn)先出B.后進(jìn)先出C.后進(jìn)后出D.不分順序2、要求數(shù)據(jù)遵循FIFO（先進(jìn)先出）原則的數(shù)據(jù)結(jié)構(gòu)是（）。A.線性表 B.鏈表 C.隊列 D.棧3、若進(jìn)棧的序列為1,2,3,4，則以下哪一個不可能是一個出棧序列。A.3,2,4,1 B.3,2,1,4 C.4,2,3,1 D.1,3,2,4有六個元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪一個不是合法的出棧序列？（）A.543612B.453126C.346521D.234156設(shè)棧的輸入序列是1，2，3，4,則（）不可能是其出棧序列。A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，一個棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（）。A.23415B.54132C.23145D.154328、數(shù)字1、2依次入棧，則出棧的順序可能有（）種情況；數(shù)字1、2依次進(jìn)入隊列，則出隊列的順序可能有（）種情況。A.1,2B.2,1C.2,2D.1,1設(shè)一個棧的輸入序列是1，2，3，4，5，則下列序列中，是棧的合法輸出序列的是（）。A.51234B.45132C.43125D.32154某堆棧的輸入序列為a,b，c，d,下面的四個序列中，不可能是它的輸出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b設(shè)有三個元素X，Y，Z順序進(jìn)棧（進(jìn)的過程中允許出棧），下列得不到的出棧排列是()。A．XYZB.YZXC.ZXYD.ZYX一個遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分14、如下四個選項中，那個選項是能夠正確判斷循環(huán)隊列是否排滿元素的操作（其中MAXQSIZE表示隊列的容量）（）：A．if(Q.rear==Q.front)… B．if(Q.rear==(Q.front+MAXQSIZE))C．if(Q.rear==(Q.front+1)%MAXQSIZE)D．if(Q.front==(Q.rear+1)%MAXQSIZE)假設(shè)以數(shù)組A[m]存放循環(huán)隊列的元素，其頭尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)為（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？()A.1和5B.2和4C.4和2D.5和117、利用棧進(jìn)行十進(jìn)制數(shù)1348轉(zhuǎn)換成八進(jìn)制數(shù)，則入棧的數(shù)依次是（）。A.1,3,4,8B.8,4,3,1C.2,5,0,4D.4,0,5,2最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front棧和隊列的共同點是（）。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點處插入和刪除元素D.沒有共同點二、填空題棧是___操作受限（或限定僅在表尾進(jìn)行插入和刪除操作）的線性表，其運算遵循___后進(jìn)先出____的原則。，其特點是__先進(jìn)先出__。用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為___S×SS×S××__。表達(dá)式求值是___棧____應(yīng)用的一個典型例子。5、棧和隊列在本質(zhì)上都是同一種基本數(shù)據(jù)結(jié)構(gòu)的特例，這種基本的數(shù)據(jù)結(jié)構(gòu)就是線性表。在作進(jìn)棧運算時，應(yīng)先判別棧是否.滿，在作退棧運算時應(yīng)先判別棧是否空。當(dāng)棧中元素為n個，作進(jìn)棧運算時發(fā)生上溢，則說明該棧的最大容量為n。三、簡答題1、簡要敘述循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)，分析循環(huán)隊列的隊頭指針和隊尾指針與循環(huán)隊列元素之間的關(guān)系，寫出InitQueue()、QueueLength()、EnQueue()、DeQueue()等循環(huán)隊列的基本操作算法，并舉例說明循環(huán)隊列的操作函數(shù)的應(yīng)用。參考答案：（1）隊列：是一種先進(jìn)先出(firstinfirstout，簡稱FIFO表)的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除元素。在隊列中，允許插入的一端叫做隊尾(rear)，允許刪除的一端稱為隊頭(front)。假設(shè)隊列為q=（a1,a2,…an），則a1為隊頭元素，an為隊尾元素。隊列的順序存儲結(jié)構(gòu)稱為順序隊列。順序隊列用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素。由于隊列的隊頭和隊尾的位置是變化的，因而需要附設(shè)兩個指針front和rear以指示隊頭和隊尾元素在隊列中的位置。在C語言中為了方便描述，約定：初始化創(chuàng)建空隊列時，令front=rear=0(頭尾指針相等)。每當(dāng)插入新的隊尾元素時，rear指針增1。每當(dāng)刪除隊頭元素時，front指針增1。因此，在非空隊列中，頭指針front始終指向隊頭元素，而尾指針rear始終指向隊尾元素的下一位置。循環(huán)隊列：用順序存儲結(jié)構(gòu)的一維數(shù)組表示隊列，由于隊列的性質(zhì)（隊尾插入和隊頭刪除），容易造成“假溢出”現(xiàn)象，即:隊尾已到達(dá)一維數(shù)組的高下標(biāo)，不能再插入，然而隊中元素個數(shù)小于隊列的長度（容量）。為了解決循環(huán)隊列上述“假溢出”現(xiàn)象，可采用犧牲一個存儲單元（即少用了隊列的一個元素空間）的方法解決“隊滿”和“隊空”的判定問題，并規(guī)定:隊空時：front==rear；隊滿時：(rear+1)%MAXQSIZE==front。循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)#defineMAXQSIZE100//最大隊列長度typedefstruct{QElemType*base;//指向初始化的動態(tài)分配存儲空間intfront;//頭指針,若隊列不空，指向隊列頭元素intrear;//尾指針,若隊列不空，指向隊列尾元素的下一個位置}SqQueue;（2）循環(huán)隊列的隊頭指針和隊尾指針與循環(huán)隊列元素之間的關(guān)系見如下示意圖：循環(huán)隊列為了克服“假溢出”現(xiàn)象，少用了隊列的一個元素空間。在循環(huán)隊列中，指針和隊列元素之間的關(guān)系不變。每當(dāng)插入新的隊尾元素時，rear指針增1。每當(dāng)刪除隊頭元素時，front指針增1。并規(guī)定:隊空時：front==rear；隊滿時：(rear+1)%MAXQSIZE==front。（3）基本操作的算法描述StatusInitQueue(SqQueue&Q){//構(gòu)造一個空隊列QQ.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存儲分配失敗Q.front=Q.rear=0;returnOK;}intQueueLength(SqQueueQ){//返回隊列Q的元素個數(shù)，即隊列的長度return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}StatusEnQueue(SqQueue&Q,ElemTypee){//插入元素e為Q的新的隊尾元素if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//隊列滿Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}StatusDeQueue(SqQueue&Q,ElemType&e){//若隊列不空，則刪除Q的隊頭元素，//用e返回其值，并返回OK;否則返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}注意:上述函數(shù)代碼要很好掌握?。?）循環(huán)隊列的操作函數(shù)的應(yīng)用舉例（略）注意:上述操作要很好理解和掌握,能靈活應(yīng)用！2、若元素的進(jìn)棧序列為：A、B、C、D、E，運用棧操作，能否得到出棧序列B、C、A、E、D和D、B、A、C、E？為什么？答案：能得到出棧序列B、C、A、E、D，不能得到出棧序列D、B、A、C、E。其理由為：若出棧序列以D開頭，說明在D之前的入棧元素是A、B和C，三個元素中C是棧頂元素，B和A不可能早于C出棧，故不可能得到D、B、A、C、E出棧序列。3、有字符串次序為3*-y-a/y^2,利用棧，給出將次序改為3y-*ay2^/-的操作步驟。（可用X代表掃描該字符串過程中順序取一個字符進(jìn)棧的操作，用S代表從棧中取出一個字符加入到新字符串尾的出棧操作。例如，ABC變?yōu)锽CA的操作步驟為XXSXSS。答案：XSXXXSSSXXSXXSXXSSSS四、算法分析1、簡要敘述順序棧的數(shù)據(jù)結(jié)構(gòu)，分析順序棧的棧頂指針和棧底指針與順序棧元素之間的關(guān)系，寫出Push(&S,e)，Pop(&S,&e)，StackEmpty(S)，GetTop(S,&e)，InitStack(&S)等順序棧的基本操作算法，并舉例說明順序棧的操作函數(shù)的應(yīng)用。參考答案：（1）順序棧：用一片地址連續(xù)的存儲空間來存儲棧的元素。順序棧的數(shù)據(jù)結(jié)構(gòu)#defineSTACK_INIT_SIZE100//存儲空間初始分配量#defineSTACKINCREMENT10//存儲空間分配增量typedefstruct{SElemType*base;//棧底指針SElemType*top;//棧頂指針inttacksize;//當(dāng)前分配量,以元素為單位}SqStack;規(guī)定top永遠(yuǎn)指向下一次要插入的位置，非空棧中，top棧頂指針始終指在棧頂元素的下一個位置上。（2）順序棧的棧頂指針和棧底指針與順序棧元素之間的關(guān)系見如下示意圖：首先說明：當(dāng)base=NULL時，說明棧不存在。如圖所示，?？諘r：base=top，此時,棧頂指針top，棧底指針base都指向棧底；每當(dāng)插入新元素，指針top加1，刪除棧頂元素時，指針top減1。棧的長度：top-base的值。（3）基本操作的算法描述StatusInitStack(SqStack&S){//構(gòu)造一個空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZEsizeof(SElemType));if(!S.base)exit(OVERFLOW);//存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusGetTop(SqStackS,SElemType&e){//若棧不空，則用e返回S的棧頂元素，并//返回OK，否則返回ERRORif(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}StatusPush(SqStack&S,SElemTypee){//插入元素e為新的棧頂元素if(S.top-S.base>=S.stacksize)//當(dāng)前存儲空間已滿，增加分配{S.base=(SElemType*)realloc(S.base，(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存儲分配失敗S.top=S.base+S.stacksize;//top指針位置S.stacksize+=STACKINCREMENT//存儲容量增加}*S.top++=e;returnOK;}StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，并用e返回其值，并返回OK，否則返回//ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}StatusDestroyStack(SqStack*S){/*銷毀棧S，S不再存在*/free((*S).base);(*S).base=NULL;(*S).top=NULL;(*S).stacksize=0;returnOK;}StatusClearStack(SqStack*S){/*把S置為空棧*/(*S).top=(*S).base;returnOK;}StatusStackEmpty(SqStackS){/*若棧S為空棧，則返回TRUE，否則返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;}intStackLength(SqStackS){/*返回S的元素個數(shù)，即棧的長度*/returnS.top-S.base;}注意:上述函數(shù)代碼要很好掌握?。?）順序棧的操作函數(shù)的應(yīng)用舉例（略）注意:上述操作要很好理解和掌握,能靈活應(yīng)用！2、一個棧的輸入序列為123，則棧的輸出序列有哪幾種？答案：共有以下5種情況：1進(jìn)棧,1出棧,2進(jìn)棧,2出棧,3進(jìn)棧,3出棧,棧的輸出序列是1231進(jìn)棧,2進(jìn)棧,2出棧,1出棧,3進(jìn)棧,3出棧,棧的輸出序列是2131進(jìn)棧,2進(jìn)棧,2出棧,3進(jìn)棧,3出棧,1出棧,棧的輸出序列是2311進(jìn)棧,2進(jìn)棧,3進(jìn)棧,3出棧,2出棧,1出棧,棧的輸出序列是3211進(jìn)棧,1出棧,2進(jìn)棧,3進(jìn)棧,3出棧,2出棧,棧的輸出序列是132五、算法描述題編寫一個算法，利用棧的基本運算將指定棧中的內(nèi)容進(jìn)行逆轉(zhuǎn)?！舅惴ǚ治觥坷脙蓚€臨時棧s1和s2。先將s棧中的內(nèi)容移到s1棧中，再將s1棧中的內(nèi)容移到s2棧中，最后將s2棧中的內(nèi)容移到s棧中，即可實現(xiàn)?！舅惴ㄔ创a】reverse(SqStack*s){SqStack*s1,*s2;

/*s,s1,s2均為棧類型

ElemTypex;

/*棧中元素的類型，用于存儲從棧中取出元素的臨時變量*/

initstack(s1);/*棧的初始化*/

initstack(s2);while(!stackempty(s))

/*如果棧不空，將s棧中的內(nèi)容移到s1棧中*/

{pop(s,x);

/*取棧頂元素放入變量x中*/

push(s1,x);

/*將變量x入棧*/

}

while(!stackempty(s1))/*如果棧不空，將s1棧中的內(nèi)容移到s2棧中*/

{pop(s1,x);

push(s2,x);

}

while(!stackempty(s2))/*如果棧不空，將s2棧中的內(nèi)容移到s棧中*/

{pop(s2,x);

push(s,x);

}}《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)題及參考答案-第6章樹和二叉樹////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、選擇題1、在二叉樹的第I層(I≥1)上最多含有結(jié)點數(shù)為（）A.2IB.2I-1-1C.2I-1D.2I-12、深度為6的二叉樹最多有()個結(jié)點A．64B.63C.32D.313、一棵樹高為K的完全二叉樹至少有()個結(jié)點A.2k–1B.2k-1–1C.2k-1D.2k4、有關(guān)二叉樹下列說法正確的是（）A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個結(jié)點的度為2D.二叉樹中任何一個結(jié)點的度都為25、n個結(jié)點的線索二叉樹上含有的線索數(shù)為（）A.2nB.n－lC.n＋lD.n6、線性表和樹的結(jié)構(gòu)區(qū)別在于（）A．前驅(qū)數(shù)量不同，后繼數(shù)量相同 B．前驅(qū)數(shù)量相同，后繼數(shù)量不同C．前驅(qū)和后繼的數(shù)量都相同 D．前驅(qū)和后繼的數(shù)量都不同7、已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，則其前綴形式為()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE8、設(shè)有一表示算術(shù)表達(dá)式的二叉樹（見下圖），EEFDGAB/++*-C*它所表示的算術(shù)表達(dá)式是（）A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C.(A*B+C)/(D*E+（F-G）)D.A*B+C/D*E+F-G9、一棵具有n個結(jié)點的完全二叉樹的樹高度（深度）(符號表示取不大于x的最大整數(shù))是（）A.B.C.D.10、利用二叉鏈表存儲樹，則根結(jié)點的右指針是（）。A．指向最左孩子B．指向最右孩子C．空D．非空11、已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷的結(jié)果為（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定12、某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E則前序序列是：A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不對13、若前序遍歷二叉樹的結(jié)果為序列A、B、C，則有_________棵不同的二叉樹可以得到這一結(jié)果。A.3 B.4 C.5 D.614、已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則它的前序遍歷是（）。A.acbedB.decabC.deabcD.cedba15、線索二叉樹是一種（）結(jié)構(gòu)。A．邏輯B．邏輯和存儲C．物理D．線性二、填空題1、對于任意一棵二叉樹，如果其葉子結(jié)點數(shù)為N0，度為1的結(jié)點數(shù)為N1，度為2的結(jié)點數(shù)為N2，則N0=___N2+1_________。2、具有256個結(jié)點的完全二叉樹的深度為___9___。3、一個深度為4的二叉樹，其結(jié)點至少有4個，至多有15個：4、深度為H的完全二叉樹至少有_2H-1__個結(jié)點；至多有2H-1_個結(jié)點；H和結(jié)點總數(shù)N之間的關(guān)系是H=?log2N?+1。5、若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，N個結(jié)點的二叉樹共有__2N__個指針域，其中有_N-1__個指針域是存放了地址，有__N+1_____個指針是空指針。6、設(shè)一棵赫夫曼樹有6個葉子結(jié)點，權(quán)值分別為3、4、7、14、15、20，則根結(jié)點的權(quán)值是__63____7、已知二叉樹的先序遍歷次序是abdcef，中序遍歷次序是bdaecf，則它的后序遍歷次序是：dbefca。8、對一棵完全二叉樹，設(shè)一個結(jié)點的編號為i，若它的左孩子結(jié)點存在，則其編號為2i；若右孩子結(jié)點存在，則其編號為2i+1；而雙親結(jié)點的編號為。9、赫夫曼樹是帶權(quán)路徑長度最小的二叉樹，又稱最優(yōu)二叉樹，路徑上權(quán)值較大的結(jié)點離根較近。10、structnode*rchildT=NULL11、二叉樹由_根結(jié)點__，__左子樹_，_右子樹__三個基本單元組成。12、樹的鏈表存儲結(jié)構(gòu)常用的有三種，其中，雙親表示法——以一組連續(xù)空間存儲樹的結(jié)點，在每個結(jié)點中設(shè)一個指示器指示雙親結(jié)點的位置。孩子表示法——每個結(jié)點的孩子以單鏈表的形式存儲，n個結(jié)點有n個孩子鏈表，n個頭指針又組成一個線性表，并以順序存儲結(jié)構(gòu)存儲。孩子兄弟表示法——以二叉鏈表作為樹的存儲結(jié)構(gòu)，鏈表中的結(jié)點的兩個指針分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點。//P135-13613、利用樹的孩子兄弟表示法存儲，可以將一棵樹轉(zhuǎn)換為__二叉樹____。14、在二叉樹中，指針p所指結(jié)點為葉子結(jié)點的條件是_p->lchild==NULL&&p->rchlid==NULL_____。15、樹的孩子兄弟表示法和二叉樹的二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。16、樹和二叉樹邏輯上都是樹形結(jié)構(gòu)，但是二叉樹不是樹的特例，二叉樹與樹是兩個不同的概念。二叉樹的度至多為2，樹無此限制；二叉樹有左右子樹之分，即使在只有一個分枝的情況下，也必須指出是左子樹還是右子樹，樹無此限制。17、8層的完全二叉樹至少有_128(第七層滿，加第八層１個)_個結(jié)點，擁有100個結(jié)點的完全二叉樹的最大層數(shù)為__7__。18、對于樹的孩子表示法，由于樹中每個結(jié)點可能有多棵子樹，則可用多重鏈表表示其存儲結(jié)構(gòu)。假設(shè)多重鏈表中的結(jié)點結(jié)構(gòu)相同，則一棵結(jié)點數(shù)為n的d叉樹中必有n(d-1)+1個空鏈域。三、簡答題1、已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ，中序遍歷的結(jié)果是KBCDAFHIGJ,試畫出這棵二叉樹，并寫出后序遍歷結(jié)果。答案：當(dāng)前序序列為ABKCDFGHIJ，中序序列為KBCDAFHIGJ時，逐步形成二叉樹的過程如下圖所示：這棵二叉樹的后序遍歷結(jié)果是：KDCBIHJGFA2、某通信電文由A、B、C、D、E、F六個字符組成，它們在電文中出現(xiàn)的次數(shù)（權(quán)值）分別是16，5，7，3，8，1。試畫出其哈夫曼樹，確定其對應(yīng)的哈夫曼編碼，并計算其帶權(quán)路徑長度。為使結(jié)果唯一，請將權(quán)值較小的結(jié)點作為其雙親的左孩子，而將權(quán)值較大的結(jié)點作為其雙親的右孩子。答案：哈夫曼樹如下：對應(yīng)的哈夫曼編碼如下：A:0B:101C:110D:1001E:111F:1000帶權(quán)路徑長度為:WPL=(1+3)*4+(5+7+8)*3+16*1=923、對下圖所示二叉樹分別按前序﹑中序﹑后序遍歷，給出相應(yīng)的結(jié)點序列，同時給二叉樹加上中序線索。答案：（1）前序序列：ABDEHCFG（2）中序序列：DHEBAFCG（3）后序序列：HEDBFGCA（4）中序線索見圖中虛線箭頭所示。4、試評述二叉樹的順序存儲表示法、二叉鏈表表示法、三叉鏈表表示法和雙親鏈表表示法這四種二叉樹的存儲結(jié)構(gòu)表示法的優(yōu)、缺點。答案：略（p126-p128，自己看書總結(jié)）。5、滿二叉樹和完全二叉樹有什么特點？答案：略（p124，自己看書）。6、試評述樹的雙親表示法、孩子表示法、孩子兄弟表示法這三種樹的存儲結(jié)構(gòu)表示法的優(yōu)、缺點。答案：略（p135-p137，自己看書總結(jié)）。四、算法分析題1、已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法，之后，對于如下所示的二叉樹：（1）畫出執(zhí)行下面算法后所建立的結(jié)構(gòu)；（2）說明該算法的功能。typedefstructnode{DateTypedata；Structnode*next；}ListNode；typedefListNode*LinkList；LinkListLeafhead=NULL；voidInorder(BinTreeT){LinkLists；If(T){Inorder(T－>lchild)；If((!T－>lchild)&&(!T－>rchild)){s=(ListNode*)malloc(sizeof(ListNode))；s－>data=T－>data；s－>next=Leafhead；Leafhead=s；}Inorder(T－>rchild);}}答案：2、已知二叉樹中的結(jié)點類型BinTreeNode定義為:

structBinTreeNode{ElemTypedata;

structBinTreeNode*left,*right;};其中data為結(jié)點值域，left和right分別為指向左、右孩子結(jié)點的指針域。下面函數(shù)的功能是從二叉樹BT中查找值為x的結(jié)點，若查找成功則返回結(jié)點地址，否則返回空。按標(biāo)號填寫空缺的內(nèi)容，要求統(tǒng)一填寫在算法后面的標(biāo)記處。

structBinTreeNode*BTF(

structBinTreeNode*BT，ElemTypex)

{

if(BT==NULL)_returnNULL__;

else{if(BT->data==x)_returnBT

_;

else{

structBinTreeNode*t;

if(t=BTF(BT->left,x))returnt;

___if(t=BTF(BT->right,x))returnt

_____;

returnNULL;

}

}

}3、由二叉樹的前序序列和中序序列能否唯一確定一棵二叉樹？由二叉樹的中序序列和后序序列能否唯一確定一棵二叉樹？由二叉樹的前序序列和后序序列能否唯一確定一棵二叉樹？請分別進(jìn)行論述。答案：(1)給定二叉樹結(jié)點的前序序列和中序序列，可以唯一確定該二叉樹。因為前序序列的第一個元素是根結(jié)點，該元素將二叉樹中序序列分成兩部分，左邊（設(shè)l個元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（設(shè)r個元素）是右子樹，若為空，則右子樹為空。根據(jù)前序遍歷中“根—左子樹—右子樹”的順序，則由從第二元素開始的l個結(jié)點序列和中序序列根左邊的l個結(jié)點序列構(gòu)造左子樹，由前序序列最后r個元素序列與中序序列根右邊的r個元素序列構(gòu)造右子樹。(2)由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。證明如下：當(dāng)n=1時，只有一個根結(jié)點，由中序序列和后序序列可以確定這棵二叉樹。設(shè)當(dāng)n=m-1時結(jié)論成立，現(xiàn)證明當(dāng)n=m時結(jié)論成立。設(shè)中序序列為S1，S2，…，Sm,后序序列是P1,P2,…，Pm。因后序序列最后一個元素Pm是根，則在中序序列中可找到與Pm相等的結(jié)點（設(shè)二叉樹中各結(jié)點互不相同）Si(1≤i≤m)，因中序序列是由中序遍歷而得，所以Si是根結(jié)點，S1，S2，…，Si-1是左子樹的中序序列，而Si+1,Si+2,…,Sm是右子樹的中序序列。若i=1，則S1是根，這時二叉樹的左子樹為空，右子樹的結(jié)點數(shù)是m-1,則{S2，S3，…，Sm}和{P1，P2，…，Pm-1}可以唯一確定右子樹，從而也確定了二叉樹。若i=m,則Sm是根，這時二叉樹的右子樹為空，左子樹的結(jié)點數(shù)是m-1，則{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一確定左子樹，從而也確定了二叉樹。最后，當(dāng)1<i<m時，Si把中序序列分成{S1，S2，…，Si-1}和{Si+1,Si+2,…，Sm}。由于后序遍歷是“左子樹—右子樹—根結(jié)點”，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉樹的左子樹和右子樹的后序遍歷序列。因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}可唯一確定二叉樹的左子樹，由{Si+1,Si+2,…，Sm}和{Pi,Pi+1,…，Pm-1}可唯一確定二叉樹的右子樹。(3)由二叉樹的前序序列和后序序列不能唯一確定一棵二叉樹。因為無法確定左右子樹兩部分。例如，任何結(jié)點只有左子樹的二叉樹和任何結(jié)點只有右子樹的二叉樹，其前序序列相同，后序序列相同，但卻是兩棵不同的二叉樹。五、算法描述題試寫出復(fù)制一棵二叉樹的遞歸函數(shù)的算法。BiTreeCopy(BiTreet)//復(fù)制二叉樹t{BiTreebt;if(t==null)bt=null;else{bt=(BiTree)malloc(sizeof(BiNode));bt->data=t->data;bt->lchild=Copy(t->lchild);bt->rchild=Copy(t->rchild);}return(bt);}《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)題及參考答案-第7章圖////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、選擇題1、以下數(shù)據(jù)結(jié)構(gòu)中，哪種具有非線性結(jié)構(gòu)？A．棧B．隊列C．雙向鏈表D．十字鏈表2、下面關(guān)于圖的存儲的敘述中正確的是（）。A.用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)。B.用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點個數(shù)都有關(guān)。C.用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān)。D.用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)3、在圖的鄰接表存儲結(jié)構(gòu)上執(zhí)行深度優(yōu)先搜索遍歷類似于二叉樹上的（）A.先根遍歷B.中根遍歷C.后根遍歷D.按層次遍歷4、圖的廣度優(yōu)先遍歷算法類似于樹的（）。A.中根遍歷 B.先根遍歷 C.后根遍歷 D.按層次遍歷5、設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（）條邊。A．n-1B．n(n-1)/2C．n(n+1)/2D．06、設(shè)有n個結(jié)點的無向圖，該圖至少應(yīng)有()條邊才能確保是一個連通圖。A．n-1