數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

1、WORD格式2021 2021 學(xué)年度第 2 學(xué)期"數(shù)據(jù)構(gòu)造"復(fù)習(xí)提綱一、單項選擇題題號12345678910答案CADCABABCD題號11121314151617181920答案AADAADCBAB1在數(shù)據(jù)構(gòu)造中，從邏輯上可以把數(shù)據(jù)構(gòu)造分為_ 兩類。A 動態(tài)構(gòu)造和靜態(tài)構(gòu)造B 緊湊構(gòu)造和非緊湊構(gòu)造C線性構(gòu)造和非線性構(gòu)造D 內(nèi)部構(gòu)造和外部構(gòu)造2鏈表不具有的特點是_。A 可隨機訪問任一元素B 插入、刪除不需要移動的元素C不必事先估計存儲空間D 所需空間與線性表長度成正比3假設(shè)線性表最常用的運算是存取第i 個元素及其前驅(qū)元素，那么采用_存儲方式節(jié)省時間。A 單鏈表B 雙鏈表C循

2、環(huán)單鏈表D順序表4算法分析的目的是_。A 找出數(shù)據(jù)構(gòu)造的合理性B 研究算法中的輸入和輸出關(guān)系C分析算法的效率以求改進D 分析算法的易讀性和文檔性5假設(shè)一個棧用數(shù)組data1.n 存儲，初始棧頂指針top 為 0 ，那么以下元素x 進棧的操作正確的選項是_。A top+;datatop=x;B datatop=x;top+;Ctop-;datatop=x; D datatop=x;top-;6表達式a*(b+c)-d的后綴表達式是_。A abcd*+-B abc+*d-Cabc*+d-D -+*abcd7遞歸函數(shù)f(1)=1 ， f(n)=f(n-1)+n(n 1) 的遞歸出口是 _。A f(1

3、)=1B f(1)=0Cf(0)=0D f(n)=n8將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用_保存中間結(jié)果。A 隊列B 棧C鏈表D樹9對稀疏矩陣采用壓縮存儲，其缺點之一是_。A 無法判斷矩陣有多少行、多少列B 無法根據(jù)行、列號查找某個矩陣元素C無法根據(jù)行、列號直接計算矩陣元素的存儲地址D 使矩陣元素之間的邏輯關(guān)系更加復(fù)雜10一個 n 階上三角矩陣a 按行優(yōu)先順序壓縮存放在一維數(shù)組b 中，那么 b 中的元素個數(shù)是 _。A nB n2Cn(n+1)/2D n(n+1)/2+111度為 4，高度為 h 的樹 _ 。A 至少有 h+3 個結(jié)點 B最多有4h-1 個結(jié)點C最多有 4h 個結(jié)點D

4、 至少有h+4 個結(jié)點12用雙親存儲構(gòu)造表示樹，其優(yōu)點之一是比較方便_。A 找指定結(jié)點的雙親結(jié)點B 找指定結(jié)點的孩子結(jié)點C找指定結(jié)點的兄弟結(jié)點D 判斷某結(jié)點是不是葉子結(jié)點專業(yè)資料整理WORD格式第1頁共12頁專業(yè)資料整理WORD格式13設(shè)有 13 個值，用它們組成一棵哈夫曼樹，那么該哈夫曼樹共有_個結(jié)點。A 13B12C26D 2514無向圖的鄰接矩陣是一個_。A 對稱矩陣B 零矩陣C上三角矩陣D對角矩陣15在圖的廣度優(yōu)先遍歷算法中用到一個隊列，每個頂點最多進隊_次。A 1B 2C3D不確定16在用 Prim 和 Kruskal 算法構(gòu)造最小生成樹時，前者更適合于_。A 有向圖B 無向圖C稀疏

5、圖D稠密圖17有一個有序表R1.13=1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，當(dāng)用二分查找法查找值為82的節(jié)點時，經(jīng)過_次比較后查找成功。A 1B 2C4D 818在采用分塊查找時，假設(shè)線性表中共有625 個元素，查找每個元素的概率一樣，假設(shè)采用順序查找來確定結(jié)點所在的塊，那么每塊分為_個結(jié)點最正確。A 9B25C6D 62519假設(shè) R 中有 10000 個元素，如果僅要求求出其中最大的10 個元素，那么采用 _方法最節(jié)省時間。A 堆排序B 希爾排序C快速排序D基數(shù)排序20有一組序列 48, 36, 68, 99, 75, 24, 2

