線性表08-12年1月試題及參考答案

1、.第 2 章 線性表 08-12 年 1 月試題及參考答案（ 2008 年 1 月）2、在下列對順序表進(jìn)行的操作中，算法時(shí)間復(fù)雜度為O(1)的是（）A 、訪問第 i 個(gè)元素的前驅(qū)（ 1<i n ）B、在第 i 個(gè)元素之后插入一個(gè)新元素 ( 1 i n )C、刪除第 i 個(gè)元素 (1 i n )D、對順序表中元素進(jìn)行排序3、假設(shè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針為head,則該鏈表為空的判定條件是（）A 、head= =NULLB、head>next= =NULLC、 head!=NULLD、head>next= =head17 、輸入線性表的n 個(gè) 元素 建立 帶頭 結(jié)點(diǎn)的單鏈表

2、，其時(shí)間復(fù)雜度為_。30、假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表,閱讀下列算法 f30,并回答問題 :(1) 設(shè)線性表為 ( a1, a2, a3, a4, a5, a6, a7 ), 寫出執(zhí)行算法 f30 后的線性表；(2) 簡述算法 f30 的功能。void f30(LinkList L)/L 為帶頭結(jié)點(diǎn)單鏈表的頭指針LinkList p,q;p=L;while (p &&p >next)q = p >next;p >next =q >next;p =q>next; free(q);(1)(2)34、假設(shè)以單鏈表表示線性表,單鏈表的類型定義如下 :t

3、ypedef struct node DataType data;struct node *next; LinkNode, *LinkList;編寫算法 ,將一個(gè)頭指針為 head且不帶頭結(jié)點(diǎn)的單鏈表改造為一個(gè)含頭結(jié)點(diǎn)且頭指針仍為 head的單向循環(huán)鏈表 ,并分析算法的時(shí)間復(fù)雜度。;.（ 2008 年 10 月）3、在頭指針為 head 的非空單循環(huán)鏈表中，指針p 指向尾結(jié)點(diǎn)，下列關(guān)系成立的是（）A 、 p->next=headB、 p->next->next=headC、 p->next=NULLD、 p=head17、將兩個(gè)長度分別為m 和 n 的遞增有序單鏈表，歸

4、并成一個(gè)按元素遞減有序的單鏈表，可能達(dá)到的最好的時(shí)間復(fù)雜度是。30、已知線性表的存儲(chǔ)結(jié)構(gòu)為順序表，閱讀下列算法，并回答問題：（ 1）設(shè)線性表 L=（21， -7，-8，19，0，-11，34，30，-10），寫出執(zhí)行 f30(&L)后的 L 狀態(tài)；（ 2）簡述算法 f30 的功能。voidf30 (SeqList*L) inti,j;for (i=j=0;i<L->length; i+)if(L->datai>=0)if(i!=j)L->dataj=L->datai;j+ ；L->length=j;(1)(2)（ 2009 年 1 月）2、假設(shè)

5、某個(gè)帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，則判定該表為空表的條件是()A 、head=NULL ；B、head->next=NULL ；C、 head!=NULL ；D、head->next=head；17、在雙向循環(huán)鏈表中插入一個(gè)新的結(jié)點(diǎn)時(shí)，應(yīng)修改_個(gè)指針域的值。30、假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表，單鏈表的類型定義如下：typedefintDataType;typedef struct node DataType data;struct node * next; LinkNode, * LinkList;閱讀下列算法，并回答問題：(1)已知初始鏈表如圖所示，畫出執(zhí)行f30(he

6、ad)之后的鏈表；;.題30圖(2)簡述算法 f30 的功能。void f30( LinkList head)LinkListp,r, s;if (head - > next)r = head - > next;p = r->next;r - > next = NULL;while (p)s =p;p = p->next;if ( s - > data% 2 = = 0)s - > next = head - > next;head - > next = s;elses - > next = r - > next;r->n

7、ext = s;r =s;(1)(2)34、假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表，單鏈表的類型定義如下：typedef int DataType;typedef struct node DataType data;struct node * next; LinkNode, * LinkList;編寫算法，刪除線性表中最大元素(假設(shè)最大值唯一存在 )。函數(shù)原型為：voidf34(LinkList head) ;（ 2009 年 10 月）;.3、指針 p、q 和 r 依次指向某循環(huán)鏈表中三個(gè)相鄰的結(jié)點(diǎn)，交換結(jié)點(diǎn)*q 和結(jié)點(diǎn) *r在表中次序的程序段是（）A 、p->next=r；q->ne

8、xt=r->next；r->next=q；B、 p->next=r；r->next=q；q->next=r->next；C、 r->next=q；q->next=r->next；p->next=r；D、r->next=q；p->next=r；q->next=r->next；17、如果需要對線性表頻繁進(jìn)行_或_操作，則不宜采用順序存儲(chǔ)結(jié)構(gòu)。31、假設(shè)學(xué)生成績按學(xué)號(hào)增序存儲(chǔ)在帶頭結(jié)點(diǎn)的單鏈表中，類型定義如下：typedefstructNodeintid;/* 學(xué)號(hào) */intscore；/* 成績 */struct

9、Node*next ； LNode， *LinkList ；閱讀算法 f31，并回答問題：(1)設(shè)結(jié)點(diǎn)結(jié)構(gòu)為，成績鏈表 A 和 B 如圖所示，畫出執(zhí)行算法f31(A ， B)后 A 所指的鏈表；(2)簡述算法 f31 的功能。voidf31(LinkList A,LinkList B)LinkListp, q;p=A->next;q=B->next;while (p && q)if(p->id<q->id)p=p->next;else if (p->id>q->id)q=q->next;elseif (p->sc

10、ore<60)if (q->score<60)p->score=q->score;.else p->score=60;p=p->next;q=q->next;34、假設(shè)線性表采用順序存儲(chǔ)結(jié)構(gòu)，其類型定義如下：#defineListSize100typedefstructintdataListSize;intlength; SeqList, *Table;編寫算法，將順序表L 中所有值為奇數(shù)的元素調(diào)整到表的前端。（ 2010 年 1 月）3、將長度為 n 的單鏈表連接在長度為m 的單鏈表之后，其算法的時(shí)間復(fù)雜度為（）A 、O(1)B、O(m)C、

11、O(n)D、O(m+n)4、在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中插入一個(gè)新結(jié)點(diǎn)，需要修改的指針域數(shù)量是（）A、2 個(gè)B、3 個(gè)C、4 個(gè)D、6 個(gè)17、長度為 n 的線性表采用單鏈表結(jié)構(gòu)存儲(chǔ)時(shí)，在等概率情況下查找第i 個(gè)元素的時(shí)間復(fù)雜度是 _。30、已知下列程序， Ls 指向帶頭結(jié)點(diǎn)的單鏈表。Typedefstruct node DataTypedata;struct node * next; * LinkList;void f30( LinkList Ls )LinkList p, q;q = Ls->next;if ( q && q->next )Ls->next

12、= q->next;p=qwhile ( p->next )p = p->next;p->next = q;.q->next = NULL;請回答下列問題：(1)當(dāng) Ls 指向的鏈表如下圖所示，請畫出執(zhí)行本函數(shù)之后的鏈表的結(jié)果。(2)請簡述算法的功能。（ 2010 年 10 月）2、若對某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，要使操作時(shí)間最少，下列選項(xiàng)中，應(yīng)選擇的存儲(chǔ)結(jié)構(gòu)是()A 、無頭結(jié)點(diǎn)的單向鏈表B、帶頭結(jié)點(diǎn)的單向鏈表C、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D、帶頭結(jié)點(diǎn)的單循環(huán)鏈表3、若帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，則判斷鏈表是否為空的

13、條件是()A 、head=NULLB、head->next=NULLC、 head!=NULLD、 head->next!=head17、已知鏈表結(jié)點(diǎn)定義如下：typedefstructnodechardata16；struct node*next; LinkStrNode ；如果每個(gè)字符占 1個(gè)字節(jié)，指針占 4個(gè)字節(jié)，則該鏈表的存儲(chǔ)密度是_。30、已知線性表 (a1,a2,a3， ，an)按順序存放在數(shù)組 a中，每個(gè)元素均為整數(shù)，下列程序的功能是將所有小于 0的元素移到全部大于等于 0的元素之前。例如，有 7個(gè)整數(shù)的原始序列為 (x,x,-x,-x,x,x,-x) ，變換后數(shù)組中

14、保存的序列是 (-x,-x,-x,x,x,x,x) 。請?jiān)诔绦蛱幪钊牒线m的內(nèi)容，使其成為完整的算法。f30(int a,int n) int k,m,temp；m=(1)；while(am<0 &&m<n)m=(2)；k=m;while(k<n) while(ak>=0&&k<n)k=(3)；if(k<n) temp=ak；ak=am ；;.am=(4)；m=(5)；(1)(2)(3)(4)(5)33、設(shè)有單鏈表類型定義如下：typedefstructnode intdata;structnode*next; *LinkLis

