專升本十套-數據結構(試題及答案)

1、數據結構試卷(一)一、單選題(每題2分,共20分)棧與隊列得共同特點就是()。A、只允許在端點處插入與刪除元素B、都就是先進后出C、都就是先進先出D、沒有共同點用鏈接方式存儲得隊列,在進行插入運算時()、A、僅修改頭指針B、頭、尾指針都要修改C、僅修改尾指針D、頭、尾指針可能都要修改以下數據結構中哪一個就是非線性結構？()A、隊列B、棧C、線性表D、二叉4.設有一個二維數組Amn,假設A00存放位置在644(10),A22存放位置在676(0),每個元素占一個空間，問A33(10)存放在什么位置？腳注(0)表示用10進制表示。A.688B.678樹最適合用來表示()。A、有序數據元素C、元素之

2、間具有分支層次關系得數據二叉樹得第k層得結點數最多為()、A2k1B、2K+1C.692D.696B、無序數據元素D、元素之間無聯系得數據C、2K-1D、2k-i7.若有18個元素得有序表存放在一維數組A19中，第一個元素放A1中，現進行二分查找，則查找A3得比較序列得下標依次為()A、1,2,3。舊、9,5,2,3C、9,5,3沁D、9,4,2,3&對n個記錄得文件進行快速排序，所需要得輔助存儲空間大致為A、0(1)B、O(n)C、O(1ogn)D、0(n2)對于線性表(7,34,55,25,64,46,20,10)進行散列存儲時，若選用H(K)=K%9作為散列函數,則散列地址為1得元素有(

3、)個，Ao1B.2C.3D.4設有6個結點得無向圖,該圖至少應有()條邊才能確保就是一個連通圖。A、5B、6C、7D、8二、填空題(每空1分,共26分)通常從四個方面評價算法得質量：、與假定一個線性表為(12,23,74,55,63,40),若按Key%4條件進行劃分,使得同一余數得元素成為一個子表，則得到得四個子表分別為與。向一棵B_樹插入元素得過程中,若最終引起樹根結點得分裂，則新樹比原樹得高度在堆排序得過程中，對任一分支結點進行篩運算得時間復雜度為，整個堆排序過程得時間復雜度為。在快速排序、堆排序、歸并排序中，排序就是穩(wěn)定得.三、計算題(每題6分，共24分)在如下數組A中鏈接存儲了一個線

4、性表，表頭指針為A0、next，試寫出該線性表2.請畫出下圖得鄰接矩陣與鄰接表。63572041A01234datanext3.已知一個圖得頂點集3,4,5,6,7；E=(1,2)3,10,(2,3)6,(3,4)(3,5)12,(3,6)V與邊集E分別為：V=1,2,(1,3)5,(1,4)8,(2,5)15,9,(4,6)4,(4,7)20,(5,6)18,(6,7)25；用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到得各條邊。畫出向小根堆中加入數據4,2,5,8,3時，每加入一個數據后堆得變化。四、閱讀算法(每題7分洪14分)1.LinkListmynote(LinkLis

5、tL)/L就是不帶頭結點得單鏈表得頭指針if(L&L一next)q=L;L=Lnext;p=L；SI:while(p-next)P=Pnext;S2：pnext=q；qnext=NULL;returnL；請回答下列問題：(1)說明語句S1得功能；(2)說明語句組S2得功能；(3)設鏈表表示得線性表為fa”a2，,a，寫出算法執(zhí)行后得返回值所表示得線性表.2.voidABC(BTNode大BT)ifBTABC(BTleft);ABC(BTright);coutVVBTdata；該算法得功能就是：五、算法填空(共8分)二叉搜索樹得查找-遞歸算法:boolFind(BTreeNode*BST,Ele

6、mType&item)if(BST=NULL)returnfalse;/查找失敗elseif(item=BSTdata)item=BST-data;/查找成功return.；elseif(itemBSTdata)returnFind(,item)；elsereturnFind(,item)；/if六、編寫算法(共8分)統(tǒng)計出單鏈表HL中結點得值等于給定值X得結點數。intCountX(LNode*HL,ElemTypex)數據結構試卷(二)一、選擇題(24分)1.下面關于線性表得敘述錯誤得就是()。(A)線性表采用順序存儲必須占用一片連續(xù)得存儲空間。線性表采用鏈式存儲不必占用一片連續(xù)得存儲空間

