數(shù)算期中試題-2010試卷答案

信息科學(xué)技術(shù)學(xué)院2010-2011學(xué)年第一學(xué)期考試科目：數(shù)據(jù)結(jié)構(gòu)與算法 考試時(shí)間：2010年11月12題一二三四（45總得一、填空題（共20分，填空題的答案也寫在空白答題紙上（2分）12120n2+3nlogn2n3，則該算法的時(shí)間復(fù)雜度為/++-C*+ E （3分）push和pop/++-C*+ E 432109876468753290256748931432105678123456987046538172A147986530214365879（2分）右上圖是一棵表達(dá)式二叉樹(shù)，它所對(duì)應(yīng)的不帶冗余括號(hào)的等價(jià)四則運(yùn)算中綴表達(dá)式是(A-B+C)/(D*E+(F+G))。（B類的有修改）b)+c”中的括號(hào)冗余，但“a+(b+c)”括號(hào)不冗余。（2分）下面術(shù)語(yǔ)中， 與數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)無(wú)a)順序 b)鏈 c)隊(duì) d)循環(huán)鏈 e)（2分）字符串""的長(zhǎng)度 1字 6（3 ；處于離最遠(yuǎn)，而且子結(jié)點(diǎn)權(quán)重和最小的那個(gè)結(jié)點(diǎn)擁有的 m-(n-1)%(m-1)或者n-(m-1)*[(n-1)/(m-1)取下整]（有變種）（3分）一棵二叉搜索樹(shù)（BST）結(jié)點(diǎn)的中序周游序列是A、B、C、D、E、F。若根結(jié)點(diǎn)為E，則它的一種可能的前序遍歷為_(kāi)d (a). (b). (c). (d).（3分）11TimDotEvaRomKimGuyAnn,JimKayRon,Jan，按字典建立最小堆（Ann為堆頂，所得到最小堆為：_Ann,DotEvaJimJan,GuyTimRomKayRon, 二、算法填空（共20分，每個(gè)空格填0個(gè)語(yǔ)句或多個(gè)語(yǔ)句個(gè)兄弟時(shí)標(biāo)記位rtag為1，否則為0。以下算法給出從帶雙標(biāo)記位的層次次序表示導(dǎo)出各結(jié)點(diǎn)的llinkrlink的過(guò)程，請(qǐng)?zhí)顚懰惴ㄖ械目瞻滋?，以完成相?yīng)的功能。class {//Tintltag, //Tree<T>::Tree(DualTagTreeNode*nodeArray,intcount) usingstd::queue;queue<TreeNode<T>*>aQueue;TreeNode<T>*pointer=newTreeNode<T>;root=pointer;for(inti=0;i<count-1;i++)if 【1 elsepointer->setChild(NULL)TreeNode<T>*temppointer=newTreeNode<T>;if(nodeArray[i].rtag==0) }elsepointer=aQueue.front();}pointer=}pointer–>setValue(nodeArray[count-pointer–> pointer–>33(3)pointer-3(2)pointer-2(1)nodeArray[i].ltag==int*findNext(stringP){inti=0,k=-1;intint*next=newint[m];while(i<m-while(k>=0&&P[i]!=P[k]) 66分，if3}

}return}intKMPStrMatching(StringT,String int*N,intstart)intistart,j i為模式的下標(biāo)變量，jintpLenP.length(tLenT.length();//iftLenpLenreturn //whilei j //4分，if4分，if2else }2分//(j-pLen+12分//(j-pLen+1)1return(j- elsereturn(-}三、辨析與簡(jiǎn)答（15分1（5O表示法，需要給出分析過(guò)程。在模式匹配算法KMPStrMatching中，利用特征向量算法中沒(méi)有回溯的過(guò)程，因此算法時(shí)間復(fù)雜度與文本TO(|T|)；KMP模式匹配方式，因此其時(shí)間代價(jià)也與PO(|P|)；回答出復(fù)雜度為O(|P|+|T|)13分； 計(jì)算特征向量的算法本身采用的也是KMP模式匹配方式，其復(fù)雜度與模式長(zhǎng)度成正比，得1分。2（524種。 8種：abcdbacddcabdcbacabdcbaddabcab相鄰，d在最外層：分兩種情況，ab/ba在中間，和在隊(duì)列一頭雙端隊(duì)列可以在隊(duì)列的兩端進(jìn)行和刪除操作，既可在隊(duì)尾進(jìn)行/刪除，也可在隊(duì)頭進(jìn)行/刪除。第一個(gè)元素從左或右入隊(duì)沒(méi)有區(qū)別，以后每個(gè)元素都有兩種入隊(duì)方式。即有2^3=8a,b,c,d,各種排列如下：第一次放入a，形成：b 第三次放入c，則有：cababccbabacdcabcabddabcabcddcbacbaddbac8種。8320.5(1,2),(3,4),(3,5),(1,7),(3,6),(8,9),(3,11),(3,12),(3,13),(14,15),(16,10),(14,16),請(qǐng)把上述1-16的人群歸為若干個(gè)，使得都是親戚，而之間不存在親1030萬(wàn)。請(qǐng)問(wèn)你采用什么數(shù)據(jù)結(jié)構(gòu)來(lái)輔助進(jìn)(1){1,2,3,4,5,6,7,11,12,13}{8,9}{10,14,15,16}，2分(2)并查集；重量權(quán)衡合并規(guī)則與路徑壓縮規(guī)則，31四、算法設(shè)計(jì)與實(shí)現(xiàn)（45分助數(shù)據(jù)結(jié)構(gòu)請(qǐng)簡(jiǎn)單定義。對(duì)算法設(shè)計(jì)有質(zhì)量要求，如果時(shí)間空間代價(jià)低效將扣分。1.（15分）template<classclass{voidboolenQueue(constT booldeQueue(T&item); //返回隊(duì)頭元素并刪除之，成功則返回真boolgetFront(T&item); //返回隊(duì)頭元素，但不刪除，成功則返回真boolisEmpty(); //返回真，若隊(duì)列已空bool //基本思想：4921（搜索）樹(shù)（先出隊(duì)依次O(nO(nlogn)。但情況，例如隊(duì)列本身有序（或接近有序BST，時(shí)間會(huì)為O(n^2)。AVL樹(shù)或樹(shù)，使得O(nlogn)2O(nlogn) 、直接選擇這樣O(n^2)的簡(jiǎn)單算法，扣1分B做法一：類似于排序的思想。讓輔助隊(duì)列B保持有序，每次從原隊(duì)列A出隊(duì)一個(gè)元素e,e在輔助隊(duì)列中應(yīng)該的合適位置。即，如果輔助隊(duì)列中當(dāng)前的元素比e小，則出隊(duì)，并隊(duì)尾，若比e大，則先e隊(duì)尾，在將輔助隊(duì)列中尚未處理過(guò)的原有元素依次出隊(duì)、入隊(duì)。在每一輪處理中，Bm并出隊(duì),a依次出隊(duì)，與之比較,a>=ma列，否則，若a<mma替換mm加入輔助n-1輪即可。無(wú) O（n^2基本做法得4分，時(shí)空代價(jià)分析各1份。相應(yīng)的代碼實(shí)現(xiàn)分成3部分（選擇 選擇第k小元素正確得5分，其他得4分。采用棧（O（n）,時(shí)間代價(jià)O（n^2，1采用數(shù)組（或STL容器，導(dǎo)入數(shù)組后，但直接采用qsort()系統(tǒng)函數(shù)進(jìn)行快速排序，再倒O(n+logn),O(nlogn)）2（15ff值的結(jié)點(diǎn)。template<classclassBinaryTreeNode //二叉樹(shù)結(jié)點(diǎn)ADT value()const; //返回當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)BinaryTreeNode<T>*leftchild()const; //返回左子樹(shù)BinaryTreeNode<T>*rightchild()const; //返回右子樹(shù)voidsetLeftchild(BinaryTreeNode<T>*);//設(shè)置左子樹(shù)voidsetRightchild(BinaryTreeNode<T>*);//設(shè)置右子樹(shù)voidsetValue(constT&val); //設(shè)置數(shù)據(jù)域boolisLeaf // 42分9分ffBSTf值的那個(gè)1,2,4步均為O(logn)O(logn) if(root== return BinaryTreeNode*tmp= TMax,Min, BinaryTreeNode*Result= For(tmp=root;tmp!=null;tmp=tmp- Min= For(tmp=root;tmp!=null;tmp=tmp- Max=}fceilMax //floor((Max+Min)/20.5),result ////BST樹(shù)，找出大于等于f且與f絕對(duì)值最小的結(jié)點(diǎn)for(tmp=root;tmp!=null;){ //f if(tmp->value()== result= return //當(dāng)前結(jié)點(diǎn)小于f elseif(tmp->value()< tmp=tmp- //當(dāng)前結(jié)點(diǎn)大于fresult result= tmp=tmp- }return}3（15template<class //classTreeNode bool //T //TreeNode<T //TreeNode<T //voidsetValue(constT& //voidsetChild(TreeNode<T // // //以第一個(gè)左孩子結(jié)voidInsertNext(TreeNode<T> //以右兄弟的結(jié)template<class //class publicTreeNode<T>* //33分。9分簡(jiǎn)潔的非遞歸前序周游：遇到一個(gè)結(jié)點(diǎn)，就該結(jié)點(diǎn)，并把此結(jié)點(diǎn)的非空右結(jié)點(diǎn)推入棧中，然后下降Template<classVoidtraverse(TreeNode<T>* Stack<TreeNode<T>*> TreeNode<T>*curr= while(!s.empty()|| if(curr->RightSibling()!= curr=curr-> if(curr==NULL) curr= 類似于二叉樹(shù)的非遞歸前序,類似于二叉樹(shù)的非遞歸前序, 為棧的深度，平均為O(log 方法二:基本一樣,當(dāng)左子樹(shù)周游不下去時(shí)，從棧頂中推出待的結(jié)點(diǎn)，繼續(xù)周游。在算法執(zhí)行過(guò)程中只有非voidTree<T>::RootFirstTraverse(TreeNode<T>*root){usingstd::stack;stack<TreeNode<T>*>aStack;TreeNo