6、8, 52 進展快速排序，要求結(jié)果從小到大排序，那么進展一次劃分之后的結(jié)果為 _。A 24 28 36 48 52 68 75 99B 28 36 24 48 75 99 68 52C36 68 99 48 75 24 28 52D 28 36 24 48 99 75 68 52二、填空題題號答案題號答案題號答案1問題規(guī)模2O(n)3假溢出42855462h-17關(guān)鍵活動8無環(huán)圖9RL10 基數(shù)排序1在分析算法的時間復(fù)雜度時，通常認為算法的執(zhí)行時間是_的函數(shù)。2求一個雙鏈表長度的算法的時間復(fù)雜度為_。3在實現(xiàn)順序隊的時候，通常將數(shù)組看成是一個首尾相連的環(huán)，這樣做的目的是為了防止產(chǎn)生_現(xiàn)象。4有

7、如下遞歸過程：void reverse( int m )printf("%d", n%10);if( n/10!=0 )reverse(n/10);調(diào)用語句reverse(582) 的結(jié)果是 _。5廣義表 (a, b,( ), c), d), e, (f), g)的深度是 _。6在高度為h h0的二叉樹中最多有_ 個結(jié)點。7 AOE 網(wǎng)中從源點到匯點長度最長的路徑稱為關(guān)鍵路徑，該路徑上的活動稱為_。8可以進展拓撲排序的有向圖一定是_。9輸入序列為20 ， 35 ， 30 ，構(gòu)造一棵平衡二叉樹，其中的第一次調(diào)整為_型調(diào)整。10 在排序過程中，任何情況下都不比較關(guān)鍵字大小的排序

8、方法是_。專業(yè)資料整理WORD格式第2頁共12頁專業(yè)資料整理WORD格式三、判斷題題號12345678910答案FTFFFTFTFF1如果數(shù)據(jù)元素值發(fā)生改變，那么數(shù)據(jù)的邏輯構(gòu)造也隨之改變。2在循環(huán)單鏈表中沒有為空的指針域。3順序棧中元素值的大小是有序的。4任何遞歸算法都是尾遞歸。5稀疏矩陣的特點是矩陣中元素較少。6哈夫曼樹中不存在度為1 的結(jié)點。7完全二叉樹中的每個結(jié)點或者沒有孩子或者有兩個孩子。8強連通分量是有向圖中的極大強連通子圖。9哈希沖突是指同一個關(guān)鍵字的記錄對應(yīng)多個不同的哈希地址。10 任何情況下折半插入排序都優(yōu)于直接插入排序。四、問答題1 設(shè)計一個算法，刪除一個單鏈表 L 中元素值

9、最大的結(jié)點假設(shè)這樣的結(jié)點唯一。 void delmaxnode(LinkList *&L)LinkList *p,*pre, *maxp, *maxpre; p=L->next; pre=L;maxp=p; maxpre=pre; while (p!=NULL)if (maxp->data<p->data)maxp=p;maxpre=pre;pre=p;p=p->next;maxpre->next=maxp->next;free(maxp);2一棵完全二叉樹的第 6 層設(shè)根為第 1 層有 8 個葉子結(jié)點，那么該完全二叉樹的結(jié)點個數(shù)最多是多少。完

10、全二叉樹的葉子結(jié)點只能在最下兩層，對于此題，結(jié)點最多的情況是第6 層為倒數(shù)第二層，即 16 層構(gòu)成一個滿二叉樹，其結(jié)點總數(shù)為26 -1=63 。第 6 層有 25=32 個結(jié)點，其中含 8 個葉子結(jié)點， 另外有 32-8=24個非葉子結(jié)點，它們中的每個結(jié)點都有兩個孩子結(jié)點均為第7 層的葉子結(jié)點 ，計 48 個葉子結(jié)點，這樣最多的結(jié)點個數(shù)=63+48=111 。3一個有向圖G 的鄰接表存儲如以下列圖所示，要求：專業(yè)資料整理WORD格式第3頁共12頁專業(yè)資料整理WORD格式 1給出該圖的鄰接矩陣存儲構(gòu)造； 2給出該圖的所有強連通分量。4什么是平衡二叉樹？輸入關(guān)鍵字序列16， 3 ， 7， 11 ，

