自考數(shù)據(jù)結(jié)構(gòu)作業(yè)題及解析

1、20132013年4月考試數(shù)據(jù)結(jié)構(gòu)第三次作業(yè)月考試數(shù)據(jù)結(jié)構(gòu)第三次作業(yè)一、填空題（本大題共一、填空題（本大題共2020分，共分，共4小題，每小題小題，每小題5分）分）1.二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按NLR次序），后序法（即按______次序）和中序法（也稱對(duì)稱序法，即按LNR次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH

2、，中序序列是FEBGCHD，則它的后序序列必是______。2.假設(shè)有二維數(shù)組A68，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A的體積（存儲(chǔ)量）為______；末尾元素A57的第一個(gè)字節(jié)地址為______；若按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為______；若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為______。3.一個(gè)算法的時(shí)間復(fù)雜度為(3n22nlog2n4n7)(5n)，

3、其數(shù)量級(jí)表示為______。4.在一棵樹中，______結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)。二、程序閱讀題（本大題共二、程序閱讀題（本大題共2020分，共分，共2小題，每小題小題，每小題1010分）分）1.對(duì)一組關(guān)鍵子49，7，50，5，94，16，90，29，71進(jìn)行排序，寫出分別用下列排序方法排序時(shí)，每一趟排序結(jié)束時(shí)這些關(guān)鍵字的序列。1）簡(jiǎn)單插入排序2）希爾排序（d1=4d2=2，d3=1）2.下述算法的功能是什么LinkListDemo(LinkL

4、istL)L是無(wú)頭結(jié)點(diǎn)單鏈表ListNodeQPif(LL=LnextP=Lwhile(Pnext)P=PnextPnext=QQnext=NULLreturnLDemo三、簡(jiǎn)答題（本大題共三、簡(jiǎn)答題（本大題共3030分，共分，共2小題，每小題小題，每小題1515分）分）1.索引順序表的查找要求“分塊有序”，什么是“分塊有序”？2.請(qǐng)敘述圖的廣度優(yōu)先搜索思想。四、程序設(shè)計(jì)題（本大題共四、程序設(shè)計(jì)題（本大題共3030分，共分，共2小題，每

5、小題小題，每小題1515分）分）1.已知兩個(gè)單鏈表中的元素遞增有序，試寫一算法將這兩個(gè)有序表歸并成一個(gè)遞增有序的單鏈表。算法應(yīng)利用原有的鏈表結(jié)點(diǎn)空間。2.寫一算法將帶頭結(jié)點(diǎn)的單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果表中各結(jié)點(diǎn)值均不相同答案：答案：一、填空題（一、填空題（2020分，共分，共4題，每小題題，每小題5分）分）1.參考答案：參考答案：LRN，F(xiàn)EGHDCB94，29，71；5，7，16，29，49，50，90，94，71；5，7

6、，16，29，49，50，71，90，94；2）希爾排序：49，7，50，5，94，16，90，29，71；49，7，50，5，71，16，90，29，94；49，5，50，7，71，16，90，29，94；5，7，16，29，49，50，71，90，94評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：332.參考答案：參考答案：答：該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。解題方案：

7、解題方案：答：該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：5三、簡(jiǎn)答題（三、簡(jiǎn)答題（3030分，共分，共2題，每小題題，每小題1515分）分）1.參考答案：參考答案：答：所謂“分塊有序”指的是第二個(gè)子表中所有記錄的關(guān)鍵字均大于第一個(gè)子表中的最大關(guān)鍵字，第三個(gè)子表中的所有關(guān)鍵字均大于第二個(gè)子表中的最大關(guān)鍵字，…，依次類推。解題方案：解題方案：

8、答：所謂“分塊有序”指的是第二個(gè)子表中所有記錄的關(guān)鍵字均大于第一個(gè)子表中的最大關(guān)鍵字，第三個(gè)子表中的所有關(guān)鍵字均大于第二個(gè)子表中的最大關(guān)鍵字，…，依次類推。評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：62.參考答案：參考答案：答：使用廣度優(yōu)先搜索在訪問(wèn)了起始頂點(diǎn)v之后，由v出發(fā)，依次訪問(wèn)v的各個(gè)未曾被訪問(wèn)過(guò)的鄰接頂點(diǎn)w1w2…wt，然后再順序訪問(wèn)w1w2…wt的所有還未被訪問(wèn)過(guò)的鄰接頂點(diǎn)。再?gòu)倪@些訪問(wèn)過(guò)的頂點(diǎn)出發(fā)，再訪問(wèn)它們的所有還未被訪問(wèn)過(guò)的鄰接頂點(diǎn)，…如此