15、t;閱讀下列算法，并回答問題：voidf33(LinkListhead,intA,intB)LinkList p=NULL;While(head !=NULL)if(head->data>A&&head->data<B)p=head;head=head->next;if(p !=NULL)printf("%dn",p->data);(1)已知鏈表 h如下圖所示，給出執(zhí)行f33(h，5，8)之后的輸出結(jié)果；(2)簡述算法 f33的功能。（2011年 1 月）2、將兩個(gè)各有 n 個(gè)元素的有序表歸并成一個(gè)有序表， 最少的比較次數(shù)

16、是（）A 、n-1B、nC、2n-1D、2n17、在單鏈表中某結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)，需要修改_個(gè)結(jié)點(diǎn)指針域的值。32、閱讀下列程序。voidf32(intA,intn);.inti,j,m=l,t ；for(i=0;i<n-l&&m;i+)for(j=0； j<n； j+)printf( “%d ” ,Aj) ；printf( “ n”);m=0：for(j=1;j<n-i;j+)if(Aj-1>Aj)t=Aj-l;Aj-1=Aj ；Aj=t ；m=1；回答問題：已知整型數(shù)組 A =34,26,15,89,42 ，寫出執(zhí)行函數(shù)調(diào)用f32(A,5) 后的輸

17、出結(jié)果。34、假設(shè)用帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示線性表，單鏈表的類型定義如下：typedef struct node int data;struct node*next;LinkNode ，*LinkList;編寫程序，求頭指針為 head 的單循環(huán)鏈表中 data 域值為正整數(shù)的結(jié)點(diǎn)個(gè)數(shù)占結(jié)點(diǎn)總數(shù)的比例，若為空表輸出 0，并給出所寫算法的時(shí)間復(fù)雜度。函數(shù)原型為：floatf34(LinkListhead);（ 2011年 10 月）2.在一個(gè)長度為n 的順序表中插入一個(gè)元素的算法的時(shí)間復(fù)雜度為（）A.O（ 1）B.（ log n）C.O（ n）D.O（ n2）3.指針 p1 和 p2 分別指向兩

