計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)統(tǒng)考?xì)v年真題答案2009-2015

1、2009 1-5：BCDBC6-10：BADBA41.該方法求得的路徑不一定是最短路徑。例如，對(duì)于下圖所示的帶權(quán)圖，如果按照題中的原則，從A到C的最短路徑為ABC，事實(shí)上其最短路徑為ADC。 42.（1）算法的基本設(shè)計(jì)思想：定義兩個(gè)指針變量p和q，初始時(shí)均指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。P指針沿鏈表移動(dòng)；當(dāng)p指針移動(dòng)到第k個(gè)結(jié)點(diǎn)時(shí)，q指針開始與p指針同步移動(dòng)；當(dāng)p指針移動(dòng)到鏈表最后一個(gè)結(jié)點(diǎn)時(shí)，q指針?biāo)冈貫榈箶?shù)第k個(gè)結(jié)點(diǎn)。以上過(guò)程對(duì)鏈表僅進(jìn)行一遍掃描。 （2）算法的詳細(xì)實(shí)現(xiàn)步驟： count=0,p和q指向鏈表表頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)； 若p為空，轉(zhuǎn)； 若count等于k,則q指向下一個(gè)結(jié)點(diǎn);否則,co

2、unt=count+1; p指向下一個(gè)結(jié)點(diǎn)，轉(zhuǎn)步驟； 若count等于k,則查找成功,輸出該結(jié)點(diǎn)的data域的值,返回1;返回； 查找失敗,返回0; 算法結(jié)束。（3）算法實(shí)現(xiàn)：typedef struct LNode int data; struct LNode * link; * LinkList;int SearchN(LinkList list,int k)LinkList p,q;int count=0; /*計(jì)數(shù)器賦初值*/p=q=list-link; /*p和q指向鏈表表頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)*/while(p!=NULL)if(countlink;/*q移到下一個(gè)結(jié)點(diǎn)*/ p=p-l

3、ink; /*p移到下一個(gè)結(jié)點(diǎn)*/if(countdata); /*查找成功*/ return (1);/else/SearchN 2010 1-5：DCDCB 6-11：ACBBDA41.（1）構(gòu)造的散列表如下下標(biāo)0123456789關(guān)鍵字71481130189（2）查找成功的平均查找長(zhǎng)度:ASL成功=12/7。 查找不成功的平均查找長(zhǎng)度:ASL不成功=18/7。42.（1）給出算法的基本設(shè)計(jì)思想：先將n個(gè)數(shù)據(jù)x0x1xpxn-1原地逆置，得到xn-1xpxp-1x0,然后再將前n-p個(gè)和后p個(gè)元素分別原地逆置，得到最終結(jié)果:xpxp+1xn-1x0x1xp-1。（2）算法實(shí)現(xiàn)： void

4、reverse(int r,int left,int right) int k=left,j=right,temp; /k等于左邊界left,j等于右邊界right while(k0&pn)reverse(r,0,n-1);/將全部數(shù)據(jù)逆置reverse(r,0,n-p-1);/將前n-p個(gè)元素逆置reverse(r,n-p,n-1);/將后p個(gè)元素逆置（3）說(shuō)明算法復(fù)雜性：上述算法的時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)。2011 1-5：ABBCC 6-10：DACBA 41.高分筆記 圖 最后一題42. (1)算法的基本設(shè)計(jì)思想：(5分) 1) 比較笨的方法：將兩升序序列歸并排序，然

