《計算機文化基礎習題與答案(第3部分 數(shù)據(jù)結(jié)構(gòu)習題與答案)》由會員分享，可在線閱讀，更多相關(guān)《計算機文化基礎習題與答案(第3部分 數(shù)據(jù)結(jié)構(gòu)習題與答案)（57頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第3部分 數(shù)據(jù)結(jié)構(gòu)習題與答案第12章 基礎知識及線性結(jié)構(gòu)習題121 單項選擇題1.以下術(shù)語中與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的是 。A）散列表 B）雙鏈表 C）棧 D）循環(huán)順序隊列2.算法必須具備 、輸入、輸出5個特性。A）可行性、可移植性、可擴充性B）可行性、確定性、有窮性C）確定性、有窮性、穩(wěn)定性D）易讀性、穩(wěn)定性、安全性 3.評價算法的兩個主要標準是 。A）正確性和簡明性B）可讀性和文檔性C）空間復雜度和時間復雜度D）數(shù)據(jù)復雜度和程序復雜度4.在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要表示出 。A）數(shù)據(jù)的處理方法B）數(shù)據(jù)元素之間的關(guān)系C）數(shù)據(jù)元素的類型D）數(shù)據(jù)的存儲方法5.程序段 for(

2、i=0;in;i+) for(j=0;jnext=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é)省運行時間應采用的存儲方式是 。A）單鏈表B）僅有頭指針的單循環(huán)鏈表C）雙鏈表D）僅有尾指針的單循環(huán)鏈表19.與單鏈表相比，雙鏈表的優(yōu)點之一是 。A）向前后兩個方向順序訪問相鄰結(jié)點更方便B）可以進行隨機訪問C）插入、刪除操作更簡單D）使用的空間更小2

3、0.鏈表不具備的特點是 。 A）所需空間隨線性表長度的變化而變化B）可隨機訪問指定下標的元素C）插入和刪除不需要移動元素D）不必事先估計存儲空間21.設對一組數(shù)據(jù)的處理具有“后進先出”的特點，則應采用的最佳數(shù)據(jù)結(jié)構(gòu)是 。A）隊列B）棧C）順序表D）二叉樹22.若進棧序列為3、5、7、9，進棧和出?？纱┎暹M行，則不可能的出棧序列是 。 A）7，5，3，9B）9，5，7，3C）9，7，5，3D）7，5，9，323.設用一維數(shù)組Am存儲棧，令Am-1為棧底，t指示當前棧頂?shù)奈恢?。如果棧不空，則出棧時應使 。A）t=t+1B）t=t-1C）t=m-1D）不改變t24.設用一維數(shù)組Am存儲棧，令A0為棧

4、底，top指示當前棧頂?shù)奈恢?，當把棧清空時所要執(zhí)行的操作是 。A）top-B）top=0C）top=-1D）top=m-125.設棧s的初始狀態(tài)為空，如果進棧序列為1、2、3、4、5、6，出棧序列3、2、5、6、4、1，則s的容量至少是 。A）6B）4C）2D）326.設棧S最多能容納4個元素，現(xiàn)有A、B、C、D、E、F六個元素按順序進棧，以下可能的出棧序列是 。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鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是 。A）插入操作更加方便B）通常不會出現(xiàn)棧滿的情況C）不會出現(xiàn)?？盏那闆rD）刪除操作更

5、加方便28在完成出棧操作時， 。A）必須判斷棧是否滿B）要判別棧元素的類型C）必須判斷棧是否空D）不必做任何判斷29.已知棧的入棧序列是1、2、3、n，出棧序列是e1、e2、en，若e1=n，則ei為 。 A）iB）n-i+1C）n-iD）不能確定30.在解決計算機主機與打印機之間速度不匹配問題時，通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，打印機則從該緩沖區(qū)取出數(shù)據(jù)打印，該緩沖區(qū)應該是一個 結(jié)構(gòu)。 A）棧B）隊列C）線性表D）數(shù)組31. 不是隊的基本運算。 A）向隊尾插入一個元素B）讀隊頭元素C）刪除隊中第i個元素D）判隊是否為空32當以順序方式存儲隊列時，解決“假溢出”

