數(shù)據(jù)結(jié)構(gòu)題庫(kù)

1、2013-2014學(xué)年二學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試模擬試卷(16卷)一、應(yīng)用題(3小題,共24分)1已知某字符串S中共有8種字符，各種字符分別出現(xiàn)2次、1次、4次、5次、7次、3次、4次和9次，對(duì)該字符串用0，1進(jìn)行前綴編碼，問(wèn)該字符串的編碼至少有多少位?！窘獯稹恳愿髯址霈F(xiàn)的次數(shù)作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造的哈夫曼編碼樹如圖所示。其帶權(quán)路徑長(zhǎng)度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，該字符串的編碼長(zhǎng)度至少為98位。2已知關(guān)鍵碼序列為（Jan, Feb, Mar, Apr, May, Ju

2、n, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空間為016，設(shè)散列函數(shù)為H(x)= i/2 (取下整數(shù)) ，其中i為關(guān)鍵碼中第一個(gè)字母在字母表中的序號(hào)，采用鏈地址法處理沖突構(gòu)造散列表，并求等概率情況下查找成功的平均查找長(zhǎng)度?！窘獯稹縃(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采用鏈地址法處理沖突，得到的開散列表如下：平均查找長(zhǎng)度=(1×7+2×4+3×1)/12=18/123分析下面各程序段的時(shí)間復(fù)雜度（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）返回結(jié)點(diǎn)*p的直接前趨結(jié)點(diǎn)地址。  （2）交換結(jié)點(diǎn)*p和結(jié)點(diǎn)*q（p和q的值不變）。1對(duì)給定的一組權(quán)值W（5，2，9，11，8，3，7），試構(gòu)造相應(yīng)的哈夫曼樹，并計(jì)算它的帶權(quán)路徑長(zhǎng)度?！窘獯稹繕?gòu)造的哈夫曼樹如圖所示。WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1202已知散列函數(shù)H(k)=k mod 12，鍵值序列為(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82)，采用鏈表法處理沖突，試構(gòu)造散列表?！窘獯稹縃(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構(gòu)造的開散列表如下：3分析下面各程序段的時(shí)間復(fù)雜度（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設(shè)無(wú)向圖G（所下圖所示），要求給出從1出發(fā)對(duì)該圖進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷的序列。   深度：125364，廣度：123456   （不唯一）4已知無(wú)向圖G的鄰接表如圖所示，分別寫出從頂點(diǎn)1出發(fā)的深度遍歷和廣度遍歷序列?！窘獯稹可疃葍?yōu)先遍歷序列為：1，2，3，4，5，6   廣度優(yōu)先遍歷序列為：1，2，4，3，5，6二、判斷正誤(7小題,共14分)1線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。（ ）2一個(gè)棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，

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

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

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

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

12、; ）2稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。（  ）5對(duì)任意一個(gè)圖，從某頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問(wèn)圖的所有頂點(diǎn)。（  ）6當(dāng)向二叉排序樹中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（  ）7數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是相同的。（ ）8數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映像。（  ）三、單項(xiàng)選擇題(8小題,共16分)1下面關(guān)于線性表的敘述錯(cuò)誤的是（  D ）。A 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 B 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間 C 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作

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

14、6，則通過(guò)棧的作用后可以得到的輸出序列為（ 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"，其子串的數(shù)目最多是：（   C ） 。    A35         B36           C37

16、0;          D38 5二叉排序樹中，最小值結(jié)點(diǎn)的（A ）。A 左指針一定為空          B 右指針一定為空C 左、右指針均為空        D 左、右指針均不為空6在散列函數(shù)H(k)= k mod m中，一般來(lái)講，m應(yīng)?。– ）。A 奇數(shù)      B 偶數(shù) 

17、0;   C 素?cái)?shù)     D 充分大的數(shù)7用直接插入排序?qū)ο旅嫠膫€(gè)序列進(jìn)行由小到大排序，元素比較次數(shù)最少的是（  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使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以（B ）。A 提高查找速度     B 更方便數(shù)據(jù)的插入和刪除C 節(jié)約存儲(chǔ)空間     D 很快回收存儲(chǔ)空間2鏈表不具有的特點(diǎn)是（B ）A.不必事先估計(jì)存儲(chǔ)空間              B.可隨機(jī)訪問(wèn)任一元素 C.插入刪除不需要移動(dòng)元素    

