數(shù)據(jù)結(jié)構(gòu)試題庫(kù)

1、數(shù)據(jù)結(jié)構(gòu)試題庫(kù)一、單項(xiàng)選擇題1 .下列程序段所代表的算法的時(shí)間復(fù)雜度為(D)。x=n;y=0;while(x>=(y+1)*(y+1)y+;(A)O(n)(B)O(n2)(C)O(log2n)(D)O(,n)2 .在一個(gè)長(zhǎng)度為n的以順序結(jié)構(gòu)存儲(chǔ)的線性表中，假設(shè)在線性表的任何位置刪除元素的概率相等，則刪除一個(gè)元素時(shí)線性表所需移動(dòng)元素的平均次數(shù)為(B)。(A)n2(B)(n-1)/2(C)(n+1)/2(D)n/23 .在一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行執(zhí)行操作為(C)。(A)HS->next=s;(B)s->next=HS->next;HS->n

2、ext=s;(C)s->next=HS;HS=s;(D)s->next=HS;HS=HS>next;4 .假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列Q并且隊(duì)列只設(shè)一個(gè)頭指針front,不設(shè)隊(duì)列尾指針。若要進(jìn)隊(duì)一個(gè)元素*s,則在下列程序算法的空白處應(yīng)添加的操作語(yǔ)句是(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->fr

3、ont=s;(C)s->next=p;p->next=Q->front;(D)Q->front->next=s;s->next=p;5 .設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類(lèi)二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為(B)。(A)2h-1(B)2h-1+1(C)2h-1(D)2h-1-36 .現(xiàn)有數(shù)據(jù)集53,30,37,12,45,24,96,從空二叉樹(shù)逐個(gè)插入數(shù)據(jù)形成二叉排序樹(shù)，若希望查找此二叉樹(shù)中任一結(jié)點(diǎn)的平均查找長(zhǎng)度最小，則應(yīng)選擇下面哪個(gè)序列輸入(C)。(A)45,24,53,12,37,96,30(B)30,24,12,37,45,96,53(C)

4、37,24,12,30,53,45,96(D)12,24,30,37,45,53,967 .有一組數(shù)值5,12,9,20,3,用以構(gòu)造哈夫曼樹(shù)，則其帶權(quán)路徑長(zhǎng)度WPLS為(D)。(A)93(B)96(C)123(D)1038 .已知一個(gè)有向圖G的頂點(diǎn)v=v1,v2,v3,v4,v5,v6,其鄰接表如下圖所示，根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)遍歷序列是(B)0(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,v69,設(shè)有m=2-1個(gè)關(guān)鍵字，假設(shè)對(duì)每個(gè)關(guān)鍵字查找的概率

5、相等，查找失敗的概率為0,若采用二分法查找一個(gè)關(guān)鍵字，則平均查找長(zhǎng)度為(D)。(A)n-1(B)n-n/m(C)(n-1)-n/m(D)(n-1)+n/m10 .已知一個(gè)待散列存儲(chǔ)的線性表18,81,58,34,26,75,67,49,93,散列函數(shù)為h(k尸k%11,散列地址空間為010。若采用線性探查法解決沖突，則平均查找長(zhǎng)度為(A)。(A)5/3(B)13/9(C)16/9(D)3/211 .下列程序段所代表的算法的時(shí)間復(fù)雜度為(C)。y=n;x=1;while(x<=y)x*=2;(A)O(n)(B)O(n2)(C)O(log2n)(D)O(、n)12 .在一個(gè)長(zhǎng)度為n的以順序結(jié)

6、構(gòu)存儲(chǔ)的線性表中，假設(shè)在線性表的任何位置插入元素的概率相等，則插入一個(gè)元素時(shí)線性表所需移動(dòng)元素的平均次數(shù)為(B)。(A)n2(B)(n+1)/2(C)(n-1)/2(D)n/213 .若對(duì)一個(gè)已有序的線性表最頻繁的操作是查找值為x的元素(假設(shè)存在的話)，則采用(D)存儲(chǔ)方式實(shí)現(xiàn)查找，其算法的時(shí)間復(fù)雜度為最小。(A)單鏈表(B)雙鏈表(C)單循環(huán)鏈表(D)順序表14 .一個(gè)帶頭結(jié)點(diǎn)head的循環(huán)單鏈表為空的判斷條件是(C)。(A)head=NULL(B)head->next=NULL(C)head->next=head(D)head!=NULL15 .若鏈隊(duì)列HQ中只有一個(gè)結(jié)點(diǎn)，則隊(duì)

7、列的頭指針和尾指針滿足下列條件(D)0(A)HQ->rear->next=HQ->front(B)HQ->front->next=HQ->rear->next(C)HQ->front=HQ->rear(D)HQ->front->next=HQ->rear16 .從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除結(jié)點(diǎn)的值，則應(yīng)執(zhí)行操作為(A)。(A)x=HS->data;HS=HS->next;(B)x=HS->data;HS->NEXT=NULL;(C)HS=HS->next;x=HS

8、->data;(D)x=HS->data;HS=NULL;17 .一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，有m個(gè)葉子結(jié)點(diǎn)，深度為h,那么n、m和h滿足條件(D)。(A)n=m+h(B)h+m=2n(C)m=h-1(D)n=2h-118 .一棵左、右子樹(shù)均不為空的二叉樹(shù)在先序線索化后，其空指針域數(shù)為(B)。(A)0(B)1(C)2(D)不確定.19 .有一組數(shù)值5,12,9,20,3,用以構(gòu)造哈夫曼樹(shù)，則其帶權(quán)路徑長(zhǎng)度WPLS為(C)。(A)49(B)96(C)103(D)12520 .在一個(gè)n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中查找一個(gè)關(guān)鍵字，進(jìn)行關(guān)鍵字比較次數(shù)最大值為(A)。(A)n(B)n/2(C)log2

9、n(D)n*log2n21 .已知有向圖G=(V,E),其中V=v1,v2,v3,v4,v5,v6,則下列邊集合E中(A)所對(duì)應(yīng)的有向圖沒(méi)有拓?fù)湫蛄小?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

10、,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 .冒泡排序算法在最好情況下的時(shí)間復(fù)雜度為(B)。(A)O(l

11、og2n)(B)O(n)(C)O(1)(D)O(n2)23 .在下列內(nèi)部排序方法中，排序時(shí)不穩(wěn)定的，而且關(guān)鍵字的比較次數(shù)與記錄的初始排列次序無(wú)關(guān)的是(D)(A)快速排序(B)冒泡排序(C)歸并排序(D)堆排序24 .已知一個(gè)待散列存儲(chǔ)的線性表18,81,58,34,26,75,67,49,93,散列函數(shù)為h(k尸k%11,散列地址空間為010。若采用線性探查法解決沖突，則平均查找長(zhǎng)度為(C)。(A)5/3(B)13/9(C)16/9(D)3/225 .下列程序段所代表的算法的時(shí)間復(fù)雜度為(D)。i=1;j=0;while(i<=n)i+=j；j+；)(A)O(n)(B)O(n2)(C)O

12、(log2n)(D)O(.n)26 .將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，在最壞的情況下，其比較次數(shù)是(A)。(A)2n-1?(B)n?(C)n+1?(D)n-127 .若某鏈表中最常用的操作是在最后的一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用(D)存儲(chǔ)方式最節(jié)省運(yùn)行時(shí)間。(A)單鏈表(B)單循環(huán)鏈表(C)無(wú)頭雙向鏈表(D)帶頭雙向鏈表28 .已知head是一個(gè)非空單鏈表的頭指針，指針p指向單鏈表的最后一個(gè)結(jié)點(diǎn)，若要在p之后插入一個(gè)新結(jié)點(diǎn)*s,并將單鏈表變?yōu)檠h(huán)單鏈表，則應(yīng)執(zhí)行的操作是(B)0(A)s->next=p->next;p->next=s;(B)s-

13、>next=head;p->next=s;(C)s->next=p->next;p->next=head;(D)s->next=p->next;s->next=p;29 .已知用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n,若只設(shè)頭指針，則出隊(duì)和入隊(duì)一個(gè)元素的時(shí)間復(fù)雜度分別是(B)。(A)O(1)和O(1)(B)O(1)和O(n)(C)O(n)和O(1)(D)O(n)和O(n)30 .設(shè)鏈隊(duì)列Q的頭指針和尾指針?lè)謩e為front和rear,初始時(shí)隊(duì)列為空，若向隊(duì)列插入一個(gè)元素*s,則應(yīng)執(zhí)行的指針操作為(C)。(A)Q->front->next=s;s-&

