數(shù)據(jù)結構Java版第二章習題

PAGEPAGE16（按照自己的情況選作部分習題，不要抄襲）第二章習題順序存儲線性表一判斷題1．線性表的邏輯順序與存儲順序總是一致的?！?．順序存儲的線性表可以按序號隨機存取。√3．順序表的插入和刪除操作不需要付出很大的時間代價，因為每次操作平均只有近一半的元素需要移動?！?．線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對象?！?．在線性表的順序存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。×6．在線性表的順序存儲結構中，插入和刪除時，移動元素的個數(shù)與該元素的位置有關?！潭芜x題(請從下列A，B，C，D選項中選擇一項)1．線性表是(A)。(A)一個有限序列，可以為空；(B)一個有限序列，不能為空；(C)一個無限序列，可以為空；(D)一個無序序列，不能為空。2．對順序存儲的線性表，設其長度為n，在任何位置上插入或刪除操作都是等概率的。插入一個元素時平均要移動表中的（A）個元素。(A)n/2(B)n+1/2(C)n-1/2(D)n三填空題1．在順序表中做插入操作時首先檢查___表是否滿了______________。四算法設計題設線性表存放在向量A[arrsize]的前elenum個分量中，且遞增有序。試寫一算法，將x插入到線性表的適當位置上，以保持線性表的有序性。并且分析算法的時間復雜度。已知一順序表A，其元素值非遞減有序排列，編寫一個函數(shù)刪除順序表中多余的值相同的元素。編寫一個函數(shù)，從一給定的順序表A中刪除值在x~y(x<=y)之間的所有元素，要求以較高的效率來實現(xiàn)。提示：可以先將順序表中所有值在x~y之間的元素置成一個特殊的值，并不立即刪除它們，然后從最后向前依次掃描，發(fā)現(xiàn)具有特殊值的元素后，移動其后面的元素將其刪除掉。線性表中有n個元素，每個元素是一個字符，現(xiàn)存于向量R[n]中，試寫一算法，使R中的字符按字母字符、數(shù)字字符和其它字符的順序排列。要求利用原來的存儲空間，元素移動次數(shù)最小。（研54）線性表用順序存儲，設計一個算法，用盡可能少的輔助存儲空間將順序表中前m個元素和后n個元素進行整體互換。即將線性表（a1,a2,…,am,b1,b2,…,bn）改變?yōu)椋海╞1,b2,…,bn,a1,a2,…,am）。五上機實習題目約瑟夫環(huán)問題約瑟夫環(huán)問題：設編號為1，2，3，……，n的n(n>0)個人按順時針方向圍坐一圈，每個人持有一個正整數(shù)密碼。開始時任選一個正整數(shù)做為報數(shù)上限m，從第一個人開始順時針方向自1起順序報數(shù)，報到m是停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的下一個人開始重新從1報數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設計一個程序模擬此過程，求出出列編號序列。package算法設計;importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;publicclassYueSeFu{publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);System.out.print("請輸入總人數(shù)：");inttotalNum=scan.nextInt();System.out.print("請輸入報數(shù)的大?。?);intcycleNum=scan.nextInt();yuesefu(totalNum,cycleNum);scan.close();}publicstaticvoidyuesefu(inttotalNum,intcountNum){//初始化人數(shù)List<Integer>start=newArrayList<Integer>();for(inti=1;i<=totalNum;i++){start.add(i);}//從第K個開始計數(shù)intk=0;while(start.size()>0){k=k+countNum;//第m人的索引位置k=k%(start.size())-1;//判斷是否到隊尾if(k<0){System.out.println(start.get(start.size()-1));start.remove(start.size()-1);k=0;}else{System.out.println(start.get(k));start.remove(k);}}}}鏈式存儲線性表一判斷題1．在線性表的鏈式存儲結構中，邏輯上相鄰的元素在物理位置上不一定相鄰。×2．線性表的鏈式存儲結構優(yōu)于順序存儲結構。×3．線性表的鏈式存儲結構是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的。√4．在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構?！炼芜x題(請從下列A，B，C，D選項中選擇一項)1．線性表是(A)。(A)一個有限序列，可以為空；(B)一個有限序列，不能為空；(C)一個無限序列，可以為空；(D)一個無序序列，不能為空。2．線性表采用鏈式存儲時，其地址(D)。(A)必須是連續(xù)的；(B)部分地址必須是連續(xù)的；(C)一定是不連續(xù)的；(D)連續(xù)與否均可以。3．用鏈表表示線性表的優(yōu)點是（C）。(A)便于隨機存取(B)花費的存儲空間較順序存儲少(C)便于插入和刪除(D)數(shù)據(jù)元素的物理順序與邏輯順序相同4.某鏈表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后一個元素，則采用(D)存儲方式最節(jié)省運算時間。(A)單鏈表(B)雙鏈表(C)單循環(huán)鏈表(D)帶頭結點的雙循環(huán)鏈表循環(huán)鏈表的主要優(yōu)點是(D)。(A)不在需要頭指針了(B)已知某個結點的位置后，能夠容易找到他的直接前趨(C)在進行插入、刪除運算時，能更好的保證鏈表不斷開(D)從表中的任意結點出發(fā)都能掃描到整個鏈表下面關于線性表的敘述錯誤的是(B)。線性表采用順序存儲，必須占用一片地址連續(xù)的單元；線性表采用順序存儲，便于進行插入和刪除操作；線性表采用鏈式存儲，不必占用一片地址連續(xù)的單元；線性表采用鏈式存儲，不便于進行插入和刪除操作；單鏈表中，增加一個頭結點的目的是為了（C）。(A)使單鏈表至少有一個結點(B)標識表結點中首結點的位置（C）方便運算的實現(xiàn)(D)說明單鏈表是線性表的鏈式存儲若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（D）存儲方式最節(jié)省運算時間。(A)單鏈表(B)僅有頭指針的單循環(huán)鏈表(C)雙鏈表(D)僅有尾指針的單循環(huán)鏈表若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（）存儲方式最節(jié)省運算時間（C）。(A)單鏈表(B)順序表(C)雙鏈表(D)單循環(huán)鏈表三填空題1．帶頭結點的單鏈表H為空的條件是__H->next==NULL_____。非空單循環(huán)鏈表L中*p是尾結點的條件是___p->next==L________。3．在一個單鏈表中p所指結點之后插入一個由指針f所指結點，應執(zhí)行s->next=__p->next___;和p->next=____s_________的操作。4．在一個單鏈表中p所指結點之前插入一個由指針f所指結點，可執(zhí)行以下操作：s->next=_p->next_______;p->next=s;t=p->data;p->data=___s->data________;s->data=____t_______;四算法設計題1.已知帶頭結點的單鏈表L中的結點是按整數(shù)值遞增排列的，試寫一算法，將值為x的結點插入到表L中，使得L仍然有序。并且分析算法的時間復雜度。packagexiti; classLii{ intdata; Liinext; publicLii(){ data=0; } publicLii(intid){ data=id; } publicvoiddisplay(){ System.out.print(data+""); } } classLii_2{ publicLiifirst; publicLii_2(){ first=newLii(); } publicbooleanisEmpty(){ return(first.next==null); } publicbooleaninsert_2(intid){ Liinewnode=newLii(id); Liip=first; while(p.next!=null&&p.next.data<id) p=p.next; newnode.next=p.next; p.next=newnode; returntrue; } publicvoidlistdisplay(){ Liip=first; System.out.println("顯示鏈表："); while(p!=null){ p.display(); p=p.next; } System.out.println(); System.out.println("**************"); } } publicclassL{ publicstaticvoidmain(String[]args){ Lii_2s1=newLii_2(); for(inti=1;i<=9;i=i+2){ s1.insert_2(i); } s1.listdisplay(); s1.insert_2(2); s1.listdisplay(); }}時間復雜度：O(elenum)2.假設有兩個已排序的單鏈表A和B，編寫一個函數(shù)將他們合并成一個鏈表C而不改變其排序性。packagexiti1;classlink{ intdata;//數(shù)據(jù)域（結點關鍵字） linknext;//指針域（指向下一結點） publiclink(intid){//結點構造方法 data=id;//結點構造方法 } publicvoiddisplay(){//顯示自身的數(shù)據(jù)域 System.out.print(data+""); }}classlink_1{ linkfirst;//單鏈表的頭指針 publiclink_1(){//構造方法 first=null;//空單鏈表，頭指針為空 } //從單鏈表最前面插入一個新結點，作為第一個結點 publicbooleaninsert_1(intid){ linknewLink=newlink(id); linkp; if(first==null) first=newLink; else{ p=first; while(p.next!=null)p=p.next; p.next=newLink; } returntrue; } publicintget(intindex){ linkp=first; if(p!=null&&index>=0){ intj=0; while(p!=null&&j<index){ j++; p=p.next; } if(p!=null) returnp.data; } return0; } publicintLength(){ linkp=first; inti=0; while(p!=null){ p=p.next; i++; } returni; } //顯示全部鏈表 publicvoidlistdisplay(){ linkp=first; System.out.println("顯示鏈表："); while(p!=null){ p.display(); p=p.next; } System.out.println(); System.out.println("*****************"); }}publicclassAB{ publicstaticlink_1Merge(link_1A,link_1B){ intl=A.Length()+B.Length(); link_1C=newlink_1(); intj=0,iA=0,iB=0; while(iA<A.Length()&&iB<B.Length()){ if(A.get(iA)<B.get(iB)) C.insert_1(A.get(iA++)); else C.insert_1(B.get(iB++)); } for(;iA<A.Length();) C.insert_1(A.get(iA++)); for(;iB<B.Length();) C.insert_1(B.get(iB++)); returnC; } publicstaticvoidmain(String[]args){ link_1s1=newlink_1(); link_1s2=newlink_1(); s1.insert_1(12); s1.insert_1(15); s1.insert_1(19); s1.insert_1(20); s1.insert_1(23); s1.listdisplay(); s2.insert_1(10); s2.insert_1(14); s2.insert_1(17); s2.insert_1(21); s2.insert_1(26); s2.listdisplay(); link_1s3=Merge(s1,s2); s3.listdisplay(); }}3.假設長度大于1的循環(huán)單鏈表中，既無頭結點也無頭指針，p為指向該鏈表中某一結點的指針，編寫一個函數(shù)刪除該結點的前趨結點。4.已知兩個單鏈表A和B分別表示兩個集合，其元素遞增排列，編寫一個函數(shù)求出A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲。packagexiti;classlink{ publicintdata;//數(shù)據(jù)域（結點關鍵字） publiclinknext;////指針域（指向下一結點） publiclink(intid){//結點構造方法 data=id; } publicvoidDisplay(){//顯示自身的數(shù)據(jù)域 System.out.print(data+""); }}classlinkList{ linkfirst;//單鏈表的頭指針 publiclinkList(){//構造方法 first=null;//空單鏈表，頭指針為空 } //在單鏈表尾部插入一個新結點 publicbooleaninsertBack(intid){ linknewlink=newlink(id);//誕生新結點newlink4 linkp;//輔助結點指針 if(first==null) first=newlink; else{ p=first;//指向第一結點 while(p.next!=null) p=p.next;//把p移到最后一個結點 p.next=newlink;//把新結點接在p所指結點的后面 } returntrue; } publicvoidlistDisplay(){//顯示鏈表 linkp=first;//指向第一個結點 System.out.println("顯示鏈表："); while(p!=null){ p.Display();//顯示結點 p=p.next; } System.out.println("*******"); } publiclinkListinterSection(linkListA,linkListB){ linkListC; linkpa,pb; C=newlinkList(); pa=A.first; pb=B.first; while(pa!=null){ while(pb!=null){//和B鏈表的每個元素遍歷 if(pa.data==pb.data)//相等的時候給C鏈表插入pa.fd C.insertBack(pa.data); pb=pb.next; } pa=pa.next; pb=B.first; } returnC; }}publicclassABC{ publicstaticvoidmain(String[]args){ linkListA=newlinkList(); linkListB=newlinkList(); linkListC=newlinkList(); A.insertBack(10); A.insertBack(12); A.insertBack(15); A.insertBack(18); A.listDisplay(); B.insertBack(13); B.insertBack(10); B.insertBack(12); B.insertBack(18); B.listDisplay(); C=C.interSection(A,B); C.listDisplay(); }}5.設有一個雙向鏈表，每個結點中除有prior、data和next域外，還有一個訪問頻度freq域，在鏈表被起用之前，該域其值初始化為零。每當在鏈表進行一次Locata(L,x)運算后，令值為x的結點中的freq域增1，并調整表中結點的次序，使其按訪問頻度的遞減序列排列，以便使頻繁訪問的結點總是靠近表頭。試寫一個算法滿足上述要求的Locata(L,x)算法。五上機實習題目一元多項式的相加提示：一元多項式的表示問題：對于任意一元多項式：Pn(x)=P0+P1X1+P2X2+…+PiXi+…+PnXn可以抽象為一個由“系數(shù)-指數(shù)”對構成的線性表，且線性表中各元素的指數(shù)項是遞增的：P=((P0,0),(P1,1),(P2,2),…,(Pn,n))(2)用一個單鏈表表示上述線性表，結點結構為：coefexpnexttypedefsturctnodecoefexpnext{floatcoef;/*系數(shù)域*/intexp;/*指數(shù)域*/structnode*next;/*指針域*/}PloyNode;package一元多項式的加法;import一元多項式的加法.Elem.Node;publicclassLinkedAdd{publicNodeadd(Eleme1,Eleme2){Nodepre=e1.getNode();Nodeqre=e2.getNode();Nodep=pre.next;Nodeq=qre.next;Noderesult=p;while(p!=null&&q!=null){if(p.exp<q.exp){pre=p;p=p.next;}elseif(p.exp>q.exp){Nodetemp=q.next;pre.next=q;q.next=p;q=temp;}else{p.coef=p.coef+q.coef;if(p.coef==0){pre.next=p.next;p=pre.next;}else{pre=p;p=p.next;}qre.next=q.next;q=qre.next;}}if(q!=null){pre.next=q;}returnresult;}publicstaticvoidmain(String[]args){Elemnode1=newElem();node1.insert(7,0);node1.insert(12,3);node1.insert(2,8);node1.insert(5,12);Elemnode2=newElem();node2.insert(4,1);node2.insert(6,3);node2.insert(2,8);node2.insert(5,20);node2.insert(7,28);LinkedAddl=newLinkedAdd();Nodenode=l.add(node1,node2);while(node!=null){System.out.println("coef:"+node.coef+"exp:"+node.exp);node=node.next;}}}package一元多項式的加法;classElem{publicclassNode{publicintcoef;//系數(shù)publicintexp;//指數(shù)publicNodenext=null;//下一個節(jié)點publicNode(){coef=0;exp=0;}publicNode(intcoef,intexp){this.coef=coef;this.exp=exp;}}publicNodefirst=newNode();publicvoidinsert(intcoef,intexp){//添加節(jié)點Nodenode=newNode(coef,exp);