數據結構（Java語言版）-習題及答案 第2章線性表習題答案

第2章線性表習題參考答案一、單選題ABCDABCD關系字符數據元素數據項ABCD以下關于線性表和ABCD線性表中元素不能重復出現有序表屬于線性表的存儲結構線性表和有序表的元素具有相同的邏輯關系有序表可以采用順序表存儲，而線性表不能采用順序表存儲ABCABCD順序表的優(yōu)點是存儲密度大且插入、刪除運算效率高順序表的優(yōu)點是具有隨機存取特性順序表中所有元素可以連續(xù)也可以不連續(xù)存放在含n個元素的順序表中查找序號為的元素的時間復雜度為ABCD在含n個元素的順序表中，算法的時間復雜度是OABCD訪問第個元素（≤≤n）和求第個元素的前驅元素（≤≤n）在第個元素后插入一個新元素（≤≤n）刪除第個元素（≤≤n）ABCABCD所有的操作算法實現簡單便于隨機存取便于插入和刪除元素節(jié)省存儲空間ABCABCD必須是連續(xù)的一定是不連續(xù)的部分地址必須是連續(xù)的連續(xù)與否均可以ABCABCD大于1等于1小于1不能確定ABCABCD一個結點的數據成員用于存放線性表的一個數據元素一個結點的指針成員用于指向下一個數據元素的結點單鏈表必須帶有頭結點單鏈表中所有結點可以連續(xù)也可以不連續(xù)存放ABCABCD可隨機訪問任一結點插入刪除不需要移動結點不必事先估計存儲空間所需空間與其長度成正比ABCABCD結點中除元素值外還包括指針成員，因此存儲密度小于順序存儲結構邏輯上相鄰的元素物理上不必相鄰可以根據頭結點地址直接計算出第i個結點的地址插入、刪除運算操作方便，不必移動結點ABCD若某線性表最常用的操作是查找序號ABCD順序表帶頭結點的循環(huán)雙鏈表單鏈表帶尾結點的循環(huán)單鏈表ABCD將兩個各有nABCDn2n-12nn-1以下關于單鏈表的敘述中正確的是 。Ⅰ結點中除元素值外還包括指針成員，存儲密度小于順序表Ⅱ找第個結點的時間為O)Ⅲ在插入和刪除操作時不必移動結點AABCD僅Ⅰ、Ⅱ僅Ⅱ、Ⅲ僅Ⅰ、Ⅲ.Ⅰ、Ⅱ、ⅢABCABCD刪除單鏈表中的首結點刪除單鏈表中的尾結點在單鏈表首結點前插入一個新結點在單鏈表尾結點素后插入一個新結點ABCABCD插入一個結點使之有序的算法的時間復雜度為O)刪除最大值結點使之有序的算法的時間復雜度為O)找最小值結點的算法的時間復雜度為O)以上都不對已知兩個長度分別為m和n的遞增單鏈表，若將它們合并為一個長度為m+n的遞減單鏈表，則最好情況下的時間復雜度是 。ABCABCDO)O×n)O+n)在一個雙鏈表中，刪除p結點（非尾結點）的操作是 。 A.pprrnex=pnex;pnexprr=pprr;B.pprr=pprrprr;pprrprr=p;CC.pnexprr=p;pnex=pnexnex;D.pnex=pprrprr;pprr=pprrprr;<gye="x-dh:%;"rc="hp://cdnqngnene/bccebcdbcpng"/>ABCABCDO)On)On)Ongn)ABCD在長度為n（n≥1）的雙鏈表中插入一個結點p（非尾結點ABCD1234在長度為n（n≥1）的雙鏈表中刪除一個結點p（非尾結點）要修改 個指針成員。AABCD1234ABCABCD單鏈表的存儲密度較雙鏈表高單鏈表的存儲密度較雙鏈表低雙鏈表較單鏈表存放更多的元素單鏈表不能表示線性表的邏輯關系，而雙鏈表可以ABCABCD插入、刪除操作更簡單可以進行隨機訪問可以省略表頭指針或表尾指針訪問前后相鄰結點更方便ABCABCD單鏈表僅有頭結點的循環(huán)單鏈表雙鏈表僅有尾指針的循環(huán)單鏈表ABCABCD不再需要頭結點已知某個結點能夠容易找到它的前驅結點在進行插入、刪除操作時，能更好地保證鏈表不斷開從表中任意結點出發(fā)都能遍歷整個鏈表ABCABCDpnex==nulp==nulpnex==hedp==headABCABCDO)On)On)Ongn)ABCABCD對于這兩個鏈表來說，刪除首結點的時間復雜度都是O)對于這兩個鏈表來說，刪除尾結點的時間復雜度都是On)循環(huán)單鏈表B比非循環(huán)單鏈表A占用更多的內存空間以上都不對ABCABCDpprr=q;qnex=p;pprrnex=q;qprr=pprr;pprr=q;pprrnex=q;qnex=p;qprr=pprr;qnex=p;qprr=pprr;pprr=q;pprrnex=q;qnex=p;qprr=pprr;pprrnex=q;pprr=q;<gye="x-dh:%;"rc="hp://cdnqngnene/eebedbdbcdddpng"/>有一個非空循環(huán)雙鏈表，在結點p之后插入結點q的操作是qnex=pnex;pnex=q;qprr=p; 。 .pnex=q;.qprrnex=q;CC.qnexprr=q;D.qnexnex=q;<gye="xdh:%;"rc="hp://cdnqngnene/bdbdcdpng"/>ABCD在長度為n的 上，刪除尾結點的時間復雜度為OABCD單鏈表雙鏈表循環(huán)單鏈表循環(huán)雙鏈表線性表是具有n個（）的有限序列。AABCD表元素字符數據元素數據項線性表是（）。AABCD一個有限序列，不可以為空一個無限序列，可以為空一個無限序列，不可以為空線性表有一個特點（）。AABCD若沒有開始元素，則一定沒有終端元素每個元素必須有一個前趨元素任何一個元素都還可能既是開始元素又是終端元素關于線性表的正確說法是（）。ABABCD線性表中至少有一個元素表中元素的排序順序必須是由小到大或由大到小除第一個元素和最后一個元素外，其余每個元素有且僅有一個前趨和一個后繼元素線性表的順序存儲結構是一種（）。AABCD順序存取的存儲結構索引存取的存儲結構散列存取的存儲結構以下關于順序表的敘述中，正確的是（）。AABCD在順序表中，邏輯上相鄰的元素在物理位置上不一定相鄰順序表和一維數組一樣，都可以進行隨機存取在順序表中每一個元素的類型不必相同一個順序表所占用存儲空間的大小與（）無關。AABCD順序表中元素的數據類型順序表中元素各數據項的數據類型順序表中各元素的存放次序