5、后求其中位數(shù)，時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度O(n)。 2) 高效的方法：分別求兩個(gè)升序序列A和B的中位數(shù)，設(shè)為a和b。如果a=b，則a或者b即為所求的中位數(shù)。原因：如果將兩序列歸并排序，則最終序列中，排在子序列ab前邊的元素為先前兩序列中排在a和b前邊的元素;排在子序列ab后邊的元素為先前兩序列a和b后邊的元素。所以子序列ab一定位于最終序列的中間，有因?yàn)閍=b，顯然a就是中位數(shù)。如果ab(假設(shè)a原因：同樣可以用歸并排序后的序列來(lái)驗(yàn)證，歸并后排序后必然有形如ab的序列出現(xiàn)，中位數(shù)必然出現(xiàn)在(a，b)范圍內(nèi)。因此可以做如下處理：舍棄a所在序列A之中比較小的一半，同時(shí)舍棄b所在序列B之中比較大

6、的一半。在保留的兩個(gè)升序序列中求出新的中位數(shù)a和b，重復(fù)上述過(guò)程，直到兩個(gè)序列只含一個(gè)元素為止，則較小者即為所求中位數(shù)。(2)算法實(shí)現(xiàn)(高效方法)：(8分)int Search(int A, int B, int n) int s1,e1,mid1,s2,e2,mid2; s1=0;e1=n-1;s2=1;e2=n-1; while(s1!=e1|s2!=e2)mid1=(s1+e1)/2;mid2=(s2+e2)/2;if(Amid1=Bmid2) return Amid1;if(Amid1len2) longList=L1-next; shortlist=L2-next; L=len1-l

7、en2;/表長(zhǎng)之差 /if else longList=L2-next; shortlist=L1-next; L=len2-len1;/表長(zhǎng)之差 /else While(L-) longList=longList-next; while(longList!=NULL) if(longList=shortList)/同步尋找共同結(jié)點(diǎn) returnlongList; else longList=longList-next; shortlist=shortlist-next; /else /while returnNULL;/Search_First_Common（3）算法的時(shí)間復(fù)雜度為O(len

8、1+len2)，空間復(fù)雜度為O(1)。2013 1-5：DCDBA 6-10：CCDCA 41.（1）給出算法的基本設(shè)計(jì)思想：（4分）算法的策略是從前向后掃描數(shù)組元素，標(biāo)記出一個(gè)可能成為主元素的元素Num。然后重新計(jì)數(shù)，確認(rèn)Num是否是主元素。算法可分為以下兩步：選取候選的主元素：依次掃描所給數(shù)組中的每個(gè)整數(shù)，將第一個(gè)遇到的整數(shù)Num保存到c中記錄Num的出現(xiàn)次數(shù)為1；若遇 到 的下一個(gè) 整 數(shù) 仍 等 于Num則計(jì)數(shù)加一，否則計(jì)數(shù)減一；當(dāng)計(jì)數(shù)減到0時(shí)，將遇到的下一個(gè)整數(shù)保存到c中，計(jì)數(shù)重新記為1，開始新一輪計(jì)數(shù)，即從當(dāng)前位置開始重復(fù)上述過(guò)程，直到掃描完全部數(shù)組元素。判斷c中元素是否是真正的主

9、元素：再次掃描該數(shù)組，統(tǒng)計(jì)c中元素出現(xiàn)的次數(shù)，若大于n/2，則為主元素；否則，序列中不存在主元素。（2）算法實(shí)現(xiàn)：（7分）intMajority(intA,intn) inti,c,count=1;/c用來(lái)保存候選主元素，count用來(lái)計(jì)數(shù) c=A0;/設(shè)置A0為候選主元素 for(i=1;i0) count-;/處理不是候選主元素的情況 else/更換候選主元素，重新計(jì)數(shù) c=Ai; count=1; /else /for if(count0) for(i=count=0;in/2)returnc;/確認(rèn)候選主元素 elsereturn-1;/不存在主元素/Majority42.（1）采用順

10、序存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素按其查找概率降序排列。（2分）采用順序查找方法。（1分）查找成功時(shí)的平均查找長(zhǎng)度=0.351+0.352+0.153+0.154=2.1。（2分）（2）【答案一】采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，數(shù)據(jù)元素按其查找概率降序排列，構(gòu)成單鏈表。（2分）采用順序查找方法。（1分）查找成功時(shí)的平均查找長(zhǎng)度=0.351+0.352+0.153+0.154=2.1。（2分）【答案二】采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，構(gòu)造二叉排序樹，元素存儲(chǔ)方式見下圖。（2分）2014 1-5：CBADC 6-11：DDDDBC41解答：考查二叉樹的帶權(quán)路徑長(zhǎng)度，二叉樹的帶權(quán)路徑長(zhǎng)度為每個(gè)葉子結(jié)點(diǎn)的深度與權(quán)值之積的總和，可以使用先序

11、遍歷或?qū)哟伪闅v解決問(wèn)題。1）算法的基本設(shè)計(jì)思想：基于先序遞歸遍歷的算法思想是用一個(gè)static變量記錄wpl，把每個(gè)結(jié)點(diǎn)的深度作為遞歸函數(shù)的一個(gè)參數(shù)傳遞，算法步驟如下：若該結(jié)點(diǎn)是葉子結(jié)點(diǎn)，那么變量wpl加上該結(jié)點(diǎn)的深度與權(quán)值之積；若該結(jié)點(diǎn)非葉子結(jié)點(diǎn)，那么若左子樹不為空，對(duì)左子樹調(diào)用遞歸算法，若右子樹不為空，對(duì)右子樹調(diào)用遞歸算法，深度參數(shù)均為本結(jié)點(diǎn)的深度參數(shù)加一；最后返回計(jì)算出的wpl即可?；趯哟伪闅v的算法思想是使用隊(duì)列進(jìn)行層次遍歷，并記錄當(dāng)前的層數(shù)，當(dāng)遍歷到葉子結(jié)點(diǎn)時(shí)，累計(jì)wpl；當(dāng)遍歷到非葉子結(jié)點(diǎn)時(shí)對(duì)該結(jié)點(diǎn)的把該結(jié)點(diǎn)的子樹加入隊(duì)列；當(dāng)某結(jié)點(diǎn)為該層的最后一個(gè)結(jié)點(diǎn)時(shí)，層數(shù)自增1；隊(duì)列空時(shí)遍歷結(jié)