6、較為有效的方法是采用 。A）順序隊列B）鏈式隊列C）順序循環(huán)隊列D）三種都可以33.設數(shù)組Q用于存放循環(huán)隊列中的元素，同時用f指示當前隊頭元素的位置，r指示當前隊尾元素的下一個位置。假定隊中元素個數(shù)總小于m，則計算隊列中元素個數(shù)的公式為 。A）(m+r-f)%mB）r-f C）m-(f-r)D）(m+(f-r)%m34.若用一個大小為10的一維數(shù)組存儲順序循環(huán)隊列，且當前rear和front的值分別為4和8，當從隊列中刪除3個元素再加入2個元素后，rear和front的值分別是 。A）無法完成要求的操作B）1和6C）7和0C）11和635.棧和隊列都是運算受限的線性表，它們的共同點是 。A）只

7、允許在端點處插入和刪除元素B）元素都是后進先出C）元素都是先進先出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.設有nn階的對稱矩陣A，為節(jié)省存儲空間，只將主對角線及主對角線之上的元素按行優(yōu)先順序存放到一維數(shù)組B中，則數(shù)組B的最小容量是 。 A）nnB）(n+1)/2C）n2/2D）n(n+1)/

8、240.上題中，存儲矩陣A上三角中任意元素aij(0ijn-1)的B數(shù)組元素的下標為 。 A）i+jB）i(i+1)/2+jC）i(2n-i-1)/2+j D）in+j41.若把三對角矩陣帶狀區(qū)域中的元素按行優(yōu)先順序存放在一維數(shù)組B中，則存儲處于帶狀區(qū)域上的元素aij(|i-j|1)的數(shù)組B中的元素下標為 。 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）長度相等且對應位置的字符相同C）長度相等且前面若干個對

9、應位置的字符相同D）前面若干個對應位置的字符相同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.B3

10、0.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)在計算機中的具體實現(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. 請說明評價排序算法的好壞的兩個標準。答

11、：執(zhí)行算法所需要的時間；執(zhí)行算法所需要的空間。3. 如果一個線性表中元素的總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取表中指定位置的元素，對該線性表應選用何種存儲結(jié)構(gòu)？為什么？答：應選用順序存儲結(jié)構(gòu)。因為，在以順序方式存儲線性表時，線性表中元素的存儲順序與邏輯順序相一致，根據(jù)元素的下標可以很快地找到它的存儲位置。4.一個理發(fā)店有兩名理發(fā)師，一名理發(fā)師專為年紀最大的顧客服務，另一名理發(fā)師為進入理發(fā)店時間最長的顧客服務，進入理發(fā)店的顧客根據(jù)到達的時間先后順序都排入一個隊列。假設用程序來模擬理發(fā)店顧客隊列的變化情況，該顧客隊列在邏輯上可視為哪種數(shù)據(jù)結(jié)構(gòu)？要存儲相關(guān)信息應采用哪一種存

12、儲結(jié)構(gòu)？為什么？答：線性表，因為顧客出隊沒有限定在一端；鏈式存儲結(jié)構(gòu)，因為新來的顧客要加入隊列，接受理發(fā)師服務的顧客要離開隊列，對顧客隊列這個線性表來說，需要經(jīng)常的插入和刪除操作。5. 單鏈表中設置頭結(jié)點的作用是什么？答：設置頭結(jié)點后，由于頭指針總是指向頭結(jié)點，所以在實現(xiàn)對單鏈表的操作時不必區(qū)分空表和非空表，對開始結(jié)點的操作與對其他結(jié)點的操作也相同，這樣，可簡化處理。6. 設棧S的初始狀態(tài)為空，隊列Q的初始狀態(tài)為 隊頭隊尾a1 a2 a3 a4對棧S和隊列Q進行以下操作：1） Q中元素依次出隊，并壓入棧S中，直至Q為空。2） 依次彈出S中的元素并進入Q，直至S為空。請畫出在上述操作后隊列Q的狀

13、態(tài)。隊頭隊尾a4 a3 a2 a1答：7.在以順序方式存儲隊列時，會出現(xiàn)“假溢出”現(xiàn)象，清解釋這一現(xiàn)象，并說明解決“假溢出”的方法及其原理。答：“假溢出”是指存儲隊列的空間中還有空余，但不能進行入隊操作，它是由隊列的操作方式?jīng)Q定的。解決“假溢出”的方法有：1）建立一個足夠大的存儲空間，但這樣會造成空間的浪費。2）采用循環(huán)隊列方式。把存儲隊列的一維空間看成是一個首尾相接的圓環(huán)，這樣就可以實現(xiàn)對由于元素出隊而空出來的空間的循環(huán)使用。3）采用平移元素的方法。每當出現(xiàn)“假溢出”時，將隊列中所有元素平移，使當前隊頭元素位于數(shù)組的最前端，并修改隊頭和隊尾指示器。此方法效率很低。8.設用一維數(shù)組Am存儲循環(huán)

14、隊列，只設置一個隊頭指示器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”的人立即站到隊的最右端，此過程反復進行，直到n個人都已出列。設已知n個人原來在隊列中的順序，以下程序可求出他們出列的順序。例如，設n=6，初始順序為1

