《數(shù)據(jù)結(jié)構(gòu)線性表習(xí)題.docx》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)線性表習(xí)題.docx（7頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)線性表習(xí)題第二章作業(yè)題1求單鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前驅(qū)的時(shí)間復(fù)雜度分別是（）AO（n）和O（1）BO（1）和O（1）CO（1）和O（n）DO(n)和O（n）2非空的單循環(huán)鏈表的頭指針為head,尾指針為rear，則下列條件成立的是（）Arear-next= =head Brear-next-next= =headChead-next= =rear Dhead-next-next= =rear3在帶頭結(jié)點(diǎn)的循環(huán)鏈表L中，結(jié)點(diǎn)的數(shù)據(jù)元素為整型，且按值遞增有序存放。給定兩個(gè)整數(shù)a和b，且aA插入B刪除C排序D定位5.已知指針p和q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。假設(shè)指針s指向另一

2、個(gè)單鏈表中某個(gè)結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語(yǔ)句為( ) 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；6若線性表的插入和刪除操作頻繁地在表頭或表尾位置進(jìn)行，則更適宜采用的存儲(chǔ)結(jié)構(gòu)為（）A無(wú)頭結(jié)點(diǎn)的雙向鏈表B帶尾指針的循環(huán)鏈表C無(wú)頭結(jié)點(diǎn)的單鏈表D帶頭指針的循環(huán)鏈表7.在下列對(duì)順序表進(jìn)行的操作中，算法時(shí)間復(fù)雜度為O(1)的是（）A.訪問(wèn)第i個(gè)元素的前驅(qū)（1i）B.在第i個(gè)元素之后插入一個(gè)新元素(n1)iC.刪除第i個(gè)元素(n)i

3、1D.對(duì)順序表中元素進(jìn)行排序8.在鏈表的結(jié)點(diǎn)中，數(shù)據(jù)元素所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)量之比稱作_。8鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是借助_來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。10在一個(gè)長(zhǎng)度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)。11假設(shè)帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表中僅設(shè)尾指針L，則在第1個(gè)結(jié)點(diǎn)之前插入指針s所指結(jié)點(diǎn)的語(yǔ)句依次是_ _；_。12已知head為帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針，鏈表中的數(shù)據(jù)元素依次為（a1，a2,a3,a4,a n）,A為指向空的順序表的指針。閱讀以下程序段，并回答問(wèn)題：（1）寫出執(zhí)行下列程序段后的順序表A中的數(shù)據(jù)元素；（2）簡(jiǎn)要敘述該程序段的功能。if(head-n

4、ext!=head)p=head-next;A-length=0;while(p-next!=head)p=p-next;A-dataA-length +=p-data;if(p-next!=head)p=p-next;(1)(2)13已知鏈串的存儲(chǔ)結(jié)構(gòu)描述如下：#define NodeSize 4typedef struct Node char data NodeSize;struct Node * next; * LinkStr;閱讀下列算法，并回答問(wèn)題：（1）t1和t2的串值分別為Chinese和China時(shí)，寫出f31(t1,t2)的返回值；（2）t1和t2的串值分別為Japan和Ja

5、panese時(shí)，寫出f31(t1,t2)的返回值；（3）t1和t2的串值都為string時(shí)，寫出f31(t1,t2)的返回值；（4）簡(jiǎn)述函數(shù)f31的功能。inf f31(LinkStr t1,LinkStr t2)/串值以0為結(jié)束符int i;while (1)for (i=0;iif (t1-datai= =0&t2-datai= =0return 0;if(t1-datai= =0)return 1;if(t2-datai= =0)return 1;if(t1-datait2-dataireturn 1;if(t1-datait1=t1-next;t2=t2-next;(1)(2)(3)(

6、4)14已知用有序鏈表存儲(chǔ)整數(shù)集合的元素。閱讀算法f30，并回答下列問(wèn)題：（1）寫出執(zhí)行f30（a,b）的返回值，其中a和b分別為指向存儲(chǔ)集合2，4，5，7，9，12和2，4，5，7，9的鏈表的頭指針；（2）簡(jiǎn)述算法f30的功能；（3）寫出算法f30的時(shí)間復(fù)雜度。int f30(LinkList ha,LinkList hb)/LinkList是帶有頭結(jié)點(diǎn)的單鏈表/ha和hb分別為指向存儲(chǔ)兩個(gè)有序整數(shù)集合的鏈表的頭指針LinkList pa,pb;pa=ha-next;pb=hb-next;while(pa & pb & pa-data=pb-data) pa=pa-next;pb=pb-next;if(pa=NULL & pb=NULL) return 1;else return 0;(1)(2)(3)15假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示有序表，單鏈表的類型定義如下：typedef struct nodeDataType data;struct node *nextLinkNode, *LinkList;編寫算法，從有序表A中刪除所有和有序表B中元素相同的結(jié)點(diǎn)。16.假設(shè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針為head,則該鏈表為空的判定條件是（）A.head= =NULLB.headnext= =NULLC.head!=NULLD.headnext= =head