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

數(shù)據(jù)構(gòu)造試卷〔一〕一、單項(xiàng)選擇題〔每題2分，共20分〕棧和隊(duì)列的共同特點(diǎn)是(a)。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點(diǎn)用鏈接方式存儲的隊(duì)列，在進(jìn)展插入運(yùn)算時(d).A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改以下數(shù)據(jù)構(gòu)造中哪一個是非線性構(gòu)造？(d)A.隊(duì)列B.棧C.線性表D.二叉樹設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。cA．688B．678C．692D．696樹最適合用來表示(c)。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為(d).A．2k-1B.2K+1C.2K-1D.2k-1假設(shè)有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進(jìn)展二分查找，那么查找A［3］的比擬序列的下標(biāo)依次為(cd)A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，3對n個記錄的文件進(jìn)展快速排序，所需要的輔助存儲空間大致為cA.O〔1〕B.O〔n〕C.O〔1og2n〕D.O〔n2〕對于線性表〔7，34，55，25，64，46，20，10〕進(jìn)展散列存儲時，假設(shè)選用H〔K〕=K%9作為散列函數(shù)，那么散列地址為1的元素有〔cd〕個，A．1B．2C．3D．4設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有(a)條邊才能確保是一個連通圖。二、填空題〔每空1分，共26分〕通常從四個方面評價算法的質(zhì)量：____時間正確性_____、____占用內(nèi)存_易讀性____、____復(fù)雜度__強(qiáng)壯性___和_____準(zhǔn)確度_高效率___。一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為___30〔n〕_____。假定一棵樹的廣義表表示為A〔C，D〔E，F(xiàn)，G〕，H〔I，J〕〕，那么樹中所含的結(jié)點(diǎn)數(shù)為_____9_____個，樹的深度為_____3______，樹的度為____2_____。后綴算式923+-102/-的值為____3__-1____。中綴算式〔3+4X〕-2Y/3對應(yīng)的后綴算式為______34X*+2Y*/-_________________________。假設(shè)用鏈表存儲一棵二叉樹時，每個結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲構(gòu)造中，n個結(jié)點(diǎn)的二叉樹共有____n_2n___個指針域，其中有_____n-1___個指針域是存放了地址，有________3__n+1______個指針是空指針。對于一個具有n個頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有___e+1_e___個和____e+1__2e__個。AOV網(wǎng)是一種________有向無回路___________的圖。在一個具有n個頂點(diǎn)的無向完全圖中，包含有____n-1_n(n-1)/2___條邊，在一個具有n個頂點(diǎn)的有向完全圖中，包含有____n-1___n(n-1)_條邊。假定一個線性表為(12,23,74,55,63,40)，假設(shè)按Key%4條件進(jìn)展劃分，使得同一余數(shù)的元素成為一個子表，那么得到的四個子表分別為___________(12,40)_________________、_______(23,63,55)________、_______(74)________________和_________()_________________。向一棵B_樹插入元素的過程中，假設(shè)最終引起樹根結(jié)點(diǎn)的分裂，那么新樹比原樹的高度______增加1____。在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)展篩運(yùn)算的時間復(fù)雜度為___0〔n/2〕___O(log2n)__，整個堆排序過程的時間復(fù)雜度為__0〔1〕__O(nlog2n)____。在快速排序、堆排序、歸并排序中，____堆排序__歸并排序___排序是穩(wěn)定的。三、計(jì)算題〔每題6分，共24分〕在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A[0].next，試寫出該線性表。A01234567data6next3572041A[0]A[3]A[2]A[7]A[1]A[5]A[4]A[0]線性表為：〔78，50，40，60，34，90〕請畫出以下圖的鄰接矩陣和鄰接表。鄰接矩陣：一個圖的頂點(diǎn)集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20畫出向小根堆中參加數(shù)據(jù)4,2,5,8,3時，每參加一個數(shù)據(jù)后堆的變化。四、閱讀算法〔每題7分，共14分〕LinkListmynote(LinkListL){//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；}請答復(fù)以下問題：〔1〕說明語句S1的功能；判斷p的下一節(jié)點(diǎn)是否為空，如不為空p那么指向下一節(jié)點(diǎn)查詢鏈表的尾節(jié)點(diǎn)〔2〕說明語句組S2的功能；使P的下一節(jié)點(diǎn)賦值給q，并令q的下一節(jié)點(diǎn)為空指針。將第一個節(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾節(jié)點(diǎn)〔3〕設(shè)鏈表表示的線性表為〔a1,a2,…,an〕,寫出算法執(zhí)行后的返回值所表示的線性表。a2,a3,…an,a1voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<<BT->data<<'';}}該算法的功能是：判斷是否為滿二叉樹遞歸的后序遍歷鏈?zhǔn)酱鎯Φ亩鏄湮?、算法填空〔?分〕二叉搜索樹的查找——遞歸算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失敗else{if(item==BST->data){item=BST->data;//查找成功return____item__true_____;}elseif(item<BST->data)returnFind(______BST->data____BST->left____,item);elsereturnFind(_______item____BST->right____,item);}//if}六、編寫算法〔共8分〕統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。intCountX(LNode*HL,ElemTypex){ intcount; node*head,*p; head=HL; p=head->next; if(head->data!=null) { while(p->next) { if(p->data==x)count++; } } } StructnodeHL { elemtypedata; Structnode*next; }node;intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i為計(jì)數(shù)器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循環(huán)時i中的值即為x結(jié)點(diǎn)個數(shù)returni;}//CountX數(shù)據(jù)構(gòu)造試卷〔一〕參考答案選擇題〔每題2分，共20分〕二、填空題〔每空1分，共26分〕正確性易讀性強(qiáng)壯性高效率O(n)933-134X*+2Y*3/-2nn-1n+1e2e有向無回路n(n-1)/2n(n-1)〔12，40〕〔〕〔74〕〔23,55，63〕增加1O(log2n)O(nlog2n)歸并三、計(jì)算題〔每題6分，共24分〕線性表為：〔78，50，40，60，34，90〕鄰接矩陣：鄰接表如圖11所示：圖11用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20見圖1244444222552852834528434444422255285283452843讀算法〔每題7分，共14分〕〔1〕查詢鏈表的尾結(jié)點(diǎn)〔2〕將第一個結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)〔3〕返回的線性表為〔a2,a3,…,an,a1〕遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄?。法填空〔每?分，共8分〕trueBST->leftBST->right編寫算法〔8分〕intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i為計(jì)數(shù)器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循環(huán)時i中的值即為x結(jié)點(diǎn)個數(shù)returni;}//CountX數(shù)據(jù)構(gòu)造試卷〔二〕一、選擇題(24分)1．下面關(guān)于線性表的表達(dá)錯誤的選項(xiàng)是〔〕。 (A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間 (B)線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C)線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)2．設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，假設(shè)用二叉鏈表作為存儲構(gòu)造，那么該哈夫曼樹中總共有〔〕個空指針域。 (A)2m-1 (B)2m (C)2m+1 (D)4m3．設(shè)順序循環(huán)隊(duì)列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，那么該循環(huán)隊(duì)列中的元素個數(shù)為〔〕。 (A)R-F (B)F-R (C)(R-F+M)％M (D)(F-R+M)％M4．設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，那么后序遍歷該二叉樹得到序列為〔〕。 (A)BADC (B)BCDA (C)CDAB (D)CBDA5．設(shè)某完全無向圖中有n個頂點(diǎn)，那么該完全無向圖中有〔〕條邊。 (A)n(n-1)/2 (B)n(n-1) (C)n2 (D)n2-16．設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，那么該二叉樹的最小高度為〔〕。 (A)9 (B)10 (C)11 (D)127．設(shè)某有向圖中有n個頂點(diǎn)，那么該有向圖對應(yīng)的鄰接表中有〔〕個表頭結(jié)點(diǎn)。 (A)n-1 (B)n (C)n+1 (D)2n-18．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)展一趟快速排序的結(jié)果為〔〕。 (A)2，3，5，8，6 (B)3，2，5，8，6 (C)3，2，5，6，8 (D)2，3，6，5，8二、填空題(24分)為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是____________________和__________________________。下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-1)printf(“overflow〞);else{____________________;_________________;}}中序遍歷二叉排序樹所得到的序列是___________序列〔填有序或無序〕?？焖倥判虻淖顗臅r間復(fù)雜度為___________，平均時間復(fù)雜度為__________。設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，那么該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_________；假設(shè)采用二叉鏈表作為該二叉樹的存儲構(gòu)造，那么該二叉樹中共有_______個空指針域。設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，那么e=_______。設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，那么利用篩選法建立的初始堆為___________________________。8．一有向圖的鄰接表存儲構(gòu)造如下：從頂點(diǎn)1出發(fā)，DFS遍歷的輸出序列是，BFS遍歷的輸出序列是三、應(yīng)用題(36分)設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，那么分別給出第4趟簡單項(xiàng)選擇擇排序和第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)的兩個指針域分別為llink和rlink〕。設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時的比擬次數(shù)并計(jì)算出查找成功時的平均查找長度。設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法〔二叉鏈表〕表示出該樹的存儲構(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)鍵字序列〔K1，K2，…，Kn〕，要求設(shè)計(jì)一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩局部，其中左半局部的每個關(guān)鍵字均小于Ki，右半局部的每個關(guān)鍵字均大于等于Ki。設(shè)有兩個集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?gòu)造表示。數(shù)據(jù)構(gòu)造試卷〔二〕參考答案一、選擇題1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C二、填空題構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法stack.top++，stack.s[stack.top]=x有序O(n2)，O(nlog2n)N0-1，2N0+N1d/2(31，38，54，56，75，80，55，63)(1，3，4，5，2)，(1，3，2，4，5)三、應(yīng)用題(22，40，45，48，80，78)，(40，45，48，80，22，78)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樹的鏈?zhǔn)酱鎯?gòu)造略，二叉樹略E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}略四、算法設(shè)計(jì)題設(shè)有一組初始記錄關(guān)鍵字序列〔K1，K2，…，Kn〕，要求設(shè)計(jì)一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩局部，其中左半局部的每個關(guān)鍵字均小于Ki，右半局部的每個關(guān)鍵字均大于等于Ki。voidquickpass(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è)有兩個集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?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->data==p->data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}}}數(shù)據(jù)構(gòu)造試卷〔三〕一、選擇題(每題1分，共20分)1．設(shè)某數(shù)據(jù)構(gòu)造的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，那么數(shù)據(jù)構(gòu)造A是〔〕。 (A)線性構(gòu)造 (B)樹型構(gòu)造 (C)物理構(gòu)造 (D)圖型構(gòu)造2．下面程序的時間復(fù)雜為〔〕for〔i=1，s=0；i<=n；i++〕{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；} (A)O(n) (B)O(n2) (C)O(n3) (D)O(n4)3．設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，假設(shè)刪除單鏈表中結(jié)點(diǎn)A，那么需要修改指針的操作序列為〔〕。 (A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)； (C)q=p->next；p->next=q->next；free(q)； (D)q=p->next；p->data=q->data；free(q)；4．設(shè)有n個待排序的記錄關(guān)鍵字，那么在堆排序中需要〔〕個輔助記錄單元。 (A)1 (B)n (C)nlog2n (D)n25．設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，那么以20為基準(zhǔn)記錄的一趟快速排序完畢后的結(jié)果為()。(A)10，15，14，18，20，36，40，21 (B)10，15，14，18，20，40，36，21 (C)10，15，14，20，18，40，36，2l (D)15，10，14，18，20，36，40，216．設(shè)二叉排序樹中有n個結(jié)點(diǎn)，那么在二叉排序樹的平均平均查找長度為〔〕。 (A)O(1) (B)O(log2n) (C) (D)O(n2)7．設(shè)無向圖G中有n個頂點(diǎn)e條邊，那么其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個數(shù)分別為〔〕。 (A)n，e (B)e，n (C)2n，e (D)n，2e8.設(shè)某強(qiáng)連通圖中有n個頂點(diǎn)，那么該強(qiáng)連通圖中至少有〔〕條邊。 (A)n(n-1) (B)n+1 (C)n (D)n(n+1)9．設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，那么用以下〔〕方法可以到達(dá)此目的。 (A)快速排序 (B)堆排序 (C)歸并排序 (D)插入排序10.以下四種排序中〔〕的空間復(fù)雜度最大。 (A)插入排序 (B)冒泡排序 (C)堆排序 (D)歸并排序二、填空殖(每空1分共20分)數(shù)據(jù)的物理構(gòu)造主要包括_____________和______________兩種情況。設(shè)一棵完全二叉樹中有500個結(jié)點(diǎn)，那么該二叉樹的深度為__________；假設(shè)用二叉鏈表作為該完全二叉樹的存儲構(gòu)造，那么共有___________個空指針域。設(shè)輸入序列為1、2、3，那么經(jīng)過棧的作用后可以得到___________種不同的輸出序列。設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲構(gòu)造，那么該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的________，第i列上所有元素之和等于頂點(diǎn)i的________。設(shè)哈夫曼樹中共有n個結(jié)點(diǎn)，那么該哈夫曼樹中有________個度數(shù)為1的結(jié)點(diǎn)。設(shè)有向圖G中有n個頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，那么e和d的關(guān)系為_________。__________遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個遞增的關(guān)鍵字序列〔填先序、中序或后序〕。設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，那么最多需要比擬________次就可以斷定數(shù)據(jù)元素X是否在查找表中。不管是順序存儲構(gòu)造的棧還是鏈?zhǔn)酱鎯?gòu)造的棧，其入棧和出棧操作的時間復(fù)雜度均為____________。設(shè)有n個結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開場順序編號，那么第i個結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為____________，右孩子結(jié)點(diǎn)的編號為___________。設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，那么以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為___________________________。設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，那么該圖的一種拓?fù)湫蛄袨開___________________。以下算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請?jiān)谙聞澗€處填上正確的語句。structrecord{intkey;intothers;};inthashsqsearch(structrecordhashtable[],intk){inti,j;j=i=k%p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);}if(_______________________)return(j);elsereturn(-1);}以下算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請?jiān)谙聞澗€處填上正確的語句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){ if(t==0)return(0);elsewhile(t!=0)if(t->key==k)_____________;elseif(t->key>k)t=t->lchild;else_____________;}三、計(jì)算題(每題10分，共30分)1.二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。2．待散列的線性表為〔36，15，40，63，22〕，散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H〔K〕=Kmod7，假設(shè)發(fā)生沖突采用線性探查法處理，試：〔1〕計(jì)算出每一個元素的散列地址并在以下圖中填寫出散列表：`0123456〔2〕求出在查找每一個元素概率相等情況下的平均查找長度。3．序列〔10，18，4，3，6，12，1，9，18，8〕請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。四、算法設(shè)計(jì)題(每題15分，共30分)設(shè)計(jì)在單鏈表中刪除值一樣的多余結(jié)點(diǎn)的算法。設(shè)計(jì)一個求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。數(shù)據(jù)構(gòu)造試卷〔三〕參考答案一、選擇題1.B 2.B 3.A 4.A 5.A6.B 7.D 8.C 9.B 10.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快速排序、歸并排序和插入排序必須等到整個排序完畢后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的根底上再進(jìn)展10次篩選即可，每次篩選的時間復(fù)雜度為O(log2n)。二、填空題順序存儲構(gòu)造、鏈?zhǔn)酱鎯?gòu)造9，5015出度，入度0e=d中序7O(1)i/2，2i+1(5，16，71，23，72，94，73)(1，4，3，2)j+1，hashtable[j].key==kreturn(t)，t=t->rchild第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進(jìn)展二分查找時的查找長度不超過二叉判定樹的高度1+log2n。三、計(jì)算題1．2、H(36)=36mod7=1;H１(22)=(1+1)mod7=2;….沖突H(15)=15mod7=1;….沖突H2(22)=(2+1)mod7=3;H１(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;….沖突〔1〕01234566336152240〔2〕ASL=3、(8,9,4,3,6,1),10,(12,18,18)(1,6,4,3),8,(9),10,12,(18,18)1,(3,4,6),8,9,10,12,18,(18)1,3,(4,6),8,9,10,12,18,181,3,4,6,8,9,10,12,18,18四、算法設(shè)計(jì)題設(shè)計(jì)在單鏈表中刪除值一樣的多余結(jié)點(diǎn)的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p->next){for(q=p->next,s=q;q!=0;)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{s=q,q=q->next;}}}設(shè)計(jì)一個求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}數(shù)據(jù)構(gòu)造試卷〔四〕一、選擇題(每題1分共20分)1．設(shè)一維數(shù)組中有n個數(shù)組元素，那么讀取第i個數(shù)組元素的平均時間復(fù)雜度為〔〕。 (A)O(n) (B)O(nlog2n) (C)O(1) (D)O(n2)2．設(shè)一棵二叉樹的深度為k，那么該二叉樹中最多有〔〕個結(jié)點(diǎn)。 (A)2k-1 (B)2k (C)2k-1 (D)2k-13．設(shè)某無向圖中有n個頂點(diǎn)e條邊，那么該無向圖中所有頂點(diǎn)的入度之和為〔〕。 (A)n (B)e (C)2n (D)2e4．在二叉排序樹中插入一個結(jié)點(diǎn)的時間復(fù)雜度為〔〕。 (A)O(1) (B)O(n) (C)O(log2n) (D)O(n2)5．設(shè)某有向圖的鄰接表中有n個表頭結(jié)點(diǎn)和m個表結(jié)點(diǎn)，那么該圖中有〔〕條有向邊。 (A)n (B)n-1 (C)m (D)m-16．設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，那么用基數(shù)排序需要進(jìn)展〔〕趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。 (A)3 (B)4 (C)5 (D)87．設(shè)用鏈表作為棧的存儲構(gòu)造那么退棧操作〔〕。 (A)必須判別棧是否為滿 (B)必須判別棧是否為空 (C)判別棧元素的類型 (D)對棧不作任何判別8．以下四種排序中〔〕的空間復(fù)雜度最大。 (A)快速排序 (B)冒泡排序 (C)希爾排序 (D)堆9．設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，那么以下等式成立的是〔〕。 (A)N0=N1+1 (B)N0=Nl+N2 (C)N0=N2+1 (D)N0=2N1+l10.設(shè)有序順序表中有n個數(shù)據(jù)元素，那么利用二分查找法查找數(shù)據(jù)元素X的最多比擬次數(shù)不超過〔〕。 (A)log2n+1 (B)log2n-1 (C)log2n (D)log2(n+1)二、填空題(每空1分共20分)設(shè)有n個無序的記錄關(guān)鍵字，那么直接插入排序的時間復(fù)雜度為________，快速排序的平均時間復(fù)雜度為_________。設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，那么刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為_________________________________________________________〔設(shè)結(jié)點(diǎn)中的兩個指針域分別為llink和rlink〕。根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。深度為k的完全二叉樹中最少有____________個結(jié)點(diǎn)。設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，Kn)，那么用篩選法思想建堆必須從第______個元素開場進(jìn)展篩選。設(shè)哈夫曼樹中共有99個結(jié)點(diǎn)，那么該樹中有_________個葉子結(jié)點(diǎn)；假設(shè)采用二叉鏈表作為存儲構(gòu)造，那么該樹中有_____個空指針域。設(shè)有一個順序循環(huán)隊(duì)列中有M個存儲單元，那么該循環(huán)隊(duì)列中最多能夠存儲________個隊(duì)列元素；當(dāng)前實(shí)際存儲________________個隊(duì)列元素〔設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個位置，尾指針指向當(dāng)前隊(duì)尾元素的位置〕。設(shè)順序線性表中有n個數(shù)據(jù)元素，那么第i個位置上插入一個數(shù)據(jù)元素需要移動表中_______個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_______個元素。設(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個頂點(diǎn)，用鄰接矩陣A作為該圖的存儲構(gòu)造，那么頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是______________________。設(shè)無向圖對應(yīng)的鄰接矩陣為A，那么A中第i上非0元素的個數(shù)_________第i列上非0元素的個數(shù)〔填等于，大于或小于〕。設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，那么后序遍歷該二叉樹的序列為_____________。設(shè)散列函數(shù)H(k)=kmodp，解決沖突的方法為鏈地址法。要求在以下算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn)，成功時返回指向關(guān)鍵字的指針，不成功時返回標(biāo)志0。typedefstructnode{intkey;structnode*next;}lklist;voidcreatelkhash(lklist*hashtable[]){inti,k;lklist*s;for(i=0;i<m;i++)_____________________;for(i=0;i<n;i++){s=(lklist*)malloc(sizeof(lklist));s->key=a[i];k=a[i]%p;s->next=hashtable[k];_______________________;}}三、計(jì)算題(每題10分，共30分)1、畫出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表存儲構(gòu)造。2、以下圖所示的森林：(1)求樹〔a〕的先根序列和后根序列；(2)求森林先序序列和中序序列；〔3〕將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；3、設(shè)散列表的地址范圍是[0..9]，散列函數(shù)為H〔key〕=〔ke