數(shù)據(jù)結構試題庫及參考答案

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

2、時，應執(zhí)行執(zhí)行操作為（C）。(A)HSnext=s(B)snext=HSnextHSnext=s(C)snext=HSHS=s(D)snext=HSHS=HSnext4假設以帶頭結點的循環(huán)鏈表表示隊列Q，并且隊列只設一個頭指針front，不設隊列尾指針。若要進隊一個元素s，則在下列程序算法的空白處應添加的操作語句是（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設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)至少為（B）。第3頁共101頁11下列程序段所代表的算法的時間復雜度為（C）。y=nx=1while(xnext==NULL(C)headnext==head(D)head

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