專升本十套-數(shù)據(jù)結(jié)構(gòu)(試題及答案)

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

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

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

4、性表，表頭指針為A0、next，試寫出該線性表2.請(qǐng)畫(huà)出下圖得鄰接矩陣與鄰接表。63572041A01234datanext3.已知一個(gè)圖得頂點(diǎn)集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；用克魯斯卡爾算法得到最小生成樹(shù)，試寫出在最小生成樹(shù)中依次得到得各條邊。畫(huà)出向小根堆中加入數(shù)據(jù)4,2,5,8,3時(shí)，每加入一個(gè)數(shù)據(jù)后堆得變化。四、閱讀算法(每題7分洪14分)1.LinkListmynote(LinkLis

5、tL)/L就是不帶頭結(jié)點(diǎn)得單鏈表得頭指針if(L&L一next)q=L;L=Lnext;p=L；SI:while(p-next)P=Pnext;S2：pnext=q；qnext=NULL;returnL；請(qǐng)回答下列問(wèn)題：(1)說(shuō)明語(yǔ)句S1得功能；(2)說(shuō)明語(yǔ)句組S2得功能；(3)設(shè)鏈表表示得線性表為fa”a2，,a，寫出算法執(zhí)行后得返回值所表示得線性表.2.voidABC(BTNode大BT)ifBTABC(BTleft);ABC(BTright);coutVVBTdata；該算法得功能就是：五、算法填空(共8分)二叉搜索樹(shù)得查找-遞歸算法: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)計(jì)出單鏈表HL中結(jié)點(diǎn)得值等于給定值X得結(jié)點(diǎn)數(shù)。intCountX(LNode*HL,ElemTypex)數(shù)據(jù)結(jié)構(gòu)試卷(二)一、選擇題(24分)1.下面關(guān)于線性表得敘述錯(cuò)誤得就是()。(A)線性表采用順序存儲(chǔ)必須占用一片連續(xù)得存儲(chǔ)空間。線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)得存儲(chǔ)空間

7、線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入與刪除操作得實(shí)現(xiàn)線性表采用順序存儲(chǔ)便于插入與刪除操作得實(shí)現(xiàn)2。設(shè)哈夫曼樹(shù)中得葉子結(jié)點(diǎn)總數(shù)為m,若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有()個(gè)空指針域。2m1(B)2m(C)2m+1。(D)4m設(shè)順序循環(huán)隊(duì)列Q0:M1得頭指針與尾指針?lè)謩e為F與R,頭指針F總就是指向隊(duì)頭元素得前一位置，尾指針R總就是指向隊(duì)尾元素得當(dāng)前位置，則該循環(huán)隊(duì)列中得元素個(gè)數(shù)為()。RF(B)FR。(C)(RF+M)%M。(D)(F-R+M)%M4.設(shè)某棵二叉樹(shù)得中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹(shù)得到序列為()。(A)BADC(B)BCDA(C)CDABD)CB

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

9、問(wèn)題就是與。下面程序段得功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確得語(yǔ)句.typedefstructints100；inttop;sqstack；voidpush(sqstack&stack,intx)if(stack、top=ml)printf(“overf1ow);TOC o 1-5 h zelse；中序遍歷二叉排序樹(shù)所得到得序列就是列(填有序或無(wú)序)。快速排序得最壞時(shí)間復(fù)雜度為,平均時(shí)間復(fù)雜度為.設(shè)某棵二叉樹(shù)中度數(shù)為0得結(jié)點(diǎn)數(shù)為N。，度數(shù)為1得結(jié)點(diǎn)數(shù)為兒，則該二叉樹(shù)中度數(shù)為2得結(jié)點(diǎn)數(shù)為；若采用二叉鏈表作為該二叉樹(shù)得存儲(chǔ)結(jié)構(gòu)，則該二叉樹(shù)中共有個(gè)空指針域。設(shè)某無(wú)向圖中頂點(diǎn)數(shù)與邊數(shù)分別為n與e

