2、、設(shè)字符串s1='abcde,,s2=,opqr,,則Concat(sl,s2)=,Index(s2,,p')=。6、已知一棵二叉樹的屮序遍歷結(jié)果為DBHEAFICG,后序遍歷結(jié)果為DHEBIFGCA,則先序遍歷結(jié)果為o7、設(shè)有序表有100個元素，在折半查找時，最大比較次數(shù)是,最小比較次數(shù)是8、設(shè)哈希函數(shù)H(k)=kmod11，哈希表的地址空間為0?11,假定哈希表中已填有關(guān)鍵字分別為17,60,29的記錄。若采用二次探測再散列，則關(guān)鍵字為39的第四個記錄應(yīng)填入位置o若不采用二次探測再散列，而是采用線性探測再散列，則則關(guān)鍵字為39的第四個記錄應(yīng)填入
3、位置。9、設(shè)有關(guān)鍵字輸入序列：(45,25,80,60,18,30,12,40,70),生成一棵二叉查找樹，在等查找概率情況下查找成功時的平均查找長度為o10、以下為鏈式Stack的拷貝構(gòu)造函數(shù)，請在其中的下劃線處填上適當?shù)膬?nèi)容。Stack::Stack(constStack&original)//copyconstructor/*Post:TheStackisinitializedasacopyofStackoriginal."7{NodeFew_copy,*original_node=;if(original_node==NULL)top_no
4、de=NULL;else{//Duplicatethelinkednodes.top_node=new_copy=;while(original_node->next!=NULL){original_node=original_node->next;new_copy->next=newNode(original_node->entry);}二、應(yīng)用題1、對于如圖所示的樹，試回答：（1）樹的度是多少？樹的深度是多少？（2）哪些為非終端結(jié)點？（3）畫出其孩子兄弟鏈表。（4）將該樹轉(zhuǎn)換為二叉樹。（10分）2、以遞歸樹形式畫岀漢諾塔遞歸函數(shù)move（3,1
5、,2,3）的執(zhí)行過程。（8分）（2）從結(jié)點VI出發(fā)分別給出G的一個拓撲序列。3、已知如圖所示帶權(quán)有向圖G,（1）給出鄰接矩陣和鄰接表;對G進行深度優(yōu)先搜索和廣度優(yōu)先搜索，給出結(jié)點序列；（3）4、(1)設(shè)一組記錄的關(guān)鍵字序列為(25,50,15,35,80,85,20,40,36,70),對其進行2■路歸并排序，寫出排序過程。(2)在堆排序、快速排序和歸并排序三種排序方法中，若從節(jié)省存儲空間考慮，則應(yīng)首選哪種方法？若只從算法穩(wěn)定性考慮，則應(yīng)選取哪種方法？若只從最壞情況下排序最快并口要節(jié)省內(nèi)存考慮，應(yīng)選取哪種方法？(10分)三、算法設(shè)計題1、寫岀循環(huán)隊
6、列的類定義，并編寫代碼，實現(xiàn)循環(huán)隊列的入隊和岀隊方法。(10分)classQueue(總10分){public:(4分)Queue();boolempty();boolfull();Error_codeAppend(Qentry&item);Error_codeserve();Error_coderetrieve(Qentry&item);Private:intrear;intlength;Qentryentry
7、Maxq
8、;}Error_codeappend(Qentry&item){if(length==maxq)returnOVERFLOW;
9、real-(rear+1)%maxq;entry[rear]=e;length++;returnOK;}(3分)Error_codeserve(Qentry&item){if(length==0)returnERROR;head=((rear+maxq)-length+l)%maxq;item=entry[head];length—;returnOK;}(3分)2、編寫算法，在兄弟孩子鏈表表示的樹中求葉子結(jié)點數(shù)。(10分)樹的孩子兄弟鏈表定義：typedefstructCSNode{ElemTypedata;StructCSNode*firstch
10、ild,*nextsibling;}CSNode,^CSTree;inttree_leafcount(CSTreeT);3
