東北林業(yè)大學數(shù)據(jù)結構(A)2005-2006答案

東北林業(yè)大學2005－2006學年第二學期考試試題PAGE6PAGE5考試科目：數(shù)據(jù)結構（A）評分標準及參考答案得分一、單項選擇題（在每個小題四個備選答案中選出一個正確答案，填在題末的括號中）（本大題共10小題，每小題1.5分，總計10分）(選對1個題給1.5分，選錯1個題不給分)1、從邏輯上可以把數(shù)據(jù)結構分為（）兩大類。A．動態(tài)結構、靜態(tài)結構B．順序結構、鏈式結構C．線性結構、非線性結構D．初等結構、構造型結構答案（C）2、若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。A．順序表B．雙鏈表C．帶頭結點的雙循環(huán)鏈表D．單循環(huán)鏈表答案（A）3、循環(huán)隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是()。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front答案（A）4、串的長度是指（）A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)答案（B）5、設廣義表L=（（a,b,c）），則L的長度和深度分別為（）。A.1和1B.1和3C.1和2D.2和3答案（C）6、二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是：()A.EB.FC.GD.H答案（C）7、深度為h的滿m叉樹的第k層有（）個結點。(1=<k=<h)A．mk-1B．mk-1C．mh-1D．mh-1答案（A）8、關鍵路徑是事件結點網絡中（）。A．從源點到匯點的最長路徑B．從源點到匯點的最短路徑C．最長回路D．最短回路答案（A）9、散列文件使用散列函數(shù)將記錄的關鍵字值計算轉化為記錄的存放地址，因為散列函數(shù)是一對一的關系，則選擇好的（）方法是散列文件的關鍵。A.散列函數(shù)B.除余法中的質數(shù)C.沖突處理D.散列函數(shù)和沖突處理答案（D）10、m階B-樹是一棵()A.m叉排序樹B.m叉平衡排序樹C.m-1叉平衡排序樹D.m+1叉平衡排序樹答案（B）得分二、判斷題（本大題共10小題，每小題1分，總計10分）(判斷對1個題給1分，判斷錯1個題不給分)1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(×)數(shù)據(jù)項2、對任何數(shù)據(jù)結構鏈式存儲結構一定優(yōu)于順序存儲結構。(×)3、隊列和棧都是運算受限的線性表，只允許在表的兩端進行運算。（×）4、數(shù)組不適合作為任何二叉樹的存儲結構。（×）5、哈夫曼樹無左右子樹之分。(×)6、拓撲排序算法把一個無向圖中的頂點排成一個有序序列。（×）7、B-樹的插入算法中，通過結點的向上“分裂”，代替了專門的平衡調整。（√）8、倒排文件與多重表文件的次關鍵字索引結構是不同的。（√）9、快速排序和歸并排序在最壞情況下的比較次數(shù)都是O(nlog2n)。（×）10、稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（√）得分三、填空（本大題共10小題，每小題1.5分，總計10分）(填對1個題給1.5分，填錯1個題不給分)1、下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：（log2n）i=1；WHILE（i<n）i=i*2；2、在雙向鏈表結構中，若要求在p指針所指的結點之前插入指針為s所指的結點，則需執(zhí)行下列語句：s->next=p；s->prior=p->prior；p->prior=s；(p->prior->next)=s；3、隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是（先進先出）。4、已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹有（12）個葉子結點。5、在完全二叉樹中，編號為i和j的兩個結點處于同一層的條件是(?log2i?=?log2j?)。6、在有向圖的鄰接矩陣表示中，計算第I個頂點入度的方法是（第I列非零元素個數(shù)或意思相同的描述）。7、在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關鍵碼值20，需做的關鍵碼比較次數(shù)為（4）.8、外排序的基本操作過程是（生成有序歸并段（順串））和歸并。9、鏈接存儲的特點是利用（指針）來表示數(shù)據(jù)元素之間的邏輯關系。10、用一維數(shù)組設計棧，初態(tài)是?？?，top=0。現(xiàn)有輸入序列是a、b、c、d，經過push、push、pop、push、pop、push操作后，輸出序列是（bc），棧頂指針是（2或d都給分）。得分四、應用題（本大題共6小題，每小題6分，總計36分）1、利用兩個棧sl,s2模擬一個隊列時，如何用棧的運算實現(xiàn)隊列的插入，刪除以及判隊空運算。請簡述這些運算的算法思想。(本題6分)答：棧的特點是后進先出，隊列的特點是先進先出。初始時設棧s1和棧s2均為空。（1）用棧s1和s2模擬一個隊列的輸入：設s1和s2容量相等。分以下三種情況討論：若s1未滿，則元素入s1棧；若s1滿，s2空，則將s1全部元素退棧，再壓棧入s2，之后元素入s1棧；若s1滿，s2不空（已有出隊列元素），則不能入隊。（2）用棧s1和s2模擬隊列出隊（刪除）：若棧s2不空，退棧，即是隊列的出隊；若s2為空且s1不空，則將s1棧中全部元素退棧，并依次壓入s2中，s2棧頂元素退棧，這就是相當于隊列的出隊。若棧s1為空并且s2也為空，隊列空，不能出隊。（3）判隊空若棧s1為空并且s2也為空，才是隊列空。（要點答出或意思說清楚就給分，若要點沒有完全答出則酌情扣分）FEFECIABGDH解：（共6分）（畫對給6分，若有錯誤酌情扣分）設有正文AADBAACACCDACACAAD,字符集為A,B,C,D,設計一套二進制編碼，使得上述正文的編碼最短。1351359000111（1）寫出：字符A，B，C，D出現(xiàn)的次數(shù)為9,1,5,3或相應意思則這給1分。（2）畫出哈夫曼樹給4分。（不一定必須與右圖相同，只要畫正確就給分）（3寫出其編碼：哈夫曼編碼如下A:1B:000C:01D:001（哈夫曼編碼不一定與上述一致，只要寫對就給分）給1分。4、已知某圖的鄰接表為如右圖所示：（1）寫出此鄰接表對應的鄰接矩陣；（2）寫出由v1開始的深度優(yōu)先遍歷的序列；（3）寫出由v1開始的深度優(yōu)先的生成樹；（4）寫出由v1開始的廣度優(yōu)先遍歷的序列；（5）寫出由v1開始的廣度優(yōu)先的生成樹；解：（共6分）（1）（2分）（2）V1V2V3V4V5（1分）(4)V1V2V3V4V5（1分）(5)(3)（1分）（1分）(5)V1V2V1V2V3V4V5V1V1V2V3V4V55、設哈希(Hash)表的地址范圍為0～17，哈希函數(shù)為：H(K)=KMOD16,K為關鍵字，用線性探測再散列法處理沖突，輸入關鍵字序列:(10,24,32,17,31,30,46,47,40,63,49)造出哈希表，試回答下列問題：(1)畫出哈希表示意圖；(2)若查找關鍵字63，需要依次與哪些關鍵字比較?(3)若查找關鍵字60，需要依次與哪些關鍵字比較?(4)假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。解：（共6分）（1）（3分）散列地址01234567891011121314151617關鍵字3217634924401030314647比較次數(shù)11631211133（2）查找關鍵字63，H（k）=63MOD16=15，依次與31，46，47，32，17，63比較。（1分）（3）查找關鍵字60，H（k）=60MOD16=12，散列地址12內為空，查找失敗。（1分）（4）ASLsucc=23/11（1分）6、有一隨機數(shù)組(25,84,21,46,13,27,68,35,20),現(xiàn)采用某種方法對它們進行排序,其每趟排序結果如下,則該排序方法是什么?初始:25,84,21,46,13,27,68,35,20第一趟:20,13,21,25,46,27,68,35,84第二趟:13,20,21,25,35,27,46,68,84第三趟:13,20,21,25,27,35,46,68,84答：該排序方法為快速排序。得分五、算法設計題（本大題共3小題，每小題8分，總計24分）1、已知一個單鏈表中每個結點存放一個整數(shù)，并且結點數(shù)不少于2，請設計算法以判斷該鏈表中第二項起的每個元素值是否等于其序號的平方減去其前驅的值，若滿足則返回ture，否則返回false.（8分）解：（共8分）typedeffalse0typedeftrue1typedefstructnode{ElemTypedata;structnode*next;}node,*LinkList;intJudge（LinkedListla）zz{p=la->next->next；pre=la->next；i=2；while（p!=null）if（p->data==i*i-pre->data）{i++；pre=p；p=p->next；}elsebreak；if（p!=null）return（false）；elsereturn（true）；}2、設一棵二叉樹中各結點的值互不相同，其前序序列和中序序列分別存于兩個一維數(shù)組pre[1..n]和mid[1..n]中，試遍寫算法建立該二叉樹的二叉鏈表。解：（共8分）typedefstructBiNode{ElemTypedata;StructBiNode*lchild,*rchild;}BiNode,*BiTree;voidPreInCreat(BiTreeroot,ElemTypepre[],ElemTypein[],intl1,inth1,intl2,inth2){root=(BiTree)malloc(sizeof(BiNode));root->data=pre[l1];for(i=l2;I<=h2;I++)if(in[i]==pre[l1]break;if(i==l2)root->lchild=null;elsePreInCreat(root->lchild,pre,in,l1+1,l1+(i-l2),l2,i-1);if(i==h2)root->rchild=null;elsePreInCreat(root->rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2);}3、以鄰接表為存儲結構，寫出圖的深度優(yōu)先搜索DFS算法的非遞歸算法。解：（共8分）#defineVexNum10typedefstructnode{intadjvex;structnode*nextarc;}ArcNode;typedefstruct{vertypedata;ArcNode*firstarc;}Adjlist[VexNum];typedefstruct{Adjlistadjlist;intvexnum,arcnum;}Graph;VoidDFS(Graph