10、,所有頂點(diǎn)得度數(shù)之與為小，則。=.設(shè)一組初始記錄關(guān)鍵字序列為(55,63，44,38,75,80,31,56),則利用篩選法建立得初始堆為。已知一有向圖得鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)，DFS遍歷得輸出序列就是,BFS遍歷得輸出序列就三、應(yīng)用題(36分)設(shè)一組初始記錄關(guān)鍵字序列為(45,80,48,40,22,78)，則分別給出第4趟簡(jiǎn)單選擇排序與第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,

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

12、，其中左半部分得每個(gè)關(guān)鍵字均小于Ki,右半部分得i每個(gè)關(guān)鍵字均大于等于K。i設(shè)有兩個(gè)集合A與集合B,要求設(shè)計(jì)生成集合C=AHB得算法，其中集合A、B與C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷(三)一、選擇題(每題1分,共20分)1。設(shè)某數(shù)據(jù)結(jié)構(gòu)得二元組形式表示為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,則數(shù)據(jù)結(jié)構(gòu)A就是()。(A)線性結(jié)構(gòu)(B)樹(shù)型結(jié)構(gòu)C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu)2下面程序得時(shí)間復(fù)雜為()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設(shè)指針變量P指向單鏈表中結(jié)點(diǎn)A,若刪除單鏈表中結(jié)點(diǎn)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。設(shè)有n個(gè)待排序得記錄關(guān)鍵字，則在堆排序中需要()個(gè)輔助記錄單元。A)1B)n(C)nlogn(D)n225。設(shè)一組初

14、始關(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,18,20,40,36,2110,15,14,20,18,40,36,2l。(D)15,10,14,18,20,36,40,216。設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)得平均平均查找長(zhǎng)度為().(A)0(1)(1。叮)(C)(D)OS)7。設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)得鄰接表中得表頭結(jié)點(diǎn)與表結(jié)點(diǎn)得個(gè)數(shù)分別為()。A)n,e(B)e,n(C)2n,e(D)n,2e8。設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該

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

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

17、從自上到下、從左到右從1開(kāi)始順序編號(hào)，則第i個(gè)結(jié)點(diǎn)得雙親結(jié)點(diǎn)編號(hào)為，右孩子結(jié)點(diǎn)得編號(hào)為。設(shè)一組初始記錄關(guān)鍵字為(72,73,71,23,94,16,5),則以記錄關(guān)鍵字72為基準(zhǔn)得一趟快速排序結(jié)果為。設(shè)有向圖G中有向邊得集合E=仃，2，V2,3,V1,4,4,2,V4,3,則該圖得一種拓?fù)湫蛄袨?下列算法實(shí)現(xiàn)在順序散列表中查找值為x得關(guān)鍵字，請(qǐng)?jiān)谙聞澗€處填上正確得語(yǔ)句。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)；下列算法實(shí)現(xiàn)在二叉排序樹(shù)上查找關(guān)鍵值k,請(qǐng)?jiān)谙聞澗€處填上正確得語(yǔ)句。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;三、計(jì)算題(每題10分,共30分)1、已知二叉樹(shù)得前序遍歷序

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

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

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

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

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

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

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

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

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

28、“STRUCTURE”。(B)“DATA。(C)“ASTRUCTUR”(D)“DATASTRUCTURE”5。設(shè)一個(gè)有序得單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序,則該操作得時(shí)間復(fù)雜度為()。(A)O(logn)(B)O(1)(C)0(n2)(D)O(n)6。設(shè)一棵m叉樹(shù)中度數(shù)為0得結(jié)點(diǎn)數(shù)為N0,度數(shù)為1得結(jié)點(diǎn)數(shù)為叫,度數(shù)為m得結(jié)點(diǎn)數(shù)為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。設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素

