-數(shù)據(jù)結(jié)構(gòu)與算法A卷參考答案

1、江西財(cái)經(jīng)大學(xué)0607第一學(xué)期授課課時(shí)：112適用對(duì)象：本科期末考試參考答案與評(píng)分標(biāo)準(zhǔn)授課課時(shí)：112適用對(duì)象：本科試卷代碼：03266A課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法一、單項(xiàng)選擇題（每小題2分，共24分。）TOC o 1-5 h z1.D2.D3.C4.B5.C6.C7.D8.B9.D10.A11.C12.D二、填空題（每空1分，共7分。）父（或前驅(qū)）,1n-1不包含任何字符的串（n+1）/2素?cái)?shù)0111223123三、簡(jiǎn)答題（每小題5分，共15分）1答：順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)密度大，存儲(chǔ)空間利用率高。缺點(diǎn)：插

2、入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度?。?|四、判斷題（本大題共10小題，命題正確的在題后括號(hào)內(nèi)寫“T”，錯(cuò)誤的在題后括號(hào)內(nèi)寫“F”，每小題1分，共10分）T2.F3.T4.F5.F6.F7.T8.F9.T10.F五、分析應(yīng)用題（1、4小題各6分，2、3小題各7分）1（6分）答：程序段的功能是利用tmp棧將一個(gè)非空棧si的所有元素按原樣復(fù)制到一個(gè)棧s2當(dāng)中去。2（7分）答：為方便起見，設(shè)各種字符的權(quán)值w=5,29,7,8,14,23,3,11。因

3、為n=8,所以要構(gòu)造的赫夫曼樹共有m=2n-1=2*8T=15個(gè)結(jié)點(diǎn)。生成的赫夫曼樹為下圖所示：0001001100001001100111101101110111157）=5，H（20）=7，H（03）=3，H（78）赫夫曼編碼為：概率為0.23的字符編碼為概率為0.11的字符編碼為概率為0.05的字符編碼為概率為0.03的字符編碼為概率為0.29的字符編碼為概率為0.14的字符編碼為概率為0.07的字符編碼為概率為0.08的字符編碼為3.（7分）答：使用散列函數(shù)H（key）二keymod13有:H（12）=12，H（23）=10，H（45）=6，H=0，H（31）=5，H（15）=2，H（

4、36）=10利用線性探查法造表：0123456789101112781503574520312336121111114121搜索成功的平均搜索長(zhǎng)度為：ASL=1/10（1+1+1+1+1+1+4+1+2+1）=14/104.（6分）答：希爾排序（增量為5,2,1）初始掃初始掃E列d=5102ISS18121C203023fi=211111102ISS16*12IB20302Ed=1I丨丨II丨丨丨丨I2S10121616*IB20230六、算法設(shè)計(jì)題(第1小題10分，第2小題8分)(10分)includeincludestring.hintcharnumber=128;voidfrequency(string&s,intC)for(inti=0;icharnumber;i+)Ci=0;for(i=0;is.length();i+)Catoi(si)+;for(i=0;i0)cout”(”i”):t”Cidata);/出隊(duì)，訪問結(jié)點(diǎn)if(p-lchild&!p-rchild|!p-lchild&p-rchild)num+;/度為1的結(jié)點(diǎn)if(p-lchild)QueueIn(Q,p-lchild)