數(shù)據(jù)結(jié)構(gòu)第2章典型例題解析(完整版)
【正文】 、判斷題1．線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。pnext=s。 snext=pnext。 pnextprior=s?！敬鸢浮緼13．非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足 ?！敬鸢浮緽9．線性表的靜態(tài)鏈表存儲(chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比優(yōu)點(diǎn)是 。鏈表需要通過指針才能找到線性表的莫以指定序號(hào)的元素，需要一定的時(shí)間開銷?！敬鸢浮緼3．帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是 ?！敬鸢浮緾2．順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是 。A．順序表 B．雙鏈表C．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D．單循環(huán)鏈表【分析】某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算。【答案】B8．鏈表不具有的特點(diǎn)是 。A．O(i) B．O(1) C．O(n) D．O(i1)【分析】線性表以鏈接方式存儲(chǔ)時(shí)，訪問第i個(gè)位置元素從第一個(gè)元素開始移動(dòng)指針到第i個(gè)元素，移動(dòng)指針的次數(shù)為ni+1，即時(shí)間復(fù)雜度為O(n)。 pnextprior=s。 pnext=s。應(yīng)先執(zhí)行操作pnextprior=s，再執(zhí)行操作pnext=s。 D．pnext=s?！敬鸢浮空_3．鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。雖然兩種存儲(chǔ)結(jié)構(gòu)下的插入操作時(shí)間復(fù)雜度均為O(n)，但由于兩者的基本操作不同，因此不能說它們的執(zhí)行時(shí)間是相等的?！痉治觥恳?yàn)殪o態(tài)鏈表的存取特性與動(dòng)態(tài)鏈表是一樣的，只能順序地找到第i個(gè)元素，不能隨機(jī)地存取第i個(gè)元素，故其存取表中第i個(gè)元素的時(shí)間與i有關(guān)。pprior=s。 pprior=s。j++)A[j1]=A[j]。 L=Lnext。若原鏈表表示的線性表是(a1,a2,…,an)，則操作后表示的線性表為(a2,a3,…, an,a1)。頭結(jié)點(diǎn)的作用有兩個(gè)：一是使得對(duì)空表和非空表的處理得以統(tǒng)一。并且分析算法的時(shí)間復(fù)雜度。 i?！舅惴ā縱iod delepre(LNode *s){ LNode *p,*q。算法中指針p用來指向A中的當(dāng)前結(jié)點(diǎn)，指針q用來指向B中的當(dāng)前結(jié)點(diǎn)，將其值進(jìn)行比較，兩者相等時(shí)，屬于交集中的一個(gè)元素，兩者不等時(shí)，將其較小者跳過，繼續(xù)后面的比較。 q ) if (pdataqdata) p=pnext。 rnext=NULL。 if(Lnext){ p=Lnext。 snext=knext。 if(cur_b==NULL) { Return 0。 cur_a=cur_a224。 return 1。 cur_b224。 while(cur_a!=NULLamp。 } }}前兩個(gè)while循環(huán)和起來最多循環(huán)n次，第三個(gè)while循環(huán)最多循環(huán)n次，即刪除n個(gè)結(jié)點(diǎn)，故算法的時(shí)間復(fù)雜度為O(n)。 while (pdata=max){ s=p。 delete C。 sdata=pdata。 C=new LNode。 while (pnext==s){ q=p。 //找到的位置是插入位的下一位 (*num)++?！舅惴ā縄nsertSeq(DataType A[],int *num,DataType x){ //設(shè)num為表的最大下標(biāo) int i。5．在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，而不知道頭指針，能否將結(jié)點(diǎn)p從相應(yīng)的鏈表中刪除？若可以，其時(shí)間復(fù)雜度各為多少？【解答】單鏈表：若結(jié)點(diǎn)p有后繼結(jié)點(diǎn)，則可將結(jié)點(diǎn)p的后繼元素?cái)?shù)據(jù)放入結(jié)點(diǎn)p中，再將后繼結(jié)點(diǎn)刪除?！窘獯稹款^指針是一個(gè)指針變量，里面存放的是鏈表中首結(jié)點(diǎn)的地址，并以此來標(biāo)識(shí)一個(gè)鏈表。 while (pnext) p=pne
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1