自考數(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次序），后序法（即按______次序）和中序法（也稱對稱序法，即按LNR次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH

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

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

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

5、小題小題，每小題1515分）分）1.已知兩個單鏈表中的元素遞增有序，試寫一算法將這兩個有序表歸并成一個遞增有序的單鏈表。算法應(yīng)利用原有的鏈表結(jié)點空間。2.寫一算法將帶頭結(jié)點的單鏈表中值重復(fù)的結(jié)點刪除，使所得的結(jié)果表中各結(jié)點值均不相同答案：答案：一、填空題（一、填空題（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評分標(biāo)準(zhǔn)：評分標(biāo)準(zhǔn)：332.參考答案：參考答案：答：該算法的功能是：將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。解題方案：

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

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