11、給出構(gòu)造一棵平衡二叉樹的過程。假設(shè)一棵二叉排序樹中每個結(jié)點的左右子樹的高度最多相差1，那么稱此二叉樹為平衡二叉樹。10-10167716000013316316011專業(yè)資料整理WORD格式第4頁共12頁專業(yè)資料整理WORD格式5線性表有順序表和鏈表兩種存儲方式，不同的排序方法適合不同的存儲構(gòu)造。對于常見的內(nèi)部排序方法，說明哪些更適合于順序表，哪些更適合于鏈表？哪些兩者都適合？更適合于順序表的排序方法有希爾排序、折半插入排序、快速排序、堆排序和歸并排序。更適合于鏈表的排序方法是基數(shù)排序兩者都適合的排序方法有直接插入排序、冒泡排序和簡單排序。五、算法設(shè)計題用 Floyd 算法計算圖中任意兩個頂點

12、之間的最短路徑。void Floyd(MGraph g)int AMAXVMAXV,pathMAXVMAXV;int i,j,k;for (i=0; i<g.n; i+)for (j=0; j<g.n; j+)Aij=g.edgesij;pathij=-1;for (k=0; k<g.n; k+)for (i=0; i<g.n; i+)for (j=0; j<g.n; j+)if (Aij>Aik+Akj)Aij=Aik+Akj;pathij=k;/修改最短路徑Dispath(A,path,g.n);/輸出最短路徑專業(yè)資料整理WORD格式第5頁共12頁專業(yè)資

13、料整理WORD格式一、選擇題1研究數(shù)據(jù)構(gòu)造就是研究。A 數(shù)據(jù)的邏輯構(gòu)造B 數(shù)據(jù)的存儲構(gòu)造C 數(shù)據(jù)的邏輯和存儲構(gòu)造D 數(shù)據(jù)邏輯構(gòu)造、 存儲構(gòu)造及其數(shù)據(jù)在運算上的實現(xiàn)2鏈表不具有的特點是。A 可隨機訪問任一元素B 插入刪除不需要移動元素C 不必事先估計存儲空間D 所需空間與線性表長度成正比3設(shè)一個棧的輸入序列為1，2，3，4，那么借助一個棧所得到的輸出序列不可能是。A1，2，3，4B2，4，3，1C3，1，4，2D3，2，4，14設(shè)計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用數(shù)據(jù)構(gòu)造最正確。A 線性表的順序存儲構(gòu)造B 棧C 線性表的鏈?zhǔn)酱鎯?gòu)造D 隊列5表達式 a*(b+c)-d 的后綴表

14、達式是。Aabcd*+-Babc+*d-Cabc*+d-D-+*abcd6隊列的操作原那么是。A 先進先出B 只能進展插入C 后進先出D 只能進展刪除7判斷帶頭結(jié)點的單鏈表llist 為空的條件是。Allist->link=llistBllist=NULLCllist->link=NULLDllist!=NULL8一個具有 20個結(jié)點的完全二叉樹，其葉結(jié)點個數(shù)為。A9B10C11D129以下不屬于內(nèi)部排序的算法是。A 歸并排序B 拓撲排序C 選擇排序D 插入排序10 在一棵度為 3 的樹中，度為 3 的結(jié)點數(shù)為 2，度為 2 的結(jié)點數(shù)為 1，那么葉結(jié)點數(shù)為。A4B5C6D71234

15、5678910DACBBACBBC二、填空題1二叉樹有 50 個葉子結(jié)點，那么該二叉樹的總結(jié)點數(shù)至少是99 。2在一個長度為 n 的線性表的第 i 個元素 1 i n之前插入一個元素時，插入函數(shù)需向后移動n-i+1個元素。3假設(shè)頻繁地對線性表進展插入與刪除操作，該線性表應(yīng)采用鏈?zhǔn)酱鎯?gòu)造。4假設(shè)某線性表采用順序存儲構(gòu)造，每個元素占2 個存儲單元，首地址為是100 ，那么第 5 個元素的地址是108。5假設(shè)結(jié)點 y 是結(jié)點 x 的一棵子樹的根，那么x 稱作 y 的父結(jié)點。6一個串中包括的字符個數(shù)稱作這個串的長度。專業(yè)資料整理WORD格式第6頁共12頁專業(yè)資料整理WORD格式7一棵樹高為 h 的完

