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

1、第二章作業(yè)題1 .求單鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前驅(qū)的時間復(fù)雜度分別是（）A. 0 (n)和 0 (1)B. 0 (1 )和 0( 1)C. 0 (1 )和 0 (n)D. 0(n)和 0 (n)2 .非空的單循環(huán)鏈表的頭指針為head,尾指針為rear,則下列條件成立的是（)A. rear->next= =headB. rear->next->next= =headC. head->next= =rearD. head->next->next= =rear3.在帶頭結(jié)點(diǎn)的循環(huán)鏈表L中，結(jié)點(diǎn)的數(shù)據(jù)元素為整型，且按值遞增有序存放。給定兩個整數(shù)a和b,且a<b

2、，編寫算法刪除鏈表L中元素值大于a且小于b的所有結(jié)點(diǎn)。4 在線性表的下列運(yùn)算中，不.改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（）A 插入B.刪除C.排序D .定位5已知指針p和q分別指向某單鏈表中第一個結(jié)點(diǎn)和最后一個結(jié)點(diǎn)。假設(shè)指針s指向另一個單鏈表中某個結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(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

3、->next;6 若線性表的插入和刪除操作頻繁地在表頭或表尾位置進(jìn)行，則更適宜采用的存儲結(jié)構(gòu)為（ ）A .無頭結(jié)點(diǎn)的雙向鏈表B.帶尾指針的循環(huán)鏈表C.無頭結(jié)點(diǎn)的單鏈表D .帶頭指針的循環(huán)鏈表7在下列對順序表進(jìn)行的操作中，算法時間復(fù)雜度為0（1）的是（）A. 訪問第i個元素的前驅(qū)（1<r<n ）B. 在第i個元素之后插入一個新元素（1心豈n ）C. 刪除第i個元素（1n ）D. 對順序表中元素進(jìn)行排序8在鏈表的結(jié)點(diǎn)中，數(shù)據(jù)元素所占的存儲量和整個結(jié)點(diǎn)所占的存儲量之比稱作。&鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)是借助 來表示數(shù)據(jù)元素之間的邏輯關(guān)系。10. 在一個長度為 n的單鏈表L中，刪除鏈

4、表中*p的前驅(qū)結(jié)點(diǎn)的時間復(fù)雜度為 。11. 假設(shè)帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表中僅設(shè)尾指針L,則在第1個結(jié)點(diǎn)之前插入指針s所指結(jié)點(diǎn)的語句依次是; 。12 .已知head為帶頭結(jié)點(diǎn) 的單循環(huán)鏈 表的頭指針，鏈表中的 數(shù)據(jù)元素依 次為（a1 , 32,a3,a4,an） ,A為指向空的順序表的指針。閱讀以下程序段，并回答問題：（1） 寫出執(zhí)行下列程序段后的順序表A中的數(shù)據(jù)元素；（2）簡要敘述該程序段的功能。if(head->n ext!=head)p=head->n ext;A->le ngth=O;while(p->n ext!=head)p=p->n ext;A->

5、;dataA->le ngth +=p->data;if(p->n ext!=head)p=p->n ext;(1)13. 已知鏈串的存儲結(jié)構(gòu)描述如下：#define NodeSize 4typedef struct Node char data NodeSize;structNode * n ext; * Li nkStr;閱讀下列算法，并回答問題：(1) t1和t2的串值分別為Chinese''和 China時，寫出f31(t1,t2)的返回值；(2) t1和t2的串值分別為"Japan"和"Japanes6'時

6、，寫出f31(t1,t2)的返回值;(3) t1和t2的串值都為string"時，寫出f31(t1,t2)的返回值；(4 )簡述函數(shù)f31的功能。inf f31(L in kStr t1,L i nkStr t2)/串值以0'為結(jié)束符int i;while (1)for (i=0;i<NodeSize;i+)if (t1->datai= = ' 0 ' &&t2->datai= =' 0' return 0;if(t1->datai= = ' 0' )return -;if(t2->

7、datai= = ' 0' )return 1;if(t1->datai>t2->dataireturn 1;if(t1->datai<t2->dataireturn -;t1=t1-> next;t2=t2-> next; (1)14. 已知用有序鏈表存儲整數(shù)集合的元素。閱讀算法f30,并回答下列問題：(1 )寫出執(zhí)行f30( a,b)的返回值，其中a和b分別為指向存儲集合2，4, 5，7，9，12 和2，4，5，7, 9的鏈表的頭指針；(2) 簡述算法f30的功能；(3) 寫出算法f30的時間復(fù)雜度。int f30(Li nk

8、List ha,L in kList hb)/LinkList是帶有頭結(jié)點(diǎn)的單鏈表/ha和hb分別為指向存儲兩個有序整數(shù)集合的鏈表的頭指針Lin kList pa,pb;pa=ha->n ext;pb=hb->n ext;while(pa && pb && pa->data=pb->data)pa=pa->n ext;pb=pb->n ext;if(pa=NULL && pb=NULL) return 1;else return 0;(1)15. 假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示有序表，單鏈表的類型定義如下：typedef struct no deDataType data;struct node *n extLi nkNode, *Li nkList;編寫算法，從有序表A中刪除