數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)第2版習(xí)題答案—嚴(yán)蔚敏(簡(jiǎn)化版)

1、1第2章線性表線性表1選擇題（1）順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（）。A110B108C100D120答案：B解釋：順序表中的數(shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為：10024=108。（3）向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)的元素個(gè)數(shù)為（）。A8B63.5C63D7答案：B解釋：平均要移動(dòng)的元素個(gè)數(shù)為：n2。（4）鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（）。

2、A分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B只有一部分，存放結(jié)點(diǎn)值C只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針D分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)答案：A（5）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。A必須是連續(xù)的B部分地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)或不連續(xù)都可以答案：D（6）線性表Ｌ在（）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。A需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值Ｂ需不斷對(duì)Ｌ進(jìn)行刪除插入CＬ中

3、含有大量的結(jié)點(diǎn)ＤＬ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜答案：B解釋：鏈表最大的優(yōu)點(diǎn)在于插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，直接修改指針即可。（7）單鏈表的存儲(chǔ)密度（）。A大于1B等于1C小于1D不能確定答案：C解釋：存儲(chǔ)密度是指一個(gè)結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)空間和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)空間之比，假設(shè)單鏈表一個(gè)結(jié)點(diǎn)本身所占的空間為D，指針域所占的空間為N，則存儲(chǔ)密度為：D(DN)，一定小于1。（8）將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。AnB2n

4、1C2nDn13Dqpri=pqnext=pnextpnext=qpnextpri=q答案：C2算法設(shè)計(jì)題（1）將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲(chǔ)空間不另外占用其它的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。[算法描述]voidMergeList(LinkListpb=Lbnextpa和pb分別是鏈表La和Lb的工作指針初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)Lc=pc=La用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)wh

5、ile(papc=papa=panext取較小者La中的元素，將pa鏈接在pc的后面，pa指針后移elseif(padatapbdata)pcnext=pbpc=pbpb=pbnext取較小者Lb中的元素，將pb鏈接在pc的后面，pb指針后移else相等時(shí)取La中的元素，刪除Lb中的元素pcnext=papc=papa=panextq=pbnextpbpb=qpcnext=papa:pb插入剩余段Lb釋放Lb的頭結(jié)點(diǎn)（6）設(shè)計(jì)一個(gè)算法，