16、全二叉樹至少有 2h-1個結(jié)點，至多有2h -1個結(jié)點。8算法的復(fù)雜性分析主要從算法的時間復(fù)雜性和空間復(fù)雜性進展考慮。9數(shù)據(jù)構(gòu)造主要根據(jù)邏輯構(gòu)造和存儲構(gòu)造進展分類。10 圖的遍歷分為兩種類型：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。三、算法分析與設(shè)計題1在鏈表中，假設(shè)指針p，要在指針 p 所指的結(jié)點之后插入數(shù)據(jù)域值相繼為 a 和 b 的兩個結(jié)點，指針 s 指向結(jié)點 a。寫出實現(xiàn)上述插入操作的關(guān)鍵語句。As->next->next=p->next;專業(yè)資料整理WORD格式p->next=s;2如下列圖的一棵二叉樹，寫出對此樹的先根序列、中根序列和后根序列。先根序列： ABDEFC中根

17、序列： DEFBAC后根序列： FEDBCABCD專業(yè)資料整理WORD格式E3以5， 6， 7， 8，9，10， 15，18 ，22 作為葉結(jié)點的權(quán)值來構(gòu)造一棵Huffman 樹。F1004159192226339101115151856784請設(shè)計一個算法，求出循環(huán)表中結(jié)點的個數(shù)。int Countnode(ClinkList clist)int n ；PNode p ；p=clist->link ；n=0 ；while(p!=clist)n+ ；p=p->link ；return(+n) ； 專業(yè)資料整理WORD格式第7頁共12頁專業(yè)資料整理WORD格式一、填空題1設(shè)有一個 8

18、 階的對稱矩陣 A, 采用壓縮存儲方式 ,按行優(yōu)先順序存儲方式。 設(shè) a11 為第一個元素其存儲地址為1,假設(shè)每個元素占用1 個存儲單元64 的存儲地址為19。, 那么 a2假設(shè)頻繁地對線性表進展插入與刪除操作，該線性表應(yīng)采用鏈?zhǔn)酱鎯?gòu)造。3算法的 5 個重要特征是有窮性 、確定性、可行性、輸入和輸出。4. 每次從無序子表中取出一個元素， 然后把它插入到有序子表的適當(dāng)位置， 那么此種排序方法專業(yè)資料整理WORD格式叫做直接插入排序。專業(yè)資料整理WORD格式5設(shè)二維數(shù)組A1.M，1.N即M行N 列按行優(yōu)先順序存儲在一維數(shù)組B1.M*N中，專業(yè)資料整理WORD格式那么二維數(shù)組元素Ai,j在一維數(shù)組

19、B 中的下標(biāo)為(i-1)*N+j。專業(yè)資料整理WORD格式6在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找( 二分查找) 方法查找元素24，專業(yè)資料整理WORD格式需要進展4次元素之間的比較。專業(yè)資料整理WORD格式7一棵樹高為 h 的完全二叉樹至少有2 h-1個結(jié)點，至多有2 h-1 個結(jié)點。8由權(quán)值分別為11,8,6,2,5的葉結(jié)點生成一棵Huffman 樹，它的帶權(quán)路徑長度為71 。9對關(guān)鍵字序列 (52,80,63,44,48,91)一趟快速排序后的結(jié)果(48 ，44，52，63，80，91) 。二、單項選擇題題號12345678910答案DAAAC

20、BDBAC題號111213141516 17181920答案CAADDCDAAC1. 數(shù)據(jù)構(gòu)造是指。A. 一種數(shù)據(jù)類型B. 數(shù)據(jù)的存儲構(gòu)造C. 一組性質(zhì)一樣的數(shù)據(jù)元素的集合D. 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2. 以下算法的時間復(fù)雜度為。void fun(int n)int i=1;第8頁共12頁專業(yè)資料整理WORD格式while (i<=n)i+;A. O(n)B. O(n )C. O(nlog 2n)D. O(log 2n)3. 在一個長度為 n 的有序順序表中刪除元素值為x 的元素時， 在查找元素 x 時采用二分查找， 此時的時間復(fù)雜度為。A. O(n)B. O(n

21、log 2n)C. O(n 2)D. O(n )4.在一個帶頭結(jié)點的循環(huán)單鏈表L 中，刪除元素值為x 的結(jié)點，算法的時間復(fù)雜度為。A. O(n)B. O(n )C. O(nlog 2n)D. O(n 2)5.假設(shè)一個棧采用數(shù)組 s0.n-1 存放其元素，初始時棧頂指針為n，那么以下元素x 進棧的正確操作是。A.top+;stop=x;B.stop=x;top+;C.top-;stop=x;B.stop=x;top-;6. 中綴表達式“ 2*(3+4) - 1的后綴表達式是，其中 #表示一個數(shù)值的完畢。A. 2#3#4#1#*+ -B. 2#3#4#+*1# -C. 2#3#4#*+1# -D.

