本文格式為Word版，下載可任意編輯——其次部分線性表答案其次部分線性表

一、選擇題

1．關于順序存儲的表達中,哪一條是不正確的(B)

A.存儲密度大

B.規(guī)律上相鄰的結(jié)點物理上不必鄰接C.可以通過計算直接確定第i個結(jié)點的位置D.插入、刪除操作不便利

2．長度為n的單鏈表連接在長度為m的單鏈表后的算法的時間繁雜度為(C)

AO(n)BO(1)CO(m)DO(m+n)

3．在n個結(jié)點的順序表中，算法的時間繁雜度是O(1)的操作是：(A)

A訪問第i個結(jié)點（1link=p;p->link=s;（B）s->link=p->link;p->link=s;（C）s->link=p->link;p=s;（D）p->link=s;s->link=p;

16.在循環(huán)鏈表中first為指向鏈表表頭的指針，current為鏈表當前指針，在循環(huán)鏈表中

檢測current是否達到鏈表表尾的語句是(D)。（A）current->link=NULL(B)first->link=current（C）first=current(D)current->link=first

17.從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的狀況下，需平

均比較(D)個結(jié)點。A.n

B.n/2

C.（n-1）/2

D.(n+1)/2

18.在一個具有n個結(jié)點的有序單鏈表中，插入一新結(jié)點并依舊有序的時間繁雜度為(B)。A.O(1)

B.O(n)

C.O(n2)

D.O(nlog2n)

19.用鏈表表示線性表的優(yōu)點是(C)。

A.便于隨機存取B.花費的存儲空間比順序表少

C.便于插入與刪除D.數(shù)據(jù)元素的物理順序與規(guī)律順序一致20.當需要隨機查找線性表的元素時,宜采用(C)作存儲結(jié)構(gòu)。

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

21.線性表的鏈接實現(xiàn)有利于（A）運算。A、插入b、讀表元c、查找d、定位22.線性表采用鏈式存儲時，其地址（D）。

A必需是連續(xù)的B部分地址是連續(xù)的C一定是不連續(xù)的D連續(xù)與否均可以

23.設單鏈表中指針p指著結(jié)點a，若要刪除a之后的結(jié)點（若存在），則需要修改指針的操作為（A）。

A、p->next=p->next->nextb、p=p->nextC、p=p->next->nextd、p->next=p

24.向一個有127個元素原順序表中插入一個新元素并保存原來順序不變，平均要移動（B）個元素。

A、8B、63.5C、63D、7

25.向一個有127個元素的順序表中刪除一個元素，平均要移動（C）個元素（A）8（B）63.5（C）63（D）726.用鏈表表示線性表的優(yōu)點是（A）

A便于插入和刪除操作

B數(shù)據(jù)元素的物理順序與規(guī)律順序一致D便于隨即存取

C花費的存儲空間較順序存儲少

27.以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是（C）

A隊列

B線性表

C二叉樹

D棧

28．對長度為N的線性表進行順序查找，在最壞狀況下所需要的比較次數(shù)為（B）。

A．N+1

B．N

C．(N+1)/2

D．N/2

29．以下表達中正確的是(A)。

A.線性表是線性結(jié)構(gòu)

B.棧與隊列是非線性結(jié)構(gòu)D.二叉樹是線性結(jié)構(gòu)

C.線性鏈表是非線性結(jié)構(gòu)

30．在單鏈表中，增加頭結(jié)點的目的是(A)。

A.便利運算的實現(xiàn)

B.使單鏈表至少有一個結(jié)點

D.說明單鏈表是線性表的鏈式存儲實現(xiàn)

C.標識表結(jié)點中首結(jié)點的位置

31．線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是（B）。

A.順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)B.隨機存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)C.隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu)D.任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)33．線性表中正確的說法是(D)。

A.每個元素都有一個直接前驅(qū)和一個直接后繼B.線性表至少要求一個元素

C.表中的元素必需按由小到大或由大到小排序

D.除了第一個和最終一個元素外，其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼

34．線性表是具有n個（C）的有限序列。

