【正文】 有一組數(shù)值14,21,32,15,28，用以構(gòu)造huffman樹，則其WPL值為（ ）。 (A)O(n),O(log2n) (B)O(n2),O(log2n) (C)O(log2n),O(n2) (D)O(nlog2n),O(n2)48． 假設(shè)結(jié)點(diǎn)序列為{60,30,90,50,95,70,40,80}，以此構(gòu)成一棵二叉排序樹，則在該二叉排序樹上查找一個(gè)結(jié)點(diǎn)的平均查找長(zhǎng)度為（ ）。for(i=1。 i++) for(j=1。 j++){ c[i][j]=0。k＜＝w。 (A)（n+1）/2 (B)n/2 (C)n (D)n+151． 利用3，6，8，12，5，7這六個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹的深度為（ B ）。 (A)a,b,c,d,e,f,g (B)c,b,d,a,e,g,f (C)c,d,b,g,f,e,a (D)a,b,e,c,d,f,g53． 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ ）。 (B)O(1) (D)O(n2)54． 若在線性表中采用折半查找法查找元素，該線性表應(yīng)該（ ）。 (B)采用順序存儲(chǔ)結(jié)構(gòu) (C)元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu) (D)元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)55． 已知一算術(shù)表達(dá)式的中綴形式為A＋B *CD/E，后綴形式為ABC *+DE/，其前綴形式為（ ）。(A)–A+B*C/DE (D)+A*BC/DE56． 若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左右子樹的位置，利用（ ）遍歷方法最合適。(A)前序 (C)后序 (B)中序 (D)按層次58． 具有n個(gè)頂點(diǎn)的有向圖最多有（ ）條邊。(A)n C n(n+1) (B)選擇 (D)二路歸并60． 排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是（ ）排序法。(A)插入 (C)冒泡 (A)插入 (C)二路歸并 (A){38，46，79，56，40，84} (B){38，79，56，46，40，84}(C){40，38，46，56，79，84} (D){38，46，56，79，40，84}63． 線性鏈表不具有的特點(diǎn)是（ ）。(A)n1 (B)n (C)n+1 (D)n+265． 具有65個(gè)結(jié)點(diǎn)的完全二叉樹的高度為（?。?。(A)直接插入排序 (B)快速排序(C)歸并排序 (D)直接選擇排序67． 在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ ）倍。 (A)R[0]，R[1]，R[2]，R[3] (B)R[0]，R[13]，R[2]，R[3] (C)R[6]，R[2]，R[4]，R[3] (D)R[6]，R[4]，R[2]，R[3]69． 若度為m的哈夫曼樹中,其葉結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù)為（ ）。 (A)算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)(B)為解決某問題的算法同為該問題編寫的程序含義是相同的(C)算法的可行性是指指令不能有二義性 (D)以上幾個(gè)都是錯(cuò)誤的71． 以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語(yǔ)是（ ）。(A)廣義表 (B)二叉樹 (C)稀疏矩陣 (D) 串73． 以下那一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？（ ）(A)棧 (B)哈希表 (C)線索樹 (D) 雙向鏈表74． 在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（ ）。(A) O(2n) (B)O(n) (C)O(n2) (D)O(log2n) 75． 以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（ ）。 (A)一定連續(xù) (B)一定不連續(xù) (C)不一定連續(xù) (D)部分連續(xù)，部分不連續(xù)77． (A)0 (B)1 (C)2 (D)不確定78． 設(shè)圖G采用鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度是（ B ）。(A)堆排序 (B)冒泡排序 (C)快速排序 (D)SHELL排序80． 已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，則采用（ B ）排序算法最節(jié)省時(shí)間。(A)不少于一個(gè)字母的序列 (B)任意個(gè)字母的序列(C)不少于一個(gè)字符的序列 (D)有限個(gè)字符的序列82． 一個(gè)棧的輸入序列為12345，則下列序列中是棧的輸出序列的是（ A ）。(A)rf (B)rf+1 (C)(rf) mod n +1 (D)(rf+n) mod n84． 二叉樹在線索化后，仍不能有效求解的問題是（ D ）。(A)O(n) (B)O(n+e) (C)O(n2) (D)O(n3)86． 一棵左右子樹不空的二叉樹在先序線索化后，其空指針域數(shù)為（ B ）。(A)1140 (B)1145 (C)1120 (D)112588． 在下列排序算法中，在待排序的數(shù)據(jù)表已經(jīng)為有序時(shí)，花費(fèi)時(shí)間反而最多的是（ A ）。(A)123 (B)9523 (C)953 (D)942390． 下列排序算法中，某一趟結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是（ D ）。(A)LL (B)LR (C)RL (D)RR92． 下列各式中，按增長(zhǎng)率由小至大的順序正確排列的是（ ）。(A)s＞next=p＞next。(B)p＞next=s。 s＞next=p。p＞next=s＞next。(A)各自的頭結(jié)點(diǎn) (B)各自的尾結(jié)點(diǎn)(C)各自的第一個(gè)元素結(jié)點(diǎn) (D)一個(gè)表的頭結(jié)點(diǎn)，另一個(gè)表的尾結(jié)點(diǎn)95． 棧的兩種常用存儲(chǔ)結(jié)構(gòu)分別為（ ）。(A)5 (B)6 (C)16 (D)1797． 已知在如下定義的鏈串結(jié)點(diǎn)中，每個(gè)字符占1個(gè)字節(jié)，指針占4個(gè)字節(jié)，則該鏈串的存儲(chǔ)密度為（ ）。struct node * next。(A)1/4 (B)1/2 (C)2/3 (D)3/498． 應(yīng)用簡(jiǎn)單的匹配算法對(duì)主串s=“BDBABDABDAB”與子串t=“BDA”進(jìn)行模式匹配，在匹配成功時(shí)，進(jìn)行的字符比較總次數(shù)為（ ）。(A)574 (B)576 (C)578 (D)580100． 對(duì)廣義表L=((a,b),c,d)進(jìn)行操作tail (head (L))的結(jié)果是（ ）。(A)ABCDEF (B)ABCEFD (C)ABFCDE (D)ABCDFE102． 一個(gè)含n個(gè)頂點(diǎn)和e條弧的有向圖以鄰接矩陣表示法為存儲(chǔ)結(jié)構(gòu)，則計(jì)算該有向圖中某個(gè)頂點(diǎn)出度的時(shí)間復(fù)雜度為（ ）。(A)4，4，3 (B)4， 3， 3 (C)3，4，4 (D)3，3，4104． 下列排序方法中，最好與最壞時(shí)間復(fù)雜度不相同的排序方法是（ ）。(A) (B) (C) (D)106． 在下列各種文件中，不能進(jìn)行順序查找的文件是（ ）。 for(int i=0。i++) for(int j=i+1。j++) coutijendl。(A)(n1)/2 (B)n/2 (C)(n+1)/2 (D)不確定109． 在雙向鏈表p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是（ ）。right=s。left=p。right224。s224。right。right=s。right224。s224。s224。right。left=p。right=p224。p224。p224。left=s。left=p。right=p224。p224。left=s。right=s。 (A)串長(zhǎng)度相等 (B)串使用相同的存儲(chǔ)結(jié)構(gòu) (C)串相同位置對(duì)應(yīng)的字符相等 (D)A和C111． 將一個(gè)遞歸算法改為對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用（ ）。(A) 12345 (B)54321 (C)32514 (D)12354 113． 設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1~n，其頭尾指針分別為f和r，則其元素個(gè)數(shù)為（ ）。(A) DFEBHCGA (B)DFEBHGCA (C)DEFBHGCA (D)DFEHBGCA 115． 正則二叉樹是只有度為0和2的結(jié)點(diǎn)的二叉樹，已知正則二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)為n，則該二叉樹總得結(jié)點(diǎn)數(shù)為（ ）。(A)快速排序、歸并排序都是一種不穩(wěn)定的排序方法(B)直接插入排序和折半插入排序移動(dòng)元素的次數(shù)相同(C)簡(jiǎn)單選擇排序移動(dòng)元素的次數(shù)最少(D)根據(jù)排序需要的平均時(shí)間，快速排序是目前最好的一種內(nèi)部排序方法117． 折半查找有序表（3，4，5，10，13，14，20，30），若查找元素3， 則被比較的元素依次為（ ）。(A)棧是先進(jìn)先出的線性表，隊(duì)列是后進(jìn)先出的線性表(B)棧是先進(jìn)先出的線性表，隊(duì)列也是先進(jìn)先出的線性表(C)棧是后進(jìn)先出的線性表，隊(duì)列是先進(jìn)先出的線性表(D)棧是后進(jìn)先出的線性表，隊(duì)列也是后進(jìn)先出的線性表119． 兩個(gè)各有n個(gè)元素的有序列表并成一個(gè)有序表，其最少的比較次數(shù)是（ ）。 (A)rf (B)rf 1 (C)(rf 1)mod n (D)(rf n)mod n121． 一個(gè)5行6列的二維數(shù)組s采用從最后一行開始，每一行的元素從右至左的方式映射到一維數(shù)組a中，s和a的下標(biāo)均從0開始，則s[3][3]在a中的下標(biāo)是（ ）。 (A)2n (B)n (C)2n 1 (D)2n1123． 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（ ）個(gè)（設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為1）。 (A)前序周游 (B)中序周游 (C)后序周游 (D)層次周游125． 一棵前序序列為1，2，3，4的二叉樹，其中序序列不可能是（ ） 。 (A)e (B)2e (C)n2e (D)n22e 127． 具有n個(gè)頂點(diǎn)和e條邊的圖的深度優(yōu)先搜索算法的時(shí)間復(fù)雜度為（ ）。 (A)n (B)n l (C)nl (D)2n 129． 堆排序算法在平均情況下的時(shí)間復(fù)雜度為（ ）。 (A)直接插入排序 (B)直接選擇排序 (C)快速排序 (D)歸并排序 131． 在理想情況下，散列表中查找元素所需的比較次數(shù)為（ ）。 (A)m (B)m +1 (C)ml (D)m／2133． 設(shè)順序循環(huán)隊(duì)列Q[0：M1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ C ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA135． 設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（ A ）條邊。 (A) 9 (B) 10 (C) 11 (D) 12137． 設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（ B ）個(gè)表頭結(jié)點(diǎn)。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8139． 設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，則數(shù)據(jù)結(jié)構(gòu)A是（ B ）。 (A) q=pnext；pdata=qdata；pnext=qnext；free(q)；(B) q=pnext；qdata=pdata；pnext=qnext；free(q)； (C) q=pnext；pnext=qnext；free(q)； (D) q=pnext；pdata=qdata；free(q)；142． 設(shè)有n個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要（ A ）個(gè)輔助記錄單元。 (A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，21144． 設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長(zhǎng)度為（ B ）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e