一次作弊,終生遺憾誠(chéng)信考試,從我做起姓名：考號(hào)：身份證號(hào)：1、考生必須將姓名、考號(hào)等項(xiàng)填寫(xiě)在裝訂線(xiàn)左側(cè)內(nèi)，不得超出，否則按違紀(jì)處理。2、請(qǐng)將證件放在桌角處備查。3、遵守考場(chǎng)規(guī)則。4、凡違反考紀(jì)者按規(guī)定給予相應(yīng)處分。

北京建筑大學(xué)2016年專(zhuān)升本考試數(shù)據(jù)結(jié)構(gòu) 課程考試試卷題號(hào) 1 2 3 總分題分 30 55 15 100得分閱卷人復(fù)核人一、單項(xiàng)選擇題，請(qǐng)選擇最佳答案（每題1.5分，共30分）。1、【 】是數(shù)據(jù)的基本單位。A.數(shù)據(jù)項(xiàng) B.數(shù)據(jù)元素 C.結(jié)構(gòu) D.算法2、數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及它們之間的【 】。A.關(guān)系 B.運(yùn)算 C.計(jì)算方法 D.存儲(chǔ)3、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的【 】。A．存儲(chǔ)結(jié)構(gòu) B．邏輯結(jié)構(gòu) C.物理結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)4、算法分析的目的【 】。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法的輸入輸出關(guān)系C.分析算法的效率以求改進(jìn) D.算法是否具有較好的可讀性5、算法效率度量的重要尺度是【 】。A．可讀性 B.健壯性C.時(shí)間復(fù)雜度和空間復(fù)雜度 D.算法應(yīng)當(dāng)滿(mǎn)足具體問(wèn)題的需求6、下列程序段的時(shí)間復(fù)雜度為【 】。s=0;for(i=0;i<=n;i++)for(j=1;j<n;j++)s++;A.O(n) B.O(nlog2n) C.O(n3) D.O(n2)7、不帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是【 】。A．L==NULL B．L->next==NULLC．L->next=L D．L!=NULL8、鏈表不具備的特點(diǎn)是【 】。A.可隨機(jī)訪(fǎng)問(wèn)任何一個(gè)元素 B.插入、刪除操作不需要移動(dòng)元素C.無(wú)需事先估計(jì)存儲(chǔ)空間大小 D.所需存儲(chǔ)空間與線(xiàn)性表長(zhǎng)度成正比9、如果最常用的操作是取第i個(gè)元素及其前驅(qū)，則采用【 】存儲(chǔ)方式最節(jié)省時(shí)間。A.單鏈表 B.雙向鏈表 C.循環(huán)鏈表 D.順序表10、進(jìn)制轉(zhuǎn)換程序執(zhí)行時(shí)，要用到的數(shù)據(jù)結(jié)構(gòu)是【 】。A.棧 B.隊(duì)列 C.線(xiàn)性表 D.數(shù)組11、一個(gè)隊(duì)列的數(shù)據(jù)入列序列是1，2，3，則隊(duì)列的出隊(duì)時(shí)輸出序列是【 】。A.1，2，3 B.3，2，1 C.1，3，2 D.3，2，112、兩個(gè)串相等是指【 】。A．串的長(zhǎng)度相等 B．兩個(gè)串中對(duì)應(yīng)元素相等C．兩個(gè)串中對(duì)應(yīng)元素相等，且長(zhǎng)度相等 D.都是空串13、稀疏矩陣用三元組表示的目的是【 】。A.便于進(jìn)行矩陣運(yùn)算 B.便于輸入和輸出C.節(jié)省存儲(chǔ)空間 D.降低運(yùn)算的時(shí)間復(fù)雜度14、樹(shù)最合適用來(lái)表示【 】。A．元素之間具有線(xiàn)性關(guān)系的數(shù)據(jù) B.元素之間具有分支層次關(guān)系的數(shù)據(jù)C．元素之間具有網(wǎng)狀關(guān)系的數(shù)據(jù) D．元素之間無(wú)聯(lián)系的數(shù)據(jù)

