【正文】 字序列{15，92，124，5，27，28，18，6，36，34，30，26，32，259}，將它們用散列函數(shù)H(key)=key MOD 11 按順序散列到HASH表HT（0:10）中，用鏈地址解決沖突。 (D)后序34． 已知一個長度為12的線性表（8，2，5，7，12，3，10，4，1，6，9，11），并將線性表中的元素依次插入到一個原先為空的二叉排序樹中去。 (B)前序 (A)直接插入排序 (B)簡單選擇排序(C)冒泡排序 (D)快速排序33． 對二叉排序樹進(jìn)行（ C ）遍歷，可以得到該二叉樹所有結(jié)點構(gòu)成的排序序列。 E={(3,1)6，(3,4)7，(3,7)5，(1,2)3，(1,4)4，(4,7)8，(4,5)4，(7,8)5，(2,6)3，(2,5)5, (5,8)8, (5,6)5, (8,6)6}, 則該圖的最小生成樹的權(quán)值為（ C ）。snext=NULL。(D)Qfrontnext=s。Qrear=s。Qrear=NULL。(B)snext=Qfront。snext=Qrear。(A)O(1)和O(1) (B)O(1)和O(n) (C)O(n)和O(1) (D)O(n) 和O(n)30． 設(shè)鏈隊列Q的頭指針和尾指針分別為front和rear，初始時隊列為空，若向隊列插入一個元素*s，則應(yīng)執(zhí)行的指針操作為（ C ）。 snext=p。pnext=head。pnext=s。pnext=s。(A)單鏈表 (B)單循環(huán)鏈表 (C)無頭雙向鏈表 (D)帶頭雙向鏈表28． 已知head是一個非空單鏈表的頭指針，指針p指向單鏈表的最后一個結(jié)點，若要在p之后插入一個新結(jié)點*s，并將單鏈表變?yōu)檠h(huán)單鏈表，則應(yīng)執(zhí)行的操作是（ B ）。 (C)n+1 (A)2n1j++。j=0。(A)5/3 (B)13/9 (C)16/9 (D)3/225． 下列程序段所代表的算法的時間復(fù)雜度為（ D ）。 (A)快速排序 (B)冒泡排序 (C)歸并排序 (D)堆排序24． 已知一個待散列存儲的線性表{18,81,58,34,26,75,67,49,93}，散列函數(shù)為h(k)=k%11，散列地址空間為0~10。(A) E={v2,v1,v6,v2,v1,v3,v2,v3,v5,v3,v3,v4,v4,v6,v5,v6}(B) E={v1,v2,v1,v3,v1,v4,v3,v5,v3,v2,v4,v5,v6,v5,v6,v4}(C) E={v1,v3,v1,v4,v1,v5,v2,v3,v2,v2,v3,v5,v3,v6,v4,v5,v4,v6,v5,v6}(D) E={v1,v2,v1,v3,v2,v3,v1,v4,v2,v5,v3,v6,v4,v6,v5,v6}22． 冒泡排序算法在最好情況下的時間復(fù)雜度為（ B ）。(A)49 (B)96 (C)103 (D)12520． 在一個n個結(jié)點的二叉排序樹中查找一個關(guān)鍵字，進(jìn)行關(guān)鍵字比較次數(shù)最大值為（ A ）。(A)n=m+h (B)h+m=2n (C)m=h1 (D)n=2h118． 一棵左、右子樹均不為空的二叉樹在先序線索化后，其空指針域數(shù)為 （ B ）。 HS=NULL。x=HSdata。HSNEXT=NULL。 HS=HSnext。(A)HQrearnext==HQfront (B)HQfrontnext==HQrearnext(C)HQfront==HQrear (D)HQfrontnext==HQrear16． 從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點時，用x保存被刪除結(jié)點的值，則應(yīng)執(zhí)行操作為（ A ）。(A)單鏈表 (B)雙鏈表 (C)單循環(huán)鏈表 (D)順序表14． 一個帶頭結(jié)點head的循環(huán)單鏈表為空的判斷條件是（ C ）。(A)O(n) (B)O(n2) (C)O(log2n) (D)O()12． 在一個長度為n的以順序結(jié)構(gòu)存儲的線性表中，假設(shè)在線性表的任何位置插入元素的概率相等，則插入一個元素時線性表所需移動元素的平均次數(shù)為（ B ）。x=1。(A)5/3 (B)13/9 (C)16/9 (D)3/211． 下列程序段所代表的算法的時間復(fù)雜度為（ C ）。(A)n1 (B) nn/m (C) (n1)n/m (D) (n1)+n/m10． 已知一個待散列存儲的線性表{18,81,58,34,26,75,67,49,93}，散列函數(shù)為h(k)=k%11，散列地址空間為0~10。(A)93 (B)96 (C)123 (D)1038． 已知一個有向圖G的頂點v={v1,v2,v3,v4,v5,v6}，其鄰接表如下圖所示，根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點遍歷序列是（ B ）。(A)2h1 (B)2h1+1 (C)2h1 (D)2h136． 現(xiàn)有數(shù)據(jù)集{53,30,37,12,45,24,96}，從空二叉樹逐個插入數(shù)據(jù)形成二叉排序樹，若希望查找此二叉樹中任一結(jié)點的平均查找長度最小，則應(yīng)選擇下面哪個序列輸入（ C ）。snext=p。pnext=Qfront。Qfront=s。snext=Qfront。while(pnext!=Qfront) p=pnext。若要進(jìn)隊一個元素*s，則在下列程序算法的空白處應(yīng)添加的操作語句是（ A ）。HS=HSnext。HS=s。HSnext=s。(A)HSnext=s。(A)O(n) (B)O(n2) (C)O(log2n) (D)O()2． 在一個長度為n的以順序結(jié)構(gòu)存儲的線性表中，假設(shè)在線性表的任何位置刪除元素的概率相等，則刪除一個元素時線性表所需移動元素的平均次數(shù)為（ B ）。 y=0。數(shù)據(jù)結(jié)構(gòu)試題庫一、 單項選擇題1． 下列程序段所代表的算法的時間復(fù)雜度為（ D ）。x=n。while (x=(y+1)*(y+1)) y++。(A) n2 (B)(n1)/2 (C)(n+1)/2 (D)n/23． 在一個棧頂指針為HS的鏈棧中插入一個*s結(jié)點時，應(yīng)執(zhí)行執(zhí)行操作為 （ C ）。　　 　 (B)snext=HSnext。(C)snext=HS?！? 　(D)snext=HS。4． 假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列Q，并且隊列只設(shè)一個頭指針front，不設(shè)隊列尾指針。 void AddQueue(struct linkqueue Q) { p=Qfront。 }(A)pnext=s。 (B)Qfrontnext=s。(C)snext=p。(D)Qfrontnext=s。5． 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（ B ）。(A)45,24,53,12,37,96,30 (B) 30,24,12,37,45,96,53(C) 37,24,12,30,53,45,96 (D) 12,24,30,37,45,53,967． 有一組數(shù)值{5,12,9,20,3}，用以構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度WPL值為（ D ）。(A)v1,v2,v3,v6,v4,v5 (B)v1,v2,v3,v6,v5,v4 (C)v1,v2,v5,v6,v3,v4 (D)v1,v2,v5,v3,v4,v6v3 ^v4 ^v5v5 ^v6 ^v1v2v2v3^v3v6 ^v4^v5v4v6^9． 設(shè)有m=2n1個關(guān)鍵字，假設(shè)對每個關(guān)鍵字查找的概率相等，查找失敗的概率為0，若采用二分法查找一個關(guān)鍵字，則平均查找長度為（ D ）。若采用線性探查法解決沖突，則平均查找長度為（ A ）。y=n。while(x=y)x*=2。(A)n2 (B)(n+1)/2 (C)(n1)/2 (D)n/213． 若對一個已有序的線性表最頻繁的操作是查找值為x的元素(假設(shè)存在的話)，則采用（ D ）存儲方式實現(xiàn)查找，其算法的時間復(fù)雜度為最小。(A)head==NULL (B)headnext==NULL(C)headnext==head (D)head!=NULL15． 若鏈隊列HQ中只有一個結(jié)點，則隊列的頭指針和尾指針滿足下列條件 （ D ）。(A)x=HSdata。 (B)x=HSdata。(C)HS=HSnext。 (D)x=HSdata。17． 一棵有n個結(jié)點的滿二叉樹，有m個葉子結(jié)點，深度為h，那么n、m和h滿足條件（ D ）。(A)0 (B)1 (C)2 (D)不確定19． 有一組數(shù)值{5,12,9,20,3}，用以構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度WPL值為（ C ）。(A)n (B)n/2 (C)log2n (D)n*log2n 21． 已知有向圖G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，則下列邊集合E中（ A ）所對應(yīng)的有向圖沒有拓?fù)湫蛄小?(A)O(log2n) (B)O(n) (C)O(1) (D)O(n2)23． 在下列內(nèi)部排序方法中，排序時不穩(wěn)定的，而且關(guān)鍵字的比較次數(shù)與記錄的初始排列次序無關(guān)的是（ D ）。若采用線性探查法解決沖突，則平均查找長度為（ C ）。 i=1。 while(i=n) {i+=j。 }(A)O(n) (B)O(n2) (C)O(log2n) (D)O()26． 將兩個各有n個元素的有序表歸并成一個有序表，在最壞的情況下，其比較次數(shù)是（ A ）。 (B)n (D)n127． 若某鏈表中最常用的操作是在最后的一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用（ D ）存儲方式最節(jié)省運(yùn)行時間。(A)snext=pnext。 (B)snext=head。(C)snext=pnext。 (D)snext=pnext。29． 已知用循環(huán)鏈表表示的隊列長度為n，若只設(shè)頭指針，則出隊和入隊一個元素的時間復(fù)雜度分別是（ B ）。(A)Qfrontnext=s。Qrear=NULL。Qrearnext=s。(C)Qrearnext=s。snext=NULL。Qrear=s。31． 已知一個帶權(quán)圖的頂點集V和邊集G分別為： V={1,2,3,4,5,6,7,8}。(A)24 (B)29 (C)30 (D)3132． 當(dāng)待排序的關(guān)鍵字個數(shù)n很小，且初始排列為逆序時，采用下列排序方法中的（ D ），算法的時間復(fù)雜度最小。(A)層次 (C)中序 假設(shè)查找每一個元素的概率相同，則查找該二叉樹中任一結(jié)點的平均查找長度為（ A ）。假設(shè)查找每一個元素的概率相同，則查找該HASH表中任一元素的平均查找長度為（ C ）。 (A)165 (B)203 (C)124 (D)18737． 假定對線性表R[0…n1]進(jìn)行分塊查找，若將表均勻地分為b塊，每塊含有n/b個記錄；又假定表中每個記錄的查找概率相等，并用順序查找確定所在的塊，若要使分塊查找的平均查找長度ASL最小，則分塊數(shù)b的值應(yīng)為（ B ）。(A)n(n+1)/2和n (B)n(n1)/2和n1(C) n(n+1)/21和n1 (D)n2和n39． 若在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序，則該操作的時間復(fù)雜度是（ ）。(A)headnext=s。(B)snext=head。(C)headnext=s。(D)snext=head。41． 設(shè)鏈隊列Q的頭指針和尾指針分別為front和rear，隊中元素個數(shù)為n(n1)，指針*p指向隊首元素m。(A)Qfrontnext=pnext (B)Qrear=Qfront(C)Qfront=prear (D)Qrear=pnext42． 假設(shè)二叉樹T中有n個葉子結(jié)點，且所有非葉子結(jié)點都有左、右子樹，那么二叉樹T共有（ ）個結(jié)點。(A)v1,v6,v3,v4,v2,v5 (B)v1,v6,v4,v3,v2,v5(C)v1,v3,v2,v4,v6,v5 (D)v1,v3,v6,v4,v5,v244． 已知一棵二叉樹的結(jié)點數(shù)據(jù)采用順序存儲結(jié)構(gòu)，數(shù)組內(nèi)容如下表所示，則該二叉樹的后序遍歷序列為（ ）。 (A)n/2 (B)(n2)/2 (C)(n1)/2 (D)(n+1)/246．