7、線性表采用鏈式存儲便于插入與刪除操作得實現線性表采用順序存儲便于插入與刪除操作得實現2。設哈夫曼樹中得葉子結點總數為m,若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有()個空指針域。2m1(B)2m(C)2m+1。(D)4m設順序循環(huán)隊列Q0:M1得頭指針與尾指針分別為F與R,頭指針F總就是指向隊頭元素得前一位置，尾指針R總就是指向隊尾元素得當前位置，則該循環(huán)隊列中得元素個數為()。RF(B)FR。(C)(RF+M)%M。(D)(F-R+M)%M4.設某棵二叉樹得中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹得到序列為()。(A)BADC(B)BCDA(C)CDABD)CB

8、DA5。設某完全無向圖中有n個頂點，則該完全無向圖中有()條邊。(A)n(n1)/2。(B)n(n1)。(C)n2*D)m16設某棵二叉樹中有2000個結點，則該二叉樹得最小高度為()(A)9(B)10o(C)11(D)127設某有向圖中有n個頂點，則該有向圖對應得鄰接表中有()個表頭結點.。(A)n-(B)no(C)n+lD)2n18。設一組初始記錄關鍵字序列(5,2,6，3，8),以第一個記錄關鍵字5為基準進行一趟快速排序得結果為()。A)2，3，5，8，6。3，2，5,8，6。(03,2,5,6,8D)2,3,6,5,8二、填空題(24分)為了能有效地應用HASH查找技術，必須解決得兩個

9、問題就是與。下面程序段得功能實現數據x進棧，要求在下劃線處填上正確得語句.typedefstructints100；inttop;sqstack；voidpush(sqstack&stack,intx)if(stack、top=ml)printf(“overf1ow);TOC o 1-5 h zelse；中序遍歷二叉排序樹所得到得序列就是列(填有序或無序)?？焖倥判虻米顗臅r間復雜度為,平均時間復雜度為.設某棵二叉樹中度數為0得結點數為N。，度數為1得結點數為兒，則該二叉樹中度數為2得結點數為；若采用二叉鏈表作為該二叉樹得存儲結構，則該二叉樹中共有個空指針域。設某無向圖中頂點數與邊數分別為n與e

10、,所有頂點得度數之與為小，則。=.設一組初始記錄關鍵字序列為(55,63，44,38,75,80,31,56),則利用篩選法建立得初始堆為。已知一有向圖得鄰接表存儲結構如下：從頂點1出發(fā)，DFS遍歷得輸出序列就是,BFS遍歷得輸出序列就三、應用題(36分)設一組初始記錄關鍵字序列為(45,80,48,40,22,78)，則分別給出第4趟簡單選擇排序與第4趟直接插入排序后得結果。設指針變量p指向雙向鏈表中結點A,指針變量q指向被插入結點B,要求給出在結點A得后面插入結點B得操作序列(設雙向鏈表中結點得兩個指針域分別為llink與rlink)。設一組有序得記錄關鍵字序列為(13,18,24,35,

11、47,50,62,83,90),查找方法用二分查找,要求計算出查找關鍵字62時得比較次數并計算出查找成功時得平均查找長度.設一棵樹T中邊得集合為(A,B),(A,C),(A,D),(B,E),(C,F),(C,G),要求用孩子兄弟表示法(二叉鏈表)表示出該樹得存儲結構并將該樹轉化成對應得二叉樹。設有無向圖G,要求給出用普里姆算法構造最小生成樹所走過得邊得集合設有一組初始記錄關鍵字為(45，80，48,40，22,78),要求構造一棵二叉排序樹并給出構造過程。四、算法設計題(16分)設有一組初始記錄關鍵字序列(K,K,，K),要求設計一個算法能夠在0(n)得時12n間復雜度內將線性表劃分成兩部分

