數(shù)據(jù)結(jié)構(gòu)與算法期末練習(xí)題1

1、、選擇：（每題2分，共30分）簡單選擇排序冒泡排序歸并排序穩(wěn)定1、下列排序算法中，其中（）是穩(wěn)定的。堆排序希爾排序快速排序基數(shù)排序不穩(wěn)定A）堆排序，冒泡排序B）快速排序，堆排序C）直接選擇排序，希爾排序D）歸并排序，冒泡排序2、下列排序方法中，哪一個(gè)是穩(wěn)定的排序方法？（）A）堆排序B）二分法插入排序C）希爾排序D）快速排序3、一個(gè)棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（）。A）23415B）54132C）23145D）154324、非空循環(huán)鏈表head的尾結(jié)點(diǎn)*p滿足下列（）條件A）head->next=p;B）head=p;C）p->next=head;D

2、）p->next=05、下列編碼中屬前綴碼的是（）A）1,01,000,001B）1,01,011,010C）0,10,110,11D）0,1,00,116、對于哈希函數(shù)H（key）=key%7,被稱為同義詞的關(guān)鍵字是（）A）36和50B）23和39C）15和44D）25和517、將一個(gè)長度為n的向量的第i個(gè)元素刪除時(shí)，需要前移（）個(gè)元素。A）iB）n-iC）n+1D）n-i+18、有一個(gè)有序表為1,3,9,12,32,41,45,62,77,88,92,100,用折半查找法，若要找62,要經(jīng)過（次比較。A.3B.6C.4D.59、高度為K的二叉樹最大的結(jié)點(diǎn)數(shù)為（）。A）2kB）2k-1

3、C）2k-1D）2k-1-110、對表長為n的順序表進(jìn)行順序查找，在查找概率相等的情況下，查找成功的平均查找長度為（）A）（n-1）/2B）n/2C）（n+1）/2D）n11、如果求一個(gè)連通圖中以某個(gè)頂點(diǎn)為根的高度最小的生成樹，應(yīng)采用（）A）深度優(yōu)先搜索算法B）廣度優(yōu)先搜索算法C）求最小生成樹的prim算法D）拓?fù)渑判蛩惴?2、已知有向圖的正鄰接鏈表的存儲(chǔ)結(jié)構(gòu)如下，從頂點(diǎn)1出發(fā)的按深度優(yōu)先遍歷序列是A）1234B）1423C）1324D）143213、一個(gè)循環(huán)順序隊(duì)列，隊(duì)頭、尾指針的值分別為front,rear,則隊(duì)列中元素個(gè)數(shù)為（）。（maxlen為循環(huán)順序B)(rear-front)%ma

4、xlen表的長度）A)(rear-front+maxlen)%maxlenC)rear-front+1D)front-rear+114、一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（）A）logn+1B）logn+1C）15、下面給出的四種排序法中（）A）插入B）冒泡C）二、填空題：（每空2分，共20分）1、深度為9的完全二叉樹最多有l(wèi)ognD）logn-1排序法是不穩(wěn)定性排序法。二路歸并D）快速排序511個(gè)結(jié)點(diǎn)。2、已知二叉樹后序?yàn)镈GEBFCA中序?yàn)镈BGEAQF則前序一定是ABDEGCF3、利用篩選法將關(guān)鍵字序列(37,66,48,29,31,75)建成的大根堆為(7566482931

5、37)。4、在順序表(8,11,15,19,25,26,30,33,42,48,50)中，用二分(折半)法查找關(guān)鍵碼值11,需做的關(guān)鍵碼比較次數(shù)為45、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下,從左到右依次對結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的孩子編號(hào)為：9899_6、在AOE-網(wǎng)中，設(shè)e(i)和l(i)分別表示活動(dòng)ai的最早開始時(shí)間和最晚開始時(shí)間，則當(dāng)且僅當(dāng)e(i)=l(i)時(shí)，ai為關(guān)鍵活動(dòng)。7、下面程序段的時(shí)間復(fù)雜度為o(n2)。(用O估計(jì))FORi:=1TOnDOFORj:=iTOnDOs=s+j;8、后根遍歷樹林正好等同于按后序遍歷對應(yīng)的二叉樹。9、在有序表A1.12