14、gt;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 .已知一個(gè)帶權(quán)圖的頂點(diǎn)集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)

15、4,(7,8)5,(2,6)3,(2,5)5,(5,8)8,(5,6)5,(8,6)6).則該圖的最小生成樹(shù)的權(quán)值為(C)。(A)24(B)29(C)30(D)3132 .當(dāng)待排序的關(guān)鍵字個(gè)數(shù)n很小，且初始排列為逆序時(shí)，采用下列排序方法中的(D),算法的時(shí)間復(fù)雜度最小。(A)直接插入排序(B)簡(jiǎn)單選擇排序(C)冒泡排序(D)快速排序33 .對(duì)二叉排序樹(shù)進(jìn)行(C)遍歷，可以得到該二叉樹(shù)所有結(jié)點(diǎn)構(gòu)成的排序序列。(A)層次？?(B)前序？?(C)中序？?(D)后序34 .已知一個(gè)長(zhǎng)度為12的線性表(8,2,5,7,12,3,10,4,1,6,9,11),并將線性表中的元素依次插入到一個(gè)原先為空的二叉

16、排序樹(shù)中去。假設(shè)查找每一個(gè)元素的概率相同，則查找該二叉樹(shù)中任一結(jié)點(diǎn)的平均查找長(zhǎng)度為(A)。(A)10/3(B)13/3(C)37/12(D)13/235 .一組關(guān)鍵字序列15,92,124,5,27,28,18,6,36,34,30,26,32,259,將它們用散列函數(shù)H(key)=keyMOD11按順序散列到HASKHT(0:10)中，用鏈地址解決沖突。假設(shè)查找每一個(gè)元素的概率相同，則查找該HASHg中任一元素的平均查找長(zhǎng)度為(C)。(A)3/2(B)10/7(C)11/7(D)9/736 .以數(shù)據(jù)集4,5,6,7,12,18,10為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹(shù)，則其帶權(quán)路徑長(zhǎng)度WP西(A)0(

17、A)165(B)203(C)124(D)18737 .假定對(duì)線性表R0n-1進(jìn)行分塊查找，若將表均勻地分為b塊，每塊含有n/b個(gè)記錄；又假定表中每個(gè)記錄的查找概率相等，并用順序查找確定所在的塊，若要使分塊查找的平均查找長(zhǎng)度ASL最小，則分塊數(shù)b的值應(yīng)為(B)。(A)(B)詬+1(C)log2n(D)log2n+138 .對(duì)n個(gè)記錄進(jìn)行直接插入排序，所需的關(guā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 .若在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序，則該操作的時(shí)間復(fù)雜度是()

18、。(A)O(1)(B)O(n2(C)O(nlog2n)(D)O(n)40 .在一個(gè)頭結(jié)點(diǎn)為head的空循環(huán)鏈表中插入一個(gè)結(jié)點(diǎn)s,則指針s應(yīng)執(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;41 .設(shè)鏈隊(duì)列Q的頭指針和尾指針?lè)謩e為front和rear,隊(duì)中元素個(gè)數(shù)為n(n>1),指針*p指向隊(duì)首元素mi若刪除元素m,則應(yīng)進(jìn)行的

19、指針操作為()。(A)Q->front->next=p->next(B)Q->rear=Q->front(C)Q->front=p->rear(D)Q->rear=p->next42 .假設(shè)二叉樹(shù)T中有n個(gè)葉子結(jié)點(diǎn)，且所有非葉子結(jié)點(diǎn)都有左、右子樹(shù)，那么二叉樹(shù)T共有()個(gè)結(jié)點(diǎn)。(A)2n(B)2n-1(C)2n+1(D)2n+243 .已知有向圖G的鄰接矩陣如下所示，則下列序列中()不可能是圖G的拓?fù)湫蛄小?A)v1,v6,v3,v4,v2,v5(B)v1,v6,v4,v3,v2,v5(C)v1,v3,v2,v4,v6,v5(D)v1,v3,

