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

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

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

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

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

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

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

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

8、率分別為0.070.190.020.060.320.030.210.10。為這8個字母設(shè)計哈夫曼編碼（要求畫出哈夫曼樹）。解：哈夫曼樹如下：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è)計哈希表的長度取值m；（2）畫出用開放地址法的線性探查法解決哈希沖突的哈希表結(jié)構(gòu)；解：（1）要存放的數(shù)據(jù)元素個數(shù)為n=12，m最好取1.1n~1.7n之間的一個素數(shù)，所以設(shè)計哈希表的長度m≈1.5n=19。（也可取17）2分（若取其它大于12的值最多得1分）（2）用哈希函數(shù)h(k)=kmodm=kmod19，哈希沖突函數(shù)d0=h(k)di