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

數(shù)據(jù)結(jié)構(gòu)試題庫(kù)單項(xiàng)選擇題下列程序段所代表的算法的時(shí)間復(fù)雜度為（D)。x=n；ｙ=0；ｗhｉle(x>=(y+１)*(y+１）)y＋+;(A)O（n)(Ｂ）Ｏ(ｎ２)(Ｃ)O(lｏg2n)(D)Ｏ()在一個(gè)長(zhǎng)度為n的以順序結(jié)構(gòu)存儲(chǔ)的線性表中,假設(shè)在線性表的任何位置刪除元素的概率相等，則刪除一個(gè)元素時(shí)線性表所需移動(dòng)元素的平均次數(shù)為（B）。(A)ｎ２（B)(n-1)／２(C)（n+1)/2(D)n/2在一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí),應(yīng)執(zhí)行執(zhí)行操作為（Ｃ)。(A)HS->nｅxt=s；(Ｂ)s->neｘt=HS－>next;ＨS－>neｘt=ｓ;(Ｃ）s->ｎext=HS;HＳ=s;(D）ｓ-＞ｎexｔ＝ＨS;HＳ=ＨS>nｅxｔ;假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表達(dá)隊(duì)列Q，并且隊(duì)列只設(shè)一個(gè)頭指針ｆront,不設(shè)隊(duì)列尾指針。若要進(jìn)隊(duì)一個(gè)元素*s，則在下列程序算法的空白處應(yīng)添加的操作語(yǔ)句是(A）。vｏidＡddQueue(ｓtｒuｃtlｉnkｑｕeｕeQ）｛ｐ＝Ｑ->ｆroｎt;wｈile(p－>neｘt!=Q－＞fｒont)p=ｐ->next;}(Ａ）ｐ－>neｘｔ=ｓ;s－>nｅｘt=Q->frｏｎt;(B)Q->fｒont－>next=s;Q->frｏnt=s;（C)s->ｎext=p;p->nｅxt=Q->frｏｎt;(D)Q->ｆｒont－>ｎext=s;s->nｅxt=p；設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn),則此類(lèi)二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為（B)。(A)2h－1（B)2ｈ－1＋1(C)２ｈ－1(D)2ｈ－1-3現(xiàn)有數(shù)據(jù)集{53,30,37,1２,４5,24,9６}，從空二叉樹(shù)逐個(gè)插入數(shù)據(jù)形成二叉排序樹(shù),若希望查找此二叉樹(shù)中任一結(jié)點(diǎn)的平均查找長(zhǎng)度最小，則應(yīng)選擇下面哪個(gè)序列輸入（C)。(A）45,２4,５3,1２,37,9６,3０（B)30,２4,1２,37，45,96,５3(C)3７,24,12,30,5３，45,96（Ｄ)12,24,3０,3７,45,５3,96有一組數(shù)值｛5,12，9，20,3}，用以構(gòu)造哈夫曼樹(shù)，則其帶權(quán)途徑長(zhǎng)度WPL值為(D)。(A)９3(B)96(C)123(D)１0３已知一個(gè)有向圖G的頂點(diǎn)ｖ={v1,v２,v3,ｖ４，v5,v6}，其鄰接表如下圖所示,根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā),所得到的頂點(diǎn)遍歷序列是(Ｂ)。(A)v1,v2,ｖ３,v6,v4,ｖ５(B)v1，ｖ2,v3,v6,ｖ5,v4(C)v1,v2,v5，v6，v3,v4（Ｄ)ｖ１,v2,v5,v3,ｖ4,v６v3^v4^v5v5^v6v3^v4^v5v5^v6^v1v2v2v2v3^v3v3v6^v6^v４＾v5v4v4v６＾設(shè)有m=2ｎ－1個(gè)關(guān)鍵字，假設(shè)對(duì)每個(gè)關(guān)鍵字查找的概率相等，查找失敗的概率為0，若采用二分法查找一個(gè)關(guān)鍵字,則平均查找長(zhǎng)度為(D）。（A)ｎ－１(Ｂ)n-n/m(Ｃ)（n-１)－n/ｍ(Ｄ)(n-1)+ｎ／m已知一個(gè)待散列存儲(chǔ)的線性表{1８,81,５8，３4,２6,75,67,49,9３}，散列函數(shù)為ｈ（ｋ)=k%１１，散列地址空間為０~1０。若采用線性探查法解決沖突,則平均查找長(zhǎng)度為（A）。(A）５/3(B)13/9(C)１６/9（Ｄ)3/2下列程序段所代表的算法的時(shí)間復(fù)雜度為（Ｃ）。y=ｎ;x＝1;ｗhile（x＜=ｙ）x*=２;(Ａ)O（ｎ)(B)O(n2)(C)O（log２n)(D)O（)在一個(gè)長(zhǎng)度為n的以順序結(jié)構(gòu)存儲(chǔ)的線性表中,假設(shè)在線性表的任何位置插入元素的概率相等，則插入一個(gè)元素時(shí)線性表所需移動(dòng)元素的平均次數(shù)為（B)。(A)n２（Ｂ)(n+1）／2(C)(n-１)/２(D)n／2若對(duì)一個(gè)已有序的線性表最頻繁的操作是查找值為x的元素(假設(shè)存在的話),則采用（D)存儲(chǔ)方式實(shí)現(xiàn)查找，其算法的時(shí)間復(fù)雜度為最小。(Ａ）單鏈表(Ｂ)雙鏈表(C）單循環(huán)鏈表（D)順序表一個(gè)帶頭結(jié)點(diǎn)head的循環(huán)單鏈表為空的判斷條件是(C)。(A）heａｄ==NULL（B)heａd－>neｘｔ＝=NＵLL(Ｃ)hｅad->next=＝ｈｅad(D)ｈｅad!=NＵLＬ若鏈隊(duì)列HQ中只有一個(gè)結(jié)點(diǎn)，則隊(duì)列的頭指針和尾指針滿足下列條件(D)。(Ａ)ＨＱ－>rear->nｅxt==ＨQ-＞front(B)HQ->froｎt->ｎext＝=HQ->reａr->ｎｅxt(C)HQ->frｏｎt==ＨQ－＞reａr（D)HQ->front－>next==HQ->rｅar從一個(gè)棧頂指針為ＨS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用ｘ保存被刪除結(jié)點(diǎn)的值,則應(yīng)執(zhí)行操作為（A)。(A)x=HS－>dａt(yī)a;HS＝HS-＞neｘt;（B）x＝HS->daｔａ;ＨS->NＥＸT=NＵLL;(C)HS＝HS->ｎext;ｘ＝HS->data;(Ｄ)x＝HＳ->data;HS＝ＮUＬL；一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù),有ｍ個(gè)葉子結(jié)點(diǎn),深度為h，那么n、m和h滿足條件(D)。(A)ｎ＝m＋h（B)h+m＝2n（C)m＝ｈ-1(Ｄ)n=2ｈ-1一棵左、右子樹(shù)均不為空的二叉樹(shù)在先序線索化后,其空指針域數(shù)為（B)。(A)0(B)1（Ｃ）２(D)不擬定有一組數(shù)值{5，12,9,20,３}，用以構(gòu)造哈夫曼樹(shù),則其帶權(quán)途徑長(zhǎng)度WＰL值為(Ｃ）。(A)4９(B)９6(C）10３(D)12５在一個(gè)ｎ個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中查找一個(gè)關(guān)鍵字,進(jìn)行關(guān)鍵字比較次數(shù)最大值為（Ａ)。(A)n（B)n/2（C)ｌｏg２n（D)n*log2n已知有向圖Ｇ=(V,E)，其中V={v１,ｖ２,v3,v4,ｖ5,v6},則下列邊集合Ｅ中（A)所相應(yīng)的有向圖沒(méi)有拓?fù)湫蛄?。E={＜v2,v1>,<v6,v２>，<v1,v３>,<v２,v3＞,<v５,ｖ３>,＜ｖ3,v4>,<v４，v6>,<ｖ5,v6＞}E={<v1,v2>,<v1,ｖ3>，<ｖ1,v4>,＜v3,ｖ5>,<v３，v2＞,＜v4,v5>，<ｖ6,v5>,<ｖ６，v4>｝E={<v１,v3>,<v1,v4＞,<ｖ1,v5>,<v2,v３>，＜ｖ2,v2>,<v3，v5>，＜v3,v6>,<v4，v5＞,<ｖ4,ｖ６>，＜v５,ｖ6>}E={<v1,v２>,＜v1，ｖ3>,<v２,v3＞，＜v１,v4>,＜v2，v5＞,<v3,v6>,<ｖ４,ｖ６＞,<v5，v6>｝冒泡排序算法在最佳情況下的時(shí)間復(fù)雜度為（B)。(A)O(lｏｇ2n)(B)O(n）(C)O(１)(D）O(n2）在下列內(nèi)部排序方法中，排序時(shí)不穩(wěn)定的,并且關(guān)鍵字的比較次數(shù)與記錄的初始排列順序無(wú)關(guān)的是（D）。(A)快速排序（B)冒泡排序(C)歸并排序(D)堆排序已知一個(gè)待散列存儲(chǔ)的線性表{18,８1,58,３4,26,75,６7,4９,93},散列函數(shù)為h(ｋ)=k%1１，散列地址空間為0～１0。若采用線性探查法解決沖突,則平均查找長(zhǎng)度為（C）。(Ａ)5/3(B)13/9(Ｃ)１6/9(D)3／2下列程序段所代表的算法的時(shí)間復(fù)雜度為(D）。i=1;j＝0;while（ｉ<=n)｛i＋=j；ｊ++；}(A)Ｏ(n)(B)O（ｎ２)（C）O(lｏg2n）(D)Ｏ（)將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，在最壞的情況下,其比較次數(shù)是(Ａ）。(Ａ)2ｎ－1

(B)n

(C)ｎ+1

(Ｄ)ｎ-1若某鏈表中最常用的操作是在最后的一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn),則采用(D)存儲(chǔ)方式最節(jié)省運(yùn)營(yíng)時(shí)間。(Ａ)單鏈表(B）單循環(huán)鏈表(C)無(wú)頭雙向鏈表（D)帶頭雙向鏈表已知head是一個(gè)非空單鏈表的頭指針，指針p指向單鏈表的最后一個(gè)結(jié)點(diǎn)，若要在p之后插入一個(gè)新結(jié)點(diǎn)*s,并將單鏈表變?yōu)檠h(huán)單鏈表，則應(yīng)執(zhí)行的操作是（B）。(A)s->next=p->nｅxt；p->ｎext=s;(B)ｓ－>ｎｅxｔ=heａｄ；p－>neｘt=s;(C）s－>next=p->next;ｐ－>ｎext＝head；(D)s－>nexｔ=p－>nexｔ;s->next=ｐ;已知用循環(huán)鏈表表達(dá)的隊(duì)列長(zhǎng)度為n,若只設(shè)頭指針,則出隊(duì)和入隊(duì)一個(gè)元素的時(shí)間復(fù)雜度分別是（B）。(A)Ｏ(1)和O（1)(B)Ｏ(1)和O（n)（C)O(n)和O(1)(D）O(n)和Ｏ(ｎ)設(shè)鏈隊(duì)列Ｑ的頭指針和尾指針?lè)謩e為fｒont和ｒear,初始時(shí)隊(duì)列為空,若向隊(duì)列插入一個(gè)元素*s，則應(yīng)執(zhí)行的指針操作為(C)。(A)Q-＞ｆrｏnt->ｎext=ｓ;s－>ｎext=Q->rear；Ｑ－>ｒear＝NULL;(Ｂ)s->ｎeｘt=Q->front；Q－>reaｒ->nexｔ=s;Q－>reaｒ=NULL;(C）Q->reaｒ-＞nexｔ=ｓ;Ｑ->reａr=s;s->neｘt=ＮULL；(D)Q-＞front->ｎｅｘｔ=s;Q-＞rear=s;s－＞nｅxｔ=NUＬL;已知一個(gè)帶權(quán)圖的頂點(diǎn)集V和邊集G分別為：Ｖ＝｛1,2,3，4,5,6，7，8｝;E＝｛(3,1）6,(３，４)7,(3,7）5,(１,２)3，(1,4)4,(４，7)８，(4,５)4，(7,8)５,（2,6)3,(2,5)5,(5，8)8,(5,6)5，(8,6)6},則該圖的最小生成樹(shù)的權(quán)值為（C）。(Ａ)24(B)２９(Ｃ)３0(D）31當(dāng)待排序的關(guān)鍵字個(gè)數(shù)n很小,且初始排列為逆序時(shí),采用下列排序方法中的(D），算法的時(shí)間復(fù)雜度最小。（A)直接插入排序(Ｂ)簡(jiǎn)樸選擇排序(C)冒泡排序(D)快速排序?qū)Χ媾判驑?shù)進(jìn)行（C）遍歷，可以得到該二叉樹(shù)所有結(jié)點(diǎn)構(gòu)成的排序序列。（Ａ)層次

