【正文】 ，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為（ A ）。 (A) n1 (B) n (C) n+1 (D) 2n1138． 設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（ C ）。 (A) RF (B) FR (C) (RF+M)％M (D) (FR+M)％M134． 設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ A ）。 (A)O(n) (B)O(nlogn) (C)O(n2) (D)O(logn) 130． 在待排序數(shù)據(jù)已基本有序的前提下，下述排序方法中效率最高的是（ ）。 (A)4,1,2,3 (B)4,3,2,1 (C)2,4,3,1 (D)3,4,2,1126． 在含n個頂點和e條邊的有向圖的鄰接矩陣中，零元素的個數(shù)為（ ）。 (A)7 (B)8 (C)9 (D)10122． 設(shè)只含根結(jié)點的二叉樹的高度為1，則高度為n的二叉樹中所含葉子結(jié)點的個數(shù)最多為（ ）個。(A)10,20,30 (B)10,14,30 (C)13,3 (D)10, 4, 3118． 下面關(guān)于棧和隊列的說法正確的是（ ）。(A)rf (B)rf+1 (C)(rf) mod n +1 (D)(rf+n) mod n114． 某二叉樹的前序遍歷結(jié)點訪問順序是ABDEFCGH, 中序遍歷的結(jié)點訪問順序是DBFEAGHC, 則其后序遍歷的結(jié)點訪問順序是（ ）。110． 字符串相等的充分必要條件是（ ）。right224。s224。right224。right。(C)s224。left=p。p224。right=p224。p224。(A)p224。jn。(A)順序文件 (B)索引文件 (C)散列文件 (D)多重表文件107． 下面帶有標(biāo)記的語句的頻度(n10)是（ ）。(A)O(n) (B)O(e) (C)O(n+e) (D)O(n2)103． 在關(guān)鍵字序列（12，23，34，45，56，67，78，89，91）中二分查找關(guān)鍵字為45，89和12的結(jié)點時，所需進(jìn)行的比較次數(shù)分別為（ ）。(A)7 (B)9 (C)10 (D)1299． 二維數(shù)組A[20][10]采用列優(yōu)先的存儲方法，若每個元素占2個存儲單元，且第1個元素的首地址為200，則元素A[8][9]的存儲地址為（ ）。typedef struct node{char date[8]。94． 若要在O（1）的時間復(fù)雜度上實現(xiàn)兩個循環(huán)鏈表頭尾相接，則應(yīng)對兩個循環(huán)鏈表各設(shè)置一個指針，分別指向（ ）。 s＞next=p＞next(C)p＞next=s＞next。(A),n!,2n,n3/2 (B)n3/2,2n,nlogn,2100(C)2n, logn, nlogn, n3/2 (D)2100, logn, 2n, nn93． 若要在單鏈表中的結(jié)點*p之后插入一個結(jié)點*s，則應(yīng)執(zhí)行的語句是（ ）。(A)快速排序 (B)希爾排序 (C)冒泡排序 (D)堆排序89． 對有18個元素的有序表做折半查找，則查找A[3]的比較序列的下標(biāo)依次為（ D ）。(A)先序線索二叉樹中求先序后繼 (B)中序線索二叉樹中求中序后繼 (C)中序線索二叉樹中求中序前驅(qū) (D)后序線索二叉樹中求后序后繼85． 求最短路徑的FLOYD算法的時間復(fù)雜度為（ D ）。(A)堆排序 (B)插入排序 (C)快速排序 (D)直接選擇排序81． 串是（ D ）。一棵左右子樹均不空的二叉樹在先序前驅(qū)和后序后繼線索化后，其空鏈域數(shù)為（ A ）。FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1。 (A)[(n+1)/(m+1)]1 (B)[n/m]1 (C)[(n1)/(m1)] (D)[n/(m1)]1 70． 下面關(guān)于算法說法錯誤的是（ ）。（根的層次號為0） (A)8 (B)7 (C)6 (D)566． 若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，則采用（ ）方法比較次數(shù)最少。 (D)堆62． 一個對象序列的排序碼為{46，79，56，38，40，84}，采用快速排序以位于最左位置的對象為基準(zhǔn)而得到的第一次劃分結(jié)果為（ ）。 (B)選擇 (C)shell (D)n259． 從未排序序列中依次取出一個元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（ ）排序法。 (A) 前序 (B)中序 (B)–A+B*CD/E (C)+*ABC/DE (A)元素按值有序 (C)O(n) (A)3 (B)4 (C)5 (D)652． 一棵二叉樹的廣義表表示為a(b(c,d),e(,f(g))),則得到的層次遍歷序列為 （ D ）。 for(k=1。i＜＝n。 (A)267 (B)189 (C)110 (D)29447． 采用折半插入排序，關(guān)鍵字的比較次數(shù)與移動次數(shù)分別為（ ）。(A)2n (B)2n1 (C)2n+1 (D)2n+243． 已知有向圖G的鄰接矩陣如下所示，則下列序列中（ ）不可能是圖G的拓?fù)湫蛄?。headnext=s。headnext=NULL。(A)O(1) (B)O(n2) (C)O(nlog2n) (D)O(n)40． 在一個頭結(jié)點為head的空循環(huán)鏈表中插入一個結(jié)點s，則指針s應(yīng)執(zhí)行操作（ ）。(A)3/2 (B)10/7 (C)11/7 (D)9/736． 以數(shù)據(jù)集{4，5，6，7，12，18，10}為結(jié)點權(quán)值所構(gòu)造的哈夫曼樹，則其帶權(quán)路徑長度WPL為（ A ）。 (D)后序34． 已知一個長度為12的線性表（8，2，5，7，12，3，10，4，1，6，9，11），并將線性表中的元素依次插入到一個原先為空的二叉排序樹中去。 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 ）。(D)Qfrontnext=s。Qrear=NULL。snext=Qrear。 snext=p。pnext=s。(A)單鏈表 (B)單循環(huán)鏈表 (C)無頭雙向鏈表 (D)帶頭雙向鏈表28． 已知head是一個非空單鏈表的頭指針，指針p指向單鏈表的最后一個結(jié)點，若要在p之后插入一個新結(jié)點*s，并將單鏈表變?yōu)檠h(huán)單鏈表，則應(yīng)執(zhí)行的操作是（ B ）。 j++。(A)5/3 (B)13/9 (C)16/9 (D)3/225． 下列程序段所代表的算法的時間復(fù)雜度為（ D ）。(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)n=m+h (B)h+m=2n (C)m=h1 (D)n=2h118． 一棵左、右子樹均不為空的二叉樹在先序線索化后，其空指針域數(shù)為 （ B ）。x=HSdata。 HS=HSnext。(A)單鏈表 (B)雙鏈表 (C)單循環(huán)鏈表 (D)順序表14． 一個帶頭結(jié)點head的循環(huán)單鏈表為空的判斷條件是（ C ）。x=1。(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)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 ）。pnext=Qfront。snext=Qfront。若要進(jìn)隊一個元素*s，則在下列程序算法的空白處應(yīng)添加的操作語句是（ A ）。HS=s。(A)HSnext=s。 y=0。x=n。(A) n2 (B)(n1)/2 (C)(n+1)/2 (D)n/23． 在一個棧頂指針為HS的鏈棧中插入一個*s結(jié)點時，應(yīng)執(zhí)行執(zhí)行操作為 （ C ）。(C)snext=HS。4． 假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列Q，并且隊列只設(shè)一個頭指針front，不設(shè)隊列尾指針。 }(A)pnext=s。(C)snext=p。5． 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（ B ）。(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 ）。y=n。(A)n2 (B)(n+1)/2 (C)(n1)/2 (D)n/213． 若對一個已有序的線性表最頻繁的操作是查找值為x的元素(假設(shè)存在的話)，則采用（ D ）存儲方式實現(xiàn)查找，其算法的時間復(fù)雜度為最小。(A)x=HSdata。(C)HS=HSnext。17． 一棵有n個結(jié)點的滿二叉樹，有m個葉子結(jié)點，深度為h，那么n、m和h滿足條件（ D ）。(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ù)湫蛄小Ｈ舨捎镁€性探查法解決沖突，則平均查找長度為（ C ）。 while(i=n) {i+=j。 (B)n (D)n127． 若某鏈表中最常用的操作是在最后的一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用（ D ）存儲方式最節(jié)省運(yùn)行時間。 (B)snext=head。 (D)snext=pnext。(A)Qfrontnext=s。Qrearnext=s。snext=NULL。31． 已知一個帶權(quán)圖的頂點集V和邊集G分別為： V={1,2,3,4,5,6,7,8}。(A)層次 假設(shè)查找每一個元素的概率相同，則查找該HASH表中任一元素的平均查找長度為（ C ）。(A)n(n+1)/2和n (B)n(n1)/2和n1(C) n(n+1)/21和n1 (D)n2和n39． 若在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序，則該操作的時間復(fù)雜度是（ ）。(B)snext=head。(D)snext=head。(A)Qfrontnext=pnext (B)Qrear=Qfront(C)Qfront=prear (D)Qrear=pnext42． 假設(shè)二叉樹T中有n個葉子結(jié)點，且所有非葉子結(jié)點都有左、右子樹，那么二叉樹T共有（ ）個結(jié)點。 (A)n/2 (B)(n2)/2 (C)(n1)/2 (D)(n+1)/246． 有一組數(shù)值14,21,32,15,28，用以構(gòu)造huffman樹，則其WPL值為（ ）。for(i=1。 j++){ c[i][j]=0。 (A)（n+1）/2 (B)n/2 (C)n (D)n+1