15、、2、3、4、5、6，則出列順序為1、3、5、2、6、4。 算法說明:此問題可利用隊列結(jié)構(gòu)處理。設一維數(shù)組p存放循環(huán)隊列，f和r分別為隊列的隊頭和隊尾指示器，首先讓n個人的初始序號依次入隊，然后反復執(zhí)行以下操作，直到隊列為空。 (1)輸出隊頭元素，并刪除之。 (2)若剛剛離隊的元素值在當時的隊列中最大，則記錄下當前隊列中最大元素值，否則將隊頭元素插入到隊尾。 程序如下: #include 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+)

16、p (1) =i; r=(r+1)%N; do int t=pf; coutt ; f= (2) ; if(t=qm)qm-; else (3) =pf; r= (4) ; f= (5) ; while(f!=r); coutendl; return 0; 答：(1)r (2)(f+1)%N (3)pr (4)(r+1)%N (5)(f+1)%N2.以下函數(shù)的功能是，將一維整型數(shù)組A中所有奇數(shù)移到所有偶數(shù)之前。算法說明：可以設置兩個下標變量i 和j，它們的初值分別為0和n-1。從數(shù)組的兩端開始，讓i向右，j向左對數(shù)組中元素進行掃描，若Ai為偶數(shù)，Aj為奇數(shù)，則交換Ai和Aj。當i和j重合時，算

17、法結(jié)束。void oddbefore(int A,int n)int i,j,t;i=0; j=n-1;while(ij)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）(ij)（2）(ij)（3）ij3.設一維數(shù)組A中有n個元素，以下函數(shù)實現(xiàn)從A中刪除值在x到y(tǒng)（x=y）之間的所有元素。算法說明：從A0開始向后掃描A中元素，用k記錄滿足刪除條件的元素個數(shù)，對不滿足刪除條件的元素，將其前移k個位置。templatevoid de

18、lall(T A,int &n,T x,T y)int i=0,k=0;while(i=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)

19、 =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(jn) if( (3) ) Ai=Aj; Aj=0; i+; (4) ; 答： (1)i0;j-) aj=aj-1; （3） ; 答：（1）im（2）j=n-1 （3）

20、a0=x; 6.一維數(shù)組A中有n個有序的元素，以下函數(shù)實現(xiàn)刪除數(shù)組中重復的元素，并返回刪除重復元素后數(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)in (2)i+ (3)k+17Reverse是在單鏈表類Chain中增加的成員函數(shù)，它的功能是在原地實現(xiàn)表元素的反轉(zhuǎn)。templatevoid Chain:Reverse() Node *current = head-next, /指向當前處理的結(jié)點*next,/ 指

21、向當前結(jié)點的直接后繼*last = 0;/ 指向反轉(zhuǎn)后當前結(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。templatebool Chain:IsSorted() const if (length=0) re

22、turn true; / 表空 Node *current = head-next, /指向當前處理的結(jié)點 *next = current-next; /指向當前結(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ù)，其功能是刪除單鏈表中值相同的重復結(jié)點。templatevoid Chain:Del()Node *p,*pre,*q

23、;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表進行如下操作：刪去那些既在B表又在C表中出現(xiàn)的元素。在以下實現(xiàn)上述操作的函數(shù)中，假定線性表以順序方式存儲。template void SeqList_Delete(SeqList &A,SeqLis

24、t &B,SeqList &C)int i,j,k;i=j=k=0;T a,b,c,x;while(iA.Length()&jB.Length()&kC.Length()B.Find(j,b);C.Find(k,c);if(bc) （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)&ac11.以下函數(shù)用于檢驗一個表達式中括號是否匹配。如果匹配返回1，否則返回0。設表達式中只

25、使用了括號()和方括號，表達式在一維數(shù)組exp中。 算法說明:為檢查表達式中括號的匹配情況，可設置一個棧s。從左到右掃描表達式，若當前字符為左括號，則將其壓入棧s中。若當前字符為右括號，則檢查它是否與棧頂?shù)淖罄ㄌ栂嗥ヅ洹Ｈ粝嗥ヅ?，則刪去這一對括號;不相匹配，則表示表達式中括號不匹配。若掃描完表達式時棧為空，則說明表達式中括號是匹配的，否則是不匹配的。函數(shù)中使用變量flag作為括號匹配的標志，flag為1表示匹配，flag為0表示不匹配。 程序如下: const int MaxSize 100 int matching(char expMaxSize) char sMaxSize; int to

26、p=-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)fla