20、v6,v4,v5,v244 .已知一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，數(shù)組內(nèi)容如下表所示，則該二叉樹(shù)的后序遍歷'序列為()01234567891011121314151617181920121EAFDGCJIHB(A)ACBDJEFIGH(B)ABCDJEFHGI(C)BCJDAHIGFE(D)EADCBJFGIH45 .若T為n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，則T的葉子結(jié)點(diǎn)數(shù)為()。(A)n/2(B)(n-2)/2(C)(n-1)/2(D)(n+1)/246 .有一組數(shù)值14,21,32,15,28,用以構(gòu)造huffman樹(shù)，則其WPlfi為()。(A)267(B)189(C)110(D)29

21、447 .采用折半插入排序，關(guān)鍵字的比較次數(shù)與移動(dòng)次數(shù)分別為()。(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)成一棵二叉排序樹(shù)，則在該二叉排序樹(shù)上查找一個(gè)結(jié)點(diǎn)的平均查找長(zhǎng)度為()。(A)23/8(B)11/4(C)9/2(D)449 .下面程序段的時(shí)間復(fù)雜性的量級(jí)為(D)。for(i=1;i<=n;i+)for(j=1;j<=m;j+)cij=0;for(k=1;k<=w;k+)cij+=aik*bkj(A)O

