國開大學2015年07月1252《數(shù)據(jù)結(jié)構(gòu)(本)》期末考試參考答案

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