12、，其中左半部分得每個關鍵字均小于Ki,右半部分得i每個關鍵字均大于等于K。i設有兩個集合A與集合B,要求設計生成集合C=AHB得算法，其中集合A、B與C用鏈式存儲結構表示。數據結構試卷(三)一、選擇題(每題1分,共20分)1。設某數據結構得二元組形式表示為A=(D,R),D=01,02,03,04,05,06,07,08,09,R=r,r=,V01,03,01,04,02,05，,03,07,03,08,03,09,則數據結構A就是()。(A)線性結構(B)樹型結構C)物理結構(D)圖型結構2下面程序得時間復雜為()for(i=1,s=0；iv=n；i+)t=1；for(j=l；jv=i；j+

13、)t=t*j；s=s+t;(A)0(n)。(B)O(n2)(C)0(e)。(D)0(nJ3設指針變量P指向單鏈表中結點A,若刪除單鏈表中結點A,則需要修改指針得操作序列為().。(A)q=pnext;p-data二qdata;pnext=q-next;free(q)；q=pnext；q-data二p-data；pnext=qnext；free(q)；*C)q=pnext；pnext=q-next；free(q);(D)q=pnext;p-data二qdata;free(q);4。設有n個待排序得記錄關鍵字，則在堆排序中需要()個輔助記錄單元。A)1B)n(C)nlogn(D)n225。設一組初

14、始關鍵字記錄關鍵字為(20,15,14,18,21,36,40,10)，則以20為基準記錄得一趟快速排序結束后得結果為()。10,15,14,18,20,36,40,2110,15,14,18,20,40,36,2110,15,14,20,18,40,36,2l。(D)15,10,14,18,20,36,40,216。設二叉排序樹中有n個結點，則在二叉排序樹得平均平均查找長度為().(A)0(1)(1。叮)(C)(D)OS)7。設無向圖G中有n個頂點e條邊，則其對應得鄰接表中得表頭結點與表結點得個數分別為()。A)n,e(B)e,n(C)2n,e(D)n,2e8。設某強連通圖中有n個頂點，則該

15、強連通圖中至少有()條邊。(A)n(n-1)b(B)n+1(C)n(D)n(n+1)9。設有5000個待排序得記錄關鍵字,如果需要用最快得方法選出其中最小得10個記錄關鍵字,則用下列()方法可以達到此目得。b(A)快速排序(B)堆排序b(C)歸并排序。(D)插入排序10。下列四種排序中()得空間復雜度最大.(A)插入排序b(B)冒泡排序(C)堆排序(D)歸并排序二、填空殖(每空1分共20分)數據得物理結構主要包括與兩種情況.設一棵完全二叉樹中有500個結點，則該二叉樹得深度為；若用二叉鏈表作為該完全二叉樹得存儲結構，則共有個空指針域。設輸入序列為1、2、3,則經過棧得作用后可以得到種不同得輸出

16、序列。設有向圖G用鄰接矩陣Ann作為存儲結構，則該鄰接矩陣中第i行上所有元素之與等于頂點i得,第i列上所有元素之與等于頂點i得。設哈夫曼樹中共有n個結點，則該哈夫曼樹中有個度數為1得結點。設有向圖G中有n個頂點e條有向邊，所有得頂點入度數之與為d,則e與d得關系為遍歷二叉排序樹中得結點可以得到一個遞增得關鍵字序列(填先序、中序或后序)。&設查找表中有100個元素，如果用二分法查找方法查找數據元素X,則最多需要比較.次就可以斷定數據元素X就是否在查找表中.不論就是順序存儲結構得棧還就是鏈式存儲結構得棧，其入棧與出棧操作得時間復雜度TOC o 1-5 h z均為。設有n個結點得完全二叉樹，如果按照

