數(shù)據(jù)結(jié)構(gòu)各章習題無答案給學生用

1、數(shù)據(jù)結(jié)構(gòu)習題第 1 章概述一、單項選擇題1.數(shù)據(jù)結(jié)構(gòu)是指（ ）。A.數(shù)據(jù)元素的組織形式B.數(shù)據(jù)類型D.數(shù)據(jù)定義C.數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)在計算機器內(nèi)表示時，物理地址與邏輯地址不相同的，稱之為（B.邏輯結(jié)構(gòu)）。A.結(jié)構(gòu)C.鏈式結(jié)構(gòu)D.順序間存在一種（ ）。結(jié)構(gòu)3.樹形結(jié)構(gòu)是數(shù)據(jù)元A.一對一關(guān)系 C.多對一關(guān)系設語句 x+的時間是for(i=1; i<=n; i+) for(j=i; j<=n; j+)x+;B.多對多關(guān)系D.一對多關(guān)系時間，則以下語句的時間復雜度為（ ）。4.B.O( n 2 )D.O( n 3 )A.O(1)C.O(n)5.算法分析的目的是（1），算法分析的兩個主要方面是

2、（2）。（1） A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 C.分析算法的效率以求改進（2） A.空間復雜度和時間復雜度C.可讀性和文B.研究算法中的輸入和輸出關(guān)系D.分析算法的易懂性和文B.正確性和簡明性D.數(shù)據(jù)復雜性和程序復雜性6. 計算機算法指的是（1），它具備輸入，輸出和（2）等五個特性。（1） A.計算方法C.解決問題的有限運算序列（2） A.可行性，可移植性和可擴充性C.確定性，有窮性和穩(wěn)定性7. 數(shù)據(jù)在計算機內(nèi)有鏈式和順序兩種要（ ）。B.排序方法D.調(diào)度方法B.可行性，確定性和有窮性D.易讀性，穩(wěn)定性和安全性方式，在空間使用的靈活性上，鏈式比順序A.低8. 數(shù)據(jù)結(jié)構(gòu)作為一門A.1946B.高C.

3、相同D.不好說的課程出現(xiàn)是在（ ）年。B.1953C.1964D.19689. 數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點（ ）。A.正確C.前半句對，后半句錯10. 計算機內(nèi)部數(shù)據(jù)處理的基本B.錯誤D.前半句錯，后半句對是（ ）。A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)項D.數(shù)據(jù)庫二、填空題1. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是和。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)， 分別是、1數(shù)據(jù)結(jié)構(gòu)習題 和。3. 線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 的。4. 一個算法的效率可分為效率和效率。5. 在樹型結(jié)構(gòu)中， 樹根結(jié)點沒有結(jié)點， 其余每個結(jié)點的有且只有 個前趨驅(qū)結(jié)點；

4、可以。點沒有結(jié)點；其余每個結(jié)點的后續(xù)結(jié)點6. 在圖型結(jié)構(gòu)中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以。7. 線 性 結(jié) 構(gòu) 中 元間 存 在關(guān) 系 ； 樹 型 結(jié) 構(gòu) 中 元間 存 在 關(guān)系；圖型結(jié)構(gòu)中元間存在關(guān)系。8. 下面程序段的時間復雜度是。for(i=0;i<n;i+) for(j=0;j<n;j+)Aij=0;9. 下面程序段的時間復雜度是。i=s=0; while(s<n) i+;s+=i;10. 下面程序段的時間復雜度是。s=0;for(i=0;i<n;i+) for(j=0;j<n;j+)s+=Bij;sum=s;11. 下面程序段的時間復雜度是。i=

5、1;while(i<=n) i=i*3;12. 衡量算法正確性的標準通常是。13. 算法時間復雜度的分析通常有兩種方法，即和的方法，通常我們對算法求時間復雜度時，采用后法。三、求下列程序段的時間復雜度。1.x=0;for(i=1;i<n;i+) for(j=i+1;j<=n;j+)x+;x=0;for(i=1;i<n;i+) for(j=1;j<=n-i;j+)x+;int i,j,k; for(i=0;i<n;i+)2.3.2數(shù)據(jù)結(jié)構(gòu)習題for(j=0;j<=n;j+) cij=0;for(k=0;k<n;k+) cij=aik*bkji=n-

