PAGE36附錄：大連理工大學(xué)2002年碩士入學(xué)試題數(shù)據(jù)結(jié)構(gòu)部分(共50分)一、算法填空題(20分)1．對(duì)以下函數(shù)填空，實(shí)現(xiàn)將頭指針為h的單鏈表逆置，即原鏈表的第一個(gè)結(jié)點(diǎn)變成逆置后新鏈表的最后一個(gè)結(jié)點(diǎn)，原鏈表的第二個(gè)結(jié)點(diǎn)變成新鏈表的倒數(shù)第二個(gè)結(jié)點(diǎn)，如此等等，直到最后一個(gè)結(jié)點(diǎn)作為新鏈表的第一個(gè)結(jié)點(diǎn)，并返回指向該結(jié)點(diǎn)的指針。設(shè)單鏈表結(jié)點(diǎn)類(lèi)型的定義為typedefstructnode{intdata；strcutnode*next；}NODE；NODE*dlbnz(NODE*h){NODE*p，*q；q=NULL；while(h)p=h；h=h->next；；；}returnq；}2．假設(shè)算術(shù)表達(dá)式由字符串b表示，其中可以包含三種括號(hào)：圓括號(hào)和方括號(hào)及花括號(hào)，其嵌套的順序隨意，如{[]([])}。請(qǐng)對(duì)以下函數(shù)填空，實(shí)現(xiàn)判別給定表達(dá)式中所含括號(hào)是否正確配對(duì)出現(xiàn)的算法。#defineM10intkhjc(char*b){charsM}；inti，j=0，f=1；j=0；for(i=0；f&&b[i]!=’\0’；i++){switch(b[i]){case’(’：；break；case’[’：；break；case‘{’：；break；case’)’：case’]’：case’[’：if(j==0;||b[I]!=)f=0；}}returnf&&；}3．對(duì)以下函數(shù)填空，實(shí)現(xiàn)以帶頭結(jié)點(diǎn)的單鏈表h為存儲(chǔ)結(jié)構(gòu)的直接選擇排序。設(shè)單鏈表結(jié)點(diǎn)類(lèi)型的定義為typedefstructnode{intkey；structnode*next；}NODE；voidpxx(NODE*h){NODE*p，*q，*m；intz；p=h->next；while(p!=NULL){q=p->next；m=p；while(q!=NULL){if(m->key>q->key)；；}if(p!=m){x=p->key；p->key=m->key；m->key=x；}；}}二、算法設(shè)計(jì)題(30分)請(qǐng)用類(lèi)C或類(lèi)PASCAL語(yǔ)言設(shè)計(jì)實(shí)現(xiàn)下列功能的算法。1．設(shè)二叉排序樹(shù)以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫(xiě)一個(gè)非遞歸算法，從大到小輸出二叉排序樹(shù)中所有其值不小于X的鍵值。(10分)2．設(shè)由n個(gè)整數(shù)組成一個(gè)大根堆(即第一個(gè)數(shù)是堆中的最大值)，請(qǐng)編寫(xiě)一個(gè)時(shí)間復(fù)雜度為O(log2n)的算法，實(shí)現(xiàn)將整數(shù)X插入到堆中，并保證插入后仍是大根堆。(10分)3．請(qǐng)編寫(xiě)一個(gè)算法，判斷含n個(gè)頂點(diǎn)和e條邊的有向圖中是否存在環(huán)。并分析算法的時(shí)間復(fù)雜度。(10分)大連理工大學(xué)2003年碩士入學(xué)試題數(shù)據(jù)結(jié)構(gòu)部分(共75分)一、回答下列問(wèn)題(20分)1．循環(huán)隊(duì)列用數(shù)組A[0．．m—1)存放其數(shù)據(jù)元素。設(shè)tail指向其實(shí)際的隊(duì)尾，front指向其實(shí)際隊(duì)首的前一個(gè)位置，則當(dāng)前隊(duì)列中的數(shù)據(jù)元素有多少個(gè)?如何進(jìn)行隊(duì)空和隊(duì)滿(mǎn)的判斷?2．設(shè)散列表的地址空間為0~10，散列函數(shù)為H(key)=key％11(％為求余函數(shù))，采用線(xiàn)性探查法解決沖突，并將鍵值序列{15，36，50，27，19，48}依次存儲(chǔ)到散列表中，請(qǐng)畫(huà)出相應(yīng)的散列表；當(dāng)查找鍵值48時(shí)需要比較多少次?3．什么是m階B-樹(shù)?在什么情況下向一棵m階B-樹(shù)中插入一個(gè)關(guān)鍵字會(huì)產(chǎn)生結(jié)點(diǎn)分裂?在什么情況下從一棵m階B-樹(shù)中刪除一個(gè)關(guān)鍵字會(huì)產(chǎn)生結(jié)點(diǎn)合并?4．什么是線(xiàn)索二叉樹(shù)?一棵二叉樹(shù)的中序遍歷序列為由djbaechif，前序遍歷序列為abdjcefhi，請(qǐng)畫(huà)出該二叉樹(shù)的后序線(xiàn)索二叉樹(shù)。二、請(qǐng)用類(lèi)C或類(lèi)PASCAL語(yǔ)言進(jìn)行算法設(shè)計(jì)，并回答相應(yīng)問(wèn)題。(45分)1．設(shè)計(jì)一非遞歸算法采用深度優(yōu)先搜索對(duì)無(wú)向圖進(jìn)行遍歷，并對(duì)算法中的無(wú)向圖的存儲(chǔ)結(jié)構(gòu)予以簡(jiǎn)單說(shuō)明。2．用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存放一元多項(xiàng)式Pn(x)=P1xel+P2xe2+…+Pnxen，其中Pi是指數(shù)為ei的項(xiàng)的非零系數(shù)，且滿(mǎn)足0≤e1≤e2…<en=n。請(qǐng)?jiān)O(shè)計(jì)算法將多項(xiàng)式B=Pn2(x)加到多項(xiàng)式A=Pn1(x)，同時(shí)對(duì)算法及鏈表的結(jié)點(diǎn)結(jié)構(gòu)給出簡(jiǎn)單注釋。要求利用Pnl(x)和Pn2(x)的結(jié)點(diǎn)產(chǎn)生最后求得的和多項(xiàng)式，不允許另建和多項(xiàng)式的結(jié)點(diǎn)空間。3．(1){Rl，R2，…，Rn}為待排序的記錄序列，請(qǐng)?jiān)O(shè)計(jì)算法對(duì){R1，R2，…，Rn}按關(guān)鍵字的非遞減次序進(jìn)行快速排序。(2)若待排序的記錄的關(guān)鍵字集合是{30，4，48，25，95，13，90，27，18)，請(qǐng)給出采用快速排序的第一趟、第二趟排序結(jié)果。(3)若對(duì)(2)中給出的關(guān)鍵字集合采用堆排序，請(qǐng)問(wèn)初建的小根堆是什么?(4)當(dāng)給定的待排序的記錄的關(guān)鍵字基本有序時(shí)，應(yīng)采用堆排序還是快速排序?為什么?三、算法填空(10分)1．一棵樹(shù)以孩子兄弟表示法存儲(chǔ)，遞歸算法numberofleaf計(jì)算并返回根為r的樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)(NULL代表空指針)。typedefstructnode{structnode*firstchild，*nextbrother；}TFNNode；intnumberofleaf(TFNNode*r){intnum；if(r==NULL)num=0；elseif(r->firstchild==NULL)num=+numberofleaf；(r->nextbrother)；else；return(num)；}2．在根結(jié)點(diǎn)為r的二叉排序樹(shù)中，插人數(shù)據(jù)域值為x的結(jié)點(diǎn)，要求插入新結(jié)點(diǎn)后的樹(shù)仍是一棵二叉排序樹(shù)(NULL代表空指針)。二叉排序樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)為typedefstructnode{intkey；structnode*lc,*rc；}BiNode；BiNode*insert(BiNode*r,intx){BiNode*p,*q,*s;s=(BiNode*)malloc(sizeof(BiNode));s->key=x;s->lc=NULL;s->rc=NULL;q=NULL;if(r==NULL){r=s;return(r);}p=r;while(){q=p;if()p=p->lc;elsep=p->rc}if(x<q->key);else;return;}清華大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)試題試題內(nèi)容：一、試給出下列有關(guān)并查集(mfsets)的操作序列的運(yùn)算結(jié)果：union(1，2)，union(3，4)，union(3，5)，union(1，7)，union(3，6)，union(8，9)，union(1，8)，union(3，10)，union(3，11)，union(3，12)，union(3，13)，union(14，15)，union(16，0)，union(14，16)，union(1，3)，union(1，14)。(union是合并運(yùn)算，在以前的書(shū)中命名為merge)要求：(1)對(duì)于union(i，j)，以i作為j的雙親；(5分)(2)按i和j為根的樹(shù)的高度實(shí)現(xiàn)union(i，j)，高度大者為高度小者的雙親；(5分)(3)按i和j為根的樹(shù)的結(jié)點(diǎn)個(gè)數(shù)實(shí)現(xiàn)union(i，j)，結(jié)點(diǎn)個(gè)數(shù)大者為結(jié)點(diǎn)個(gè)數(shù)小者的雙親。(5分)二、設(shè)在4地(A，B，C，D)之間架設(shè)有6座橋，如下圖所示：要求從某一地出發(fā)，經(jīng)過(guò)每座橋恰巧一次，最后仍回到原地。(1)試就以上圖形說(shuō)明：此問(wèn)題有解的條件是什么?(5分)(2)設(shè)圖中的頂點(diǎn)數(shù)為n，試用C或Pascal描述與求解此問(wèn)題有關(guān)的數(shù)據(jù)結(jié)構(gòu)并編寫(xiě)一個(gè)算法，找出滿(mǎn)足要求的一條回路。(10分)三、針對(duì)以下情況確定非遞歸的歸并排序的運(yùn)行時(shí)間(數(shù)據(jù)比較次數(shù)與移動(dòng)次數(shù))：(1)輸人的n個(gè)數(shù)據(jù)全部有序；(5分)(2)輸入的n個(gè)數(shù)據(jù)全部逆向有序；(5分)(3)隨機(jī)地輸入幾個(gè)數(shù)據(jù)。(5分)四、簡(jiǎn)單回答有關(guān)AVL樹(shù)的問(wèn)題。(1)在有N個(gè)結(jié)點(diǎn)的AVL樹(shù)中，為結(jié)點(diǎn)增加一個(gè)存放結(jié)點(diǎn)高度的數(shù)據(jù)成員，那么每一個(gè)結(jié)點(diǎn)需要增加多少個(gè)字位(bit)?(5分)(2)若每一個(gè)結(jié)點(diǎn)中的高度計(jì)數(shù)器有8bit，那么這樣的AVL樹(shù)可以有多少層?最少有多少個(gè)關(guān)鍵碼?(5分)五、一個(gè)散列表包含hashSize=13個(gè)表項(xiàng)，其下標(biāo)從0到12，采用線(xiàn)性探查法解決沖突。請(qǐng)按以下要求，將下列關(guān)鍵碼散列到表中。101003245581263292004000(1)散列函數(shù)采用除留余數(shù)法，用％hashSize(取余運(yùn)算)將各關(guān)鍵碼映像到表中。請(qǐng)指出每一個(gè)產(chǎn)生沖突的關(guān)鍵碼可能產(chǎn)生多少次沖突。(7分)(2)散列函數(shù)采用先將關(guān)鍵碼各位數(shù)字折疊相加，再用％hashSize將相加的結(jié)果映像到表中的辦法。請(qǐng)指出每一個(gè)產(chǎn)生沖突的關(guān)鍵碼可能產(chǎn)生多少次沖突。(8分)六、設(shè)一棵二叉樹(shù)的結(jié)點(diǎn)定義為structBinTreeNode{ElemTypedata；BinTreeNode*leftChild,*rightChild；}現(xiàn)采用輸入廣義表表示建立二叉樹(shù)。具體規(guī)定如下：(1)樹(shù)的根結(jié)點(diǎn)作為由子樹(shù)構(gòu)成的表的表名放在表的最前面；(2)每個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)用逗號(hào)隔開(kāi)。若僅有右子樹(shù)，沒(méi)有左子樹(shù)，逗號(hào)不能省略。(3)在整個(gè)廣義表表示輸入的結(jié)尾加上一個(gè)特殊的符號(hào)(例如“#”)表示輸入結(jié)果。；例如，對(duì)于如右圖所示的二叉樹(shù)，其廣義表表示為A(B(D，E(G，))，C(，F(xiàn)))此算法的基本思路是：依次從保存廣義表的字符串ls中輸入每個(gè)字符。若遇到的是字母(假定以字母作為結(jié)點(diǎn)的值)，則表示是結(jié)點(diǎn)的值，應(yīng)為它建立一個(gè)新的結(jié)點(diǎn)，并把該結(jié)點(diǎn)作為左子女當(dāng)(k=1)或右子女(當(dāng)k=2)鏈接到其雙親結(jié)點(diǎn)上。若遇到的是左括號(hào)”(”，則表明子表的開(kāi)始，將A置為1；若遇到的是右括號(hào)”)”，則表明子表結(jié)束。若遇到的是逗號(hào)”，”，則表示以左子女為根的子樹(shù)處理完畢，應(yīng)接著處理以右子女為根的子樹(shù)，將A置為2。在算法中使用了一個(gè)棧s，在進(jìn)入子表之前，將根結(jié)點(diǎn)指針進(jìn)棧，以便括號(hào)內(nèi)的子女鏈接之用。在子表處理結(jié)束時(shí)退棧。相關(guān)的棧操作如下：MakeEmpty(s)置空棧Push(s，p)元素p進(jìn)棧Pop(s)退棧Top(s)存取棧頂元素的函數(shù)下面給出了建立二叉樹(shù)的算法，其中有5個(gè)語(yǔ)句缺失。請(qǐng)閱讀此算法并把缺失的語(yǔ)句補(bǔ)上。(每空3分)VoidCreateBinTree(BinTreeNode*&BT,charls){Stack<BinTreeNode*>s；MakeEmpty(s)；BT=NULL；//置二叉樹(shù)BinTreeNode*p；intk；istreamins(ls)；//把串ls定義為輸入字符串流對(duì)象inscharch；ins>>ch；//從ins順序讀入一個(gè)字符while(ch!=”#”){//逐個(gè)字符處理，直到遇到’#’為止switch(ch){case’(’：(1)k=1；break；case’)’：pop(s)；break；case‘,’(2)break；default：p=newBinTreeNode；(3)p->leftChild=NULL；p->rightChfild=NULL；if(BT==NULL)(4)elseif(k==1)top(s)->leftChild=p；elsetop(8)->rightChild=p；}(5)}}|七、下面是一個(gè)用C編寫(xiě)的快速排序算法。為了避免最壞情況，取基準(zhǔn)記錄pivot采用從left，right和mid=(1eft+right)/2中取中間值，并交換到right位置的辦法。數(shù)組a存放待排序的一組記錄，數(shù)據(jù)類(lèi)型為T(mén)ype，left和right是待排序子區(qū)間的最左端點(diǎn)和最右端點(diǎn)。Voidquicksort(Typea&#,intlefl，intright){Typetemp；if(left<right){Typepivot=medlian3(a,left，right)；inti=left，j=right-1;for(；；){while(i<j&&s[I]<pivot)i++；while(i<j&&pivot<a[j]j--；if(i<j){temp=a[i]；a[j]=a[i]；a[i]=temp；i++；j--；}elsebreak；}if(s[i]>pivot){temp=a[i]；a[i]=a[right]；a[right]=temp；}quicksort(a,left，i-1)；//遞歸排序左子區(qū)間quicksort(a，i+1，right)；//遞歸排序右子區(qū)間}}(1)用C或Pascal實(shí)現(xiàn)三者取中子程序median3(a,left,right)；(5分)(2)改寫(xiě)quicksoft算法，不用棧消去第二個(gè)遞歸調(diào)用quicksort(a，j+1，right)；(5分)(3)繼續(xù)改寫(xiě)quicksort算法，用棧消去剩下的遞歸調(diào)用。(5分)上海交通大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計(jì)試題注意：程序設(shè)計(jì)請(qǐng)采用C語(yǔ)言，程序應(yīng)有注解及說(shuō)明?；卮饐?wèn)題簡(jiǎn)潔、清晰全面。不得采用類(lèi)C之類(lèi)的語(yǔ)言寫(xiě)程序。一、參見(jiàn)下圖，該有向圖是AOE網(wǎng)絡(luò)。該圖上已標(biāo)出了源點(diǎn)及匯點(diǎn)，并給出了活動(dòng)(邊)的權(quán)值。請(qǐng)求出該AOE網(wǎng)絡(luò)的關(guān)鍵路徑，以及事件(結(jié)點(diǎn))的最早發(fā)生時(shí)間及最遲發(fā)生時(shí)間。(本題8分)二、已知某二叉樹(shù)的每個(gè)結(jié)點(diǎn)，要么其左、右子樹(shù)皆為空，要么其左、右子樹(shù)皆不空。又知該二叉樹(shù)的前序序列為(即先根次序)：J、F、D、B、A、C、E、H、X、I、K；后序序列為(即后根次序)：A、C、B、E、D、X、I、H、F、K、Jo請(qǐng)給出該二叉樹(shù)的中序序列(即中根次序)，并畫(huà)出相應(yīng)的二叉樹(shù)樹(shù)形。(本題8分)三、回答下列問(wèn)題：(本題10分)1)具有N個(gè)結(jié)點(diǎn)且互不相似的二叉樹(shù)的總數(shù)是多少?2)具有N個(gè)結(jié)點(diǎn)且不同形態(tài)的樹(shù)的總數(shù)是多少?3)對(duì)二叉樹(shù)而言，如果它的葉子結(jié)點(diǎn)總數(shù)為N0，度為2的結(jié)點(diǎn)的總為N2，則N0和N2之間的關(guān)系如何?4)二叉樹(shù)是否是結(jié)點(diǎn)的度最多為2的樹(shù)?請(qǐng)說(shuō)明理由。5)具有n片葉子的哈夫曼樹(shù)(即赫夫曼樹(shù))中，結(jié)點(diǎn)總數(shù)為多少？四、在外部分類(lèi)時(shí)，為了減少讀、寫(xiě)的次數(shù)，可以采用k路平衡歸并的最佳歸并樹(shù)模式。當(dāng)初始?xì)w并段的總數(shù)不足時(shí)，可以增加長(zhǎng)度為零的“虛段”。請(qǐng)問(wèn)增加的“虛段”的數(shù)目為多少?請(qǐng)推導(dǎo)之。設(shè)初始?xì)w并段的總數(shù)為m。(本題8分)五、對(duì)平衡的排序二叉樹(shù)進(jìn)行刪除結(jié)點(diǎn)的操作，必須保證刪除之后平衡樹(shù)中的每個(gè)結(jié)點(diǎn)的平衡因子是+1，-1，0三種情況之一，且該樹(shù)仍然是排序二叉樹(shù)?，F(xiàn)假定刪除操作是在p結(jié)點(diǎn)的左子樹(shù)上進(jìn)行的，且該左子樹(shù)原高為h-l，現(xiàn)變?yōu)閔-2。因此，必須從p的左子樹(shù)沿著到根的方向回溯調(diào)整結(jié)點(diǎn)的平衡因子，并進(jìn)行樹(shù)形的調(diào)整。設(shè)p是調(diào)整時(shí)遇到的第一個(gè)平衡因子力圖由-1變成-2的最年輕的“前輩”結(jié)點(diǎn)。我們知道，以p為根的子樹(shù)經(jīng)調(diào)整后，高度有可能減少1。試用圖形把調(diào)整前及調(diào)整后的相關(guān)結(jié)點(diǎn)的平衡因子、樹(shù)形表示出來(lái)；僅僅針對(duì)調(diào)整后子樹(shù)的高度減少1的情況即可。注意，羅列出所有可能的情況。上圖可供參考。(本題10分)1如果1如果n=15T(n/3)+n如果n>1Tn=Tn=七、如右圖所示，該二叉樹(shù)是某棵有序樹(shù)變換成的相對(duì)應(yīng)的二叉樹(shù)。試給出原來(lái)的有序樹(shù)的形狀。并回答以下問(wèn)題：1)原有序樹(shù)是度為多少的樹(shù)?2)原有序樹(shù)的葉子結(jié)點(diǎn)有哪幾個(gè)?3)是否所有的二叉樹(shù)都可以找到相對(duì)應(yīng)的有序樹(shù)?必須滿(mǎn)足什么條件?(本題5分)八、在排序二叉樹(shù)上進(jìn)行查找操作時(shí)，設(shè)對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)查找概率相同。設(shè)由n個(gè)結(jié)點(diǎn)構(gòu)成的序列生成的排序二叉樹(shù)是“隨機(jī)”的。試求出在成功查找的情況下，平均查找長(zhǎng)度是多少?為了簡(jiǎn)單起見(jiàn)，最后得到的遞推式可不予求解。(本題8分)九、設(shè)從鍵盤(pán)每次輸入兩個(gè)字符。如A、B，則表示存在著一條由數(shù)據(jù)場(chǎng)之值為字符A的結(jié)點(diǎn)到數(shù)據(jù)場(chǎng)之值為字符B的結(jié)點(diǎn)的有向邊。依此輸入這些有向邊，直至出現(xiàn)字符!為止。試設(shè)計(jì)一個(gè)程序，生成該有向圖的鄰接表及逆鄰接表。必須交待所用的結(jié)構(gòu)、變量、加以適當(dāng)注解。(本題20分)·十、設(shè)二叉樹(shù)中結(jié)點(diǎn)的數(shù)據(jù)場(chǎng)之值為一字符。采用二叉鏈表的方式存儲(chǔ)該二叉樹(shù)中的所有結(jié)點(diǎn)，設(shè)p為指向樹(shù)根結(jié)點(diǎn)的指針。設(shè)計(jì)一個(gè)程序在該二叉樹(shù)中尋找數(shù)據(jù)場(chǎng)之值為key(key為一變量，變量?jī)?nèi)容為一字符)的那個(gè)結(jié)點(diǎn)的所有祖先。設(shè)二叉樹(shù)中結(jié)點(diǎn)數(shù)據(jù)場(chǎng)之值互不重復(fù)。(本題15分)注意：有些書(shū)上將二叉樹(shù)的二叉鏈表存儲(chǔ)形式稱(chēng)之為標(biāo)準(zhǔn)存儲(chǔ)形式。南開(kāi)大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)試題一、選擇題(每小題3分，共21分)在下列各題中，每題之后均有若干個(gè)備選答案，請(qǐng)選出所有正確的答案，填人“”處。答案請(qǐng)寫(xiě)在答題紙上。1．任何一個(gè)無(wú)向連通圖的最小生成樹(shù)。①只有一棵②有一棵或多棵③一定有多棵④可能不存在2．已知一棵非空二叉樹(shù)的，則能夠惟一確定這棵二叉樹(shù)。①先序遍歷序列和后序遍歷序列②先序遍歷序列和中序遍歷序列③先序遍歷序列④中序遍歷序列，3．使用指針實(shí)現(xiàn)二叉樹(shù)時(shí)，如果結(jié)點(diǎn)的個(gè)數(shù)為n，則非空的指針域個(gè)數(shù)為。①n-1②2n-1③n+1④2n+14．設(shè)隊(duì)列存儲(chǔ)于一個(gè)一維數(shù)組中，數(shù)組下標(biāo)范圍是1-n，頭尾指針?lè)謩e為f和r，f指向第一個(gè)元素的前一個(gè)位置，r指向隊(duì)列中的最后一個(gè)元素，則隊(duì)列中元素個(gè)數(shù)為。①r-f②r-f+1③(r-f+1)modn④(r-f+n)modn5．任意一個(gè)AOE網(wǎng)絡(luò)的關(guān)鍵路徑。①一定有多條②只有一條③可能不只一條④可能不存在．6．下列排序算法中，在每一趟都能選出一個(gè)元素放到其最終位置上的是。①插入排序②希爾排序③快速排序④堆排序7．任意一個(gè)有向圖的拓?fù)渑判蛐蛄小＂僖欢ㄓ卸喾N②只有一種③可能不存在④以上都不對(duì)二、(7分)已知散列表地址空間為0-8，哈希函數(shù)為H(k)=kmod7，采用線(xiàn)性探測(cè)再散列法解決沖突。將下面關(guān)鍵字?jǐn)?shù)據(jù)依次填入該散列表中，同時(shí)將查找每個(gè)關(guān)鍵字所需的比較次數(shù)m填入下表中，并求等概率下的平均查找長(zhǎng)度。關(guān)鍵字值：100，20，21，35，3，78，99，45A012345678A1002021353789945mm三、(12分)回答下列問(wèn)題：(1)(3分)什么叫基數(shù)排序?(2)(3分)什么是AVL樹(shù)中的平衡因子，它有什么特點(diǎn)?(3)(6分)n個(gè)元素的序列{k1,k2,…kn}滿(mǎn)足什么條件才能稱(chēng)之為堆?簡(jiǎn)述對(duì)它進(jìn)行堆排序的過(guò)程。四、(10分)順序給出以下關(guān)鍵字：63、23、31、26、7、91、53、15、72、52、49、68，構(gòu)造3階B-樹(shù)。要求從空樹(shù)開(kāi)始，每插入一個(gè)關(guān)鍵字，畫(huà)出一個(gè)樹(shù)形。五、(6分)設(shè)有向無(wú)環(huán)圖G如下圖所示：試寫(xiě)出圖G的六種不同的拓?fù)渑判蛐蛄?。六?10分)設(shè)二叉樹(shù)以二叉鏈表表示，各結(jié)點(diǎn)的結(jié)構(gòu)如下所示：leftdatasubsumright其中l(wèi)eft、right分別為指向該結(jié)點(diǎn)左、右孩子的指針，data為存儲(chǔ)關(guān)鍵字值的整數(shù)域，subsum中存儲(chǔ)以該結(jié)點(diǎn)為根的子樹(shù)中所有關(guān)鍵字值之和。試使用C或C++語(yǔ)言設(shè)計(jì)算法，計(jì)算所給樹(shù)T中所有結(jié)點(diǎn)的subsum值。七、(12分)給出一個(gè)帶表頭的單鏈表L，L的每個(gè)結(jié)點(diǎn)中存放一個(gè)整數(shù)?，F(xiàn)給定一個(gè)閾值K，將L分成兩個(gè)子表L1和L2，其中L1中存放L中所有關(guān)鍵字值大于等于是的結(jié)點(diǎn)，L2中存放L中所有關(guān)鍵字值小于K的結(jié)點(diǎn)。試編程實(shí)現(xiàn)這個(gè)過(guò)程。要求，使用C或C++語(yǔ)言實(shí)現(xiàn)算法，L1和L2仍占用L的存儲(chǔ)空間。八、(10分)設(shè)有一維整數(shù)數(shù)組A，試使用C或C++語(yǔ)言設(shè)計(jì)算法，將A中所有的奇數(shù)排在所有偶數(shù)之前。要求，時(shí)間復(fù)雜度盡可能地少，結(jié)果仍放在A(yíng)原來(lái)的存儲(chǔ)空間。九、(12分)簡(jiǎn)述哈夫曼編碼的構(gòu)造過(guò)程。華東理工大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)試題一、單選題(10分)1．若某線(xiàn)性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用——存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表2．若在線(xiàn)性表中采用折半查找法查找元素，該線(xiàn)性表應(yīng)該。A．元素按值有序B．采用順序存儲(chǔ)結(jié)構(gòu)C．元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)D．元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3．對(duì)于給定的結(jié)點(diǎn)序列abcdef，規(guī)定進(jìn)棧只能從序列的左端開(kāi)始。通過(guò)棧的操作，能得到的序列為。A．a(chǎn)bcfedB．cabfedC．a(chǎn)bcfdeD．cbafde4．已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為。A．-A+B*C/DEB．-A+B*CD/EC．-+*ABC/DED．-+A*BC/DE5．如果n1和n2是二叉樹(shù)T中兩個(gè)不同結(jié)點(diǎn)，n2為n1的后代，那么按遍歷二叉樹(shù)T時(shí)，結(jié)點(diǎn)n2一定比結(jié)點(diǎn)n1先被訪(fǎng)問(wèn)。A．前序B．中序C．后序D．層次序6．具有65個(gè)結(jié)點(diǎn)的完全二叉樹(shù)其深度為。(根的層次號(hào)為1)A．8B．7C．6D．57．已知二叉樹(shù)的前序遍歷序列是abdgcefh，中序遍歷序列是dgbaechf，它的后序遍歷序列是。A．bdgcefhaB.gdbecfhaC．bdgechfaD．gdbehfca8．對(duì)于前序遍歷和后序遍歷結(jié)果相同的二叉樹(shù)為。A．一般二叉樹(shù)B．只有根結(jié)點(diǎn)的二叉樹(shù)C．根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù)D．根結(jié)點(diǎn)無(wú)右孩子的二叉樹(shù)9．對(duì)于前序遍歷與中序遍歷結(jié)果相同的二叉樹(shù)為。A．根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù)B．根結(jié)點(diǎn)無(wú)右孩子的二叉樹(shù)C．所有結(jié)點(diǎn)只有左子樹(shù)的二叉樹(shù)D．所有結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)10．在有n個(gè)葉子的哈夫曼樹(shù)中，其結(jié)點(diǎn)總數(shù)為。A．不確定B．2nC．2n+1D．2n-1二、是非題(10分)1．順序存儲(chǔ)方式只能用于存儲(chǔ)線(xiàn)性結(jié)構(gòu)。2．消除遞歸不一定需要使用棧。3．將一棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)后，根結(jié)點(diǎn)沒(méi)有右子樹(shù)。4．完全二叉樹(shù)可以采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，存儲(chǔ)非完全二叉樹(shù)則不能。5．在前序遍歷二叉樹(shù)的序列中，任何結(jié)點(diǎn)的子樹(shù)的所有結(jié)點(diǎn)都是直接跟在該結(jié)點(diǎn)之后。6．鄰接表法只能用于有向圖的存儲(chǔ)，而鄰接矩陣法對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用。7．在一個(gè)有向圖的鄰接表中，如果某個(gè)頂點(diǎn)的鏈表為空，則該頂點(diǎn)的度一定為零。8．二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值。9．最佳二叉排序樹(shù)的任何子樹(shù)都是最佳二叉排序樹(shù)。10．對(duì)兩棵具有相同關(guān)鍵字集合的而形狀不同的二叉排序樹(shù)，按中序遍歷它們得到的序列的順序是一樣的。三、問(wèn)答題(應(yīng)屆生限做2，3，4，5題；在職生任選做四題；共40分)1．(10分)什么是廣義表?請(qǐng)簡(jiǎn)述廣義表與線(xiàn)性表的主要區(qū)別。2．(10分)下圖表示一個(gè)地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線(xiàn)路，邊上的權(quán)表示架設(shè)線(xiàn)路花費(fèi)的代價(jià)。①請(qǐng)分別給出該圖的鄰接表和鄰接矩陣，要求每種存儲(chǔ)結(jié)構(gòu)能夠表達(dá)出該圖的全部信息，并分別對(duì)這二種形式中每個(gè)部分的含義(物理意義)予以簡(jiǎn)要說(shuō)明。②若假設(shè)每個(gè)域(包括指針域)的長(zhǎng)度為一個(gè)字節(jié)，請(qǐng)分別計(jì)算出這二種結(jié)構(gòu)所占用的空間大小。3．(10分)已知如下所示長(zhǎng)度為12的表：(Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec)①試按表中元素的順序依次插入一棵初始為空的二叉排序樹(shù)，請(qǐng)畫(huà)出插入完成之后的二叉排序樹(shù)，并求其在等概率的情況下查找成功的平均查找長(zhǎng)度。②若對(duì)表中元素先進(jìn)行排序構(gòu)成有序表，求在等概率的情況下對(duì)此有序表進(jìn)行折半查找時(shí)查找成功的平均查找長(zhǎng)度。③按表中元素順序構(gòu)造一棵平衡二叉排序樹(shù)，并求其在等概率的情況下查找成功的平均查找長(zhǎng)度。4．(10分)在起泡排序過(guò)程中，有的關(guān)鍵字在某趟排序中可能朝著與最終排序相反的方向移動(dòng)，試舉例說(shuō)明之。快速排序過(guò)程中有沒(méi)有這種現(xiàn)象?5．(10分)調(diào)用下列函數(shù)f(n)，回答下列問(wèn)題：①試指出f(n)值的大小，并寫(xiě)出f(n)值的推導(dǎo)過(guò)程；②假定n=5，試指出f(5)值的大小和執(zhí)行f(5)的輸出結(jié)果。C函數(shù)intf(intn){inti，j，k，sum=0；for(j=1；i<n+1i++){for(j=n；j>i-1；j--)for(k=1；k<j+1；k++)suni++；prinft(”sum=%d\n”，sum)；}return(sum)；}Pascal函數(shù)FUNCTIONf(n：integer)：integer；VARi，j，k，sum，integer；BEGIN．sum：=0；FORi：=1TOnDOBEGINFORj：=nDOWNiDOFORk：=1TOjDOsum：=sum+1writeln(’sum=’，sum)END；f：=sumEND；四、編寫(xiě)算法(應(yīng)屆生限做1、2、3、4題，在職生任選四題，每題10分，共40分)1．(10分)利用兩個(gè)棧S1和S2模擬一個(gè)隊(duì)列，寫(xiě)出入隊(duì)和出隊(duì)的算法(可用棧的基本操作)。棧的操作有：makeEmpty(s：stack)；置空棧push(s：stack；value：datatype)；新元素value進(jìn)棧pop(s：stack)：datatype；出棧，返回棧頂值isEmpty(s：stack)：boolean；判?？辗耜?duì)列的操作有enQtleue(s1：stack；s2：stack；value：datatype)；元素value進(jìn)隊(duì)deQueue(s1：stack；s2：stack)：datatype；出隊(duì)列，返回隊(duì)頭值2．(10分)試寫(xiě)出給定的二叉樹(shù)進(jìn)行層次遍歷的算法，在遍歷時(shí)使用一個(gè)鏈接隊(duì)列。3．(10分)試寫(xiě)一個(gè)算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑(i<>j)。假設(shè)分別基于下述策略：1)圖的深度優(yōu)先搜索；2)圖的廣度優(yōu)先搜索；4．(10分)設(shè)二叉排序樹(shù)中關(guān)鍵字由1至1000的整數(shù)構(gòu)成，現(xiàn)要檢索關(guān)鍵字為531的結(jié)點(diǎn)，下述關(guān)鍵字序列中哪些可能是二叉排序樹(shù)上搜索到的序列，哪些不可能是二叉排序樹(shù)上搜索到的序列，哪些不可能是二叉排序樹(shù)上搜索到的序列？a)800，399，588，570，500，520，566，531b)730，355，780，390，701，401，530，531c)732，321，712，385，713，392，531d)8，578，555，340，433，551，550，450，531通過(guò)對(duì)上述序列的分析，試寫(xiě)一個(gè)算法判定給定的關(guān)鍵字序列(假定關(guān)鍵字互不相同)是否可能是二叉排序樹(shù)的搜索序列。若可能則返回真，否則返回假?？杉俣ū慌卸ǖ男蛄幸汛嫒霐?shù)組中。5．(10分)編寫(xiě)一個(gè)在非空的帶表頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)就地排序的程序。(不額外申請(qǐng)新的鏈表空間)華中理工大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)試題說(shuō)明：在有數(shù)據(jù)類(lèi)型定義和算法設(shè)計(jì)的各題中，任取C語(yǔ)言、PASCAL語(yǔ)言之一作答，但不許使用所謂“類(lèi)C”或“類(lèi)PASCAL”。一、選擇題(從下列各題四個(gè)備選答案中選出一至四個(gè)正確答案，將其代號(hào)(A，B，C，D)寫(xiě)在題干前面的括號(hào)內(nèi)。答案選錯(cuò)或未選全者，該題不得分。每小題1分，共計(jì)20分)()1．一個(gè)算法具有等特點(diǎn)。A．可行性B．至少有一個(gè)輸入量C．確定性D．健壯性()2.是一個(gè)線(xiàn)性表。A．(A，B，C，D)B．{’A’，’B’，’C’，’D’}C．(1，2，3，…)D．(40，-22，88)()3．可使用作壓縮稀疏矩陣的存儲(chǔ)結(jié)構(gòu)。A．鄰接矩陣B．三元組表C．鄰接表D．十字鏈表()4．采用一維數(shù)組表示順序存儲(chǔ)結(jié)構(gòu)時(shí)，可用它來(lái)表示。A．字符串B．2度樹(shù)C．二叉樹(shù)D．無(wú)向圖()5．假設(shè)進(jìn)入棧的元素序列為d，c，a，b，e，那么可得到出棧的元素序列。A．a(chǎn)，b，c，d，eB．a(chǎn)，b，e，d，cC．d，b，a，e，cD．d，b，a，c，e()6．對(duì)隊(duì)列的操作有。A．在隊(duì)首插入元素B．刪除值最小的元素C．按元素的大小排序D．判斷是否還有元素()7．假設(shè)有60行70列的二維數(shù)組a[1．．60，1．．70]，以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a[32，58]的存儲(chǔ)地址為。(無(wú)第0行第0列元素)A．16902B．16904C．14454D．答案A，B，C均不對(duì)()8.是C語(yǔ)言中"abcd321ABCD"的子串。A．a(chǎn)bedB．32lABC．”abeABC”D．”2lAB”()9．在下列各廣義表中，長(zhǎng)度為3的廣義表有。A．(a，b，c，())B．((g)，(a，b，c，d，f)，())C．(a，(b，(c)))D．((()))()10．一個(gè)堆(heap)又是一棵。A．二叉排序樹(shù)B．完全二叉樹(shù)C．平衡二叉樹(shù)D．哈夫曼(Huffman)樹(shù)()11．折半查找有序表(4，6，10，20，30，50，70，88，100)，若查找元素58，則它將依次與表中元素比較大小，查找結(jié)果是失敗。A．20，70，30，50B．30，88，70C．20，50D．30，88，50，70()12．對(duì)27個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較次關(guān)鍵字。A．3B．4C．5D．6()13．具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有。A．5個(gè)葉子B．5個(gè)度為2的結(jié)點(diǎn)C．7個(gè)分支結(jié)點(diǎn)D．2個(gè)度為1的結(jié)點(diǎn)()14．具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為。A．log2(n)B．log2(n+1)C．log2(n)+1D．loge(n)+1()15．用5個(gè)權(quán)值{3，2，4，5，1}構(gòu)造的哈夫曼(Huffman)樹(shù)的帶權(quán)路徑長(zhǎng)度是。A．32B．33C．34D．15()16．對(duì)14個(gè)記錄的表進(jìn)行2路歸并排序，共需移動(dòng)次記錄。A．42B．56C．91D．84()17．對(duì)有n個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是。A．O(n)B．O(n2)C．O(nlog2n)D．O(2n)()18．在最好情況下，下列算法中排序算法所需比較關(guān)鍵字次數(shù)最少。A．冒泡B．歸并C．快速D．直接插入()19．置換選擇排序的功能是。A．選出最大的元素B．產(chǎn)生初始?xì)w并段C．產(chǎn)生有序文件D．置換某個(gè)記錄()20．可在構(gòu)造一個(gè)散列文件。A．內(nèi)存B．軟盤(pán)C．磁帶D．硬盤(pán)二、試用2種不同表示法畫(huà)出下列二叉樹(shù)B1的存儲(chǔ)結(jié)構(gòu)，并評(píng)述這2種表示法的優(yōu)、缺點(diǎn)。(共10分)二題圖B1三題圖G三、對(duì)圖G：從頂點(diǎn)A出發(fā)，求圖G的一棵深度優(yōu)先生成樹(shù)；從頂點(diǎn)B出發(fā)，求圖G的一棵廣度優(yōu)先生成樹(shù)；3．求圖G的一棵最小生成樹(shù)。(共12分)四、設(shè)哈希(Hash)函數(shù)為：H(k)=kMODl4，其中k為關(guān)鍵字(整數(shù))，MOD為取模運(yùn)算，用線(xiàn)性探測(cè)再散列法處理沖突，在地址范圍為0~14散列區(qū)中，試用關(guān)鍵字序列(19，27，26，28，29，40，64，21，15，12)造一個(gè)哈希表，回答下列問(wèn)題：1．畫(huà)出該哈希表的存儲(chǔ)結(jié)構(gòu)圖；2．若查找關(guān)鍵字40，必須依次與表中哪些關(guān)鍵字比較大小？3．假定每個(gè)關(guān)鍵字的查找概率相同，試求查找成功時(shí)的平均查找長(zhǎng)度。(共13分)五、給定頭指針為ha的單鏈表A，和頭指針為hb的遞增有序單鏈表B。試?yán)帽鞟和表B的結(jié)點(diǎn)，將表A和表B歸并為遞增有序表C，其頭指針為hc，允許有相同data值(數(shù)據(jù)元素)的結(jié)點(diǎn)存在，表A，B，C均帶表頭結(jié)點(diǎn)。例如，給定：將它們歸并為：1．在下列C算法merge中有下劃線(xiàn)的位置填空，使之成為完整的算法，要求在填空后加注釋?zhuān)蕴岣咚惴ǖ目勺x性。2．假定單鏈表A和B的長(zhǎng)度分別為m和n(m>0，n>0)，試分別就最好情況、最壞情況和平均性能，分析算法merge的時(shí)間復(fù)雜度。(共15分)結(jié)點(diǎn)類(lèi)型定義如下：structnode、{intdata；structnode*next；}；算法如下：Voidmerge(structnode*ha，structnode*hb，structnode*hc){structnode*pc，*qc，*pa，*fa；intsearch；hc=hb；hb=NULL；pa=ha->next；free(ha)；while(pa){pc=hc；qc=hc->next；search=；while(qc&&search){if(pa->data<=qc->data)；else{pc=qc；qc=；}}fa=；pa=；fa->next=；；}}六、設(shè)下圖二叉樹(shù)B2的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，root為根指針，結(jié)點(diǎn)結(jié)構(gòu)為：(1child，data，rchild)其中：lchild，rchild分別為指向左右孩子的指針，data為字符型。(共10分)對(duì)下列二叉樹(shù)B2，執(zhí)行下列算法traversel(root)，試指出其輸出結(jié)果；2．假定二叉樹(shù)B2共有n個(gè)結(jié)點(diǎn)，試分析算法traversal的時(shí)間復(fù)雜度。結(jié)點(diǎn)類(lèi)型定義如下：structnode{chardata；structnode*lchild，*rchild；}；算法如下：voidtraversal(structnode*root){if(root){prinft(“%c”，root->data)；二叉樹(shù)B2traversal(root->lchild)；二叉樹(shù)B2prinft(”%c”，root->data)；traversal(root->rchild)；}}七、算法設(shè)計(jì)題(要求：(1)寫(xiě)出所用數(shù)據(jù)結(jié)構(gòu)的類(lèi)型定義和變量說(shuō)明；(2)寫(xiě)出算法，并在相關(guān)位置加注釋?zhuān)蕴岣咚惴ǖ目勺x性。)1．試設(shè)計(jì)一算法：輸入一個(gè)有m行n列的整數(shù)矩陣，然后將每一行的元素按非減次序輸出。例如，若輸入：4，3，5，6，29，8，1，2，87，1，2，3，8則輸出如下結(jié)果：2，3，4，5，61，2，8，8，91，2，3，7，82．如果字符串的一個(gè)子串(其長(zhǎng)度大于1)的各個(gè)字符均相同，則稱(chēng)之為等值子串。試設(shè)計(jì)一算法：輸入字符串S，以’!’為結(jié)束標(biāo)志，如果串S中不存在等值子串，則輸出信息：”無(wú)等值子串”，否則求出(輸出)一個(gè)長(zhǎng)度最大的等值子串。例如，若S=”abcl23abcl23！”，則輸出：”無(wú)等值子串”；又如，若S=”abcaabcccdddddaaadd!”，則輸出等值子串：”ddddd”。(共20分)北京理工大學(xué)2001年程序設(shè)計(jì)(含數(shù)據(jù)結(jié)構(gòu))試題第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)(共50分)一、選擇題(12分，每題2分)1．下列數(shù)據(jù)中哪些是非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。A．棧B．隊(duì)列C．完全二叉樹(shù)D．堆2．靜態(tài)鏈表中指針表示的是。A．內(nèi)存地址B．?dāng)?shù)組下標(biāo)C．下一元素地址D．左、右孩子地址3．用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)。A．僅修改隊(duì)頭指針B．僅修改隊(duì)尾指針C．隊(duì)頭，隊(duì)尾指針都要修改D．隊(duì)頭，隊(duì)尾指針都可能要修改4．在下列排序算法中，哪一個(gè)算法的時(shí)間復(fù)雜度與初始排列無(wú)關(guān)。A．直接插入排序B．起泡排序C．快速排序D．直接選擇排序5．二叉樹(shù)第i層結(jié)點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)最多是(設(shè)根的層數(shù)為1)。A．2i-1B．2i-1C．2iD．2i-16．樹(shù)的后根遍歷序列等同于該樹(shù)對(duì)應(yīng)的二叉樹(shù)的。A．先序序列B．中序序列C．后序序列二、填空(8分，每空1分)1．?dāng)?shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是——。2．順序存儲(chǔ)結(jié)構(gòu)是通過(guò)表示元素之間的關(guān)系的。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)表示元素之間的關(guān)系的。3．AOV網(wǎng)中，結(jié)點(diǎn)表示，邊表示。AOE網(wǎng)中，結(jié)點(diǎn)表示，邊表示。4．哈夫曼樹(shù)是。三、求解下列問(wèn)題(25分，每題5分)1．請(qǐng)用C語(yǔ)言給出線(xiàn)性鏈表的類(lèi)型定義。2．已知二叉樹(shù)的先序序列：CBHEGAF，中序序列：HBGEACF，試構(gòu)造該二叉樹(shù)。3．設(shè)散列表的地址空間為0到12的存儲(chǔ)單元，散列函數(shù)為：h(key)=keymod13，用鏈地址法解決沖突，初始時(shí)散列表為空。現(xiàn)依次將關(guān)鍵字25，33，48，25，43，38，39插入散列表，試畫(huà)出完成上述所有插入操作后散列表的狀態(tài)，并計(jì)算在等概率的情況下，在該表中查找成功的平均查找長(zhǎng)度。4．給出如下圖所示的圖形。1)試寫(xiě)出該圖的鄰接表；2)試寫(xiě)出該圖從結(jié)點(diǎn)0出發(fā)的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列，并畫(huà)出遍歷過(guò)程中所經(jīng)的路徑。5．全國(guó)統(tǒng)考答題對(duì)上圖，按迪杰斯特拉算法求出從結(jié)點(diǎn)0到其余各點(diǎn)的最短路徑，并給出在求解過(guò)程中數(shù)組distance的變化狀態(tài)。6．單獨(dú)考試答題(可在5或6中任選一題做)給出關(guān)鍵字序列27，18，21，77，26，45，66，34試寫(xiě)出快速排序的過(guò)程。四、算法題(12分)(請(qǐng)?jiān)谒惴ǖ闹饕襟E上加注釋)1．下面是用C語(yǔ)言編寫(xiě)的對(duì)不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行就地置逆的算法，該算法用L返回置逆后鏈表的頭指針。試在空缺處填入適當(dāng)?shù)恼Z(yǔ)句。voidreverse(1inklist&L){p=NULL；q=L；while(q!=NULL){q->next=p；p=q；}}2．全國(guó)統(tǒng)考答題設(shè)二叉樹(shù)用二叉鏈表存儲(chǔ)，試編寫(xiě)按層輸出二叉樹(shù)結(jié)點(diǎn)的算法。3．單獨(dú)考試答題(可在2或3中任選一題做)試編寫(xiě)在帶頭結(jié)點(diǎn)的單鏈表中刪除(一個(gè))最小值結(jié)點(diǎn)的(高效)算法。voiddelete(Linklist&L)北京郵電大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)試題一、選擇題(10分，每題2分)1．B+樹(shù)是應(yīng)用在()文件系統(tǒng)中。①I(mǎi)SAM②VSAM2．將一棵樹(shù)t轉(zhuǎn)換為孩子-兄弟鏈表表示的二叉樹(shù)h，則t的后根遍歷是h的()。①前序遍歷②中序遍歷③后序遍歷3．一個(gè)有向無(wú)環(huán)圖的拓?fù)渑判蛐蛄?)是惟一的。①一定②不一定4．將10個(gè)元素散列到100000個(gè)單元的哈希表中，則()產(chǎn)生沖突。①一定會(huì)②一定不會(huì)③仍可能會(huì)5．若要求盡可能快地對(duì)序列進(jìn)行穩(wěn)定的排序，則應(yīng)選()。①快速排序②歸并排序③冒泡排序二、填空題(20分，每空2分)1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是指。2．區(qū)分循環(huán)隊(duì)列的滿(mǎn)與空，只有兩類(lèi)辦法，它們是和。3．用一維數(shù)組B以列優(yōu)先存放帶狀矩陣A中的非零元素A[i，j](1≤i≤n，i-2≤j≤i+2)，B中的第8個(gè)元素是A中第行、第列的元素。4．字符串’ababaaab’的nextval函數(shù)值為——。5．下圖中的強(qiáng)連通分量的個(gè)數(shù)為個(gè)。6．外部排序的基本方法是歸并排序，但在之前必須先生成。7．若不考慮基數(shù)排序，則在排序過(guò)程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的和記錄的三、簡(jiǎn)答題(15分，每題5分)1．特殊矩陣和稀疏矩陣哪種壓縮存儲(chǔ)后會(huì)失去隨機(jī)存取的功能?為什么?2．試問(wèn)線(xiàn)索二叉樹(shù)的目的何在?3．在多關(guān)鍵字排序時(shí)，LSD和MSD兩種方法的特點(diǎn)是什么?四、應(yīng)用題(25分，每題5分)1．畫(huà)出按下表中元素的順序構(gòu)造的平衡二叉排序樹(shù)，并求其在等概率的情況下查找成功的平均查找長(zhǎng)度。{15，12，24，3，27，21，18，6，36，33，30，26，3}2．假設(shè)用于通信的電文由字符集{a，b，c，d，e，f，g}中的字母構(gòu)成，它們?cè)陔娢闹谐霈F(xiàn)的頻率分別為{0.31，0.16，0.10，0.08，0.11，0.20，0.04}。(1)為這7個(gè)字母設(shè)計(jì)哈夫曼編碼；(2)對(duì)這7個(gè)字母進(jìn)行等長(zhǎng)編碼，至少需要幾位二進(jìn)制數(shù)?哈夫曼編碼比等長(zhǎng)編碼使電文總長(zhǎng)壓縮多少?3．試推導(dǎo)當(dāng)總盤(pán)數(shù)為n時(shí)的Hanoi塔的移動(dòng)次數(shù)。4．一棵滿(mǎn)k叉樹(shù)，按層次遍歷存儲(chǔ)在一維數(shù)組中，試計(jì)算結(jié)點(diǎn)下標(biāo)為u的結(jié)點(diǎn)的第i個(gè)孩子的下標(biāo)以及結(jié)點(diǎn)下標(biāo)為v的結(jié)點(diǎn)的父母結(jié)點(diǎn)的下標(biāo)。5．有一圖的鄰接矩陣如下，試給出用弗洛伊德算法求各點(diǎn)間最短距離的矩陣序列A(1)、A(2)、A(3)和A(4)。A=A=02∞∞∞0165∞043∞∞0五、算法(30分，每題10分)1．在單鏈表中，每個(gè)結(jié)點(diǎn)含有5個(gè)正整型的數(shù)據(jù)元素(若最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素不滿(mǎn)5個(gè)，以值0填充)，試編寫(xiě)一算法查找值為n(n>0)的數(shù)據(jù)元素所在的結(jié)點(diǎn)指針以及在該結(jié)點(diǎn)中的序號(hào)，若鏈表中不存在該數(shù)據(jù)元素則返回空指針。2．將一組數(shù)據(jù)元素按哈希函數(shù)H(key)散列到哈希表m(0．．m)中，用線(xiàn)性探測(cè)法處理沖突(H(key)+1、H(key)+2、…、H(key)-1，假設(shè)空單元用EMPTY表示，刪除操作是將哈希表中結(jié)點(diǎn)標(biāo)志位從INUSE標(biāo)記為DELETED，試寫(xiě)出該散列表的查找、插入和刪除三個(gè)基本操作算法。3．給出算法將二叉鏈表表示的表達(dá)式二叉樹(shù)按中綴表達(dá)式輸出，并加上相應(yīng)的括號(hào)。北京航空航天大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)試題一、問(wèn)答題(本題10分)一般情況下，線(xiàn)性表可以采用哪幾種存儲(chǔ)結(jié)構(gòu)?請(qǐng)分別敘述每一種存儲(chǔ)結(jié)構(gòu)的構(gòu)造原理與特點(diǎn)。二、(本題10分)已知AOE網(wǎng)為G=(V，E)，V={v1，v2，v3，v4，v5，v6，v7，v8，V9，vl0}，E={a1，a2，a3，a4，a5，a6，a7，a8，a9，al0，a11，a12，a13，a14}，其中：a1：(v1，v2)5a2：(v1，v3)6a3：(v2，v5)3a4：(v3，V4)3a5：(v3，v5)6a6：(v4，v5)3a7：(v4，v7)1a8：(v4，v8)4a9：(v5，v6)4al0：(v5，v7)1a11：(v6，vl0)4a12：(v7，v9)5a13：(v8，v9)2a14：(v9，v10)2注：頂點(diǎn)偶對(duì)右下角的數(shù)字表示邊上的權(quán)值。請(qǐng)按下述過(guò)程指出所有關(guān)鍵路徑：ee[1:10]:le[1:10]:e[1:14]:l[1:14]:其中，ee[i]與le[i]分別表示事件vi的最早發(fā)生時(shí)間與最晚發(fā)生時(shí)間；e[i]與l[i]分別表示活動(dòng)ai的最早開(kāi)始時(shí)間與最晚開(kāi)始時(shí)間。三、(本題共30分，每小題10分)欲建立一文獻(xiàn)庫(kù)，其正文(文獻(xiàn)本身)存放在一個(gè)雙向循環(huán)鏈表的各個(gè)鏈結(jié)點(diǎn)中。1．為便于鏈結(jié)點(diǎn)的插入、刪除操作，以及按題目、發(fā)表日期、發(fā)表者名稱(chēng)、主題詞(假設(shè)每文最多給出三個(gè)主題詞)進(jìn)行檢索，請(qǐng)?jiān)O(shè)計(jì)該鏈表的鏈結(jié)點(diǎn)結(jié)構(gòu)(給出鏈結(jié)點(diǎn)每個(gè)域的名稱(chēng)，并說(shuō)明該域內(nèi)存放什么信息。注：以下各小題設(shè)計(jì)鏈結(jié)點(diǎn)結(jié)構(gòu)也這樣要求)。畫(huà)出整個(gè)鏈表結(jié)構(gòu)的示意圖。2．設(shè)計(jì)一個(gè)三級(jí)索引結(jié)構(gòu)，其中第三級(jí)索引稱(chēng)為題目索引，是按文獻(xiàn)題目構(gòu)造的稠密索引，通過(guò)該級(jí)索引并根據(jù)給定題目可得到每個(gè)文獻(xiàn)的存放地址；該級(jí)索引按文獻(xiàn)學(xué)科類(lèi)分類(lèi)存放。第二級(jí)索引稱(chēng)為中類(lèi)索引，是題目索引的索引，指出同一中類(lèi)的文獻(xiàn)題目索引的存放位置(例如農(nóng)林類(lèi)、氣象類(lèi)……，古代史類(lèi)、近代史類(lèi)……)。第一級(jí)索引稱(chēng)為大類(lèi)索引，指出同一大類(lèi)(如：自然科學(xué)類(lèi)、歷史類(lèi)……)的文獻(xiàn)的中類(lèi)索引的存放位置。請(qǐng)?jiān)O(shè)計(jì)每一級(jí)索引的結(jié)點(diǎn)結(jié)構(gòu)，并畫(huà)出該索引的整體示意圖。3．再設(shè)計(jì)一種三級(jí)索引結(jié)構(gòu)，其中第三級(jí)索引仍是題目索引(與2題所述相同)，第二級(jí)索引把具有相同主題詞的文獻(xiàn)題目索引地址組織在一個(gè)單鏈表中。第一級(jí)索引稱(chēng)為主題詞索引，用文獻(xiàn)給出的主題詞作關(guān)鍵字組成雜湊表，即該級(jí)索引為一個(gè)雜湊表，能夠指出具有同一主題詞的文獻(xiàn)題目索引的索引鏈表的第一個(gè)鏈結(jié)點(diǎn)的存儲(chǔ)位置。該雜湊表采用鏈地址法處理沖突。請(qǐng)?jiān)O(shè)計(jì)每一級(jí)索引的結(jié)點(diǎn)結(jié)構(gòu)，并畫(huà)出該索引的整體示意圖。四、(本題10分)已知非空線(xiàn)性鏈表由list指出，鏈結(jié)點(diǎn)的構(gòu)造為datalink請(qǐng)寫(xiě)一算法，將鏈表中數(shù)據(jù)域值最小的那個(gè)鏈結(jié)點(diǎn)移至鏈表的最前面。要求：不得額外申請(qǐng)新的鏈結(jié)點(diǎn)。五、(本題15分，第1小題5分，第2小題10分)已知求兩個(gè)正整數(shù)m與n的最大公因子的過(guò)程用自然語(yǔ)言可以表述為反復(fù)執(zhí)行如下動(dòng)作：第一步：若n等于零，則返回m；第二步：若m小于n，則m與n相互交換；否則，保存m，然后將n送m，將保存的m除以n的余數(shù)送n。1．將上述過(guò)程用遞歸函數(shù)表達(dá)出來(lái)(設(shè)求x除以y的余數(shù)可以用xMODy形式表示)。2．寫(xiě)出求解該遞歸函數(shù)的非遞歸算法。六、(本題10分)函數(shù)voidinsert(char*s，char*t，intpos)將字符串t插入到字符串s中，插入位置為pos。請(qǐng)用C語(yǔ)言實(shí)現(xiàn)該函數(shù)。假設(shè)分配給字符串s的空間足夠認(rèn)字符串t插入。(說(shuō)明：不得使用任何庫(kù)函數(shù)。)七、(本題15分)。命令sgrep用來(lái)在文件中查找給定字符串，并輸出串所在行及行號(hào)。命令格式為：sgrep[-i]filenamesearchstring其中：-i：表示查找的大小寫(xiě)無(wú)關(guān)，省略時(shí)表示大小寫(xiě)相關(guān)。filename：給定文件名。searchstring：所要查找的串。用C語(yǔ)言實(shí)現(xiàn)該程序，該程序應(yīng)具有一定的錯(cuò)誤處理能力。(提示：使用命令行參數(shù))注意：除文件及輸入/出操作可使用庫(kù)函數(shù)外，其他不允許使用庫(kù)函數(shù)。西安交通大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)試題一、判斷下列敘述是否正確，正確的填√，不正確的填×(10分)1．?dāng)?shù)據(jù)對(duì)象就是一組數(shù)據(jù)元素的集合。()2．任何一棵前序線(xiàn)索二叉樹(shù)，都可以不用棧實(shí)現(xiàn)前序遍歷。()3．就平均查找長(zhǎng)度而言，分塊查找最小，折半查找次之，順序查找最大。()4．用shell方法排序時(shí)，若關(guān)鍵字的排列雜亂無(wú)序，則效率最高。()5．在m階B-樹(shù)中，所有非終端結(jié)點(diǎn)至少包含m／2。()二、選擇填空題(15分)1．假設(shè)以數(shù)組A[m．．n]存放循環(huán)隊(duì)列的元素，其頭指針是front，當(dāng)前隊(duì)列有k個(gè)元素，則隊(duì)列的尾指針為()。A．(front+k)mod(n-m+1)B．(m+k)modn+frontC．(front-m+k)mod(n-m+1)+mD．(front-m+k)mod(n-m+1)已知二叉樹(shù)如右圖所示，此二叉樹(shù)的順序存儲(chǔ)的結(jié)點(diǎn)序列是()。A．123□45B．12345C．12□435D．□241533．若用冒泡排序?qū)﹃P(guān)鍵字序列{20，17，11，8，6，2}從小到大進(jìn)行排序，則需要交換的總次數(shù)為()。A．3B．6C．12D．154．對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是()。A．head=NULLB．head->next=NULLC．head->next==headD．head!=NULL5．已知串s=“ABCDEFGH'’，則s的所有不同子串的個(gè)數(shù)為()。A．8B．9C．36D．37三、填空題(15分)1．假設(shè)一個(gè)12階的上三角矩陣A按行優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，則非零元素a8，9，在B中的存儲(chǔ)位置k=。2．在拓?fù)渑判蛑校負(fù)湫蛄械牡谝粋€(gè)頂點(diǎn)必定是的頂點(diǎn)。3．由六個(gè)分別帶權(quán)值為5，12，9，30，7，16的葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼(Huffinan)樹(shù)，該樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為，樹(shù)的帶權(quán)路徑長(zhǎng)度為。4．在的情況下，鏈隊(duì)列的出隊(duì)操作需要修改尾指針。5．對(duì)表長(zhǎng)為n的順序表進(jìn)行分塊查找，若以順序查找確定塊，且每塊長(zhǎng)度為s，則在等概率查找的情況下，查找成功時(shí)的平均查找長(zhǎng)度為。四、簡(jiǎn)答題(50分)1．(6分)已知廣義表L：((a，b)，(c，(d，(e)))，f)。(1)試?yán)脧V義表取表頭head(L)和取表尾tail(L)的基本運(yùn)算，將原子c從下列廣義表中分解出來(lái)，請(qǐng)寫(xiě)出運(yùn)算表達(dá)式。(2)請(qǐng)給出下列表達(dá)式的運(yùn)算結(jié)果：①hem(tail(head(tail(L))))②tail(tail(head(L)))2．(10分)已知一個(gè)圖G=(V，E)，其中：V={a，b，c，d，e，f}；E={<a，b>，<a，d>，<a，e>，<d，e>，<e，b>，<c，b>，<c，e>，<c，f>，<f，e>}(1)請(qǐng)畫(huà)出該圖，并寫(xiě)出鄰接矩陣。(2)根據(jù)鄰接矩陣，分別同從頂點(diǎn)a出發(fā)的深度優(yōu)先和廣度優(yōu)先遍歷序列。(3)畫(huà)出由此得到的深度優(yōu)先和廣度優(yōu)先生成樹(shù)(或森林)。3．(6分)已知一個(gè)棧s的輸入序列為abcd，下面兩個(gè)序列能否通過(guò)棧的PUSH和POP操作輸出；如果能，請(qǐng)寫(xiě)出操作序列；如果不能，請(qǐng)說(shuō)明原因。①dbca②cbda4．(5分)設(shè)模式串t=”abaabacababa”，試求出t的next和nextval函數(shù)值。5．(7分)已知一組關(guān)鍵字K={20，15，4，18，9，6，25，12，3，22}，請(qǐng)判斷此序列是否為堆?如果不是，請(qǐng)調(diào)整為堆。6．(8分)對(duì)于表達(dá)式(a-b+c)*d/(e+f)(1)畫(huà)出它的中序二叉樹(shù)，并標(biāo)出該二叉樹(shù)的前序線(xiàn)索；(2)給出它的前綴表達(dá)式和后綴表達(dá)式。7．(8分)設(shè)散列長(zhǎng)度為9，散列函數(shù)為H(k)=kmod9，給出關(guān)鍵字序列：23，45，14，17，9，29，37，18，25，41，33，采用鏈地址法解決沖突。(1)請(qǐng)畫(huà)出散列表；(2)求出查找各關(guān)鍵字的比較次數(shù)；(3)計(jì)算在等概率情況下，查找成功的平均查找長(zhǎng)度。五、算法填空(10分)已知圖的鄰接表存儲(chǔ)結(jié)構(gòu)描述如下：CONSTN=圖的頂點(diǎn)數(shù)：TYPEarcprt=↑arcnode；arcnode=RECORDadjvex：integer；nextarc：acrptrEND；vexnode=RECORDvexdata：char；firstarc：arcptrEND；Graph=ARRAY[1．．N]ofvexnode；下面是一個(gè)圖的深度優(yōu)先遍歷的非遞歸算法，請(qǐng)?jiān)谔幪钌线m當(dāng)內(nèi)容，使其成為一個(gè)完整算法。PROCEDUREtraver_dfs(g：graph)；VARvisited：ARRAY[1．．N]ofBOOLEAN；s：STACK；{s為一個(gè)棧}p：arcptr：BEGINFORi：=1TONDOvisited[i]：=①I(mǎi)NISTACK(S)；FORi=1TONDOBEGIN②BEGINvisited[i]：=true；visit(i)；//訪(fǎng)問(wèn)第i個(gè)頂點(diǎn)IFg[i].firstarc≠NILTHENPUSH(d，g[i].firstarc)ENDWHILE③DOBECINp：POP(s)；IFp↑.nextarc≠NILTHENPUSH(s，p↑.nextarc)；j：=p↑.adjvex；IFNOTvisited[i]THENBEGINvisited[j]：=true；visit(j)；IFe[j].firstarc≠NILTHEN④ENDENDENDEND中國(guó)科學(xué)院軟件研究所2001年數(shù)據(jù)結(jié)構(gòu)試題一、單項(xiàng)選擇題(每空2分，共20分)1．下列函數(shù)中漸近時(shí)間復(fù)雜度最小的是()。A．T1(n)=nlog2n+5000nB．T2(n)=n2-8000nC．T3(n)=nlog221-6000nD．T4(n)=2nlog2n-7000n2．線(xiàn)性表的靜態(tài)鏈表存儲(chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比優(yōu)點(diǎn)是()。A．所有的操作算法實(shí)現(xiàn)簡(jiǎn)單B．便于隨機(jī)存取C．便于插入和刪除D．便于利用零散的存儲(chǔ)器空間3．設(shè)棧的輸入序列為1，2，…，n，輸出序列為a1，a2，…，an，若存在1≤k≤n使得ak=n，則當(dāng)k≤i≤n時(shí)，ai為()。A．n-i+lB．n-(i-k)C．不確定4．設(shè)高度為h的二叉樹(shù)(根的層數(shù)為1)上只有度為0和度為2的節(jié)點(diǎn)，則此類(lèi)二叉樹(shù)中所包含的節(jié)點(diǎn)數(shù)至少為()。A．2hB．2h-1C．2h+lD．h+l5．設(shè)指針p指向線(xiàn)索樹(shù)中的某個(gè)結(jié)點(diǎn)，則查找*p在某種次序下的前驅(qū)或后繼不能獲得加速的是()。A．前序線(xiàn)索樹(shù)中查找*p的前序后繼B．中序線(xiàn)索樹(shù)中查找*p的中序后繼C．中序線(xiàn)索樹(shù)中查找*p的中序前繼D．后序線(xiàn)索樹(shù)中查找*p的后序前繼6．假定有k個(gè)關(guān)鍵字互為同義詞，若用線(xiàn)性探測(cè)法將這k個(gè)關(guān)鍵字存入散列表中，至少需要進(jìn)行()次探測(cè)。A．k-1B．kC．k+lD．k(k+1)/27．若待排序元素基本有序，則下列排序中平均速度最快的排序是()；若要求輔助空間為O(1)，則平均速度最快的排序是()；若要求排序是穩(wěn)定的，且關(guān)鍵字為實(shí)數(shù)，則平均速度最快的排序是()。A．直接插入排序B．直接選擇排序C．Shell排序D．冒泡排序E．快速排序F．堆排序C．歸并排序H．基數(shù)排序8．對(duì)于多關(guān)鍵字而言，()是一種方便而又高效的文件組織文式。A．順序文件B．索引文件C．散列文件D．倒排文件二、問(wèn)答題(共25分)1．設(shè)A[-2：6；-3：6]是一個(gè)用行主序存儲(chǔ)的二維數(shù)組，已知A[-2，-3]的起始存儲(chǔ)位置為loc(-2，-3)=1000，每個(gè)數(shù)組元素占用4個(gè)存儲(chǔ)單元，求：(6分)1)A[4，5]的起始存儲(chǔ)位置loc(4，5)；2)起始存儲(chǔ)位置為1184的數(shù)組元素的下標(biāo)。2．給定二叉樹(shù)的先序和后序遍歷序列，能否重構(gòu)出該二叉樹(shù)?若能，試證明之，否則給出反例。(6分)3．在含有n個(gè)關(guān)鍵字的m階B-樹(shù)中進(jìn)行查找，至多讀盤(pán)多少次?完全平衡的二叉排序樹(shù)的讀盤(pán)次數(shù)大約比它大多少倍?(設(shè)兩種樹(shù)中的每個(gè)節(jié)點(diǎn)均是一個(gè)存儲(chǔ)塊)。(8分)4．用向量表示的循環(huán)隊(duì)列的隊(duì)首和隊(duì)尾位置分別為1和max_size，試給出判斷隊(duì)列為空和為滿(mǎn)的邊界條件。(5分)三、閱讀程序題(共10分)1．設(shè)G是一個(gè)有向無(wú)環(huán)圖，試指出下述算法的功能，輸出的序列是G的什么序列?(10分)voidDemo(ALGraphG){//G是圖的逆鄰接表，向量outdegree的各分量初值為0。for(i=0；i<G.NodeNum；i++)for(p=G.adjlist[i].firstedge；p；p=p->next)//掃描i的入邊表outdegree[p->adjvex]++；//設(shè)p->adjvex=j，則將<i，j>的起點(diǎn)j的出度加1initStack(&s)；//設(shè)置空棧sfor(i=0；i<G.NodeNum；i++)if(outdegree[i]==0)Push(&s，i)；//出度為0的頂點(diǎn)i入棧while(!StackEmpty(s))//棧s非空{(diào)i=Pop(&Q)；//出棧，相當(dāng)于刪去頂點(diǎn)iprinft(“%c”，G.adjlist[i].vertex)；//輸出頂點(diǎn)i