6、中，采用二分查找算法查等于A12的元素，所比較的元素下標(biāo)依次為69111210、n個(gè)頂點(diǎn)的連通無向圖，其邊的條數(shù)至少為n-1。三、解答題：(每題6分，共30分)1、已知一棵二叉樹的前序掃描序列和中序掃描序列分別為ABCDEFGHIJ和BCDAFEHJIG，試給出該二叉樹的后序序列并繪出該二叉樹對應(yīng)的森林。后序序列為：DCBFJIHGEA2、已知一棵二叉樹的前序序列和中序序列分別為abdghcefi和gdhbaecif,請畫出該二叉樹。ABCDEFGHI(I為f左子樹e為葉子)3、在二叉平衡檢索樹(AVL樹)的調(diào)整中，將最靠近新插入點(diǎn)的不平衡結(jié)點(diǎn)調(diào)整平衡后，樹中是否還會(huì)有不平衡結(jié)點(diǎn)？為什么？不會(huì)

7、再有不平衡點(diǎn)。因?yàn)椴迦虢Y(jié)點(diǎn)發(fā)生不平衡現(xiàn)象后，會(huì)改變以“靠近新插入點(diǎn)的不平衡結(jié)點(diǎn)”為根的子樹(即最小不平橫樹)的高度加1,經(jīng)過調(diào)整后使最小不平衡樹的整體高度又恢復(fù)到原來的值，所以不會(huì)對原平衡樹的其他部分造成危害，因此不會(huì)再有不平衡點(diǎn)。4、某通訊系統(tǒng)只可能有A、B、C、D、E、F6種字符,試畫出相應(yīng)的哈夫曼樹，并設(shè)計(jì)哈夫曼編碼。10060402535DECA字母對應(yīng)編碼出現(xiàn)頻率A00010.1B10.4C00000.04D0100.16E0110.19F0010.11其出現(xiàn)的概率分別是0.1、0.4、0.04、0.16、0.19、0.11,5、指定Hash函數(shù)H(k)=3

8、*kmod11及線性探測開地址法處理沖突，試在010的散列空間中對關(guān)鍵字序列(22,41,53,46,30,13,01,67)構(gòu)造Hash表，并求在等查找概率下查找成功的平均查找長度。5、解：插入元素后的分布情況:0123456789102241300153461367四、算法題：(每題10分，共20分)1、編寫一個(gè)函數(shù)或過程判定兩棵二叉樹是否相似，所謂兩棵二叉樹s和t相似，即是要么它們都為空或都只有一個(gè)結(jié)點(diǎn)，要么它們的左右子樹都相似。intSimilar(BiTreep,q)/判斷二叉機(jī)1由p和q是否相似if(p=null&&q=null)return(1);elseif(!

9、p&&q|p&&!q)return(0);elsereturn(Similar(p->lchild,q->lchild)&&Similar(p->rchild,q->rchild)/結(jié)束Similar2、下表列出了某工序之間的優(yōu)先關(guān)系和各工序所需時(shí)間，要求：(1)畫出AOE網(wǎng)(2)列出各事件的最早、最晚發(fā)生時(shí)間(3)找出該AOE網(wǎng)中的關(guān)鍵路徑，并回答完成該工程所需要的最短時(shí)間。工序代號(hào)所需時(shí)間先驅(qū)工序工序代號(hào)所需時(shí)間先驅(qū)工序A15無H15G、IB10無I120EC50A、BJ60ID8BK15F、IE15C、DL30H、J

10、、KF40BM20LG300E(2)各事件的最早最遲發(fā)生時(shí)間事件編號(hào)1234567891011ve(i)01510655080200380395425445vl(i)015576538080335380395425445(3)通過上表不用求出活動(dòng)的最早最遲開始時(shí)間就可以看出關(guān)鍵路徑為:1,2,4,6,8,9,10,11完成工程所需的最短時(shí)間為：445一、選擇：(每題2分，共30分)1、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中()。A)從源點(diǎn)到匯點(diǎn)的最長路徑B)從源點(diǎn)到匯點(diǎn)的最短路徑C)最長回路D)最短回路4、非空循環(huán)鏈表head的尾結(jié)點(diǎn)p滿足下列（）條件。A.head->next=pB.head=pC.