設一個順序表（最多可存放個元素）目前有個元素，第（≤≤）個元素存放在d中，若把一個新元素存入d，則（）。AABCD會產生運行錯誤d～d不構成一個順序表順序表的長度大于順序表元素個數，會降低存儲空間的利用率以上都不對設一個順序表（最多可存放個元素）目前有個元素，第（≤≤）個元素存放在d中，現刪除d的元素而不做元素移動，則（）AABCDd～d不構成一個順序表順序表的長度變?yōu)?9以上都不對順序表具有隨機存取特性，指的是（）。AABCD查找值為x的元素與順序表中元素個數n有關查找序號為i的元素與順序表中元素個數n無關查找序號為i的元素與順序表中元素個數n有關

二、編程題H—數列有序問題時間限制：，空間限制：。個整數，已經按照從小到大順序排列好，現在另外給一個整數m，請將該數插入到序列中，并使新的序列仍然有序。輸入格式：輸入數據包含多個測試實例，每組數據由兩行組成，第一行是n和m，第二行是已經有序的n個數的數列。n和m同時為0標示輸入數據的結束，本行不做處理。輸出格式：對于每個測試實例，輸出插入新的元素后的數列。答：prtvu*;pubccsn{cnt]n=newn;pubccntJephntk){ntcnp;nk=)reurnnk;rnt=k+;;++){rcn=*kp=;cn>k;cn){p=p+)%cn;p<k)cn=;}cn==k){reurn;}}}pubccvdnSrngrg){Scnnercn=newScnnerSyen;hecnhNex){ntk=cnnexIn;fk==)brek;SyeuprnnJephk;}}}.HDU1443—：2000ms，空間限制：65536Kn個人，編號為1，2，…，n，站在一個圓圈中，每隔m個人就殺一個人，最后僅剩下一個人。約瑟夫很聰明，可以選擇最后一個人的位置，從而挽救他的生命。例如，當n=6且m=5時，按順序出列人員是5，4，6，2，3，1，那么1會活下來。假設在圈子里前面恰好有k個好人，后面恰好有k個壞人，你必須確定所有壞人都在第一個好人前面被殺的最小m。輸入格式：輸入文件包含若干行，每行一個k，最后一行為0，你可以假設0<k<14。輸出格式：輸出文件中每行給出輸入文件中的k對應的最小m。答：prtvu*;pubccsn{cnt]n=newn;pubccntJephntk){ntcnp;nk=)reurnnk;rnt=k+;;++){rcn=*kp=;cn>k;cn){p=p+)%cn;p<k)cn=;}cn==k){reurn;}}}pubccvdnSrngrg){Scnnercn=newScnnerSyen;hecnhNex){ntk=cnnexIn;fk==)brek;SyeuprnnJephk;}}}.OJ—公牛數學問題時間限制：，空間限制：。問題描述：公牛在數學上比奶牛好多了，它們可以將巨大的整數相乘，得到完全精確的答案。農夫約翰想知道它們的答案是否正確。請你幫助他檢查公牛隊的答案。讀入兩個正整數（每個不超過40位）并計算其結果，以常規(guī)方式輸出（沒有額外的前導零）。約翰要求你自己這樣做，不要使用特殊的庫函數進行乘法。輸入格式：輸入兩行每行包含一個十進制數。輸出格式：輸出一行表示乘積。答：prtvng*;prtvu*;pubccsn{pubccSrnguSrngSrng)//兩個數字字符串相乘{nt]=newn;nt]b=newn;nt]c=newn;nt;nt=engh;ntn=engh;r=;i<;++)=chr;r=;i<n;++)b=chrn;r=;i<;++)r=;j<n;++)c+]+=*b;r=;i<;++)>=10){c+]+=c/;10;}Srngn="";r=cengh;>=;)c=)brek;r;>=;)+=c[i];returnans;pubccvdnSrng]rg){Scnnercn=newScnnerSyen;Srng;=cnnexne;=cnnexne;Srng=u;Syeuprnn;}}