22、(i*j*k)(B)O(n*m*k)(C)O(n*j*k)(D)O(n*m*w)50 .在一個(gè)長(zhǎng)度為n的線性表中，刪除值為x的元素時(shí)需要比較元素和移動(dòng)元素的總次數(shù)為(C)。(A)(n+1)/2(B)n/2(C)n(D)n+151 .利用3,6,8,12,5,7這六個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹(shù)，該樹(shù)的深度為(B)。(A)3(B)4(C)5(D)652 .一棵二叉樹(shù)的廣義表表示為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,g53 .若長(zhǎng)度為n的

23、線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為()。(1<i<n+1)(A)O(0)?(B)O(1)?(C)O(n)?(D)O(n2)54 .若在線性表中采用折半查找法查找元素，該線性表應(yīng)該()。(A)元素按值有序？?？(B)采用順序存儲(chǔ)結(jié)構(gòu)(C)元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)(D)元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)55 .已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為()。?(A)-A+B*C/DE?(B)-A+B*CD/E(C)-+*ABC/DE?(D)-+A*BC/DE56 .若二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，

24、要交換其所有分支結(jié)點(diǎn)左右子樹(shù)的位置，利用()遍歷方法最合適。?(A)前序？?？(B)中序？?？(C)后序？?？(D)按層次57 .對(duì)二叉排序樹(shù)進(jìn)行()遍歷，可以得到該二叉樹(shù)所有結(jié)點(diǎn)構(gòu)成的排序序列。?(A)前序？?？(B)中序？?？(C)后序？?？(D)按層次58 .具有n個(gè)頂點(diǎn)的有向圖最多有()條邊。?(A)n?(B)n(n1)?Cn(n+1)?(D)n259 .從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為()排序法。?(A)插入?(B)選擇?(C)shell?(D)二路歸并60 .排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是()