27、g & top=-112.編寫一個函數(shù)，利用隊列和棧的基本運算將指定隊列中的元素進行逆轉(zhuǎn)。算法說明：利用一個臨時棧tempst，將指定隊列que中所有元素出隊并入棧到tempst，然后再將棧tempst中的所有元素出棧并入隊到que，此時，隊列que中的元素已發(fā)生逆轉(zhuǎn)。在以下函數(shù)中使用了STL的容器適配器定義隊列和棧。程序如下：#include #include using namespace std;template void reverse_que(queue &que)T x;stack tempst;while( （1） )x=que.front();/取隊頭元素到xtempst.pu

28、sh(x);/x入棧 （2） ;while(!tempst.empty()/當棧不為空時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) ;

29、 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列中值最小的元素，

30、則稱該元素為矩陣的一個鞍點。編寫函數(shù)求出mn階矩陣A的所有鞍點。為簡單起見，這里假定每行和每列中的元素各不相同。算法說明：先求出每行值最小的元素，放入一維數(shù)組min之中，再求出每列值最大的元素，放入一維數(shù)組max之中，比較min和max中的元素，如果mini和maxj相等，則說明Aij是一個鞍點。 #include 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;im;i+)mini= （1） ;for(j=1;jn;j+)if(

31、（2） )mini=Aij;for(j=0;jn;j+)maxj=A0j;for(i=1;imaxj)maxj=Aij;for(i=0;im;i+)for(j=0;jn;j+)if( （3） )couti , j : Aijendl; （4） ;if(have=0)cout沒有鞍點!n;答： （1）Ai0（2）Aijmini（3）mini=maxj （4）have=116.設稀疏矩陣A采用三元組表示，編寫函數(shù)求其轉(zhuǎn)置矩陣B，要求B也采用三元組表示。算法說明：在稀疏矩陣的三元組表示中，非0元素按行優(yōu)先順序存放。為保證轉(zhuǎn)置后的矩陣在B中按行優(yōu)先順序存放，需要在A中首先找出下標為0列的所有元素（它們

32、是轉(zhuǎn)置矩陣下標為0行的非0元素），將它們依次存放在B中。按此方法逐列處理即可。程序如下：template 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(t0)q=1;for(col=0;coln;col+)for(p=1;pt;p+)if( （3） )Bq0=Ap1;Bq1=Ap0;Bq2=Ap2; q+;答：（1）n或A00（2）m或A01（3）Ap1=col17.設mn階的稀疏矩陣A和 nl

33、階的稀疏矩陣B均采用三元組表示，編寫函數(shù)計算C=AB，要求C也采用三元組表示。算法說明：為通過給定的行下標i和列下標j找出原矩陣的對應元素，這里設計了一個函數(shù)value，如果在三元組中找到該元素，則返回其值，否則，返回0。template 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 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;im;i

34、+)for(j=0;jl;j+) （2） ;for(k=0;k0)的完全二叉樹中，第h-1層上包含的結(jié)點個數(shù)為 。A）不確定 B）2h C）2h-1 D）2h-1+113.對于一個有n個結(jié)點的二叉樹，當它為一棵 時高度最小。A）單支樹B）完全二叉樹C）二叉排序樹D）哈夫曼樹14.把一棵含70個結(jié)點的完全二叉樹以順序方式存儲在一維數(shù)組A中，該完全二叉樹中編號為26的結(jié)點的左子女存放在中 。A）A53 B）A54 C.A52 D）該結(jié)點設有左子女15.在以鏈接方式存儲一棵具有n個結(jié)點的二叉樹時，對應二叉鏈表中指針域的總數(shù)是 。A）2n個B）n個C）n-1個D）n+1個 16.設F是由T1、T2、T

35、3三棵樹組成的森林，與F對應的二叉樹為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.設森林F對應的二叉樹為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)

36、造出種不同的形態(tài)的樹 。 A）2B）3C）4D）521.由三個結(jié)點可以構(gòu)造出種不同的形態(tài)的二叉樹 。A）2B）3C）4D）522.設二叉樹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.在一個

37、圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 倍。A）1/2B）4C）1D）227.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 倍。A）1/2B）4C）1D）228.設無向圖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個頂點的完全無向圖應有 條邊。A）12B）16C）20D）630.對于一個具有n個頂點的無向圖，如果采用鄰接矩陣表示，則相應的矩陣大小是 。A）n(n+1)B）(n-1)(n-1)C) n2D) n(n-1)31.在一個圖G的鄰接表表示中，每個頂點的鄰接表中包含的

38、結(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ù)等于第

39、i列上非零元素的個數(shù)D） 矩陣中非全零行的行數(shù)等于圖中頂點數(shù)36.設對有向圖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)的拓撲序列中，如果頂點Vi在Vj之前，則下列情況中不可能出現(xiàn)的是 。 A）Vi，Vj是圖中的邊B）圖中有一條從Vi到Vj的路徑