數(shù)據(jù)結(jié)構(gòu)試卷ds答案

一、選擇題（每題2分，共20分123456789CDCADDBDCB二、綜合填空題(每空2分，共24分1中序遍22n-324456n-7p-89k三、算法閱讀題16分1．(8分算能：將鏈表中數(shù)據(jù)域值最小的那個(gè)鏈結(jié)點(diǎn)移到鏈表的最前面，以及所有等價(jià)表述；(4分)pre指向鏈表中數(shù)據(jù)域最小值結(jié)點(diǎn)的前驅(qū)(2分q指向數(shù)據(jù)域最小值結(jié)點(diǎn)(2分)2．(8分算能：(1)插入排序/直接插入排序(5分(2)作為監(jiān)視哨(或哨兵)或其它等價(jià)描述(3分)四、應(yīng)用題(30分1．(8分(1)(4分abcdefghk06457706687218天(2分關(guān)鍵活動(dòng)：<a,b>,<b,e><e,h><h,k>(2分,0.5分用權(quán)值表示關(guān)鍵活動(dòng)（6,1,7,4）不扣分。2．(7分應(yīng)用算法求解，最短路徑長度矩陣序列如下01010 00 23820101690610 16209 610 312045 20 從D(4)中可以看出每列中最大值依次為9,12,16,20,其中最小值為9，所以中心俱樂部應(yīng)設(shè)在A村莊，使得離中心最遠(yuǎn)的村莊離最近，最短距離為9。2分。3．(6分（60.571分 （2分）(10分BBAECDFGH4．(5分H(key)=key%13計(jì)算出鍵值序列的散列地址。并用探查次數(shù)表示待0123456789131221191101234567891312211911查找成功1125．(4分14五、算法設(shè)計(jì)題10分voidLayer(BiTree{struct{BiTreebase[MaxSize]; //1 //1if(b!=NULL)printf("%c",b- //該結(jié)點(diǎn)和結(jié)點(diǎn)入隊(duì)列，1 //循環(huán)條件判隊(duì)空，1{ //過的結(jié)點(diǎn)出隊(duì)列，1{printf("%c",b->lchild->data);//先左孩子，1分 //左孩子入隊(duì)列，1分q.rear=(q.rear+1)%MaxSize;}{printf("%c",b->rchild->data);//右孩子，1分q.base[q.rear]=b->rchild;//右孩子入隊(duì)列，1分q.rear=(q.rear+1)%MaxSize;}}}voidLayer(BiTree{SqQueue //初始化隊(duì)列，1if(p!=NULL)printf("%c",p- //該結(jié)點(diǎn)，1 //結(jié)點(diǎn)入隊(duì)列，1 //循環(huán)條件，1{ //過的結(jié)點(diǎn)出隊(duì)列，1 /