計(jì)算機(jī)與軟件學(xué)院《數(shù)據(jù)結(jié)構(gòu)》筆試題及答案

閣的鄰接麥存儲(chǔ)結(jié)相閣的鄰接麥存儲(chǔ)結(jié)相計(jì)算機(jī)與軟件學(xué)院考試試卷及參考答案課程名稱：數(shù)據(jù)結(jié)構(gòu)一、填空題（24分）為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問(wèn)題是 和下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語(yǔ)句。typedefstruct{ints[100];inttop;}sqstack;voidpush（sqstack&stack,intx）{if（stack.top==m-l）printf（“overflow”）；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ù)為N,則該二叉樹(shù)中度數(shù)為2的結(jié)點(diǎn)數(shù)為 ;若采用二叉鏈表作為該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則該二叉樹(shù)中共有 個(gè)空指針域。設(shè)某無(wú)向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(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,47,50,62,83,90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。4.設(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ù)。5.設(shè)有無(wú)向圖G,要求給出用普里姆算法構(gòu)造最小生成樹(shù)所走過(guò)的邊的集合。三、算法設(shè)計(jì)題(16分)設(shè)有一組初始記錄關(guān)鍵字序列(K,K,…，K),要求設(shè)計(jì)一個(gè)算法能夠在0(n)的時(shí)間復(fù)1 2 n雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于K,右半部分的每個(gè)關(guān)1鍵字均大于等于K。i設(shè)有兩個(gè)集合A和集合B,要求設(shè)計(jì)生成集合C=AHB的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。參考答案一、填空題1.構(gòu)造一個(gè)好的HASH函數(shù)，確定解決沖突的方法2.stack.top++，stack.s[stack.top]=x3.有序4.O(n2)，O(nlogn)5.N-1，2N+NCl 0 16.001d/27.(31，38，54，56，75，80，55，63)8.(1，3，4，5，2)，(1，3，2，4，5)二、應(yīng)用題1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;2,ASL=91*1+2*2+3*4+4*2)=25/9樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹(shù)略5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}三、算法設(shè)計(jì)題設(shè)有一組初始記錄關(guān)鍵字序列(K,K,…，K),要求設(shè)計(jì)一個(gè)算法能夠在0(n)的時(shí)間復(fù)1 2 n雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于K,右半部分的每個(gè)關(guān)1鍵字均大于等于Ki。ivoidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]>x)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<x)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}設(shè)有兩個(gè)集合A和集合B,要求設(shè)計(jì)生成集合C=AHB的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){for(q=hb;q!=0;q=q->next)if(q->