29、X最多需要比較()次。(A)25(B)10。(C)7。(D)18。設(shè)連通圖G中得邊集E=(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷得頂點(diǎn)序列為().A)abedfcB)acfebd(C)aebdfc。(D)aedfcb設(shè)輸入序列就是1、2、3、n,經(jīng)過(guò)棧得作用后輸出序列得第一個(gè)元素就是n,則輸出序列中第i個(gè)輸出元素就是()。(A)ni。(B)n-1-iC)n+1i。(D)不能確定10設(shè)一組初始記錄關(guān)鍵字序列為(45,80,55,40,42,85),則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序得結(jié)果就是()。(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分)設(shè)有一個(gè)順序共享?xiàng)0：n1,其中第一個(gè)棧項(xiàng)指針top1得初值為-1，第二個(gè)棧頂指針top2得初值為n,則判斷共享?xiàng)M得條件就是.在圖得鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)得優(yōu)點(diǎn)就是。設(shè)有一個(gè)n階得下三角矩陣A,如果按照行得順序?qū)⑾氯蔷仃囍械迷?包括對(duì)角線上元素)存放在n(n+1)個(gè)連續(xù)得存儲(chǔ)單元中，則Aij與A00之間有個(gè)數(shù)據(jù)元素。棧得插入與刪除只能在棧得棧頂進(jìn)行，后進(jìn)棧得元素必定先出棧，所以又把棧稱為表；隊(duì)列得

31、插入與刪除運(yùn)算分別在隊(duì)列得兩端進(jìn)行，先進(jìn)隊(duì)列得元素必定先出隊(duì)列，所以又把隊(duì)列稱為表。設(shè)一棵完全二叉樹(shù)得順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCDEF，則該二叉樹(shù)得前序遍歷序列為,中序遍歷序列為,后序遍歷序列為設(shè)一棵完全二叉樹(shù)有128個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)得深度為,有個(gè)葉子結(jié)點(diǎn).設(shè)有向圖G得存儲(chǔ)結(jié)構(gòu)用鄰接矩陣A來(lái)表示，則A中第i行中所有非零元素個(gè)數(shù)之與等TOC o 1-5 h z于頂點(diǎn)i得,第i列中所有非零元素個(gè)數(shù)之與等于頂點(diǎn)i得.&設(shè)一組初始記錄關(guān)鍵字序列(k,k,k)就是堆，則對(duì)i=1,2,，n/2而言12n滿足得條件為。下面程序段得功能就是實(shí)現(xiàn)冒泡排序算法，請(qǐng)?jiān)谙聞澗€處填上正確得語(yǔ)句。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；下面程序段得功能就是實(shí)現(xiàn)二分查找算法，請(qǐng)?jiān)谙聞澗€處填上正確得語(yǔ)句。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);三、應(yīng)用題(32分)設(shè)某棵二叉樹(shù)得中序遍歷序列為DBEAC,前序遍歷序列為ABDEC,要求給出該二叉樹(shù)得得后序遍歷序列。設(shè)無(wú)向圖G(如右圖所示)，給出該圖得最小生成樹(shù)上邊得集合并計(jì)算最小生成樹(shù)各邊上得權(quán)值之與。設(shè)一組初始記錄關(guān)鍵字序列為(15,17,18,22,35,51,60),要求計(jì)算出成功查找時(shí)得平均查找長(zhǎng)度。設(shè)散列表得長(zhǎng)度為8,散列函數(shù)H(k)=kmod7,初始記錄關(guān)鍵字序列為(25,3

34、1,8,27，13，68)，要求分別計(jì)算出用線性探測(cè)法與鏈地址法作為解決沖突方法得平均查找長(zhǎng)度。四、算法設(shè)計(jì)題(28分)1設(shè)計(jì)判斷兩個(gè)二叉樹(shù)就是否相同得算法.2設(shè)計(jì)兩個(gè)有序單鏈表得合并排序算法.數(shù)據(jù)結(jié)構(gòu)試卷(六)一、選擇題(30分)1。設(shè)一組權(quán)值集合W=2,3,4,5,6,則由該權(quán)值集合構(gòu)造得哈夫曼樹(shù)中帶權(quán)路徑長(zhǎng)度之與為().(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。設(shè)一條單鏈

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

36、個(gè)結(jié)點(diǎn)，則該三叉樹(shù)得最小高度為()。(A)3o(B)4C)5。(D)6順序查找不論在順序線性表中還就是在鏈?zhǔn)骄€性表中得時(shí)間復(fù)雜度為().(A)0(n)。(B)0(n2)(C)0(ni/2)。(D)0(1og2n)9。二路歸并排序得時(shí)間復(fù)雜度為()。(A)0(n)。(B)0(n2)(C)0(nlogn)(D)0(1og2n)10、深度為k得完全叉樹(shù)中最少有()個(gè)結(jié)點(diǎn).。(A)2k-i1(B)2ki。(C)2ki+1D)2k111、設(shè)指針變量front表示鏈?zhǔn)疥?duì)列得隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列得隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列得結(jié)點(diǎn)X,則入隊(duì)列得操作序列為()(A)frontnext=

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

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