A.表元素

B.字符

C.數(shù)據(jù)元素

D.數(shù)據(jù)項

35．若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間繁雜度為（C）。（1≤i≤n+1）

A.O(0)

B.O(1)

C.O(n)

D.O(n)

D.O(n2)

2

36．在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并使鏈表依舊有序的時間繁雜度（B）。

A.O(1)

B.O(n)

C.O(nlogn)

37．某線性表最常用的運算是插入和刪除，插入運算是指在表尾插入一個新元素，刪除運算是指刪除表頭第一個元素，那么采用（A）存儲方式最節(jié)省運算時間。

二、填空題

1．在單項鏈表中刪除一個指定結(jié)點的后繼的時間繁雜度為[O(1)]

2．線性表中______數(shù)據(jù)元素的個數(shù)______________________稱為表的長度。3.在n個結(jié)點的單鏈表中，在P指向的結(jié)點之后插入一個結(jié)點的時間繁雜度為_O（n）。4．設長度為n的線性表順序存貯,若在它的第i-1和第i個元素之間插入一個元素,共需移動__n-i+1_______個元素(1link;

p->link=__p->link->link____Deleteq

9．將適當?shù)恼Z句添入單鏈表探尋函數(shù)find中。

A.僅有尾指針的單向循環(huán)鏈表C.單向鏈表

B.僅有頭指針的單向循環(huán)鏈表D.雙向鏈表

templateListNode*List::find(Typevalue)

{

current=first->link；while(current!=NULL)

if(current->data=value)breakelsecurrent=current->link;return__current_____}

10．順序存儲方法是把規(guī)律上相鄰的結(jié)點存儲在物理位置__也相鄰______的存儲單元中。

11．順序存儲結(jié)構(gòu)使線性表中規(guī)律上相鄰的數(shù)據(jù)元素在物理上也相鄰。因此，這種表便于__隨機__訪問，是一種__隨機訪問存儲結(jié)構(gòu)__。

12．在一個不帶頭結(jié)點的單鏈表中，在表頭插入或刪除與其在其他位置插入或刪除操作的過程___不一致________。

13．已知L是無頭結(jié)點的單鏈表，且P結(jié)點既不是首元素結(jié)點，也不是尾元素結(jié)點，添加適合的語句。

1)P結(jié)點之后插入結(jié)點S：S->next=P->next;P->next=S;2)P結(jié)點之前插入結(jié)點S：

pre=L;

while(pre->next!=P)pre=pre->next;S->next=P;pre->next=S;

3)在表首插入結(jié)點S：S->next=L;L=S;4)在表尾插入結(jié)點S：

while(P->next)P=P->next;P->next=S;S->next=NULL;

14．已知P結(jié)點是某雙向鏈表的中間結(jié)點，添加適合的語句。

1)P結(jié)點之后插入結(jié)點S：

S->next=P->next;S->prior=P;P->next->Prior=S;P->next=S;2)P結(jié)點之前插入結(jié)點S：

S->next=P;S->prior=P->prior;

P->prior->next=S;P->prior=S;3)刪除P結(jié)點的直接后繼結(jié)點：

Q=P->next;P->next=Q->next;Q->next->prior=P;free(Q);4)刪除P結(jié)點的直接前驅(qū)結(jié)點：

Q=P->prior;P->prior=Q->prior;Q->prior->next=P;free(Q);5)刪除P結(jié)點：

P->prior->next=P->next;P->next->prior=P->prior;free(P);

15．在鏈表的結(jié)點中，數(shù)據(jù)元素所占存儲量和整個結(jié)點所占的存儲量之比稱作存儲密度。

三、判斷題

1．線性鏈表中各個鏈結(jié)點之間的地址不一定要連續(xù)。(R)

2．若頻繁地對線性表進行插入和刪除操作，該線性表采用順序存儲結(jié)構(gòu)更適合。(W)3．若線性表采用順序存儲結(jié)構(gòu)，每個數(shù)據(jù)元素占用4個存儲單元，第12個數(shù)據(jù)元素的存儲地址為144，則第1個數(shù)據(jù)元素的存儲地址是101。(W)