(Ｂ)前序

(C）中序

（D)后序已知一個(gè)長(zhǎng)度為1２的線性表（８,2，5，7，１2,3，10，4,1,6,９,１1），并將線性表中的元素依次插入到一個(gè)原先為空的二叉排序樹(shù)中去。假設(shè)查找每一個(gè)元素的概率相同,則查找該二叉樹(shù)中任一結(jié)點(diǎn)的平均查找長(zhǎng)度為（A）。(A)10/3(B）13/3(C)３7/1２(Ｄ)１3／2一組關(guān)鍵字序列{１5,９2,12４，5，27,２８,１8，6，36，３4，30,2６，32，259｝，將它們用散列函數(shù)Ｈ(ｋey）=ｋeyＭOD１1按順序散列到HＡＳH表HT（０:１０)中,用鏈地址解決沖突。假設(shè)查找每一個(gè)元素的概率相同,則查找該HASH表中任一元素的平均查找長(zhǎng)度為(C）。(A)3/２(B)1０／7(C)1１／7(D)9/７以數(shù)據(jù)集｛4,５，6,7，1２,18,10}為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹(shù)，則其帶權(quán)途徑長(zhǎng)度ＷPL為(A）。(Ａ)165(B）203(C)124(D)18７假定對(duì)線性表Ｒ[0…n-１]進(jìn)行分塊查找,若將表均勻地分為b塊,每塊具有n/b個(gè)記錄;又假定表中每個(gè)記錄的查找概率相等，并用順序查找擬定所在的塊,若要使分塊查找的平均查找長(zhǎng)度ASL最小,則分塊數(shù)b的值應(yīng)為(B）。(A)(B）+１（Ｃ）「lｏg2n」（D）「ｌｏg2n」＋１對(duì)n個(gè)記錄進(jìn)行直接插入排序,所需的關(guān)鍵字比較次數(shù)的最大值和最小值分別是(C)。(A)n(n+1）／2和ｎ(Ｂ)ｎ（n-1）/2和n－1(C）n（n+1)/2-1和ｎ－１(D)n２和n若在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序，則該操作的時(shí)間復(fù)雜度是（)。（A）O(1)（B)O(n2)(C）Ｏ(nｌog2n)(D）Ｏ(n)在一個(gè)頭結(jié)點(diǎn)為hｅad的空循環(huán)鏈表中插入一個(gè)結(jié)點(diǎn)ｓ，則指針ｓ應(yīng)執(zhí)行操作(）。(A)hｅad-＞ｎext=s;ｓ-＞neｘt=NＵLL；(Ｂ)s->ｎext＝head;ｈead－>next=ＮUＬL;（C）ｈｅaｄ->nｅxｔ＝s;s-＞next＝head－>next;(D)s->neｘt=head;ｈeａd－>nｅxt=ｓ；設(shè)鏈隊(duì)列Q的頭指針和尾指針?lè)謩e為ｆｒont和ｒeａr,隊(duì)中元素個(gè)數(shù)為n（n>1),指針*p指向隊(duì)首元素ｍ。若刪除元素ｍ，則應(yīng)進(jìn)行的指針操作為（）。(Ａ)Ｑ-＞fronｔ->next=ｐ->ｎext（B)Ｑ->ｒeａr=Q－＞front(C)Q－＞front=p->rear(D）Ｑ－>rear=p->next假設(shè)二叉樹(shù)T中有n個(gè)葉子結(jié)點(diǎn)，且所有非葉子結(jié)點(diǎn)都有左、右子樹(shù)，那么二叉樹(shù)T共有（）個(gè)結(jié)點(diǎn)。(A)２n(B)2n-１(C）2ｎ+１(Ｄ)2ｎ+2已知有向圖G的鄰接矩陣如下所示，則下列序列中（）不也許是圖Ｇ的拓?fù)湫蛄小?A）ｖ1,v6，v3,ｖ4,v2，ｖ５(B）v1,ｖ6,v4,v3,v2，v5(Ｃ)v１,ｖ3,ｖ2,ｖ4,v6,v5(Ｄ)v１,v3,v6,v４,ｖ5,v2已知一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu),數(shù)組內(nèi)容如下表所示，則該二叉樹(shù)的后序遍歷序列為(）。11２３45６７89１0111２1３14１5161７18192021EＡFＤGCJIHB(Ａ）ACBDＪEＦIＧＨ(B）ABCＤJＥFＨGI(C)BＣJDＡHIGFE(D)EADＣBJFGIH若T為ｎ個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，則T的葉子結(jié)點(diǎn)數(shù)為（）。(A)ｎ／２(B)（n-2）/2(C）(n-1)/2(D)(n+1)／２有一組數(shù)值１4,２１，32,１5,28,用以構(gòu)造hufｆman樹(shù)，則其WPL值為（)。(A)２6７(B)18９(Ｃ)110(D）294采用折半插入排序,關(guān)鍵字的比較次數(shù)與移動(dòng)次數(shù)分別為（）。(A)O(n），O(lｏｇ2n）(B)O（n2),Ｏ(lｏg2n)(C)O(ｌｏｇ２n),O(n2)（D）Ｏ(nloｇ2n),O(n2)假設(shè)結(jié)點(diǎn)序列為｛60,３0,90,５０，９5,7０,40,80}，以此構(gòu)成一棵二叉排序樹(shù)，則在該二叉排序樹(shù)上查找一個(gè)結(jié)點(diǎn)的平均查找長(zhǎng)度為（)。(A）２3/8(B)１1/４(C）９/2(D)4下面程序段的時(shí)間復(fù)雜性的量級(jí)為(D）。foｒ(i=1；ｉ<＝n；i++)fｏｒ(j=1；j<＝m;j++){c[ｉ][j]=0;for（k=1;k<=w;k+＋)c［i]［j]+=ａ[i][ｋ]*ｂ[ｋ][j］}(Ａ)O(i*ｊ*k)(B)O（ｎ*m＊k)(C)O(n*j*ｋ)(D)Ｏ（n＊m*w)在一個(gè)長(zhǎng)度為n的線性表中,刪除值為x的元素時(shí)需要比較元素和移動(dòng)元素的總次數(shù)為(C）。（A)（n+1）／2(B)n／2(C)n(Ｄ)n+1運(yùn)用3，6，8,12，5,7這六個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹(shù)，該樹(shù)的深度為（B)。(A)3(B）4（C)5(D)６一棵二叉樹(shù)的廣義表表達(dá)為ａ（b(c,d),e(,f(g))）,則得到的層次遍歷序列為(D）。(A)a,b,c,ｄ，e，f，g(B)c,b,d,ａ,e,g，f(Ｃ）c,d，ｂ,g,ｆ,e，a(D）a,b，ｅ，c,d,f,g若長(zhǎng)度為n的線性表采用順序存儲(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)若在線性表中采用折半查找法查找元素，該線性表應(yīng)當(dāng)(）。(Ａ)元素按值有序

(B)采用順序存儲(chǔ)結(jié)構(gòu)(C)元素按值有序,且采用順序存儲(chǔ)結(jié)構(gòu)(D)元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)已知一算術(shù)表達(dá)式的中綴形式為A＋B＊C-D/E,后綴形式為ABC*+DＥ/－，其前綴形式為()。

(Ａ)–A+Ｂ＊C/ＤE

(B)–A+B*CD/Ｅ(Ｃ)-+*AＢＣ/DE

(Ｄ)-+A＊BC／DＥ若二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu),要互換其所有分支結(jié)點(diǎn)左右子樹(shù)的位置，運(yùn)用()遍歷方法最合適。

（A)前序

(Ｂ)中序

(C)后序

(Ｄ)按層次對(duì)二叉排序樹(shù)進(jìn)行(）遍歷,可以得到該二叉樹(shù)所有結(jié)點(diǎn)構(gòu)成的排序序列。

(Ａ)前序

（Ｂ）中序

(C）后序

(D)按層次具有ｎ個(gè)頂點(diǎn)的有向圖最多有（)條邊。

(A)n

(B)n(n—1)

Cn（n+１)

(D)n２從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置,該排序方法稱為（)排序法。

（A)插入

(Ｂ)選擇

（C)shelｌ

(D)二路歸并排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是（）排序法。

(A)插入

（Ｂ)選擇

（Ｃ)冒泡

（D)快速下面給出的四種排序法中(）排序法是不穩(wěn)定性排序法。(Ａ）插入

(B）冒泡

(C)二路歸并

（D）堆一個(gè)對(duì)象序列的排序碼為{46，79，５6,３8，40,8４｝，采用快速排序以位于最左位置的對(duì)象為基準(zhǔn)而得到的第一次劃分結(jié)果為()。(Ａ){３8,4６,79,56,40,８4}(Ｂ){38，79,５6，4６，４0，84}(C)｛40,38,46，5６，７9，84｝（D)｛38，46，56,7９，40,8４}線性鏈表不具有的特點(diǎn)是()。(A)隨機(jī)訪問(wèn)(B)不必事先估計(jì)所需存儲(chǔ)空間大小(Ｃ)插入與刪除時(shí)不必移動(dòng)元素(D)所需空間與線性表長(zhǎng)度成正比設(shè)Ｆ是一個(gè)森林，Ｂ是由F轉(zhuǎn)換得到的二叉樹(shù)，F(xiàn)中有n個(gè)非葉結(jié)點(diǎn),則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有()個(gè)。（A）n-1（Ｂ)ｎ(C)ｎ+1(D)ｎ+2具有6５個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為()。（根的層次號(hào)為0）(A)８(B)７(C）6(D）５若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序,則采用()方法比較次數(shù)最少。(A)直接插入排序(Ｂ)快速排序（Ｃ）歸并排序（D）直接選擇排序在一個(gè)無(wú)向圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的()倍。(A)3(B)2(Ｃ)1（D)1／２對(duì)有１4個(gè)數(shù)據(jù)元素的有序表R[１4]進(jìn)行折半搜索，搜索到R[3]的關(guān)鍵碼等于給定值，此時(shí)元素比較順序依次為()。（A)Ｒ[0]，Ｒ［1］,R[２],R[３](B)R[0]，R[１3],Ｒ[２］，R[3](Ｃ)R[6]，R［2］，R［４］，R［3]（D)Ｒ［6]，R[４］,R［2］,Ｒ[3］若度為m的哈夫曼樹(shù)中,其葉結(jié)點(diǎn)個(gè)數(shù)為n，則非葉結(jié)點(diǎn)的個(gè)數(shù)為()。（A）[（n+1)/(ｍ+1)]-１(Ｂ）［n/ｍ]－１（C)[(n-1）／(m-１)](D）[ｎ/(m-1)]－１下面關(guān)于算法說(shuō)法錯(cuò)誤的是(）。（A)算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)(Ｂ)為解決某問(wèn)題的算法同為該問(wèn)題編寫(xiě)的程序含義是相同的(C)算法的可行性是指指令不能有二義性（D)以上幾個(gè)都是錯(cuò)誤的以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（)。(A）循環(huán)隊(duì)列(B）鏈表(Ｃ)哈希表（D)棧以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（）。(A)廣義表（B)二叉樹(shù)(C)稀疏矩陣(D）串以下那一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？（)（A)棧(B）哈希表(C）線索樹(shù)(Ｄ)雙向鏈表在下面的程序段中,對(duì)x的賦值語(yǔ)句的頻度為（)。FＯRi:＝1TＯnＤOFORj：=1TOｎDOx：=x+1；(A）O（2n）(B)O（n）（C)O(n2)（D）O(log2n)以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類(lèi)型（)。(Ａ)棧(B)廣義表(Ｃ)有向圖(D)字符串連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址(）。(A)一定連續(xù)(Ｂ)一定不連續(xù)(C）不一定連續(xù)(Ｄ）部分連續(xù),部分不連續(xù)

一棵左右子樹(shù)均不空的二叉樹(shù)在先序前驅(qū)和后序后繼線索化后,其空鏈域數(shù)為(Ａ）。（Ａ)0（Ｂ)1（C)2(D)不擬定設(shè)圖G采用鄰接表存儲(chǔ),則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度是（B)。(A）Ｏ(n)(B)O(n+e)(C)O（n２)(D)O（n＊ｅ)下列排序算法中，時(shí)間復(fù)雜度為Ｏ(nlog2ｎ)且占用額外空間最少的是（A）。(A)堆排序(Ｂ)冒泡排序(C)快速排序(D）SＨELL排序已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn),則采用（B）排序算法最節(jié)省時(shí)間。(A)堆排序(Ｂ)插入排序（C）快速排序(Ｄ)直接選擇排序串是（D)。(A)不少于一個(gè)字母的序列(B)任意個(gè)字母的序列(C)不少于一個(gè)字符的序列(D）有限個(gè)字符的序列一個(gè)棧的輸入序列為12３4５,則下列序列中是棧的輸出序列的是(A)。(A)２３４15(B)54１32(Ｃ)3124５(D）1４253設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1~n,其頭尾指針?lè)謩e為f和r，則其元素個(gè)數(shù)為（Ｄ)。(A)r-f（B）ｒ－f＋１(C)（ｒ-f)ｍodn+１（Ｄ）(r－f+n)ｍｏdn二叉樹(shù)在線索化后,仍不能有效求解的問(wèn)題是(D)。（A)先序線索二叉樹(shù)中求先序后繼(B)中序線索二叉樹(shù)中求中序后繼（C)中序線索二叉樹(shù)中求中序前驅(qū)(D）后序線索二叉樹(shù)中求后序后繼求最短途徑的FLＯYD算法的時(shí)間復(fù)雜度為（Ｄ）。(A)O(n)(B)Ｏ(ｎ+e)(C)Ｏ（n２)(Ｄ)O(n３)一棵左右子樹(shù)不空的二叉樹(shù)在先序線索化后，其空指針域數(shù)為(B)。(A)0(B)1(C)2(D)不擬定數(shù)組A[1.．5,1..６]的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先順序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中,則元素A［5,5]的地址為（A）。（Ａ)1140(B）１145(Ｃ)11２０(D)1１25在下列排序算法中,在待排序的數(shù)據(jù)表已經(jīng)為有序時(shí),花費(fèi)時(shí)間反而最多的是(A）。(A)快速排序(B）希爾排序(C)冒泡排序(D)堆排序?qū)τ校?個(gè)元素的有序表做折半查找，則查找A[3］的比較序列的下標(biāo)依次為(D）。（A)１-2-3(B)9-５-2-3(C)9-5-3(D)9－4-2-3下列排序算法中,某一趟結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是（D）。(A）堆排序(Ｂ)冒泡排序(C)快速排序（D)直接插入排序在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后導(dǎo)致了不平衡，設(shè)最低的不平衡點(diǎn)為A,并已知Ａ的左孩子的平衡因子為－1，右孩子的平衡因子為0,則做（Ｂ)型調(diào)整以使其平衡。(A)LL(B)ＬＲ（C)RL(D)RR下列各式中,按增長(zhǎng)率由小至大的順序?qū)Φ呐帕械氖?）。(Ａ),n！,2n，n3/２(B）n3/２,2ｎ,nlogn，2100(C)2ｎ,lｏgｎ,ｎｌogn,ｎ３/２(D)２100，lｏgn，2n,nn若要在單鏈表中的結(jié)點(diǎn)*p之后插入一個(gè)結(jié)點(diǎn)*s,則應(yīng)執(zhí)行的語(yǔ)句是（）。(A)s-＞nｅxt＝p－>ｎexｔ;ｐ－＞ｎexｔ=s;（B)p－>next=s;s－＞nexｔ＝p－>nexｔ(C)p->neｘｔ=ｓ->neｘt;ｓ-＞neｘt=p;（D)s-＞nｅｘt=p;p-＞ｎｅxt=ｓ->next；若要在O（1)的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩個(gè)循環(huán)鏈表頭尾相接,則應(yīng)對(duì)兩個(gè)循環(huán)鏈表各設(shè)立一個(gè)指針，分別指向()。(Ａ)各自的頭結(jié)點(diǎn)(B)各自的尾結(jié)點(diǎn)(C）各自的第一個(gè)元素結(jié)點(diǎn)(D)一個(gè)表的頭結(jié)點(diǎn)，另一個(gè)表的尾結(jié)點(diǎn)棧的兩種常用存儲(chǔ)結(jié)構(gòu)分別為(）。(A）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(B)順序存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)（C）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和索引存儲(chǔ)結(jié)構(gòu)(D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組ｄatａ［21],且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為8和3，則該隊(duì)的當(dāng)前長(zhǎng)度為（）。(A)5(B)6(C)16(Ｄ)17已知在如下定義的鏈串結(jié)點(diǎn)中,每個(gè)字符占1個(gè)字節(jié),指針占4個(gè)字節(jié)，則該鏈串的存儲(chǔ)密度為（)。typedefｓtｒｕctnode{chaｒdate[８];structnｏde＊nexｔ；}LinkStrNoｄｅ;(A）１/4(B)1/2(C）2／3(Ｄ)３／4應(yīng)用簡(jiǎn)樸的匹配算法對(duì)主串ｓ=“BＤBＡBDＡBDAB”與子串ｔ=“BDA”進(jìn)行模式匹配,在匹配成功時(shí),進(jìn)行的字符比較總次數(shù)為（）。(A)7(B）9（C)10(D)1２二維數(shù)組A[2０][1０]采用列優(yōu)先的存儲(chǔ)方法，若每個(gè)元素占2個(gè)存儲(chǔ)單元，且第1個(gè)元素的首地址為２0０,則元素A［8][9]的存儲(chǔ)地址為（)。(Ａ)574（B)576（C)５78(D)58０對(duì)廣義表L＝((a,b），ｃ，ｄ）進(jìn)行操作ｔaｉl(ｈｅad（L）)的結(jié)果是（)。(Ａ）(c，d)(B)（d)(C）b(D)(b）已知一棵樹(shù)的前序序列為AＢＣDEF，后序序列為CEDＦBA,則對(duì)該樹(shù)進(jìn)行層次遍歷得到的序列為()。(A）ＡBＣDEF(Ｂ）ABＣEFD（Ｃ）AＢＦCＤE（D）ABCDＦE一個(gè)含n個(gè)頂點(diǎn)和e條弧的有向圖以鄰接矩陣表達(dá)法為存儲(chǔ)結(jié)構(gòu)，則計(jì)算該有向圖中某個(gè)頂點(diǎn)出度的時(shí)間復(fù)雜度為(）。(Ａ)O（ｎ）(B)O（ｅ）（Ｃ）O(ｎ+e)(D）Ｏ(n2)在關(guān)鍵字序列（12,2３，34，45，5６,67，78，８9,91)中二分查找關(guān)鍵字為４５,89和1２的結(jié)點(diǎn)時(shí)，所需進(jìn)行的比較次數(shù)分別為（）。（A)4,4，3(Ｂ)4，3，3（Ｃ)３,4，4(D)３，3,4下列排序方法中，最佳與最壞時(shí)間復(fù)雜度不相同的排序方法是（）。(A)冒泡排序（B）直接選擇排序（Ｃ)堆排序(D)歸并排序已知含10個(gè)結(jié)點(diǎn)的二叉排序樹(shù)是一棵完全二叉樹(shù),則該二叉排序樹(shù)在等概率情況下查找成功的平均查找長(zhǎng)度等于(）。(A)1.0(B）2．9(C)３.4(D)5．5在下列各種文獻(xiàn)中，不能進(jìn)行順序查找的文獻(xiàn)是()。(Ａ）順序文獻(xiàn)(B)索引文獻(xiàn)(C)散列文獻(xiàn)(D)多重表文獻(xiàn)下面帶有@標(biāo)記的語(yǔ)句的頻度(n>１0）是()。 fｏｒ(inｔi=0;i<n－１；i++) ?fｏr(iｎｔj=ｉ＋1；ｊ<ｎ；ｊ++)??@couｔ<＜i＜<j<＜enｄｌ;(A）n＊(n-1)/2(B)n＊ｎ/2（Ｃ）n＊（n+1)/2（D)不擬定已知使用順序表存儲(chǔ)數(shù)據(jù),表長(zhǎng)為n，假設(shè)在表中的任意位置插入元素的概率相等，則插入一個(gè)元素，平均需要移動(dòng)的元素個(gè)數(shù)（）。(A)(n-1)/2（B）ｎ/２（C)（n+1)/2(D)不擬定在雙向鏈表p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是()。(A）prｉght＝ｓ;sｌefｔ=p;pｒighｔleｆt=s；sriｇｈｔ=pｒｉghｔ；(B）prigｈt＝s;ｐrightlefｔ＝s；slｅft＝p;sright=prｉｇht;(Ｃ)sleft=ｐ；srighｔ=prigｈt;pｒiｇｈｔ=ｓ;ｐｒiｇhｔleｆt＝s;(D)ｓleｆt=p;srｉghｔ=ｐrighｔ;prightｌｅft=s;ｐｒiｇhｔ＝ｓ；字符串相等的充足必要條件是()。(A）串長(zhǎng)度相等(B)串使用相同的存儲(chǔ)結(jié)構(gòu)(C)串相同位置相應(yīng)的字符相等(D)A和C將一個(gè)遞歸算法改為相應(yīng)的非遞歸算法時(shí),通常需要使用(）。(A)數(shù)組?(B）棧?(C）隊(duì)列 (Ｄ)二叉樹(shù)一個(gè)棧的入棧序列1,2，３，4，5,則棧的不也許的輸出序列是（)。(Ａ)１2345(B)５４321（C)３2５1４（D)123５４設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1～n，其頭尾指針?lè)謩e為f和r,則其元素個(gè)數(shù)為（)。(A)ｒ-f(Ｂ)r-ｆ+１(C)(ｒ－f）ｍｏdn+1(D)(ｒ－f+n)moｄn某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是AＢDEFCGＨ,中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是ＤBFEＡGHC，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是（)。（A）DFEBHCＧA(Ｂ)DFEBHGCA(C)ＤEFBＨGCA(Ｄ）DFＥHＢGCA正則二叉樹(shù)是只有度為０和2的結(jié)點(diǎn)的二叉樹(shù)，已知正則二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)為ｎ,則該二叉樹(shù)總得結(jié)點(diǎn)數(shù)為(）。(A)n+1（B)2*n（C)２＊n+1（D)2＊n-1下面關(guān)于排序的說(shuō)法錯(cuò)誤的是（)。（A)快速排序、歸并排序都是一種不穩(wěn)定的排序方法(B）直接插入排序和折半插入排序移動(dòng)元素的次數(shù)相同（C)簡(jiǎn)樸選擇排序移動(dòng)元素的次數(shù)最少(D)根據(jù)排序需要的平均時(shí)間,快速排序是目前最佳的一種內(nèi)部排序方法折半查找有序表(3,4,５，10,13，１４，２0，30),若查找元素3，則被比較的元素依次為(）。(A）1０,20，30(B）1０,１4，30（Ｃ)13,3(D)1０,4,3下面關(guān)于棧和隊(duì)列的說(shuō)法對(duì)的的是()。(Ａ）棧是先進(jìn)先出的線性表,隊(duì)列是后進(jìn)先出的線性表(B）棧是先進(jìn)先出的線性表，隊(duì)列也是先進(jìn)先出的線性表(C)棧是后進(jìn)先出的線性表,隊(duì)列是先進(jìn)先出的線性表(D)棧是后進(jìn)先出的線性表,隊(duì)列也是后進(jìn)先出的線性表兩個(gè)各有n個(gè)元素的有序列表并成一個(gè)有序表，其最少的比較次數(shù)是()。

(A)n(Ｂ)2n-1（Ｃ）2n(D)n－1設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是0~n-１,f表達(dá)隊(duì)首元素的前驅(qū)位置,r表達(dá)隊(duì)尾元素的位置，則隊(duì)列中元素個(gè)數(shù)為(）。

（A)r-f(B)r-f1(C)(r-ｆ１)modn(D)（ｒ-ｆｎ)modn一個(gè)5行6列的二維數(shù)組ｓ采用從最后一行開(kāi)始，每一行的元素從右至左的方式映射到一維數(shù)組a中，s和ａ的下標(biāo)均從0開(kāi)始,則ｓ[3][3]在ａ中的下標(biāo)是()。?(A)7(B)8（C)9(D)１０設(shè)只含根結(jié)點(diǎn)的二叉樹(shù)的高度為1,則高度為n的二叉樹(shù)中所含葉子結(jié)點(diǎn)的個(gè)數(shù)最多為（）個(gè)。?(A)2n(B)ｎ(C)2ｎ-1(Ｄ)２n－1設(shè)高度為h的二叉樹(shù)上只有度為０和度為2的結(jié)點(diǎn),則此二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為（）個(gè)（設(shè)只含根結(jié)點(diǎn)的二叉樹(shù)的高度為1）。

（A）2ｈ(B)2h－1(C）2h+1(D）h+1對(duì)一棵二叉檢索樹(shù)進(jìn)行（）得到的結(jié)點(diǎn)序列是一個(gè)有序序列。?（Ａ）前序環(huán)游(B)中序環(huán)游(Ｃ)后序環(huán)游（D)層次環(huán)游一棵前序序列為1,２，3,4的二叉樹(shù)，其中序序列不也許是(）。

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

(A)e(B)2e(C)ｎ2-e(D)n2-2ｅ具有ｎ個(gè)頂點(diǎn)和e條邊的圖的深度優(yōu)先搜索算法的時(shí)間復(fù)雜度為(）。(A)Ｏ(ｎ)（B）Ｏ(n３)(C)Ｏ(ｎ2)(D)O(ne)假如具有n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有()棵生成樹(shù)。?(A)n(B)nl(Ｃ)n-l(D)2n堆排序算法在平均情況下的時(shí)間復(fù)雜度為(）。（A)Ｏ(n)(B)O（nlogn）(C)O(n2)(D)O（logｎ)在待排序數(shù)據(jù)已基本有序的前提下，下述排序方法中效率最高的是（）。（A)直接插入排序（B）直接選擇排序(C)快速排序（Ｄ)歸并排序在抱負(fù)情況下，散列表中查找元素所需的比較次數(shù)為(）。?(A)n(B)O(Ｃ)n/2(D)1在一棵m階Ｂ樹(shù)中,若在某結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂,則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是(）。?（A)m(B)m+1（C）m－ｌ（Ｄ)m/2設(shè)順序循環(huán)隊(duì)列Q[０：Ｍ－1]的頭指針和尾指針?lè)謩e為Ｆ和R，頭指針F總是指向隊(duì)頭元素的前一位置,尾指針R總是指向隊(duì)尾元素的當(dāng)前位置,則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為(C）。 （A）R-F (B）F－R (C)（R-F＋M）%Ｍ?（D)(Ｆ-R+M)%Ｍ設(shè)某棵二叉樹(shù)的中序遍歷序列為AＢCD,前序遍歷序列為CABD，則后序遍歷該二叉樹(shù)得到序列為（A)。 (A)BＡＤC?(Ｂ)BCDＡ?(C)ＣDAB?(D)CＢDＡ設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn),則該完全無(wú)向圖中有(A）條邊。?（Ａ）n(n-1)/2?(Ｂ)n(n-1)?(C)ｎ2 (D）n２-1設(shè)某棵二叉樹(shù)中有202３個(gè)結(jié)點(diǎn),則該二叉樹(shù)的最小高度為（Ｃ)。?（A)９ （B)１0 (Ｃ)1１?(D)1２設(shè)某有向圖中有n個(gè)頂點(diǎn),則該有向圖相應(yīng)的鄰接表中有（B）個(gè)表頭結(jié)點(diǎn)。 （A)n-１ (B)n (C)ｎ＋１?(D）2n-1設(shè)一組初始記錄關(guān)鍵字序列(５，2，6,3,8）,以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（C)。 (A)2，3,5,8,6 ?(B)3,2，5，８,６ (C)3,2,5,６,８ ?（Ｄ)2,3，6,5,8設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表達(dá)為A=(D，R），D={０1,0２,03,04,05，06,07,０８,０9}，R={r}，r={<01，０2>，＜01,03>，<０１,０4＞，<0２,05>，<02，０6>，<03，07>,<03，0８>，＜03，０9＞｝,則數(shù)據(jù)結(jié)構(gòu)A是(Ｂ）。 （A）線性結(jié)構(gòu) （B)樹(shù)型結(jié)構(gòu) (Ｃ）物理結(jié)構(gòu)?(Ｄ)圖型結(jié)構(gòu)下面程序的時(shí)間復(fù)雜為(B)for(i=１,s＝0；i<=ｎ;i++）｛t＝１;foｒ(j＝１;j<=i；j＋＋)t=t＊j;ｓ=ｓ+t；}?(A)Ｏ(n)?（B)Ｏ(n２) （C）O(ｎ３) ?(D）O(n4）設(shè)指針變量ｐ指向單鏈表中結(jié)點(diǎn)Ａ，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為(A)。?(Ａ)q=p-＞next;p－＞data=q->dａｔa；ｐ-＞nｅxt=q->nｅｘt；free(q);(B)q=p->next；q－>ｄata=ｐ－>data；ｐ->next=q->ｎｅxt;free（q)； (C）ｑ＝p->nｅｘt；p->next＝q->next；freｅ(q)； (D)q=p-＞ｎeｘｔ；p-＞data=q－＞data;ｆree（q）;設(shè)有n個(gè)待排序的記錄關(guān)鍵字,則在堆排序中需要（A)個(gè)輔助記錄單元。 (Ａ)1?（B)n?(C)nlog2n?(D)ｎ2設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為（2０,1５,14，18，21，36，4０，１0),則以2０為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為（A）。（Ａ)10，15，14，18,20，３6,４0,２1?(Ｂ)10，1５，14，1８,20，40，36，21?(Ｃ)1０,１5,１４，20,18,4０,３6，2l （D)15，1０，１4,18，20,３6,４0，２1設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn),則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為（B）。 (A）O(１）?(B）Ｏ(loｇ2n) (C)loｇ2ｎ?(D）O（ｎ2)設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊,則其相應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為(D）。 (A）n，e?(B)e，n?(C）2n，e?(D）n,2e設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn),則該強(qiáng)連通圖中至少有（C）條邊。 (A)ｎ(n-1)?(B)ｎ+1?（C)ｎ (D)n（n+1)設(shè)有5０00個(gè)待排序的記錄關(guān)鍵字，假如需要用最快的方法選出其中最小的１0個(gè)記錄關(guān)鍵字,則用下列（B)方法可以達(dá)成此目的。?(Ａ)快速排序?(Ｂ）堆排序 （C)歸并排序 (Ｄ)插入排序下列四種排序中（D)的空間復(fù)雜度最大。 (A)插入排序 （Ｂ)冒泡排序 (Ｃ）堆排序 (Ｄ)歸并排序設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第ｉ個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（C)。 (A)O(ｎ）?(B)O（ｎloｇ2n)?(C)O（1)?(D)O(n２)設(shè)一棵二叉樹(shù)的深度為ｋ,則該二叉樹(shù)中最多有（D）個(gè)結(jié)點(diǎn)。 (Ａ)２k-１ (B）２k?（Ｃ)2ｋ-１?(D)２k－１設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊,則該無(wú)向圖中所有頂點(diǎn)的入度之和為(D)。?(A)n?(B）ｅ?(C)2ｎ (D)2e在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（B)。 （Ａ)O(1)?（B)O(ｎ) (Ｃ)O(loｇ2n)?(Ｄ）O(n2)設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（C)條有向邊。?(Ａ）n （Ｂ）ｎ-1?(C)m （D)m-1設(shè)一組初始記錄關(guān)鍵字序列為(3４5,２5３，674，924,６２７),則用基數(shù)排序需要進(jìn)行（A）趟的分派和回收才干使得初始關(guān)鍵字序列變成有序序列。?（A)3?(B)4 (C)5 （D)８設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作（B)。 (A)必須判別棧是否為滿?（B）必須判別棧是否為空 (C)判別棧元素的類(lèi)型?(D）對(duì)棧不作任何判別下列四種排序中(A）的空間復(fù)雜度最大。?（A）快速排序 (B）冒泡排序?(C）希爾排序 (D）堆設(shè)某二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為Ｎ０,度數(shù)為1的結(jié)點(diǎn)數(shù)為Nｌ,度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（C)。?(A)N0=N1+1?（B)Ｎ0=Ｎl+Ｎ２?(C）N0=N2+1?(D)N0=２Ｎ１＋l設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素,則運(yùn)用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過(guò)(Ａ）。?(A)loｇ2ｎ+1 (B）ｌog2n－1?(C)lｏg2n?(D)ｌoｇ2(n＋1）數(shù)據(jù)的最小單位是(A)。?（Ａ)數(shù)據(jù)項(xiàng) （Ｂ）數(shù)據(jù)類(lèi)型 （C)數(shù)據(jù)元素 (D)數(shù)據(jù)變量設(shè)一組初始記錄關(guān)鍵字序列為（50，4０，95，２０,１5,７0，6０，４5)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（B)。 (Ａ)4０，5０,2０,95 (B)15,40，60，20 （C）15，２０，４0,４5?(D)45，40，1５,20設(shè)一組初始記錄關(guān)鍵字序列為(2５，５0,15，35，80,８５，20,４０，36，70）,其中具有5個(gè)長(zhǎng)度為2的有序子表，則用歸并排序的方法對(duì)該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（A)。（Ａ)15，２５,35,５0，2０,40，８0,8５,36,70(Ｂ)１5，25，3５，５0，80，20，8５，４0，70，3６（C)15，25，35,５0,８0，８5,２0，36，４0，7０(D)15,25,35,50，80，２０，36，40,7０,85設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)規(guī)定插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序,則該操作的時(shí)間復(fù)雜度為(Ｄ)。?(A)O(ｌoｇ2n）?(B)O(1)?(C)O(n２) (D)O（ｎ）設(shè)一棵m叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0,度數(shù)為1的結(jié)點(diǎn)數(shù)為Nｌ,……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm,則Ｎ0=（B)。（Ａ)Nl＋N2+……+Nｍ(B)l＋Ｎ2+2N3+3N4+……+(m-１）Nｍ(Ｃ)Ｎ2+２N3+３N4＋……+（m-1)Nm（D)2Nl+3N2+……＋(m＋1)Nm設(shè)有序表中有1０00個(gè)元素，則用二分查找查找元素X最多需要比較（B）次。 (A)2５ (B)10?(C)７? (D)1設(shè)連通圖G中的邊集E={（a，b),(a,e）,(a，ｃ)，(b，e),(e,d）,(d，f),(f,ｃ)｝,則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為(Ｂ）。?(A)abeｄfc?(B)acfebd?(C)ａebdfc (Ｄ)aeｄfcｂ設(shè)輸入序列是1、2、3、……、n,通過(guò)棧的作用后輸出序列的第一個(gè)元素是n,則輸出序列中第i個(gè)輸出元素是(C)。 (A)n-i?(Ｂ）ｎ－１－i?(C)n+1-i ?（D)不能擬定設(shè)一組初始記錄關(guān)鍵字序列為（45，8０，55,40,42,85),則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（C）。 (Ａ）40,42,４5，5５，80,83 (B)4２,4０,45，80,8５,8８ （C)42，40,45，55,80,85 （Ｄ)４２，４0，4５,85，５５,8０設(shè)一組權(quán)值集合W＝{2,3，4,5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹(shù)中帶權(quán)途徑長(zhǎng)度之和為(D)。 （A)20?（B）30?(Ｃ)40 (D)４5執(zhí)行一趟快速排序可以得到的序列是(A）。?(A)[４1,12,3４，4５,27]５5[７２,63］?(B)[45,34,12,４1]55［72,63，2７] （C）［６3，1２,34，45，27]55[41，72]?（Ｄ)[１2,2７,45，41]55[３4，63,7２]設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn),則其判空條件是(A）。(A）heａd==0? （B)heaｄ->neｘt==0(C）hｅad->nｅxt=＝heaｄ （Ｄ)ｈｅad!＝0時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為Ｏ(nｌｏg２n)的是(A)。 (A)堆排序?(B）冒泡排序 (Ｃ)希爾排序?（D）快速排序設(shè)二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反,則該二叉樹(shù)滿足的條件是（D)。 （A）空或只有一個(gè)結(jié)點(diǎn) （B）高度等于其結(jié)點(diǎn)數(shù) （C）任一結(jié)點(diǎn)無(wú)左孩子 (D)任一結(jié)點(diǎn)無(wú)右孩子一趟排序結(jié)束后不一定可以選出一個(gè)元素放在其最終位置上的是（D)。?(A)堆排序?(Ｂ)冒泡排序?(C)快速排序 (Ｄ)希爾排序設(shè)某棵三叉樹(shù)中有40個(gè)結(jié)點(diǎn)，則該三叉樹(shù)的最小高度為（B）。 (Ａ）3 (Ｂ)４?(C)5 (Ｄ)６順序查找不管在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為(Ａ)。?(A）Ｏ(n) (B)Ｏ（n2）?(C)Ｏ(ｎ1/2) (D)Ｏ(1og2n)二路歸并排序的時(shí)間復(fù)雜度為(C）。?(A)O(n) （B）Ｏ(ｎ2)?(C）O(nlog2n） (D)O(log2n)深度為k的完全二叉樹(shù)中最少有（B）個(gè)結(jié)點(diǎn)。?(A)2ｋ-1-1 (B）2k-1?(Ｃ）２k-1+１?(D）２k-1設(shè)指針變量froｎt表達(dá)鏈?zhǔn)疥?duì)列的隊(duì)頭指針,指針變量rｅaｒ表達(dá)鏈?zhǔn)疥?duì)列的隊(duì)尾指針,指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（Ｃ)。 (A）fｒonｔ->neｘt=s；ｆront=s;?(B)s->nexｔ=rear；rear=s； （C)rear－＞nｅxｔ＝s；ｒear=ｓ;?(Ｄ)s->nｅxt=ｆｒｏnt;fronｔ=s；設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為(A）。 (Ａ)O(n+e) (B)O(n2) (C)Ｏ（ｎe)?（D)Ｏ(n3)設(shè)某哈夫曼樹(shù)中有199個(gè)結(jié)點(diǎn),則該哈夫曼樹(shù)中有(B）個(gè)葉子結(jié)點(diǎn)。 (A)９9 （B)10０?(C)101 (Ｄ）102設(shè)二叉排序樹(shù)上有ｎ個(gè)結(jié)點(diǎn),則在二叉排序樹(shù)上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為(D)。 （A）O(n) (B)O(n2） （C)Ｏ(ｎloｇ2n)?(Ｄ)O（log2n)設(shè)用鄰接矩陣A表達(dá)有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（Ｂ)。?(Ａ)第i行非0元素的個(gè)數(shù)之和?(B)第ｉ列非0元素的個(gè)數(shù)之和?(C)第i行0元素的個(gè)數(shù)之和?(D)第ｉ列0元素的個(gè)數(shù)之和設(shè)某無(wú)向圖有n個(gè)頂點(diǎn),則該無(wú)向圖的鄰接表中有(B）個(gè)表頭結(jié)點(diǎn)。?(A)２n (B)n?(Ｃ)n／2?（Ｄ）ｎ(n-1）設(shè)無(wú)向圖G中有ｎ個(gè)頂點(diǎn)，則該無(wú)向圖的最小生成樹(shù)上有（B)條邊。 （A）ｎ (Ｂ)n-1?(C)2n?(Ｄ)２ｎ-1設(shè)一組初始記錄關(guān)鍵字序列為(６０，80，55,40，42，85），則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是(C)。?(A)40,42，６０,5５，８0，85 (B)4２，4５，55，60,85，80 (C)42，4０,55,６0，8０,８5?(D)42,40,60，８5，５5,80(Ｂ）二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。?(A)先序遍歷?(B)中序遍歷?（Ｃ）后序遍歷 (D）層次遍歷設(shè)按照從上到下、從左到右的順序從1開(kāi)始對(duì)完全二叉樹(shù)進(jìn)行順序編號(hào)，則編號(hào)為ｉ結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為(B）。?(A)2i＋1 (B）2i （C)i／2?(Ｄ)2i-1程序段s＝ｉ=0;dｏ｛i＝i+１;s＝ｓ＋ｉ;｝wｈilｅ(i<=n);的時(shí)間復(fù)雜度為(A)。?（A）O(n） (Ｂ)O(ｎlog2ｎ) (C)O(n2)?(D）O(ｎ3/2）設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（C）。?(A)head＝=0 (Ｂ)head->next==0?(C)head->ｎeｘt==ｈeａd?(D)ｈead！=０設(shè)某棵二叉樹(shù)的高度為１0，則該二叉樹(shù)上葉子結(jié)點(diǎn)最多有(C)。?(A)2０?(B)256?（C)5１２?（Ｄ)1０２4設(shè)一組初始記錄關(guān)鍵字序列為(13,１8,24,3５,47，50，6２,８3，9０,115,１34),則運(yùn)用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（Ｂ）。?(Ａ)1?(B)2?(Ｃ)3 (D)4設(shè)指針變量ｔop指向當(dāng)前鏈?zhǔn)綏５臈ｍ?則刪除棧頂元素的操作序列為（D)。 (Ａ)top＝toｐ+1； (B)tｏp=ｔｏp-1;?(Ｃ）ｔoｐ->next=tｏｐ；?（D)ｔｏp＝tｏp->next;建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為（C) (A)O（ｎ) （B）O(１)?（C)O（n2)?(D)Ｏ(ｌoｇ2n)設(shè)某散列表的長(zhǎng)度為1０0，散列函數(shù)H(k)＝k%P，則P通常情況下最佳選擇(B)。 (A)99 (B)97 （Ｃ）９１ (D）９3在二叉排序樹(shù)中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（Ｂ）。 （Ａ)O（n） (B)Ｏ（log２ｎ） （C)O(log2n) (D）O（n2)設(shè)一個(gè)順序有序表A［1：14］中有1４個(gè)元素,則采用二分法查找元素A[4]的過(guò)程中比較元素的順序?yàn)?C)。 （A)A[1],Ａ[２]，A[3]，A[４]?（B)A[1］,Ａ[1４］，Ａ［7]，A[4］ （C)A［7]，Ａ[３],A［5]，Ａ［４]?(D)Ａ[7］，A[5],Ａ[３]，Ａ[4]設(shè)一棵完全二叉樹(shù)中有６5個(gè)結(jié)點(diǎn),則該完全二叉樹(shù)的深度為（Ｂ）。 (A)８?(B）7 (C)６ (D)5設(shè)一棵三叉樹(shù)中有2個(gè)度數(shù)為1的結(jié)點(diǎn),２個(gè)度數(shù)為2的結(jié)點(diǎn),2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有(C）個(gè)度數(shù)為0的結(jié)點(diǎn)。?(A)5 (B)６ (Ｃ)７ (D）8設(shè)無(wú)向圖Ｇ中的邊的集合E={(a，ｂ）,（a,e）,(a,c)，(b,ｅ）,（e,d),(d，f)，(ｆ,ｃ）},則從頂點(diǎn)ａ出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（Ａ)。?(Ａ）ａedｆcb （B)acfebｄ (C)aeｂcｆd?(Ｄ)aｅdfbc下列程序段的時(shí)間復(fù)雜度為(A）。for(i=0；i<m;i++)fｏr(j=0；j<t；ｊ++）c[i][j]=0;for（i=０;i<m；i++)for(ｊ=0;ｊ＜t；ｊ+＋）for(k=0;k<n;k++)c[i][ｊ]=c[i][j]+a[ｉ］[k]*ｂ[k][j］;?(A)O(m＊n*t)?(B)O(m+n+t)?（Ｃ)O（m+n*t） (D)O（m*ｔ+n)設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)（A）個(gè)元素。 (A）n－i (Ｂ)ｎ+ｌ-i?(C）n-1-i?(D)i設(shè)Ｆ是由T1、T２和Ｔ3三棵樹(shù)組成的森林,與F相應(yīng)的二叉樹(shù)為B,Ｔ１、T2和T3的結(jié)點(diǎn)數(shù)分別為Ｎ1、N2和N3,則二叉樹(shù)B的根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)數(shù)為（A)。（A）N1－１?（B)N2-1（C)N２+N3?(D)Ｎ1+Ｎ3運(yùn)用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（C)。（A）Ｏ（ｎ） （B)O（nlog2n）?(C）O(ｎ2) （D)O(log２ｎ）設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為(D）。 （A)p->ｒight=s;s->left=ｐ；p->riｇht->left=s；s->rigｈｔ＝p->ｒiｇht;?（B)s->ｌeｆt=ｐ;s－>righｔ＝p-＞right；p->rigｈt=ｓ；p-＞ｒighｔ->leｆt=s; (C)p－>righｔ＝s;p－＞rｉghｔ->ｌeft=s;s－>ｌeft＝ｐ;s->ｒight=p－>riｇhｔ；?（Ｄ)s－>ｌeft=p;s-＞righｔ=p->riｇht；p-＞ｒight->left=s；p->riｇhｔ＝s;下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（D)。?(Ａ)快速排序 （B)堆排序 (C)歸并排序 （Ｄ）冒泡排序設(shè)輸入序列1、2、3、…、n通過(guò)棧作用后，輸出序列中的第一個(gè)元素是n，則輸出序列中的第i個(gè)輸出元素是（C)。?(A)n-i (B)n-1-i?(C）n+l-i?(D)不能擬定設(shè)散列表中有m個(gè)存儲(chǔ)單元,散列函數(shù)H（ｋey)=keｙ％p,則p最佳選擇(Ｂ）。?(A）小于等于m的最大奇數(shù) (B)小于等于m的最大素?cái)?shù) （C)小于等于ｍ的最大偶數(shù)?(D)小于等于m的最大合數(shù)設(shè)在一棵度數(shù)為3的樹(shù)中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為１的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（C）個(gè)。?(A)4?(B)5?(C)６?(Ｄ)7設(shè)完全無(wú)向圖中有ｎ個(gè)頂點(diǎn),則該完全無(wú)向圖中有(A)條邊。(A)ｎ(n-1）/2?(B）n（n-1) (C）n(ｎ+１)／2?(D）(n－１)/２設(shè)順序表的長(zhǎng)度為ｎ,則順序查找的平均比較次數(shù)為（C）。 (Ａ)n (B）n/2 (C)(n+１)/2?（D)(ｎ－1)／2設(shè)有序表中的元素為（1３，18，2４,3５，47,5０,62),則在其中運(yùn)用二分法查找值為2４的元素需要通過(guò)(C）次比較。 (A)1?(B）２?(C)３?(Ｄ)4設(shè)順序線性表的長(zhǎng)度為30，提成5塊,每塊６個(gè)元素,假如采用分塊查找,則其平均查找長(zhǎng)度為（D)。 （A)６?(B)11?(C）5?（D）6.5設(shè)有向無(wú)環(huán)圖G中的有向邊集合E={<1，2＞,<2，3>，<3，4>,＜１,4>},則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖?A）。 (Ａ)1，2，3，4?（B）2，3，4,１?（C)1,４，2，3 (D)1,2,4,3設(shè)有一組初始記錄關(guān)鍵字序列為(３4,76,45,1８,26,54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹(shù)的深度為（A）。 (Ａ)4 (Ｂ)5 (C)6 （D)7下列程序段的時(shí)間復(fù)雜度為（A）。i＝0,s=0;whiｌｅ(s<n){s＝s＋i;i+＋；} (A)O（n1/2） (B）O(n1/3）?(C）O(ｎ) (D）O(ｎ2)設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（Ｄ)存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 （A)單向鏈表 ?(B)單向循環(huán)鏈表(C)雙向鏈表??(D）雙向循環(huán)鏈表設(shè)指針ｑ指向單鏈表中結(jié)點(diǎn)Ａ,指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B,指針s指向被插入的結(jié)點(diǎn)Ｘ,則在結(jié)點(diǎn)A和結(jié)點(diǎn)Ｂ插入結(jié)點(diǎn)X的操作序列為(B）。(A)s－>ｎｅxt=p->ｎｅxt；p->ｎeｘt=-s; (B)q-＞neｘｔ=s；ｓ->nｅxt=p；(C)p->next=s-＞next;s->next=p； (D)ｐ->nexｔ=s;s-＞ｎｅｘｔ=q；設(shè)輸入序列為1、2、3、4、５、6，則通過(guò)棧的作用后可以得到的輸出序列為（Ｂ)。(A)5,3,4，6,１,2?(Ｂ)３，2，5，6，４，１（C)3，１,2,５,４，６ (D)1，5,4，6，2，３設(shè)有一個(gè)10階的下三角矩陣A（涉及對(duì)角線),按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的５5個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占１個(gè)字節(jié)的存儲(chǔ)空間,則A[5]［４]地址與A［０]［0]的地址之差為（B)。 (Ａ)10 （B）1９ （C）28?(D)55設(shè)一棵ｍ叉樹(shù)中有N１個(gè)度數(shù)為1的結(jié)點(diǎn),N2個(gè)度數(shù)為2的結(jié)點(diǎn)，……，Nm個(gè)度數(shù)為m的結(jié)點(diǎn),則該樹(shù)中共有(D）個(gè)葉子結(jié)點(diǎn)。 （A) (Ｂ） （C)?(D)二叉排序樹(shù)中左子樹(shù)上所有結(jié)點(diǎn)的值均（A)根結(jié)點(diǎn)的值。 (A)＜ （B)> (C)=?(D）!＝設(shè)一組權(quán)值集合W＝(１５,3,14，2，６，9，1６,17)，規(guī)定根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹(shù),則這棵哈夫曼樹(shù)的帶權(quán)途徑長(zhǎng)度為(D)。 (A)129?(B）2１9?(Ｃ）18９?(Ｄ)229設(shè)有n個(gè)關(guān)鍵字具有相同的Ｈash函數(shù)值,則用線性探測(cè)法把這n個(gè)關(guān)鍵字映射到HＡSH表中需要做（D)次線性探測(cè)。?(A）n２ (Ｂ)ｎ(n+1) （C）n(n+1）/２?（D)ｎ(ｎ-1）/2設(shè)某棵二叉樹(shù)中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n,則這棵二叉中共有（C)個(gè)結(jié)點(diǎn)。 (A)2n (B)n+l (C)2n-1?(D)2ｎ+l設(shè)一組初始記錄關(guān)鍵字的長(zhǎng)度為8,則最多通過(guò)(B)趟插入排序可以得到有序序列。?(A)６?(B)7 (C）8?（D)９設(shè)一組初始記錄關(guān)鍵字序列為（Ｑ,H,Ｃ，Ｙ,Ｐ，A，M,S，Ｒ,D,F,X),則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（Ｄ）。(A)F，H，C,Ｄ,P,Ａ，M,Q，R,S，Y，Ｘ（B)P,A，Ｃ，S,Ｑ,D,F，X,R，H，M，Y(C)A，D,C，R，F(xiàn),Ｑ,M,S,Y，P，Ｈ,X(D)Ｈ,C，Q，Ｐ，A,Ｍ，S,R，D,Ｆ，X,Y設(shè)有一個(gè)二維數(shù)組A[m]［n］，假設(shè)A［0]［０]存放位置在6４4(10)，A[2][2]存放位置在６76（１0)，每個(gè)元素占一個(gè)空間，問(wèn)A[3]［3]（10）存放在什么位置？腳注(10）表達(dá)用1０進(jìn)制表達(dá)。(C)(A）６8８（Ｂ）678(C)692(D)6９6若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A［3］的比較序列的下標(biāo)依次為（D）。（A)1,2,3 ? (B)9，５，2,３(C）9，5，3? ? （D）9,4,2，３對(duì)n個(gè)記錄的文獻(xiàn)進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大體為（C)。(A)O(1）(Ｂ)O(n)(C)O（1ｏg2n)(D)Ｏ（ｎ2)對(duì)于線性表(7,34，５5,2５,64,4６,20，10)進(jìn)行散列存儲(chǔ)時(shí),若選用H(K)＝K%9作為散列函數(shù)，則散列地址為1的元素有（Ｄ)個(gè)。(A）1(B）２(Ｃ)3（D)4設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖,該圖至少應(yīng)有(A)條邊才干保證是一個(gè)連通圖。(A)5（B)6（C)７(D）8設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為ｍ，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有（B）個(gè)空指針域。?(A)２m－1?（B)2m?(C)2m+１ （Ｄ)4m二、判斷題數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。（）鏈表的每個(gè)結(jié)點(diǎn)都恰好有一個(gè)指針。（）同一組不反復(fù)輸入序列執(zhí)行不同的入棧出棧組合操作,所得結(jié)果也也許相同。()改善的ＫMP算法中，字符串”abaaabａ”的nextｖａl數(shù)組值是０101110。（)用六叉鏈表表達(dá)30個(gè)結(jié)點(diǎn)的六叉樹(shù),則樹(shù)中共有１51個(gè)空指針。()數(shù)組是一種線性結(jié)構(gòu)，因此只能用來(lái)存儲(chǔ)線性表。（)若有向圖不存在回路,即使不用訪問(wèn)標(biāo)志位同一結(jié)點(diǎn)也不會(huì)被訪問(wèn)兩次。（)若裝填因子a為１，則向散列表中散列元素時(shí)一定會(huì)產(chǎn)生沖突。()若把堆當(dāng)作是一個(gè)完全二叉樹(shù),則該樹(shù)一定是一棵排序二叉樹(shù)。()外排中使用置換選擇排序的目的，是為了增長(zhǎng)初始?xì)w并段的長(zhǎng)度。（)抽象數(shù)據(jù)類(lèi)型與計(jì)算機(jī)內(nèi)部表達(dá)和實(shí)現(xiàn)無(wú)關(guān)。(Ｙ）線性表的插入和刪除總是隨著著大量數(shù)據(jù)的移動(dòng)。（N)隊(duì)列在程序調(diào)用是必不可少,因此遞歸離不開(kāi)隊(duì)列。(N)字符串’aaｂabaaaｂa’的改善函數(shù)nextval數(shù)組值是。(Y）二叉樹(shù)中有雙子女的父結(jié)點(diǎn),在中序遍歷中后繼一定是其中一個(gè)子女結(jié)點(diǎn)。（N)不用遞歸就不能實(shí)現(xiàn)二叉樹(shù)的前序遍歷。(N）若有向圖有n個(gè)頂點(diǎn),則其強(qiáng)連通分量最多有n個(gè)。（Ｙ)平衡二叉樹(shù)一定是一棵完全二叉樹(shù)。(Ｎ)若某內(nèi)部排序算法不穩(wěn)定,則該算法沒(méi)有使用價(jià)值。(N)倒排文獻(xiàn)的目的是為了多關(guān)鍵字查找。(Y)已知指針curr指向鏈表中的某結(jié)點(diǎn),執(zhí)行語(yǔ)句cｕrr=cuｒr->nexｔ；不會(huì)刪除該鏈表中的結(jié)點(diǎn)。(）若二叉樹(shù)的葉結(jié)點(diǎn)數(shù)為1,則其高度等于結(jié)點(diǎn)數(shù)(僅含根結(jié)點(diǎn)的二叉樹(shù)高度為1)。（)按中序環(huán)游二叉樹(shù)時(shí)，某個(gè)結(jié)點(diǎn)的直接后繼是它的右子樹(shù)中第一個(gè)被訪問(wèn)的結(jié)點(diǎn)。（)完全二叉樹(shù)的某結(jié)點(diǎn)若無(wú)左孩子，則它必是葉結(jié)點(diǎn)。(）向二叉檢索樹(shù)中插入一個(gè)新結(jié)點(diǎn),需要比較的次數(shù)不也許大于此二叉樹(shù)的高度。（)對(duì)一個(gè)堆按層次環(huán)游,一定能得到一個(gè)有序序列。()一棵樹(shù)中的葉子結(jié)點(diǎn)數(shù)一定等于其相應(yīng)的二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)。（)將一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)表達(dá)后,該二叉樹(shù)的根結(jié)點(diǎn)沒(méi)有右子樹(shù)。(）任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)湫蛄?，并且拓?fù)湫蛄胁晃ㄒ?。?快速排序在最差情況下的時(shí)間復(fù)雜度是0(ｎ2)，此時(shí)它的性能并不比冒泡排序更好。()AVL樹(shù)的任何子樹(shù)都是AＶL樹(shù)。（Y）用相鄰矩陣表達(dá)圖所用的存儲(chǔ)空間大小與圖的邊數(shù)成正比。（N)霍夫曼樹(shù)一定是滿二叉樹(shù)。(Y）棧是一種線性結(jié)構(gòu)。（Y）B＋樹(shù)既適于隨機(jī)檢索，也適于順序檢索。（N)記