運(yùn)用證據(jù)認(rèn)定案件事實(shí)問(wèn)題研究

《運(yùn)用證據(jù)認(rèn)定案件事實(shí)問(wèn)題研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、《數(shù)據(jù)結(jié)構(gòu)》部分一、簡(jiǎn)答題（10分，每題5分）1、數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的存儲(chǔ)有幾種表示方法？各有什么特點(diǎn)？（P6）解：數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有四種不同的表示方法：?(1)順序存儲(chǔ)方法。數(shù)據(jù)元素順序存放，每個(gè)結(jié)點(diǎn)只含有一個(gè)元素。存儲(chǔ)位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲(chǔ)密度大，但有些操作(如插入、刪除)效率較差。?(2)鏈?zhǔn)酱鎯?chǔ)方法。每個(gè)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組指針。指針?lè)从硵?shù)據(jù)元素間的邏輯關(guān)系。這種操作不要求存儲(chǔ)空間連續(xù)，便于進(jìn)行插入和刪除等操作，但存儲(chǔ)空間利用率較低。另外，由于邏輯上相鄰的數(shù)據(jù)元素在存儲(chǔ)空間上不一定相鄰，所以不能對(duì)其進(jìn)行隨機(jī)存取。?(

2、3)索引存儲(chǔ)方法。除數(shù)據(jù)元素存儲(chǔ)在一地址連續(xù)的內(nèi)存空間外，尚需建立一個(gè)索引表。索引表中的索引指示結(jié)點(diǎn)的存儲(chǔ)位置，兼有動(dòng)態(tài)和靜態(tài)特性。??(4)哈希(或散列)存儲(chǔ)方法。通過(guò)哈希函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將哈希函數(shù)的值作為該數(shù)據(jù)元素的存儲(chǔ)地址。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存儲(chǔ)，也不能折半存取。2、對(duì)于堆排序法，快速排序法和歸并排序法，若僅從節(jié)省存儲(chǔ)空間考慮，則應(yīng)該首先選取其中哪種方法？其次選取哪種方法？若僅考慮排序結(jié)果的穩(wěn)定性，則應(yīng)該選取其中哪種方法？若僅從平均情況下排序最快這一點(diǎn)考慮，則應(yīng)該選取其中哪些方法？（P28

3、9）答：若只從存儲(chǔ)空間考慮，則應(yīng)首先選取堆排序?方法，其次選取?快速排序?方法，最后選取?歸并排序?方法；?若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取歸并排序方法；若只從平均情況下最快考慮，則應(yīng)選取快速排序方法；?若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取堆排序方法。二、應(yīng)用題（55分）1、證明：同一棵二叉樹(shù)的所有葉子結(jié)點(diǎn)，在前序序列、中序序列以及后序序列中都按相同的相對(duì)位置出現(xiàn)（即先后順序相同）。（8分）（例如先序abc，后序bca，中序bac。）(P128)答：【答案】先序遍歷是“根左右”，中序遍歷是“左根右”，后序遍歷是“左右根”。三種遍歷中只是訪問(wèn)“根”結(jié)點(diǎn)的時(shí)機(jī)

4、不同，對(duì)左右子樹(shù)均是按左右順序來(lái)遍歷的，因此所有葉子都按相同的相對(duì)位置出現(xiàn)。2、設(shè)有正文AADBAACACCDACACAAD，字符集為A,B,C,D,設(shè)計(jì)一套二進(jìn)制編碼，使得上述正文的編碼最短。（10分）(P144;P148)3、對(duì)于下圖完成下列指定操作。（12分）(1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(shù)。(P167;)(2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹(shù)。(P169;)(3)根據(jù)普利姆(Prim)算法，求它的最小生成樹(shù)。(P173)4.設(shè)哈希(Hash)表的地址范圍為0～17，哈希函數(shù)為：H(K)=KMOD16,K為關(guān)鍵字，用線性探測(cè)再散列法處理沖突，輸入關(guān)鍵字序列

5、:(10,24,32,17,31,30,46,47,40,63,49)構(gòu)造哈希表，試回答下列問(wèn)題：（15分）（P257）(1)畫(huà)出哈希表示意圖。(2)若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字比較?(3)若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較?(4)假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。答：（1）畫(huà)表如下（2）查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次?。?）查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?2號(hào)單元為空（應(yīng)當(dāng)有空標(biāo)

6、記），所以應(yīng)當(dāng)只比較這一次即可。（4）對(duì)于黑色數(shù)據(jù)元素，各比較1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，ASL=1/11（6＋2＋3×3）＝17/11≈1.555．奇偶交換排序如下所述：對(duì)于初始序列A[1]，A[2],…,A[n],第一趟對(duì)所有奇數(shù)i（1<=iA[i+1]，則將兩者交換；第二趟對(duì)所有偶數(shù)i（2<=iA[i+1]，則將兩者交換；第三趟對(duì)所有奇數(shù)i（1<

7、=i