中南大學(xué)十套數(shù)據(jù)結(jié)構(gòu)試題及答案2

數(shù)據(jù)結(jié)構(gòu)試卷（一）一、單選題（每題2分，共20分）1?棧和隊(duì)列的共同特點(diǎn)是（）?Ao只允許在端點(diǎn)處插入和刪除元素Bo都是先進(jìn)后出C.都是先進(jìn)先出Do沒有共同點(diǎn)用鏈接方式存儲的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)（）。A.僅修改頭指針Bo頭、尾指針都要修改Co僅修改尾指針D.頭、尾指針可能都要修改以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？（）A.隊(duì)列B.棧Co線性表D.二叉樹4?設(shè)有一個(gè)二維數(shù)組A[川][門假設(shè)A[0][0]存放位置在644g4[2][2]存放位置在676g,每5.個(gè)元素占一個(gè)空間，A?688樹最適合用來表示（Ao有序數(shù)據(jù)元素問AB.[3][3]（⑼存放在什么位置？腳注（心表示用10進(jìn)制表示.678C.5.個(gè)元素占一個(gè)空間，A?688樹最適合用來表示（Ao有序數(shù)據(jù)元素問AB.[3][3]（⑼存放在什么位置？腳注（心表示用10進(jìn)制表示.678C.）。692D.696E?無序數(shù)據(jù)元素Do元素之間無聯(lián)系的數(shù)據(jù)C.元素之間具有分支層次關(guān)系的數(shù)據(jù)二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為（）.A?2k—1B.2K+1Co2K—1Do2k_1若有18個(gè)元素的有序表存放在一維數(shù)組A[1刃中，第一個(gè)元素放A[I]中，現(xiàn)進(jìn)行二分查找,則查找A[3]的比較序列的下標(biāo)依次為（Aob2,3C.9,5,3對n個(gè)記錄的文件進(jìn)行快速排序，Ao0（1）Bo0（n）對于線性表（7,34,55,25,64,函數(shù)，則散列地址為1的元素有A?1B?210?設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（A.5Bo6C.7D..Bo6Co2K—1)B.9,5,2,3Do9,4,2,3所需要的輔助存儲空間k致為Co046,20,10)()個(gè)，C.3（log：n）Do0（n2）進(jìn)行散列存儲時(shí)，若選用H（K）二K%9作為散列D?4）條邊才能確保是一個(gè)連通圖。填空題（每空1分，共26分）1.2.3.TOC\o"1-5"\h\z通常從四個(gè)方面評價(jià)算法的質(zhì)量:、.和?1.2.3.一個(gè)算法的時(shí)間復(fù)雜度為葉+/logw+14n）/憶其數(shù)量級表示為?假定一棵樹的廣義表表示為A（C,D（E,F,G）,H（IJ））,則樹中所含的結(jié)點(diǎn)數(shù)為個(gè)，樹的深度為，樹的度為.后綴算式923+-102/—的值為。中綴算式（3+4X）—2Y/3對應(yīng)的后綴算式為若用鏈表存儲一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹共有個(gè)指針域，其中有個(gè)指針域是存放了地址，有個(gè)指針是空指針。對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖,在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有個(gè)和個(gè)。AOV網(wǎng)是一種的圖.在一個(gè)具有11個(gè)頂點(diǎn)的無向完全圖中，包含有條邊，在一個(gè)具有11個(gè)頂點(diǎn)的有向完全圖中，包含有條邊。假定一個(gè)線性表為（12,23/74,55,63,40）,若按Key%4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為、、和-

10.11.12.

10.11.12.