19、        D.所需空間與線性表長(zhǎng)度成正比  3下面關(guān)于線性表的敘述錯(cuò)誤的是（ D  ）。A 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 B 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間 C 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn) D 線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn) 4從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較（  D ）個(gè)結(jié)點(diǎn)。 A n    &

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

21、60; D動(dòng)態(tài)變化 6  兩個(gè)字符串相等的充要條件是（C  ）。A  兩個(gè)字符串的長(zhǎng)度相等      B  兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等C  同時(shí)具備(A)和(B)兩個(gè)條件    D  以上答案都不對(duì) 8設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（ C ）。A  N0=N1+1     B  N0=Nl+

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

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

24、其結(jié)點(diǎn)數(shù)C  任一結(jié)點(diǎn)無(wú)左孩子         D  任一結(jié)點(diǎn)無(wú)右孩子 12在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來(lái)考慮應(yīng)最好選擇（ 快速  ）排序，如果從節(jié)省存儲(chǔ)空間的角度來(lái)考慮則最好選擇（ 堆  ）排序。 13設(shè)有以下四種排序方法，則（ B  ）的空間復(fù)雜度最大。 A  冒泡排序  B  快速排序    

25、 C  堆排序     D  希爾排序14數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（C ）A存儲(chǔ)結(jié)構(gòu)  B物理結(jié)構(gòu)  C邏輯結(jié)構(gòu)  D物理和存儲(chǔ)結(jié)構(gòu)15數(shù)據(jù)的基本單位是（  B  ）。A.  數(shù)據(jù)結(jié)構(gòu)     B.  數(shù)據(jù)元素  C.  數(shù)據(jù)項(xiàng)      D.  文件1已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)占m個(gè)存儲(chǔ)單元，若第一

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

27、單循環(huán)鏈表 C 雙鏈表 D 帶尾指針的單循環(huán)鏈表4在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個(gè)（ B  ）結(jié)構(gòu)。A 棧            B隊(duì)列        C 數(shù)組         D線性表 5用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)(  D

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

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

30、或h+1           D 任意 9設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有（B  ）個(gè)空指針域。     A  2m-1                  B  2m   &

31、#160;             C  2m+1              D  4m 10設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（ B ）個(gè)表頭結(jié)點(diǎn)。     A  n-1      

32、               B  n                    C  n+1             &#

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

34、            C  =                    D  != 12靜態(tài)查找與動(dòng)態(tài)查找的根本區(qū)別在于（B ）。A 它們的邏輯結(jié)構(gòu)不一樣 B 施加在其上的操作不同C 所包含的數(shù)據(jù)元素的類型不一樣   D 存儲(chǔ)實(shí)現(xiàn)不一樣13散列技術(shù)中的沖突指的

35、是（ D）。A 兩個(gè)元素具有相同的序號(hào)                 B 兩個(gè)元素的鍵值不同，而其他屬性相同C 數(shù)據(jù)元素過(guò)多                            

36、;D 不同鍵值的元素對(duì)應(yīng)于相同的存儲(chǔ)地址14一組記錄的關(guān)鍵碼為46, 79, 56, 38, 40, 84，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ 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對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（

37、 B ）方面的內(nèi)容。    A健壯性和可讀性   B并行性     C正確性     D時(shí)空復(fù)雜度1單鏈表的存儲(chǔ)密度（  C  ）。   A 大于1            B 等于1        C小于1   

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

39、#160;      C  O(n2)              D  O(n) 3在下列鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到其余各結(jié)點(diǎn)的是（ C   ）。A雙向鏈表        B單循環(huán)鏈表    C單鏈表     

40、60;    D雙向循環(huán)鏈表 4從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行下列 (   D )命令。   Ax=top;top=top->next;      Btop=top->next;x=top->data;   Cx=top->data;            &#

41、160; Dx=top->data;top=top->next; 5設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（  D）。     A  top=top+1;            B  top=top-1;       C  top->next=top;   

42、0;     D  top=top->next; 6字符串的長(zhǎng)度是指（  C ）。         A  串中不同字符的個(gè)數(shù)                  B  串中不同字母的個(gè)數(shù)      

43、;   C  串中所含字符的個(gè)數(shù)                  D  串中不同數(shù)字的個(gè)數(shù) 7數(shù)組的邏輯結(jié)構(gòu)不同于下列（ D ）的邏輯結(jié)構(gòu)。       A  線性表           B

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

45、有一個(gè)結(jié)點(diǎn)                       B  高度等于其結(jié)點(diǎn)數(shù)       C  任一結(jié)點(diǎn)無(wú)左孩子               

46、60;       D  任一結(jié)點(diǎn)無(wú)右孩子  10下圖為由7個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn)1出發(fā)，對(duì)它進(jìn)行廣度優(yōu)先遍歷得到的頂點(diǎn)序列是_C_。    A、1534267     B、1726453   C、1354276     D、1247653 11下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（  D ）。   &#

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

