數(shù)據(jù)結(jié)構(gòu)線性表習(xí)題1

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)題1指導(dǎo)老師：常璐璐姓名：邢莉彬 學(xué)校：濱州學(xué)院 院系：信息工程學(xué)院軟件技術(shù)填空題1. 對于一個 n 個結(jié)點(diǎn)的單鏈表，在表頭插入元素的時間復(fù)雜度為 O(1) ， 在 表 尾 插 入 元 素 的 時 間 復(fù) 雜 度 為O(n)。2. 刪除非空線性鏈表中由 q 所指的鏈結(jié)點(diǎn)(其直接前驅(qū)結(jié)點(diǎn)由r 指 出 ) 的 動 作 時 執(zhí) 行 語 句 _r->link=q->link 和free(q)。結(jié)點(diǎn)結(jié)構(gòu)為typedef struct Nodeint value;node * link;node;3. 非空線性鏈表中，若要在由 p 所指的鏈結(jié)點(diǎn)后面插入新結(jié)點(diǎn)q ， 則 應(yīng) 執(zhí) 行

2、語 句 q->link=p->link; 和 p->link=q;。結(jié)點(diǎn)結(jié)構(gòu)為typedef struct Nodeint value;node* link;node;4 .線性表L= (a1,a2,an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是(n-1)/2 。5 .在一個長度為n的順序表中第i個元素(iwiwn)之前插入一個元素時，需向后移動 n-i+1 個元素。6 .在具有n 個鏈結(jié)點(diǎn)的鏈表中查找一個鏈結(jié)點(diǎn)的時間復(fù)雜度為O(n_)。7 . 線性表中的插入、 刪除操作， 在順序存儲方式下平均移動近一半的元素，時間復(fù)雜度為 O( n

3、) ；而在鏈?zhǔn)酱鎯Ψ绞较?，插入和刪除操作的時間復(fù)雜度都是 O(1) 。8 . 若某線性表采用順序存儲結(jié)構(gòu)，每個元素占 4 個存儲單元，首地址為 100，則第 10個元素的存儲地址為 136。選擇題1 .對于一個帶頭結(jié)點(diǎn)的單鏈表，頭指針為 head,判定該表為空 的條件是 B_。A. head=NULL B. head->next=NULL C. head->next=head D. head!=NULL2 . 將長度為 m 的線性鏈表鏈接在長度為 n 的線性鏈表之后的過程的時間復(fù)雜度若采用大O 形式表示，則應(yīng)該是B 。A O(m)B O(n)C O(m+n)D O(m-n)3 .在

4、包含1000 個數(shù)據(jù)元素的線性表中，實(shí)現(xiàn)如下 4 個操作所需要的執(zhí)行時間最長的是A 。A. 線性表采用順序存儲結(jié)構(gòu)，在第10個元素后面插入一個新的元素B. 線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，在第10個元素后面插入一個新的元素C. 線性表采用順序存儲結(jié)構(gòu)，刪除第 990 個元素D. 線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，刪除p 所指的鏈結(jié)點(diǎn)4 . 在非空雙向循環(huán)鏈表中由 q 所指的那個鏈結(jié)點(diǎn)前面插入一個由 p 所指的鏈結(jié)點(diǎn)的動作所對應(yīng)的語句依次為： p 一 >rlink=q; p一>llink=q>llink; q >llink=p;D。（空白處為一條賦值語句 ）A. q 一 >rlink

5、= p;B. q>llink>rlink=p;C. p>rlink>rlink= p;D. p >llink >rlink=p;5 .在一個單向循環(huán)鏈表中， 若要在 p 所指向的結(jié)點(diǎn)之后插入一個新結(jié)點(diǎn)，則需要相繼修改 B個指針域的值A(chǔ). 1 B. 2 C. 3 D. 46 .在一個具有n 個鏈結(jié)點(diǎn)的線性鏈表中查找某一個鏈結(jié)點(diǎn)， 若查找成功，需要平均比較C個鏈結(jié)點(diǎn)。A. nB. n/2C. (n+1)/2D. (n-1)/27 .給定一個具有n 個元素的順序表， 建立一個有序線性鏈表的時間復(fù)雜度為 C 。A. O(1)B.O(n)C. O(n2) D. O(l

6、og2n)8 . 鏈表不具有的特點(diǎn)是( B)A.插入、刪除不需要移動元素B.可隨機(jī)訪問任一元素C.不必事先估計存儲空間D.所需空間與線性長度成正比9 . 下面關(guān)于線性表的敘述中，錯誤的是哪一個？ _BA.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B.線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D.線性表采用鏈接存儲，便于插入和刪除操作。10 .下列哪一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？ DA. 順序表B. 鏈表C. 散列表D. 隊(duì)列11 .設(shè)指針q指向單鏈表中結(jié)點(diǎn) A,指針p指向單鏈表中結(jié)點(diǎn) A 的后繼結(jié)點(diǎn)B,指針s指向被插入的結(jié)點(diǎn) X,則在結(jié)

7、點(diǎn)A和結(jié)點(diǎn)B 插入結(jié)點(diǎn) X 的操作序列為 B。A s->next=p->nex；t p->next=-s；B q->next=s； s->next=p；C p->next=s->nex；t s->next=p；D p->next=s； s->next=q；12 .在一個單鏈表中，若 p所指節(jié)點(diǎn)不是最后節(jié)點(diǎn)，在 p之后插入 s 所指節(jié)點(diǎn)，則執(zhí)行BA. s->link=p; p->link=s;B. s->link=p->link; p->link=s;C. s->link=p->link; p=

8、s;D. p->link=s; s->link=p;13 .某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用_D存儲方式最節(jié)省運(yùn)算時間。A. 單鏈表 B. 僅有頭指針的單循環(huán)鏈表C. 雙鏈表 D. 僅有尾指針的單循環(huán)鏈表14 .對 N 個元素的表做順序查找時， 若查找每個元素的概率相同，則平均查找長度為_BA N/2 B. ( N+1) /2 C. N D. ( 1+N) *N /215 .若長度為 n 的線性表采用順序存儲結(jié)構(gòu)，在其第 i 個位置插入一個新元素的算法的時間復(fù)雜度為 (C) (1<=i<=n+1)。A. O(0) B. O(

9、1) C. O(n) D. O(n2)16 .在一個以 h 為頭的單循環(huán)鏈表中， p 指針指向鏈尾的條件是A 。A. p->next = h B. p->next = NULL C. p->next->next = h D.p->data = -1算法填空題：設(shè)lista, listb分別為兩個有序鏈表(升序)的第1個鏈結(jié)點(diǎn)的指針， 將這兩個有序鏈表合并為一個有序鏈表， 并設(shè)合并后的鏈表的第一個鏈結(jié)點(diǎn)的指針為 listc.LinkList MERGELIST(LinkList lista,LinkList listb)LinkList listc,p=lista,q=listb,r;if(lista->data<=listb->data)listc=lista;r=lista;p=lista->link;elselistc=listb;r=listb;q=listb->link;whil