11、p->next=headD.p->next=nil7、將一個(gè)長度為n的向量的第i個(gè)元素刪除時(shí)，需要前移（）個(gè)元素。A）iB）n-iC）n+1D）n-i+19、已知L是帶頭結(jié)點(diǎn)的單鏈表，p指向表中某結(jié)點(diǎn)，則要?jiǎng)h除p結(jié)點(diǎn)的后繼結(jié)點(diǎn)應(yīng)執(zhí)行操作（）。A）pnext:=pnextnext;B）pnextnext:=.next;C）pnext:=s;snext:=pnext;D）snext:=pnext;pnext:=s;11、如果求一個(gè)連通圖中以某個(gè)頂點(diǎn)為根的高度最小的生成樹，應(yīng)采用（）A）深度優(yōu)先搜索算法B）廣度優(yōu)先搜索算法C）求最小生成樹的prim算法D）拓?fù)渑判蛩惴?2、從下列有關(guān)樹的

12、敘述中，選出正確的敘述（）A）二叉樹中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，而樹無此限制，因此二叉樹是樹的特殊情況。B）當(dāng)K>1時(shí)高度為K的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。C）哈夫曼樹是帶權(quán)路徑最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。D）在二叉樹中插入結(jié)點(diǎn)，該二叉樹便不再是二叉樹。五、填空題：（每空2分，共20分）1、樹中結(jié)點(diǎn)的最大層次稱為樹的高度或深度。_3、用一維數(shù)組r0.m-1表示順序存儲(chǔ)的循環(huán)隊(duì)列，設(shè)隊(duì)頭親口隊(duì)尾指針分別是front和rear,且隊(duì)頭指針?biāo)傅膯卧e置，則隊(duì)滿的條件是_（rear+1）%m=front,隊(duì)空的條件是_rear=front。六、解答題：（每題6分，共30分）1、在具有n

13、個(gè)結(jié)點(diǎn)的K（k>=2）叉樹的K叉鏈表表示中，有多少個(gè)空指針。2、已知一棵二叉樹的前序序列和中序序列分別為abdghcefi和gdhbaecif,請畫出該二叉樹。ABCDEFGHI（I為f左子樹e為葉子）3、若一組記錄的關(guān)鍵碼為（46,79,56,38,40,84）,則利用快速排序的方法，分別寫出以第一個(gè)記錄為基準(zhǔn)得到的前三次劃分結(jié)果。4038465679843840465679843840465679844、下圖是帶權(quán)的有向圖G的鄰接矩陣表示，請給出：A、其鄰接表存儲(chǔ)結(jié)構(gòu)B、按Floyd算法求所有頂點(diǎn)對之間最短距離的矩陣變化過程。V1V2V3V4V1|01oo4V2|oo092V3|35

14、08V4|oooo60AV1->v21->v44AV2->v39->v42AV3->v13->v25->v88AV4->v36->v40A5、判斷下列二叉樹是否為二叉搜索樹，如果是，是否為AVL樹，依次插入22、4、1,并對此表作相應(yīng)的調(diào)整。305、插入4后:20251522284050七、算法題：(每題10分，共20分)1、已知某哈希表的裝載因子小于1,哈希函數(shù)H(key)為關(guān)鍵字(標(biāo)識(shí)符)的第一個(gè)字母在字母表中的序號(hào)，處理沖突的方法為線性探測開放定址法，請編寫一個(gè)按第一個(gè)字母的順序輸出哈希表中所有關(guān)鍵字的算法。voidPrint_Has

15、h(HashTableH)按第一個(gè)字母順序輸出Hash表中的所有關(guān)鍵字，1、voidPrint_Hash(HashTableH)/按第一個(gè)字母順序輸出Hash表中的所有關(guān)鍵字，其中處理沖突采用線性探測開放定址法for(i=1;i<=26;i+)線性探測(小寫)for(j=i;H.elemj.key;j=(j+1)%hashsizesizeindex)/if(H(H.elemj.key)=i)printf("%sn",H.elemj);/Print_HashintH(char*s)/求Hash函數(shù)if(s)returns0-96;/求關(guān)鍵字第一個(gè)字母的字母序號(hào)elser