17、從自上到下、從左到右從1開始順序編號，則第i個結點得雙親結點編號為，右孩子結點得編號為。設一組初始記錄關鍵字為(72,73,71,23,94,16,5),則以記錄關鍵字72為基準得一趟快速排序結果為。設有向圖G中有向邊得集合E=仃，2，V2,3,V1,4,4,2,V4,3,則該圖得一種拓撲序列為.下列算法實現在順序散列表中查找值為x得關鍵字，請在下劃線處填上正確得語句。struetrecordintkey;intothers;；inthashsqsearch(structrecordhashtable,intk)inti,j；j=i=k%p；while(hashtablej、key!=k&ha

18、shtab1ejflag!=0)j=()%m；if(i=j)return(1)；if()return(j);e1sereturn(1)；下列算法實現在二叉排序樹上查找關鍵值k,請在下劃線處填上正確得語句。typedefstructnodeintkey;struetnode*lchild；structnoderchild;bitree;bitreebstsearch(bitree*t,intk)if(t=0)return(0)；elsewhile(t!=0)if(tkey=k)；elseif(tkey)k)t=tlchild；else;三、計算題(每題10分,共30分)1、已知二叉樹得前序遍歷序

19、列就是AEFBGCDHIKJ，中序遍歷序列就是EFAGBCHKIJD,畫出此二叉樹，并畫出它得后序線索二叉樹。2。已知待散列得線性表為(36,15,40,63,22),散列用得一維地址空間為0、6,假定選用得散列函數就是H(K)=Kmod7,若發(fā)生沖突采用線性探查法處理，試：計算出每一個元素得散列地址并在下圖中填寫出散列表：0123456求出在查找每一個元素概率相等情況下得平均查找長度。3。已知序列(10,18,4,3,6,12,1,9,188)請用快速排序寫出每一趟排序得結果。四、算法設計題(每題15分，共30分)1設計在單鏈表中刪除值相同得多余結點得算法。2設計一個求結點x在二叉樹中得雙親

20、結點算法。數據結構試卷(四)一、選擇題(每題1分共20分)設一維數組中有n個數組元素，則讀取第i個數組元素得平均時間復雜度為()。TOC o 1-5 h zO(n)B)O(nlon)(C)0(1)(D)0(e)2。設一棵二叉樹得深度為k,則該二叉樹中最多有()個結點。(A)2k-h(B)2“(C)2i(D)2kl3設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點得入度之與為()。(A)n(B)e。(C)2n(D)2e4。在二叉排序樹中插入一個結點得時間復雜度為()。(A)0(1)(B)0(n)o(C)0(logn)o(D)O(n2)5。設某有向圖得鄰接表中有n個表頭結點與m個表結點，則該圖中

21、有()條有向邊.(A)n。(B)n1(C)m(D)m16設一組初始記錄關鍵字序列為(345,253,674,924,627),則用基數排序需要進行()趟得分配與回收才能使得初始關鍵字序列變成有序序列。3(B)4(C)5(D)8設用鏈表作為棧得存儲結構則退棧操作().(必須判別棧就是否為滿(B)必須判別棧就是否為空判別棧元素得類型(D)對棧不作任何判別8。下列四種排序中()得空間復雜度最大。(A)快速排序(B)冒泡排序。(C)希爾排序。(D)堆設某二叉樹中度數為0得結點數為N0,度數為1得結點數為叫,度數為2得結點數為N2,則下列等式成立得就是()。(A)N=N+1B)N=N+N*C)N=N+1

22、。(D)N=2N+l010l2020110、設有序順序表中有n個數據元素，則利用二分查找法查找數據元素X得最多比較次數不超過()。A)logn+1(B)logn1(C)logn(D)log(n+1)2222二、填空題(每空1分共20分)1設有n個無序得記錄關鍵字,則直接插入排序得時間復雜度為,快速排序得平均時間復雜度為。設指針變量p指向雙向循環(huán)鏈表中得結點X,則刪除結點X需要執(zhí)行得語句序列為(設結點中得兩個指針域分別為llink與rlink)。根據初始關鍵字序列(19,22,01,38,10)建立得二叉排序樹得高度為深度為k得完全二叉樹中最少有個結點.設初始記錄關鍵字序列為(K,K,K),則用

