數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題1/2〔按照自己的情況選作部分習(xí)題,不要抄襲第二章習(xí)題順序存儲線性表一判斷題1．線性表的邏輯順序與存儲順序總是一致的。×2．順序存儲的線性表可以按序號隨機(jī)存取?！?．順序表的插入和刪除操作不需要付出很大的時間代價,因為每次操作平均只有近一半的元素需要移動?！?．線性表中的元素可以是各種各樣的,但同一線性表中的數(shù)據(jù)元素具有相同的特性,因此是屬于同一數(shù)據(jù)對象?！?．在線性表的順序存儲結(jié)構(gòu)中,邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰?！?．在線性表的順序存儲結(jié)構(gòu)中,插入和刪除時,移動元素的個數(shù)與該元素的位置有關(guān)?！潭芜x題<請從下列A,B,C,D選項中選擇一項>1．線性表是<A>。<A>一個有限序列,可以為空；<B>一個有限序列,不能為空；<C>一個無限序列,可以為空；<D>一個無序序列,不能為空。2．對順序存儲的線性表,設(shè)其長度為n,在任何位置上插入或刪除操作都是等概率的。插入一個元素時平均要移動表中的〔A個元素。<A>n/2<B>n+1/2<C>n-1/2<D>n三填空題1．在順序表中做插入操作時首先檢查___表是否滿了______________。四算法設(shè)計題設(shè)線性表存放在向量A[arrsize]的前elenum個分量中,且遞增有序。試寫一算法,將x插入到線性表的適當(dāng)位置上,以保持線性表的有序性。并且分析算法的時間復(fù)雜度。已知一順序表A,其元素值非遞減有序排列,編寫一個函數(shù)刪除順序表中多余的值相同的元素。編寫一個函數(shù),從一給定的順序表A中刪除值在x~y<x<=y>之間的所有元素,要求以較高的效率來實現(xiàn)。提示：可以先將順序表中所有值在x~y之間的元素置成一個特殊的值,并不立即刪除它們,然后從最后向前依次掃描,發(fā)現(xiàn)具有特殊值的元素后,移動其后面的元素將其刪除掉。數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第1頁。線性表中有n個元素,每個元素是一個字符,現(xiàn)存于向量R[n]中,試寫一算法,使R數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第1頁。線性表用順序存儲,設(shè)計一個算法,用盡可能少的輔助存儲空間將順序表中前m個元素和后n個元素進(jìn)行整體互換。即將線性表〔a1,a2,…,am,b1,b2,…,bn改變?yōu)椋骸瞓1,b2,…,bn,a1,a2,…,am。五上機(jī)實習(xí)題目約瑟夫環(huán)問題約瑟夫環(huán)問題：設(shè)編號為1,2,3,……,n的n<n>0>個人按順時針方向圍坐一圈,每個人持有一個正整數(shù)密碼。開始時任選一個正整數(shù)做為報數(shù)上限m,從第一個人開始順時針方向自1起順序報數(shù),報到m是停止報數(shù),報m的人出列,將他的密碼作為新的m值,從他的下一個人開始重新從1報數(shù)。如此下去,直到所有人全部出列為止。令n最大值取30。要求設(shè)計一個程序模擬此過程,求出出列編號序列。package算法設(shè)計;importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;publicclassYueSeFu{publicstaticvoidmain<String[]args>{Scannerscan=newScanner<System.in>;System.out.print<"請輸入總?cè)藬?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;數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第2頁。數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第2頁。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>;}}}}鏈?zhǔn)酱鎯€性表一判斷題1．在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中,邏輯上相鄰的元素在物理位置上不一定相鄰。×2．線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)?！?．線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的。√4．在單鏈表中,要取得某個元素,只要知道該元素的指針即可,因此,單鏈表是隨機(jī)存取的存儲結(jié)構(gòu)?！炼芜x題<請從下列A,B,C,D選項中選擇一項>1．線性表是<A>。<A>一個有限序列,可以為空；<B>一個有限序列,不能為空；<C>一個無限序列,可以為空；<D>一個無序序列,不能為空。2．線性表采用鏈?zhǔn)酱鎯r,其地址<D>。<A>必須是連續(xù)的；<B>部分地址必須是連續(xù)的；<C>一定是不連續(xù)的；<D>連續(xù)與否均可以。3．用鏈表表示線性表的優(yōu)點是〔C。<A>便于隨機(jī)存取<B>花費(fèi)的存儲空間較順序存儲少<C>便于插入和刪除<D>數(shù)據(jù)元素的物理順序與邏輯順序相同4.某鏈表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后一個元素,則采用<D>存儲方式最節(jié)省運(yùn)算時間。<A>單鏈表數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第3頁。<B>數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第3頁。<C>單循環(huán)鏈表<D>帶頭結(jié)點的雙循環(huán)鏈表循環(huán)鏈表的主要優(yōu)點是<D>。<A>不在需要頭指針了<B>已知某個結(jié)點的位置后,能夠容易找到他的直接前趨<C>在進(jìn)行插入、刪除運(yùn)算時,能更好的保證鏈表不斷開<D>從表中的任意結(jié)點出發(fā)都能掃描到整個鏈表下面關(guān)于線性表的敘述錯誤的是<B>。線性表采用順序存儲,必須占用一片地址連續(xù)的單元；線性表采用順序存儲,便于進(jìn)行插入和刪除操作；線性表采用鏈?zhǔn)酱鎯?不必占用一片地址連續(xù)的單元；線性表采用鏈?zhǔn)酱鎯?不便于進(jìn)行插入和刪除操作；單鏈表中,增加一個頭結(jié)點的目的是為了〔C。<A>使單鏈表至少有一個結(jié)點<B>標(biāo)識表結(jié)點中首結(jié)點的位置〔C方便運(yùn)算的實現(xiàn)<D>說明單鏈表是線性表的鏈?zhǔn)酱鎯θ裟尘€性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素,則采用〔D存儲方式最節(jié)省運(yùn)算時間。<A>單鏈表<B>僅有頭指針的單循環(huán)鏈表<C>雙鏈表<D>僅有尾指針的單循環(huán)鏈表若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素,則采用〔存儲方式最節(jié)省運(yùn)算時間〔C。<A>單鏈表<B>順序表<C>雙鏈表<D>單循環(huán)鏈表三填空題1．帶頭結(jié)點的單鏈表H為空的條件是__H->next==NULL_____。非空單循環(huán)鏈表L中*p是尾結(jié)點的條件是___p->next==L________。3．在一個單鏈表中p所指結(jié)點之后插入一個由指針f所指結(jié)點,應(yīng)執(zhí)行s->next=__p->next___;和p->next=____s_________的操作。4．在一個單鏈表中p所指結(jié)點之前插入一個由指針f所指結(jié)點,可執(zhí)行以下操作：s->next=_p->next_______;p->next=s;t=p->data;p->data=___s->data________;s->data=____t_______;四算法設(shè)計題數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第4頁。1.已知帶頭結(jié)點的單鏈表L中的結(jié)點是按整數(shù)值遞增排列的,試寫一算法,將值為x的結(jié)點插入到表L中,使得L數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第4頁。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; }數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第5頁。 System.out數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第5頁。 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<>; }}時間復(fù)雜度：O<elenum>2.假設(shè)有兩個已排序的單鏈表A和B,編寫一個函數(shù)將他們合并成一個鏈表C而不改變其排序性。packagexiti1;classlink{intdata;//數(shù)據(jù)域〔結(jié)點關(guān)鍵字 linknext;//指針域〔指向下一結(jié)點publiclink<intid>{//結(jié)點構(gòu)造方法 data=id;//結(jié)點構(gòu)造方法 }publicvoiddisplay<>{//顯示自身的數(shù)據(jù)域 System.out.print<data+"">; }}classlink_1{ linkfirst;//單鏈表的頭指針publiclink_1<>{//構(gòu)造方法 first=null;//空單鏈表,頭指針為空 } //從單鏈表最前面插入一個新結(jié)點,作為第一個結(jié)點publicbooleaninsert_1<intid>{ linknewLink=newlink<id>; linkp;if<first==null>數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第6頁。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<"*****************">; }數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第7頁。數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第7頁。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.假設(shè)長度大于1的循環(huán)單鏈表中,既無頭結(jié)點也無頭指針,p為指向該鏈表中某一結(jié)點的指針,編寫一個函數(shù)刪除該結(jié)點的前趨結(jié)點。數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第8頁。4.已知兩個單鏈表A和B分別表示兩個集合,其元素遞增排列,編寫一個函數(shù)求出A和B的交集C,要求C數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第8頁。packagexiti;classlink{publicintdata;//數(shù)據(jù)域〔結(jié)點關(guān)鍵字publiclinknext;////指針域〔指向下一結(jié)點publiclink<intid>{//結(jié)點構(gòu)造方法 data=id; }publicvoidDisplay<>{//顯示自身的數(shù)據(jù)域 System.out.print<data+"">; }}classlinkList{ linkfirst;//單鏈表的頭指針publiclinkList<>{//構(gòu)造方法 first=null;//空單鏈表,頭指針為空 } //在單鏈表尾部插入一個新結(jié)點publicbooleaninsertBack<intid>{ linknewlink=newlink<id>;//誕生新結(jié)點newlink4 linkp;//輔助結(jié)點指針 if<first==null> first=newlink;else{ p=first;//指向第一結(jié)點while<p.next!=null> p=p.next;//把p移到最后一個結(jié)點 p.next=newlink;//把新結(jié)點接在p所指結(jié)點的后面 } returntrue; }publicvoidlistDisplay<>{//顯示鏈表 linkp=first;//指向第一個結(jié)點 System.out.println<"顯示鏈表：">;while<p!=null>{ p.Display<>;//顯示結(jié)點 p=p.next; }數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第9頁。 System.out數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第9頁。 }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<>; }}數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第10頁。5.設(shè)有一個雙向鏈表,每個結(jié)點中除有prior、data和next域外,還有一個訪問頻度freq域,在鏈表被起用之前,該域其值初始化為零。每當(dāng)在鏈表進(jìn)行一次Locata<L,x>運(yùn)算后,令值為x的結(jié)點中的freq域增1,并調(diào)整表中結(jié)點的次序,使其按訪問頻度的遞減序列排列,以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一個算法滿足上述要求的Locata<L,x>數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第10頁。五上機(jī)實習(xí)題目一元多項式的相加提示：一元多項式的表示問題：對于任意一元多項式：Pn<x>=P0+P1X1+P2X2+…+PiXi+…+PnXn可以抽象為一個由"系數(shù)-指數(shù)"對構(gòu)成的線性表,且線性表中各元素的指數(shù)項是遞增的：P=<<P0,0>,<P1,1>,<P2,2>,…,<Pn,n>><2>用一個單鏈表表示上述線性表,結(jié)點結(jié)構(gòu)為：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;數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第11頁。if<p.coef==0>{數(shù)據(jù)結(jié)構(gòu)Java版第二章習(xí)題全文共13頁，當(dāng)前為第11頁。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>;