三、填空題線性表是有限個性質相同的數據元素的。 答：序列在線性表中，除了開始元素外，每個元素。 答：只有唯一的前趨元素在非空線性表中，終端元素是。 答：唯一的有10個學生排成一列，這些學生的信息構成的邏輯結構是一種。 答：線性表順序表是線性表的一種順序存儲結構，采用存放線性表中的元素及其關系。 答：一維數組線性表的存儲結構是一種隨機存儲結構。 答：順序順序表中邏輯上相鄰的元素的物理位置相鄰。單鏈表中邏輯上相鄰的元素的物理位置相鄰。 答：必定;不一定.在線性表的順序存儲結構中，元素之間的邏輯關系是通過元素的決定的；在線性表的鏈式存儲結構中，元素之間的邏輯關系是通過結點的決定的。答：物理存儲位置;指針域

四、判斷題線性表中所有元素的數據類型必須相同。 答：正確線性表中的結點按前趨、后繼關系可以排成一個線性序列。 答：正確空的線性表就是所有元素尚未賦值的線性表。 答：錯誤在一個含有n（n≥）個元素的線性表中，所有元素值不能相同。 答：錯誤線性表中每個元素都有一個前趨元素和一個后繼元素。 答：錯誤線性表的長度是線性表占用的存儲空間的大小。 答：錯誤線性表的存儲結構大小與線性表中元素類型有關。 答：正確線性表的邏輯順序總與其物理順序一致。 答：錯誤線性表的順序存儲結構優(yōu)于鏈式存儲結構。 答：錯誤順序表具有隨機存取特性，而鏈表不具有隨機存取特性。 答：正確五、簡答題線性表有何特點，線性表中的元素可以重復出現嗎？ 答：線性表是有限個相同性質的元素的序列，數據元素呈現線性關系，每個元素至多只有一個前趨元素和一個后繼元素。由于線性表中元素與其位置有關，所以線性表中的元素可以重復出現。什么叫做隨機存取特性？ 答：隨機存取特性是針對存儲結構的，而不是針對邏輯結構的。一種存儲結構具有隨機存取特性，是指對于給定元素序號，在時間O內能夠找到該元素的值，順序表具有隨機存取特性。順序表具有隨機存取特性，所以在含有n個元素的順序表中查找值為x的元素所花時間為O。這句話正確嗎？ 答：錯誤。一種存儲結構具有隨機存取特性，是指對于給定元素序號，在時間O內能夠找到該元素的值，并不是給定元素值x，能在時間O能夠找到該元素。在順序表中查找值為x的元素所花時間為On。要想在O的時間內存取第個表元素，線性表采用順序表還是單鏈表？ 答：采用順序表，因為順序表具有隨機存取特性，而單鏈表不具有隨機存取特性，在單鏈表中存取第個表元素的時間為On簡述順序表和鏈表存儲方式的主要優(yōu)缺點。 答：順序表的優(yōu)點是可以隨機存取元素，存儲密度高，結構簡單；缺點是需要一片地址連續(xù)的存儲空間，不便于插入和刪除元素（需要移動大量的元素），表的容量不便擴充。鏈表的優(yōu)點是便于結點的插入和刪除（只需要修改指針域，不需要移動結點），表的容量擴充十分方便；缺點是不能進行隨機訪問，只能順序訪問，另外每個結點上增加指針域，導致存儲密度較低。.線性表有兩種存儲結構：一是順序表，二是鏈表。試問：（1）如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數也會自動地改變。在此情況下，應選用哪種存儲結構？為什么？（2）若線性表的總數基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應采用哪種存儲結構？為什么？答：應選擇鏈式存儲結構。它可動態(tài)申請內存空間，容易實現表容量的擴充，不受表長度（即表中元素個數）的影響，另外插入和刪除操作的時間復雜度為O。應選擇順序存儲結構。順序表具有隨機存取特性，當以序號存取元素時的時間復雜度為O。在什么情況下使用順序表比鏈表好？ 答：當線性表很少進行插入和刪除操作，或者插入和刪除操作總是在尾部進行時，使用順序表比鏈表好。何時選用順序表、何時選用鏈表作為線性表的存儲結構為宜？ 答：在實際應用中，應根據具體問題的要