6、1; while(i>=0)&&Ai!=k)j-;return (i); fact(n) if(n<=1)return (1); elsereturn (n*fact(n-1);4.5.第 2、3 章線性表一、單項選擇題1. 線性表是。A一個有限序列，可以為空C一個無限序列，可以為空B一個有限序列，不可以為空D一個無限序列，不可以為空2. 在一個長度為 n 的順序表中刪除第 i 個元素(0<=i<=n)時，需向前移動個元素。An-iBn-i+lCn-i-1Di3. 線性表采用鏈式A必須是連續(xù)的時，其地址。B一定是不連續(xù)的C部分地址必須是連續(xù)的D連續(xù)與否均

7、可以4. 從一個具有 n 個結(jié)點的單鏈表中查找其值等于 x 的結(jié)點時，在查找 個元素結(jié)點。的情況下，需平均比較An/2BnC（n+1）/2D（n-1）/25. 在雙向循環(huán)鏈表中，在 p 所指的結(jié)點之后s 指針所指的結(jié)點，其操作是。Ap->next=s;s->prior=p;p->next->prior=s; s->next=p->next;Bs->prior=p; p->next=s; p->next=s; s->prior=p;s->prior=p;s->next=p->next; p->next->p

8、rior=s; p->next->prior=s; s->next=p->next;s->next=p->next;CDp->next->prior=s; p->next=s;6. 設單鏈表中指針 p 指向結(jié)點 m，若要刪除 m 之后的結(jié)點（若存在），則需修改指針的操作為 。3數(shù)據(jù)結(jié)構(gòu)習題Ap->next=p->next->next;Cp=p->next->next;Bp=p->next;Dp->next=p;7. 在一個長度為 n 的順序表中向第 i 個元素(0< i<n+l )之前個

9、元素。一個新元素時，需向后移動 An-iBn-i+lCn-i-1Di8. 在一個單鏈表中，已知 q 結(jié)點是p 結(jié)點的前趨結(jié)點，若在 q 和p 之間As->next=p->next;p->next=s Bq->next=s;s->next=pCp->next=s->next;s->next=p Dp->next=s;s->next=q9. 以下關(guān)于線性表的說法不正確的是。A. 線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、等不同類型。B. 線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。C. 線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。D存在這樣的

10、線性表：表中各結(jié)點都沒有直接前趨和直接后繼。s 結(jié)點，則須執(zhí)行10. 線性表的順序A. 隨機存取結(jié)構(gòu)是一種的結(jié)構(gòu)。B順序存取C索引存取D散列存取11. 在順序表中，只要知道，就可在相同時間內(nèi)求出任一結(jié)點的地址。A基地址C向量大小B結(jié)點大小D基地址和結(jié)點大小12. 在等概率情況下，順序表的操作要移動結(jié)點。A全部C三分之一B一半D四分之一13. 在運算中，使用順序表比鏈表好。AC根據(jù)序號查找B刪除D根據(jù)元素值查找14. 在一個具有 。AO(1) CO(n2)n個結(jié)點的有序單鏈表中一個新結(jié)點并保持該表有序的時間復雜度是BO(n)DO(log2n)15. 設有一個棧，元素的進棧次序為 A, B, C,

11、 D, E,下列是不可能的出棧序列。AA, B, C, D, ECE, A, B, C, DBB, C, D, E, ADE, D, C, B, A16. 在一個具有 n 個單元的順序棧中，假定以地址低端（即 0 單元）作為棧底，以 top 作為棧頂指針，當做出棧處理時，top 變化為。Atop 不變Btop=0Ctop-Dtop+17. 向一個棧頂指針為 hs 的鏈棧中一個 s 結(jié)點時，應執(zhí)行。A. hs->next=s;Bs->next=hs;hs=s;Cs->next=hs->next;hs->next=s;Ds->next=hs; hs=hs->

12、;next;18. 在具有 n 個單元的順序斷隊滿的條件為。Arearn= = front的循環(huán)隊列中，假定 front 和 rear 分別為隊頭指針和隊尾指針，則判B（front+l）n= = rear4數(shù)據(jù)結(jié)構(gòu)習題Crearn -1= = front19. 在具有 n 個單元的順序斷隊空的條件為。Arearn= = frontCrear= = frontD(rear+l)n= = front的循環(huán)隊列中，假定 front 和 rear 分別為隊頭指針和隊尾指針，則判Bfront+l= rearD(rear+l)n= front20. 在一個鏈隊列中，假定 front 和 rear 分別為隊

13、首和隊尾指針，則刪除一個結(jié)點的操作為。Afront=front->nextCrear=front->nextBrear=rear->nextDfront=rear->next二、填空題1.2.3.4.線性表是一種典型的結(jié)構(gòu)。在一個長度為 n 的順序表的第 i 個元前一個元素，需要后移個元素。順序表中邏輯上相鄰的元素的物理位置。要從一個順序表刪除一個元素時，被刪除元后的所有元素均需一個位置，移動過程是從向依次移動每一個元素。5.性表的順序中，元間的邏輯關(guān)系是通過決定的；性表的中，元間的邏輯關(guān)系是通過決定的。6. 在雙向鏈表中，每個結(jié)點含有兩個指針域，一個指向結(jié)點，另一個指

14、向結(jié)點。7. 當對一個線性表經(jīng)常進行存取操作，而很少進行和刪除操作時，則采用 結(jié)構(gòu)為宜。相反，當經(jīng)常進行的是和刪除操作時，則采用 結(jié)構(gòu)為宜。8. 順序表中邏輯上相鄰的元素，物理位置相鄰，單鏈表中邏輯上相鄰的元素，物理位置 相鄰。9. 線性表、棧和隊列都是結(jié)構(gòu)，可以性表的位置和刪除元素；對于棧只能在位置和刪除元素；對于隊列只能在位置元素和在位置刪除元素。10. 根據(jù)線性表的鏈式結(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表可分為和；而根據(jù)指針的聯(lián)接方式，鏈表又可分為和。11. 在單鏈表中設置頭結(jié)點的作用是。12. 對于一個具有 n 個結(jié)點的單鏈表，在已知的結(jié)點 p 后一個新結(jié)點的時間復雜度為，在給定值為 x

15、 的結(jié)點后一個新結(jié)點的時間復雜度為。13. 對于一個棧作進棧運算時，判別棧是否為，作退棧運算時，判別棧是否為 ，當棧中元素為 m 時，作進棧運算時發(fā)生上溢，則說明棧的可用最大容量為。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時， 兩棧的 分別設在這片內(nèi)存空間的兩端，這樣只有當時才產(chǎn)生上溢。14. 設有一空棧，現(xiàn)有輸入序列 1，2，3，4，5，經(jīng)過 push, push, pop, push, pop, push, push 后，輸出序列是。15. 無論對于順序 。三、簡答題還是鏈式的棧和隊列來說，進行或刪除運算的時間復雜度均相同為1.2.3.描述以下三個概念

16、的區(qū)別：頭指針，頭結(jié)點，表頭結(jié)點。線性表的兩種結(jié)構(gòu)各有哪些優(yōu)缺點？對于線性表的兩種結(jié)構(gòu)，如果有 n 個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變，在此情況下，用哪一種結(jié)構(gòu)？為什么？4. 對于線性表的兩種結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進行和刪除操作，但要求以最快的速度存取線性表中的元素，用何種結(jié)構(gòu)？試說明理由。5數(shù)據(jù)結(jié)構(gòu)習題5.6.7.8.在單循環(huán)鏈表中設置尾指針比設置頭指針好嗎？為什么?假定有四個元素 A, B, C, D 依次進棧，進棧過程中出棧，試寫出所有可能的出棧序列。什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。下述算法的功能是什么?

17、LinkList *Demo(LinkList *L) / L 是無頭結(jié)點的單鏈表LinkList *q,*p; if(L&&L->next) q=L; L=L->next; p=L; while (p->next)p=p->next;p->next=q; q->next=NULL;return (L);四、算法設計題1.2.3.4.設計在無頭結(jié)點的單鏈表中刪除第 i 個結(jié)點的算法。在單鏈表上實現(xiàn)線性表的長 ListLength(L)運算。設計將帶表頭的鏈表逆置算法。假設有一個帶表頭結(jié)點的鏈表，表頭指針為 head，每個結(jié)點含三個域：data

18、, next 和 prior。其中data 為整型數(shù)域，next 和 prior 均為指針域?，F(xiàn)在所有結(jié)點已經(jīng)由 next 域連接起來，試編一個算法，利用 prior 域（此域初值為 NULL）把所有結(jié)點按照其值從小到大的順序起來。結(jié)構(gòu)。試編寫一個刪除表中所5. 已知線性表的元素按遞增順序排列，并以結(jié)點的單鏈表作有值大于 min 且小于 max 的元素（若表中存在這樣的元素）的算法。6. 已知線性表的元素是無序的，且以于 max 但大于 min 的元素的算法。結(jié)點的單鏈表作為結(jié)構(gòu)。設計一個刪除表中所有值小7. 假定用一個單循環(huán)鏈表來表示隊列（也稱為循環(huán)隊列），該隊列只設一個隊尾指針，不設隊首指

19、針，試編寫下列各種運算的算法：（1）向循環(huán)鏈隊列一個元素值為 x 的結(jié)點；（2）從循環(huán)鏈隊列中刪除一個結(jié)點。8. 設順序表L 是一個遞減有序表，試寫一算法，將 x其后仍保持 L 的有序性。第 4 章串一、單項選擇題1. 空串與空格字符組成的串的區(qū)別在于（）。A.沒有區(qū)別C.兩串的長度相等B.兩串的長度不相等D.兩串包含的字符不相同2. 一個子串在包含它的主串中的位置是指（ ）。A. 子串的最后那個字符在主串中的位置B. 子串的最后那個字符在主串中首次出現(xiàn)的位置C.子串的第一個字符在主串中的位置6數(shù)據(jù)結(jié)構(gòu)習題D.子串的第一個字符在主串中首次出現(xiàn)的位置下面的說法中，只有（ ）是正確的。A. 字符串

20、的長度是指串中包含的字母的個數(shù)B. 字符串的長度是指串中包含的不同字符的個數(shù)C.若T 包含在 S 中，則T 一定是S 的一個子串D.一個字符串不能說是其自身的一個子串兩個字符串相等的條件是（）。A. 兩串的長度相等B. 兩串包含的字符相同C. 兩串的長度相等，并且兩串包含的字符相同 D.兩串的長度相等，并且對應位置上的字符相同若 SUBSTR（S，i，k）表示求 S 中從第 i 個字符開始的連續(xù) k 個字符組成的子串的操作，則對于Nanjing”，SUBSTR（S，4，5）=（ ）。3.4.5.S=“A. “ijing”C. “ingNa”B. “jing”D. “ingN”6.若 INDEX

21、（S，T）表示求 T 在 S 中的位置的操作，則對于 S=“Nanjing”，T=“jing”，INDEX（S，T）=（）。A.2B.3C.4D.57. 若 REPLACE（S，S1，S2）表示用字符串 S2 替換字符串 S 中的子串 S1 的操作，則對于 S=“Nanjing”，S1=“”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。A. “NanjingShanghai”C. “ShanghaiNanjing”8. 在長度為n 的字符串 S 的第 i 個位置A.i0 C.1inB. “NanjingNanjing”D. “ShanghaiNanjing”另外一個字

22、符串，i 的合法值應該是（ ）。B. in D.1in+19. 字符串采用結(jié)點大小為 1 的鏈表作為其A. 鏈表的長度為 1B. 鏈表中只存放 1 個字符C. 鏈表的每個鏈結(jié)點的數(shù)據(jù)域中不僅只存放了一個字符D.鏈表的每個鏈結(jié)點的數(shù)據(jù)域中只存放了一個字符結(jié)構(gòu)，是指（）。二、填空題1. 計算機軟件系統(tǒng)中， 有兩種處理字符串長度的方法： 一種是， 第二種是 。2. 兩個字符串相等的充要條件是和。3. 設字符串 S1= “ABCDEF”，S2= “PQRS”，則運算 S=CONCAT（SUB（S1，2，LEN（S2），SUB（S1，LEN（S2），2）后的串值為 。4. 串是指。5. 空串是指，空格串

23、是指。三、算法設計題1. 設有一個長度為 s 的字符串，其字符順序存放在一個一維數(shù)組的第 1 至第 s 個單元中（每個單元存放一個字符）?，F(xiàn)要求從此串的第 m 個字符以后刪除長度為 t 的子串，m<s，t<(s-m)，并將刪除后的結(jié)果 在該數(shù)組的第 s 單元以后的單元中，試設計此刪除算法。2. 設 s 和 t 是表示成單鏈表的兩個串，試編寫一個找出 s 中第 1 個不在 t 中出現(xiàn)的字符（假定每個7數(shù)據(jù)結(jié)構(gòu)習題結(jié)點只存放 1 個字符）的算法。第 5 章數(shù)組和廣義表一、單項選擇題1. 設二維數(shù)組 A0m-10n-1按行優(yōu)先順序在內(nèi)存中，第一個元素的地址為 p，每個元素占k 個字節(jié)，則

24、元素 aij 的地址為（A.p +i*n+j-1*k C.p+(j-1)*n+i-1*k）。B.p+(i-1)*n+j-1*kD.p+j*n+i-1*k2. 已知二維數(shù)組 A10×10 中，元素 a20 的地址為 560，每個元素占 4 個字節(jié)，則元素 a10 的地址為（）。A.520B.522C.524D.518，則 aij 地址為（ ）。3. 若數(shù)組 A0m0n按列優(yōu)先順序A.LOC(a00)+j*m+iC.LOC(a00)+(j-1)*n+i-1B.D.LOC(a00)+j*n+i LOC(a00)+(j-1)*m+i-1在數(shù)組 Sa0(n+1)n/2中，則非零元素 aij 的

25、地址為（4. 若下三角矩陣 An×n，按列順序壓縮（設每個元素占 d 個字節(jié)）( j - 2)( j - 1)）。2A. (j-1)*n-+i-1*d( j - 2)( j - 1)2B. (j-1)*n-+i*d( j - 2)( j - 1)2C(j-1)*n-+i+1*d( j - 2)( j - 1)2D(j-1)*n-+i-2*d5.設有廣義表 D=(a,b,D)，其長度為（），深度為（C.2）。A.無窮大B.3D.56.廣義表 A=（a），則表尾為（）。A.aB.( )C.空表D.(a)7.廣義表 A=(x,(a,B),(x,(a,B),y)，則運算 head(head(

26、tail(A)的結(jié)果為（ ）。A.xB.(a,B)C.(x,(a,B)D.A8.下列廣義表用圖來表示時，分支結(jié)點最多的是（ ）。A.L=(x,(a,B),(x,(a,B),y) C.B=(x,(a,B),y)通常對數(shù)組進行的兩種基本操作是（A.建立與刪除C.查找和修改B.A=(s,(a,B) D.D=(a,B),(c,(a,B),D)）。B.索引和修改D.查找與索引9.10. 假定在數(shù)組 A 中，每個元素的長度為 3 個字節(jié)，行下標 i 從 1 到 8，列下標 j 從 1 到 10，從首地址 SA 開始連續(xù)存放在器內(nèi)，存放該數(shù)組至少需要的單元數(shù)為（ ）。8數(shù)據(jù)結(jié)構(gòu)習題A.80B.100C.24

27、0D.27011. 數(shù)組 A 中，每個元素的長度為 3 個字節(jié)，行下標 i 從 1 到 8，列下標 j 從 1 到 10，從首地址 SA開始連續(xù)存放在A.SA+141器內(nèi)，該數(shù)組按行存放時，元素 A85的起始地址為（ ）。B.SA+144C.SA+222D.SA+22512. 稀疏矩陣一般的壓縮A.二維數(shù)組和三維數(shù)組C.三元組和十字鏈表13. 若采用三元組壓縮技術(shù)方法有兩種，即（ ）。B.三元組和散列 D.散列和十字鏈表稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉(zhuǎn)置運算，這種觀點（ ）。A.正確14. 一個廣義表的表頭總是一個（B.不正確）。A.廣義表B.元素C.空表D.

28、元素或廣義表15. 一個廣義表的表尾總是一個（）。A.廣義表B.元素C.空表D.元素或廣義表16. 數(shù)組就是矩陣，矩陣就是數(shù)組，這種說法（）。A.正確C.前句對，后句錯B.錯誤D.后句對二、填空題1. 一維數(shù)組的邏輯結(jié)構(gòu)是，為和兩種不同的結(jié)構(gòu)是；對于二維或方式。數(shù)組，分2. 對于一個二維數(shù)組 Amn，若按行序為主序 。素 Aij相對于 A00的地址為，則3.4.一個廣義表為(a,(a,b),d,e,(i,j),k)，則該廣義表的長度為，深度為。一個稀疏矩陣為，則對應的三元組線性表為。é00000200ùê30úêê0ú-15

29、úê00ú0ëû5.6.一個 n×n 的對稱矩陣，如果以行為主序或以列為主序存入內(nèi)存，則其容量為。已知廣義表 A=(a,b,c),(d,e,f)，則運算 head(tail(tail(A)=。7. 設有一個 10 階的對稱矩陣 A，采用壓縮方式以行序為主序，a 00 為第一個元素，其地址為 0，每個元素占有 1 個地址空間，則 a 85 的地址為。8. 已知廣義表 Ls=(a,(b,c,d),e) ， 運用 head 和 tail 函數(shù)取出 Ls 中的原子 b 的運算是 。9. 三維數(shù)組 Rc1d1,c2d2,c3d3共含有個元素。（

30、其中：c1d1,c2d2,c3d3）10.數(shù)組A110，-26，28以行優(yōu)先的順序，設第一個元素的首地址是 100，每個元素占3 個三、長度的空間，則元素 A5，0，7的題地址為。1.2.3.4.5.數(shù)組可看作基本線性表的一種推廣，因此與線性表一樣，可以對它進行數(shù)組可以看作數(shù)據(jù)元素也是基本線性表的基本線性表。（ ）、刪除等操作。（ ）以行為主序或以列為主序?qū)τ跀?shù)組的沒有影響。（ ）對于不同的特殊矩陣應該采用不同的方式。（）采用壓縮之后，下三角矩陣的空間可以節(jié)約一半。（ ）9數(shù)據(jù)結(jié)構(gòu)習題6.7.8.9.在一般情況下，采用壓縮之后，對稱矩陣是所有特殊矩陣中空間節(jié)約最多的。（ ）矩陣不僅是表示數(shù)組，

31、而且是表示圖的重要工具。（ ）距陣中的數(shù)據(jù)元素可以是不同的數(shù)據(jù)類型。（ ）矩陣中的行列數(shù)往往是不相等的。（ ）10. 廣義表的表頭可以是廣義表，也可以是單個元素。（ ）11. 廣義表的表尾一定是一個廣義表。（ ）12.13.14.15.廣義表的元素可以是子表，也可以是單元素。（ ） 廣義表不能遞歸定義。（ ）廣義表實際上是基本線性表的推廣。（ ）廣義表的組成元素可以是不同形式的元素。（ ）第 6 章樹一、單項選擇題1. 在一棵度為 3 的則度為 0 的結(jié)點數(shù)為（A. 4，度為 3 的結(jié)點數(shù)為 2 個，度為 2 的結(jié)點數(shù)為 1 個，度為 1 的結(jié)點數(shù)為 2 個，）個。B. 5C. 6D. 72.

32、假設在一棵二中，雙分支結(jié)點數(shù)為 15，單分支結(jié)點數(shù)為 30 個，則點數(shù)為（）個。15B. 16C. 17D. 47A.假A.3.三的結(jié)點數(shù)為 50，則它的最小高度為（ ）。3B. 4C. 5D. 64.上第 4 層的結(jié)點數(shù)最多為（在一棵二A. 2用順序）。B. 4的方法將完全二C. 6D. 85.中的所有結(jié)點逐層存放在數(shù)組中 R1.n，結(jié)點 Ri若有，其的編號為結(jié)點（ ）。A.由A.R2i+1B. R2iC. Ri/2點生成一棵C. 72D. R2i-1樹，它的帶權(quán)路徑長度為（）。D. 536.分別為 3,8,6,2,5 的B. 48247.線索二A. 邏輯線索二是一種（）結(jié)構(gòu)。B. 邏輯和中

33、，結(jié)點 p 沒有C. 物理樹的充要條件是（B. p->ltag=1D. 以上都不對D. 線性）。8.A. p->lc=NULLC. p->ltag=1 且p->lc=NULL9.設 n , m 為一棵二A. n 在 m 右方C. n 是 m 的祖先上的兩個結(jié)點，在中序遍歷序列中 n 在 m 前的條件是（）。B.D.n 在 m 左方n 是 m 的子孫，那么 T 中結(jié)點的前序就是 F 中結(jié)點的（10. 如果 F 是由有序樹 T 轉(zhuǎn)換而來的二）。A. 中序11. 欲實現(xiàn)任意二結(jié)構(gòu)。A. 三叉鏈表B. 前序C.后序D. 層次序的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二采用

34、（）B. 廣義表C. 二叉鏈表D. 順序12. 下面敘述正確的是（）。10數(shù)據(jù)結(jié)構(gòu)習題A.B.C.D.二二是特殊的樹等價于度為 2 的樹完全二必為滿二二的左右子樹有次序之分13. 任何一棵二A. 不發(fā)生改變C. 不能確定的點在先序、中序和后序遍歷序列中的相對次序（B. 發(fā)生改變D. 以上都不對）。14. 已知一棵完全二的結(jié)點總數(shù)為 9 個，則最后一層的結(jié)點數(shù)為（）。A. 1B.2C. 3D. 415. 根據(jù)先序序列 ABDC 和中序序列 DBAC 確定對應的二，該二（）。A. 是完全二C. 是滿二題B. 不是完全二D. 不是滿二二、1.2.3.4.5.6.7.8.9.中每個結(jié)點的度不能超過 2

35、，所以二的前序遍歷中，任意結(jié)點均處在其二二是一種特殊的樹。結(jié)點之前。（）線索二是一種邏輯結(jié)構(gòu)。樹的總結(jié)點個數(shù)（多于 1 時）不能為偶數(shù)。的先序序列和后序序列可以唯一確定一顆二由二。樹的后序遍歷與其對應的二的后序遍歷序列相同。根據(jù)任意一種遍歷序列即可唯一確定對應的二。滿二也是完全二樹一定是完全二。10. 樹的子無序的。三、填空題1. 假樹的廣義表表示為 A（B（E），C（F（H，I，J），G），D），則該樹的度為 ，樹的深度為，終端結(jié)點的個數(shù)為，單分支結(jié)點的個數(shù)為，雙分支結(jié)點的個數(shù)為，三分支結(jié)點的個數(shù)為，C 結(jié)點的雙親結(jié)點為，其孩子結(jié)點為和結(jié)點。2. 設 F 是一個森林，B 是由 F 轉(zhuǎn)換得到的

36、二結(jié)點有個。，F(xiàn) 中有 n 個非終端結(jié)點，則 B 中右指針域為空的3. 對于一個有 n 個結(jié)點的二，當它為一棵二時具有最小高度，即為，當它為一棵具有高度，即為。4.5.6.3，9，6，2，5 的 5 個樹，則帶權(quán)路徑長度為。由帶點一棵在一棵二叉排序樹上按遍歷得到的結(jié)點序列是一個有序序列。對于一棵具有 n 個結(jié)點的二，當進行時，其二叉鏈表中的指針域的總數(shù)為 個，其中個用于孩子結(jié)點，個空閑著。7. 在一棵二中，度為 0 的結(jié)點個數(shù)為 n0，度為 2 的結(jié)點個數(shù)為 n2，則 n0=。8. 一棵深度為 k 的滿二的結(jié)點總數(shù)為，一棵深度為 k 的完全二值為，最大值為。的結(jié)點總數(shù)的最小9. 由三個結(jié)點的二

37、，共有種不同的形態(tài)。10. 設高度為 h 的二 。中只有度為 0 和度為 2 的結(jié)點，則此類二中所包含的結(jié)點數(shù)至少為11. 一棵含有 n 個結(jié)點的 k，形態(tài)達到最大深度，形態(tài)達到最小深度。12. 對于一棵具有 n 個結(jié)點的二，若一個結(jié)點的編號為 i(1in)，則它的結(jié)點的編號11數(shù)據(jù)結(jié)構(gòu)習題為，右孩子結(jié)點的編號為，雙親結(jié)點的編號為。13. 對于一棵具有 n 個結(jié)點的二，采用二叉鏈表時，鏈表中指針域的總數(shù)為個，其中個用于孩子結(jié)點，個空閑著。14.15.16.17.18.19.指的二。空二指，最小的指。的鏈式結(jié)構(gòu)有和兩種。三叉鏈表比二叉鏈表多一個指向的指針域。線索是指。線索鏈表中的 rtag 域值

38、為時，表示該結(jié)點無右孩子，此時域為指向該結(jié)點后繼線索的指針。20. 本節(jié)中我們學習的樹的結(jié)構(gòu)有、和。四、應用題1. 已知一棵樹邊的集合為<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>，請畫出這棵樹，并回答下列問題：（1）哪個是根結(jié)點？（2）哪些是點？（3） 哪個是結(jié)點 g 的雙親？（4） 哪些是結(jié)點 g 的祖先？（5） 哪些是結(jié)點 g

39、 的孩子？（6） 哪些是結(jié)點 e 的孩子？（7） 哪些是結(jié)點 e 的兄弟？哪些是結(jié)點 f 的兄弟？（8） 結(jié)點b 和 n 的層次號分別是什么？（9） 樹的深度是多少？（10） 以結(jié)點 c 為根的子樹深度是多少？2.3.4.一棵度為 2 的樹與一棵二有何區(qū)別。試分別畫出具有 3 個結(jié)點的二的所有不同形態(tài)？：ABCDEFGHIJKL，寫出該二已知用一維數(shù)組存放的一棵完全二的先序、中序和后序遍歷序列。5. 一棵深度為 H 的滿 k有如下性質(zhì)：第 H 層上的結(jié)點都是點，其層上每個結(jié)點都有 k 棵非空子樹，如果按層次自上至下，從左到右順序從 1 開始對全部結(jié)點編號，回答下列問題：（1） 各層的結(jié)點數(shù)目是

40、多少？（2） 編號為n 的結(jié)點的父結(jié)點如果存在，編號是多少？（3） 編號為n 的結(jié)點的第 i 個孩子結(jié)點如果存在，編號是多少？（4）編號為n 的結(jié)點6. 找出所有滿足下列條件的二的條件是什么？其右兄弟的編號是多少？：（1） 它們在先序遍歷和中序遍歷時，得到的遍歷序列相同；（2） 它們在后序遍歷和中序遍歷時，得到的遍歷序列相同；（3） 它們在先序遍歷和后序遍歷時，得到的遍歷序列相同；7. 假設一棵二后序遍歷序列。8. 假設一棵二后序遍歷序列。的先序序列為 EBADCFHGIKJ，中序序列為 ABCDEFGHIJK，請寫出該二的的后序序列為 DCEGBFHKJIA，中序序列為 DCBGEAHFIJ

41、K，請寫出該二的9. 給出如圖 5-14 所示的森林的先根、后根遍歷結(jié)點序列，然后畫出該森林對應的二。10給定一組（5，9，11，2，7，16），試設計相應的樹。12數(shù)據(jù)結(jié)構(gòu)習題AGKLCIBHMDEFJON圖 5-14五、算法設計題1. 一棵具有n 個結(jié)點的完全二遍歷的算法。以一維數(shù)組作為結(jié)構(gòu)，試設計一個對該完全二進行先序2. 給用二叉鏈表表示的二，其中的指針 t 指向根結(jié)點，試寫出從根開始，按層次遍歷二的算法，同層的結(jié)點按從的次序。中結(jié)點 P 的右子3.4.寫出在中序線索二一個結(jié)點 s 的算法。二，用二叉鏈表表示，其根指針為 t，試寫出求該二中結(jié)點 n 的雙親結(jié)點的算給法。若沒有結(jié)點 n

42、或者該結(jié)點沒有雙親結(jié)點，分別輸出相應的信息；若結(jié)點 n 有雙親，輸出其雙親的值。第 7 章圖一、單項選擇題1. 在一個具有 n 個頂點的有)。，若所有頂點的出度數(shù)之和為 s，則所有頂點的入度數(shù)之和為(A. s2. 在一個具有)。A. sB. s-1n 個頂點的有C. s+1D. n，若所有頂點的出度數(shù)之和為 s，則所有頂點的度數(shù)之和為(B. s-1C. s+1D. 2s3.在一個具有 n 個頂點的無，若具有 e 條邊，則所有頂點的度數(shù)之和為()。A. nB. eC. n+eD. 2e)。4.在一個具有 n 個頂點的無向完全圖中，所含的為(A. nB. n(n-1)C. n(n-1)/2D.n(

43、n+1)/2)。n(n+1)/25.在一個具有 n 個頂點的有向完全圖中，所含的為(A. n在一個無A. kB. n(n-1)C. n(n-1)/2D.6.，若兩頂點之間的路徑長度為 k，則該路徑上的頂點數(shù)為()。B. k+1C. k+2D. 2k7.對于一個具有 n 個頂點的無向連通圖，它包含的連通分量的個數(shù)為()。A. 0B. 1C. nD. n+18.若一個圖中包含有 k 個連通分量，若要按照深度優(yōu)先搜索的方法)次深度優(yōu)先搜索遍歷的算法。所有頂點，則必須調(diào)用(A. kB. 1C. k-1通圖，則至少需要(D. k+1)條邊。9.若要把 n 個頂點連接為13數(shù)據(jù)結(jié)構(gòu)習題A. nB. n+1

44、C. n-1D. 2n10. 在一個具有 n 個頂點和 e 條邊的無的鄰接矩陣中，表示邊存在的元素（又稱為有效元素）的個數(shù)為(A. n)。B. n´eD. 2´eC. e11. 在一個具有 n 個頂點和 e 條邊的有的鄰接矩陣中，表示邊存在的元素個數(shù)為()。B. n´eD. 2´eA. nC. e12.在一個具有 n 個頂點和 e 條邊的無的鄰接表中，邊結(jié)點的個數(shù)為()。B. n´eD. 2´eA. nC. e13.少為(在一個具有 n 個頂點和 e 條邊的有)。的鄰接表中，保存頂點單鏈表的表頭指針向量的大小至A. n在一個無A. 1

45、對于一個有)。A. k1對于一個有)。A. k1對于一個無B. 2nC. eD.2e)域。414.的鄰接表表示中，每個邊結(jié)點至少包含(B. 2C. 3D.15.數(shù)為(，若一個頂點的度為 k1，出度為 k2，則對應鄰接表中該頂點單鏈表中的邊結(jié)點B. k2C. k1-k2D. k1+k216.點數(shù)為(，若一個頂點的度為 k1，出度為 k2，則對應逆鄰接表中該頂點單鏈表中的邊結(jié)B. k2，下面(C. k1-k2)種說法是正確的。D. k1+k217.A. 每個頂點的入度等于出度C. 每個頂點的入度為 0B. 每個頂點的度等于其入度與出度之和D. 每個頂點的出度為 018.在一個有A. 出的鄰接表中，

46、每個頂點單鏈表中結(jié)點的個數(shù)等于該頂點的()。B. 入C. 度數(shù)D. 度數(shù)減 119.若一個圖的邊集為(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，則從頂點 A 開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能為(A. A,B,C,F,D,EC. A,B,D,C,F,E)。B. A,C,F,D,E,BD. A,B,D,F,E,C20. 若一個圖的邊集為(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，則從頂點 A 開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為(A. A,B,C,D,E,FC. A,B,D,C,E,F)。B. A,B,C,F,D,E

47、D. A,C,B,F,D,E21. 若一個圖的邊集為<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>，則從頂點 1 開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能為( A. 1,2,5,4,3C. 1,2,5,3,4)。B. 1,2,3,4,5D. 1,4,3,2,522. 若一個圖的邊集為<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>，則從頂點 1 開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為( A.

48、 1,2,3,4,5C. 1,2,4,5,3)。B. 1,2,4,3,5D. 1,4,2,5,323. 由一個具有 n 個頂點的連通圖生成的最小生成，具有(D. 2´n)條邊。A. n24. 已知一個有B. n-1C. n+1的邊集為<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>，則由該圖產(chǎn)生的一種可能的拓撲序列為()。14數(shù)據(jù)結(jié)構(gòu)習題A. a,b,c,d,eB. a,b,d,e,bC. a,c,b,e,dD. a,c,d,b,e二、填空題1. 在一個圖中，所有頂點的度數(shù)之和等于所有的倍。

49、2. 在一個具有 n 個頂點的無向完全圖中，包含有條邊，在一個具有 n 個頂點的有向完全圖中，包含有條邊。3. 假定一個有的頂點集為a,b,c,d,e,f，邊集為<a,c>, <a,e>, <c,f>, <d,c>, <e,b>, <e,d>，則出度為 0 的頂點個數(shù)為，入度為 1 的頂點個數(shù)為。4.5.6.7.8.9.在一個具有 n 個頂點的無，要連通所有頂點則至少需要條邊。表示圖的兩種結(jié)構(gòu)為和。在通圖中存在著個連通分量。圖中的一條路徑長度為 k，該路徑所含的頂點數(shù)為。若一個圖的頂點集為a,b,c,d,e,f，邊集為(a

50、,b),(a,c),(b,c),(d,e)，則該圖含有個連通分量。對于一個具有 n 個頂點的圖，若采用鄰接矩陣表示，則矩陣大小至少為´。10. 對于具有 n 個頂點和 e 條邊的有別為和。11. 在有的鄰接表和逆鄰接表表示中，每個頂點鄰接表分別 結(jié)點。和無，在它們對應的鄰接表中，所含邊結(jié)點的個數(shù)分著該頂點的所有和12. 對于一個具有 n 個頂點和 e 條邊的無，當分別采用鄰接矩陣和鄰接表表示時，求任一頂點度數(shù)的時間復雜度分別為和。13. 假定一個圖具有 n 個頂點和 e 條邊，則采用鄰接矩陣和鄰接表表示時，其相應的空間復雜度分別為和。14. 一個圖的邊集為(a,c),(a,e),(b,e),(c,d),(d,e)，從頂點 a 出發(fā)進行深度優(yōu)先搜索遍歷得到的頂點序列為，從頂點 a 出發(fā)進行廣度優(yōu)先搜索遍歷得到的頂點序列為。15. 一個圖的邊集為<a,c>,<