1、2013-2014學年二學期數據結構期末考試模擬試卷(16卷)一、應用題(3小題,共24分)1已知某字符串S中共有8種字符，各種字符分別出現2次、1次、4次、5次、7次、3次、4次和9次，對該字符串用0，1進行前綴編碼，問該字符串的編碼至少有多少位。【解答】以各字符出現的次數作為葉子結點的權值構造的哈夫曼編碼樹如圖所示。其帶權路徑長度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，該字符串的編碼長度至少為98位。2已知關鍵碼序列為（Jan, Feb, Mar, Apr, May, Ju

2、n, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空間為016，設散列函數為H(x)= i/2 (取下整數) ，其中i為關鍵碼中第一個字母在字母表中的序號，采用鏈地址法處理沖突構造散列表，并求等概率情況下查找成功的平均查找長度。【解答】H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/

3、2=2采用鏈地址法處理沖突，得到的開散列表如下：平均查找長度=(1×7+2×4+3×1)/12=18/123分析下面各程序段的時間復雜度（1） s1(int n) int p=1,s=0;  for (i=1;i<=n;i+)     p*=i;s+=p; return(s); O(n)（2） s2(int n)x=0;y=0; For (k=1;k<=n;k+) x+; For (i=1;i<=n;i+) For (j=1;j<=n;j+)y+; O(n2)1下述算法的功能是什么?（1）（

4、1）返回結點*p的直接前趨結點地址。  （2）交換結點*p和結點*q（p和q的值不變）。1對給定的一組權值W（5，2，9，11，8，3，7），試構造相應的哈夫曼樹，并計算它的帶權路徑長度。【解答】構造的哈夫曼樹如圖所示。WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1202已知散列函數H(k)=k mod 12，鍵值序列為(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82)，采用鏈表法處理沖突，試構造散列表。【解答】H(25)=1, H(37)=1,

5、 H(52)=4, H(43)=7, H(84)=0, H(99)=3,H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10構造的開散列表如下：3分析下面各程序段的時間復雜度（1）      for (i=0;i<n;i+)         for (j=0;j<m;j+)          &#

6、160; Aij O(n*m)（2） s=0;       for (i=0;i<n;i+)         for (j=0;j<n;j+)            s+=Bij;         sum=s; O(n2)  （

7、3） A=B; B=C; C=A; O(1)3設無向圖G（所下圖所示），要求給出從1出發對該圖進行深度優先和廣度優先遍歷的序列。   深度：125364，廣度：123456   （不唯一）4已知無向圖G的鄰接表如圖所示，分別寫出從頂點1出發的深度遍歷和廣度遍歷序列。【解答】深度優先遍歷序列為：1，2，3，4，5，6   廣度優先遍歷序列為：1，2，4，3，5，6二、判斷正誤(7小題,共14分)1線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數據元素。（ ）2一個棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，

8、A，B，D。（ ）3稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（ ）4如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。（  ）5用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點個數有關，而與圖的邊數無關。（ ）6向二叉排序樹中插入一個結點需要比較的次數可能大于該二叉樹的高度。（  ）7  邏輯結構與數據元素本身的內容和形式無關。（ ）1對鏈表進行插入和刪除操作時不必移動鏈表中結點。(  )3如果兩個串含有相同的字符，則說明它們相等。(   )4在線索二叉樹中，任一結點均有指向其前趨和后繼的線索。(

9、0;)5帶權無向圖的最小生成樹是唯一的。（   ）6稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。（  ）7無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣一定是不對稱的。(   )8分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（  ）1由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（  ）2稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。（  ）4分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（  ）5設初始記錄關鍵字基本有序，則

10、快速排序算法的時間復雜度為O(nlog2n)。（  ）6每種數據結構都具備三個基本操作：插入、刪除和查找。（  ）1順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。（×） 2在線性表的鏈式存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。3鏈表的每個結點都恰好包含一個指針域。（×）4有向圖的鄰接表和逆鄰接表中表結點的個數不一定相等。（×）5對連通圖進行深度優先遍歷可以訪問到該圖中的所有頂點。（  ）6當裝填因子小于1時，向散列表中存儲元素時不會引起沖突。（×）2  線性表的邏輯順