22、 - +*2#3#4#1#7.設(shè)環(huán)形隊列中數(shù)組的下標(biāo)為0 N- 1，其隊頭、隊尾指針分別為front 和 rear front 指向隊列中隊頭元素的前一個位置， rear 指向隊尾元素的位置 ，那么其元素個數(shù)為。A. rear - frontB. rear- front - 1C. (rear- front) N+1D. (rear - front+N) N8.假設(shè)用一個大小為 6 的數(shù)組來實現(xiàn)環(huán)形隊列，隊頭指針front指向隊列中隊頭元素的前一個位置，隊尾指針 rear 指向隊尾元素的位置。 假設(shè)當(dāng)前 rear 和 front 的值分別為0 和 3，當(dāng)從隊列中刪除一個元素，再參加兩個元素后，

23、 rear 和 front 的值分別為。A.1 和5B.2和4C.4和2D.5和19.一棵深度為 h h 1的完全二叉樹至少有個結(jié)點。A. 2 h-1B. 2hhh-1+1C.2 +1D. 210.一棵含有 n 個結(jié)點的線索二叉樹中，其線索個數(shù)為。A. 2nB. n- 1C. n+1D. n11. 設(shè)一棵哈夫曼樹中有 1999個結(jié)點，該哈夫曼樹用于對個字符進展編碼。A. 999B. 998C. 1000D. 100112.一個含有 n 個頂點的無向連通圖采用鄰接矩陣存儲，那么該矩陣一定是。A.對稱矩陣B. 非對稱矩陣C.稀疏矩陣D. 稠密矩陣13.設(shè)無向連通圖有 n 個頂點 e 條邊，假設(shè)滿足

24、，那么圖中一定有回路。A. e nB. e<nC. e=n- 1D. 2e n14. 對于 AOE 網(wǎng)的關(guān)鍵路徑，以下表達是正確的。A. 任何一個關(guān)鍵活動提前完成，那么整個工程一定會提前完成B. 完成整個工程的最短時間是從源點到匯點的最短路徑長度專業(yè)資料整理WORD格式第9頁共12頁專業(yè)資料整理WORD格式C. 一個 AOE 網(wǎng)的關(guān)鍵路徑一定是唯一的D. 任何一個活動持續(xù)時間的改變可能會影響關(guān)鍵路徑的改變15.設(shè)有 100 個元素的有序表，用折半查找時，不成功時最大的比較次數(shù)是。A. 25B. 50C. 10D. 716.在一棵 m 階 B- 樹中刪除一個關(guān)鍵字會引起合并，那么該結(jié)點原有

25、個關(guān)鍵字。A. 1B. m/2C. m/2 - 1D. m/2 +117.哈希查找方法一般適用于情況下的查找。A. 查找表為鏈表B. 查找表為有序表C. 關(guān)鍵字集合比地址集合大得多D. 關(guān)鍵字集合與地址集合之間存在著某種對應(yīng)關(guān)系。18. 對含有 n 個元素的順序表采用直接插入排序方法進展排序，在最好情況下算法的時間復(fù)雜度為。A. O(n)B. O(nlog 2n)C. O(n 2)D. O(n )19. 用某種排序方法對數(shù)據(jù)序列 24,88,21,48,15,27,69,35,20 進展遞增排序，元素序列的變化情況如下： 1 24,88,21,48,15,27,69,35,20（ 2 20,1

26、5,21,24,48,27,69,35,88（ 3 15,20,21,24,35,27,48,69,88（ 4 15,20,21,24,27,35,48,69,88那么所采用的排序方法是。A.快速排序B. 簡單項選擇擇排序C.直接插入排序D. 歸并排序20.以下序列是堆的是。A. 75,65,30,15,25,45,20,10B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10D. 75,45,65,10,25,30,20,15三、問答題1.有一棵二叉排序樹按先序遍歷得到的序列為：(12,5,2,8,6,10,16,15,18,20) 。答復(fù)

