數(shù)據(jù)結(jié)構(gòu)線性表答案

1、第1章線性表線性表2.12.1描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。解：解：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié)點(diǎn)是在首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為了方便對(duì)鏈表的操作。它可以對(duì)空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。2.22.2填空題。

2、填空題。解：解：(1)在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與元素元素在表中的位置在表中的位置有關(guān)。(2)順序表中邏輯上相鄰的元素的物理位置必定必定緊鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定不一定緊鄰。(3)在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其前驅(qū)結(jié)點(diǎn)的鏈域的值其前驅(qū)結(jié)點(diǎn)的鏈域的值指示。(4)在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊處理插入和刪除首元結(jié)點(diǎn)時(shí)

3、不用進(jìn)行特殊處理。2.32.3在什么情況下用順序表比鏈表好？在什么情況下用順序表比鏈表好？解：解：當(dāng)線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲(chǔ)的時(shí)候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行隨機(jī)存取。2.42.4對(duì)以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。對(duì)以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。解：解：(6)(6)Snext=NULLSnext=NULL(7)(7)Q=PQ=P(8)(8)while(Pnext!=Q)whi

4、le(Pnext!=Q)P=PnextP=Pnext(9)(9)while(Pnext!=NULL)while(Pnext!=NULL)P=PnextP=Pnext(10)(10)P=QP=Q(11)(11)P=LP=L(12)(12)L=SL=S(13)(13)L=PL=P解：解：a.(4)(1)b.(7)(11)(8)(4)(1)c.(5)(12)d.(9)(1)(6)2.72.7已知已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且是帶表頭結(jié)點(diǎn)的

5、非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。案中選擇合適的語句序列。a.a.刪除刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是________________________________________。b.b.刪除刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是_________________

6、_______________________。c.c.刪除刪除P結(jié)點(diǎn)的語句序列是結(jié)點(diǎn)的語句序列是________________________________________。d.d.刪除首元結(jié)點(diǎn)的語句序列是刪除首元結(jié)點(diǎn)的語句序列是________________________________________。e.e.刪除尾元結(jié)點(diǎn)的語句序列是刪除尾元結(jié)點(diǎn)的語句序列是_________________________________

7、_______。(1)(1)P=PnextP=Pnext(2)(2)Pnext=PPnext=P(3)(3)Pnext=PnextnextPnext=Pnextnext(4)(4)P=PnextnextP=Pnextnext(5)(5)while(P!=NULL)while(P!=NULL)P=PnextP=Pnext(6)(6)while(Qnext!=NULL)while(Qnext!=NULL)P=QP=QQ=QnextQ=Qne

8、xt(7)(7)while(Pnext!=Q)while(Pnext!=Q)P=PnextP=Pnext(8)(8)while(Pnextnext!=Q)while(Pnextnext!=Q)P=PnextP=Pnext(9)(9)while(Pnextnext!=NULL)while(Pnextnext!=NULL)P=PnextP=Pnext(10)(10)Q=PQ=P(11)(11)Q=PnextQ=Pnext(12)(12)P=

9、LP=L(13)(13)L=LnextL=Lnext(14)(14)free(Q)free(Q)解：解：a.(11)(3)(14)b.(10)(12)(8)(3)(14)c.(10)(12)(7)(3)(14)d.(12)(11)(3)(14)e.(9)(11)(3)(14)2.82.8已知已知P結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。a.a

10、.在P結(jié)點(diǎn)后插入結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是結(jié)點(diǎn)的語句序列是______________________________________________。b.b.在P結(jié)點(diǎn)前插入結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是結(jié)點(diǎn)的語句序列是______________________________________________。c.c.刪除刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是________________________