數(shù)據(jù)結(jié)構(gòu)第2章線(xiàn)性表

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)第2章線(xiàn)性表第2章線(xiàn)性表

一選擇題

1．下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（）

A．存儲(chǔ)密度大B．插入運(yùn)算便利C．刪除運(yùn)算便利D．可便利地用于各種規(guī)律結(jié)構(gòu)的存儲(chǔ)表示

2．下面關(guān)于線(xiàn)性表的表達(dá)中，錯(cuò)誤的是哪一個(gè)？（）

A．線(xiàn)性表采用順序存儲(chǔ)，必需占用一片連續(xù)的存儲(chǔ)單元。B．線(xiàn)性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C．線(xiàn)性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D．線(xiàn)性表采用鏈接存儲(chǔ)，便于插入和刪除操作。3．線(xiàn)性表是具有n個(gè)（）的有限序列（n>0）。

A．表元素B．字符C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項(xiàng)

4．若某線(xiàn)性表最常用的操作是存取任一指定序號(hào)的元素和在最終進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。

A．順序表B．雙鏈表C．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D．單循環(huán)鏈表5.鏈表不具有的特點(diǎn)是（）

A．插入、刪除不需要移動(dòng)元素B．可隨機(jī)訪(fǎng)問(wèn)任一元素C．不必事先估計(jì)存儲(chǔ)空間D．所需空間與線(xiàn)性長(zhǎng)度成正比

6.若長(zhǎng)度為n的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間繁雜度為（）(1next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;

10．對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（）

A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL二、判斷題

1.線(xiàn)性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。()2．對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。()3．集合與線(xiàn)性表的區(qū)別在于是否按關(guān)鍵字排序。()

4.線(xiàn)性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。()5.循環(huán)鏈表不是線(xiàn)性表.()6.線(xiàn)性表就是順序存儲(chǔ)的表。()三、填空題

1．線(xiàn)性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率一致，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是________。

2．設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn),若將結(jié)點(diǎn)y插入結(jié)點(diǎn)