23、篩選法思想建堆必須從第個元12n素開始進行篩選.設哈夫曼樹中共有99個結點，則該樹中有個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有個空指針域。設有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲個隊列元素；當前實際存儲個隊列元素(設頭指針F指向當前隊頭元素得前一個位置,尾指針指向當前隊尾元素得位置)。設順序線性表中有n個數據元素，則第i個位置上插入一個數據元素需要移動表中個數據元素；刪除第i個位置上得數據元素需要移動表中個元素。設一組初始記錄關鍵字序列為(20,18,22,16,30,19),則以20為中軸得一趟快速排序結果為。設一組初始記錄關鍵字序列為(20,18,22,1

24、6,30,19),則根據這些初始關鍵字序列建TOC o 1-5 h z成得初始堆為.設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖得存儲結構，則頂點i與頂點j互為鄰接點得條件就是。設無向圖對應得鄰接矩陣為A,則A中第i上非0元素得個數第i列上非0元素得個數(填等于,大于或小于)。13設前序遍歷某二叉樹得序列為ABCD，中序遍歷該二叉樹得序列為BADC,則后序遍歷該二叉樹得序列為。14設散列函數H(k)=kmodp,解決沖突得方法為鏈地址法。要求在下列算法劃線處填上正確得語句完成在散列表hashtalbe中查找關鍵字值等于k得結點，成功時返回指向關鍵字得指針,不成功時返回標志0。typedefs

