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

1、第 1 頁 共 101 頁數(shù)據(jù)結(jié)構(gòu)試題庫一、 單項(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( ) n2．在一個(gè)長度為 n 的以順序結(jié)構(gòu)存儲的線性表中，假設(shè)在線性表的任何位置刪除元素的概率相等，則刪除一個(gè)元素時(shí)線性表所需移動元素的平均次數(shù)為（

2、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->next=s;(C)s->next=HS;HS=s; (D)s->next=HS;

3、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)添加的操作語句是（ A ） 。void AddQueue(struct linkqueue Q){ p=Q->front;while(p->next!=Q->front) p=p->next;}(A)p->next=s;s->nex

4、t=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;5．設(shè)高度為 h 的二叉樹上只有度為 0 和度為 2 的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（ B ） 。第 3 頁 共 101 頁11． 下列程序段所代表的算法的時(shí)間復(fù)

5、雜度為（ C ） 。y=n;x=1;while(xnext==NULL(C)head->next==head (D)head!=NULL15． 若鏈隊(duì)列 HQ 中只有一個(gè)結(jié)點(diǎn)，則隊(duì)列的頭指針和尾指針滿足下列條件 （ D ） 。(A)HQ->rear->next==HQ->front (B)HQ->front->next==HQ->rear->next(C)

6、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