25、排序法。?(A)插入？?？(B)選擇？?？(C)冒泡？?？(D)快速61 .下面給出的四種排序法中()排序法是不穩(wěn)定性排序法。(A)插入？?(B)冒泡？?？(C)二路歸并？(D)堆62 .一個(gè)對(duì)象序列的排序碼為46,79,56,38,40,84,采用快速排序以位于最左位置的對(duì)象為基準(zhǔn)而得到的第一次劃分結(jié)果為()。(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,8463 .線性鏈表不具有的特點(diǎn)是()。(A)隨機(jī)訪問(wèn)(B)不必事先估計(jì)所需存儲(chǔ)空間大小(C)插入與刪除時(shí)不必移動(dòng)元素(D)所需空

26、間與線性表長(zhǎng)度成正比64 .設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹(shù)，F(xiàn)中有n個(gè)非葉結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有()個(gè)。(A)n-1(B)n(C)n+1(D)n+265 .具有65個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為()。(根的層次號(hào)為0)(A)8(B)7(C)6(D)566 .若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，則采用()方法比較次數(shù)最少。(A)直接插入排序(B)快速排序(C)歸并排序(D)直接選擇排序67 .在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的()倍。(A)3(B)2(C)1(D)1/268 .對(duì)有14個(gè)數(shù)據(jù)元素的有序表R14進(jìn)行折半搜索，搜索到R3的關(guān)鍵碼等于給定值，

27、此時(shí)元素比較順序依次為()。(A)R0,R1,R2,R3(B)R0,R13,R2,R3(C)R6,R2,R4,R3(D)R6,R4,R2,R369 .若度為m的哈夫曼樹(shù)中，其葉結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù)為()(A)(n+1)/(m+1)-1(B)n/m-1(C)(n-1)/(m-1)(D)n/(m-1)-170 .下面關(guān)于算法說(shuō)法錯(cuò)誤的是()。(A)算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)(B)為解決某問(wèn)題的算法同為該問(wèn)題編寫(xiě)的程序含義是相同的(C)算法的可行性是指指令不能有二義性(D)以上幾個(gè)都是錯(cuò)誤的71 .以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是()。(A)循環(huán)隊(duì)列(B)鏈表(C)哈希表(D)棧72 .

28、以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)()。(A)廣義表(B)二叉樹(shù)(C)稀疏矩陣(D)用73 .以下那一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？()(A)棧(B)哈希表(C)線索樹(shù)(D)雙向鏈表74 .在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為()。FORi:=1TOnDOFORj:=1TOnDOx:=x+1;(A)O(2n)(B)O(n)(C)O(n2)(D)O(log2n)75 .以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類(lèi)型()。(A)棧(B)廣義表(C)有向圖(D)字符串76 .連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址()。(A)一定連續(xù)(B)一定不連續(xù)(C)不一定連續(xù)(D)部分連續(xù)，部分不連續(xù)77 .?一棵左右子樹(shù)均不空的二

29、叉樹(shù)在先序前驅(qū)和后序后繼線索化后，其空鏈域數(shù)為(A)。(A)01(B)1(C)2(D)不確定78 .設(shè)圖G采用鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度是(B)0(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n*e)79 .下列排序算法中，時(shí)間復(fù)雜度為O(nlog2n)且占用額外空間最少的是(A)。(A)堆排序(B)冒泡排序(C)快速排序(D)SHELL排序80 .已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，則采用(B)排序算法最節(jié)省時(shí)間快速排序(D)直接選擇排序任意個(gè)字母的序列有限個(gè)字符的序列(A)堆排序(B)插入排序(C)81 .用是(D)。(A)不少于一個(gè)字母的序列(B)(C)不少于

30、一個(gè)字符的序列(D)82 .一個(gè)棧的輸入序列為12345,則下列序列中是棧的輸出序列的是(A)(A)23415(B)54132(C)31245(D)1425383 .設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1n,其頭尾指針?lè)謩e為f和r,則其元素個(gè)數(shù)為(D)。(A)r-f(B)r-f+1(C)(r-f)modn+1(D)(r-f+n)modn84 .二叉樹(shù)在線索化后，仍不能有效求解的問(wèn)題是(D)。(A)先序線索二叉樹(shù)中求先序后繼(B)中序線索二叉樹(shù)中求中序后繼(C)中序線索二叉樹(shù)中求中序前驅(qū)(D)后序線索二叉樹(shù)中求后序后繼85 .求最短路徑的FLOYDT法的時(shí)間復(fù)雜度為(D)。(A)O(n)(B)O(n+e

31、)(C)O(n2)(D)O(n3)86 .一棵左右子樹(shù)不空的二叉樹(shù)在先序線索化后，其空指針域數(shù)為(B)。(A)0(B)1(C)2(D)不確定87 .數(shù)組A1.5,1.6的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先順序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A5,5的地址為(A)。(A)1140(B)1145(C)1120(D)112588 .在下列排序算法中，在待排序的數(shù)據(jù)表已經(jīng)為有序時(shí)，花費(fèi)時(shí)間反而最多的是(A)。(A)快速排序(B)希爾排序(C)冒泡排序(D)堆排序89 .對(duì)有18個(gè)元素的有序表做折半查找，則查找A3的比較序列的下標(biāo)依次為(D)。(A)1-2-3(B)9-5-2-3(C)9

