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

來源網(wǎng)絡來源網(wǎng)絡來源網(wǎng)絡數(shù)據(jù)結構試題庫單項選擇題下列程序段所代表的算法的時間復雜度為（D）。x=n;y=0;while(x>=(y+1)*(y+1))y++;(A)O(n)(B)O(n2)(C)O(log2n)(D)O()在一個長度為n的以順序結構存儲的線性表中，假設在線性表的任何位置刪除元素的概率相等，則刪除一個元素時線性表所需移動元素的平均次數(shù)為（B）。(A)n2(B)(n-1)/2(C)(n+1)/2(D)n/2在一個棧頂指針為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;假設以帶頭結點的循環(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;設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)至少為（B）。(A)2h-1(B)2h-1+1(C)2h-1(D)2h-1-3現(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,96有一組數(shù)值{5,12,9,20,3}，用以構造哈夫曼樹，則其帶權路徑長度WPL值為（D）。(A)93(B)96(C)123(D)103已知一個有向圖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,v6v3^v4^v5v5^v6^v3^v4^v5v5^v6^v1v2v2v2v3^v3v3v6^v6^v4^v5v4v4v6^設有m=2n-1個關鍵字，假設對每個關鍵字查找的概率相等，查找失敗的概率為0，若采用二分法查找一個關鍵字，則平均查找長度為（D）。(A)n-1(B)n-n/m(C)(n-1)-n/m(D)(n-1)+n/m已知一個待散列存儲的線性表{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/2下列程序段所代表的算法的時間復雜度為（C）。y=n;x=1;while(x<=y)x*=2;(A)O(n)(B)O(n2)(C)O(log2n)(D)O()在一個長度為n的以順序結構存儲的線性表中，假設在線性表的任何位置插入元素的概率相等，則插入一個元素時線性表所需移動元素的平均次數(shù)為（B）。(A)n2(B)(n+1)/2(C)(n-1)/2(D)n/2若對一個已有序的線性表最頻繁的操作是查找值為x的元素(假設存在的話)，則采用（D）存儲方式實現(xiàn)查找，其算法的時間復雜度為最小。(A)單鏈表(B)雙鏈表(C)單循環(huán)鏈表(D)順序表一個帶頭結點head的循環(huán)單鏈表為空的判斷條件是（C）。(A)head==NULL(B)head->next==NULL(C)head->next==head(D)head!=NULL若鏈隊列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->rear從一個棧頂指針為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;一棵有n個結點的滿二叉樹，有m個葉子結點，深度為h，那么n、m和h滿足條件（D）。(A)n=m+h(B)h+m=2n(C)m=h-1(D)n=2h-1一棵左、右子樹均不為空的二叉樹在先序線索化后，其空指針域數(shù)為（B）。(A)0(B)1(C)2(D)不確定有一組數(shù)值{5,12,9,20,3}，用以構造哈夫曼樹，則其帶權路徑長度WPL值為（C）。(A)49(B)96(C)103(D)125在一個n個結點的二叉排序樹中查找一個關鍵字，進行關鍵字比較次數(shù)最大值為（A）。(A)n(B)n/2(C)log2n(D)n*log2n已知有向圖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>}冒泡排序算法在最好情況下的時間復雜度為（B）。(A)O(log2n)(B)O(n)(C)O(1)(D)O(n2)在下列內部排序方法中，排序時不穩(wěn)定的，而且關鍵字的比較次數(shù)與記錄的初始排列次序無關的是（D）。(A)快速排序(B)冒泡排序(C)歸并排序(D)堆排序已知一個待散列存儲的線性表{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/2下列程序段所代表的算法的時間復雜度為（D）。i=1;j=0;while(i<=n){i+=j;j++;}(A)O(n)(B)O(n2)(C)O(log2n)(D)O()將兩個各有n個元素的有序表歸并成一個有序表，在最壞的情況下，其比較次數(shù)是（A）。(A)2n-1?(B)n???(C)n+1?(D)n-1若某鏈表中最常用的操作是在最后的一個結點之后插入一個結點或刪除最后一個結點，則采用（D）存儲方式最節(jié)省運行時間。(A)單鏈表(B)單循環(huán)鏈表(C)無頭雙向鏈表(D)帶頭雙向鏈表已知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;已知用循環(huán)鏈表表示的隊列長度為n，若只設頭指針，則出隊和入隊一個元素的時間復雜度分別是（B）。(A)O(1)和O(1)(B)O(1)和O(n)(C)O(n)和O(1)(D)O(n)和O(n)設鏈隊列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;已知一個帶權圖的頂點集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)31當待排序的關鍵字個數(shù)n很小，且初始排列為逆序時，采用下列排序方法中的（D），算法的時間復雜度最小。(A)直接插入排序(B)簡單選擇排序(C)冒泡排序(D)快速排序對二叉排序樹進行（C）遍歷，可以得到該二叉樹所有結點構成的排序序列。(A)層次???(B)前序???(C)中序???(D)后序已知一個長度為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/2一組關鍵字序列{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/7以數(shù)據(jù)集{4，5，6，7，12，18，10}為結點權值所構造的哈夫曼樹，則其帶權路徑長度WPL為（A）。(A)165(B)203(C)124(D)187假定對線性表R[0…n-1]進行分塊查找，若將表均勻地分為b塊，每塊含有n/b個記錄；又假定表中每個記錄的查找概率相等，并用順序查找確定所在的塊，若要使分塊查找的平均查找長度ASL最小，則分塊數(shù)b的值應為（B）。(A)(B)+1(C)「log2n」(D)「log2n」+1對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和n若在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序，則該操作的時間復雜度是（）。(A)O(1)(B)O(n2)(C)O(nlog2n)(D)O(n)在一個頭結點為head的空循環(huán)鏈表中插入一個結點s，則指針s應執(zhí)行操作（）。(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;設鏈隊列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->next假設二叉樹T中有n個葉子結點，且所有非葉子結點都有左、右子樹，那么二叉樹T共有（）個結點。(A)2n(B)2n-1(C)2n+1(D)2n+2已知有向圖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,v2已知一棵二叉樹的結點數(shù)據(jù)采用順序存儲結構，數(shù)組內容如下表所示，則該二叉樹的后序遍歷序列為（）。1123456789101112131415161718192021EAFDGCJIHB(A)ACBDJEFIGH(B)ABCDJEFHGI(C)BCJDAHIGFE(D)EADCBJFGIH若T為n個結點的完全二叉樹，則T的葉子結點數(shù)為（）。(A)n/2(B)(n-2)/2(C)(n-1)/2(D)(n+1)/2有一組數(shù)值14,21,32,15,28，用以構造huffman樹，則其WPL值為（）。(A)267(B)189(C)110(D)294采用折半插入排序，關鍵字的比較次數(shù)與移動次數(shù)分別為（）。(A)O(n),O(log2n)(B)O(n2),O(log2n)(C)O(log2n),O(n2)(D)O(nlog2n),O(n2)假設結點序列為{60,30,90,50,95,70,40,80}，以此構成一棵二叉排序樹，則在該二叉排序樹上查找一個結點的平均查找長度為（）。(A)23/8(B)11/4(C)9/2(D)4下面程序段的時間復雜性的量級為（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)在一個長度為n的線性表中，刪除值為x的元素時需要比較元素和移動元素的總次數(shù)為（C）。(A)（n+1）/2(B)n/2(C)n(D)n+1利用3，6，8，12，5，7這六個值作為葉子結點的權，生成一棵哈夫曼樹，該樹的深度為（B）。(A)3(B)4(C)5(D)6一棵二叉樹的廣義表表示為a(b(c,d),e(,f(g))),則得到的層次遍歷序列為（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,g若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為（）。(1≤i≤n+1)(A)O(0)???(B)O(1)???(C)O(n)???(D)O(n2)若在線性表中采用折半查找法查找元素，該線性表應該（）。(A)元素按值有序???(B)采用順序存儲結構(C)元素按值有序，且采用順序存儲結構(D)元素按值有序，且采用鏈式存儲結構已知一算術表達式的中綴形式為A＋B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為（）。?(A)–A+B*C/DE???(B)–A+B*CD/E(C)-+*ABC/DE???(D)-+A*BC/DE若二叉樹采用二叉鏈表存儲結構，要交換其所有分支結點左右子樹的位置，利用（）遍歷方法最合適。?(A)前序???(B)中序???(C)后序???(D)按層次對二叉排序樹進行（）遍歷，可以得到該二叉樹所有結點構成的排序序列。?(A)前序???(B)中序???(C)后序???(D)按層次具有n個頂點的有向圖最多有（）條邊。?(A)n???(B)n(n—1)???Cn(n+1)???(D)n2從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（）排序法。?(A)插入???(B)選擇???(C)shell???(D)二路歸并排序趟數(shù)與序列的原始狀態(tài)有關的排序方法是（）排序法。?(A)插入???(B)選擇???(C)冒泡???(D)快速下面給出的四種排序法中（）排序法是不穩(wěn)定性排序法。(A)插入???(B)冒泡???(C)二路歸并???(D)堆一個對象序列的排序碼為{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}線性鏈表不具有的特點是（）。(A)隨機訪問(B)不必事先估計所需存儲空間大小(C)插入與刪除時不必移動元素(D)所需空間與線性表長度成正比設F是一個森林，B是由F轉換得到的二叉樹，F(xiàn)中有n個非葉結點，則B中右指針域為空的結點有（）個。(A)n-1(B)n(C)n+1(D)n+2具有65個結點的完全二叉樹的高度為（）。（根的層次號為0）(A)8(B)7(C)6(D)5若待排序對象序列在排序前已按其排序碼遞增順序排序，則采用（）方法比較次數(shù)最少。(A)直接插入排序(B)快速排序(C)歸并排序(D)直接選擇排序在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。(A)3(B)2(C)1(D)1/2對有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]若度為m的哈夫曼樹中,其葉結點個數(shù)為n,則非葉結點的個數(shù)為（）。(A)[(n+1)/(m+1)]-1(B)[n/m]-1(C)[(n-1)/(m-1)](D)[n/(m-1)]-1下面關于算法說法錯誤的是（）。(A)算法最終必須由計算機程序實現(xiàn)(B)為解決某問題的算法同為該問題編寫的程序含義是相同的(C)算法的可行性是指指令不能有二義性(D)以上幾個都是錯誤的以下與數(shù)據(jù)的存儲結構無關的術語是（）。(A)循環(huán)隊列(B)鏈表(C)哈希表(D)棧以下數(shù)據(jù)結構中，哪一個是線性結構（）。(A)廣義表(B)二叉樹(C)稀疏矩陣(D)串以下那一個術語與數(shù)據(jù)的存儲結構無關？（）(A)棧(B)哈希表(C)線索樹(D)雙向鏈表在下面的程序段中，對x的賦值語句的頻度為（）。FORi:=1TOnDOFORj:=1TOnDOx:=x+1;(A)O(2n)(B)O(n)(C)O(n2)(D)O(log2n)以下哪個數(shù)據(jù)結構不是多型數(shù)據(jù)類型（）。(A)棧(B)廣義表(C)有向圖(D)字符串連續(xù)存儲設計時，存儲單元的地址（）。(A)一定連續(xù)(B)一定不連續(xù)(C)不一定連續(xù)(D)部分連續(xù)，部分不連續(xù)?一棵左右子樹均不空的二叉樹在先序前驅和后序后繼線索化后，其空鏈域數(shù)為（A）。(A)0(B)1(C)2(D)不確定設圖G采用鄰接表存儲，則拓撲排序算法的時間復雜度是（B）。(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n*e)下列排序算法中，時間復雜度為O(nlog2n)且占用額外空間最少的是（A）。(A)堆排序(B)冒泡排序(C)快速排序(D)SHELL排序已知數(shù)據(jù)表A中每個元素距其最終位置不遠，則采用（B）排序算法最節(jié)省時間。(A)堆排序(B)插入排序(C)快速排序(D)直接選擇排序串是（D）。(A)不少于一個字母的序列(B)任意個字母的序列(C)不少于一個字符的序列(D)有限個字符的序列一個棧的輸入序列為12345，則下列序列中是棧的輸出序列的是（A）。(A)23415(B)54132(C)31245(D)14253設循環(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)modn二叉樹在線索化后，仍不能有效求解的問題是（D）。(A)先序線索二叉樹中求先序后繼(B)中序線索二叉樹中求中序后繼(C)中序線索二叉樹中求中序前驅(D)后序線索二叉樹中求后序后繼求最短路徑的FLOYD算法的時間復雜度為（D）。(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n3)一棵左右子樹不空的二叉樹在先序線索化后，其空指針域數(shù)為（B）。(A)0(B)1(C)2(D)不確定數(shù)組A[1..5,1..6]的每個元素占5個單元，將其按行優(yōu)先順序存儲在起始地址為1000的連續(xù)的內存單元中，則元素A[5,5]的地址為（A）。(A)1140(B)1145(C)1120(D)1125在下列排序算法中，在待排序的數(shù)據(jù)表已經(jīng)為有序時，花費時間反而最多的是（A）。(A)快速排序(B)希爾排序(C)冒泡排序(D)堆排序對有18個元素的有序表做折半查找，則查找A[3]的比較序列的下標依次為（D）。(A)1-2-3(B)9-5-2-3(C)9-5-3(D)9-4-2-3下列排序算法中，某一趟結束后未必能選出一個元素放在其最終位置上的是（D）。(A)堆排序(B)冒泡排序(C)快速排序(D)直接插入排序在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡點為A，并已知A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則做（B）型調整以使其平衡。(A)LL(B)LR(C)RL(D)RR下列各式中，按增長率由小至大的順序正確排列的是（）。(A),n!,2n,n3/2(B)n3/2,2n,nlogn,2100(C)2n,logn,nlogn,n3/2(D)2100,logn,2n,nn若要在單鏈表中的結點*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;若要在O（1）的時間復雜度上實現(xiàn)兩個循環(huán)鏈表頭尾相接，則應對兩個循環(huán)鏈表各設置一個指針，分別指向（）。(A)各自的頭結點(B)各自的尾結點(C)各自的第一個元素結點(D)一個表的頭結點，另一個表的尾結點棧的兩種常用存儲結構分別為（）。(A)順序存儲結構和鏈式存儲結構(B)順序存儲結構和散列存儲結構(C)鏈式存儲結構和索引存儲結構(D)鏈式存儲結構和散列存儲結構已知循環(huán)隊列的存儲空間為數(shù)組data[21]，且當前隊列的頭指針和尾指針的值分別為8和3，則該隊的當前長度為（）。(A)5(B)6(C)16(D)17已知在如下定義的鏈串結點中，每個字符占1個字節(jié)，指針占4個字節(jié)，則該鏈串的存儲密度為（）。typedefstructnode{chardate[8];structnode*next;}LinkStrNode;(A)1/4(B)1/2(C)2/3(D)3/4應用簡單的匹配算法對主串s=“BDBABDABDAB”與子串t=“BDA”進行模式匹配，在匹配成功時，進行的字符比較總次數(shù)為（）。(A)7(B)9(C)10(D)12二維數(shù)組A[20][10]采用列優(yōu)先的存儲方法，若每個元素占2個存儲單元，且第1個元素的首地址為200，則元素A[8][9]的存儲地址為（）。(A)574(B)576(C)578(D)580對廣義表L=((a,b),c,d)進行操作tail(head(L))的結果是（）。(A)(c,d)(B)(d)(C)b(D)(b)已知一棵樹的前序序列為ABCDEF，后序序列為CEDFBA，則對該樹進行層次遍歷得到的序列為（）。(A)ABCDEF(B)ABCEFD(C)ABFCDE(D)ABCDFE一個含n個頂點和e條弧的有向圖以鄰接矩陣表示法為存儲結構，則計算該有向圖中某個頂點出度的時間復雜度為（）。(A)O(n)(B)O(e)(C)O(n+e)(D)O(n2)在關鍵字序列（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，4下列排序方法中，最好與最壞時間復雜度不相同的排序方法是（）。(A)冒泡排序(B)直接選擇排序(C)堆排序(D)歸并排序已知含10個結點的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于（）。(A)1.0(B)2.9(C)3.4(D)5.5在下列各種文件中，不能進行順序查找的文件是（）。(A)順序文件(B)索引文件(C)散列文件(D)多重表文件下面帶有@標記的語句的頻度(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)不確定已知使用順序表存儲數(shù)據(jù)，表長為n，假設在表中的任意位置插入元素的概率相等，則插入一個元素，平均需要移動的元素個數(shù)（）。(A)(n-1)/2(B)n/2(C)(n+1)/2(D)不確定在雙向鏈表p所指結點之后插入s所指結點的操作是（）。(A)p?right=s;s?left=p;p?right?left=s;s?right=p?right;(B)p?right=s;p?right?left=s;s?left=p;s?right=p?right;(C)s?left=p;s?right=p?right;p?right=s;p?right?left=s;(D)s?left=p;s?right=p?right;p?right?left=s;p?right=s;字符串相等的充分必要條件是（）。(A)串長度相等(B)串使用相同的存儲結構(C)串相同位置對應的字符相等(D)A和C將一個遞歸算法改為對應的非遞歸算法時，通常需要使用（）。(A)數(shù)組 (B)棧 (C)隊列 (D)二叉樹一個棧的入棧序列1,2,3,4,5,則棧的不可能的輸出序列是（）。(A)12345(B)54321(C)32514(D)12354設循環(huán)隊列中數(shù)組的下標范圍是1~n，其頭尾指針分別為f和r，則其元素個數(shù)為（）。(A)r-f(B)r-f+1(C)(r-f)modn+1(D)(r-f+n)modn某二叉樹的前序遍歷結點訪問順序是ABDEFCGH,中序遍歷的結點訪問順序是DBFEAGHC,則其后序遍歷的結點訪問順序是（）。(A)DFEBHCGA(B)DFEBHGCA(C)DEFBHGCA(D)DFEHBGCA正則二叉樹是只有度為0和2的結點的二叉樹，已知正則二叉樹的葉子結點個數(shù)為n，則該二叉樹總得結點數(shù)為（）。(A)n+1(B)2*n(C)2*n+1(D)2*n-1下面關于排序的說法錯誤的是（）。(A)快速排序、歸并排序都是一種不穩(wěn)定的排序方法(B)直接插入排序和折半插入排序移動元素的次數(shù)相同(C)簡單選擇排序移動元素的次數(shù)最少(D)根據(jù)排序需要的平均時間，快速排序是目前最好的一種內部排序方法折半查找有序表（3，4，5，10，13，14，20，30），若查找元素3，則被比較的元素依次為（）。(A)10,20,30(B)10,14,30(C)13,3(D)10,4,3下面關于棧和隊列的說法正確的是（）。(A)棧是先進先出的線性表，隊列是后進先出的線性表(B)棧是先進先出的線性表，隊列也是先進先出的線性表(C)棧是后進先出的線性表，隊列是先進先出的線性表(D)棧是后進先出的線性表，隊列也是后進先出的線性表兩個各有n個元素的有序列表并成一個有序表，其最少的比較次數(shù)是（）。

(A)n(B)2n-1(C)2n(D)n-1設循環(huán)隊列中數(shù)組的下標范圍是0~n-1，f表示隊首元素的前驅位置，r表示隊尾元素的位置，則隊列中元素個數(shù)為（）。

(A)r-f(B)r-f1(C)(r-f1)modn(D)(r-fn)modn一個5行6列的二維數(shù)組s采用從最后一行開始，每一行的元素從右至左的方式映射到一維數(shù)組a中，s和a的下標均從0開始，則s[3][3]在a中的下標是（）。

(A)7(B)8(C)9(D)10設只含根結點的二叉樹的高度為1，則高度為n的二叉樹中所含葉子結點的個數(shù)最多為（）個。

(A)2n(B)n(C)2n-1(D)2n-1設高度為h的二叉樹上只有度為0和度為2的結點，則此二叉樹中所包含的結點數(shù)至少為（）個（設只含根結點的二叉樹的高度為1）。

(A)2h(B)2h-1(C)2h+1(D)h+1對一棵二叉檢索樹進行（）得到的結點序列是一個有序序列。

(A)前序周游(B)中序周游(C)后序周游(D)層次周游一棵前序序列為1，2，3，4的二叉樹，其中序序列不可能是（）。

(A)4,1,2,3(B)4,3,2,1(C)2,4,3,1(D)3,4,2,1在含n個頂點和e條邊的有向圖的鄰接矩陣中，零元素的個數(shù)為（）。

(A)e(B)2e(C)n2-e(D)n2-2e具有n個頂點和e條邊的圖的深度優(yōu)先搜索算法的時間復雜度為（）。(A)O(n)(B)O(n3)(C)O(n2)(D)O(ne)如果具有n個頂點的圖是一個環(huán)，則它有（）棵生成樹。

(A)n(B)nl(C)n-l(D)2n堆排序算法在平均情況下的時間復雜度為（）。(A)O(n)(B)O(nlogn)(C)O(n2)(D)O(logn)在待排序數(shù)據(jù)已基本有序的前提下，下述排序方法中效率最高的是（）。(A)直接插入排序(B)直接選擇排序(C)快速排序(D)歸并排序在理想情況下，散列表中查找元素所需的比較次數(shù)為（）。

(A)n(B)O(C)n／2(D)1在一棵m階B樹中，若在某結點中插入一個新關鍵字而引起該結點分裂，則此結點中原有的關鍵字的個數(shù)是（）。

(A)m(B)m+1(C)m-l(D)m／2設順序循環(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)％M設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（A）。 (A)BADC (B)BCDA (C)CDAB (D)CBDA設某完全無向圖中有n個頂點，則該完全無向圖中有（A）條邊。 (A)n(n-1)/2 (B)n(n-1) (C)n2 (D)n2-1設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為（C）。 (A)9 (B)10 (C)11 (D)12設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有（B）個表頭結點。 (A)n-1 (B)n (C)n+1 (D)2n-1設一組初始記錄關鍵字序列(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，8設某數(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）。 (A)線性結構 (B)樹型結構 (C)物理結構 (D)圖型結構下面程序的時間復雜為（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)設指針變量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)；設有n個待排序的記錄關鍵字，則在堆排序中需要（A）個輔助記錄單元。 (A)1 (B)n (C)nlog2n (D)n2設一組初始關鍵字記錄關鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結束后的結果為（A）。(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，21設二叉排序樹中有n個結點，則在二叉排序樹的平均平均查找長度為（B）。 (A)O(1) (B)O(log2n) (C)log2n (D)O(n2)設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數(shù)分別為（D）。 (A)n，e (B)e，n (C)2n，e (D)n，2e設某強連通圖中有n個頂點，則該強連通圖中至少有（C）條邊。 (A)n(n-1) (B)n+1 (C)n (D)n(n+1)設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（B）方法可以達到此目的。 (A)快速排序 (B)堆排序 (C)歸并排序 (D)插入排序下列四種排序中（D）的空間復雜度最大。 (A)插入排序 (B)冒泡排序 (C)堆排序 (D)歸并排序設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為（C）。 (A)O(n) (B)O(nlog2n) (C)O(1) (D)O(n2)設一棵二叉樹的深度為k，則該二叉樹中最多有（D）個結點。 (A)2k-1 (B)2k (C)2k-1 (D)2k-1設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（D）。 (A)n (B)e (C)2n (D)2e在二叉排序樹中插入一個結點的時間復雜度為（B）。 (A)O(1) (B)O(n) (C)O(log2n) (D)O(n2)設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（C）條有向邊。 (A)n (B)n-1 (C)m (D)m-1設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（A）趟的分配和回收才能使得初始關鍵字序列變成有序序列。 (A)3 (B)4 (C)5 (D)8設用鏈表作為棧的存儲結構則退棧操作（B）。 (A)必須判別棧是否為滿 (B)必須判別棧是否為空 (C)判別棧元素的類型 (D)對棧不作任何判別下列四種排序中（A）的空間復雜度最大。 (A)快速排序 (B)冒泡排序 (C)希爾排序 (D)堆設某二叉樹中度數(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+l設有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（A）。 (A)log2n+1 (B)log2n-1 (C)log2n (D)log2(n+1)數(shù)據(jù)的最小單位是（A）。 (A)數(shù)據(jù)項 (B)數(shù)據(jù)類型 (C)數(shù)據(jù)元素 (D)數(shù)據(jù)變量設一組初始記錄關鍵字序列為(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，20設一組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為（A）。(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85設一個有序的單鏈表中有n個結點，現(xiàn)要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（D）。 (A)O(log2n) (B)O(1) (C)O(n2) (D)O(n)設一棵m叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，……，度數(shù)為m的結點數(shù)為Nm，則N0=（B）。(A)Nl+N2+……+Nm(B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm設有序表中有1000個元素，則用二分查找查找元素X最多需要比較（B）次。 (A)25 (B)10 (C)7 (D)1設連通圖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)aedfcb設輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（C）。 (A)n-i (B)n-1-i (C)n+1-i (D)不能確定設一組初始記錄關鍵字序列為(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，80設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為（D）。 (A)20 (B)30 (C)40 (D)45執(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]設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是（A）。(A)head==0 (B)head->next==0(C)head->next==head (D)head!=0時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（A）。 (A)堆排序 (B)冒泡排序 (C)希爾排序 (D)快速排序設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（D）。 (A)空或只有一個結點 (B)高度等于其結點數(shù) (C)任一結點無左孩子 (D)任一結點無右孩子一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是（D）。 (A)堆排序 (B)冒泡排序 (C)快速排序 (D)希爾排序設某棵三叉樹中有40個結點，則該三叉樹的最小高度為（B）。 (A)3 (B)4 (C)5 (D)6順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（A）。 (A)O(n) (B)O(n2) (C)O(n1/2) (D)O(1og2n)二路歸并排序的時間復雜度為（C）。 (A)O(n) (B)O(n2) (C)O(nlog2n) (D)O(log2n)深度為k的完全二叉樹中最少有（B）個結點。 (A)2k-1-1 (B)2k-1 (C)2k-1+1 (D)2k-1設指針變量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；設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為（A）。 (A)O(n+e) (B)O(n2) (C)O(ne) (D)O(n3)設某哈夫曼樹中有199個結點，則該哈夫曼樹中有（B）個葉子結點。 (A)99 (B)100 (C)101 (D)102設二叉排序樹上有n個結點，則在二叉排序樹上查找結點的平均時間復雜度為（D）。 (A)O(n) (B)O(n2) (C)O(nlog2n) (D)O(log2n)設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（B）。 (A)第i行非0元素的個數(shù)之和 (B)第i列非0元素的個數(shù)之和 (C)第i行0元素的個數(shù)之和 (D)第i列0元素的個數(shù)之和設某無向圖有n個頂點，則該無向圖的鄰接表中有（B）個表頭結點。 (A)2n (B)n (C)n/2 (D)n(n-1)設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（B）條邊。 (A)n (B)n-1 (C)2n (D)2n-1設一組初始記錄關鍵字序列為(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，80（B）二叉排序樹可以得到一個從小到大的有序序列。 (A)先序遍歷 (B)中序遍歷 (C)后序遍歷 (D)層次遍歷設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為（B）。 (A)2i+1 (B)2i (C)i/2 (D)2i-1程序段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)設帶有頭結點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（C）。 (A)head==0 (B)head->next==0 (C)head->next==head (D)head!=0設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（C）。 (A)20 (B)256 (C)512 (D)1024設一組初始記錄關鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關鍵字90需要比較的關鍵字個數(shù)為（B）。 (A)1 (B)2 (C)3 (D)4設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（D）。 (A)top=top+1; (B)top=top-1; (C)top->next=top; (D)top=top->next;建立一個長度為n的有序單鏈表的時間復雜度為（C） (A)O(n) (B)O(1) (C)O(n2) (D)O(log2n)設某散列表的長度為100，散列函數(shù)H(k)=k%P，則P通常情況下最好選擇（B）。 (A)99 (B)97 (C)91 (D)93在二叉排序樹中插入一個關鍵字值的平均時間復雜度為（B）。 (A)O(n) (B)O(log2n) (C)O(log2n) (D)O(n2)設一個順序有序表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]設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為（B）。 (A)8 (B)7 (C)6 (D)5設一棵三叉樹中有2個度數(shù)為1的結點，2個度數(shù)為2的結點，2個度數(shù)為3的結點，則該三叉鏈權中有（C）個度數(shù)為0的結點。 (A)5 (B)6 (C)7 (D)8設無向圖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)aedfbc下列程序段的時間復雜度為（A）。for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；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)設順序線性表中有n個數(shù)據(jù)元素，則刪除表中第i個元素需要移動（A）個元素。 (A)n-i (B)n+l-i (C)n-1-i (D)i設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+N3利用直接插入排序法的思想建立一個有序線性表的時間復雜度為（C）。(A)O(n) (B)O(nlog2n) (C)O(n2) (D)O(log2n)設指針變量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；下列各種排序算法中平均時間復雜度為O(n2)是（D）。 (A)快速排序 (B)堆排序 (C)歸并排序 (D)冒泡排序設輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（C）。 (A)n-i (B)n-1-i (C)n+l-i (D)不能確定設散列表中有m個存儲單元，散列函數(shù)H(key)=key%p，則p最好選擇（B）。 (A)小于等于m的最大奇數(shù) (B)小于等于m的最大素數(shù) (C)小于等于m的最大偶數(shù) (D)小于等于m的最大合數(shù)設在一棵度數(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)7設完全無向圖中有n個頂點，則該完全無向圖中有（A）條邊。(A)n(n-1)/2 (B)n(n-1) (C)n(n+1)/2 (D)(n-1)/2設順序表的長度為n，則順序查找的平均比較次數(shù)為（C）。 (A)n (B)n/2 (C)(n+1)/2 (D)(n-1)/2設有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過（C）次比較。 (A)1 (B)2 (C)3 (D)4設順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為（D）。 (A)6 (B)11 (C)5 (D)6.5設有向無環(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，3設有一組初始記錄關鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關鍵字生成的二叉排序樹的深度為（A）。 (A)4 (B)5 (C)6 (D)7下列程序段的時間復雜度為（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)設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（D）存儲方式最節(jié)省運算時間。 (A)單向鏈表 (B)單向循環(huán)鏈表(C)雙向鏈表 (D)雙向循環(huán)鏈表設指針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；設輸入序列為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，3設有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（B）。 (A)10 (B)19 (C)28 (D)55設一棵m叉樹中有N1個度數(shù)為1的結點，N2個度數(shù)為2的結點，……，Nm個度數(shù)為m的結點，則該樹中共有（D）個葉子結點。 (A) (B) (C) (D)二叉排序樹中左子樹上所有結點的值均（A）根結點的值。 (A)< (B)> (C)= (D)!=設一組權值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權值集合構造一棵哈夫曼樹，則這棵哈夫曼樹的帶權路徑長度為（D）。 (A)129 (B)219 (C)189 (D)229設有n個關鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關鍵字映射到HASH表中需要做（D）次線性探測。 (A)n2 (B)n(n+1) (C)n(n+1)/2 (D)n(n-1)/2設某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結點且度數(shù)為0的結點數(shù)為n，則這棵二叉中共有（C）個結點。 (A)2n (B)n+l (C)2n-1 (D)2n+l設一組初始記錄關鍵字的長度為8，則最多經(jīng)過（B）趟插入排序可以得到有序序列。 (A)6 (B)7 (C)8 (D)9設一組初始記錄關鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結束后的結果是（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設有一個二維數(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)696若有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，3對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為（C）。(A)O（1）(B)O（n）(C)O（1og2n）(D)O（n2）對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（D）個。(A)1(B)2(C)3(D)4設有6個結點的無向圖，該圖至少應有（A）條邊才能確保是一個連通圖。(A)5(B)6(C)7(D)8設哈夫曼樹中的葉子結點總數(shù)為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（B）個空指針域。 (A)2m-1 (B)2m (C)2m+1 (D)4m二、判斷題數(shù)據(jù)項是數(shù)據(jù)的最小單位。（）鏈表的每個結點都恰好有一個指針。（）同一組不重復輸入序列執(zhí)行不同的入棧出棧組合操作，所得結果也可能相同。（）改進的KMP算法中，字符串”abaaaba”的nextval數(shù)組值是0101110。（）用六叉鏈表表示30個結點的六叉樹，則樹中共有151個空指針。（）數(shù)組是一種線性結構，因此只能用來存儲線性表。（）若有向圖不存在回路，即使不用訪問標志位同一結點也不會被訪問兩次。（）若裝填因子a為1，則向散列表中散列元素時一定會產(chǎn)生沖突。（）若把堆看成是一個完全二叉樹，則該樹一定是一棵排序二叉樹。（）外排中使用置換選擇排序的目的，是為了增加初始歸并段的長度。（）抽象數(shù)據(jù)類型與計算機內部表示和實現(xiàn)無關。（Y）線性表的插入和刪除總是伴隨著大量數(shù)據(jù)的移動。（N）隊列在程序調用是必不可少，因此遞歸離不開隊列。（N）字符串’aababaaaba’(Y)二叉樹中有雙子女的父結點，在中序遍歷中后繼一定是其中一個子女結點。（N）不用遞歸就不能實現(xiàn)二叉樹的前序遍歷。（N）若有向圖有n個頂點，則其強連通分量最多有n個。(Y)平衡二叉樹一定是一棵完全二叉樹。（N）若某內部排序算法不穩(wěn)定，則該算法沒有使用價值。（N）倒排文件的目的是為了多關鍵字查找。(Y)已知指針curr指向鏈表中的某結點，執(zhí)行語句curr=curr->next；不會刪除該鏈表中的結點。()若二叉樹的葉結點數(shù)為1，則其高度等于結點數(shù)(僅含根結點的二叉樹高度為1)。（）按中序周游二叉樹時，某個結點的直接后繼是它的右子樹中第一個被訪問的結點。()完全二叉樹的某結點若無左孩子，則它必是葉結點。()向二叉檢索樹中插入一個新結點，需要比較的次數(shù)不可能大于此二叉樹的高度。()對一個堆按層次周游，一定能得到一個有序序列。()一棵樹中的葉子結點數(shù)一定等于其對應的二叉樹中的葉子結點數(shù)。()將一棵樹轉換為二叉樹表示后，該二叉樹的根結點沒有右子樹。()任何有向圖的結點都可以排成拓撲序列，而且拓撲序列不唯一。()快速排序在最差情況下的時間復雜度是0(n2)，此時它的性能并不比冒泡排序更好。()AVL樹的任何子樹都是AVL樹。（Y）用相鄰矩陣表示圖所用的存儲空間大小與圖的邊數(shù)成正比。（N）霍夫曼樹一定是滿二叉樹。（Y）棧是一種線性結構。（Y）B＋樹既適于隨機檢索，也適于順序檢索。（N）記錄是數(shù)據(jù)處理的最小單位。（）數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系。()算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。（）健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。(Y)算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。（）數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內的實際存儲形式。(Y)數(shù)據(jù)結構的抽象操作的定義與具體實現(xiàn)有關。（）在順序存儲結構中，有時也存儲數(shù)據(jù)結構中元素之間的關系。（）順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（）數(shù)據(jù)結構的基本操作的設置的最重要的準則是，實現(xiàn)應用程序與存儲結構的獨立。(Y)數(shù)據(jù)的邏輯結構說明數(shù)據(jù)元素之間的順序關系,它依賴于計算機的儲存結構.（）數(shù)據(jù)結構概念包括數(shù)據(jù)之間的邏輯結構，數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個方面。(Y)線性表中的每個結點最多只有一個前驅和一個后繼。(Y)線性的數(shù)據(jù)結構可以順序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)結構只能鏈接存儲。()棧和隊列邏輯上都是線性表。(Y)單鏈表從任何一個結點出發(fā)，都能訪問到所有結點。()設串S的長度為n,則S的子串個數(shù)為n(n+1)/2。(Y)一般樹和二叉樹的結點數(shù)目都可以為0。(Y)（101，88，46，70，34，39，45，58，66，10）是堆。......(Y)將一棵樹轉換成二叉樹后，根結點沒有左子樹。()用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷。(Y)即使對不含相同元素的同一輸入序列進行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同。()哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離很較近。(Y)數(shù)據(jù)的基本單位是數(shù)據(jù)項。()帶權的無向連通圖的最小生成樹是唯一的。()數(shù)組元素之間的關系，既不是線性的，也不是樹形的。()對于有n個對象的待排序序列進行歸并排序，所需平均時間為O（nlog2n）。(Y)用鄰接矩陣法存儲一個圖所需的存儲單元數(shù)目與圖的邊數(shù)有關。(Y)在霍夫曼編碼中，當兩個字符出現(xiàn)的頻率相同時，其編碼也相同，對于這種情況應當特殊處理。()線性表采用順序存儲表示時，必須占用一片連續(xù)的存儲單元。(Y)由樹轉化成二叉樹，其根的右子女指針總是空的。(Y)直接選擇排序是一種穩(wěn)定的排序方法。()裝載因子是散列表的一個重要參數(shù)，它反映了散列表的裝滿程度。(Y)若一個棧的輸入序列為123…n，其輸出序列的第一個元素為n，則其輸出序列的每個元素ai一定滿足ai=n-i+1。(i=1,2,...,n)（Y）二叉樹中的葉子結點就是二叉樹中沒有左右子樹的結點。（N）一棵樹中的葉子結點數(shù)一定等于與其對應的二叉樹中的葉子結點數(shù)。（N）刪除二叉排序樹中的一個結點，再重新插入上去，一定能得到原來的二叉排序樹。（N）線性表就是順序表。（N）若一棵樹中某結點的度為1，則該結點僅有一棵子樹。（Y）所謂平衡二叉樹是指左右子樹的高度差的絕對值不大于1的二叉樹。（N）AOE網(wǎng)所表示的工程至少所需的時間等于從源點到匯點的最短路徑的長度。（N）若某二叉樹的葉子結點數(shù)為1，則其先序序列和后序序列一定相反。（Y）在采用線性探測法處理沖突的散列表中，所有的同義詞在表中相鄰。（N）對B-樹中任一非葉子結點中的某關鍵字K，比K小的最大關鍵字和比K大的最小關鍵字一定都在非葉結點的最下層。（Y）若一個連通無向圖的以頂點1為起點的深度遍歷序列唯一，則可唯一確定該圖。（Y）若一個有向圖的以頂點1為起點的深度遍歷序列唯一，則可唯一確定該圖。（N）在數(shù)據(jù)表基本有序時，冒泡排序算法的時間復雜度一定接近O(n)。（N）設指針p指向單鏈表中的一個結點，則語句序列u:=p^.next;u:=u^.next將刪除一個結點。（N）線性表的長度是線性表所占用的存儲空間的大小。（N）雙循環(huán)鏈表中，任意一結點的后繼指針均指向其邏輯后繼。（N）在對鏈隊列做出隊操作時，不會改變front指針的值。（N）如果兩個串含有相同的字符，則說它們相等。（N）如果二叉樹中某結點的度為1，則說該結點只有一棵子樹。（Y）已知一棵樹的先序序列和后序序列，一定能構造出該樹。（N）圖G的一棵最小代價生成樹的代價未必小于G的其它任何一棵生成樹的代價。（Y）圖G的拓撲序列唯一，則其弧數(shù)必為n-1（其中n為頂點數(shù)）。（N）9.對一個堆按層次遍歷，不一定能得到一個有序序列。（Y）10.直接選擇排序算法滿足：其時間復雜度不受數(shù)據(jù)的初始特性影響，為O(n2)。（Y）如果兩個串含有相同的字符，則這兩個串相等。（N）數(shù)組可以看成線性結構的一種推廣，因此可以對它進行插入、刪除等運算。（N）在索引順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關，而且與每一塊中元素個數(shù)有關。（Y）在順序表中取出第i個元素所花費的時間與i成正比。（N）在棧滿情況下不能作進棧運算，否則產(chǎn)生“上溢”。(Y）二路歸并排序的核心操作是將兩上有序序列歸并為一個有序序列。（Y）對任意一個圖，從它的某個頂點出發(fā)，進行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個頂點.（N）二叉排序樹或者是一棵空二叉樹，或者是具有下列性質的二叉樹：若它的左子樹非空，則根結點的值大于其左孩子的值;若它的右子樹非空，則根結點的值小于其右孩子的值。（N）在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。（N）一個有向圖的鄰接表和逆鄰接表中表結點的個數(shù)一定相等。（Y）算法與程序的主要區(qū)別是算法滿足有窮性??并且算法不一定用機器可執(zhí)行的程序設計語言書寫。（Y）某線性表采用順序存儲結構??元素長度為4??首地址為100??則下標為12的??第13個??元素的存儲地址為148。（Y）在任何一種線性鏈表上都無法進行隨機訪問。（N）順序棧是一種規(guī)定了元素進棧順序的棧。（N）循環(huán)列表中每一個元素都有后繼。（Y）樹的先根遍歷與該樹對應二叉樹的前序遍歷結果不同。（N）任何有向網(wǎng)絡??AOV網(wǎng)絡??拓撲排序的結果是唯一的。（N）無向圖中的連通分量定義為無向圖的極大連通子圖。（Y）刪除一個二叉樹中的一個結點??再重新插入上去??一定能得到原來的二叉排序樹。（N）數(shù)據(jù)結構包括數(shù)據(jù)間的邏輯結構??數(shù)據(jù)的存儲方式和數(shù)據(jù)的運算三個方面的內容。（Y）在動態(tài)單向鏈表中??每個結點總是占用一片連續(xù)的內存空間。（N）高級語言中通常利用“遞歸工作?！眮硖幚磉f歸。（Y）中綴表示式??a+b??*(c+d)的后綴形式為ab+cd+*。（Y）棧和隊列都不適合用散列存儲法存儲。（N）廣義表的深度與廣義表中含有多少個子表元素有關。（Y）如果樹用二叉樹鏈表表示??則判斷某個結點是不是樹葉的條件是該結點左??右兩個指針域的值都為空。（Y）一組關鍵碼已完全有序時??最快的排序方法是快速排序。（Y）n個結點的無向圖最多有n*(n-1)/2條邊。（Y）線性結構中的結點按前驅??后繼關系可以排成一個線性序列。（Y）在動態(tài)單向鏈表中??每個結點總是占用一片連續(xù)的內存空間。（N）算法的有窮性是指一個算法無論在什么情況下都應在執(zhí)行有窮步后結束。（Y）后綴表達式ABC+*的中綴形式為A*??B+C??。（Y）對順序棧進行插入??刪除操作??不涉及元素的前后移動問題。（N）廣義表的長度是廣義表中元素的個數(shù)。（Y）在任何一棵完全二叉樹中??葉結點的個數(shù)或者和分支結點一樣多，或者只比分支結點多一個。（Y）直接選擇排序是一種穩(wěn)定的排序方法。（N）n個頂點的生成樹中有n-1條邊。（Y）有向圖的鄰接表和逆鄰接表中表結點的個數(shù)不一定相等。(錯)對鏈表進行插入和刪除操作時不必移動鏈表中結點。(對)子串“ABC”在主串“AABCABCD”中的位置為2。(對)若一個葉子結點是某二叉樹的中序遍歷序列的最后一個結點，則它必是該二叉樹的先序遍歷序列中的最后一個結點。(對)希爾排序算法的時間復雜度為O(n2)。(錯)用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數(shù)無關而與圖中邊數(shù)有關。(錯)中序遍歷一棵二叉排序樹可以得到一個有序的序列。(對)入棧操作和入隊列操作在鏈式存儲結構上實現(xiàn)時不需要考慮棧溢出的情況。(對)順序表查找指的是在順序存儲結構上進行查找。（錯）堆是完全二叉樹，完全二叉樹不一定是堆。（對）調用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（錯）分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（對）冒泡排序在初始關鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（對）滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（對）設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（錯）層次遍歷初始堆可以得到一個有序的序列。（錯）設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（對）線性表的順序存儲結構比鏈式存儲結構更好。（錯）中序遍歷二叉排序樹可以得到一個有序的序列。（對）快速排序是排序算法中平均性能最好的一種排序。（對）不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。（對）當向二叉排序樹中插入一個結點，則該結點一定成為葉子結點。（對）設某堆中有n個結點，則在該堆中插入一個新結點的時間復雜度為O(log2n)。（對）完全二叉樹中的葉子結點只可能在最后兩層中出現(xiàn)。（對）哈夫曼樹中沒有度數(shù)為1的結點。（對）對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（對）先序遍歷一棵二叉排序樹得到的結點序列不一定是有序的序列。（對）由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（錯）線性表中的所有元素都有一個前驅元素和后繼元素。（錯）帶權無向圖的最小生成樹是唯一的。（錯）如果兩個關鍵字的值不等但哈希函數(shù)值相等，則稱這兩個關鍵字為同義詞。（對）設初始記錄關鍵字基本有序，則快速排序算法的時間復雜度為O(nlog2n)。（錯）分塊查找的基本思想是首先在索引表中進行查找，以便確定給定的關鍵字可能存在的塊號，然后再在相應的塊內進行順序查找。（對）二維數(shù)組和多維數(shù)組均不是特殊的線性結構。（錯）向二叉排序樹中插入一個結點需要比較的次數(shù)可能大于該二叉樹的高度。（錯）如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。（對）非空的雙向循環(huán)鏈表中任何結點的前驅指針均不為空。（對）不論線性表采用順序存儲結構還是鏈式存儲結構，刪除值為X的結點的時間復雜度均為O(n)。（對）圖的深度優(yōu)先遍歷算法中需要設置一個標志數(shù)組，以便區(qū)分圖中的每個頂點是否被訪問過。（對）稀疏矩陣的壓縮存儲可以用一個