39、子樹(shù)。()8線性表得順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。()9中序遍歷二叉排序樹(shù)可以得到一個(gè)有序得序列。()10、快速排序就是排序算法中平均性能最好得一種排序。()三、填空題(30分)for(i=l,t=1,s=0；i二n;i+)t=t*i；s=s+1;得時(shí)間復(fù)雜度為2。設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入得新結(jié)點(diǎn)X,則進(jìn)行插入操作得語(yǔ)句序列為(設(shè)結(jié)點(diǎn)得指針域?yàn)閚ext)。3。設(shè)有向圖G得二元組形式表示為G=(D,R),D=1,2,3,4,5,R=r,r=vl,2,V4,5,1,3，,3,5,則給出該圖得一種拓?fù)渑判蛐蛄?。設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖中每個(gè)頂點(diǎn)得度數(shù)最多就是

40、。設(shè)二叉樹(shù)中度數(shù)為0得結(jié)點(diǎn)數(shù)為50，度數(shù)為1得結(jié)點(diǎn)數(shù)為30,則該二叉樹(shù)中總共有個(gè)結(jié)點(diǎn)數(shù)。6設(shè)F與R分別表示順序循環(huán)隊(duì)列得頭指針與尾指針，則判斷該循環(huán)隊(duì)列為空得條件為_(kāi)7設(shè)二叉樹(shù)中結(jié)點(diǎn)得兩個(gè)指針域分別為lchild與child，則判斷指針變量p所指向得結(jié)點(diǎn)為葉子結(jié)點(diǎn)得條件就是TOC o 1-5 h z&簡(jiǎn)單選擇排序與直接插入排序算法得平均時(shí)間復(fù)雜度為。9快速排序算法得空間復(fù)雜度平均情況下為，最壞得情況下為。10、散列表中解決沖突得兩種方法就是與.四、算法設(shè)計(jì)題(20分)1設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找得算法。設(shè)計(jì)判斷二叉樹(shù)就是否為二叉排序樹(shù)得算法。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法數(shù)據(jù)結(jié)構(gòu)試卷

41、(七)一、選擇題(30分)1設(shè)某無(wú)向圖有n個(gè)頂點(diǎn)，貝y該無(wú)向圖得鄰接表中有()個(gè)表頭結(jié)點(diǎn)。(A)2n(B)n(C)n/2。(D)n(n1)設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖得最小生成樹(shù)上有()條邊.(A)n(B)n-1。(C)2nD)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,80(C)42,40,55,60,80,85(D)42,40,60,85,55,80()二叉排序樹(shù)可以得到一個(gè)從小到大得有序序列。(A)先序遍歷*B)中序遍

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

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

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