15、二叉樹(shù)第3層上至多有【 】結(jié)點(diǎn)。A.4 B.8 C.3 D.716、具有8個(gè)葉結(jié)點(diǎn)的二叉樹(shù)中有【 】個(gè)度為2的結(jié)點(diǎn)。A.7 B.8 C.9 D.1017、用鄰接矩陣存儲(chǔ)有向圖，則矩陣的第i行所有元素之和等于頂點(diǎn)i的【】。A.入度B.出度C.度D.與i相鄰的邊之和18、深度為4的二叉樹(shù)最多有【】個(gè)結(jié)點(diǎn)。A.16 B.15 C.14 D.1019、具有5個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有幾條邊才能確保是一個(gè)連通圖【 】。A．7 B．6 C．5 D．420、若查找每個(gè)元素的概率相等，則在長(zhǎng)度為n的順序表上查找任一元素的平均查找長(zhǎng)度為【 】。A.n B.n+1 C.(n-1)/2 D.(n+1)/2二、填空、簡(jiǎn)答與運(yùn)算題（55分）1、數(shù)據(jù)的邏輯結(jié)構(gòu)分為 、 、 、集合。（3分）2、設(shè)有下列用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫(huà)出它們的邏輯圖形表示，并指出它屬于哪種結(jié)構(gòu)。（5分）DS=（D，S），其中：D={a,b,c,d,e,f,g,h}S={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}3、一個(gè)棧的入棧序列是1,2,3，寫(xiě)出所有可能的出棧序列。（5分）4、對(duì)下列二叉樹(shù)，回答問(wèn)題。（6分）(1)該二叉樹(shù)的深度為 ；(2)該二叉樹(shù)的度為 ；(3)該二叉樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)為 ；(4)該二叉樹(shù)的分支個(gè)數(shù)為 ；(5)該二叉樹(shù)的先序遍歷序列為 。5、請(qǐng)根據(jù)給出的無(wú)向圖，回答下列問(wèn)題：（10分）(1)該圖的鄰接矩陣表示：(2)該圖的鄰接表形式；(3)該圖從節(jié)點(diǎn)1出發(fā)的深度優(yōu)先搜索序列；(4)該圖從節(jié)點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列。第 1 頁(yè) 共2頁(yè)姓名：6、某子系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)6種字符a,b,c,d,e,f，字母在電文中的頻率分別為w＝{10,19,8,5,6,12},試為這6個(gè)字母設(shè)計(jì)Huffman編碼，要求（1）畫(huà)出哈夫曼樹(shù)（2）給考號(hào)： 出每個(gè)字母的哈夫曼編碼（3）求帶權(quán)最短路徑WPL。（12分）哈夫曼樹(shù)為：身份證號(hào)：

三、算法設(shè)計(jì)與分析（15%）1、數(shù)據(jù)存儲(chǔ)在數(shù)組a[0…n-1]中，現(xiàn)用折半查找法在數(shù)組a中查找一個(gè)給定的元素key，找到則返回其在數(shù)組中的下標(biāo)，沒(méi)有則返回-1。下列是完整的程序，將橫線(xiàn)部分填完整。(9分)intSearch(inta[],intn,intkey)//n表示數(shù)組a的大小{intlow=0;high=n-1;while( ){intm= ;if(a[m]==key)return ;elseif( )high= ;elselow= ;}return-1;}voidmain(){inta[8]={1,2,3,4,5,6,7,8};cout<<Search(a,8,5);//查找數(shù)據(jù)5的位置1、考生必須將姓名、考號(hào)等項(xiàng)填寫(xiě)在裝訂線(xiàn)左側(cè)內(nèi)，不得超出，否則按違紀(jì)處理。2、請(qǐng)將證件放在桌角處備查。3、遵守考場(chǎng)規(guī)則。4、凡違反考紀(jì)者按規(guī)定給予相應(yīng)處分

的編碼為：b的編碼為：c的編碼為：d的編碼為：e的編碼為：f的編碼為：WPL=7、設(shè)有關(guān)鍵字{18,5,9,10，27,16,11,13,2}，采用哈希法將它們填入到表長(zhǎng)p=13的表中。要求：使用哈希函數(shù)H(key)=key%p，解決沖突的方法采用線(xiàn)性探測(cè)再散列。并計(jì)算平均查找長(zhǎng)度(ASL)。（10分）0 1 2 3 4 5 6 7 8 9 10 11 12ASL=8、輸入數(shù)據(jù)（31,17,22,54,68,20,39,25），試畫(huà)出生成之后的二叉排序樹(shù)。（4分）

}2、線(xiàn)性表(a1,a2,…,an)中的元素采用順序表存儲(chǔ)，現(xiàn)判斷X是