25、tructnodeintkey;structnode大next;lklist；voidcreatelkhash(lklist大hashtable)inti,k;lklists;for(i=0;im；i+)；for(i=0；inext=hashtablek；三、計算題(每題10分,共30分)1、畫出廣義表LS=(),(e),(a,(b,c,d)得頭尾鏈表存儲結構。2、下圖所示得森林：求樹(a)得先根序列與后根序列；求森林先序序列與中序序列；將此森林轉換為相應得二叉樹;3、設散列表得地址范圍就是0、9,散列函數為H(key)=(key2+2)MOD9,并采用鏈表處理沖突，請畫出元素7、4、5、3、

26、6、2、8、9依次插入散列表得存儲結構。四、算法設計題(每題10分,共30分)1設單鏈表中有僅三類字符得數據元素(大寫字母、數字與其它字符),要求利用原單鏈表中結點空間設計出三個單鏈表得算法,使每個單鏈表只包含同類字符.設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹得算法。在鏈式存儲結構上建立一棵二叉排序樹。數據結構試卷(五)一、選擇題(20分)1。數據得最小單位就是()。(A)數據項(B)數據類型(C)數據元素(D)數據變量設一組初始記錄關鍵字序列為(50,40,95,20,15,70,60,45),則以增量d=4得一趟希爾排序結束后前4條記錄關鍵字為()。(A)40,50,20,95。(

27、B)15,40,60,20(C)15,20,40,45(D)45,40,15,203。設一組初始記錄關鍵字序列為(25,50,15,35,80,85,20,40,36,70),其中含有5個長度為2得有序子表,則用歸并排序得方法對該記錄關鍵字序列進行一趟歸并后得結果為()。(A)15,25,35,50,20,40,80,85,36,70(B)15,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。函數substr(“DATASTRUCTURE”，5,9)得返回值為()。(A)

28、“STRUCTURE”。(B)“DATA。(C)“ASTRUCTUR”(D)“DATASTRUCTURE”5。設一個有序得單鏈表中有n個結點，現要求插入一個新結點后使得單鏈表仍然保持有序,則該操作得時間復雜度為()。(A)O(logn)(B)O(1)(C)0(n2)(D)O(n)6。設一棵m叉樹中度數為0得結點數為N0,度數為1得結點數為叫,度數為m得結點數為Nm,則=()TOC o 1-5 h z(A)N+N+Nm(B)l+N+2N+3N+(m122341)Nm。(C)N+2N+3N+(m-1)Nm(D)2N+3N+(m+1)Nm234127。設有序表中有1000個元素，則用二分查找查找元素

29、X最多需要比較()次。(A)25(B)10。(C)7。(D)18。設連通圖G中得邊集E=(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷得頂點序列為().A)abedfcB)acfebd(C)aebdfc。(D)aedfcb設輸入序列就是1、2、3、n,經過棧得作用后輸出序列得第一個元素就是n,則輸出序列中第i個輸出元素就是()。(A)ni。(B)n-1-iC)n+1i。(D)不能確定10設一組初始記錄關鍵字序列為(45,80,55,40,42,85),則以第一個記錄關鍵字45為基準而得到一趟快速排序得結果就是()。(A

30、)40,42,45,55,80,83。(B)42,40,45,80,85,88。(042,40,45,55,80,85(D)42,40,45,85,55,80二、填空題(共20分)設有一個順序共享棧S0：n1,其中第一個棧項指針top1得初值為-1，第二個棧頂指針top2得初值為n,則判斷共享棧滿得條件就是.在圖得鄰接表中用順序存儲結構存儲表頭結點得優(yōu)點就是。設有一個n階得下三角矩陣A,如果按照行得順序將下三角矩陣中得元素(包括對角線上元素)存放在n(n+1)個連續(xù)得存儲單元中，則Aij與A00之間有個數據元素。棧得插入與刪除只能在棧得棧頂進行，后進棧得元素必定先出棧，所以又把棧稱為表；隊列得

31、插入與刪除運算分別在隊列得兩端進行，先進隊列得元素必定先出隊列，所以又把隊列稱為表。設一棵完全二叉樹得順序存儲結構中存儲數據元素為ABCDEF，則該二叉樹得前序遍歷序列為,中序遍歷序列為,后序遍歷序列為設一棵完全二叉樹有128個結點，則該完全二叉樹得深度為,有個葉子結點.設有向圖G得存儲結構用鄰接矩陣A來表示，則A中第i行中所有非零元素個數之與等TOC o 1-5 h z于頂點i得,第i列中所有非零元素個數之與等于頂點i得.&設一組初始記錄關鍵字序列(k,k,k)就是堆，則對i=1,2,，n/2而言12n滿足得條件為。下面程序段得功能就是實現冒泡排序算法，請在下劃線處填上正確得語句。voidb

32、ubble(intrn) HYPERLINK l bookmark38 o Current Document for(i=l；i=n1;i+) HYPERLINK l bookmark42 o Current Document for(exchange=0,j=0；j；j+)if(rjrj+1)temp=rj+1;rj=temp；exchange=1；if(exchange=0)return；下面程序段得功能就是實現二分查找算法，請在下劃線處填上正確得語句。structrecordintkey;intothers；;intbisearch(structrecordr,intk)intlow=0

33、，mid，high=n-1;while(1owV=high)if(rmid、key=k)return(mid+1)；elseif()high=mid-1；elselow=mid+1;return(0);三、應用題(32分)設某棵二叉樹得中序遍歷序列為DBEAC,前序遍歷序列為ABDEC,要求給出該二叉樹得得后序遍歷序列。設無向圖G(如右圖所示)，給出該圖得最小生成樹上邊得集合并計算最小生成樹各邊上得權值之與。設一組初始記錄關鍵字序列為(15,17,18,22,35,51,60),要求計算出成功查找時得平均查找長度。設散列表得長度為8,散列函數H(k)=kmod7,初始記錄關鍵字序列為(25,3

34、1,8,27，13，68)，要求分別計算出用線性探測法與鏈地址法作為解決沖突方法得平均查找長度。四、算法設計題(28分)1設計判斷兩個二叉樹就是否相同得算法.2設計兩個有序單鏈表得合并排序算法.數據結構試卷(六)一、選擇題(30分)1。設一組權值集合W=2,3,4,5,6,則由該權值集合構造得哈夫曼樹中帶權路徑長度之與為().(A)20(B)30。(C)40(D)452。執(zhí)行一趟快速排序能夠得到得序列就是()。A)41,12,34,45,275572,6345,34,12,415572,63,2763,12,34,45,275541,7212,27,45,415534,63,723。設一條單鏈