48、？(  B )      A.經(jīng)常需要隨機(jī)地存取元素         B.經(jīng)常需要進(jìn)行插入和刪除操作      C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間    D.表中元素的個(gè)數(shù)不變 3若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，front和rear的值分別為( 

49、0; B )。  A5和1        B4和2         C2和4             D1和5  5  設(shè)一棵三叉樹中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（ C ）個(gè)度數(shù)為0的結(jié)點(diǎn)。  

50、60;      A  5                     B  6                    C  7

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

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

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

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

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

56、（  D ）。A   F，H，C，D，P，A，M，Q，R，S，Y，X B   P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y C   A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X D   H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y =1線性表的鏈?zhǔn)芥準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種（ B   ）的存儲(chǔ)結(jié)構(gòu)。             

57、60;                       A、隨機(jī)存取             B、順序存取        C、索引存取     

58、        D、HASH存取    3設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)的算法，采用（B ）數(shù)據(jù)結(jié)構(gòu)最佳A 順序表      B 棧     C 隊(duì)列     D 鏈表4設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是（C

59、）。A 6  B 4  C 3  D 25設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針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線索二叉樹中某結(jié)點(diǎn)R沒(méi)有左孩子的充要條件是（ C）。A R.lchild=NULL      B R.ltag=0       C R.ltag=1       D R.rchild=NULL10  設(shè)一棵完全二叉樹中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為（ B ）。         A  8 

62、;                    B  7                    C  6        

63、60;           D  5  12G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有（ D）個(gè)頂點(diǎn)。A 6     B 7     C 8     D 9 14設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有(   A   )條邊才能確保是一個(gè)連通圖。A.5    

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

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

66、 D 歸并排序四、算法設(shè)計(jì)題(2小題,共24分)1設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。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設(shè)計(jì)判斷一棵二叉樹是否是二叉排序樹的算法。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設(shè)計(jì)順序查找算法，將哨兵設(shè)在下標(biāo)高端?！窘獯稹繉⑸诒O(shè)置在下標(biāo)高端，表示從數(shù)組的低端開始查找，在查找不成功的情況下，算法自動(dòng)在哨兵處終止。具體算法如下：1設(shè)計(jì)

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設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。void countnode(bitree *bt,int &count)   if(bt!=0) count+; countnode(bt->

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

71、;     for (;p->next->data!=X; q=p; p=p->next);     / 刪除指針p所指向的結(jié)點(diǎn)        q->next=p->next;    delete p;1  已知一個(gè)有向圖的鄰接表，編寫算法建立其逆鄰接表?！窘獯稹吭谟邢驁D中，若鄰接表中頂點(diǎn)vi有鄰接點(diǎn)vj，在逆鄰接表中vj一定有鄰接點(diǎn)vi，由此得到本題算法思路：首先將逆鄰接表的表頭結(jié)點(diǎn)f

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

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

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

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

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

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