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

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

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

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

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

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