35、表得頭指針變量為head且該鏈表沒有頭結點，則其判空條件就是()(A)head=O。(B)head-next=O(C)headnext二二head。(D)head!=O4時間復雜度不受數據初始狀態(tài)影響而恒為0(nlog2n)得就是()。(A)堆排序(B)冒泡排序(C)希爾排序。(D)快速排序5設二叉樹得先序遍歷序列與后序遍歷序列正好相反,則該二叉樹滿足得條件就是()。(A)空或只有一個結點(B)高度等于其結點數(C)任一結點無左孩子(D)任一結點無右孩子6。一趟排序結束后不一定能夠選出一個元素放在其最終位置上得就是()。3)堆排序(B)冒泡排序(C)快速排序(D)希爾排序7設某棵三叉樹中有40

36、個結點，則該三叉樹得最小高度為()。(A)3o(B)4C)5。(D)6順序查找不論在順序線性表中還就是在鏈式線性表中得時間復雜度為().(A)0(n)。(B)0(n2)(C)0(ni/2)。(D)0(1og2n)9。二路歸并排序得時間復雜度為()。(A)0(n)。(B)0(n2)(C)0(nlogn)(D)0(1og2n)10、深度為k得完全叉樹中最少有()個結點.。(A)2k-i1(B)2ki。(C)2ki+1D)2k111、設指針變量front表示鏈式隊列得隊頭指針，指針變量rear表示鏈式隊列得隊尾指針，指針變量s指向將要入隊列得結點X,則入隊列得操作序列為()(A)frontnext=

37、s；front二s；(B)snext=rear;rear=s；o(C)rear-next二s；rear二s;。(D)snext二front;front二s;12、設某無向圖中有n個頂點e條邊，則建立該圖鄰接表得時間復雜度為()A)0(n+e)(B)0(n2)(C)0(ne)(D)O(n3)13、設某哈夫曼樹中有199個結點,則該哈夫曼樹中有()個葉子結點。(A)99(B)100。(C)101(D)10214、設二叉排序樹上有n個結點，則在二叉排序樹上查找結點得平均時間復雜度為()(A)0(n)。(B)0(n2)o(C)0(n1ogn)(D)0(1ogn)15、設用鄰接矩陣A表示有向圖G得存儲結

38、構,，則有向圖G中頂點i得入度為()A)第i行非0元素得個數之與(B)第i列非0元素得個數之與(C)第i行0元素得個數之與(D)第i列0元素得個數之與二、判斷題(20分)1調用一次深度優(yōu)先遍歷可以訪問到圖中得所有頂點。()2分塊查找得平均查找長度不僅與索引表得長度有關，而且與塊得長度有關。()冒泡排序在初始關鍵字序列為逆序得情況下執(zhí)行得交換次數最多。()4。滿二叉樹一定就是完全二叉樹，完全二叉樹不一定就是滿二叉樹()5。設一棵二叉樹得先序序列與后序序列，則能夠唯一確定出該二叉樹得形狀.()6。層次遍歷初始堆可以得到一個有序得序列。()7。設一棵樹T可以轉化成二叉樹BT,則二叉樹BT中一定沒有右

39、子樹。()8線性表得順序存儲結構比鏈式存儲結構更好。()9中序遍歷二叉排序樹可以得到一個有序得序列。()10、快速排序就是排序算法中平均性能最好得一種排序。()三、填空題(30分)for(i=l,t=1,s=0；i二n;i+)t=t*i；s=s+1;得時間復雜度為2。設指針變量p指向單鏈表中結點A,指針變量s指向被插入得新結點X,則進行插入操作得語句序列為(設結點得指針域為next)。3。設有向圖G得二元組形式表示為G=(D,R),D=1,2,3,4,5,R=r,r=vl,2,V4,5,1,3，,3,5,則給出該圖得一種拓撲排序序列4。設無向圖G中有n個頂點，則該無向圖中每個頂點得度數最多就是