三、1.在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為,整個(gè)堆排序過程的時(shí)間復(fù)雜度為o在快速排序、堆排序、歸并排序中.排序是穩(wěn)定的。計(jì)算題(每題6分，共24分)2.請畫出卜圖的鄰接矩陣和鄰接表。6050789034403572042.請畫出卜圖的鄰接矩陣和鄰接表。6050789034403572041A01234567datanext己知一個(gè)圖的頂點(diǎn)集VE={(1,2)3,(1,(3,5)12,(3,6)9,用克魯斯卡爾算法得到各條邊。畫出向小根堆中加入數(shù)堆的變化。四、閱讀算法(每題7分，共14分)1?LuikListmvnote(LuikListL){//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L—>next){q=L:L=L—〉next;p=L:S1:while(p—>next)p=p—>next;S2:p—>next=q：q—)next=NULL：}returnL；和邊集E分別為:V={1,2,3,4,5,6,7};3)5,(1,4)&(2,5)10,(2,3)6,(3,4)15,(4,6)4,(4,7)20,(5,6)18,(6,7)25};最小生成樹，試寫出在最小生成樹中依次得到的據(jù)4,2,5,8,3時(shí)，每加入一個(gè)數(shù)據(jù)后}請回答下列問題：說明語句S1的功能；說明語句組S2的功能；設(shè)鏈表表示的線性表為(aba2,…，an)，寫出算法執(zhí)行后的返回值所表示的線性表。2?voidABC(BTNode*BT){ifBT{ABC(BT—>left);ABC(BT-)right);cout<<BT->data〈〈"；}}該算法的功能是：五、算法填空(共8分)二叉搜索樹的查找一遞歸算法：boolFind(BTreeNode*BST,ElemType&item)辻(BST二二NULL)returnfalse;//查找失敗else{if(item~BST—〉data){item=BST~>data；//查找成功return;}

elseif(item<BST—>data)returnFind(,item):elsereturnFind(,item);}//if}編寫算法(共8分)統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。intCountX(LNode*HL,ElemTypex)一、選擇題(每題2分，共20分)A2。D3.D4.C5。C6。D7。D8.C9。D10.A填空題(每空1分，共26分)1.正確性易讀性強(qiáng)壯性高效率2.0(n)3.9334.-134)(*+2Y*3/—5.2nn—1n+16.e2e7.有向無回路8.n(n—1)/2n(n-1)9.(12,40)()(74)(23,55,63)增加10(logcn)0(nlogcn)歸并三、計(jì)算題(每題6分，共24分)線性表為:(78,50,40,60,34,90)鄰接矩陣：鄰接表如圖11所示：圖11用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,(b4)8,(2,5)10.(4,7)20分)樂題7分，:作為新見圖12分)樂題7分，:作為新四、讀算法四、(1)查詢応表的尾結(jié)點(diǎn)(2)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部,(3)返回的線性表為(如^)，…Qa山)遞歸地后序遍歷鏈?zhǔn)接械漶獍橪五、法填空(每空才分，惣分)?trueBST->1eft—>right六、編寫算法(8分)匹①intCountX(LNode*HL,ElemTypex){iiiti=0;LNode*p=HL；//i為計(jì)數(shù)器while(p!=NULL){if(P—>data=x)i++：p=p>next；}//wlule,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)returni;}//CountX數(shù)據(jù)結(jié)構(gòu)試卷(二)一、選擇題(24分)下面關(guān)于線性表的敘述錯(cuò)誤的是()。線性表采用順序存儲必須占用一片連續(xù)的存儲空間線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m,若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有()個(gè)空指針域。2m-1(B)2m(C)2m+l(D)4m設(shè)順序循環(huán)隊(duì)列Q[O:M-1]的頭指針和尾指針分別為F和R,頭指針F總是指向隊(duì)頭元素的前一位置,尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為().R-F(B)F-R(C)(R-F+M)%M(D)(F—R+M)%M設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹得到序列為()。(A)BADC(B)BCDA(C)CDAB(D)CBDA設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有()條邊.(A)n(n—1)/2(B)n(n~l)(C)n"(D)rT—1設(shè)某棵二叉樹中有2000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為()。(A)9(B)10(C)11(D)12設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有()個(gè)表頭結(jié)點(diǎn)。(A)n~l(B)n(C)n+1(D)2n—1設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為()。(A)2,3,5,8,6(B)3,2,5,&6(C)3,2,5,6,8(D)2,3,6,5,8二、填空題(24分)為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問題是和下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在卞劃線處填上正確的語句.tvpedefstmct{iiits[100];iiittop;}sqstack;voidpush(sqstack&stack?iiitx){if(stackotop=m—1)priiitf("overflow”);TOC\o"1-5"\h\zelse{;:}}中序遍歷二叉排序樹所得到的序列是序列(填有序或無序)?？焖倥判虻淖顗臅r(shí)間復(fù)雜度為，平均時(shí)間復(fù)雜度為o設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為No,度數(shù)為1的結(jié)點(diǎn)數(shù)為N’，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有個(gè)空指針域。設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e,所有頂點(diǎn)的度數(shù)之和為d,則e二。設(shè)一組初始記錄關(guān)鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)QFS遍歷的輸出序列是

,EFS遍歷的輸出序列是三、應(yīng)用題(36分)設(shè)一組初始記錄關(guān)鍵字序列為(45,80,48,40,22,78),則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果.設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量q指向被插入結(jié)點(diǎn)B,要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列(設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink)。設(shè)一組有序的記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長度。設(shè)一棵樹T中邊的集合為{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹.設(shè)有無向圖G,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。設(shè)有一組初始記錄關(guān)鍵字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計(jì)題〈16分)設(shè)有一組初始記錄關(guān)鍵字序列(K：,辰，…，心)，要求設(shè)計(jì)一個(gè)算法能夠在0(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于氐，右半部分的每個(gè)關(guān)鍵字均大于等于氐。設(shè)有兩個(gè)集合A和集合B,要求設(shè)計(jì)生成集合C二AC1B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示.一、選擇題1.D2。B1.D2。B3.C4.A5oA6.C7oB8.C填空題構(gòu)造一個(gè)好的HASH函數(shù)，確定解決沖突的方法2?stackotop++,stackos[stackotop]二x有序0(n"),0(nlog：n)No-1,2No+Nid/2(31,38,54,56,75,80,55,63)(1,3,4,5,2),(1,3,2,4,5)三、應(yīng)用題(22,40,45,4&80,78),(40,45,48,80,22,78)q-〉llink=p;q—)rlHik=p—>rliiik；p->rliiik_>llink=q；p—)iiink=q:2,ASL二91*1+2*2+3*4+4*2)=25/9樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略E={(1,3),(1,2),(3,5),(5,6),(6,4)}略四、算法設(shè)計(jì)題設(shè)有一組初始記錄關(guān)鍵字序列(心&,???,&),要求設(shè)計(jì)一個(gè)算法能夠在0(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個(gè)關(guān)鍵字均小于心右半部分的每個(gè)關(guān)鍵字均人于等于K：。voidquickpass(iiitr[],ints,intt){inti=s,j=t,x=r[s]:wliile(i<j){wlule(i<j&&r[j]>x)j=j-l;if(i<j){r[i]=r|j];i=i+l;}wliile(i<j&&r[i]<x)i=i+l:if(i<j){r[j]=r[i]j=j-l：)H】］=X；}設(shè)有兩個(gè)集合A和集合B,要求設(shè)計(jì)生成集合C二ACB的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。tvpedefstmctnode{intdata;stiuctnode*next;}lklist：voidintersection(lklist*ha,lklistlklist*&hc)(lklist*t;fdr(p=hathc=0;p!=0;p=p->next){fbr(q=hb：q!=0；q=q->next)if(q—〉data=p->data)break;if(q!=O){t=(lklist*)nialloc(sizeof(lklist));t->data=p-)data；t—〉next=hc；hc=t：}}}數(shù)據(jù)結(jié)構(gòu)試卷(三)一、選擇題(每題1分，共20分)設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D,R),D={01,02,03,04,05,06,07,08,09},R={r}尸{<01,02>,<01,03〉，<01,04>,<02,05>,<02,06),<03,07>,<03,08>,<03,09>},貝I」數(shù)據(jù)結(jié)構(gòu)A是().(A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu)下面程序的時(shí)間復(fù)雜為()for(i=l,s=0；i(=n：i++){t=l：for(j=l；j<=i：j++)t=t*j：s=s+t；}(A)0(n)(B)0(n:)(C)0(n3)(D)0(n1)設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,若刪除單鏈表中結(jié)點(diǎn)A,則需要修改指針的操作序列為()。q二p—〉next；p~>data=q-)data：p—>next二q—〉next；free(q)；q二p->next；q->data二p—〉data；p—〉next二q-〉next；free(q)：q二p—〉next;p~>next=q->next；free(q)；q二p—>next;p~>data二q->data：free(q);設(shè)有n個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要()個(gè)輔助記錄單元。(A)1(B)n(C)nlog：n(D)n:設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20,15,14,18,21,36,40,10),則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為().10,15,14,18,20,36,40,2110,15,14,1&20,40,36,2110,15,14,20,18,40,36,2115,10,14,18,20,36,40,21設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長度為()。(A)0(1)(B)Odogzn)(C)(D)0(n‘)設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為()。(A)11,e(B)e,n(C)2n,e(D)n,2e設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有()條邊。(A)n(n-l)(B)n+1(C)n(D)n(n+1)設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列()方法可以達(dá)到此目的。(A)快速排序(B)堆排序(C)歸并排序(D)插入排序10o下列四種排序中()的空間復(fù)雜度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序二、填空殖(每空1分共20分)數(shù)據(jù)的物理結(jié)構(gòu)主要包拾和兩種情況.設(shè)一棵完全二叉樹中有500個(gè)結(jié)點(diǎn)，則該二叉樹的深度為；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu),則共有個(gè)空指針域。設(shè)輸入序列為1、2、3,則經(jīng)過棧的作用后可以得到種不同的輸出序列.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的，第i列上所有元素之和等于頂點(diǎn)i的o設(shè)哈夫曼樹中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有個(gè)度數(shù)為1的結(jié)點(diǎn)。設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d,則e和d的關(guān)系為.遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列(填先序、中序或后序)。

設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較次就可以斷定數(shù)據(jù)元素X是否在查找表中。不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個(gè)結(jié)點(diǎn)的雙TOC\o"1-5"\h\z親結(jié)點(diǎn)編號為,右孩子結(jié)點(diǎn)的編號為o設(shè)一組初始記錄關(guān)鍵字為(72,73,71,23,94,16,5),則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為.設(shè)有向圖G中有向邊的集合己={〈1,2),<2,3〉，<1,4〉，<4,2〉，<4,3>},則該圖的一種拓?fù)湫蛄袨閛13?下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請?jiān)谙聞澗€處填上正確的語句。stmctrecord{intkey；nitothers;}：inthashsqsearch(stinctrecordhashtable[],iiitk){intij；j=i=k%p；while(hashtable[j]?key!=k&&hashtablefj]oflag!=0){j=()%m：if(i==j)return(-1)；}if()retuin(j)：elseieturn(-l);}14.下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k,請?jiān)谙聞澗€處填上正確的語句.tvpedefstmctnode{hitkey;stmctnode*lcliild：stiuctnode*icliild：}bitree：bitree*bstsearch(bitree*t,intk)(if(t=0)return(0)：elsewliile(t!=0)if(t—>key=k)；elseif(t—>key)k)t=t_>lchild;else；}三、計(jì)算題(每題10分，共30分)已知二叉樹的前序遍歷序列是AEFBGCDHIKJ?中序遍歷序列是EFAGECHKUD,畫出此二叉樹，并畫出它的后序線索二叉樹.已知待散列的線性表為(36,15,40,63,22),散列用的一維地址空間為[0?。6]，假定選用的散列函數(shù)是H(K)=Kmod7,若發(fā)生沖突采用線性探查法處理，試：計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表：0123456求出在查找每一個(gè)元素概率相等情況下的平均查找長度。已知序列(10,18,4,3,6,12,1,9,顯、8)請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果.四、算法設(shè)計(jì)題(每題15分，共30分)設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。數(shù)據(jù)結(jié)構(gòu)試卷(三)參考答案選擇題l.B2oB6.B選擇題l.B2oB6.B7oD3.A8.C4.A9.B5.A10.D第3小題分析:首先用指針變量q指向結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B,然后將結(jié)點(diǎn)B的值復(fù)制到結(jié)點(diǎn)A中，最后刪除結(jié)點(diǎn)B.第9小題分析：9快速排序、歸并排序和插入排序必須等到整個(gè)排序結(jié)束后才能夠求出最小的10個(gè)數(shù),而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時(shí)間復(fù)雜度為0(log：n).二、填空題順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)TOC\o"1-5"\h\z9,5015出度，入度0e二d中序70(1)i/2,2i+l(5,16,7b23,72,94,73)(1,4,3,2)j+hhashtable[j].key=kreturn(t),t二t->rch訂d第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹.在有序表上進(jìn)行二分查找時(shí)的查找長度不超過二叉判定樹的高度l+log：no三、計(jì)算題1.2、2、H(36)=36mod7=1；H(15)=15mod7=1;...o沖突Hi(15)=(1+1)mod7=2;H(40)=40mod7=5;Hi(22)=(l+l)mod7=2；…。沖突H2(22)=(2+1)mod7=3;H(63)=63mod7=0：H(22)=22mod7=1：..??沖突6336152240(1)0123456(2)ASL=3、(&9,4,3,6,1),10.(12,18,18)(1,6,4,3),&(9))0J2,(18,18)(3A6)39,10,12,18,(18)b3,(4、6),&9,10,12,18,18b3,4,6,8,94042,18,18四、算法設(shè)計(jì)題~設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。tvpedefintdatatype；tvpedefstmctnode{datatypedata；structnode*next;)lklist;voiddeliedundant(lklist*&head)lklist*q.*s;fbr(p=head;p!=O;p=p-)next){for(q=p—〉next,s=q;q!=0;)if(q->data=p->data){s—>next=q—>next；flee(q)；q=s—>next；}else{s=q,q=q—>next：}}設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。tvpedefstmctnode{datatypedata；structnode*lchild,*rcliild；}bitree：bitree*q[20]：intr=0.f=0.flag=0;voidpreoider(bitree*bt,charx)if(bt!=0&&flag=0)if(bt->data==x){flag=1;return；}else{r=(r+1)%20；q[r]=bt;pieordei(bt->lchild.x):preoider(bt一>rcliild,x)；}}voidparent(bitiee*bt,charx)mti；preorder(bt,x)；fdr(i=ft-l:i<=r：i++)if(q[i]—>lcluld—〉data=x|Iq[i]—>rcliild—〉data)break;if(flag==0)piiiitf(nnotfoundx\n”)；elseif(i<=i)printf(v%cn,bt->data);elseprintf(vnotparent11);數(shù)據(jù)結(jié)構(gòu)試卷(四)一、選擇題(每題1分共20分)設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為()。0(n)(B)0(nlog;n)(C)0(1)(D)0(n：)設(shè)一棵二叉樹的深度為k,則該二叉樹中最多有()個(gè)結(jié)點(diǎn)。2k—1(B)2k(02k_1(D)2k-l設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為().(A)n(B)e(C)2n(D)2e在二叉排序樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為()。(A)0(1)(B)0(n)(C)Odogzn)(D)0(n：)設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有()條有向邊。(A)n(B)n—1(C)m(D)m—1設(shè)一組初始記錄關(guān)鍵字序列為(345,253,674,924,627),則用基數(shù)排序需要進(jìn)行()趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(A)3(B)4(C)5(D)8設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作()。(A)必須判別棧是否為滿(B)必須判別棧是否為空(C)判別棧元素的類型(D)對棧不作任何判別下列四種排序中()的空間復(fù)雜度最大。(A)快速排序(B)冒泡排序(C)希爾排序(D)堆設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N。，度數(shù)為1的結(jié)點(diǎn)數(shù)為N】,度數(shù)為2的結(jié)點(diǎn)數(shù)為N：,則下列等式成立的是().(A)N。二凡+1(B)No=Ni+N:(C)N^Nc+l(D)No二2M+1設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過()。(A)log：n+l(B)logzn—1(C)logzn(D)log：(n+1)二、填空題(每空1分共20分)設(shè)有n個(gè)無序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為，快速排序的平均時(shí)間復(fù)雜度為O設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X,則刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為(設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為11ink和rlink).根據(jù)初始關(guān)鍵字序列(19,22,01,3&10)建立的二叉排序樹的高度為o深度為k的完全二叉樹中最少有個(gè)結(jié)點(diǎn)。設(shè)初始記錄關(guān)鍵字序列為(Ki,K：,…，KJ,則用篩選法思想建堆必須從第個(gè)元素開始進(jìn)行篩選。設(shè)哈夫曼樹中共有99個(gè)結(jié)點(diǎn)，則該樹中有個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有個(gè)空指針域.設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲單元，則該循環(huán)隊(duì)列中最多能夠存儲個(gè)隊(duì)列元素；當(dāng)前實(shí)際存儲個(gè)隊(duì)列元素(設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，尾指針指向當(dāng)前隊(duì)尾元素的位置)。設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動表中個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動表中個(gè)元素。設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30.19),則以20為中軸的一趟快速排序結(jié)果為設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為設(shè)某無向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點(diǎn)1和頂點(diǎn)J互為鄰接點(diǎn)的條件是o設(shè)無向圖對應(yīng)的鄰接矩陣為A,則A中第[上非0元素的個(gè)數(shù)第1列上非0元素的個(gè)數(shù)(填等于，大于或小于).設(shè)前序遍歷某二叉樹的序列為ABCD,中序遍歷該二叉樹的序列為BADC,則后序遍歷該二叉樹的序列為O設(shè)散列函數(shù)H(k)=kmodp,解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn)，成功時(shí)返回指向關(guān)鍵字的指針，不成功時(shí)返回標(biāo)志0。typedefstmctnode{iiitkey：stmctnode*next；}lklist;voidcreatelkliash(lklist*hashtable[]){inti,k;lklist*s；for(i=0;i<m;i++):fbr(i=O;i<n;i-H-){s=(lklist*)malloc(sizeof(lklist))；s—>kev^a[i];k=a[i]%p;s->next=hashtable[k]；；}}三、計(jì)算題(每題10分，共30分)1、畫出廣義表LS二((),(e),(a,(b,c,d)))的頭尾鏈表存儲結(jié)構(gòu)。2、下圖所示的森林:(1)求樹(a)的先根序列和后根序列：求森林先序序列和中序序列：將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；3、設(shè)散列表的地址范圍是】0..9],散列函數(shù)為H(key)二(key=+2)MOD9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。四、算法設(shè)計(jì)題(每題10分，共30分)設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(犬寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。一、選擇題1.C2?D3?D6.A7?B8?A4?B9?C5?C10.A—>填空題1.0(n"),0(nlog：n)2.p>lluik—>ilnik=p—>rlu±；p—>rlnik->llink=p->rluik3.3TOC\o"1-5"\h\z2k_1n/250,51m-b(R—F+M)%Mn+1—n-i(19,18,16,20,30,22)(16,18,19,20,32,22)A[i][jl=l等于BDCAhashtable[i]=0,hashtable[k]=s三、計(jì)算題1.2.(1)ABCDEF;BDEFCA：(2)ABCDEFGHIJK：BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹；H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6四、算法設(shè)計(jì)題設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(人寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。typedefchardatatype：typedefstmctnode{datatypedata;stmctnode*next;}lklist；voidsplit(lklist*head,lklist*&ha,lklist*&hbjklist*&hc)(lklist*p；ha=0.hb=0,hc=O；for(p=head;p!=0;p=head){head=p->next；p->next=0;if(p->data>=A‘&&p一>data〈='Z'){p->next=ha：ha=p;}elseif(p-)data)='(X&&p—>data〈=‘9’){p—>next=hb：hb=p;}else{p一>next=hc;hc=p：}}設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法.typedefstmctnode{intdata；stmctnode*lcluld,*rcluld;}bitree；voidswapbitree(bitiee*bt){bitree*p;if(bt==O)return；swapbitree(bt—〉lchild)：swapbitree(bt-)rchild);p=bt->lchild：bt一〉lchild=bt一〉rchild：bt->icliild=p;}在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。#definen10typedefstmctnode{mtkey;stmctnode*lchild,*rchild;}bitree:voidbstinseil(bitiee*&bt,mtkey)if(bt==O){bt=(bitree*)malloc(sizeof(bitree))：bt一〉key=key：bt->lcliild=bt一〉ichild=O；}elseif(bt—〉key)key)bstiiisert(bt一>lchild,key)；elsebstinsert(bt->rchild>key);}voidcreatebsttree(bitree*&bt)mti；for(i=l；ibstinsert(bt,random(100))；數(shù)據(jù)結(jié)構(gòu)試卷(五)數(shù)據(jù)結(jié)構(gòu)試卷(五)一、選擇題(20分)數(shù)據(jù)的最小單位是()。數(shù)據(jù)項(xiàng)(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量2?設(shè)一組初始記錄關(guān)鍵字序列為(50,40,95,20,15,70,60,45),則以增量44的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為()o40,50,20,95(015,20,40,4540,50,20,95(015,20,40,4515,40,60,20(D)45,40,15,203?設(shè)一組初始記錄關(guān)鍵字序列為(25,50,15,35,80,85,20,40,36,70),其中含有5個(gè)長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為()。15,25,35,50,20,40.80,85,36,7015,25,35,50,80.20,85,40,70,3615,25,35,50,80,85,20,36,40,7015,25,35,50,80,20,36,40,70,854?函數(shù)substr(“DATASTRUCTURE”,5,9)的返回值為()。(A)“STRUCTURE”(B)“DATA"“ASTRUCTUR”(D)“DATASTRUCTURE"設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為()。(A)0(log：n)(B)0(1)(C)0(n2)(D)0(n)設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N。，度數(shù)為1的結(jié)點(diǎn)數(shù)為……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm,則口二()。(A)Ni+N：+……+Nm(B)1+N2+2N3+3N<+……+(m—1)Nm(C)N：+2M+3M+……+(m—1)Nm(D)2N1+3N：+……+(m+l)Nm設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較()次.(A)25(B)10(C)7(D)1設(shè)連通圖G中的邊集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},貝II從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為()。(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb9.設(shè)輸入序列是1、2、3、、n,經(jīng)過棧的作用后輸出序列的第一個(gè)元素是m則輸出序列中第i個(gè)輸出元素是()o(A)n—i(B)n-l-i(C)n+1—i(D)不能確定10設(shè)一組初始記錄關(guān)鍵字序列為(45,80,55,40,42,85),則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是()。(A)40,42,45,55,80,83(B)42,40,45,80,85,88(C)42,40,45,55,80,85(D)42,40,45,85,55,80二、填空題(共20分)設(shè)有一個(gè)順序共享?xiàng)[0：n-1],其中第一個(gè)棧項(xiàng)指針topi的初值為-1,第二個(gè)棧頂指針top2的初值為n,則判斷共享?xiàng)M的條件是。在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是o設(shè)有一個(gè)n階的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對角線上元素)存放在n(n+1)個(gè)連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有個(gè)數(shù)據(jù)元素。棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為表;隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為表.設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF,則該二叉樹的前序遍歷序列為，中序遍歷序列為.后序遍歷序列為.設(shè)一棵完全二叉樹有128個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為,有個(gè)葉子結(jié)點(diǎn)。設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的,第i列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的。設(shè)一組初始記錄關(guān)鍵字序列(也匕，……,kn)是堆，則對遼1,2,…，n/2而言滿足的條件為卜?面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請?jiān)谙聞澗€處填上正確的語句。voidbubble(iiitr[n]){for(i=l;i<=n-l;i++){for(exchaiige=OJ=0;j<;j++)if(r[j]>r[j+1]){temp=r[j+l];;r[j]=temp：exchange=1;}if(exchange=O)return；}}下面程序段的功能是實(shí)現(xiàn)二分查找算法，請?jiān)诒鍎澗€處填上正確的語句.stmctrecord{iiitkey：mtothers;}；nitbisearcli(sti-uctrecordr[],iiitk)(nitlow=0,mid,high=n—1;\vhile(low<=high)if(i[niid]okey=k)Tetuni(mid+1);elseif()lugh=mid—l;elselow=mid+l;}retuin(0);}三、應(yīng)用題(32分)設(shè)某棵二叉樹的中序遍歷序列為DBEAC,前序遍歷序列為ABDEC,要求給出該二叉樹的的后序遍歷序列。設(shè)無向圖G(如右圖所示)，給出該圖的最小生成樹上邊的集合并計(jì)算最小生成樹各邊上的權(quán)值之和.設(shè)一組初始記錄關(guān)鍵字序列為(15,17,18,22,35,51,60),要求計(jì)算出成功查找時(shí)的平均查找長度。設(shè)散列表的長度為8,散列函數(shù)H(k)=kmod7,初始記錄關(guān)鍵字序列為(25,31,8,27,13,68),要求分別計(jì)算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。四、算法設(shè)計(jì)題(28分)設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法.設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。一、選擇題A2.B3.A4.A5.D6.B7.B8.B9.C10.C二、填空題topl+l=top2可以隨機(jī)訪問到任一個(gè)頂點(diǎn)的簡單鏈表i(i+l)/2+j-lFILO,FIFO5?ABDECF,DBEAFC,DEBFCA8,64出度，入度kx<=k2i&&ki〈=k》Tn—i,r[j+1]=r[j]nud=(low+high)/2,r[mid].key>k三、應(yīng)用題DEBCAE={(1,5)，(5,2),(5,3),(34)}，W=10ASL=(1*1+2*2+3*4)/7=1刀7ASLI=7/6,ASL2=4/3四、算法設(shè)計(jì)題設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法.tvpedefstmctnode{datatypedata;stmctnode*lchild.*rcluld;}bitiee；intjudgebitree(bitree*btl,bitiee*bt2){if(btl==O&&bt2==0)return(1)；elseif(btl=OI|bt2=0|Ibtl—〉data!=bt2—〉data)return(0)；elsereturn(judgebitiee(btl-)lchild,bt2->lchild)*judgebitiee(bt1—〉rcluld,bt2—>rchild))；}設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。voidmergelklist(lklist*ha,lklist*hbJklist*&hc){lklist*s=hc=0；wliile(ha!=0&&hb!=0)if(ha->data<hb->data){if(s=0)hc=s=ha;else{s->next=ha：s=ha;};ha=ha—〉next;)else{if(s=O)hc=s=hb;else{s—>next=hb；s=hb；}；hb=hb->next：}if(ha==0)s->next=hb;elses—〉next=ha;數(shù)據(jù)結(jié)構(gòu)試卷(六)一、選擇題(30分)設(shè)一組權(quán)值集合W={2,3,4,5,6},則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為()。(A)20(B)30(C)40(D)45執(zhí)行一趟快速排序能夠得到的序列是()。[41,12,34,45,27]55[72,63][45,34,12,41]55[72,63,27][63,12,34,45,27]55[41,72][12,27,45,41]55[34,63,72]設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是()。(A)head==0(B)head->next=0(C)head-)next==head(D)head!二0時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為0(nl。別n)的是()。(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是()。(A)空或只有一個(gè)結(jié)點(diǎn)(B)高度等于其結(jié)點(diǎn)數(shù)(C)任一結(jié)點(diǎn)無左孩子(D)任一結(jié)點(diǎn)無右孩子一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是().(A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序設(shè)某棵三叉樹中有40個(gè)結(jié)點(diǎn)，則該三叉樹的最小高度為()。(A)3(B)4(C)5(D)68?順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為()(C)0(n12)(D)0(log：n)(C)0(nlogcn)(D)0(logm))個(gè)結(jié)點(diǎn)。(C)2^+1(D)2-1(A)0(n)(B)0(n2)二路歸并排序的時(shí)間復(fù)雜度為().(A)0(n)(B)0(n：)深度為k的完全二叉樹中最少有((A)2^—1(B)2k_111。設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X,則入隊(duì)列的操作序列為()。(A)front")next二s；front=s;(B)s-〉next二rear；rear=s；(C)rear-)next二s;rear二s；(D)s~)next二front；front=s；設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為()。(A)0(n+e)(B)0(n2)(C)0(ne)(D)0(n3)設(shè)某哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有()個(gè)葉子結(jié)點(diǎn)。(A)99(B)100(C)101(D)10214?設(shè)二叉排序樹上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為()o(A)0(n)(B)0(n：)(A)0(n)(B)0(n：)(C)0(nlog：n)(D)0(log：n)15.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu),則有向圖G中頂點(diǎn)i的入度為((A)(A)第i行非0元素的個(gè)數(shù)之和(C)第i行0元素的個(gè)數(shù)之和第i列非0元素的個(gè)數(shù)之和第i列0元素的個(gè)數(shù)之和二、判斷題(20分)調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn).()分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān).()冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹.（）設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）層次遍歷初始堆可以得到一個(gè)有序的序列.（）設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT,則二叉樹BT中一定沒有右子樹。（）線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。（）中序遍歷二叉排序樹可以得到一個(gè)有序的序列。（）快速排序是排序算法中平均性能最好的一種排序。（）三、填空題（30分）TOC\o"1-5"\h\zfor（i=l,t=l,s=0；i〈二n;i++）{t=t*i;s=s+t；}的時(shí)間復(fù)雜度為.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的新結(jié)點(diǎn)X,則進(jìn)行插入操作的語句序列為（設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext）。設(shè)有向圖G的二元組形式表示為G=（D.R）,D={1,2,3,4,5},R={r},r={<1,2〉，（2,4>,（4,5>,〈1,3>,<3,2>,<3,5）},則給出該圖的一種拓?fù)渑判蛐蛄衞設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖中每個(gè)頂點(diǎn)的度數(shù)最多是o設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50,度數(shù)為1的結(jié)點(diǎn)數(shù)為30,則該二叉樹中總共有個(gè)結(jié)點(diǎn)數(shù).設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循壞隊(duì)列為空的條件為設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild,則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是。簡單選擇排序和直接插入排序算法的平均時(shí)間復(fù)雜度為。快速排序算法的空間復(fù)雜度平均情況下為最壞的情況下為o10o散列表中解決沖突的兩種方法是和?四、算法設(shè)計(jì)題（20分）.設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。.設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。.在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計(jì)直接插入排序算法一、選擇題1.D2.A3.A4?A5?D6.D7.B8.A9?C10.B11?C12.A13.B14..D15.B二、判斷題1.錯(cuò)2?對3.對4.對5.錯(cuò)6.錯(cuò)7?對8.錯(cuò)9.對10.對三、填空題TOC\o"1-5"\h\z0(n)s—>next=p-)next;p—〉next=s(1,3,2,4,5)n-1129F==Rp—>lchild==O&&—〉rcliild=OO(n2)O(nlog2n),O(n)開放定址法，鏈地址法四、算法設(shè)計(jì)題設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。stmctrecord{iiitkey：intothers;}；intbisearch(stmctrecordr[],intk)(intlow=(\mid,high=n—1;while(low〈=high){nud=(low+liigh)/2;if(r[niid]okey=k)ietuin(inid+l);elseif(r[niid].key〉k)high=niid—1：elselow=inid+l;}return(0);}設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法.intminiium=一32768.flag=l;tvpedefstmctnode{intkey：stmctnode*lcliild,*rchild;}bitree；voidinorder(bitree*bt){if(bt!=O){inorder(bt一>lcliild);if(inimium>bt一〉key)flag=0；niiimum=bt一〉key;iiioider(bt一>rcluld);}}在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計(jì)直接插入排序算法voidstraightinsertsort(lklist*&head){lklist*St*p,*q；iiitt;if(head==0I|liead->next=0)leturn：elsefor(q=head,p=head——>next：p!=0；p=q——>next){fbr(s=head;s?=q—〉next；s=s->next)if(s->data>p—〉data)break;if(s==q->next)q=p；else(q-)next=p->next；p—〉next=s->next;s—>next=p：t=p—〉data；p—>data=s->data：s->data=t：}數(shù)據(jù)結(jié)構(gòu)試卷(七)一、選擇題(30分)設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有()個(gè)表頭結(jié)點(diǎn)。(A)2n(B)n(C)n/2(D)n(nT)設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖的最小生成樹上有()條邊。(A)n(B)n-l(C)2n(D)2n—1設(shè)一組初始記錄關(guān)鍵字序列為(60,80,55,40,42,85),則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是()。(A)40,42,60,55,80,85(B)42,45,55,60,85,8042,40,55,60,80,85(D)42,40,60,85,55,80()二叉排序樹可以得到一個(gè)從小到大的有序序列。(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為()。(A)2i+l(B)2i(C)i/2(D)2i—1程序段s=i=0;do{i=i+l;s=s+i;}wlule(K=n);W時(shí)間復(fù)雜度為()。(A)0(n)(B)O(nlog：n)(0O(n')(D)0(n'/2)設(shè)帶有頭結(jié)點(diǎn)的單向循壞鏈表的頭指針變量為head,則其判空條件是()o(A)head=O(B)head-〉next==0(C)head—〉next二二head(D)head!二0設(shè)某棵二叉樹的高度為10,則該二叉樹上葉子結(jié)點(diǎn)最多有()。(A)20(B)256(C)512(D)1024設(shè)一組初始記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90,115,134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為()?(A)1(B)2(C)3(D)4設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為()。(A)top二top+1;(B)top二top—1;(C)top_>next二top；(D)top二top->next;二、判斷題(20分)不論是入隊(duì)列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出"情況。()當(dāng)向二叉排序樹中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。()設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為0(1。刖1).()完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。()哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。()對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。()先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列.()由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。()線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素.()10o帶權(quán)無向圖的最小生成樹是唯一的。()三、填空題(30分)設(shè)指針變量P指向雙向鏈表中的結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為二p；s—>right=p->right；二s；p—>right—)left二s;(設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right)。設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有條有向條；設(shè)完全無向圖中有n個(gè)頂點(diǎn),則該完全無向圖中共有條無向邊。設(shè)關(guān)鍵字序列為(心圧，…，也)，則用篩選法建初始堆必須從第個(gè)元素開始進(jìn)行篩選。解決散列表沖突的兩種方法是和。設(shè)一棵三叉樹中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹中度數(shù)為3的結(jié)點(diǎn)數(shù)有個(gè)。高度為h的完全二叉樹中最少有個(gè)結(jié)點(diǎn)，最多有個(gè)結(jié)點(diǎn)。設(shè)有一組初始關(guān)鍵字序列為(24,35,12,27,18,26),則第3趟直接插入排序結(jié)束后的結(jié)果的是設(shè)有一組初始關(guān)鍵字序列為(24,35,12,27,18.26),則第3趟簡單選擇排序結(jié)束后的結(jié)果的是設(shè)一棵二叉樹的前序序列為ABC,貝lj有種不同的二叉樹可以得到這種序列.10?下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請?jiān)谙聞澗€處填上正確的語句。stmctrecord{iiitkey；datatypeotliers;}:voidquickpass(stmctrecordr[]?iiits、intt,iiit&i){intj=t；stmctlecoidx=r[s];i=s;wliile(1<j){wliile(i<j&&i[j]。key>x<>key)j=j—1;if(i<j){i[i]=r[j]；i=i+l;}while()i=i+l；if(i〈j){r[j]=r[i]:j=j—1；}}}四、算法設(shè)計(jì)題(20分)設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡單選擇排序算法.設(shè)計(jì)在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹中層次的算法。一、選擇題1.B2?B3?C4?B5?B6.A7?C8?C9?B10.D二、判斷題1.對2.對3.對4.對5.對6.對7.對8.錯(cuò)9.錯(cuò)10.錯(cuò)三、填空題1?s->left=p,p—>rightn(n—1),n(n—1)/2TOC\o"1-5"\h\zn/2開放定址法，鏈地址法142叫2h-l(12,24,35,27,18,26)(12,18,24,27,35,26)5i〈j&&r[i]okey<Xokey,r[訂=x四、算法設(shè)計(jì)題設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡單選擇排序算法.voidsimpleselectsorlklist(lklist*&head){lklist*s;intmin,t;if(head==0||liead-)next==0)return：fbr(q=head;q?=0；q=q->next)(niin=q—>data；s=q：for(p=q->next;p!=0：p=p?〉next)p—>data){niui=p—〉data;s=p；)if(s!=q){t=s—〉data；s->data=q—>data；q—〉data=t;}}}設(shè)計(jì)在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。voidsubstimg(chars[],longstart,longcount,cliart[])(longi,j,length=strlen(s):if(start<l|Istart>length)piiiitf("Thecopypositioniswrong");elseif(stail+count一1>length)printsnToocharacterstobecopied)：else{for(i=start-Lj=0；i<start+count-1;i++,j++)t[j]=s[i];t[j]='\0‘；}}設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹中層次的算法。intlev=0：tvpedefstmctnode{iiitkey：stmctnode*lchild,*rchild;}bitree:voidlevel(bitiee*bt,intx)(if(bt!=O){lev++;if(bt-)ke尸=x)return;elseif(bt-)key)x)level(bt->lchild,x);elselevel(bt->rchild,x)；}}數(shù)據(jù)結(jié)構(gòu)試卷(八)數(shù)據(jù)結(jié)構(gòu)試卷(八)一、選擇題(30分)字符串的長度是指()0(B)(B)串中不同字母的個(gè)數(shù)(D)串中不同數(shù)字的個(gè)數(shù)(C)串中所含字符的個(gè)數(shù)建立一個(gè)長度為n的有序單鏈表的時(shí)間復(fù)雜度為()(A)0(n)(B)0(1)(C)0(n2)(D)0(logm)兩個(gè)字符串相等的充要條件是()。(A)兩個(gè)字符串的長度相等(B)兩個(gè)字符串中對應(yīng)位置上的字符相等(C)同時(shí)具備(A)和(B)兩個(gè)條件(D)以上答案都不對設(shè)某散列表的長度為100,散列函數(shù)H(k)二k%P,則P通常情況卞最好選擇()。(A)99(B)97(C)91(D)93在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為()。(A)0(n)(B)0(log：n)(C)0(nlog：n)(D)0(n")設(shè)一個(gè)順序有序表A[l:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過程中比較元素的順序?yàn)?A)A[1],A[2],A[3],A[4](B)A[1],A[14],A[7],A[4](C)A[7],A[3],A[5],A[4](D)A[7],A[5],A[3],A[4]設(shè)一棵完全二叉樹中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為()?(A)8(B)7(C)6(D)5設(shè)一棵三叉樹中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有()個(gè)度數(shù)為0的結(jié)點(diǎn).(A)5(B)6(A)5(B)6(C)7(D)8設(shè)無向圖G中的邊的集合E={(a,b),(a,e),(a,c)，(b,e),(e,d),(d,f),(f,c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為().(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc隊(duì)列是一種()的線性表。(A)先進(jìn)先出(B)先進(jìn)后出(C)只能插入(D)只能刪除二、判斷題(20分)如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。()設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為0(nlog：n).()分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找.()二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。()向二叉排序樹中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能人于該二叉樹的高度。()如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。()非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。()不論線性表采用順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為0(n)。()圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問過。()10?稀疏矩陣的壓縮存儲可以用一個(gè)三元組表來表示稀疏矩陣中的非0元素。()三、填空題(30分)設(shè)一組初始記錄關(guān)鍵字序列為(49,38,65,97,76,13,27,50),則以d二4為增量的一趟希爾排序結(jié)束后的結(jié)果為。下面程序段的功能是實(shí)現(xiàn)在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，請?jiān)谙聞澗€處填上正確的內(nèi)容。tvpedefstmctnode(hitdata；stmctnode*lchild;stiiictnode*rchild：}bitiee;voidbstiiisert(bitree*&t,intk)if(t==0){；t—〉data=k；t-)lchild=t->rchild=O;}elseif(t->data〉k)bstinseil(t->lcliild,k)；else；}設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語句序列：￡—>next二p—〉next;設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p二和head二(設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為11ink和rlink)o設(shè)某棵二叉樹的中序遍歷序列為ABCD,后序遍歷序列為BADC,則其前序遍歷序列為。完全二叉樹中第5層上最少有個(gè)結(jié)點(diǎn)，最多有個(gè)結(jié)點(diǎn).設(shè)有向圖中不存在有向邊〈VSVJ，則其對應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于設(shè)一組初始記錄關(guān)鍵字序列為(49,38,65,97,76,13,27,50),則第4趟直接選擇排序結(jié)束后的結(jié)果為■設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對應(yīng)的最小生成樹上有條邊。設(shè)有一組初始記錄關(guān)鍵字序列為(50,16,23,68,94,70,73),則將它們調(diào)整成初始堆只需把16與相互交換即可。四、算法設(shè)計(jì)題(20分)設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法.設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。一、選擇題1.C2.C3?C4?B5?B6.C7.B8?C9?A10.A二、判斷題1.對2.錯(cuò)3.對4.錯(cuò)5.錯(cuò)6.對7.對8?對9.對10.對三、填空題(49,13,27.50,76,38,65,97)t=(bitree*)malloc(sizeof(bitree)),bstinsert(t-)rchild,k)p->next=shead-)rlHik.p->lliiikCABDTOC\o"1-5"\h\z1,160(13,27,38,50,76,49.65,97)n—150四、算法設(shè)計(jì)題設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。voidcountnode(bitree*bt,int&count)if(bt!=0){count++;countnode(bt一>lchild5count)；countnode(bt->rcliild,count);}}設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法.tvpedefstmct{intveitexfm]:intedgefm][m];}gadjmatrix；tvpedefstmctnode1{intinfo;intadjvertex;stiuctnodel*nextarc;}gliiiklistnode;tvpedefstmctnod亡2{intvertexinfo；glinklistnode*fiistarc;}gluiklieadnode;voidadjmatnxtoadjlist(gadjmatrixgl[],gluiklieadnodeg2[]){intij；glinklistnode*p:for(i=0;i<=n—1；i++)g2[i]?flrstarc=O;for(i=0：1<=n—l;i++)for(j=0：j<=n—1；j++)if(gl.edge[i][j]=l){p=(gluiklistnode*)malloc(sizeof(gluiklistnode))：p—>adjvertex=j;p—〉nextarc=g[i]ofiistaic：g[i]ofiistaic=p：p=(glinklistnode*)nialloc(sizeof(glinklistnode));p—〉adjvertex=i;p->nextaic=g[j].fiistarc;g[j]ofirstarc=p;數(shù)據(jù)結(jié)構(gòu)試卷(九)一、選擇題(30分)下列程序段的時(shí)間復(fù)雜度為()。for(i=0；i(m：i++)for(j=0：j<t;j++)c[i][j]=0；for(i=0；i(m：i++)for(j=0；j<t：j++)for(k=0；k(n：k++)c[i][j]=c[訂|j]+a[i][k]*b[k][j]；(A)0(m*n*t)(B)0(m+n+t)(C)0(m+n*t)(D)0(m*t+n)設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動()個(gè)元素。(A)n-i(B)n+1—i(C)nT_i(D)i設(shè)F是由Tl、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B,Tl、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3,則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為()。(A)Nl-1(B)N2—1(C)N2+N3(D)N1+N3利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為()。(A)0(n)(B)0(nlog：n)(C)O(n')(D)0(log：n)設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為()。p—〉right=s；s—〉left=p;p—>iight->left=s；s-〉right=p->right；s->left=p;s->nglit=p-)right;p—>right=s;p—〉right-)left=s：p—>right=s；p->light-)left=s；s—〉left=p：s—〉right=p-)light；s->left=p：s->right=p—〉right;p—>right->left=s：p—〉riglit=s：下列各種排序算法中平均時(shí)間復(fù)雜度為0(n‘)是()。(A)快速排序(B)堆排序(C)歸并排序(D)冒泡排序設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個(gè)元素是n,則輸出序列中的第i個(gè)輸出元素是()。(A)n~i(B)n—l~i(C)n+1—i(D)不能確定8.設(shè)散列表中有m個(gè)存儲單元，散列函數(shù)H(key)=key%p，則p最好?選擇()。(A)小于等于m的最大奇數(shù)(B)小于等于m的最大素?cái)?shù)(0小于等于m的最人偶數(shù)(D)小于等于m的最大合數(shù)設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有()個(gè)。(A)4(B)5(C)6(D)7設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有()條邊。(A)n(n—1)/2(B)n(n-l)(C)n(n+1)/2(D)(n-l)/2設(shè)順序表的長度為n,則順序查找的平均比較次數(shù)為().(A)n(B)n/2(C)(n+l)/2(D)(n—1)/212。設(shè)有序表中的元素為(13,18,24,35,47,50,62),則在其中利用二分法查找值為24的元素需要經(jīng)過()次比較。(A)1(B)2(C)3(D)413。設(shè)順序線性表的長度為30,分成5塊，每塊6個(gè)元素，如呆采用分塊查找，則其平均查找長度為()。(A)6(B)11(C)5(D)6o5設(shè)有向無環(huán)圖G中的有向邊集合E={〈1,2>,<2,3>,<3,4),〈1,4)},則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖?).(A)1,2,3,4(B)2,3,4,1(C)1,4,2,3(D)1,2,4,3設(shè)有一組初始記錄關(guān)鍵字序列為(34,76,45,18,26,54,92),則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為()。(A)4(B)5(C)6(D)7二、填空題(30分)設(shè)指針P指向單鏈表中結(jié)點(diǎn)A，指針s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為：1)s—>next二；2)p—〉next二s：3)t=p—〉data：4)p—〉data二；5)s~>data二t：設(shè)某棵完全二叉樹中有100個(gè)結(jié)點(diǎn)，則該二叉樹中有個(gè)葉子結(jié)點(diǎn).設(shè)某順序循壞隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向隊(duì)尾元素的當(dāng)前位置，則該循壞隊(duì)列中最多存儲隊(duì)列元素。對一組初始關(guān)鍵字序列(40,50,95,20,15,70,60,45,10)進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為在整個(gè)排序過程中最多需要進(jìn)行趟排序才可以完成.TOC\o"1-5"\h\z在堆排序和快速排序中，如呆從平均情況卞排序的速度最快的角度來考慮應(yīng)最好選擇排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇排序.設(shè)一組初始記錄關(guān)鍵字序列為(20,12,42,31,18,14,28),則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是?設(shè)一棵二叉樹的中序遍歷序列為BDCA,后序遍歷序列為DBAC,則這棵二叉樹的前序序列為設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為0設(shè)一組記錄關(guān)鍵字序列為(80,70,33,65,24,56,48),則用篩選法建成的初始堆為設(shè)無向圖G(如右圖所示)，則其最小生成樹上所有邊的權(quán)值之和為。三、判斷題(20分)有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等.()對鏈表進(jìn)行插入和刪除操作時(shí)不必移動鏈表中結(jié)點(diǎn)。()子串“ABC”在主串“AABCABCD”中的位置為2.()若一個(gè)葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn).()希爾排序算法的時(shí)間復(fù)雜度為0(n')°()用鄰接矩陣作為圖的存儲結(jié)構(gòu)時(shí)，則其所占用的存儲空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。()中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。()入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。()順序表查找指的是在順序存儲結(jié)構(gòu)上進(jìn)行查找。()堆是完全二叉樹，完全二叉樹不一定是堆。()五、算法設(shè)計(jì)題(20分)設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。一、選擇題A2.A3.A4.C5.D6.D7.C8.B9.C10.A11.C12.C13.D14?A15.A二填空題1.p->next,s->