1、線訂裝線攀枝花學(xué)院考試試卷20152016學(xué)年度第二學(xué)期數(shù)據(jù)結(jié)構(gòu)試卷（A卷）評(píng)閱標(biāo)準(zhǔn)及考核說明適用年級(jí)專業(yè)：適用年級(jí)專業(yè)：2014級(jí)計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程、信息與計(jì)算科學(xué)考 試 形 式：（ ）開卷、（ ）閉卷得分閱卷人一、教師答題時(shí)間：8分鐘單項(xiàng)選擇題（每個(gè)小題2分，共30分。）1、三基類C 2、三基類D 3、三基類C 4、三基類D 5、三基類B6、三基類A 7、三基類B 8、三基類C 9、三基類C 10、三基類D11、三基類D 12、三基類A 13、三基類A 14、三基類B 15、三基類A得分閱卷人二、三基類 教師答題時(shí)間：5分鐘判斷題（每個(gè)小題1分，共10分。正確的劃，錯(cuò)誤的

2、劃）題號(hào)12345678910答案得分閱卷人三、填空題（每空1分，共15分）1、三基類 教師答題時(shí)間：1 分鐘 鏈?zhǔn)?、索引2、三基類 教師答題時(shí)間：0.5 分鐘 p-next!=null 3、三基類 教師答題時(shí)間： 1 分鐘 _ O(1)_、 _O(n)_4、三基類 教師答題時(shí)間：0.5 分鐘 棧頂 、棧底5、三基類 教師答題時(shí)間：0.5 分鐘堆分配存儲(chǔ)6、三基類 教師答題時(shí)間：1 分鐘 400 、 399 7、三基類 教師答題時(shí)間：1 分鐘 鄰接表、鄰接矩陣 8、三基類 教師答題時(shí)間：1 分鐘 8662 9、三基類 教師答題時(shí)間：0.5 分鐘 比較 、 移動(dòng) 得分閱卷人四、簡(jiǎn)答題（5個(gè)小題

3、，每個(gè)小題6分，共30分）1、（6分）一般綜合型 教師答題時(shí)間：3 分鐘答：（1）生成的二叉樹如下圖所示（4分）：（2）后序遍歷序列為：GDBEHFCA （2分）2、（6分）一般綜合型 教師答題時(shí)間：3 分鐘A000011110.250.250.1220.470.280.220.5310.13DEBC答 ：(1) 一棵哈夫曼樹如右圖所示（答案不唯一）（4分）：（2）各字符的哈夫曼編碼如下（2分）：A：01B：10C：11D：000E：0013、（6分）一般綜合型 教師答題時(shí)間：3 分鐘答：答：（1）最后得到的哈希表示意圖如下表所示（4分）：地址編號(hào)012345678910關(guān)鍵字值1122479

4、21637298（2）ASL（1+2+1+1+1+4+1+2+2）/95/3=1.67（2分）4、（6分）一般綜合型 教師答題時(shí)間：3 分鐘答：根據(jù)算法思想，從頂點(diǎn)1出發(fā)得到的深度優(yōu)先生成樹和廣度優(yōu)先生成樹如下。（1）深度優(yōu)先生成樹（3分） （2）廣度優(yōu)先生成樹（3分）5、（6分）一般綜合型 教師答題時(shí)間：3 分鐘答：答：（1）每趟排序的結(jié)果序列為：初態(tài)： 14，17，16，30，17*，28，8，25，15，20，2 （1分）第一趟（Dk=5）: 2，8，5，15，17*，14，17，25，30，20，28 （1分）第二趟（Dk=3）：2，8，5，15，17*，14，17，25，30，20，

5、28 （1分）第三趟（Dk=1）：2，5，8，14，16，17*，17， 20，25，28，30 （1分）（2）希爾排序不是穩(wěn)定的排序，因?yàn)橹迪嗤膬蓚€(gè)關(guān)鍵字17和17*在排序前后位置發(fā)生了改變。（2分）得分閱卷人五、算法題（本題含2小題，共15分）1、（6分） 綜合型 教師答題時(shí)間：5分鐘：（1） high （1.5分） （2） high （1.5分）（3） low （1.5分） （4） low （1.5分）2、（9分）綜合型 教師答題時(shí)間：5分鐘參考答案:(本題答案不唯一)void delete（Linklist &L）L是帶頭結(jié)點(diǎn)的單鏈表，本算法刪除其最小值結(jié)點(diǎn)。 p=L-next； p為工作指針。指向待處理的結(jié)點(diǎn)。假定鏈表非空。 （1分） pre=L； pre指向最小值結(jié)點(diǎn)的前驅(qū)。 （1分） q=p； q指向最小值結(jié)點(diǎn)，初始假定第一元素結(jié)點(diǎn)是最小值結(jié)點(diǎn)。（1分）while（p-next!=null） （1分） If（p-next-datadata） （1分） pre=p； （1分）q=p-next； （1分） 查最小值結(jié)點(diǎn)