11、序和存儲順序總是一致的。（×）3非空的雙向循環鏈表中任何結點的前驅指針均不為空。（  ）4子串“ABC”在主串“AABCABCD”中的位置為2。（  ）5數組是一種復雜的數據結構，數組元素之間的關系既不是線性的，也不是樹形的。（×）7用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數無關而與圖中邊數有關。（×）9當裝填因子小于1時，向散列表中存儲元素時不會引起沖突。（×）10散列技術的查找效率主要取決于散列函數和處理沖突的方法。（×）1線性結構的基本特征是：每個元素有且僅有一個直接前驅和一個直接后繼。（ 

12、; ）2稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（  ）5對任意一個圖，從某頂點出發進行一次深度優先或廣度優先遍歷，可訪問圖的所有頂點。（  ）6當向二叉排序樹中插入一個結點，則該結點一定成為葉子結點。（  ）7數據的邏輯結構和數據的存儲結構是相同的。（ ）8數據的存儲結構是數據的邏輯結構的存儲映像。（  ）三、單項選擇題(8小題,共16分)1下面關于線性表的敘述錯誤的是（  D ）。A 線性表采用順序存儲必須占用一片連續的存儲空間 B 線性表采用鏈式存儲不必占用一片連續的存儲空間 C 線性表采用鏈式存儲便于插入和刪除操作

13、的實現 D 線性表采用順序存儲便于插入和刪除操作的實現 2單鏈表的存儲密度（  C  ）。   A 大于1            B 等于1        C小于1            D 不能確定 3  設輸入序列為1、2、3、4、5、

14、6，則通過棧的作用后可以得到的輸出序列為（ B ）。A  5，3，4，6，1，2                         B  3，2，5，6，4，1 C  3，1，2，5，4，6           

15、              D  1，5，4，6，2，34若串S="SOFTWARE"，其子串的數目最多是：（   C ） 。    A35         B36           C37

16、0;          D38 5二叉排序樹中，最小值結點的（A ）。A 左指針一定為空          B 右指針一定為空C 左、右指針均為空        D 左、右指針均不為空6在散列函數H(k)= k mod m中，一般來講，m應取（C ）。A 奇數      B 偶數 

17、0;   C 素數     D 充分大的數7用直接插入排序對下面四個序列進行由小到大排序，元素比較次數最少的是（  B ）。 A 94, 32, 40, 90, 80, 46, 21, 69         B 21, 32, 46, 40, 80, 69, 90, 94C 32, 40, 21, 46, 69, 94, 90, 80        

18、0;D 90, 69, 80, 46, 21, 32, 94, 401使用雙鏈表存儲線性表，其優點是可以（B ）。A 提高查找速度     B 更方便數據的插入和刪除C 節約存儲空間     D 很快回收存儲空間2鏈表不具有的特點是（B ）A.不必事先估計存儲空間              B.可隨機訪問任一元素 C.插入刪除不需要移動元素    

19、        D.所需空間與線性表長度成正比  3下面關于線性表的敘述錯誤的是（ D  ）。A 線性表采用順序存儲必須占用一片連續的存儲空間 B 線性表采用鏈式存儲不必占用一片連續的存儲空間 C 線性表采用鏈式存儲便于插入和刪除操作的實現 D 線性表采用順序存儲便于插入和刪除操作的實現 4從一個具有n個結點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均比較（  D ）個結點。 A n    &

20、#160;    B n/2          C (n-1)/2         D (n+1)/2 5在C或C+語言中，一個順序棧一旦被聲明，其占用空間的大小（  A  ）。   A已固定    B不固定       C可以改變 