32、-5-3(D)9-4-2-390 .下列排序算法中，某一趟結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是(D)0(A)堆排序(B)冒泡排序(C)快速排序(D)直接插入排序91 .在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡點(diǎn)為A,并已知A的左孩子的平衡因子為-1,右孩子的平衡因子為0,則做(B)型調(diào)整以使其平衡。(A)LL(B)LR(C)RL(D)RR92 .下列各式中，按增長(zhǎng)率由小至大的順序正確排列的是()。(A)n,n!,2n,n3/2(B)n3/2,2n,nlogn,2100(C)2n,logn,nlogn,n3/2(D)2100,logn,2n,nn93 .若要在單鏈表中的結(jié)

33、點(diǎn)*p之后插入一個(gè)結(jié)點(diǎn)*s,則應(yīng)執(zhí)行的語(yǔ)句是()。(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)的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對(duì)兩個(gè)循環(huán)鏈表各設(shè)置一個(gè)指針，分別指向()0(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

34、)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(C)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和索引存儲(chǔ)結(jié)構(gòu))O(B)順序存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)(D)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)96 .已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組為8和3,則該隊(duì)的當(dāng)前長(zhǎng)度為(data21,且當(dāng)前隊(duì)列的頭指針和尾指針的值分別(A)5(B)6(C)16)O(D)1797. 已知在如下定義的鏈審結(jié)點(diǎn)中，每個(gè)字符占1個(gè)字節(jié)，指針占4個(gè)字節(jié)，則該鏈用的存儲(chǔ)密度為()0typedefstructnodechardate8;structnode*next;LinkStrNode;(A)1/4(B)1/2(C)2/3(D)3/498. 應(yīng)用簡(jiǎn)單的匹配算法對(duì)主用s="BDBABDA

35、BDAB子用t="BDA進(jìn)行模式匹配，在匹配成功時(shí)，進(jìn)行的字符比較總次數(shù)為()。(A)7(B)9(C)10(D)1299. 二維數(shù)組A2010采用列優(yōu)先的存儲(chǔ)方法，若每個(gè)元素占2個(gè)存儲(chǔ)單元，且第1個(gè)元素的首地址為200,則元素A89的存儲(chǔ)地址為()。(A)574(B)576(C)578(D)580100. 對(duì)廣義表L=(a,b),c,d)進(jìn)行操作tail(head(L)的結(jié)果是()。(A)(c,d)(B)(d)(C)b(D)(b)101. 已知一棵樹(shù)的前序序列為ABCDEF后序序歹為CEDFBA則對(duì)該樹(shù)進(jìn)行層次遍歷得到的序列為()。(A)ABCDEF(B)ABCEFD(C)ABFCD

36、E(D)ABCDFE102. 一個(gè)含n個(gè)頂點(diǎn)和e條弧的有向圖以鄰接矩陣表示法為存儲(chǔ)結(jié)構(gòu)，則計(jì)算該有向圖中某個(gè)頂點(diǎn)出度的時(shí)間復(fù)雜度為()0(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é)點(diǎn)時(shí)，所需進(jìn)行的比較次數(shù)分別為()。(A)4,4,3(B)4,3,3(C)3,4,4(D)3,3,4104. 下列排序方法中，最好與最壞時(shí)間復(fù)雜度不相同的排序方法是()。(A)冒泡排序(B)直接選擇排序(C)堆排序(D)歸并排序105. 已知含10個(gè)結(jié)點(diǎn)的二叉排序樹(shù)是一棵完全二叉樹(shù)，則

