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

1、第1頁共101頁數(shù)據(jù)結(jié)構(gòu)試題庫一、單項(xiàng)選擇題1下列程序段所代表的算法的時(shí)間復(fù)雜度為（D）。x=ny=0while(x=(y1)(y1))y(A)O(n)(B)O(n2)(C)O(log2n)(D)O()n2在一個(gè)長度為n的以順序結(jié)構(gòu)存儲(chǔ)的線性表中，假設(shè)在線性表的任何位置刪除元素的概率相等，則刪除一個(gè)元素時(shí)線性表所需移動(dòng)元素的平均次數(shù)為（B）。(A)n2(B)(n1)2(C)(n1)2(D)n23在一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s結(jié)點(diǎn)

2、時(shí)，應(yīng)執(zhí)行執(zhí)行操作為（C）。(A)HSnext=s(B)snext=HSnextHSnext=s(C)snext=HSHS=s(D)snext=HSHS=HSnext4假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列Q，并且隊(duì)列只設(shè)一個(gè)頭指針front，不設(shè)隊(duì)列尾指針。若要進(jìn)隊(duì)一個(gè)元素s，則在下列程序算法的空白處應(yīng)添加的操作語句是（A）。voidAddQueue(structlinkqueueQ)p=Qfrontwhile(pnext!=Qfront)

3、p=pnext(A)pnext=ssnext=Qfront(B)Qfrontnext=sQfront=s(C)snext=ppnext=Qfront(D)Qfrontnext=ssnext=p5設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（B）。第3頁共101頁11下列程序段所代表的算法的時(shí)間復(fù)雜度為（C）。y=nx=1while(xnext==NULL(C)headnext==head(D)head

4、!=NULL15若鏈隊(duì)列HQ中只有一個(gè)結(jié)點(diǎn)，則隊(duì)列的頭指針和尾指針滿足下列條件（D）。(A)HQrearnext==HQfront(B)HQfrontnext==HQrearnext(C)HQfront==HQrear(D)HQfrontnext==HQrear16從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除結(jié)點(diǎn)的值，則應(yīng)執(zhí)行操作為（A）。(A)x=HSdataHS=HSnext(B)x=HSdataHSNEXT=NULL