21、60; D動態變化 6  兩個字符串相等的充要條件是（C  ）。A  兩個字符串的長度相等      B  兩個字符串中對應位置上的字符相等C  同時具備(A)和(B)兩個條件    D  以上答案都不對 8設某二叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，度數為2的結點數為N2，則下列等式成立的是（ C ）。A  N0=N1+1     B  N0=Nl+

22、N2      C  N0=N2+1       D  N0=2N1+l9在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數為(  D  )Ae     B2e      Cn2e    Dn22e10設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結點數分別為N1、N2和N3，則

23、二叉樹B的根結點的左子樹的結點數為（ A  ）。A  N1-1      B  N2-1     C  N2+N3     D  N1+N3 11設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（D  ）。A  空或只有一個結點         B  高度等于

24、其結點數C  任一結點無左孩子         D  任一結點無右孩子 12在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應最好選擇（ 快速  ）排序，如果從節省存儲空間的角度來考慮則最好選擇（ 堆  ）排序。 13設有以下四種排序方法，則（ B  ）的空間復雜度最大。 A  冒泡排序  B  快速排序    

25、 C  堆排序     D  希爾排序14數據結構中，與所使用的計算機無關的是數據的（C ）A存儲結構  B物理結構  C邏輯結構  D物理和存儲結構15數據的基本單位是（  B  ）。A.  數據結構     B.  數據元素  C.  數據項      D.  文件1已知一個順序存儲的線性表，設每個結點占m個存儲單元，若第一

26、個結點的地址為B，則第i個結點的地址為（  A  ）。A B+(i-1)*m        BB+i*m           C B-i*m           D B+(i+1)*m 3若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除第一個結點，則采用（D ）存儲方法最節省時間。 A 單鏈表 B 帶頭指針的

27、單循環鏈表 C 雙鏈表 D 帶尾指針的單循環鏈表4在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印緩沖區，該緩沖區應該是一個（ B  ）結構。A 棧            B隊列        C 數組         D線性表 5用鏈接方式存儲的隊列，在進行插入運算時(  D

28、 ).   A. 僅修改頭指針            B. 頭、尾指針都要修改   C. 僅修改尾指針              D.頭、尾指針可能都要修改 6以下論述正確的是（   C ）。   A空串與空格串是相同的    

29、  B"tel"是"Teleptone"的子串   C空串是零個字符的串         D. 空串的長度等于1 7對于完全二叉樹中的任一結點，若其右分支下的子孫的最大層次為h，則其左分支下的子孫的最大層次為（C ）。 A h          B h+1         C h

30、或h+1           D 任意 9設哈夫曼樹中的葉子結點總數為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（B  ）個空指針域。     A  2m-1                  B  2m   &

31、#160;             C  2m+1              D  4m 10設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有（ B ）個表頭結點。     A  n-1      

32、               B  n                    C  n+1             &#

33、160;  D  2n-1 11二叉排序樹中左子樹上所有結點的值均（ A ）根結點的值。     A  <                        B  >        

34、            C  =                    D  != 12靜態查找與動態查找的根本區別在于（B ）。A 它們的邏輯結構不一樣 B 施加在其上的操作不同C 所包含的數據元素的類型不一樣   D 存儲實現不一樣13散列技術中的沖突指的

35、是（ D）。A 兩個元素具有相同的序號                 B 兩個元素的鍵值不同，而其他屬性相同C 數據元素過多                            

36、;D 不同鍵值的元素對應于相同的存儲地址14一組記錄的關鍵碼為46, 79, 56, 38, 40, 84，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（ A  ）。A 40, 38, 46, 56, 79, 84        B 40, 38, 46, 79, 56, 84C 40, 38, 46, 84, 56, 79        D 84, 79, 56, 46, 40, 3815對一個算法的評價，不包括如下（

37、 B ）方面的內容。    A健壯性和可讀性   B并行性     C正確性     D時空復雜度1單鏈表的存儲密度（  C  ）。   A 大于1            B 等于1        C小于1   