12、束，返回wpl2)二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義如下：typedef struct BiTNode int weight; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;3)算法代碼如下：基于先序遍歷的算法：intWPL(BiTreeroot) return wpl_PreOrder(root,0);/intintwpl_PreOrder(BiTreeroot,intdeep) static int wpl=0;/定義一個(gè)static變量存儲(chǔ)wpl if(root-lchild=NULL&root-lchild=NULL)/若為葉子結(jié)點(diǎn)，累積wpl w

13、pl+=deep*root-weight; if(root-lchild!=NULL)/若左子樹不空，對(duì)左子樹遞歸遍歷 wpl_PreOrder(root-lchild,deep+1); if(root-rchild!=NULL)/若右子樹不空，對(duì)右子樹遞歸遍歷 wpl_PreOrder(root-rchild,deep+1); return wpl;/wpl_PreOrder基于層次遍歷的算法：#defineMaxSize100 /設(shè)置隊(duì)列的最大容量int wpl_LevelOrder(BiTree root) BiTree qMaxSize; /聲明隊(duì)列，end1為頭指針，end2為尾指針

14、 int end1, end2; /隊(duì)列最多容納MaxSize-1個(gè)元素 end1=end2=0; /頭指針指向隊(duì)頭元素，尾指針指向隊(duì)尾的后一個(gè)元素 int wpl=0, deep=0; /初始化wpl和深度 BiTree lastNode; /lastNode用來(lái)記錄當(dāng)前層的最后一個(gè)結(jié)點(diǎn) BiTree newlastNode; /newlastNode用來(lái)記錄下一層的最后一個(gè)結(jié)點(diǎn) lastNode=root; /lastNode初始化為根節(jié)點(diǎn) newlastNode=NULL; /newlastNode初始化為空 qend2+=root; /根節(jié)點(diǎn)入隊(duì) while(end1!=end2) /