16、eturn0;/H2、設(shè)計(jì)遞歸函數(shù)，求一棵二叉樹的深度。IntDeepth(PBiTNodeT)If(T=NULL)Return0;Intleft=Deepth(T->rchild);Intright=Deepth(T->rchild);If(left>right)returnleft+1;Elsereturnright+1;選擇：(每題2分，共30分)15、下面給出的四種排序法中()排序法是不穩(wěn)定性排序法。5、A)插入B)冒泡C)二路歸并D)快速排序八、算法題：(每題10分，共20分)1、設(shè)雙鏈表結(jié)點(diǎn)結(jié)構(gòu)為llinkdatarlink,請?jiān)O(shè)計(jì)算法將其中P所指結(jié)點(diǎn)與其rlin

17、k所指結(jié)點(diǎn)位置互換的算法。2、設(shè)類型為sqqueue1的循環(huán)順序隊(duì)列只用一個(gè)rear指針，它指向隊(duì)尾元素的位置。另設(shè)計(jì)數(shù)器count用于記錄隊(duì)列中的元素個(gè)數(shù)。編寫算法實(shí)現(xiàn)隊(duì)列的初始化、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素操作。sqqueue1類型的循環(huán)順序隊(duì)列定義如下：#definemaxlen100typedefstructelemtypdatamaxlen;intrear,count;sqqueue1;九、算法題：(每題10分，共20分)1、解：typedefstructDLNodeElemTypedata;structDLNode*llink,*rlink;DLNode,*DLinkList;思想：將

18、P->rlink先從鏈表中刪除掉，然后再插入到P前StatusSwapANode(DLNode*&P)/結(jié)點(diǎn)存在嗎？if(!P|!(P->rlink)returnERROR;q=P->rlink;/刪除q結(jié)點(diǎn)if(!q->rlink)P->rlink=NULL;elseP->rlink=q->rlink;q->rlink->llink=P;/將q結(jié)點(diǎn)插入到P結(jié)點(diǎn)前面if(!P->llink)q->llink=NULL;q->rlink=P;P->llink=q;elseq->llink=P->ll

19、ink;q->rlink=P;P->llink->rlink=q;P->llink=q;returnOK;2、解：sqqueuelinitiate(sqqueue1q)q.rear=0;q.count=0;returnq;)sqqueue1inq(sqqueue1q,elemtpx)if(q.count=maxlen)print("overflow!”);elseq.rear=(q.rear+1)%maxlen;q.dataq.rear=x;q.count+;)returnq;)sqqueue1outq(sqqueue1q)if(q.count=0)print

20、f("underflow!);elseq.count-;returnq;)elemtpgethead(sqqueue1q)if(q.count=0)printf("underflow");elsek=(q.rear-q.count+1+maxlen)%maxlen;returnq.datak;)十、選擇：(每題2分，共30分)1、若從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是(A、二叉排序樹B、哈夫曼樹C、堆D、AVL樹2、下列排序方法中，哪一個(gè)是穩(wěn)定的排序方法？()A)堆排序B)二分法插入排序C)希爾排序D)快速排序7、對一組數(shù)

21、據(jù)(84,47,25,15,21)排序，數(shù)據(jù)的排列次序在排序的過程中的變化為(1)8447251521(2)1547258421(3)1521258447(4)1521254784則采用的排序是()。A)選擇B)冒泡C)快速D)插入<V3,V6>,<V4,V6>,<V5,V7>,9、已知有向圖G=(V,E),其中V=V1,V2,V3,V4,V5,V6,V7,E=<V,V2>,<V,V3>,<V,V4>,<M,V5>,<V3,V5><V6,V7>,G的拓?fù)湫蛄惺?)。A)Vl,V3,V4,V6,V2,V5,V7B)V1,V3,V2,V6,V4,V5,V7C)Vl,V3,V4,V5,V2,V6,V7D)V1,V2,V5,V3,