38、0;        D 不能確定 2設一個有序的單鏈表中有n個結點，現要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（ D ）。     A  O(log2n)              B  O(1)        &

39、#160;      C  O(n2)              D  O(n) 3在下列鏈表中不能從當前結點出發訪問到其余各結點的是（ C   ）。A雙向鏈表        B單循環鏈表    C單鏈表     

40、60;    D雙向循環鏈表 4從一個棧頂指針為top的鏈棧中刪除一個結點時，用x保存被刪除的結點，應執行下列 (   D )命令。   Ax=top;top=top->next;      Btop=top->next;x=top->data;   Cx=top->data;            &#

41、160; Dx=top->data;top=top->next; 5設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（  D）。     A  top=top+1;            B  top=top-1;       C  top->next=top;   

42、0;     D  top=top->next; 6字符串的長度是指（  C ）。         A  串中不同字符的個數                  B  串中不同字母的個數      

43、;   C  串中所含字符的個數                  D  串中不同數字的個數 7數組的邏輯結構不同于下列（ D ）的邏輯結構。       A  線性表           B

44、60;棧                C 隊列                 D  樹 8設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ D ）。       A  空或只

45、有一個結點                       B  高度等于其結點數       C  任一結點無左孩子               

46、60;       D  任一結點無右孩子  10下圖為由7個頂點組成的無向圖。從頂點1出發，對它進行廣度優先遍歷得到的頂點序列是_C_。    A、1534267     B、1726453   C、1354276     D、1247653 11下列各種排序算法中平均時間復雜度為O(n2)是（  D ）。   &#

47、160; A  快速排序           B  堆排序            C  歸并排序               D  冒泡排序 = 2對線性表，在下列哪種情況下應當采用鏈表表示

48、？(  B )      A.經常需要隨機地存取元素         B.經常需要進行插入和刪除操作      C.表中元素需要占據一片連續的存儲空間    D.表中元素的個數不變 3若用一個大小為6的數組來實現循環隊列，且當前front和rear的值分別為3和0，當從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為( 

49、0; B )。  A5和1        B4和2         C2和4             D1和5  5  設一棵三叉樹中有2個度數為1的結點，2個度數為2的結點，2個度數為3的結點，則該三叉鏈權中有（ C ）個度數為0的結點。  

50、60;      A  5                     B  6                    C  7

51、60;                   D  8 6任何一棵二叉樹的葉子結點在前序、中序、后序遍歷序列中的相對次序（ A）。A 肯定不發生改變         B 肯定發生改變        C 不能確定    &#

52、160;    D 有時發生變化7設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為（ A ）。      A  O(n+e)               B  O(n2)             

53、C  O(ne)              D  O(n3) 8下面關于工程計劃的AOE網的敘述中，不正確的是（B ） A 關鍵活動不按期完成就會影響整個工程的完成時間B 任何一個關鍵活動提前完成，那么整個工程將會提前完成C 所有的關鍵活動都提前完成，那么整個工程將會提前完成D 某些關鍵活動若提前完成，那么整個工程將會提前完9下列命題正確的是（ B）。A 一個圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一B 一個圖的鄰接矩陣表示是

54、唯一的，鄰接表表示不唯一C 一個圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一D 一個圖的鄰接矩陣表示不唯一的，鄰接表表示也不唯一10  設某散列表的長度為100，散列函數H(k)=k % P，則P通常情況下最好選擇（ B ）。         A  99                    

55、; B  97                 C  91                  D  93 11設一組初始記錄關鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F，X)，則按字母升序的第一趟冒泡排序結束后的結果是

56、（  D ）。A   F，H，C，D，P，A，M，Q，R，S，Y，X B   P，A，C，S，Q，D，F，X，R，H，M，Y C   A，D，C，R，F，Q，M，S，Y，P，H，X D   H，C，Q，P，A，M，S，R，D，F，X，Y =1線性表的鏈式鏈式存儲結構是一種（ B   ）的存儲結構。             

