數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題

數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:（按照自己的情況選作部分習(xí)題，不要抄襲）第二章習(xí)題順序存儲(chǔ)線性表一判斷題1．線性表的邏輯順序與存儲(chǔ)順序總是一致的。×2．順序存儲(chǔ)的線性表可以按序號(hào)隨機(jī)存取。√3．順序表的插入和刪除操作不需要付出很大的時(shí)間代價(jià)，因?yàn)槊看尾僮髌骄挥薪话氲脑匦枰苿?dòng)。×4．線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對(duì)象。√5．在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰?！?．在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)?！潭芜x題(請(qǐng)從下列A，B，C，D選項(xiàng)中選擇一項(xiàng))1．線性表是(A)。(A)一個(gè)有限序列，可以為空；(B)一個(gè)有限序列，不能為空；(C)一個(gè)無(wú)限序列，可以為空；(D)一個(gè)無(wú)序序列，不能為空。2．對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作都是等概率的。插入一個(gè)元素時(shí)平均要移動(dòng)表中的（A）個(gè)元素。(A)n/2(B)n+1/2(C)n-1/2(D)n三填空題1．在順序表中做插入操作時(shí)首先檢查_(kāi)__表是否滿了______________。四算法設(shè)計(jì)題設(shè)線性表存放在向量A[arrsize]的前elenum個(gè)分量中，且遞增有序。試寫(xiě)一算法，將x插入到線性表的適當(dāng)位置上，以保持線性表的有序性。并且分析算法的時(shí)間復(fù)雜度。已知一順序表A，其元素值非遞減有序排列，編寫(xiě)一個(gè)函數(shù)刪除順序表中多余的值相同的元素。編寫(xiě)一個(gè)函數(shù)，從一給定的順序表A中刪除值在x~y(x<=y)之間的所有元素，要求以較高的效率來(lái)實(shí)現(xiàn)。提示：可以先將順序表中所有值在x~y之間的元素置成一個(gè)特殊的值，并不立即刪除它們，然后從最后向前依次掃描，發(fā)現(xiàn)具有特殊值的元素后，移動(dòng)其后面的元素將其刪除掉。線性表中有n個(gè)元素，每個(gè)元素是一個(gè)字符，現(xiàn)存于向量R[n]中，試寫(xiě)一算法，使R中的字符按字母字符、數(shù)字字符和其它字符的順序排列。要求利用原來(lái)的存儲(chǔ)空間，元素移動(dòng)次數(shù)最小。（研54）線性表用順序存儲(chǔ)，設(shè)計(jì)一個(gè)算法，用盡可能少的輔助存儲(chǔ)空間將順序表中前m個(gè)元素和后n個(gè)元素進(jìn)行整體互換。即將線性表（a1,a2,…,am,b1,b2,…,bn）改變?yōu)椋海╞1,b2,…,bn,a1,a2,…,am）。五上機(jī)實(shí)習(xí)題目約瑟夫環(huán)問(wèn)題約瑟夫環(huán)問(wèn)題：設(shè)編號(hào)為1，2，3，……，n的n(n>0)個(gè)人按順時(shí)針?lè)较驀蝗?，每個(gè)人持有一個(gè)正整數(shù)密碼。開(kāi)始時(shí)任選一個(gè)正整數(shù)做為報(bào)數(shù)上限m，從第一個(gè)人開(kāi)始順時(shí)針?lè)较蜃?起順序報(bào)數(shù)，報(bào)到m是停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m值，從他的下一個(gè)人開(kāi)始重新從1報(bào)數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設(shè)計(jì)一個(gè)程序模擬此過(guò)程，求出出列編號(hào)序列。package算法設(shè)計(jì);importimportimportpublicclassYueSeFu{publicstaticvoidmain(String[]args){Scannerscan=newScanner;"請(qǐng)輸入總?cè)藬?shù)：");inttotalNum=();"請(qǐng)輸入報(bào)數(shù)的大小：");intcycleNum=();yuesefu(totalNum,cycleNum);();}publicstaticvoidyuesefu(inttotalNum,intcountNum){鏈表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除最后一個(gè)元素，則采用(D)存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。(A)單鏈表(B)雙鏈表(C)單循環(huán)鏈表(D)帶頭結(jié)點(diǎn)的雙循環(huán)鏈表循環(huán)鏈表的主要優(yōu)點(diǎn)是(D)。(A)不在需要頭指針了(B)已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到他的直接前趨(C)在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開(kāi)(D)從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表下面關(guān)于線性表的敘述錯(cuò)誤的是(B)。線性表采用順序存儲(chǔ)，必須占用一片地址連續(xù)的單元；線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作；線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片地址連續(xù)的單元；線性表采用鏈?zhǔn)酱鎯?chǔ)，不便于進(jìn)行插入和刪除操作；單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了（C）。(A)使單鏈表至少有一個(gè)結(jié)點(diǎn)(B)標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置（C）方便運(yùn)算的實(shí)現(xiàn)(D)說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（D）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。(A)單鏈表(B)僅有頭指針的單循環(huán)鏈表(C)雙鏈表(D)僅有尾指針的單循環(huán)鏈表若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間（C）。(A)單鏈表(B)順序表(C)雙鏈表(D)單循環(huán)鏈表三填空題1．帶頭結(jié)點(diǎn)的單鏈表H為空的條件是__H->next==NULL_____。非空單循環(huán)鏈表L中*p是尾結(jié)點(diǎn)的條件是___p->next==L________。3．在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)由指針f所指結(jié)點(diǎn)，應(yīng)執(zhí)行s->next=__p->next___;和p->next=____s_________的操作。4．在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)由指針f所指結(jié)點(diǎn)，可執(zhí)行以下操作：s->next=_p->next_______;p->next=s;t=p->data;p->data=___s->data________;s->data=____t_______;四算法設(shè)計(jì)題1.已知帶頭結(jié)點(diǎn)的單鏈表L中的結(jié)點(diǎn)是按整數(shù)值遞增排列的，試寫(xiě)一算法，將值為x的結(jié)點(diǎn)插入到表L中，使得L仍然有序。并且分析算法的時(shí)間復(fù)雜度。packagexiti; classLii{ intdata; Liinext; publicLii(){ data=0; } publicLii(intid){ data=id; } publicvoiddisplay(){ ""); } } classLii_2{ publicLiifirst; publicLii_2(){ first=newLii(); } publicbooleanisEmpty(){ return==null); } publicbooleaninsert_2(intid){ Liinewnode=newLii(id); Liip=first; while!=null&& p=; =; =newnode; returntrue; } publicvoidlistdisplay(){ Liip=first; "顯示鏈表："); while(p!=null){ (); p=; } "**************"); } } publicclassL{ publicstaticvoidmain(String[]args){ Lii_2s1=newLii_2(); for(inti=1;i<=9;i=i+2){ (i); } (); (2); (); }}時(shí)間復(fù)雜度：O(elenum)2.假設(shè)有兩個(gè)已排序的單鏈表A和B，編寫(xiě)一個(gè)函數(shù)將他們合并成一個(gè)鏈表C而不改變其排序性。packagexiti1;classlink{ intdata;假設(shè)長(zhǎng)度大于1的循環(huán)單鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，p為指向該鏈表中某一結(jié)點(diǎn)的指針，編寫(xiě)一個(gè)函數(shù)刪除該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。4.已知兩個(gè)單鏈表A和B分別表示兩個(gè)集合，其元素遞增排列，編寫(xiě)一個(gè)函數(shù)求出A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲(chǔ)。packagexiti;classlink{ publicintdata;設(shè)有一個(gè)雙向鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和next域外，還有一個(gè)訪問(wèn)頻度f(wàn)req域，在鏈表被起用之前，該域其值初始化為零。每當(dāng)在鏈表進(jìn)行一次Locata(L,x)運(yùn)算后，令值為x的結(jié)點(diǎn)中的freq域增1，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問(wèn)頻度的遞減序列排列，以便使頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭。試寫(xiě)一個(gè)算法滿足上述要求的Locata(L,x)算法。五上機(jī)實(shí)習(xí)題目一元多項(xiàng)式的相加提示：一元多項(xiàng)式的表示問(wèn)題：對(duì)于任意一元多項(xiàng)式：Pn(x)=P0+P1X1+P2X2+…+PiXi+…+PnXn可以抽象為一個(gè)由“系數(shù)-指數(shù)”對(duì)構(gòu)成的線性表，且線性表中各元素的指數(shù)項(xiàng)是遞增的：P=((P0,0),(P1,1),(P2,2),…,(Pn,n))(2)用一個(gè)單鏈表表示上述線性表，結(jié)點(diǎn)結(jié)構(gòu)為：coefexpnexttypedefsturctnodecoefexpnext{floatcoef;/*系數(shù)域*/intexp;/*指數(shù)域*/structnode*next;/*指針域*/}PloyNode;package一元多項(xiàng)式的加法;import一元多項(xiàng)式的加法.;publicclassLinkedAdd{publicNodeadd(Eleme1,Eleme2){Nodepre=();Nodeqre=();Nodep=;Nodeq=;Noderesult=p;while(p!=null&&q!=null){if<{pre=p;p=;}elseif>{Nodetemp=;=q;=p;q=temp;}else{=+;if==0){=;p=;}else{pre=p;p=;}=;q=;}}if(q!=null){=q;}returnresult;}publicstaticvoidmain(String[]args){Elemnode1=newElem();(7,0);(12,3);(2,8);(5,12);Elemnode2=newElem();(4,1);(6,3);(2,8);(5,20);(7,28);LinkedAddl=newLinkedAdd();Nodenode=(node1,node2);while(node!=null){"coef:"++"exp:"+;node=;}}}package一元多項(xiàng)式的加法;classElem{publicclassNode{publicintcoef;/