27、以下問題：（ 1畫出該二叉排序樹。 2給出該二叉排序樹的中序遍歷序列。 3求在等概率下的查找成功和不成功情況下的平均查找長度。答： 1 先序遍歷得到的序列為：(12,5,2,8,6,10,16,15,18,20) ，中序序列是一個有序序列，所以為：(2,5,6,8,10,12,15,16,18,20) ，由先序序列和中序序列可以構(gòu)造出對應(yīng)的二叉樹，如下列圖。（ 2中序遍歷序列為： 2,5,6,8,10,12,15,16,18,20。（ 3 ASL 成功 =(1 ×1+2×2+4×3+3×4)/10=29/10 。ASL 不成功 =(5 ×3+6

28、 ×4)/11=39/11 。1251628151861020專業(yè)資料整理WORD格式第10頁共12頁專業(yè)資料整理WORD格式2. 有人提出這樣的一種從圖 G 中頂點 u 開場構(gòu)造最小生成樹的方法：假設(shè) G=(V ， E)是一個具有 n 個頂點的帶權(quán)連通無向圖， T=(U ， TE) 是 G 的最小生成樹，其中 U 是 T 的頂點集， TE 是 T 的邊集，那么由 G 構(gòu)造從起始頂點 u 出發(fā)的最小生成樹 T 的步驟如下：（ 1初始化 U=u 。以 u 到其他頂點的所有邊為候選邊。（ 2重復(fù)以下步驟 n- 1 次，使得其他 n- 1 個頂點被參加到 U 中。從候選邊中挑選權(quán)值最小的邊

29、參加到TE ，設(shè)該邊在V- U 中的頂點是v，將 v 參加 U 中?？疾祉旤cv，將 v與 V - U 頂點集中的所有邊作為新的候選邊。假設(shè)此方法求得的 T 是最小生成樹，請予以證明。假設(shè)不能求得最小邊，請舉出反例。答：此方法不能求得最小生成樹。例如，對于如圖a所示的帶權(quán)連通無向圖，按照上述方法從頂點0開場求得的結(jié)果為 b所示的樹，顯然它不是最小生成樹，正確的最小生成樹如圖c所示。在有些情況下，上述方法無法求得結(jié)果，例如對于如圖d所示的帶權(quán)連通無向圖，從頂點0 出發(fā)，找到頂點 1邊0,1，從頂點 1 出發(fā)， 找到頂點3邊 1,3，再從頂點 3 出發(fā)，找到頂點0邊 3,0，這樣構(gòu)成回路，就不能求得

30、最小生成樹了。1021014313325352 a b 1001214313332452 c d求最小生成樹的反例圖3. 如果對含有nn>1 個元素的線性表的運算只有4 種：刪除第一個元素；刪除最后一個元素；在第一個元素前面插入新元素；在最后一個元素的后面插入新元素，那么最好使用以下哪種存儲構(gòu)造，并簡要說明理由。 1只有尾結(jié)點指針沒有頭結(jié)點指針的循環(huán)單鏈表2只有尾結(jié)點指針沒有頭結(jié)點指針的非循環(huán)雙鏈表 3只有頭結(jié)點指針沒有尾結(jié)點指針的循環(huán)雙鏈表4既有頭結(jié)點指針也有尾結(jié)點指針的循環(huán)單鏈表答：此題答案為3，因為實現(xiàn)上述4 種運算的時間復(fù)雜度均為O(1) 。4. 一棵度為 4 的樹中，其度為 0、 1、 2、3 的結(jié)點數(shù)分別為 14、 4、 3、 2，求該樹的結(jié)點總數(shù) n 和度為 4 的結(jié)點個數(shù)，并給出推導(dǎo)過程。答：結(jié)點總數(shù) n=n0+n1+n2+n3+n4 ，即 n=23+n4 ，又有：度之和 =n-1=0×n0+1×n1+2×n2 +3×n3+4×n4，即 n=17+4n4 ，綜合兩式得： n4=2， n=25。所以，該樹的結(jié)點總數(shù)為 25，度為 4 的結(jié)點個數(shù)為 2。四、算法設(shè)計題1. 假設(shè)二叉樹b 采用二叉鏈存儲構(gòu)造，設(shè)計一個算法voi