國開大學2015年07月1252《數據結構(本)》期末考試參考答案

試卷代號：1252座位號數據結構(本)試題2015年7月題號二三四分數一1.下面關于線性表的敘述中，錯誤的是()。A.線性表采用順序存儲，必須占用一片連續(xù)的存儲空間B.線性表采用順序存儲，進行插入和別除操作，不需要進行數據元素間的移動C.線性表采用鏈式存儲，不必占用連續(xù)的存儲空間D.線性表采用鏈式存儲，進行插入刪除操作，不需要移動元素2.設有一個長度為28的順序表，要在第12個元素之前插入一個元素(也就是插入元素作為新表的第12個元素),則移動元素個數為()。3.元素2,4,6,8按順序依次進棧，則該棧的不可能輸出序列是()(進棧出?？梢越惶孢M行)。4.對一個棧頂指針為top的鏈棧進行出棧操作，用變量e保存棧頂元素的值，則執(zhí)行()。top=top->next;C.top=top->next;e=top->data;D.top=top->next;5.在一個尾指針為rear的六帶頭結點的單循環(huán)鏈表中，插入一個s所指的結點，并作為6.設有一個28階的對稱矩陣A(矩陣的第一個元素為a?.),采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數組B中(數組下標從1開始),則數組中第40號元素對應于矩陣中的元素是(),7.數組a經初始化chara'.]=“English”;a[1]中存放的是()。A.字符nB.字符E8.程序段chara[]="English";char*p=a;intn=0whileA.字符hB.aC.字符串的結束符D.79.在一棵二叉樹中，編號內17的結點的雙親結點的的順序編號為()。10.設一棵采用鏈式存儲的二叉樹，除葉結點外每個結點度數都為2,該樹結點中共有20個指針域為空。則該樹共有()個非葉子結點11.已知如圖1所示的一個圖，若從頂點VO出發(fā)，按深度優(yōu)先法進行遍歷，則可能得到的一種頂點序列為()。A.V?V?V?V?V?V?V?V?V?B.V?V?V?V?VC.V?V?V?V?V?V?V?V?V,D.V?V12.對()進行中序遍歷，可以使遍歷所得到的序列是有序序列。A.完全二叉樹B.二叉排序樹C.滿二叉樹排D.哈夫曼樹13.有一個長度為7的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數為()。14.排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列(初始為空)的一15.一組記錄的關鍵字序列為(12,45,22,4,6,50),利用快速排序，以第一個關鍵字為分割元素，經過一次劃分后結果為()。C.6,4,12,50,22,45D.4,6,12,22,45,5022.在對一組記錄(50,34,92,19,11,68,56,41,79)進行直接插入排序(由小到大排序),數是三、綜合題(每小題15分，共30分)三、綜合題(每小題15分，共30分)28.對給定的數列b={6,15,3,7(4)畫出在二叉樹中刪除結點3后的樹結構。29.(1)以4,5,6,13,11,12作為葉結點的權，構造一棵哈夫曼樹。(2)給出相應權重值葉結點的哈夫曼編碼。(3)一棵哈夫曼樹有n個葉結點，該樹共有多少個結點?簡述理由?(4)給出對上述哈夫曼樹中序遍歷的序列。為輔助工作單元?，F(xiàn)要以職工的工資號num為關鍵字進行排序，采用折半插人排序的算法，typedefstructNODE;(2)刪去a結點2015年7月28.(1)圖2(4分)346(4)圖3(3分)(4分)(4分)66455529.(1)圖4(4分)6