40、。設二叉樹中度數為0得結點數為50，度數為1得結點數為30,則該二叉樹中總共有個結點數。6設F與R分別表示順序循環(huán)隊列得頭指針與尾指針，則判斷該循環(huán)隊列為空得條件為_7設二叉樹中結點得兩個指針域分別為lchild與child，則判斷指針變量p所指向得結點為葉子結點得條件就是TOC o 1-5 h z&簡單選擇排序與直接插入排序算法得平均時間復雜度為。9快速排序算法得空間復雜度平均情況下為，最壞得情況下為。10、散列表中解決沖突得兩種方法就是與.四、算法設計題(20分)1設計在順序有序表中實現二分查找得算法。設計判斷二叉樹就是否為二叉排序樹得算法。在鏈式存儲結構上設計直接插入排序算法數據結構試卷

41、(七)一、選擇題(30分)1設某無向圖有n個頂點，貝y該無向圖得鄰接表中有()個表頭結點。(A)2n(B)n(C)n/2。(D)n(n1)設無向圖G中有n個頂點，則該無向圖得最小生成樹上有()條邊.(A)n(B)n-1。(C)2nD)2n-1設一組初始記錄關鍵字序列為(60,80,55，40，42,85),則以第一個關鍵字45為基準而得到得一趟快速排序結果就是()。(A)40,42,60,55,80,85(B)42,45,55,60,85,80(C)42,40,55,60,80,85(D)42,40,60,85,55,80()二叉排序樹可以得到一個從小到大得有序序列。(A)先序遍歷*B)中序遍

42、歷。(C)后序遍歷。(D)層次遍歷設按照從上到下、從左到右得順序從1開始對完全二叉樹進行順序編號，則編號為i結點得左孩子結點得編號為().(A)2i+l(B)2h(C)i/2(D)2il6。程序段s=i=O；doi=i+1；s=s+i;while(iv=n);得時間復雜度為()。(A)O(n)*B)O(nlogn)*C)O(n2)(D)0(m/2)7設帶有頭結點得單向循環(huán)鏈表得頭指針變量為head,則其判空條件就是()。(A)head=0“(B)headnext=0(C)headnext二二head。(D)head!=08。設某棵二叉樹得高度為10,則該二叉樹上葉子結點最多有().(A)20(

43、B)256。(C)512D)10249.設一組初始記錄關鍵字序列為(13,18,24,35,47,50,62,83,90,115,134),則利用二分法查找關鍵字90需要比較得關鍵字個數為()。A)1B)2(C)3。(D)410、設指針變量top指向當前鏈式棧得棧頂，則刪除棧頂元素得操作序列為()。(A)top二top+1；(B)top二top1;*C)topnext=top；(D)top=top-next;二、判斷題(20分)1。不論就是入隊列操作還就是入棧操作,在順序存儲結構上都需要考慮“溢出”情況。()2當向二叉排序樹中插入一個結點,則該結點一定成為葉子結點。()3設某堆中有n個結點，則

44、在該堆中插入一個新結點得時間復雜度為0(log2n).()4完全二叉樹中得葉子結點只可能在最后兩層中出現。()哈夫曼樹中沒有度數為1得結點.()對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中得所有頂點。()先序遍歷一棵二叉排序樹得到得結點序列不一定就是有序得序列。()8由樹轉化成二叉樹,該二叉樹得右子樹不一定為空。()9。線性表中得所有元素都有一個前驅元素與后繼元素。()10。帶權無向圖得最小生成樹就是唯一得。()三、填空題(30分)設指針變量P指向雙向鏈表中得結點A,指針變量s指向被插入得結點X,則在結點A得后面插入結點X得操作序列為=p；s-right二pright;=s；prightleft=s;(設結點中得兩個指針域分別為left與right)。設完全有向圖中有n個頂點，則該完全有向圖中共有條有向條；設