數(shù)據(jù)結(jié)構(gòu)（Java語言版）-習題及答案 第2章線性表習題答案

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

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

二、編程題H—數(shù)列有序問題時間限制：，空間限制：。個整數(shù)，已經(jīng)按照從小到大順序排列好，現(xiàn)在另外給一個整數(shù)m，請將該數(shù)插入到序列中，并使新的序列仍然有序。輸入格式：輸入數(shù)據(jù)包含多個測試實例，每組數(shù)據(jù)由兩行組成，第一行是n和m，第二行是已經(jīng)有序的n個數(shù)的數(shù)列。n和m同時為0標示輸入數(shù)據(jù)的結(jié)束，本行不做處理。輸出格式：對于每個測試實例，輸出插入新的元素后的數(shù)列。答：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會活下來。假設(shè)在圈子里前面恰好有k個好人，后面恰好有k個壞人，你必須確定所有壞人都在第一個好人前面被殺的最小m。輸入格式：輸入文件包含若干行，每行一個k，最后一行為0，你可以假設(shè)0<k<14。輸出格式：輸出文件中每行給出輸入文件中的k對應(yīng)的最小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—公牛數(shù)學問題時間限制：，空間限制：。問題描述：公牛在數(shù)學上比奶牛好多了，它們可以將巨大的整數(shù)相乘，得到完全精確的答案。農(nóng)夫約翰想知道它們的答案是否正確。請你幫助他檢查公牛隊的答案。讀入兩個正整數(shù)（每個不超過40位）并計算其結(jié)果，以常規(guī)方式輸出（沒有額外的前導零）。約翰要求你自己這樣做，不要使用特殊的庫函數(shù)進行乘法。輸入格式：輸入兩行每行包含一個十進制數(shù)。輸出格式：輸出一行表示乘積。答：prtvng*;prtvu*;pubccsn{pubccSrnguSrngSrng)//兩個數(shù)字字符串相乘{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;}}

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

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