數(shù)據(jù)結(jié)構(gòu)課后習題及解析第二章

1、第二章習題1.描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元素結(jié)點。2.填空：（1）在順序表中插入或刪除一個元素，需要平均移動元素，具體移動的元素個數(shù)與有關(guān)。（2）在順序表中，邏輯上相鄰的元素，其物理位置相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置相鄰。（3）在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的存儲位置由指示，首元素結(jié)點的存儲位置由指示，除首元素結(jié)點外，其它任一元素結(jié)點的存儲位置由指示。3已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元素結(jié)

2、點，也不是尾元素結(jié)點。按要求從下列語句中選擇合適的語句序列。a.在P結(jié)點后插入S結(jié)點的語句序列是：。b.在P結(jié)點前插入S結(jié)點的語句序列是：。c.在表首插入S結(jié)點的語句序列是：。d.在表尾插入S結(jié)點的語句序列是：。供選擇的語句有：（1）Pnext=S（2）Pnext=Pnextnext（3）Pnext=Snext（4）Snext=Pnext（5）Snext=L（6）Snext=NULL（7）Q=P（8）while(Pnext!=Q)P=P

3、next（9）while(Pnext!=NULL)P=Pnext（10）P=Q（11）P=L（12）L=S（13）L=P4.設(shè)線性表存于a(1:arrsize)的前elenum個分量中且遞增有序。試寫一算法，將X插入到線性表的適當位置上，以保持線性表的有序性。5.寫一算法，從順序表中刪除自第i個元素開始的k個元素。6.已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk

4、的元素（若表中存在這樣的元素），分析你的算法的時間復(fù)雜度（注意：mink和maxk是給定的兩個參變量，它們的值為任意的整數(shù)）。7.試分別以不同的存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法，即在原表的存儲空間將線性表（a1a2...an）逆置為（anan1...a1）。（1）以一維數(shù)組作存儲結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)的前elenum個分量中。（2）以單鏈表作存儲結(jié)構(gòu)。8.假設(shè)兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲

5、結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個按元素值遞減有序排列的線性表C，并要求利用原表（即typedefstructNodeintpasswdintnumstructNodenextNodeLinklistvoidJosephus()LinklistLNodeprqintmnCjL=(Node)malloc(sizeof(Node))初始化單向循環(huán)鏈表if(L==NULL)printf(“n鏈表申請不到空間!“)returnLnext=