18、個(gè)無頭結(jié)點(diǎn)的非空單循環(huán)鏈表中的尾結(jié)點(diǎn)，要將兩個(gè)鏈表鏈接成一個(gè)新的單循環(huán)鏈表，應(yīng)執(zhí)行的操作為（）A.p1 next=p2 next;p2 next=p1 next;B. p2 next=p1 next;p1 next=p2 next;C. p=p2 next; p1 next=p;p2 next=p1 next;D. p=p1 next; p1 next= p2 next；p2 next=p;17.在單鏈表中，除了第 1 個(gè)元素結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置均由_;.指示。30.閱讀下列算法，并回答問題：（ 1）假設(shè) L=（3，7，7，11，20，20，20， 51，51），寫出執(zhí)行函數(shù) f30（&

19、amp;L ）后的 L；（ 2）簡述 f30 的功能。void f30(SeqList *L)/L 為非空的有序表int i=1,k=0;while(i<L->length)if(L->datai!=L->datak)L->data+k=L->datai;i+;L->length=k+1;(1)(2)（ 2012 年 1 月）2.某線性表中最常用的操作是在最后一個(gè)元素之后插入元素和刪除第一個(gè)元素，則最節(jié)省運(yùn)算時(shí)間的存儲(chǔ)結(jié)構(gòu)是（）A. 單鏈表B.雙鏈表C.僅有頭指針的單循環(huán)鏈表D.僅有尾指針的單循環(huán)鏈表17.線性表 L=(a1,a2, ，an)用數(shù)組表示

