數(shù)據(jù)結構試題庫

數(shù)據(jù)結構試題庫一、 單項選擇題1．下列程序段所代表的算法的時間復雜度為（ D ）。x=n;y=0;while(x>=(y+1)*(y+1))y++;(A)O(n)2n(D)O(n)(B)O(n)(C)O(log2)2．在一個長度為 n的以順序結構存儲的線性表中，假設在線性表的任何位置刪除元素的概率相等，則刪除一個元素時線性表所需移動元素的平均次數(shù)為（ B ）。(A)n2 (B)(n-1)/2 (C)(n+1)/2 (D)n/23．在一個棧頂指針為 HS 的鏈棧中插入一個 *s 結點時，應執(zhí)行執(zhí)行操作為（ C）。(A)HS->next=s; (B)s->next=HS->next;HS->next=s;(C)s->next=HS;HS=s; (D)s->next=HS;HS=HS>next;4．假設以帶頭結點的循環(huán)鏈表表示隊列 Q，并且隊列只設一個頭指針 front，不設隊列尾指針。 若要進隊一個元素 *s，則在下列程序算法的空白處應添加的操作語句是（ A ）。voidAddQueue(structlinkqueueQ){p=Q->front;while(p->next!=Q->front)p=p->next;}(A)p->next=s;s->next=Q->front;(B)Q->front->next=s;Q->front=s;(C)s->next=p;p->next=Q->front;(D)Q->front->next=s;s->next=p;5．設高度為 h的二叉樹上只有度為 0和度為 2的結點，則此類二叉樹中所包含的結點數(shù)至少為（ B ）。(A)2h-1 (B)2h-1+1 (C)2h-1 (D)2h-1-3第 1頁 共 100 頁6．現(xiàn)有數(shù)據(jù)集 {53,30,37,12,45,24,96} ，從空二叉樹逐個插入數(shù)據(jù)形成二叉排序樹，若希望查找此二叉樹中任一結點的平均查找長度最小，則應選擇下面哪個序列輸入（ C）。(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} ，用以構造哈夫曼樹，則其帶權路徑長度 WPL 值為（ D ）。(A)93 (B)96 (C)123 (D)1038．已知一個有向圖 G的頂點 v={v1,v2,v3,v4,v5,v6} ，其鄰接表如下圖所示， 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點 v1出發(fā)，所得到的頂點遍歷序列是（ 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,v6v1v2v5v4^v2^v3v5^v3v6^v4^v5v4v6^v3^v6^n9．設有m=2-1個關鍵字，假設對每個關鍵字查找的概率相等，查找失敗的概率為0，若采用二分法查找一個關鍵字，則平均查找長度為（ D）。(A)n-1 (B)n-n/m (C)(n-1)-n/m (D)(n-1)+n/m10．已知一個待散列存儲的線性表{18,81,58,34,26,75,67,49,93} ，散列函數(shù)為h(k)=k%11，散列地址空間為 0~10。若采用線性探查法解決沖突，則平均查找長度為（ A ）。(A)5/3 (B)13/9 (C)16/9 (D)3/211．下列程序段所代表的算法的時間復雜度為（ C）。y=n;x=1;第 2頁 共 100 頁while(x<=y)x*=2;(A)O(n)2n(D)O(n)(B)O(n)(C)O(log2)12．在一個長度為n的以順序結構存儲的線性表中，假設在線性表的任何位置插入元素的概率相等，則插入一個元素時線性表所需移動元素的平均次數(shù)為（B）。2(B)(n+1)/2(C)(n-1)/2(D)n/2(A)n13．若對一個已有序的線性表最頻繁的操作是查找值為x的元素(假設存在的話)，則采用（D）存儲方式實現(xiàn)查找，其算法的時間復雜度為最小。(A)單鏈表(B)雙鏈表(C)單循環(huán)鏈表(D)順序表14．一個帶頭結點 head的循環(huán)單鏈表為空的判斷條件是（ C）。(A)head==NULL (B)head->next==NULL(C)head->next==head (D)head!=NULL15．若鏈隊列 HQ 中只有一個結點，則隊列的頭指針和尾指針滿足下列條件（ D ）。(A)HQ->rear->next==HQ->front (B)HQ->front->next==HQ->rear->next(C)HQ->front==HQ->rear (D)HQ->front->next==HQ->rear16．從一個棧頂指針為 HS的鏈棧中刪除一個結點時，用 x保存被刪除結點的值，則應執(zhí)行操作為（ A）。(A)x=HS->data;HS=HS->next; (B)x=HS->data;HS->NEXT=NULL;(C)HS=HS->next;x=HS->data; (D)x=HS->data;HS=NULL;17．一棵有 n個結點的滿二叉樹，有 m個葉子結點，深度為 h，那么 n、m和h滿足條件（ D ）。(A)n=m+h (B)h+m=2n (C)m=h-1 (D)n=2h-118．一棵左、右子 樹均不 為空的二 叉樹在 先序線 索化后， 其空指 針域數(shù)為（ B ）。(A)0 (B)1 (C)2 (D)不確定19．有一組數(shù)值 {5,12,9,20,3} ，用以構造哈夫曼樹，則其帶權路徑長度 WPL 值為（ C）。第 3頁 共 100 頁(A)49 (B)96 (C)103 (D)12520．在一個 n個結點的二叉排序樹中查找一個關鍵字， 進行關鍵字比較次數(shù)最大值為（A）。(A)n(B)n/2nn(C)log2(D)n*log221．已知有向圖 G=(V,E)，其中 V={v1,v2,v3,v4,v5,v6} ，則下列邊集合 E中A）所對應的有向圖沒有拓撲序列。E={<v2,v1>,<v6,v2>,<v1,v3>,<v2,v3>,<v5,v3>,<v3,v4>,<v4,v6>,<v5,v6>}E={<v1,v2>,<v1,v3>,<v1,v4>,<v3,v5>,<v3,v2>,<v4,v5>,<v6,v5>,<v6,v4>}E={<v1,v3>,<v1,v4>,<v1,v5>,<v2,v3>,<v2,v2>,<v3,v5>,<v3,v6>,<v4,v5>,<v4,v6>,<v5,v6>}E={<v1,v2>,<v1,v3>,<v2,v3>,<v1,v4>,<v2,v5>,<v3,v6>,<v4,v6>,<v5,v6>}22．冒泡排序算法在最好情況下的時間復雜度為（B）。(A)O(log2n)(B)O(n)(C)O(1)2(D)O(n)23．在下列內(nèi)部排序方法中， 排序時不穩(wěn)定的， 而且關鍵字的比較次數(shù)與記錄的初始排列次序無關的是（ D ）。(A)快速排序 (B)冒泡排序 (C)歸并排序 (D)堆排序24．已知一個待散列存儲的線性表{18,81,58,34,26,75,67,49,93} ，散列函數(shù)為h(k)=k%11，散列地址空間為0~10。若采用線性探查法解決沖突，則平均查找長度為（C）。(A)5/3 (B)13/9 (C)16/9 (D)3/225．下列程序段所代表的算法的時間復雜度為（ D）。i=1;j=0;while(i<=n){i+=j;j++;}(A)O(n)2n(D)O(n)(B)O(n)(C)O(log2)第 4頁 共 100 頁26．將兩個各有 n個元素的有序表歸并成一個有序表， 在最壞的情況下， 其比較次數(shù)是（ A ）。(A)2n-1 (B)n (C)n+1 (D)n-127．若某鏈表中最常用的操作是在最后的一個結點之后插入一個結點或刪除最后一個結點，則采用（ D）存儲方式最節(jié)省運行時間。(A)單鏈表 (B)單循環(huán)鏈表 (C)無頭雙向鏈表 (D)帶頭雙向鏈表28．已知head是一個非空單鏈表的頭指針，指針p指向單鏈表的最后一個結點，若要在p之后插入一個新結點*s，并將單鏈表變?yōu)檠h(huán)單鏈表，則應執(zhí)行的操作是（B）。(A)s->next=p->next;p->next=s; (B)s->next=head;p->next=s;(C)s->next=p->next;p->next=head; (D)s->next=p->next;s->next=p;29．已知用循環(huán)鏈表表示的隊列長度為 n，若只設頭指針，則出隊和入隊一個元素的時間復雜度分別是（ B ）。(A)O(1)和O(1) (B)O(1)和O(n)(C)O(n)和O(1) (D)O(n) 和O(n)30．設鏈隊列Q的頭指針和尾指針分別為front和rear，初始時隊列為空，若向隊列插入一個元素*s，則應執(zhí)行的指針操作為（C）。(A)Q->front->next=s;s->next=Q->rear;Q->rear=NULL;(B)s->next=Q->front;Q->rear->next=s;Q->rear=NULL;(C)Q->rear->next=s;Q->rear=s;s->next=NULL;(D)Q->front->next=s;Q->rear=s;s->next=NULL;31．已知一個帶權圖的頂點集 V和邊集 G分別為：V={1,2,3,4,5,6,7,8};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},則該圖的最小生成樹的權值為（C）。(A)24(B)29(C)30(D)3132．當待排序的關鍵字個數(shù) n很小，且初始排列為逆序時， 采用下列排序方法中的（ D ），算法的時間復雜度最小。第 5頁 共 100 頁(A)直接插入排序 (B)簡單選擇排序(C)冒泡排序 (D)快速排序33．對二叉排序樹進行 （ C）遍歷，可以得到該二叉樹所有結點構成的排序序列。(A)層次 (B)前序 (C)中序 (D)后序34．已知一個長度為 12的線性表（ 8，2，5，7，12，3，10，4，1，6，9，11），并將線性表中的元素依次插入到一個原先為空的二叉排序樹中去。假設查找每一個元素的概率相同，則查找該二叉樹中任一結點的平均查找長度為（ A ）。(A)10/3 (B)13/3 (C)37/12 (D)13/235．一組關鍵字序列 {15，92，124，5，27，28，18，6，36，34，30，26，32，259}，將它們用散列函數(shù) H(key)=keyMOD11 按順序散列到 HASH 表HT（0:10）中，用鏈地址解決沖突。假設查找每一個元素的概率相同，則查找該 HASH 表中任一元素的平均查找長度為（ C）。(A)3/2 (B)10/7 (C)11/7 (D)9/736．以數(shù)據(jù)集 {4，5，6，7，12，18，10}為結點權值所構造的哈夫曼樹，則其帶權路徑長度 WPL為（ A ）。(A)165 (B)203 (C)124 (D)18737．假定對線性表 R[0?ｎ-1]進行分塊查找， 若將表均勻地分為 b塊，每塊含有 n/b個記錄；又假定表中每個記錄的查找概率相等，并用順序查找確定所在的塊，若要使分塊查找的平均查找長度 ASL 最小，則分塊數(shù) b的值應為（ B ）。(A) n (B) n+1 (C)「log2n」 (D)「log2n」+138．對n個記錄進行直接插入排序， 所需的關鍵字比較次數(shù)的最大值和最小值分別是（ C）。(A)n(n+1)/2 和n (B)n(n-1)/2 和n-1(C)n(n+1)/2-1 和n-1 (D)n2和n39．若在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序，則該操作的時間復雜度是（）。(A)O(1)2n(D)O(n)(B)O(n)(C)O(nlog2)40．在一個頭結點為 head的空循環(huán)鏈表中插入一個結點 s，則指針 s應執(zhí)行操作第 6頁 共 100 頁（ ）。(A)head->next=s;s->next=NULL;(B)s->next=head;head->next=NULL;(C)head->next=s;s->next=head->next;(D)s->next=head;head->next=s;41．設鏈隊列Q的頭指針和尾指針分別為front和rear，隊中元素個數(shù)為n(n>1)，指針*p指向隊首元素m。若刪除元素m，則應進行的指針操作為（）。(A)Q->front->next=p->next (B)Q->rear=Q->front(C)Q->front=p->rear (D)Q->rear=p->next42．假設二叉樹 T中有 n個葉子結點，且所有非葉子結點都有左、右子樹，那么二叉樹 T共有（ ）個結點。(A)2n(B)2n-1(C)2n+1(D)2n+243．已知有向圖 G的鄰接矩陣如下所示，則下列序列中（ ）不可能是圖 G的拓撲序列。(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,v201110000000001001000001000000000011044．已知一棵二叉樹的結點數(shù)據(jù)采用順序存儲結構， 數(shù)組內(nèi)容如下表所示， 則該二叉樹的后序遍歷序列為（ ）。123456789101112131415161718192021EAFDGCJIHB(A)ACBDJEFIGH (B)ABCDJEFHGI(C)BCJDAHIGFE (D)EADCBJFGIH第 7頁 共 100 頁45．若T為n個結點的完全二叉樹，則 T的葉子結點數(shù)為（ ）。(A)n/2 (B)(n-2)/2 (C)(n-1)/2 (D)(n+1)/246．有一組數(shù)值14,21,32,15,28，用以構造huffman樹，則其WPL值為（）。(A)267(B)189(C)110(D)29447．采用折半插入排序，關鍵字的比較次數(shù)與移動次數(shù)分別為（）。(A)O(n),O(log2n)2(B)O(n),O(log2n)22(C)O(log2n),O(n)(D)O(nlog2n),O(n)48．假設結點序列為 {60,30,90,50,95,70,40,80} ，以此構成一棵二叉排序樹，則在該二叉排序樹上查找一個結點的平均查找長度為（ ）。(A)23/8 (B)11/4 (C)9/2 (D)449．下面程序段的時間復雜性的量級為（ D ）。for(i=1;i ＜＝n;i++)for(j=1;j＜＝m;j++){c[i][j]=0;for(k=1;k ＜＝w;k++)c[i][j]+=a[i][k]*b[k][j]}(A)O(i*j*k) (B)O(n*m*k)(C)O(n*j*k) (D)O(n*m*w)50．在一個長度為

n的線性表中， 刪除值為

x的元素時需要比較元素和移動元素的總次數(shù)為（

C ）。(A)（n+1）

/2

(B)n/2(C)n

(D)n+151．利用3，6，8，12，5，7這六個值作為葉子結點的權，生成一棵哈夫曼樹，該樹的深度為（ B ）。(A)3 (B)4 (C)5 (D)652．一棵二叉樹

的廣義表表示為第 8

a(b(c,d),e(,f(g))),頁共100頁

則得到的層次遍歷序列為（ D ）。(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．若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為（）。(1≤i≤n+1)(A)O(0)(B)O(1)(C)O(n)(D)O(n2)54．若在線性表中采用折半查找法查找元素，該線性表應該（）。(A)元素按值有序(B)采用順序存儲結構元素按值有序，且采用順序存儲結構元素按值有序，且采用鏈式存儲結構55．已知一算術表達式的中綴形式為 A＋B*C-D/E ，后綴形式為 ABC*+DE/- ，其前綴形式為（ ）。–A+B*C/DE(B)–A+B*CD/E(C)-+*ABC/DE(D)-+A*BC/DE56．若二叉樹采用二叉鏈表存儲結構， 要交換其所有分支結點左右子樹的位置， 利用（ ）遍歷方法最合適。(A)前序 (B)中序 (C)后序 (D)按層次57．對二叉排序樹進行（ ）遍歷，可以得到該二叉樹所有結點構成的排序序列。(A) 前序 (B)中序 (C)后序 (D)按層次58．具有n個頂點的有向圖最多有（ ）條邊。(A)n (B)n(n—1) Cn(n+1) (D)n259．從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（）排序法。(A)插入(B)選擇(C)shell(D)二路歸并60．排序趟數(shù)與序列的原始狀態(tài)有關的排序方法是（）排序法。(A)插入(B)選擇(C)冒泡(D)快速61．下面給出的四種排序法中（ ）排序法是不穩(wěn)定性排序法。第 9頁 共 100 頁(A)插入(B)冒泡(C)二路歸并(D)堆62．一個對象序列的排序碼為{46，79，56，38，40，84}，采用快速排序以位于最左位置的對象為基準而得到的第一次劃分結果為（）。(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．線性鏈表不具有的特點是（）。(A)隨機訪問(B)不必事先估計所需存儲空間大小(C)插入與刪除時不必移動元素(D)所需空間與線性表長度成正比64．設F是一個森林，B是由F轉換得到的二叉樹，F(xiàn)中有n個非葉結點，則B中右指針域為空的結點有（）個。(A)n-1(B)n(C)n+1(D)n+265．具有65個結點的完全二叉樹的高度為（）。（根的層次號為0）(A)8(B)7(C)6(D)566．若待排序對象序列在排序前已按其排序碼遞增順序排序，則采用（）方法比較次數(shù)最少。(A)直接插入排序(B)快速排序(C)歸并排序(D)直接選擇排序67．在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。(A)3(B)2(C)1(D)1/268．對有14個數(shù)據(jù)元素的有序表R[14]進行折半搜索，搜索到R[3]的關鍵碼等于給定值，此時元素比較順序依次為（）。(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的哈夫曼樹中 ,其葉結點個數(shù)為 n,則非葉結點的個數(shù)為（ ）。(A)[(n+1)/(m+1)]-1 (B)[n/m]-1(C)[(n-1)/(m-1)] (D)[n/(m-1)]-1第 10頁 共 100 頁70．下面關于算法說法錯誤的是（ ）。算法最終必須由計算機程序實現(xiàn)為解決某問題的算法同為該問題編寫的程序含義是相同的算法的可行性是指指令不能有二義性以上幾個都是錯誤的71．以下與數(shù)據(jù)的存儲結構無關的術語是（）。(A)循環(huán)隊列(B)鏈表(C)哈希表(D)棧72．以下數(shù)據(jù)結構中，哪一個是線性結構（）。(A)廣義表(B)二叉樹(C)稀疏矩陣(D)串73．以下那一個術語與數(shù)據(jù)的存儲結構無關？（）(A)棧(B)哈希表(C)線索樹(D)雙向鏈表74．在下面的程序段中，對 x的賦值語句的頻度為（ ）。FORi:=1 TO n DOFORj:=1 TO n DOx:=x+1;(A)O(2n) (B)O(n) (C)O(n2) (D)O(log 2n)75．以下哪個數(shù)據(jù)結構不是多型數(shù)據(jù)類型（ ）。(A)棧 (B)廣義表 (C)有向圖 (D)字符串76．連續(xù)存儲設計時，存儲單元的地址（）。(A)一定連續(xù)(B)一定不連續(xù)(C)不一定連續(xù)(D)部分連續(xù)，部分不連續(xù)77．一棵左右子樹均不空的二叉樹在先序前驅和后序后繼線索化后，其空鏈域數(shù)為（ A ）。(A)0 (B)1 (C)2 (D)不確定78．設圖G采用鄰接表存儲，則拓撲排序算法的時間復雜度是（ B）。第 11頁 共 100 頁(A)O(n) (B)O(n+e) (C)O(n2) (D)O(n*e)79．下列排序算法中，時間復雜度為O(nlog2n)且占用額外空間最少的是（A）。(A)堆排序(B)冒泡排序(C)快速排序(D)SHELL排序80．已知數(shù)據(jù)表A中每個元素距其最終位置不遠，則采用（B）排序算法最節(jié)省時間。(A)堆排序(B)插入排序(C)快速排序(D)直接選擇排序81．串是（ D ）。(A)不少于一個字母的序列 (B)任意個字母的序列(C)不少于一個字符的序列 (D)有限個字符的序列82．一個棧的輸入序列為 12345，則下列序列中是棧的輸出序列的是（ A ）。(A)23415 (B)54132 (C)31245 (D)1425383．設循環(huán)隊列中數(shù)組的下標范圍是 1~n，其頭尾指針分別為 f和r，則其元素個數(shù)為（ D ）。(A)r-f (B)r-f+1 (C)(r-f)modn+1 (D)(r-f+n)modn84．二叉樹在線索化后，仍不能有效求解的問題是（D）。(A)先序線索二叉樹中求先序后繼(B)中序線索二叉樹中求中序后繼(C)中序線索二叉樹中求中序前驅(D)后序線索二叉樹中求后序后繼85．求最短路徑的FLOYD算法的時間復雜度為（D）。(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n3)86．一棵左右子樹不空的二叉樹在先序線索化后，其空指針域數(shù)為（ B）。(A)0 (B)1 (C)2 (D)不確定87．數(shù)組A[1..5,1..6]的每個元素占 5個單元，將其按行優(yōu)先順序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[5,5]的地址為（A）。(A)1140(B)1145(C)1120(D)112588．在下列排序算法中， 在待排序的數(shù)據(jù)表已經(jīng)為有序時， 花費時間反而最多的是（ A ）。(A)快速排序 (B)希爾排序 (C)冒泡排序 (D)堆排序89．對有 18 個元素的有序表做折半查找，則查找 A[3]的比較序列的下標依次為（ D ）。(A)1-2-3 (B)9-5-2-3 (C)9-5-3 (D)9-4-2-3第 12頁 共 100 頁90．下列排序算法中，某一趟結束后未必能選出一個元素放在其最終位置上的是（ D ）。(A)堆排序 (B)冒泡排序 (C)快速排序 (D)直接插入排序91．在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡點為A，并已知A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則做（B）型調(diào)整以使其平衡。(A)LL(B)LR(C)RL(D)RR92．下列各式中，按增長率由小至大的順序正確排列的是（）。(A)n,n!,2n,n3/2(B)n3/2,2n,nlogn,2100(C)2n,logn,nlogn,n3/2(D)2100,logn,2n,nn93．若要在單鏈表中的結點 *p之后插入一個結點 *s，則應執(zhí)行的語句是（ ）。(A)s-＞next=p-＞next;p-＞next=s;(B)p-＞next=s;s-＞next=p-＞next(C)p-＞next=s-＞next;s-＞next=p;(D)s-＞next=p;p-＞next=s-＞next;94．若要在 O（1）的時間復雜度上實現(xiàn)兩個循環(huán)鏈表頭尾相接，則應對兩個循環(huán)鏈表各設置一個指針，分別指向（ ）。(A)各自的頭結點 (B)各自的尾結點(C)各自的第一個元素結點 (D)一個表的頭結點，另一個表的尾結點95．棧的兩種常用存儲結構分別為（）。(A)順序存儲結構和鏈式存儲結構(B)順序存儲結構和散列存儲結構(C)鏈式存儲結構和索引存儲結構(D)鏈式存儲結構和散列存儲結構96．已知循環(huán)隊列的存儲空間為數(shù)組data[21]，且當前隊列的頭指針和尾指針的值分別為8和3，則該隊的當前長度為（）。(A)5(B)6(C)16(D)1797．已知在如下定義的鏈串結點中， 每個字符占 1個字節(jié)， 指針占 4個字節(jié)，則該鏈串的存儲密度為（ ）。typedefstructnode{chardate[8];structnode*next;}LinkStrNode;第 13頁 共 100 頁(A)1/4 (B)1/2 (C)2/3 (D)3/498．應用簡單的匹配算法對主串 s=“BDBABDABDAB ”與子串 t=“BDA”進行模式匹配，在匹配成功時，進行的字符比較總次數(shù)為（ ）。(A)7 (B)9 (C)10 (D)1299．二維數(shù)組A[20][10]采用列優(yōu)先的存儲方法，若每個元素占2個存儲單元，且第1個元素的首地址為200，則元素A[8][9]的存儲地址為（）。(A)574(B)576(C)578(D)580100．對廣義表L=((a,b),c,d)進行操作tail(head(L))的結果是（）。(A)(c,d)(B)(d)(C)b(D)(b)101． 已知一棵樹的前序序列為 ABCDEF ，后序序列為 CEDFBA ，則對該樹進行層次遍歷得到的序列為（ ）。(A)ABCDEF (B)ABCEFD (C)ABFCDE (D)ABCDFE102． 一個含 n個頂點和 e條弧的有向圖以鄰接矩陣表示法為存儲結構，則計算該有向圖中某個頂點出度的時間復雜度為（ ）。(A)O(n) (B)O(e) (C)O(n+e) (D)O(n2)103．在關鍵字序列（12，23，34，45，56，67，78，89，91）中二分查找關鍵字為45，89和12的結點時，所需進行的比較次數(shù)分別為（）。(A)4，4，3(B)4，3，3(C)3，4，4(D)3，3，4104．下列排序方法中，最好與最壞時間復雜度不相同的排序方法是（）。(A)冒泡排序(B)直接選擇排序(C)堆排序(D)歸并排序105． 已知含 10個結點的二叉排序樹是一棵完全二叉樹， 則該二叉排序樹在等概率情況下查找成功的平均查找長度等于（ ）。(A)1.0 (B)2.9 (C)3.4 (D)5.5106．在下列各種文件中，不能進行順序查找的文件是（）。(A)順序文件(B)索引文件(C)散列文件(D)多重表文件107． 下面帶有 @標記的語句的頻度 (n>10)是（ ）。for(inti=0;i<n-1;i++)for(intj=i+1;j<n;j++)@cout<<i<<j<<endl;(A)n*(n-1)/2 (B)n*n/2 (C)n*(n+1)/2 (D)不確定第 14頁 共 100 頁108．已知使用順序表存儲數(shù)據(jù)，表長為n，假設在表中的任意位置插入元素的概率相等，則插入一個元素，平均需要移動的元素個數(shù)（）。(A)(n-1)/2(B)n/2(C)(n+1)/2(D)不確定109．在雙向鏈表p所指結點之后插入s所指結點的操作是（）。(A)pright=s;sleft=p;prightleft=s;sright=pright;(B)pright=s;prightleft=s;sleft=p;sright=pright;(C)sleft=p;sright=pright;pright=s;prightleft=s;(D)sleft=p;sright=pright;prightleft=s;pright=s;110．字符串相等的充分必要條件是（）。(A)串長度相等(B)串使用相同的存儲結構(C)串相同位置對應的字符相等(D)A和C111．將一個遞歸算法改為對應的非遞歸算法時，通常需要使用（）。(A)數(shù)組(B)棧(C)隊列(D)二叉樹112． 一個棧的入棧序列 1,2,3,4,5, 則棧的不可能的輸出序列是（ ）。(A)12345 (B)54321 (C)32514 (D)12354113． 設循環(huán)隊列中數(shù)組的下標范圍是 1~n，其頭尾指針分別為 f和r，則其元素個數(shù)為（ ）。(A)r-f (B)r-f+1 (C)(r-f)modn+1 (D)(r-f+n)modn114． 某二叉樹的前序遍歷結點訪問順序是 ABDEFCGH, 中序遍歷的結點訪問順序是 DBFEAGHC, 則其后序遍歷的結點訪問順序是（ ）。(A)DFEBHCGA (B)DFEBHGCA(C)DEFBHGCA (D)DFEHBGCA115． 正則二叉樹是只有度為 0和2的結點的二叉樹，已知正則二叉樹的葉子結點個數(shù)為 n，則該二叉樹總得結點數(shù)為（ ）。(A) n+1 (B)2*n (C)2*n+1 (D)2*n-1116． 下面關于排序的說法錯誤的是（ ）?？焖倥判?、歸并排序都是一種不穩(wěn)定的排序方法直接插入排序和折半插入排序移動元素的次數(shù)相同簡單選擇排序移動元素的次數(shù)最少根據(jù)排序需要的平均時間，快速排序是目前最好的一種內(nèi)部排序方法117． 折半查找有序表（ 3，4，5，10，13，14，20，30），若查找元素 3， 則第 15頁 共 100 頁被比較的元素依次為（ ）。(A)10,20,30 (B)10,14,30 (C)13,3 (D)10,4,3118． 下面關于棧和隊列的說法正確的是（ ）。棧是先進先出的線性表，隊列是后進先出的線性表棧是先進先出的線性表，隊列也是先進先出的線性表棧是后進先出的線性表，隊列是先進先出的線性表棧是后進先出的線性表，隊列也是后進先出的線性表119． 兩個各有 n個元素的有序列表并成一個有序表，其最少的比較次數(shù)是（ ）。(A)n (B)2n-1 (C)2n (D)n-1120． 設循環(huán)隊列中數(shù)組的下標范圍是 0~n-1，f表示隊首元素的前驅位置， r表示隊尾元素的位置，則隊列中元素個數(shù)為（ ）。(A)r-f (B)r-f1 (C)(r-f1)modn (D)(r-fn)modn121．一個5行6列的二維數(shù)組s采用從最后一行開始，每一行的元素從右至左的方式映射到一維數(shù)組a中，s和a的下標均從0開始，則s[3][3]在a中的下標是（）。(A)7(B)8(C)9(D)10122． 設只含根結點的二叉樹的高度為 1，則高度為 n的二叉樹中所含葉子結點的個數(shù)最多為（ ）個。(A)2n (B)n (C)2n-1 (D)2n-1123．設高度為h的二叉樹上只有度為0和度為2的結點，則此二叉樹中所包含的結點數(shù)至少為（）個（設只含根結點的二叉樹的高度為1）。(A)2h(B)2h-1(C)2h+1(D)h+1124．對一棵二叉檢索樹進行（）得到的結點序列是一個有序序列。(A)前序周游(B)中序周游(C)后序周游(D)層次周游125． 一棵前序序列為 1，2，3，4的二叉樹，其中序序列不可能是（ ） 。(A)4,1,2,3 (B)4,3,2,1 (C)2,4,3,1 (D)3,4,2,1126．在含n個頂點和e條邊的有向圖的鄰接矩陣中，零元素的個數(shù)為（）。(A)e(B)2e(C)n2-e(D)n2-2e第 16頁 共 100 頁127． 具有 n個頂點和 e條邊的圖的深度優(yōu)先搜索算法的時間復雜度為（ ）。(A)O(n) (B)O(n3) (C)O(n2) (D)O(ne)128．如果具有n個頂點的圖是一個環(huán)，則它有（）棵生成樹。(A)n(B)nl(C)n-l(D)2n129． 堆排序算法在平均情況下的時間復雜度為（ ）。(A)O(n) (B)O(nlogn) (C)O(n2) (D)O(logn)130． 在待排序數(shù)據(jù)已基本有序的前提下， 下述排序方法中效率最高的是 （ ）。(A)直接插入排序 (B)直接選擇排序 (C)快速排序 (D)歸并排序131．在理想情況下，散列表中查找元素所需的比較次數(shù)為（）。(A)n(B)O(C)n／2(D)1132． 在一棵 m階B樹中，若在某結點中插入一個新關鍵字而引起該結點分裂，則此結點中原有的關鍵字的個數(shù)是（ ）。(A)m (B)m+1 (C)m-l (D)m／2133．設順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為（C）。(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M134．設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（A）。(A)BADC(B)BCDA(C)CDAB(D)CBDA135．設某完全無向圖中有n個頂點，則該完全無向圖中有（A）條邊。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-1136．設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為（C）。(A)9(B)10(C)11(D)12137．設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有（B）個表頭結點。(A)n-1(B)n(C)n+1(D)2n-1第 17頁 共 100 頁138．設一組初始記錄關鍵字序列(5，2，6，3，8)，以第一個記錄關鍵字5為基準進行一趟快速排序的結果為（C）。(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ù)據(jù)結構的二元組形式表示為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ù)結構A是（B）。線性結構(B)樹型結構(C)物理結構(D)圖型結構140．下面程序的時間復雜為（B）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)141．設指針變量p指向單鏈表中結點A，若刪除單鏈表中結點A，則需要修改指針的操作序列為（A）。(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)；(C)q=p->next；p->next=q->next；free(q)；(D)q=p->next；p->data=q->data；free(q)；142．設有n個待排序的記錄關鍵字，則在堆排序中需要（A）個輔助記錄單元。(A)1(B)n(C)nlog2n(D)n2143．設一組初始關鍵字記錄關鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結束后的結果為（A）。10，15，14，18，20，36，40，2110，15，14，18，20，40，36，2110，15，14，20，18，40，36，2l15，10，14，18，20，36，40，21144． 設二叉排序樹中有 n 個結點，則在二叉排序樹的平均平均查找長度為（ B ）。(A)O(1) (B)O(log2n) (C)log2n(D)O(n2)第 18頁 共 100 頁145． 設無向圖 G中有 n個頂點 e條邊，則其對應的鄰接表中的表頭結點和表結點的個數(shù)分別為（ D）。(A)n，e(B)e，n(C)2n，e (D)n，2e146．設某強連通圖中有n個頂點，則該強連通圖中至少有（C）條邊。(A)n(n-1)(B)n+1(C)n(D)n(n+1)147．設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（B）方法可以達到此目的。快速排序(B)堆排序(C)歸并排序(D)插入排序148． 下列四種排序中（ D）的空間復雜度最大。(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 歸并排序149．設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為（C）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2)150． 設一棵二叉樹的深度為 k，則該二叉樹中最多有（ D ）個結點。(A)2k-1 (B)2k (C)2k-1 (D)2k-1151． 設某無向圖中有 n 個頂點 e條邊，則該無向圖中所有頂點的入度之和為（ D ）。(A)n (B)e (C)2n (D)2e152．在二叉排序樹中插入一個結點的時間復雜度為（B）。(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)153． 設某有向圖的鄰接表中有 n個表頭結點和 m個表結點， 則該圖中有 （ C）條有向邊。(A)n (B)n-1 (C)m (D)m-1154． 設一組初始記錄關鍵字序列為 (345，253，674，924，627)，則用基數(shù)排序需要進行（ A ）趟的分配和回收才能使得初始關鍵字序列變成有序序列。(A)3 (B)4 (C)5 (D)8155． 設用鏈表作為棧的存儲結構則退棧操作（ B）。第 19頁 共 100 頁(A) 必須判別棧是否為滿 (B) 必須判別棧是否為空(C) 判別棧元素的類型 (D) 對棧不作任何判別156． 下列四種排序中（ A）的空間復雜度最大?？焖倥判?B)冒泡排序(C)希爾排序(D)堆157．設某二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，度數(shù)為2的結點數(shù)為N2，則下列等式成立的是（C）。(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l158．設有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（A）。(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1)159． 數(shù)據(jù)的最小單位是（ A）。數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量160．設一組初始記錄關鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結束后前4條記錄關鍵字為（B）。(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20161．設一組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有 5個長度為 2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為（ A）。15，25，35，50，20，40，80，85，36，7015，25，35，50，80，20，85，40，70，3615，25，35，50，80，85，20，36，40，7015，25，35，50，80，20，36，40，70，85162． 設一個有序的單鏈表中有 n個結點，現(xiàn)要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（ D ）。(A)O(log2n) (B)O(1) (C)O(n2) (D)O(n)163．設一棵m叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，??，度數(shù)為m的結點數(shù)為Nm，則N0（B）。=第 20頁 共 100 頁(A)Nl+N2+ ??+Nm(B)l+N2+2N3+3N4+ ??+(m-1)NmN2+2N3+3N4+??+(m-1)Nm2Nl+3N2+??+(m+1)Nm164． 設有序表中有 1000個元素，則用二分查找查找元素 X最多需要比較 （ B）次。(A)25(B)10(C)7(D)1165．設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（B）。(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb166．設輸入序列是1、2、3、??、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（C）。(A)n-i(B)n-1-i(C)n+1-i(D)不能確定167．設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是（C）。(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80168． 設一組權值集合 W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為（ D ）。(A)20 (B)30 (C)40 (D)45169．執(zhí)行一趟快速排序能夠得到的序列是（A）。(A)[41，12，34，45，27]55[72，63](B)[45，34，12，41]55[72，63，27](C)[63，12，34，45，27]55[41，72](D)[12，27，45，41]55[34，63，72]170．設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是（A）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0第 21頁 共 100 頁171． 時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為 O(nlog2n)的是（ A ）。堆排序(B)冒泡排序(C)希爾排序(D)快速排序172．設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（D）?？栈蛑挥幸粋€結點(B)高度等于其結點數(shù)(C)任一結點無左孩子(D)任一結點無右孩子173．一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是（D）。(A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序174．設某棵三叉樹中有40個結點，則該三叉樹的最小高度為（B）。(A)3(B)4(C)5(D)6175．順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（A）。(A)O(n)(B)O(n2)(C)O(n1/2)(D)O(1og2n)176．二路歸并排序的時間復雜度為（C）。(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(log2n)177．深度為k的完全二叉樹中最少有（B）個結點。(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1178．設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為（C）。(A)front->next=s；front=s；(B)s->next=rear；rear=s；(C)rear->next=s；rear=s；(D)s->next=front；front=s；179． 設某無向圖中有 n個頂點 e條邊，則建立該圖鄰接表的時間復雜度為 （ A ）。(A)O(n+e) (B)O(n2) (C)O(ne) (D)O(n3)180． 設某哈夫曼樹中有 199個結點，則該哈夫曼樹中有（ B ）個葉子結點。(A)99 (B)100 (C)101 (D)102181． 設二叉排序樹上有 n個結點，則在二叉排序樹上查找結點的平均時間復雜度為（ D ）。(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(logn)2第 22頁 共 100 頁182． 設用鄰接矩陣 A表示有向圖 G的存儲結構， 則有向圖 G中頂點 i的入度為B）。第i行非0元素的個數(shù)之和(B)第i列非0元素的個數(shù)之和(C) 第i行0元素的個數(shù)之和 (D) 第i列0元素的個數(shù)之和183．設某無向圖有n個頂點，則該無向圖的鄰接表中有（B）個表頭結點。(A)2n(B)n(C)n/2(D)n(n-1)184．設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（B）條邊。(A)n(B)n-1(C)2n(D)2n-1185．設一組初始記錄關鍵字序列為(60，80，55，40，42，85)，則以第一個關鍵字45為基準而得到的一趟快速排序結果是（C）。(A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80186． （ B）二叉排序樹可以得到一個從小到大的有序序列。先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷187．設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為（B）。(A)2i+1(B)2i(C)i/2(D)2i-1188．程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的時間復雜度為（A）。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(n3/2)189．設帶有頭結點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（C）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0190．設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（C）。(A)20(B)256(C)512(D)1024191． 設一組初始記錄關鍵字序列為 (13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關鍵字 90需要比較的關鍵字個數(shù)為（ B ）。第 23頁 共 100 頁(A)1(B)2(C)3(D)4192．設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（D）。(A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next;193．建立一個長度為n的有序單鏈表的時間復雜度為（C）(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)194．設某散列表的長度為100，散列函數(shù)H(k)=k%P，則P通常情況下最好選擇（B）。(A)99(B)97(C)91(D)93195．在二叉排序樹中插入一個關鍵字值的平均時間復雜度為（B）。(A)O(n)(B)O(log2n)(C)O(log2n)(D)O(n2)196．設一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為(C)。(A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4]197．設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為（B）。(A)8(B)7(C)6(D)5198．設一棵三叉樹中有2個度數(shù)為1的結點，2個度數(shù)為2的結點，2個度數(shù)為3的結點，則該三叉鏈權中有（C）個度數(shù)為0的結點。(A)5(B)6(C)7(D)8199．設無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為（A）。(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc200． 下列程序段的時間復雜度為（ A ）。for(i=0； i<m； i++)for(j=0 ； j<t； j++)c[i][j]=0 ；第 24頁 共 100 頁for(i=0 ； i<m ； i++) for(j=0 ； j<t； j++) for(k=0 ； k<n； k++)c[i][j]=c[i][j]+a[i][k]*b[k][j] ；(A)O(m*n*t) (B)O(m+n+t)(C)O(m+n*t) (D)O(m*t+n)201． 設順序線性表中有 n個數(shù)據(jù)元素，則刪除表中第 i個元素需要移動（ A ）個元素。(A)n-i (B)n+l-i (C)n-1-i (D)i202．設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結點數(shù)分別為N1、N2和N3，則二叉樹B的根結點的左子樹的結點數(shù)為（A）。(A)N1-1(B)N2-1(C)N2+N3(D)N1+N3203．利用直接插入排序法的思想建立一個有序線性表的時間復雜度為（C）。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(log2n)204．設指針變量p指向雙向鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為（D）。(A)p->right=s；s->left=p；p->right->left=s；s->right=p->right；(B)s->left=p；s->right=p->right；p->right=s；p->right->left=s；(C)p->right=s；p->right->left=s；s->left=p；s->right=p->right；(D)s->left=p；s->right=p->right；p->right->left=s；p->right=s；205．下列各種排序算法中平均時間復雜度為2D）。O(n)是（快速排序(B)堆排序(C)歸并排序(D)冒泡排序206．設輸入序列1、2、3、?、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（C）。(A)n-i(B)n-1-i(C)n+l-i(D)不能確定207．設散列表中有m個存儲單元，散列函數(shù)H(key)=key%p，則p最好選擇（B）。(A)小于等于m的最大奇數(shù)(B)小于等于m的最大素數(shù)(C)小于等于m的最大偶數(shù)(D)小于等于m的最大合數(shù)第 25頁 共 100 頁208．設在一棵度數(shù)為3的樹中，度數(shù)為3的結點數(shù)有2個，度數(shù)為2的結點數(shù)有1個，度數(shù)為1的結點數(shù)有2個，那么度數(shù)為0的結點數(shù)有（C）個。(A)4(B)5(C)6(D)7209．設完全無向圖中有n個頂點，則該完全無向圖中有（A）條邊。(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/2210．設順序表的長度為n，則順序查找的平均比較次數(shù)為（C）。(A)n(B)n/2(C)(n+1)/2(D)(n-1)/2211．設有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過（C）次比較。(A)1(B)2(C)3(D)4212． 設順序線性表的長度為 30，分成 5塊，每塊 6個元素，如果采用分塊查找，則其平均查找長度為（ D ）。(A)6(B)11(C)5(D)6.5213．設有向無環(huán)圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓撲排序序列的是（A）。(A)1，2，3，4(B)2，3，4，1(C)1，4，2，3(D)1，2，4，3214．設有一組初始記錄關鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關鍵字生成的二叉排序樹的深度為（A）。(A)4(B)5(C)6(D)7215．下列程序段的時間復雜度為（A）。i=0，s=0； while(s<n){s=s+i ；i++；}(A)O(n1/2) (B)O(n1/3) (C)O(n) (D)O(n2)216． 設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列D）存儲方式最節(jié)省運算時間。單向鏈表(B)單向循環(huán)鏈表雙向鏈表(D)雙向循環(huán)鏈表第 26頁 共 100 頁217．設指針q指向單鏈表中結點A，指針p指向單鏈表中結點A的后繼結點B，指針s指向被插入的結點X，則在結點A和結點B插入結點X的操作序列為（B）。(A)s->next=p->next；p->next=-s；(B)q->next=s；s->next=p；(C)p->next=s->next；s->next=p；(D)p->next=s；s->next=q；218．設輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（B）。(A)5，3，4，6，1，2(B)3，2，5，6，4，1(C)3，1，2，5，4，6(D)1，5，4，6，2，3219．設有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（B）。(A)10(B)19(C)28(D)55220．設一棵m叉樹中有N1個度數(shù)為1的結點，N2個度數(shù)為2的結點，??，Nm個度數(shù)為m的結點，則該樹中共有（D）個葉子結點。m m m m(i1)NiNiNi1(i1)Ni(A)i1(B)i1(C)i2(D)i2221． 二叉排序樹中左子樹上所有結點的值均（ A）根結點的值。(A)< (B)> (C)= (D)!=222． 設一組權值集合 W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權值集合構造一棵哈夫曼樹，則這棵哈夫曼樹的帶權路徑長度為（ D ）。(A)129 (B)219 (C)189 (D)229223． 設有 n個關鍵字具有相同的 Hash函數(shù)值，則用線性探測法把這 n個關鍵字映射到 HASH 表中需要做（ D ）次線性探測。(A)n2 (B)n(n+1) (C)n(n+1)/2 (D)n(n-1)/2224． 設某棵二叉樹中只有度數(shù)為 0和度數(shù)為 2的結點且度數(shù)為 0的結點數(shù)為 n，則這棵二叉中共有（ C）個結點。第 27頁 共 100 頁(A)2n (B)n+l (C)2n-1 (D)2n+l225． 設一組初始記錄關鍵字的長度為 8，則最多經(jīng)過（ B）趟插入排序可以得到有序序列。(A)6 (B)7 (C)8 (D)9226．設一組初始記錄關鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結束后的結果是（D）。F，H，C，D，P，A，M，Q，R，S，Y，XP，A，C，S，Q，D，F(xiàn)，X，R，H，M，YA，D，C，R，F(xiàn)，Q，M，S，Y，P，H，XH，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y227．設有一個二維數(shù)組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。（C）(A)688(B)678(C)692(D)696228．若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標依次為（D）。(A)1，2，3(B)9，5，2，3(C)9，5，3(D)9，4，2，3229．對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為（C）。(A)O（1）(B)O（n）(C)O（1og2n）(D)O（n2）230．對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（D）個。(A)1(B)2(C)3(D)4231．設有6個結點的無向圖，該圖至少應有（A）條邊才能確保是一個連通圖。(A)5(B)6(C)7(D)8232． 設哈夫曼樹中的葉子結點總數(shù)為 m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（ B）個空指針域。第 28頁 共 100 頁(A)2m-1(B)2m (C)2m+1 (D)4m二、判斷題1．數(shù)據(jù)項是數(shù)據(jù)的最小單位。 （ ）2．鏈表的每個結點都恰好有一個指針。 （ ）3．同一組不重復輸入序列執(zhí)行不同的入棧出棧組合操作，所得結果也可能相同。（ ）4．改進的 KMP 算法中，字符串 ‖abaaaba‖的nextval數(shù)組值是 0101110。（ ）5．用六叉鏈表表示 30個結點的六叉樹，則樹中共有 151個空指針。（ ）6．數(shù)組是一種線性結構，因此只能用來存儲線性表。 （ ）7．若有向圖不存在回路，即使不用訪問標志位同一結點也不會被訪問兩次。 （ ）8．若裝填因子 a為1，則向散列表中散列元素時一定會產(chǎn)生沖突。 （ ）9．若把堆看成是一個完全二叉樹，則該樹一定是一棵排序二叉樹。 （ ）10．外排中使用置換選擇排序的目的，是為了增加初始歸并段的長度。 （ ）11．抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關。 （Y ）12．線性表的插入和刪除總是伴隨著大量數(shù)據(jù)的移動。 （ N）13．隊列在程序調(diào)用是必不可少，因此遞歸離不開隊列。 （ N ）14．字符串‘a(chǎn)ababaaaba‘的改進函數(shù) nextval數(shù)組值是 0020200320。(Y )15．二叉樹中有雙子女的父結點，在中序遍歷中后繼一定是其中一個子女結點。N）16．不用遞歸就不能實現(xiàn)二叉樹的前序遍歷。 （ N）17．若有向圖有 n個頂點，則其強連通分量最多有 n個。(Y)18．平衡二叉樹一定是一棵完全二叉樹。 （ N ）19．若某內(nèi)部排序算法不穩(wěn)定，則該算法沒有使用價值。 （ N ）第 29頁 共 100 頁20．倒排文件的目的是為了多關鍵字查找。 (Y)21．已知指針 curr指向鏈表中的某結點，執(zhí)行語句 curr=curr->next ；不會刪除該鏈表中的結點。 ( )22．若二叉樹的葉結點數(shù)為 1，則其高度等于結點數(shù) (僅含根結點的二叉樹高度 為。（）23．按中序周游二叉樹時，某個結點的直接后繼是它的右子樹中第一個被訪問 的結點。 ()24．完全二叉樹的某結點若無左孩子，則它必是葉結點。 ()25．向二叉檢索樹中插入一個新結點，需要比較的次數(shù)不可能大于此二叉樹的高度。 ()26．對一個堆按層次周游，一定能得到一個有序序列。 ()27．一棵樹中的葉子結點數(shù)一定等于其對應的二叉樹中的葉子結點數(shù)。 ()28．將一棵樹轉換為二叉樹表示后，該二叉樹的根結點沒有右子樹。 ()29．任何有向圖的結點都可以排成拓撲序列，而且拓撲序列不唯一。 ()30．快速排序在最差情況下的時間復雜度是 0(n2)，此時它的性能并不比冒泡排序更好。 ()31．AVL 樹的任何子樹都是 AVL 樹。（ Y）32．用相鄰矩陣表示圖所用的存儲空間大小與圖的邊數(shù)成正比。 （ N）33．霍夫曼樹一定是滿二叉樹。 （ Y）34．棧是一種線性結構。 （Y ）35． B＋樹既適于隨機檢索，也適于順序檢索。 （N ）36． 記錄是數(shù)據(jù)處理的最小單位。 （ ）37．數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系。 ( )38．算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。 （ ）39．健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。 ( Y)第 30頁 共 100 頁40．算法可以用不同的語言描述，如果用 C語言或 PASCAL 語言等高級語言來描述，則算法實際上就是程序了。（ ）41．數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。 ( Y)42．數(shù)據(jù)結構的抽象操作的定義與具體實現(xiàn)有關。 （ ）43．在順序存儲結構中，有時也存儲數(shù)據(jù)結構中元素之間的關系。 （ ）44．順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。 （ ）45．數(shù)據(jù)結構的基本操作的設置的最重要的準則是， 實現(xiàn)應用程序與存儲結構的獨立。(Y )46．數(shù)據(jù)的邏輯結