57、60;                       A、隨機存取             B、順序存取        C、索引存取     

58、        D、HASH存取    3設計一個判別表達式中左右括號是否配對的算法，采用（B ）數據結構最佳A 順序表      B 棧     C 隊列     D 鏈表4設棧S和隊列Q的初始狀態為空，元素e1、e2、e3、e4、e5、e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應該是（C

59、）。A 6  B 4  C 3  D 25設數組datam作為循環隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執行出隊操作后其頭指針front值為（  D ）   Afront=front+1                 Bfront=(front+1)%(m-1)   Cfront=(front-1)%m 

60、60;           Dfront=(front+1)%m 7廣義表(a, b, (c, (d)的表尾是（ D  ）。A (d)          B (c,(d)         C b        D (b,(c,(d

61、)  9線索二叉樹中某結點R沒有左孩子的充要條件是（ C）。A R.lchild=NULL      B R.ltag=0       C R.ltag=1       D R.rchild=NULL10  設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為（ B ）。         A  8 

62、;                    B  7                    C  6        

63、60;           D  5  12G是一個非連通無向圖，共有28條邊，則該圖至少有（ D）個頂點。A 6     B 7     C 8     D 9 14設有6個結點的無向圖，該圖至少應有(   A   )條邊才能確保是一個連通圖。A.5    

64、   B.6          C.7       D.815散列表的地址區間為0-17,散列函數為H(K)=K mod 17。采用線性探測法處理沖突，并將關鍵字序列26，25，72，38，8，18，59依次存儲到散列表中。存放元素59需要搜索的次數是（  C）A、  2         B、  3  

65、60;      C、  4        D、   516  設有5000個元素，希望用最快的速度挑選出前10個最大的，采用（  B  ）方法最好。A快速排序       B堆排序        C希爾排序     

66、 D 歸并排序四、算法設計題(2小題,共24分)1設計在順序存儲結構上實現求子串算法。void substring(char s , long start, long count, char t )  long i,j,length=strlen(s);  if (start<1 | start>length) printf("The copy position is wrong");else if (start+count-1>length) printf("Too characters to be copied&

67、quot;); else for(i=start-1,j=0; i<start+count-1;i+,j+) tj=si; tj= '0'2編寫算法，要求輸出二叉樹后序遍歷序列的逆序。void  Postordern(BiTree  *H)  if (H) visit(H->data);  Postordern(H->rchild);  Postordern(H->lchild);1設計判斷一棵二叉樹是否是二叉排序樹的算法。int minnum=-32768, flag=1;typedef struct

68、nodeint key;   struct node *lchild,*rchild;bitree;void inorder(bitree *bt)  if (bt!=0)    inorder(bt->lchild); if(minnum>bt->key) flag=0; minnum=bt->key; inorder(bt->rchild); 2設計順序查找算法，將哨兵設在下標高端。【解答】將哨兵設置在下標高端，表示從數組的低端開始查找，在查找不成功的情況下，算法自動在哨兵處終止。具體算法如下：1設計

69、判斷單鏈表中元素是否是遞增的算法。int isriselk(lklist *head)if(head=0|head->next=0) return(1);else for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0);return(1);3設計一個在鏈式存儲結構上統計二叉樹中結點個數的算法。void countnode(bitree *bt,int &count)   if(bt!=0) count+; countnode(bt->

70、;lchild,count); countnode(bt->rchild,count);1  對給定的帶頭結點的單鏈表L，編寫一個刪除L中值為X的結點的直接前趨結點的算法。解：void delete(ListNode *L)  ListNode *p=L,*q;    if (L->next->data=X)    printf (“值為x的結點是第一個結點，沒有直接前趨結點可以刪除”);      return;   

71、;     for (;p->next->data!=X; q=p; p=p->next);     / 刪除指針p所指向的結點        q->next=p->next;    delete p;1  已知一個有向圖的鄰接表，編寫算法建立其逆鄰接表。【解答】在有向圖中，若鄰接表中頂點vi有鄰接點vj，在逆鄰接表中vj一定有鄰接點vi，由此得到本題算法思路：首先將逆鄰接表的表頭結點f

72、irstedge域置空，然后逐行將表頭結點的鄰接點進行轉化。五、填空題(6小題,共12分)1在單鏈表中要在已知結點*P之前插入一個新結點，需找到*P的直接前趨結點的地址，其查找的時間復雜度為（ O(n)  ）。2設無向圖G中有n個頂點e條邊，所有頂點的度數之和為m，則e和m有（ m=2e  ）關系。3順序查找技術適合于存儲結構為（順序存儲和鏈接存儲 ）的線性表4對n個元素進行起泡排序，在（ 正序 ）情況下比較的次數最少，其比較次數為（ n-1   ）。5快速排序算法的空間復雜度平均情況下為（ &

73、#160;O(nlog2n)  ），最壞的情況下為（ O(n)   ）。6樹形結構結構中的元素之間存在（ 一對多  ）的關系1在雙向鏈表中，每個結點都有兩個指針域，它們一個指向其（ 前趨  ）結點，另一個指向其（ 后繼  ）結點。 2由兩個棧共享一個存儲空間的好處是（ 節省存儲空間，降低上溢發生的機率）3設循環隊列存放在向量sq.data0:M中，若用犧牲一個單元的辦法來區分隊滿和隊空（設隊尾指針sq.rear）,則隊滿的條件為（ (sq.rear+1)%(M+1)

74、=sq.front； ）。4設二叉樹中結點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是（   p->lchild=0&&p->rchild=0   ）。5深度為k的完全二叉樹中最少有（  2k-1 ）個結點。6設一棵二叉樹的前序序列為ABC，則有（ 5  ）種不同的二叉樹可以得到這種序列。 7對于一棵具有n個結點的二叉樹，用二叉鏈表存儲時，其指針總數為（ 2n ）個，其中（ n-1 ）個用于指向孩子，

75、（ n+1 ）個指針是空閑的。8度不為（ 零 ）的結點稱為分支結點或非終端結點。樹中各結點度的（ 最大值）稱為樹的度。9設有向圖G用鄰接矩陣Ann作為存儲結構，則該鄰接矩陣中第i行上所有元素之和等于頂點i的（  出度 ），第i列上所有元素之和等于頂點i的（  入度）。10N個頂點的強連通圖的邊數至少有（ N ）11  數據的物理結構主要包括（ 順序存儲結構 ）和（  鏈式存儲結構  ）兩種情況。12假設線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次

76、數為（ n(n-1)/2 ）13算法的空間復雜度是指（執行過程中所需要的輔助存儲空間）14順序存儲結構中數據元素之間的邏輯關系是由（  存儲位置  ）表示的，鏈接存儲結構中的數據元素之間的邏輯關系是由（  指針     ）表示的。15若算法中的語句執行次數之和為 T ( n )= 525 n +4 n log n ，則算法的時間復雜度是（    O （ n log n ）   ）。1可由一個尾指針唯一確定的鏈表有（循環鏈表 ）、（雙鏈表）。 2在

77、有n個元素的棧中，進棧操作的時間復雜度為（ O（1）  ），出棧操作的時間復雜度為（  O（1） ）。 3在串 S="structure" 中，以 t 為首字符的子串有（   12  ）個。4設有一個10階的對稱矩陣A采用壓縮存儲，A00為第一個元素，其存儲地址為d，每個元素占1個存儲單元，則元素A85的存儲地址為（d+41. 元素A85的前面共存儲了(1+2+8)+5=41個元素）。5廣義表(a,(a,b),d,e,(i,j),k)的長度是（ 5   ），深度是（ 3   ）。  6一棵二叉樹的第i（i1）層最多有（2i-1）個結點；一