37、該二叉排序樹(shù)在等概率情況下查找成功的平均查找長(zhǎng)度等于()。(A)1.0(B)2.9(C)3.4(D)5.5106. 在下列各種文件中，不能進(jìn)行順序查找的文件是()。(A)順序文件(B)索引文件(C)散列文件(D)多重表文件107.卜面帶有B記的語(yǔ)句的頻度(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)不確定108. 已知使用順序表存儲(chǔ)數(shù)據(jù)，表長(zhǎng)為n,假設(shè)在表中的任意位置插入元素的概率相等,則

38、插入一個(gè)元素，平均需要移動(dòng)的元素個(gè)數(shù)()0(A)(n-1)/2(B)n/2(C)(n+1)/2(D)不確定109. 在雙向鏈表p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是()。(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)用長(zhǎng)度相

39、等(B)用使用相同的存儲(chǔ)結(jié)構(gòu)(C)用相同位置對(duì)應(yīng)的字符相等(D)A和C111. 將一個(gè)遞歸算法改為對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用()。(A)數(shù)組(B)棧(C)隊(duì)列(D)二叉樹(shù)112. 一個(gè)棧的入棧序列1,2,3,4,5,則棧的不可能的輸出序列是()。(A)12345(B)54321(C)32514(D)12354113. 設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1n，其頭尾指針?lè)謩e為f和r,則其元素個(gè)數(shù)為()。(A)r-f(B)r-f+1(C)(r-f)modn+1(D)(r-f+n)modn114. 某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是ABDEFCGH中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是DBFEAGHC,U其后序遍歷

40、的結(jié)點(diǎn)訪問(wèn)順序是()。(A)DFEBHCGA(B)DFEBHGCA，(C)DEFBHGCA(D)DFEHBGCA115. 正則二叉樹(shù)是只有度為0和2的結(jié)點(diǎn)的二叉樹(shù)，已知正則二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)為n,則該二叉樹(shù)總得結(jié)點(diǎn)數(shù)為()。(A)n+1(B)2*n(C)2*n+1(D)2*n-1116. 下面關(guān)于排序的說(shuō)法錯(cuò)誤的是()。(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),若查找

41、元素3,則被比較的元素依次為()。(A)10,20,30(B)10,14,30(C)13,3(D)10,4,3118. 下面關(guān)于棧和隊(duì)列的說(shuō)法正確的是()。(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ù)是()。120. (A)n(B)2n-1(C)2n(D)n-1121. 設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是0n-1,f表示隊(duì)首元素的前驅(qū)位置，r表示隊(duì)尾元素的位置，則隊(duì)列中元素個(gè)

42、數(shù)為()。122. (A)r-f(B)r-f1(C)(r-f1)modn(D)(r-fn)modn123. 一個(gè)5行6列的二維數(shù)組s采用從最后一行開(kāi)始，每一行的元素從右至左的方式映射到一維數(shù)組a中，s和a的下標(biāo)均從0開(kāi)始，則s33在a中的下標(biāo)是()。124. (A)7(B)8(C)9(D)10125. 設(shè)只含根結(jié)點(diǎn)的二叉樹(shù)的高度為1,則高度為n的二叉樹(shù)中所含葉子結(jié)點(diǎn)的個(gè)數(shù)最多為()個(gè)。126. (A)2n(B)n(C)2n-1(D)2n-1127. 設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為()個(gè)(設(shè)只含根結(jié)點(diǎn)的二叉樹(shù)的高度為1)。128. (A)2h(B)

43、2h-1(C)2h+1(D)h+1129. 對(duì)一棵二叉檢索樹(shù)進(jìn)行()得到的結(jié)點(diǎn)序列是一個(gè)有序序列。130. (A)前序周游(B)中序周游(C)后序周游(D)層次周游131. 一棵前序序列為1,2,3,4的二叉樹(shù)，其中序序列不可能是()。132. (A)4,1,2,3(B)4,3,2,1(C)2,4,3,1(D)3,4,2,1133. 在含n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，零元素的個(gè)數(shù)為()。134. (A)e(B)2e(C)n2-e(D)n2-2e135. 具有n個(gè)頂點(diǎn)和e條邊的圖的深度優(yōu)先搜索算法的時(shí)間復(fù)雜度為()。(A)O(n)(B)O(n3)(C)O(n2)(D)O(ne)136.

