第二章線性表2016.3

一、選擇題

1、若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素算法的時間復雜度（）。

2

A.O（log2n）B.O（l）C.O（n）D.O（n）

2、若一個線性表中最常用的操作是取第i個元素和找第i個元素的前驅元素，則采用（）存儲方式最

節(jié)省時間。

A.順序表B.單鏈表C.雙鏈表D.單循環(huán)鏈表

3、具有線性結構的數(shù)據(jù)結構是（）。

A.圖B,樹C.二叉樹D.棧

4、在一個長度為n的順序表中，在第i個元素之前插入一個新元素時，需向后移動（）個元素。

A.n-iB.n-i+1C.n-i-1D.i

5、非空的循環(huán)單鏈表head（頭指針）的尾元素結點p滿足（）?

A.p->next==headB.p->next—NULL

C.p==NULLD.p==head

6、鏈表不具有的特點是（）o

A.可隨機訪問任一元素B.插入刪除不需要移動元素

C.不必事先估計存儲空間D.所需空間與線性表長度成正比

7、在雙向循環(huán)鏈表中，在p指針所指的結點后插入一個指針q所指向的新結點，修改指針的操作是（）o

A.p->next=q;q->prior=p;p->next->prior=q;q->next=q;

B.p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;

C.q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;

D.q->next=p->next;q->prior=p;p->next=q;p->next=q;

8、線性表采用鏈式存儲時，結點的存儲地址（）。

A.必須是連續(xù)的B.必須是不連續(xù)的

C.連續(xù)與否均可D.和頭結點的存儲地址相連續(xù)

9、在一個長度為n的順序表中刪除第i個元素，需要向前移動（）個元素。

A.n-iB.n-i+1C.n-i-1D.i+1

10、線性表是n個（）的有限序列。

A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項

11、從表中任一結點出發(fā)，都能掃描整個表的是（）。

A.單鏈表B.順序表C.循環(huán)鏈表D.靜態(tài)鏈表

12、在具有n個結點的單鏈表上查找值為x的元素時，其時間復雜度為（）。

A.O（n）B.0（1）C.0（n2）D.O（n-l）

13、線性表L=（ai,a2,……,an）,下列說法正確的是（）?

A.每個元素都有一個直接前驅和一個直接后繼

B.線性表中至少要有一個元素

C.表中諸元素的排列順序必須是由小到大或由大到小

D.除第一個和最后一個元素外，其余每個元素都由一個且僅有一個直接前驅和直接后繼

14、一個順序表的第一個元素的存儲地址是90,每個元素的長度為2,則第6個元素的存儲地址是（）。

A.98B.100C.102D.106

15、在線性表的下列存儲結構中，讀取元素花費的時間最少的是（）。

A.單鏈表B.雙鏈表C.循環(huán)鏈表D.順序表

16、在一個單鏈表中，若刪除p所指向結點的后繼結點，則執(zhí)行（）。

A.p->next=p->next->next;

B.p=p->next;p->next=p->next->next;

C.p=p->next;

D.p=p->next->next;

17、將長度為n的單鏈表連接在長度為m的單鏈表之后的算法的時間復雜度為（）。

A.0(1)B.0(n)C.0(m)D.0(m+n)

18、線性表的順序存儲結構是一種()存儲結構。

A.隨機存取B.順序存取C.索引存取D.散列存取