20、，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_。32.閱讀下列算法，并回答下列問題：(1)簡述該算法中標(biāo)號(hào)s1 所指示的循環(huán)語句的功能；(2)簡述該算法中標(biāo)號(hào)s2 所指示的循環(huán)語句的功能。LinkList Insertmnode(LinkList head ， char x，int m)LinkNode*p ，*q ，*s;int i;char ch；p=head->next；s1： while (p&&p->data!=x)p=p->next；if (p=NULL)printf("errorn")；else q

21、=p->next；s2：for(i=1 ；i<=m ；i+)s=(LinkNode *) malloc(sizeof(LinkNode) ；scanf(" c"，&ch) ；s->data=ch；p->next=s；;.p=s；p->next=q；return head；(1)(2)34.假設(shè)以單鏈表表示線性表，單鏈表的類型定義如下：typedef struct node DataType data；Struct node*next ； LinkNode ， * LinkList ；編寫算法，在一個(gè)頭指針為 head 且?guī)ь^結(jié)點(diǎn)的單鏈表

22、中，刪除所有結(jié)點(diǎn)數(shù)據(jù)域值為 x 的結(jié)點(diǎn)。函數(shù)原型為： LinkList delnode (LinkList head ， DataType x);.第 2 章 線性表 08-12 年 1 月參考答案（ 2008 年 1 月）2、 A3、D17、O(n)30、(1) (a2,a4,a6)(2)刪除線性表中奇數(shù)序號(hào)元素34、LinkListCreateCircularList(LinkList head)LinkList p;p=( LinkList)malloc(sizeof(LinkNode);p->next=head;head=p;while(p->next)p=p->ne

23、xt;p->next=head;return head;時(shí)間復(fù)雜度為 O(n)。（ 2008 年 10 月）3、 A17、O(m + n)30、(1) L=(21,19,0,34,30)(2)刪除順序表中負(fù)值元素（ 2009 年 1 月）2、B17、430、(1) head2857(2) 調(diào)整鏈表中的結(jié)點(diǎn)，將鏈表中所有值為偶數(shù)的結(jié)點(diǎn)移動(dòng)到表的前端。34、void f34(LinkList head)LinkList p,q,u,v; if(head->next=NULL) return; u=head;v=head->next; q=v; p=v->next; whil

24、e(p)if(p->data>v->data)u=q;v=p;.q=p;p=p->next;u->next=v->next;free(v);方法二：void f34(LinkList head)LinkList p,max;if(head->next=NULL) return;max=head->next;p=max->next;while(p)if(p->data>max->data)max=p;p=p->next;p=head;while(p->next!=max)p=p->next;p->next=max->next;free(max);（ 2009 年 10 月）3、 A17、插入、刪除31、(1)head170238390460560(2) 對于表 A 中成績低于 60 的學(xué)生，如果在表 B 中也有成績記錄，則將表A 中的成績修改為其在表 B 中的成績，但若其在表 B 中的成績高于 60 分，則只改為 60 分。34、void f34(SeqList *L)int i,j=0,