44、如果具有n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有()棵生成樹(shù)。137. (A)n(B)nl(C)n-l(D)2n138. 堆排序算法在平均情況下的時(shí)間復(fù)雜度為()。(A)O(n)(B)O(nlogn)(C)O(n2)(D)O(logn)139. 在待排序數(shù)據(jù)已基本有序的前提下，下述排序方法中效率最高的是()。(A)直接插入排序(B)直接選擇排序(C)快速排序(D)歸并排序140. 在理想情況下，散列表中查找元素所需的比較次數(shù)為()。141. (A)n(B)O(C)n/2(D)1142. 在一棵m階B樹(shù)中，若在某結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是()0143. (A)m(

45、B)m+1(C)m-l(D)m/2144. 設(shè)順序循環(huán)隊(duì)列Q0:M-1的頭指針和尾指針?lè)謩e為F和R,頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為(C)。(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M145. 設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD前序遍歷序列為CABD則后序遍歷該二叉樹(shù)得到序列為(A)。(A)BADC(B)BCDA(C)CDAB(D)CBDA146. 設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有(A)條邊。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-1147. 設(shè)某棵二叉樹(shù)中有20

46、00個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的最小高度為(C)。(A)9(B)10(C)11(D)12148. 設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有(B)個(gè)表頭結(jié)點(diǎn)。(A)n-1(B)n(C)n+1(D)2n-1149. 設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為(C)。(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,8150. 設(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

47、,04>,<02,05)<02,06>,<03,07><03,08)<03,09>,則數(shù)據(jù)結(jié)構(gòu)AM(B)。(A)線性結(jié)構(gòu)(B)樹(shù)型結(jié)構(gòu)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu)151. 下面程序的時(shí)間復(fù)雜為(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)作序列為(A(A)q=p->next(B)q=p->next(C)q=p->next(D)q=p->next；p->data=q->d

48、ata；q->data=p->data;p->next=q->next；p->data=q->data152. 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,若刪除單鏈表中結(jié)點(diǎn)A,則需要修改指針的操;p->next=q->next;free(q);p->next=q->next;free(q);；free(q);；free(q);153. 設(shè)有n個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要(A)個(gè)輔助記錄單元。(A)1(B)n(C)nlog2n(D)n2154. 設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20,15,14,18,21,36,40,10),則以20為基

49、準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為(A)0(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,21155. 設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為(B)。(A)O(1)(B)O(log2n)(C)log2n(D)O(n2)156. 設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為(D)。.(A)n,e(B)e,n(C)2n,e(D)n,2e157. 設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通

50、圖中至少有(C)條邊。(A)n(n-1)(B)n+1(C)n(D)n(n+1)158. 設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列(B)方法可以達(dá)到此目的。(A)快速排序(B)堆排序(C)歸并排序(D)插入排序159. 下列四種排序中(D)的空間復(fù)雜度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序160. 設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為(C)。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2)161. 設(shè)一棵二叉樹(shù)的深度為k,則該二叉樹(shù)中最多有(D)個(gè)結(jié)點(diǎn)(A)2k-1(B)

51、2k(C)2k-1(D)2k-1D)。162. 設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則該無(wú)向圖中所有頂點(diǎn)的入度之和為(A)n(B)e(C)2n(D)2e163. 在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為(B)。(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)164. 設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有(C)條有向邊。(A)n(B)n-1(C)m(D)m-1165. 設(shè)一組初始記錄關(guān)鍵字序列為(345,253,674,924,627),則用基數(shù)排序需要進(jìn)行(A)趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(A)3(B)4(C)5(D)8166. 設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作(B)0(A)必須判別棧是否為滿(B)必須判別棧是否為空(C)判別棧元素的類(lèi)型(D)對(duì)棧不作任何判別W167. 下列四種排序中(A)的空間復(fù)雜度最大。(A)快速排序(B)冒泡排序(C)希爾排序(D)堆168. 設(shè)某二