數(shù)據(jù)結(jié)構(gòu)試題a200711答案

1、第１頁(yè)共5頁(yè)陜西科技大學(xué)試題紙?jiān)囶}紙（A參考答案及評(píng)分標(biāo)準(zhǔn)）課程課程數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)班級(jí)班級(jí)信息、數(shù)學(xué)信息、數(shù)學(xué)05學(xué)號(hào)學(xué)號(hào)姓名姓名題號(hào)一二三四五六七八九十總分得分閱卷人一、選擇題（每小題1分，共15分）請(qǐng)?jiān)诿啃☆}的四個(gè)備選答案中，選出一個(gè)正確的答案，并將其號(hào)碼填在括號(hào)內(nèi)。1.設(shè)一個(gè)棧的輸入序列為1，2，3，4，則借助一個(gè)棧所得的輸出序列不可能是（D）。A1，2，3，4B4，3，2，1C1，3，4，2D4，1，2，32.設(shè)有80行的二維

2、數(shù)組A[80][60]，其元素長(zhǎng)度為4字節(jié)，按行優(yōu)先順序存儲(chǔ)，基地址為300，則元素A[18][25]的存儲(chǔ)地址為（D）。A3800B4376C3900D47203.將一棵有100個(gè)節(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根節(jié)點(diǎn)的編號(hào)為0，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（B）。A98B99C50D494.在長(zhǎng)度為n的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素（1≤i≤n）時(shí)，需要從前向后依次前移（A）個(gè)元素。Ani

3、Bni1Cni1Di5.棧的插入和刪除操作在（A）進(jìn)行。A棧頂B棧底C任意位置D指定位置6.鏈表適用于（A）查找。A順序B二分法C二分法、順序D隨機(jī)7.深度為6(根結(jié)點(diǎn)的層次為1)的二叉樹至多有（D）個(gè)結(jié)點(diǎn)。A64B32C31D638.用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用（B）來實(shí)現(xiàn)算法的。A棧B隊(duì)列C樹D圖9.設(shè)有兩個(gè)串ｐ和ｑ，求ｑ在ｐ中首次出現(xiàn)的位置的運(yùn)算稱作（B）。A連接B模式匹配C求子串D求串長(zhǎng)10.若某線性表中最常用的

4、操作是取第i個(gè)數(shù)據(jù)元素，則采用（D）存儲(chǔ)方式最節(jié)省時(shí)間。A單鏈表B雙鏈表C單向循環(huán)D順序表11.三個(gè)結(jié)點(diǎn)可構(gòu)成（D）個(gè)不同形態(tài)的二叉樹。A2B3C4D5第３頁(yè)共5頁(yè)3.比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？答：（1）順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲(chǔ)密度大，存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。2分（2）鏈?zhǔn)酱鎯?chǔ)時(shí)，相

5、鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放節(jié)點(diǎn)值；另一部分存放表示節(jié)點(diǎn)間關(guān)系的指針。優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度小，存儲(chǔ)空間利用率低。2分順序表適宜于做查找等靜態(tài)操作；鏈表適宜于做插入、刪除等動(dòng)態(tài)操作。若線性表的長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表；若線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除等操作，則采用鏈表。2分4.動(dòng)態(tài)數(shù)組和靜態(tài)數(shù)組在使用方法上有什么不同？答：（1）從使用方法上

6、來說，動(dòng)態(tài)數(shù)組和靜態(tài)數(shù)組除向系統(tǒng)申請(qǐng)內(nèi)存空間的方法不同外，數(shù)組的使用方法完全相同。3分（2）從性能上來說，靜態(tài)數(shù)組必須確切指定數(shù)組元素個(gè)數(shù)，這樣的指定在程序運(yùn)行后不能改變；動(dòng)態(tài)數(shù)組雖然也要確切指定數(shù)組元素個(gè)數(shù)，但因?yàn)檫@樣的指定是在程序運(yùn)行時(shí)通過調(diào)用函數(shù)實(shí)現(xiàn)的，一方面，可以利用malloc()函數(shù)或calloc()函數(shù)根據(jù)實(shí)際問題的需要申請(qǐng)動(dòng)態(tài)數(shù)組的元素個(gè)數(shù)，另一方面，當(dāng)所申請(qǐng)的動(dòng)態(tài)數(shù)組空間不足時(shí)，還可以通過realloc()函數(shù)來重新指

7、定動(dòng)態(tài)數(shù)組元素的個(gè)數(shù)。3分5.適宜于遞歸算法求解的問題的充分必要條件是什么？什么叫遞歸出口？答：充分必要條件是：（1）問題具有某種可借用的類同自身的子問題描述的性質(zhì)；（2）某一有限步的子問題（也稱作本原問題）有直接的解存在。3分遞歸到某一步時(shí)的子問題有直接的解存在，這個(gè)子問題就是遞歸出口。或者說遞歸出口就是遞歸結(jié)束的條件。3分四、算法思想題（每小題7分，共28分）1.假設(shè)用于通信的電文由字符集ABCDEFGH構(gòu)成，各字符在電文中出現(xiàn)的概

8、率分別為0.070.190.020.060.320.030.210.10。為這8個(gè)字母設(shè)計(jì)哈夫曼編碼（要求畫出哈夫曼樹）。解：哈夫曼樹如下：1.0000.400.210.190.280.320.110.170.100.070.060.030.050.020.6000000011111114分根據(jù)上圖可得編碼表：3分A:1001B:01C:10111D:1010E:11F:10110G:00H:10002.設(shè)有數(shù)據(jù)元素序列11，23，35

9、，47，51，60，75，88，90，102，113，126，用除留余數(shù)法構(gòu)造哈希表，要求：（1）設(shè)計(jì)哈希表的長(zhǎng)度取值m；（2）畫出用開放地址法的線性探查法解決哈希沖突的哈希表結(jié)構(gòu)；解：（1）要存放的數(shù)據(jù)元素個(gè)數(shù)為n=12，m最好取1.1n~1.7n之間的一個(gè)素?cái)?shù)，所以設(shè)計(jì)哈希表的長(zhǎng)度m≈1.5n=19。（也可取17）2分（若取其它大于12的值最多得1分）（2）用哈希函數(shù)h(k)=kmodm=kmod19，哈希沖突函數(shù)d0=h(k)di