第3部分 數(shù)據(jù)結(jié)構(gòu)習(xí)題與答案第12章 基礎(chǔ)知識及線性結(jié)構(gòu)習(xí)題121 單項選擇題1.以下術(shù)語中與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的是 。A）散列表 B）雙鏈表 C）棧 D）循環(huán)順序隊列2.算法必須具備 、輸入、輸出5個特性。A）可行性、可移植性、可擴(kuò)充性B）可行性、確定性、有窮性C）確定性、有窮性、穩(wěn)定性D）易讀性、穩(wěn)定性、安全性 3.評價算法的兩個主要標(biāo)準(zhǔn)是 。A）正確性和簡明性B）可讀性和文檔性C）空間復(fù)雜度和時間復(fù)雜度D）數(shù)據(jù)復(fù)雜度和程序復(fù)雜度4.在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要表示出 。A）數(shù)據(jù)的處理方法B）數(shù)據(jù)元素之間的關(guān)系C）數(shù)據(jù)元素的類型D）數(shù)據(jù)的存儲方法5.程序段 for(i=0;i<n;i+) for(j=0;j<n;j+) Aij=0;的時間復(fù)雜度是 。A）O(n2)B）O(n)C）O(1)D）O(log2n)6以下說法中正確的是_A) 順序存儲只適應(yīng)于存儲線性結(jié)構(gòu)B) 對二叉樹只能用鏈接方式存儲C) 對二維數(shù)組只能用順序方式存儲D) 數(shù)據(jù)運算的實現(xiàn)與存儲結(jié)構(gòu)有關(guān)7.線性表是 。A）一個有限序列，可以為空B）一個有限序列，不可以為空C）一個無限序列，可以為空D）一個無限序列，不可以為空8.順序表的優(yōu)點是 。 A）所需空間隨線性表長度的變化而變化B）可隨機(jī)訪問指定下標(biāo)的元素C）插入和刪除不需要移動元素D）不必事先估計存儲空間9.假設(shè)對一個線性表很少進(jìn)行插入、刪除，但經(jīng)常要訪問其中指定下標(biāo)的元素。該線性表適合采用的存儲方式是 。A）單鏈表B）散列表C）順序表D）循環(huán)鏈表10.線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址 。A）必須是不連續(xù)的B）連續(xù)與否均可C）必須是連續(xù)的D）和頭結(jié)點的存儲地址相連續(xù)11.線性表采用鏈?zhǔn)酱鎯r，數(shù)據(jù)元素的邏輯順序與在內(nèi)存中的存儲順序 。A）一致B）也可能不一致C）完全不一致D）有一定的關(guān)系12.以下存儲結(jié)構(gòu)中不利于線性表長度變化的是 。 A）單鏈表B）順序表C）循環(huán)鏈表D）雙鏈表13.用鏈接方式存儲線性表的優(yōu)點是 。A）便于隨機(jī)存取指定下標(biāo)的元素 B）存儲密度高C）插入和刪除不需要移動元素D）可以用元素在存儲器中的物理位置表示元素之間的邏輯關(guān)系14.在一個長度為n的順序表中，向第i個元素（0in）之前插入一個新元素時，需要向后移動的元素個數(shù)為 。A）n-iB）n-i+1C）n-i-1D）i15.在一個長度為n的順序表中，刪除第i個元素（0in-1）時，需要向前移動的元素個數(shù)為 。A）n-iB）n-i+1C）n-i-1D）i16.設(shè)指針p指向單鏈表中的結(jié)點m，若要刪除m之后的結(jié)點（假設(shè)其存在），則需要執(zhí)行的修改指針操作為 。A) p->next=pB) p->next=p->next->nextC) p=p->nextD) p= p->next->next17.如果對某線性表最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用 存儲方式最節(jié)省時間。A）單鏈表B）雙鏈表C）單循環(huán)鏈表D）順序表18.對某線性表最常用的操作是在最后一個結(jié)點之后插入和刪除開始結(jié)點，為節(jié)省運行時間應(yīng)采用的存儲方式是 。A）單鏈表B）僅有頭指針的單循環(huán)鏈表C）雙鏈表D）僅有尾指針的單循環(huán)鏈表19.與單鏈表相比，雙鏈表的優(yōu)點之一是 。A）向前后兩個方向順序訪問相鄰結(jié)點更方便B）可以進(jìn)行隨機(jī)訪問C）插入、刪除操作更簡單D）使用的空間更小20.鏈表不具備的特點是 。 A）所需空間隨線性表長度的變化而變化B）可隨機(jī)訪問指定下標(biāo)的元素C）插入和刪除不需要移動元素D）不必事先估計存儲空間21.設(shè)對一組數(shù)據(jù)的處理具有“后進(jìn)先出”的特點，則應(yīng)采用的最佳數(shù)據(jù)結(jié)構(gòu)是 。A）隊列B）棧C）順序表D）二叉樹22.若進(jìn)棧序列為3、5、7、9，進(jìn)棧和出?？纱┎暹M(jìn)行，則不可能的出棧序列是 。 A）7，5，3，9B）9，5，7，3C）9，7，5，3D）7，5，9，323.設(shè)用一維數(shù)組Am存儲棧，令A(yù)m-1為棧底，t指示當(dāng)前棧頂?shù)奈恢?。如果棧不空，則出棧時應(yīng)使 。A）t=t+1B）t=t-1C）t=m-1D）不改變t24.設(shè)用一維數(shù)組Am存儲棧，令A(yù)0為棧底，top指示當(dāng)前棧頂?shù)奈恢茫?dāng)把棧清空時所要執(zhí)行的操作是 。A）top-B）top=0C）top=-1D）top=m-125.設(shè)棧s的初始狀態(tài)為空，如果進(jìn)棧序列為1、2、3、4、5、6，出棧序列3、2、5、6、4、1，則s的容量至少是 。A）6B）4C）2D）326.設(shè)棧S最多能容納4個元素，現(xiàn)有A、B、C、D、E、F六個元素按順序進(jìn)棧，以下可能的出棧序列是 。A）E、D、C、B、A、FB）B、C、E、F、A、DC）C、B、F、D、A、ED）A、D、F、E、B、C27鏈?zhǔn)綏Ｅc順序棧相比，一個比較明顯的優(yōu)點是 。A）插入操作更加方便B）通常不會出現(xiàn)棧滿的情況C）不會出現(xiàn)?？盏那闆rD）刪除操作更加方便28在完成出棧操作時， 。A）必須判斷棧是否滿B）要判別棧元素的類型C）必須判斷棧是否空D）不必做任何判斷29.已知棧的入棧序列是1、2、3、n，出棧序列是e1、e2、en，若e1=n，則ei為 。 A）iB）n-i+1C）n-iD）不能確定30.在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，打印機(jī)則從該緩沖區(qū)取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個 結(jié)構(gòu)。 A）棧B）隊列C）線性表D）數(shù)組31. 不是隊的基本運算。 A）向隊尾插入一個元素B）讀隊頭元素C）刪除隊中第i個元素D）判隊是否為空32當(dāng)以順序方式存儲隊列時，解決“假溢出”較為有效的方法是采用 。A）順序隊列B）鏈?zhǔn)疥犃蠧）順序循環(huán)隊列D）三種都可以33.設(shè)數(shù)組Q用于存放循環(huán)隊列中的元素，同時用f指示當(dāng)前隊頭元素的位置，r指示當(dāng)前隊尾元素的下一個位置。假定隊中元素個數(shù)總小于m，則計算隊列中元素個數(shù)的公式為 。A）(m+r-f)%mB）r-f C）m-(f-r)D）(m+(f-r)%m34.若用一個大小為10的一維數(shù)組存儲順序循環(huán)隊列，且當(dāng)前rear和front的值分別為4和8，當(dāng)從隊列中刪除3個元素再加入2個元素后，rear和front的值分別是 。A）無法完成要求的操作B）1和6C）7和0C）11和635.棧和隊列都是運算受限的線性表，它們的共同點是 。A）只允許在端點處插入和刪除元素B）元素都是后進(jìn)先出C）元素都是先進(jìn)先出D）必須采用順序存儲結(jié)構(gòu)36.一維數(shù)組和線性表的區(qū)別是 。A）前者長度固定，后者長度可變B）兩者長度均可變C）兩者長度均固定D）前者長度可變，后者長度固定37.多維數(shù)組中元素之間的關(guān)系 。A）是線性的B）是樹形的C）既是線性的，又是樹形的D）既非線性的，也非樹形的38.不屬于數(shù)組基本運算的是 。A）數(shù)組的轉(zhuǎn)置B）數(shù)組相加C）插入D）數(shù)組相乘39.設(shè)有n×n階的對稱矩陣A，為節(jié)省存儲空間，只將主對角線及主對角線之上的元素按行優(yōu)先順序存放到一維數(shù)組B中，則數(shù)組B的最小容量是 。 A）n×nB）(n+1)/2C）n2/2D）n(n+1)/240.上題中，存儲矩陣A上三角中任意元素aij(0ijn-1)的B數(shù)組元素的下標(biāo)為 。 A）i+jB）i(i+1)/2+jC）i(2n-i-1)/2+j D）i×n+j41.若把三對角矩陣帶狀區(qū)域中的元素按行優(yōu)先順序存放在一維數(shù)組B中，則存儲處于帶狀區(qū)域上的元素aij(|i-j|1)的數(shù)組B中的元素下標(biāo)為 。 A）3i-jB）i+j+1C）2i+j D）i+2j-142.串是一種特殊的線性表，其特殊性體現(xiàn)在 。A）可以順序存儲B）可以鏈接存儲C）數(shù)據(jù)元素是一個字符D）數(shù)據(jù)元素可以是多個字符43.兩個串相等的充分必要條件是 。A）長度相等B）長度相等且對應(yīng)位置的字符相同C）長度相等且前面若干個對應(yīng)位置的字符相同D）前面若干個對應(yīng)位置的字符相同44.串是 。A）不少于一個字符的序列B）任意個字符的序列C）有限個字符的序列D）一個字符45.空串是 的字符串。A）含有一個空格符B）只含空格符C）不含任何字符D）任意46.一個空串的長度是 。A）0B）1C）沒有長度D）不確定47.串的長度是串中 。A）字母字符的個數(shù)B）不同字符的個數(shù)C）除空格符外字符的個數(shù)D）字符的個數(shù) 答案：1.C2.B3.C4.B5.A6.D7.A8.B9.C10.B11.B12.B13.C14.A15.C16.B17.D18.D19.A20.B21.B22.B23.A24.C25.D26.C27.B28.C29.B30.B31.C32.C33.A34.B35.A36.A37.D38.C39.D40.C41.C42.C43.B44.C45.C46.A47.D12.2 簡答題1.什么是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)?數(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ù)的邏輯結(jié)構(gòu)在計算機(jī)中的具體實現(xiàn)。數(shù)據(jù)的邏輯結(jié)構(gòu)可分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)四類基本類型，其中，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)又合稱為非線性結(jié)構(gòu)；數(shù)據(jù)的存儲結(jié)構(gòu)有順序方式、鏈接方式、索引方式和散列方式4種基本方式。2. 請說明評價排序算法的好壞的兩個標(biāo)準(zhǔn)。答：執(zhí)行算法所需要的時間；執(zhí)行算法所需要的空間。3. 如果一個線性表中元素的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取表中指定位置的元素，對該線性表應(yīng)選用何種存儲結(jié)構(gòu)？為什么？答：應(yīng)選用順序存儲結(jié)構(gòu)。因為，在以順序方式存儲線性表時，線性表中元素的存儲順序與邏輯順序相一致，根據(jù)元素的下標(biāo)可以很快地找到它的存儲位置。4.一個理發(fā)店有兩名理發(fā)師，一名理發(fā)師專為年紀(jì)最大的顧客服務(wù)，另一名理發(fā)師為進(jìn)入理發(fā)店時間最長的顧客服務(wù)，進(jìn)入理發(fā)店的顧客根據(jù)到達(dá)的時間先后順序都排入一個隊列。假設(shè)用程序來模擬理發(fā)店顧客隊列的變化情況，該顧客隊列在邏輯上可視為哪種數(shù)據(jù)結(jié)構(gòu)？要存儲相關(guān)信息應(yīng)采用哪一種存儲結(jié)構(gòu)？為什么？答：線性表，因為顧客出隊沒有限定在一端；鏈?zhǔn)酱鎯Y(jié)構(gòu)，因為新來的顧客要加入隊列，接受理發(fā)師服務(wù)的顧客要離開隊列，對顧客隊列這個線性表來說，需要經(jīng)常的插入和刪除操作。5. 單鏈表中設(shè)置頭結(jié)點的作用是什么？答：設(shè)置頭結(jié)點后，由于頭指針總是指向頭結(jié)點，所以在實現(xiàn)對單鏈表的操作時不必區(qū)分空表和非空表，對開始結(jié)點的操作與對其他結(jié)點的操作也相同，這樣，可簡化處理。6. 設(shè)棧S的初始狀態(tài)為空，隊列Q的初始狀態(tài)為 隊頭隊尾a1 a2 a3 a4對棧S和隊列Q進(jìn)行以下操作：1） Q中元素依次出隊，并壓入棧S中，直至Q為空。2） 依次彈出S中的元素并進(jìn)入Q，直至S為空。請畫出在上述操作后隊列Q的狀態(tài)。隊頭隊尾a4 a3 a2 a1答：7.在以順序方式存儲隊列時，會出現(xiàn)“假溢出”現(xiàn)象，清解釋這一現(xiàn)象，并說明解決“假溢出”的方法及其原理。答：“假溢出”是指存儲隊列的空間中還有空余，但不能進(jìn)行入隊操作，它是由隊列的操作方式?jīng)Q定的。解決“假溢出”的方法有：1）建立一個足夠大的存儲空間，但這樣會造成空間的浪費。2）采用循環(huán)隊列方式。把存儲隊列的一維空間看成是一個首尾相接的圓環(huán)，這樣就可以實現(xiàn)對由于元素出隊而空出來的空間的循環(huán)使用。3）采用平移元素的方法。每當(dāng)出現(xiàn)“假溢出”時，將隊列中所有元素平移，使當(dāng)前隊頭元素位于數(shù)組的最前端，并修改隊頭和隊尾指示器。此方法效率很低。8.設(shè)用一維數(shù)組Am存儲循環(huán)隊列，只設(shè)置一個隊頭指示器front，和一個用以記錄隊列中元素個數(shù)的計數(shù)器count。在此情況下，隊空、隊滿的條件是什么？如何確定將要入隊元素的位置？答：1）隊空條件為：count=02）隊滿條件為：count=m3）將要入隊元素的位置是：(front+count)%m9. 給出以下稀疏矩陣的三元組表。答：12.3 程序填空題 1.有n個人排成一排，每個人的編號為i(1in)，現(xiàn)讓這n個人從左到右1、2、1、2、報數(shù)，凡報“1”的人出列，報“2”的人立即站到隊的最右端，此過程反復(fù)進(jìn)行，直到n個人都已出列。設(shè)已知n個人原來在隊列中的順序，以下程序可求出他們出列的順序。例如，設(shè)n=6，初始順序為1、2、3、4、5、6，則出列順序為1、3、5、2、6、4。 算法說明:此問題可利用隊列結(jié)構(gòu)處理。設(shè)一維數(shù)組p存放循環(huán)隊列，f和r分別為隊列的隊頭和隊尾指示器，首先讓n個人的初始序號依次入隊，然后反復(fù)執(zhí)行以下操作，直到隊列為空。 (1)輸出隊頭元素，并刪除之。 (2)若剛剛離隊的元素值在當(dāng)時的隊列中最大，則記錄下當(dāng)前隊列中最大元素值，否則將隊頭元素插入到隊尾。 程序如下: #include <iostream>using std:cout;using std:endl; const int N=20; int main() int pN; int f=0,r=0，qm=N; for(int i=1;i<=N;i+) p (1) =i; r=(r+1)%N; do int t=pf; cout<<t<< ; f= (2) ; if(t=qm)qm-; else (3) =pf; r= (4) ; f= (5) ; while(f!=r); cout<<endl; return 0; 答：(1)r (2)(f+1)%N (3)pr (4)(r+1)%N (5)(f+1)%N2.以下函數(shù)的功能是，將一維整型數(shù)組A中所有奇數(shù)移到所有偶數(shù)之前。算法說明：可以設(shè)置兩個下標(biāo)變量i 和j，它們的初值分別為0和n-1。從數(shù)組的兩端開始，讓i向右，j向左對數(shù)組中元素進(jìn)行掃描，若Ai為偶數(shù)，Aj為奇數(shù)，則交換Ai和Aj。當(dāng)i和j重合時，算法結(jié)束。void oddbefore(int A,int n)int i,j,t;i=0; j=n-1;while(i<j)while(Ai%2=1&& （1） )/Ai為奇數(shù)時，i向右掃描i+;while(Aj%2=0&& （2） )/Aj為偶數(shù)時，j向左掃描j-;if( （3） )t=Ai;Ai=Aj;Aj=t;i+; j-; 答：（1）(i<j)（2）(i<j)（3）i<j3.設(shè)一維數(shù)組A中有n個元素，以下函數(shù)實現(xiàn)從A中刪除值在x到y(tǒng)（x<=y）之間的所有元素。算法說明：從A0開始向后掃描A中元素，用k記錄滿足刪除條件的元素個數(shù)，對不滿足刪除條件的元素，將其前移k個位置。template<class T>void delall(T A,int &n,T x,T y)int i=0,k=0;while(i<n)if( （1） )/k記錄被刪除元素的個數(shù)k+;elseA （2） =Ai;/前移k個位置i+;n= （3） ;答：（1）Ai>=x&&Ai<=y（2）i-k （3）n-k4.假定一維數(shù)組A中有多個零元素，以下函數(shù)可以實現(xiàn)將A中所有非零元素依次移到數(shù)組的前端，并保持它們的相對位置不變。下面是用兩種方法實現(xiàn)上述功能的函數(shù)。方法一 算法說明:依次考查數(shù)組中的各個元素，若發(fā)現(xiàn)一個零元素，則將此元素之后的所有元素依次前移一個位置。 程序如下: void mov1(int A,int n) /n為數(shù)組A中包含的元素個數(shù) int i,j,k; i=0;k=n-1; while(i<=k) if(Ai=0) for(j=i+1; (1) ;j+) (2) =Aj; Ak=0; (3) ; else (4) ; 答：(1)j<=k (2)Aj-1 (3)k- (4)i+ 方法二 算法說明:在數(shù)組中找到第一個為零的元素Ai，然后找出該元素后面的第一個非零元素Aj，將Aj存入Ai，再將Aj置為0，使i增1，繼續(xù)以上過程。 程序如下: void mov2(int A，int n) /n為數(shù)組A中包含的元素個數(shù) int i=0,j; while( (1) )i+; (2) ; while(j<n) if( (3) ) Ai=Aj; Aj=0; i+; (4) ; 答： (1)i<n && Ai!=0 (2)j=i+1 (3)Aj!=0 (4)j+5以下函數(shù)的功能是：將一維整型數(shù)組A中的 n個數(shù)循環(huán)右移m位。void move(int a,int n,int m)int i,j,x;for(i=0; （1） ;i+)x=an-1;for( （2） ;j>0;j-) aj=aj-1; （3） ; 答：（1）i<m（2）j=n-1 （3）a0=x; 6.一維數(shù)組A中有n個有序的元素，以下函數(shù)實現(xiàn)刪除數(shù)組中重復(fù)的元素，并返回刪除重復(fù)元素后數(shù)組中元素的個數(shù)。 程序如下: int delA(int A,int n) int i,k; i=1;k=0; while( (1) ) if(Ak!=Ai) k+; Ak=Ai; (2) ; return (3) ; 答：(1)i<n (2)i+ (3)k+17Reverse是在單鏈表類Chain中增加的成員函數(shù)，它的功能是在原地實現(xiàn)表元素的反轉(zhuǎn)。template<class T>void Chain<T>:Reverse() Node<T> *current = head->next, /指向當(dāng)前處理的結(jié)點*next,/ 指向當(dāng)前結(jié)點的直接后繼*last = 0;/ 指向反轉(zhuǎn)后當(dāng)前結(jié)點的直接后繼 while (current) next = current->next; current->next = last; （1） = current; current = next; （2） = last; /last指向反轉(zhuǎn)后鏈表的開始結(jié)點答：（1）last（2）head->next8IsSorted是在單鏈表類Chain中增加的成員函數(shù)，它的功能是檢查單鏈表中元素是否為非遞減順序，如果是，返回true，否則返回false。template<class T>bool Chain<T>:IsSorted() const if (length=0) return true; / 表空 Node<T> *current = head->next, /指向當(dāng)前處理的結(jié)點 *next = current->next; /指向當(dāng)前結(jié)點的直接后繼 while ( （1） ) if (current->data > next->data) （2） ; current = next; next = （3） ; return true;答：（1）next（2）return false（3）current->next9.Del是在單鏈表類Chain中增加的成員函數(shù)，其功能是刪除單鏈表中值相同的重復(fù)結(jié)點。template<class T>void Chain<T>:Del()Node<T> *p,*pre,*q;p=head->next;while( （1） )pre=p;q=p->next;while(q!=NULL)while(q!=NULL && （2） )pre=q;q=q->next;if(q!=NULL)pre->next=q->next;delete q;q=pre->next;p=p->next;答：（1）p!=NULL（2）q->data!=p->data10.已知A，B和C為三個遞增有序的線性表，現(xiàn)對A表進(jìn)行如下操作：刪去那些既在B表又在C表中出現(xiàn)的元素。在以下實現(xiàn)上述操作的函數(shù)中，假定線性表以順序方式存儲。template <typename T>void SeqList_Delete(SeqList<T> &A,SeqList<T> &B,SeqList<T> &C)int i,j,k;i=j=k=0;T a,b,c,x;while(i<A.Length()&&j<B.Length()&&k<C.Length()B.Find(j,b);C.Find(k,c);if(b<c) （1） ;else if( （2） ) k+;else/找到了B，C共有的元素x=b;while(B.Find(+j,b)&&(b=x);/在B中跳過與x相等的元素while(C.Find(+k,c)&&(c=x); /在C中跳過與x相等的元素while(A.Find(i,a)&&a<x) i+;/在A中檢索等于x的元素while(A.Find(i,a)&&a=x) A.Delete(i,a);/刪除等于x的元素答：（1）j+（2）b>c11.以下函數(shù)用于檢驗一個表達(dá)式中括號是否匹配。如果匹配返回1，否則返回0。設(shè)表達(dá)式中只使用了括號()和方括號，表達(dá)式在一維數(shù)組exp中。 算法說明:為檢查表達(dá)式中括號的匹配情況，可設(shè)置一個棧s。從左到右掃描表達(dá)式，若當(dāng)前字符為左括號，則將其壓入棧s中。若當(dāng)前字符為右括號，則檢查它是否與棧頂?shù)淖罄ㄌ栂嗥ヅ洹Ｈ粝嗥ヅ?，則刪去這一對括號;不相匹配，則表示表達(dá)式中括號不匹配。若掃描完表達(dá)式時棧為空，則說明表達(dá)式中括號是匹配的，否則是不匹配的。函數(shù)中使用變量flag作為括號匹配的標(biāo)志，flag為1表示匹配，flag為0表示不匹配。 程序如下: const int MaxSize 100 int matching(char expMaxSize) char sMaxSize; int top=-1; /s作為順序棧，top為棧頂指示器 int flag,i; flag=1;i=0; while(expi!=&&flag) switch(expi&&flag) case(: case: (1) =expi;break; case): if( (2) )top-; else flag=0; break; case: if( (3) )top-; else flag=0; break; (4) ; if( (5) )return 1; else return 0; 答：(1)s+top (2)top!=-1 && stop=( (3)top!=-1 && stop= (4)i+ (5)flag && top=-112.編寫一個函數(shù)，利用隊列和棧的基本運算將指定隊列中的元素進(jìn)行逆轉(zhuǎn)。算法說明：利用一個臨時棧tempst，將指定隊列que中所有元素出隊并入棧到tempst，然后再將棧tempst中的所有元素出棧并入隊到que，此時，隊列que中的元素已發(fā)生逆轉(zhuǎn)。在以下函數(shù)中使用了STL的容器適配器定義隊列和棧。程序如下：#include <queue>#include <stack>using namespace std;template <typename T>void reverse_que(queue<T> &que)T x;stack<T> tempst;while( （1） )x=que.front();/取隊頭元素到xtempst.push(x);/x入棧 （2） ;while(!tempst.empty()/當(dāng)棧不為空時x=tempst.top();/取棧頂元素到x （3） ;tempst.pop();/出棧答：（1）!que.empty()（2）que.pop()（3）que.push(x)13.以下函數(shù)在字符串s中尋找是否存在與字符串t相同的子串，是，則返回子串的起始位置，否則返回-1。(若有多個匹配的子串，只返回第一個子串的位置)。 int IndexBF(char s,char t) int i=0，j=0; while(si+j!=0&&tj!=0) if(si+j=tj) (1) ; else i+; (2) ; if( (3) )return i; else return -1; 答：(1) j+ (2) j=0 (3) tj=014.以下函數(shù)計算一個子串t在一個字符串s中出現(xiàn)的次數(shù)，如果子串不出現(xiàn)則為0。int substr_count(char t,char s)int i,j,k,count=0;for(i=0; （1） ;i+)for(j=i,k=0; （2） ;j+,k+);if(tk=0)count+; （3） ;答：（1）si!='0'（2）sj=tk&&tk!=0（3）return count15.如果矩陣A中元素Aij滿足以下條件：它是第i行中值最大的元素，同時又是第j列中值最小的元素，則稱該元素為矩陣的一個鞍點。編寫函數(shù)求出m×n階矩陣A的所有鞍點。為簡單起見，這里假定每行和每列中的元素各不相同。算法說明：先求出每行值最小的元素，放入一維數(shù)組min之中，再求出每列值最大的元素，放入一維數(shù)組max之中，比較min和max中的元素，如果mini和maxj相等，則說明Aij是一個鞍點。 #include <iostream> using std:cout; using std:endl;const int m=3,n=4;void minmax(int Amn)int minm,maxn;int i,j,have=0;for(i=0;i<m;i+)mini= （1） ;for(j=1;j<n;j+)if( （2） )mini=Aij;for(j=0;j<n;j+)maxj=A0j;for(i=1;i<m;i+)if(Aij>maxj)maxj=Aij;for(i=0;i<m;i+)for(j=0;j<n;j+)if( （3） )cout<<i<<" , "<<j<<" : "<<Aij<<endl; （4） ;if(have=0)cout<<"沒有鞍點!n"答： （1）Ai0（2）Aij<mini（3）mini=maxj （4）have=116.設(shè)稀疏矩陣A采用三元組表示，編寫函數(shù)求其轉(zhuǎn)置矩陣B，要求B也采用三元組表示。算法說明：在稀疏矩陣的三元組表示中，非0元素按行優(yōu)先順序存放。為保證轉(zhuǎn)置后的矩陣在B中按行優(yōu)先順序存放，需要在A中首先找出下標(biāo)為0列的所有元素（它們是轉(zhuǎn)置矩陣下標(biāo)為0行的非0元素），將它們依次存放在B中。按此方法逐列處理即可。程序如下：template <typename T>void transpose(T A3,T B3)int m,n,t;m=A00;/稀疏矩陣的行數(shù)n=A01;/稀疏矩陣的列數(shù)t=A02;/稀疏矩陣中非0元素的個數(shù)B00= （1） ; B01= （2）; B02=t;int p,q,col;if(t>0)q=1;for(col=0;col<n;col+)for(p=1;p<t;p+)if( （3） )Bq0=Ap1;Bq1=Ap0;Bq2=Ap2; q+;答：（1）n或A00（2）m或A01（3）Ap1=col17.設(shè)m×n階的稀疏矩陣A和 n×l階的稀疏矩陣B均采用三元組表示，編寫函數(shù)計算C=A×B，要求C也采用三元組表示。算法說明：為通過給定的行下標(biāo)i和列下標(biāo)j找出原矩陣的對應(yīng)元素，這里設(shè)計了一個函數(shù)value，如果在三元組中找到該元素，則返回其值，否則，返回0。template <typename T>T value(T x3,int i,int j)int k=1;while(k<=x02 && xk0!=i && xk1!=j) k+;if(k<=x02) （1） ;else return 0;template <typename T>void matmul(T A3,T B3,T C3,int m,int n,int l)int i,j,k,p,s;p=1;for(i=0;i<m;i+)for(j=0;j<l;j+) （2） ;for(k=0;k<n;k+)s+=value(A,i,k)*value(B,k,j);if(s!=0)Cp0=i;Cp1=j;Cp2=s;p+;C00=m;C01=l;C02= (3) ;答：（1）return xk2（2）s=0(3) p-1第13章 非線性結(jié)構(gòu)13.1 單項選擇題1.樹的深度是指 。A）樹中結(jié)點的個數(shù)B）結(jié)點子樹的個數(shù)C）樹中結(jié)點的最大層數(shù)D）結(jié)點子樹的最多個數(shù)2.設(shè)二叉樹根結(jié)點的層數(shù)為0，一棵高度為h的滿二叉樹中結(jié)點的個數(shù)是 。A）2hB）2h-1C）2h-1 D）2h+1-13.某二叉樹的先序遍歷序列為abdgcefh，中序遍歷序列為dgbaechf，則其后序遍歷序列為 。A）bdgcefhaB）gdbecfhaC）bdgaechfD）gdbehfca4.任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的相對次序 。A）都不相同 B）完全相同C）有時相同有時不同D）先序和中序相同，而與后序不同5.二叉樹的先序遍歷序列等同于該二叉樹對應(yīng)森林的 。 A）層次遍歷序列B）先根遍歷序列 C）后根遍歷序列D）以上都不是6.對圖5.1所示的表達(dá)式二叉樹按中序遍歷得到的結(jié)點序列是 。A）c-d*b+a-e/f B）a+b*c-d-e/f C）a+c-d*b/e-fD）abcd+-*/ef7. 前序遍歷序列與中序遍歷序列相同的二叉樹為 。 A)根結(jié)點無左子樹的二叉樹B)根結(jié)點無右子樹的二叉樹C)只有根結(jié)點的二叉樹或非葉子結(jié)點只有左子樹的二叉樹D)只有根結(jié)點的二叉樹或非葉子結(jié)點只有右子樹的二叉樹8.前序遍歷序列與后序遍歷序列相同的二叉樹為 。A)非葉子結(jié)點只有左子樹的二叉樹B)只有根結(jié)點的二叉樹C)根結(jié)點無右子樹的二叉樹D)非葉子結(jié)點只有右子樹的二叉樹9.設(shè)a、b為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，a在b前的條件是 。A）a是b的祖先B）a是b的子孫C）a在b的右方D）a在b的左方10設(shè)結(jié)點x和結(jié)點y是二叉樹T中的任意兩個結(jié)點，若在先根序列中x在y之前，而在后根序列中x在y之后，則x和y的關(guān)系是 。A）x是y的左兄弟B）x是y的右兄弟C）x是y的祖先D）x是y的后代11.如果F是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的前序序列就是F中結(jié)點的 。A）中序序列B）先序序列C）后序序列D）層次序列12.設(shè)二叉樹根結(jié)點的層數(shù)為0，一棵高度為h(h>0)的完全二叉樹中，第h-1層上包含的結(jié)點個數(shù)為 。A）不確定 B）2h C）2h-1 D）2h-1+113.對于一個有n個結(jié)點的二叉樹，當(dāng)它為一棵 時高度最小。A）單支樹B）完全二叉樹C）二叉排序樹D）哈夫曼樹14.把一棵含70個結(jié)點的完全二叉樹以順序方式存儲在一維數(shù)組A中，該完全二叉樹中編號為26的結(jié)點的左子女存放在中 。A）A53 B）A54 C.A52 D）該結(jié)點設(shè)有左子女15.在以鏈接方式存儲一棵具有n個結(jié)點的二叉樹時，對應(yīng)二叉鏈表中指針域的總數(shù)是 。A）2n個B）n個C）n-1個D）n+1個 16.設(shè)F是由T1、T2、T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B。已知T1、T2、T3中包含的結(jié)點個數(shù)分別是m1、m2和m3，則B的根結(jié)點左子樹中結(jié)點的個數(shù)是 。 A）m1B）m2C）m3-1 D）m1-117.在上題中，二叉樹根結(jié)點右子樹中結(jié)點的個數(shù)是 。 A）m1+m2B）m3C）m2+m3 D）m2+m3-118.設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為P，P的右子樹有n個結(jié)點，則F中第一棵樹的結(jié)點數(shù)目是 。 A）m-n-1B）n+1C）m-n+1 D）m-n19.樹T的度為4，其中度為1、2、3、4的結(jié)點個數(shù)分別是4、2、1、1，則T中葉結(jié)點的個數(shù)為 。 A）5B）6C）7D）820.由三個結(jié)點可以構(gòu)造出種不同的形態(tài)的樹 。 A）2B）3C）4D）521.由三個結(jié)點可以構(gòu)造出種不同的形態(tài)的二叉樹 。A）2B）3C）4D）522.設(shè)二叉樹B中度為2的結(jié)點個數(shù)是n2，則B中葉結(jié)點的個數(shù)是 。 A）n2B）n2-1C）n2+2D）n2+123.n個葉結(jié)點的哈夫曼樹的結(jié)點總數(shù)是 。A）2n+1B）2(n+1)C）無法確定D）2n-124.由權(quán)值9，2，5，7構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度是 。A）23B）37C）46D）4425.有關(guān)二叉樹的下列說法中正確的是 。 A）二叉樹的度為2B）二叉樹的度可以小于2 C）二叉樹中任何一個結(jié)點的度都為2D）一棵二叉樹中至少有一個結(jié)點的度為226.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 倍。A）1/2B）4C）1D）227.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 倍。A）1/2B）4C）1D）228.設(shè)無向圖G的頂點數(shù)為n，圖G可能具有的最少邊數(shù)和最多邊數(shù)分別是 。A）0和n(n-1)/2B)0和nC)n和n(n-1)/2D）1和n(n-1)/229.具有4個頂點的完全無向圖應(yīng)有 條邊。A）12B）16C）20D）630.對于一個具有n個頂點的無向圖，如果采用鄰接矩陣表示，則相應(yīng)的矩陣大小是 。A）n(n+1)B）(n-1)(n-1)C) n2D) n(n-1)31.在一個圖G的鄰接表表示中，每個頂點的鄰接表中包含的結(jié)點數(shù)，對于有向圖和無向圖而言分別等于該頂點的 。A）入度數(shù)和度數(shù)B）出度數(shù)和度數(shù)C）均為度數(shù)D）與頂點無關(guān)32.對于一個具有n個頂點e條邊的無向圖，若采用鄰接表表示，則頂點表的大小為 。A）nB) n+1C) n-1D) n+e33.對于一個具有n個頂點e條邊的無向圖，若采用鄰接表表示，則所有邊表中邊結(jié)點的總數(shù)為 。A）e/2B) eC) 2eD) n+e34.在圖5.2所示的有向圖中，頂點V2的入度是 。圖5.2A）6 B）4 C）2 D）135.對某個無向圖的鄰接矩陣來說， 。A） 矩陣中非零元素的個數(shù)等于圖中的邊數(shù)B） 矩陣中零元素的個數(shù)等于圖中的邊數(shù)C） 第i行上非零元素的個數(shù)等于第i列上非零元素的個數(shù)D） 矩陣中非全零行的行數(shù)等于圖中頂點數(shù)36.設(shè)對有向圖G采用鄰接矩陣法存儲，則頂點i的入度等于鄰接矩陣中 。A）第i行非0元素的和B）第i行0元素的個數(shù)C）第i列非0元素的和D）第i列0元素的個數(shù)37若有向圖中頂點數(shù)為100，則該圖最多可能有 _ 條邊。A）10000 B）9900 C）9999D）2000138.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要 條邊。A）nB) n/2C) n+1D) n-139.任何一個帶權(quán)無向連通圖的最小生成樹 。A）可能不存在B）只有一棵C）一定有多棵D）有一棵或多棵40.在AOV網(wǎng)的拓?fù)湫蛄兄?，如果頂點Vi在Vj之前，則下列情況中不可能出現(xiàn)的是 。 A）Vi，Vj是圖中的邊B）圖中有一條從Vi到Vj的路徑