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

信息科學(xué)技術(shù)學(xué)院2010-2011學(xué)年第一學(xué)期考試科目：數(shù)據(jù)結(jié)構(gòu)與算法 考試時間：2010年11月12題一二三四（45總得一、填空題（共20分，填空題的答案也寫在空白答題紙上（2分）12120n2+3nlogn2n3，則該算法的時間復(fù)雜度為/++-C*+ E （3分）push和pop/++-C*+ E 432109876468753290256748931432105678123456987046538172A147986530214365879（2分）右上圖是一棵表達(dá)式二叉樹，它所對應(yīng)的不帶冗余括號的等價四則運(yùn)算中綴表達(dá)式是(A-B+C)/(D*E+(F+G))。（B類的有修改）b)+c”中的括號冗余，但“a+(b+c)”括號不冗余。（2分）下面術(shù)語中， 與數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)無a)順序 b)鏈 c)隊 d)循環(huán)鏈 e)（2分）字符串""的長度 1字 6（3 ；處于離最遠(yuǎn)，而且子結(jié)點權(quán)重和最小的那個結(jié)點擁有的 m-(n-1)%(m-1)或者n-(m-1)*[(n-1)/(m-1)取下整]（有變種）（3分）一棵二叉搜索樹（BST）結(jié)點的中序周游序列是A、B、C、D、E、F。若根結(jié)點為E，則它的一種可能的前序遍歷為_d (a). (b). (c). (d).（3分）11TimDotEvaRomKimGuyAnn,JimKayRon,Jan，按字典建立最小堆（Ann為堆頂，所得到最小堆為：_Ann,DotEvaJimJan,GuyTimRomKayRon, 二、算法填空（共20分，每個空格填0個語句或多個語句個兄弟時標(biāo)記位rtag為1，否則為0。以下算法給出從帶雙標(biāo)記位的層次次序表示導(dǎo)出各結(jié)點的llinkrlink的過程，請?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(-}三、辨析與簡答（15分1（5O表示法，需要給出分析過程。在模式匹配算法KMPStrMatching中，利用特征向量算法中沒有回溯的過程，因此算法時間復(fù)雜度與文本TO(|T|)；KMP模式匹配方式，因此其時間代價也與PO(|P|)；回答出復(fù)雜度為O(|P|+|T|)13分； 計算特征向量的算法本身采用的也是KMP模式匹配方式，其復(fù)雜度與模式長度成正比，得1分。2（524種。 8種：abcdbacddcabdcbacabdcbaddabcab相鄰，d在最外層：分兩種情況，ab/ba在中間，和在隊列一頭雙端隊列可以在隊列的兩端進(jìn)行和刪除操作，既可在隊尾進(jìn)行/刪除，也可在隊頭進(jìn)行/刪除。第一個元素從左或右入隊沒有區(qū)別，以后每個元素都有兩種入隊方式。即有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),請把上述1-16的人群歸為若干個，使得都是親戚，而之間不存在親1030萬。請問你采用什么數(shù)據(jù)結(jié)構(gòu)來輔助進(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è)計與實現(xiàn)（45分助數(shù)據(jù)結(jié)構(gòu)請簡單定義。對算法設(shè)計有質(zhì)量要求，如果時間空間代價低效將扣分。1.（15分）template<classclass{voidboolenQueue(constT booldeQueue(T&item); //返回隊頭元素并刪除之，成功則返回真boolgetFront(T&item); //返回隊頭元素，但不刪除，成功則返回真boolisEmpty(); //返回真，若隊列已空bool //基本思想：4921（搜索）樹（先出隊依次O(nO(nlogn)。但情況，例如隊列本身有序（或接近有序BST，時間會為O(n^2)。AVL樹或樹，使得O(nlogn)2O(nlogn) 、直接選擇這樣O(n^2)的簡單算法，扣1分B做法一：類似于排序的思想。讓輔助隊列B保持有序，每次從原隊列A出隊一個元素e,e在輔助隊列中應(yīng)該的合適位置。即，如果輔助隊列中當(dāng)前的元素比e小，則出隊，并隊尾，若比e大，則先e隊尾，在將輔助隊列中尚未處理過的原有元素依次出隊、入隊。在每一輪處理中，Bm并出隊,a依次出隊，與之比較,a>=ma列，否則，若a<mma替換mm加入輔助n-1輪即可。無 O（n^2基本做法得4分，時空代價分析各1份。相應(yīng)的代碼實現(xiàn)分成3部分（選擇 選擇第k小元素正確得5分，其他得4分。采用棧（O（n）,時間代價O（n^2，1采用數(shù)組（或STL容器，導(dǎo)入數(shù)組后，但直接采用qsort()系統(tǒng)函數(shù)進(jìn)行快速排序，再倒O(n+logn),O(nlogn)）2（15ff值的結(jié)點。template<classclassBinaryTreeNode //二叉樹結(jié)點ADT value()const; //返回當(dāng)前結(jié)點的數(shù)據(jù)BinaryTreeNode<T>*leftchild()const; //返回左子樹BinaryTreeNode<T>*rightchild()const; //返回右子樹voidsetLeftchild(BinaryTreeNode<T>*);//設(shè)置左子樹voidsetRightchild(BinaryTreeNode<T>*);//設(shè)置右子樹voidsetValue(constT&val); //設(shè)置數(shù)據(jù)域boolisLeaf // 42分9分ffBSTf值的那個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樹，找出大于等于f且與f絕對值最小的結(jié)點for(tmp=root;tmp!=null;){ //f if(tmp->value()== result= return //當(dāng)前結(jié)點小于f elseif(tmp->value()< tmp=tmp- //當(dāng)前結(jié)點大于fresult result= tmp=tmp- }return}3（15template<class //classTreeNode bool //T //TreeNode<T //TreeNode<T //voidsetValue(constT& //voidsetChild(TreeNode<T // // //以第一個左孩子結(jié)voidInsertNext(TreeNode<T> //以右兄弟的結(jié)template<class //class publicTreeNode<T>* //33分。9分簡潔的非遞歸前序周游：遇到一個結(jié)點，就該結(jié)點，并把此結(jié)點的非空右結(jié)點推入棧中，然后下降Template<classVoidtraverse(TreeNode<T>* Stack<TreeNode<T>*> TreeNode<T>*curr= while(!s.empty()|| if(curr->RightSibling()!= curr=curr-> if(curr==NULL) curr= 類似于二叉樹的非遞歸前序,類似于二叉樹的非遞歸前序, 為棧的深度，平均為O(log 方法二:基本一樣,當(dāng)左子樹周游不下去時，從棧頂中推出待的結(jié)點，繼續(xù)周游。在算法執(zhí)行過程中只有非voidTree<T>::RootFirstTraverse(TreeNode<T>*root){usingstd::stack;stack<TreeNode<T>*>aStack;TreeNo