15、層次遍歷，若隊(duì)列不空則循環(huán) BiTree t=qend1+; /拿出隊(duì)列中的頭一個(gè)元素 if(t-lchild=NULL&t-lchild=NULL) wpl+=deep*t-weight; /若為葉子結(jié)點(diǎn)，統(tǒng)計(jì)wpl if(t-lchild!=NULL) /若非葉子結(jié)點(diǎn)把左結(jié)點(diǎn)入隊(duì) qend2+=t-lchild; newlastNode=t-lchild; /并設(shè)下一層的最后一個(gè)結(jié)點(diǎn)為該結(jié)點(diǎn)的左結(jié)點(diǎn) if(t-rchild!=NULL) /處理葉節(jié)點(diǎn) qend2+=t-rchild; newlastNode=t-rchild; /if if(t=lastNode)/若該結(jié)點(diǎn)為本層最后一個(gè)結(jié)

16、點(diǎn)，更新lastNode lastNode=newlastNode; deep+=1; /層數(shù)加1 /if/whilereturn wpl; /返回wpl/wpl_LevelOrder注意：上述兩個(gè)算法一個(gè)為遞歸的先序遍歷，一個(gè)為非遞歸的層次遍歷，讀者應(yīng)當(dāng)選取自己最擅長(zhǎng)的書寫方式。直觀看去，先序遍 歷 代 碼 行 數(shù) 少，不用運(yùn)用其他工具，書寫也更容易，希望讀者能掌握。在先序遍歷的算法中，static是一個(gè)靜態(tài)變量，只在首次調(diào)用函數(shù)時(shí)聲明wpl并賦值為0，以后的遞歸調(diào)用并不會(huì)使得wpl為0，具體用法請(qǐng)參考相關(guān)資料中的static關(guān)鍵字說(shuō)明，也可以在函數(shù)之外預(yù)先設(shè)置一個(gè)全局變量，并初始化。不過(guò)考

17、慮到歷年真題算法答案通常都直接僅僅由一個(gè)函數(shù)構(gòu)成，所以參考答案使用static。若對(duì)static不熟悉的同學(xué)可以使用以下形式的遞歸：int wpl_PreOrder(BiTree root,intdeep) int lwpl, rwpl; /用于存儲(chǔ)左子樹和右子樹的產(chǎn)生的wpl lwpl=rwpl=0; if(root-lchild=NULL&root-lchild=NULL) /若為葉子結(jié)點(diǎn)，計(jì)算當(dāng)前葉子結(jié)點(diǎn)的wpl return deep*root-weight; if(root-lchild!=NULL) /若左子樹不空，對(duì)左子樹遞歸遍歷 lwpl=wpl_PreOrder(root-l

18、child,deep+1); if(root-rchild!=NULL) /若右子樹不空，對(duì)右子樹遞歸遍歷 rwpl=wpl_PreOrder(root-rchild,deep+1); return lwpl+rwpl;/wpl_PreOrderC/C+語(yǔ)言基礎(chǔ)好的同學(xué)可以使用更簡(jiǎn)便的以下形式：int wpl_PreOrder(BiTree root,int deep) if(root-lchild=NULL&root-lchild=NULL) /若為葉子結(jié)點(diǎn)，累積wpl return deep*root-weight; return(root-lchild!=NULL?wpl_PreOrde

19、r(root-lchild,deep+1):0)+ (root-rchild!=NULL?wpl_PreOrder(root-rchild,deep+1):0);/wpl_PreOrder這個(gè)形式只是上面方法的簡(jiǎn)化而已，本質(zhì)是一樣的，而這個(gè)形式代碼更短，在時(shí)間有限的情況下更具優(yōu)勢(shì)，能比寫層次遍歷的考生節(jié)約很多時(shí)間，所以讀者應(yīng)當(dāng)在保證代碼正確的情況下，盡量寫一些較短的算法，為其他題目贏得更多的時(shí)間。但是，對(duì)于基礎(chǔ)不扎實(shí)的考生，還是建議使用寫對(duì)把握更大的方法，否則可能會(huì)得不償失。例如在上面的代碼中，考生容易忘記三元式(x?y:z)兩端的括號(hào)，若不加括號(hào)，則答案就會(huì)是錯(cuò)誤的。2015 1-5：DCCBD 6-11：AACBBA41.(1)算法思想：定義一個(gè)大小為N的數(shù)組，初始化為0.在遍歷鏈表的同時(shí)將數(shù)組中索引