東北林業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)(A)2005-2006答案

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