數(shù)據(jù)結(jié)構(gòu)java語言描述課后答案

數(shù)據(jù)結(jié)構(gòu)java語言描述課后答案【篇一：數(shù)據(jù)機構(gòu)第一章一一java語言描述第1章緒論習(xí)題參考答案】概念題試述下列各組概念：⑴數(shù)據(jù)、數(shù)據(jù)兀素、數(shù)據(jù)項⑵數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)⑶數(shù)據(jù)類型、數(shù)據(jù)操作⑷算法、算法的時間復(fù)雜度、算法的空間復(fù)雜度參考答案：略試述數(shù)據(jù)結(jié)構(gòu)研究的3個方面的內(nèi)容。參考答案：數(shù)據(jù)結(jié)構(gòu)研究的3個方面分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算(操作)。3.試述集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖型結(jié)構(gòu)四種常用數(shù)據(jù)結(jié)構(gòu)的特性。參考答案：集合結(jié)構(gòu)：集合中數(shù)據(jù)元素之間除了“同屬于一個集合”的特性外，數(shù)據(jù)元素之間無其它關(guān)系，它們之間的關(guān)系是松散性的。線性結(jié)構(gòu)：線性結(jié)構(gòu)中數(shù)據(jù)元素之間存在“一對一”的關(guān)系。即若結(jié)構(gòu)非空，則它有且僅有一個開始結(jié)點和終端結(jié)點，開始結(jié)點沒有前趨但有一個后繼，終端結(jié)點沒有后繼但有一個前趨，其余結(jié)點有且僅有一個前驅(qū)和一個后繼。樹形結(jié)構(gòu)：樹形結(jié)構(gòu)中數(shù)據(jù)元素之間存在“一對多”的關(guān)系。即若結(jié)構(gòu)非空，則它有一個稱為根的結(jié)點，此結(jié)點無前驅(qū)結(jié)點，其余結(jié)點有且僅有一個前驅(qū)，所有結(jié)點都可以有多個后繼。圖形結(jié)構(gòu)：圖形結(jié)構(gòu)中數(shù)據(jù)元素之間存在“多對多”的關(guān)系。即若結(jié)構(gòu)非空，則在這種數(shù)據(jù)結(jié)構(gòu)中任何結(jié)點都可能有多個前驅(qū)和后繼。4.設(shè)有數(shù)據(jù)的邏輯結(jié)構(gòu)的二元組定義形式為b=(d,r)，其中d={a1,a2,?,an}，r={ai,ai+1|i=1,2,?，n-1}，請畫由此邏輯結(jié)構(gòu)對應(yīng)的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的示意圖。參考答案：順序存儲結(jié)構(gòu)示意圖如下：012?n-2n-1鏈式存儲結(jié)構(gòu)示意圖如下：w!==5?設(shè)一個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)如圖1.9所示，請寫出它的二元組w!==圖1.9第5題的邏輯結(jié)構(gòu)圖參考答案：它的二元組定義形式為b=（d，r），其中d={k1,k2,k3,k4,k5,k6,k7,k8,k9}，r=k1,k3,k1,k8,k2,k3k2,k4,k2,k5,k3,k9,k4,k6,k4,k7,k5,k6,k8,k9,k9,k7}。6.設(shè)有函數(shù)f(n)=3n2-n+4，請證明f(n)=o(n2)。書p16的定義可得f(n)=o(n2)。7.請比較下列函數(shù)的增長率，并按增長率遞增的順序排列下列函數(shù)：(1)2100(2)(3/2)n(3)(4/3)n(4)nn(5)n2/3(6)n3/2(7)n!(8)n⑼n(10)log2n(11)1/log2n(12)log2(log2n)(13)nlog2n(14)nlog2n參考答案：按增長率遞增的排列順序是:1/log2n2100log2(log2n)log2nn1/2n2/3nnlog2nn3/2nlog2n(4/3)n(3/2)nn!nn8.試確定下列程序段中有標記符號“*的語句行的語句頻度(其中n為正整數(shù))。⑴i=1;k=0;while(i=n-1){k+=10*i;//*i++;}⑵i=1;k=0;do{k+=10*i;//*i++;}while(i=n-1);⑶i=1;k=0;while(i=n-1){i++;k+=10*i;//*}⑷k=0;for(i=1;i=n;i++){for(j=1;j=i;j++)k++;//*}⑸i=1;j=0;while(i+j=n)(if(ij)j++；//*elsei++;}⑹x=n;y=0;//n是不小于1的常數(shù)while(x=(y+1)*(y+1)){y++;//*}⑺x=91;y=100;while(y0){if(x100){x-=10;y--;}//*elsex++;⑻a=1;m=1;while(an){m+=a;a*=3;//*}參考答案：1100log3n二、算法設(shè)計題1.有一個包括100個數(shù)據(jù)元素的數(shù)組，每個數(shù)據(jù)元素的值都是實|=>最|=>最據(jù)元素的值及其下標的算法，并分析算法的時間復(fù)雜度。參考答案：voidmax(double[]a){doublemax=a[0];//初始化最大值為數(shù)組中的第一個元素intindex=0;//for(inti=0;ia.length;i++){if(maxa[i]){max=a[i];index=i;}}=J

最system.out.println(最大的實數(shù)為：+max+\n=J

最為：+index);}此算法的時間復(fù)雜度為o(n)，其中n為數(shù)組的長度。2.試編寫一個求一元多項式pn(x)??axii?0ni的值pn(x0)的算法，并確定算法中每一條語句的執(zhí)行次數(shù)和整個算法的時間復(fù)雜度。輸入是ai(i=0J1,2,?,n-1)和x0，輸出為pn(x0)。參考答案：0doublegetpolynomialresult(double[]a,doublex)(//a是多項式中系數(shù)數(shù)組doubleresult=0;doublepowx=1;//臨時變量，用于減少計算x冪的計算次數(shù)for(inti=0;ia.length;i++){4result+=a[i]*powx;5powx*=x;}returnresult;8}語句1~7的執(zhí)行次數(shù)分別是:1、1、a.length+1、a.length、length、1、1此算法的時間復(fù)雜度為o(a.length)，其中a.length也是多項式中的項數(shù)。三、上機實踐題1.編寫一個實現(xiàn)將整型數(shù)組中的數(shù)據(jù)元素按值遞增的順序進行排序的java程序。參考答案:packagech01exercise;publicclassexercise1_3_1{publicint[]bubblesort(int[]a){//a為待排序的整數(shù)數(shù)組intn=a.length;booleanisexchange=true;//交換標志■=j最for(inti=0;in-1isexchange;i++){//最多做n-1■=j最isexchange=false;for(intj=0;jn-i-1;j++){//對當前無序區(qū)進行排序if(a[j]a[j+1]){//交換數(shù)據(jù)元素inttemp=a[j];a[j]=a[j+1];a[j+1]=temp;isexchange=true;//發(fā)生了交換，故將交換標志置為真}}if(!isexchange)break;//本趟排序未發(fā)生交換，提前終止算法}returna;}publicstaticvoidmain(string[]args){int[]values={49,38,65,97,76,13,27,49};system.out.println(排序前數(shù)組中數(shù)據(jù)元素：4938659776132749);system.out.print(排序后數(shù)組中數(shù)據(jù)元素：);exercise1_3_1e=newexercise1_3_1();values=e.bubblesort(values);for(inti=0;ivalues.length;i++)system.out.print(values[i]+);}}運行結(jié)果2.設(shè)計一個復(fù)數(shù)類，要求：(1)在復(fù)數(shù)內(nèi)部用雙精度浮點數(shù)定義其實部和虛部。給復(fù)數(shù)的實部，虛部為0;第3個構(gòu)造函數(shù)將兩個雙精度浮點數(shù)分別賦給復(fù)數(shù)的實部和虛部。編寫獲取和修改復(fù)數(shù)的實部和虛部的成員函數(shù)。編寫實現(xiàn)復(fù)數(shù)的減法、乘法運算的成員函數(shù)。設(shè)計一個測試主函數(shù)，使其實際運行驗證類中各成員函數(shù)的正確性。參考答案：packagech01exercise;//復(fù)數(shù)類classcomplex{【篇二：《數(shù)據(jù)結(jié)構(gòu)(java語言版)》試卷1】考試科目：《數(shù)據(jù)結(jié)構(gòu)》考試形式：閉卷適應(yīng)班級：軟開1431-1439，目a.2,3,4,1,5b.2,3,1,4,5c.5,4,1,3,2d.1,5,4,3,211、判斷一個循環(huán)隊列(m0為最大隊列長度(以元素為單位)，front和rear分，目別為隊列的隊頭指針和隊尾指針)為空隊列的條件是()。a.front==rearb.front!=rearc.front==(rear+1)%m0d.front!=(rear+1)%m0一、單項選擇（共20題，每題2分,共40分）12、判斷一個循環(huán)隊列（m0為最大隊列長度（以元素為單位），front和rear分別為隊列的隊頭指針和隊尾指針）1、以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？（）為滿隊列的條件是（）。a.隊列b.棧c.二叉樹d.線性表a.front==rearb.front!=rearc.front==（rear+1）%m0d.front!=（rear+1）%m02、（）不是算法的主要特性。金?輸入性》輸出性c?有窮性d.高效性13、串是一種特殊的線性表，其特殊性體現(xiàn)在（）。a?可以順序存儲b,數(shù)據(jù)元素是一個字符3、（）不是線性表的存儲結(jié)構(gòu)。c,可以鏈式存儲d?數(shù)據(jù)元素可以是多個字符a?叉鏈表b.單鏈表c,雙向鏈表d.循環(huán)鏈表14、假設(shè)s="abcaabcaaabca”，t="bca”，s.indexof（t,3）（其中3為索引號，索引號從0開始編號）4、線性表是：果是（）一個有限序列，可以為空；b.一個有限序列，不能為空；a.15c.10d.0c.一個無限序列，可以為空；d.一個無序序列，不能為空15、二叉樹的數(shù)據(jù)結(jié)構(gòu)描述了數(shù)據(jù)之間的（）關(guān)系。5、用鏈表表示線性表的優(yōu)點是（）。a?鏈接關(guān)系b.層次關(guān)系便于隨機存取c.網(wǎng)狀關(guān)系d?隨機關(guān)系b?花費的存儲空間較順序存儲少c,便于插入和刪除16、（）遍歷方法在遍歷它的左子樹和右子樹后再遍歷它自身。d,數(shù)據(jù)元素的物理順序與邏輯順序相同先序遍歷b.后序遍歷c.中序遍歷d.層次遍歷6、若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。17、在構(gòu)造哈夫曼樹的過程中說法正確的是（）。a.單鏈表b.僅有頭指針的單循環(huán)鏈表c.雙鏈表d.僅有尾指針的單循環(huán)鏈表使權(quán)值越大的葉結(jié)點越遠離根結(jié)點，而權(quán)值越小的葉結(jié)點越靠近根結(jié)點使權(quán)值越大的葉結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉結(jié)點越遠離根結(jié)點7、棧中元素的進出原則是（）=j最終是帶權(quán)路徑長度最大的二叉樹=ja.先進先出b.后進先出c.?？談t進d.棧滿則出構(gòu)造的過程是一次到位8、若已知一個棧的入棧序列是1,2,3,?,n,其輸出序列為pl,p2,p3,?,pn,若p1=n，則pi為（）18■=j最、55為最第一趟快速排序的基準值，執(zhí)行一趟快速排序能夠得到的序列是（a■=j最[12,27,45,41]55[34,63,72]a.ib.n=ic.n-i+1d.不確定[45,34,12,41]55[72,63,27][63,12,34,45,27]55[41,72]9、若依次輸入數(shù)據(jù)元素序列{a,b,c,d,e,f,g}進棧，出棧操作可以和入棧操作間隔進行，則下列哪個[41,12,34,45,27]55[72,63]元素序列可以由出棧序列得到？（）a.{c,d,b,e,g,a,f}b.{f,e,g,d,a,c,b}19、對線性表進行二分查找時，要求線性表必須（）。c.{e,f,d,g,b,c,a}d.{d,e,c,f,b,g,a}a.以順序方式存儲10、一個棧的入棧序列是1,2,345,則下列序列中不可能的出棧序列是（）b?以鏈接方式存儲以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序第1頁共2頁的結(jié)d?以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序20、在采用線性探測法處理沖突所構(gòu)成的散列表上進行查找，可能要探測多個位置，在查找成功的情況下，所探測的這些位置上的鍵值（）。a.一定都是同義詞b.一定都不是同義詞C.不一定都是同義詞都相同二、 判斷題（共10題，每題2分,共20分，正確打《錯誤的打乂）三、 1-5WXXW-10X熾熾1、 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，數(shù)據(jù)項是組成數(shù)據(jù)元素的基本單位。（）2、 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯的角度來觀察數(shù)據(jù)，分析數(shù)據(jù)，與數(shù)據(jù)的存儲位置無關(guān)。（）3、鏈式存儲結(jié)構(gòu)是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里，借助元素在存儲器中的相對位置來表示數(shù)據(jù)元

素之間邏輯關(guān)系。（）4、單鏈接表可以按雙向遍歷線性表中的每一個數(shù)據(jù)元素。（）5、鏈表中刪除和插入操作比順序表快，但是出”，隊列的主要特點是“后進先出”。（）7、stringbuilder是非線程安全，stringbuffer是線程安全的。（）元素的訪問速度比順序表要慢。（）元素的訪問速度比順序表要慢。（）6、棧的主要特點是“先進先8、前序遍歷是首先遍歷根結(jié)點的左子樹，再遍歷根結(jié)點的右子樹，最后訪問根結(jié)點。（）9、插入排序的基本思想是：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當位置，直到全部記錄插入完成為止。（）10、二叉排序樹的充要條件是任一結(jié)點的值均大于其左孩子的值，小于其右孩子的值。（）三、簡答題（共2題，每題10分，共20分）1、設(shè)哈希表長m=14，哈希函數(shù)為h（k）=kmod11。如果用二次探測再散列處理沖突，請將關(guān)鍵字為15、38、49、61、84的記錄填寫在相應(yīng)的存儲單元中。012345678910111213初始關(guān)鍵字先序遍歷（abdgcef）、中序遍歷（dgbaecf）、后序遍歷（gdbefca）和層次遍歷（abcdefg）。四、編程題（共20分，第1和第2小題各8分，第3小題4分）給定一組數(shù)據(jù)：1、 編寫冒泡排序算法publicint[]bubblesort（int[]data）,實現(xiàn)對該組數(shù)據(jù)的排序。2、 編寫二分查找算法publicintbinsearch（int[]data,intkey），實現(xiàn)對關(guān)鍵字key的查找。3、用給定的初始關(guān)鍵字編寫測試程序，對兩個算法進行測試。2、請分別給出下圖中先序遍歷、中序遍歷、后序遍歷和層次遍歷的結(jié)果。第2頁共2頁【篇三：數(shù)據(jù)機構(gòu)第四章 java語言描述第4章串與數(shù)組習(xí)題參考答案】、選擇題1.下面關(guān)于串的敘述中，哪一個是不正確的？（b）a,串是字符的有限序列空串是由空格構(gòu)成的串c?模式匹配是串的一種重要運算d串既可以采用順序存儲，也可以采用鏈式存儲串的長度是指（a）a.串中包含的字符個數(shù)b.串中包含的不同字符個數(shù)串中除空格以外的字符個數(shù)d.串中包含的不同字母個數(shù)設(shè)有兩個串p和q,其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（c）a?求子串6聯(lián)接^模式匹配d?求串長設(shè)主串的長度為n，模式串的長度為m，則串匹配的kmp算法時間復(fù)雜度是（c）。串也是一種線性表，只不過（a）。a.數(shù)據(jù)元素均為字符b.數(shù)據(jù)元素是子串c.數(shù)據(jù)元素數(shù)據(jù)類型不受限制d.表長受到限制設(shè)有一個10階的對稱矩陣2，采用壓縮存儲方式，以行序為主進行存儲，all為第一元素，其存儲地址為1,每個元素占一個地址空間，則a85的地址為（b）。a.13b.33c.18d.40有一個二維數(shù)組a[1..6,0..7]，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址，那么這個數(shù)組占用的存儲空間大小是（d）個字節(jié)。a.48b.96c.252d.288設(shè)有數(shù)組a[1..8,1..10]，數(shù)組的每個元素占3字節(jié)，數(shù)組從內(nèi)存首地址ba開始以列序為主序順序存放，則數(shù)組元素a[5,8]的存儲首地址為（b）。a.ba+141b.ba+180c.ba+222d.ba+225稀疏矩陣的三元組存儲表示方法（b）實現(xiàn)轉(zhuǎn)置操作很簡單，只需將每個三元組中行下標和列下標交換即可矩陣的非零元素個數(shù)和位置在操作過程中變化不大時較有效是一種鏈式存儲方法比十字鏈表更高效用十字鏈表表示一個稀疏矩陣，每個非零元素一般用一個含有（a）域的結(jié)點表示。a.5b.4c.3d.2二、填空題1.2.串長度為03.4.模式串t=ababaab的next[]nextval[]數(shù)組值為。設(shè)數(shù)組a[1??5,1??6]的基地址為1000，每個元素占5個存儲單元，若以行序為主序順序存儲，則元素a[5,5]7.在稀疏矩陣的三元組順序表存儲結(jié)構(gòu)中，除表示非零元的三元組表以外，還需要表示矩陣的行數(shù)、列數(shù)和的對稱矩陣，如果以相同的元素只存儲一次的原則進行壓縮存儲，則其元素壓910.三、算法設(shè)計題編寫基于seqstring類的成員函數(shù)count(),統(tǒng)計當前字符串中的單詞個數(shù)。參考答案：publicintcount。{intwordcount=0;〃單詞個數(shù)charcurrchar,prechar;for(inti=1;ithis.length();i++){currchar=this.charat(i);//當前字符prechar=this.charat(i-1);//前一個字符if(((int)(currchar)65||(int)(currchar)122〃當前字符不是字母||((int)(prechar)90(int)(prechar)97))(((int)(prechar)=65(int)(prechar)=90)〃當前字符的前一個字符是字母||((int)(prechar)=97(int)(prechar)=122))){wordcount++;}}returnwordcount;}編寫基于seqstring類的成員函數(shù)replace(begin,s1,s2)。要求在當前對象串中，從下標begin開始，將所有的si子串替換為s2串。參考答案：//beginint開始位置;s1string原始字符串；s2string目標字符串；publicseqstringreplace(intbegin,seqstringsi,seqstrings2){if(si==null||s2==null){returnnull；}seqstringss=newseqstring();〃產(chǎn)生空串seqstringsource=this;intindex=-1;while((index=source.indexof(s1,begin))!=-1){ss.concat(source.substring(0,index));//串連接ss.concat(s2);source=(seqstring)source.substring(index+s1.length());//取子串}ss.concat(source);〃串連接returnss;}編寫基于seqstring類的成員函數(shù)reverse。。要求將當前對象中的字符反序存放。參考答案：publicseqstringreverse。{for(inti=0,j=this.length()-1;ij;i++,j--){chartemp=this.charat(i);setcharat(i,this.charat(j));setcharat(j,temp);}returnthis;}編寫基于seqstring類的成員函數(shù)deleteallchar(ch)。要求從當前對象串中刪除其值等于ch的所有字符。參考答案：publicseqstringdeleteallchar(charch){seqstrings1=newseqstring(string.valueof(ch));if(s1==null){returnnull;}seqstringss=newseqstring();〃產(chǎn)生空串seqstringsource=this;//當前串賦值到sourseintindex=-1;while((index=source.indexof(s1,0))!=-1)(ss.concat(source.substring(0,index));//串連接source=(seqstring)source.substring(index+1);//取子串}ss.concat(source);//串連接returnss;}5.編寫基于seqstring類的成員函數(shù)stringcount(str)。要求統(tǒng)計子串str在當前對象串中出現(xiàn)的次數(shù)，若不出現(xiàn)則返回0。參考答案：publicintstringcount(seqstringstr)(seqstringsource=this.curstr;intcount=0,begin=0;intindex;while((index=source.indexof(str,begin))!=-1)(count++;begin=index+str.length();}returncount;}6.鞍點是指矩陣中的元素aij是第i行中值最小的元素，同時又是第j列中值最大的元素。試設(shè)計一個算法求矩陣a的所有鞍點。參考答案：//存放矩陣中鞍點的類classresult(triplenodedata[];//三元組表，存放鞍點的行、列、值intnums;//鞍點個數(shù)publicresult(intmaxsize){〃構(gòu)造方法data=newtriplenode[maxsize];〃為順序表分配maxsize個存儲單元for(inti=0;idata.length;i++){data[i]=newtriplenode();}nums=0;}}//返回矩陣中的所有鞍點publicresultallsaddlepoint(int[][]ar)(inti,j,flag,m,n;resultre=newresult(ar.length);for(i=0;iar.length;i++)(m=i;n=0;flag=1;//假設(shè)當前結(jié)點是鞍點for(j=0;jar[i].length;j++)(if(ar[i][j]ar[m][n])(n=j;}}for(j=0;jar.length;j++)(if(ar[j][n]ar[m][n])(flag=0;//不是鞍點}}i