4．若長度為n的線性表采用順序存儲結(jié)構(gòu)，刪除表的第i個元素之前需要移動表中n-i+1個元素。(W)

5．在順序表中取出第i個元素所花費的時間與i成正比。（W）

四、算法題

1．設n個元素的線性表順序存儲在一維數(shù)組st[1..maxlen]的前n個位置上,試將新元素

e插入表中第i-1個和第i個元素之間,寫出算法。

typedefstruct{

ElemTypest[1..maxlen];//存放線性表的數(shù)組intn;//n是線性表的長度}SeqList;

SeqListSeqLiseInit(){//構(gòu)造一個線性鏈表L

SeqListL;//定義為順序表L.lengh=0;//順序表的長度為0returnL}

voidSeqListInsert(SeqlistL,inti,ElemTypex){//在順序表中的第i個位置插入元素xif(L.length==maxlen){

printf(\exit(0);//表滿,退出}

if(iL.length){

printf(\

exit(0);//插入位置錯,退出}

for(j=L.length-1;j>=i-1;j--)

L.data[j+1]=L.data[j];//第i個位置后的數(shù)組元素逐一后移L.data[i-1]=x;//新元素插入到第i個位置L.length++;//順序表長度增1}

3.執(zhí)行下面的C程序,指出輸出結(jié)果。

#include#includestructnode{chardata；

structnode*next；}；

voidlink_list(structnode*p){while(p!=NULL)

{printf(\；p=p->next；}

printf(\；}

main(){charch；

structnode*q,*p,*f,*head=NULL；for(ch='A'；chdata=ch；p->next=head；head=p；link_list(p)；}p=head；head=NULL；while(p!=NULL)

{q=p；p=p->next；q->next=head；while(f->next!=NULL)

{link_list(head)；f=f->next->next；}}

}ABACBADCBAEDCBAFEDCBAFFEFEDFEDFEDCFEDCFEDCBFEDCBFEDCBFEDCBAFEDCBA

head=q；f=head；FEDCBA

4．以下算法完成的功能？

1）ListNode*Demo1(LinkListL,ListNode*p)

/*L是帶有頭結(jié)點的單鏈表*/{ListNode*q=L->next;}

while(q

if(q)

returnq;

else

error(“*pisnotinL!〞);

尋覓結(jié)點P的前驅(qū)結(jié)點，若存在則返回前驅(qū)結(jié)點的地址，若不存在則給出錯誤信息2)voidDemo2(ListNode*p,ListNode*q)

{DataTypetemp;}

temp=p->data;p->data=q->data;q->data=temp;

交換結(jié)點p和q數(shù)據(jù)域的內(nèi)容3)LinkListDemo3(LinkListL)

/*L是無頭結(jié)點的單鏈表*/{ListNode*p,*q;

if(L

L=L->next;p=L;

While(p->next)p->next=q;q->next=NULL;

p=p->next;

}

}returnL;

將鏈表L第一個結(jié)點變?yōu)樽罱K一個結(jié)點

4)LinkList*Connect(LinkList*L1,LinkList*L2)

/*L1,L2是帶有頭結(jié)點的單鏈表*/{LinkList*p;}

p=L1;

while(p->next!=NULL)p->next=L2->next;return(L1);

p=p->next;

將L2連接到L1后面

5．設Head為帶頭結(jié)點的單鏈表的頭指針，試寫出算法，若為非空表，則輸出首結(jié)點和尾結(jié)點的值（data值），否則輸出“EmptyList!〞。Structnode{};

printht(structnode*Head){structnode*p;}

if(Head->next==NULL)printf(“EmptyList!〞);else{}

printf(“首結(jié)點的值為%d〞,Head->next->data);p=Head->next;

while(p->next)p=p->next;

if(p!=Head->next)printf(“尾結(jié)點的值為%d〞,p->data);elseprintf(“僅有一個結(jié)點！〞);Intdata;

Structnode*next;

6．假設有兩個按元素遞增有序排列的線