19、順序表中，插入一個元素所需移動的元素平均數(shù)是(

A.(n-l)/2B.nC.n+1D.(n+l)/2

20、循環(huán)鏈表的主要優(yōu)點是()。

A.不再需要頭指針B.已知某結點位置后能容易找到其直接前驅

C.在進行插入、刪除運算時能保證鏈表不斷開

D.在表中任一結點出發(fā)都能掃描整個鏈表

21、不帶頭結點的單鏈表head為空的判定條件是()。

A.head==NULLB.head->next==NULL

C.head->next==headD.head!=NULL

22、在下列對順序表進行的操作中，算法時間復雜度為0(1)的是()。

A.訪問第i個元素的前驅(l<i<n)B.在第i個元素之后插入一個新元素(14i4n)

C.刪除第i個元素(IViVn)D.對順序表中元素進行排序

23、已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點。假設指針s指向另一個單鏈表中某個結

點，則在S所指結點之后插入上述鏈表應執(zhí)行的語句為()。

A.q->next=s->next；s->next=p；

B.s->next=p；q->next=s->next；

C.p->next=s->next；s->next=q；

D.s->next=q；p->next=s->next；

24、在以下的敘述中，正確的是()。

A.線性表的順序存儲結構優(yōu)于鏈表存儲結構

B.線性表的順序存儲結構適用于頻繁插入/刪除數(shù)據(jù)元素的情況

C.線性表的鏈表存儲結構適用于頻繁插入/刪除數(shù)據(jù)元素的情況

D.線性表的鏈表存儲結構優(yōu)于順序存儲結構

25、在表長為n的順序表中，當在任何位置刪除一個元素的概率相同時，刪除一個元素所需移動的平均個

數(shù)為()。

A.(n-l)/2B.n/2C.(n+1)/2D.n

26、在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入一個結點s,則執(zhí)

行(

A.s->next=p->next;p->next=s;

B.p->next=s->next;s->next=p;

C.q->next=s;s->next=p;

D.p->next=s;s->next=q;

27、在單鏈表中，指針p指向元素為x的結點，實現(xiàn)刪除x的后繼的語句是()。

A.p=p->next;B.p->next=p->next->next;

C.p->next=p;D.p=p->next->next;

28、在頭指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個結點，若p->next->next==head,則

()。

A.p指向頭結點B.p指向尾結點C.p的直接后繼是頭結點D.p的直接后繼是尾結點

二、填空題

1、設單鏈表的結點結構為(data,next)。已知指針p指向單鏈表中的結點，q指向新結點，欲將q插入到p結

點之后，則需要執(zhí)行的語句：;。

2、線性表的邏輯結構是,其所含元素的個數(shù)稱為線性表的。

3、寫出帶頭結點的雙向循環(huán)鏈表L為空表的條件。

4、帶頭結點的單鏈表head為空的條件是o

5、在一個單鏈表中刪除p所指結點的后繼結點時，應執(zhí)行以下操作：

q=p->next;

p->next=;

三、判斷題

1、單鏈表不是一種隨機存儲結構。

2、在具有頭結點的單鏈表中，頭指針指向鏈表的第一個數(shù)據(jù)結點。

3、用循環(huán)單鏈表表示的鏈隊列中，可以不設隊頭指針，僅在隊尾設置隊尾指針。

4、順序存儲方式只能用于存儲線性結構。

5、在線性表的順序存儲結構中，邏輯上相鄰的兩個元素但是在物理位置上不一定是相鄰的。

6、鏈式存儲的線性表可以隨機存取。

四、程序分析填空題

1、函數(shù)GetElem實現(xiàn)返回單鏈表的第i個元素，請在空格處將算法補充完整。

intGetElem(LinkListL,inti,Elemtype*e){

LinkLislp；inij；

p=L->next;j=l;

while(p&&j<i){

(1):++i；

)

if(!p||j>i)returnERROR;

*e=(2);

returnOK;

)

2、函數(shù)實現(xiàn)單鏈表的插入算法，請在空格處將算法補充完整。

intListInsert(LinkListL,inti,ElemTypee){

LNode*p,*s;intj;

P=L;j=O;

while((p!=NULL)&&(j<i-1)){p=p->next;j++;

)

if(p==NULL|lj>i-l)returnERROR;

s=(LNode*)malloc(sizeof(LNode));

s->data=e;

______CD___________；

(2)____；

returnOK;

}/*ListInsert*/

3、函數(shù)LislDelete_sq實現(xiàn)順序表刪除算法，請在空格處將算法補充完整。

intListDelete_sq(Sqlist*L,inti){

intk;

if(i<l||i>L->length)returnERROR;

for(k=i-1;k<L->length-1;k++)

L->slist[k1=(1);

(2);

returnOK;

)

4、函數(shù)實現(xiàn)單鏈表的刪除算法，請在空格處將算法補充完整。

intListDelete(LinkListL,inti,ElemType*s){

LNode*p,*q;

intj;

p=L;j=O;

while((O))&&(j<i-1)){

p=p->next;j++;

)

if(p->next==NULL||j>i-1)returnERROR;

q=p->next;

(2)

*s=q->data;

free(q);

returnOK;

}/*listDelete*/

5、寫出算法的功能。

intL(head){

node*head;

intn=0;

node*p;

p=head;

while(p!=NULL)

{p=p->next;

n++;

)

return(n);

五、綜合題

1、設一個帶頭結點的單向鏈表的頭指針為head,設計算法，將鏈表的記錄，按照data域的值遞增排序。

2、已知head為帶頭結點的單循環(huán)鏈表的頭指針，鏈表中的數(shù)據(jù)元素依次為(al,a2,a3,a4,…,an),A為指向

空的順序表