數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案-wenkub.com
2025-06-19 14:18 本頁面
【正文】 } if(ha==0) snext=hb。 else {snext=hb。 s=ha。 while(ha!=0 amp。 else return(judgebitree(bt1lchild,bt2lchild)*judgebitree(bt1rchild,bt2rchild))。int judgebitree(bitree *bt1,bitree *bt2){ if (bt1==0 amp。 ki=k2i+19. ni，r[j+1]=r[j]10. mid=(low+high)/2，r[mid].keyk三、應(yīng)用題1. DEBCA2. E={(1,5),(5,2),(5,3),(3,4)},W=103. ASL=(1*1+2*2+3*4)/7=17/74. ASL1=7/6，ASL2=4/3四、算法設(shè)計(jì)題1. 設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法。i=n。 else bstinsert(btrchild,key)。bt,int key){ if (bt==0){bt=(bitree *)malloc(sizeof(bitree))。define n 10typedef struct node{int key。p=btlchild。void swapbitree(bitree *bt){ bitree *p。} }}2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。) {pnext=hb。 amp。) {pnext=ha。 amp。p=head) { head=pnext。hc){ lklist *p。}lklist。 BDEFCAIJKHG林轉(zhuǎn)換為相應(yīng)的二叉樹；3．H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6四、算法設(shè)計(jì)題1. 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。 else printf(not parent)。 i=r。 preorder(btrchild,x)。 return。 int r=0,f=0,flag=0。typedef struct node {datatype data。 free(q)。p!=0。}lklist。 ….沖突（1） 0 1 2 3 4 5 66336152240（2）ASL=(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,18 1,3, 4,6,8,9,10,12,18,18四、算法設(shè)計(jì)題1. 設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。 H１(15)=(1+1) mod 7=2。三、計(jì)算題1． H(36)=36 mod 7=1。}}}數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案一、選擇題 第3小題分析：首先用指針變量q指向結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，然后將結(jié)點(diǎn)B的值復(fù)制到結(jié)點(diǎn)A中，最后刪除結(jié)點(diǎn)B。if(q!=0){ t=(lklist *)malloc(sizeof(lklist))。p!=0。}lklist。} } r[i]=x。amp。 r[j]x) j=j1。3. 2,ASL=91*1+2*2+3*4+4*2)=25/94. 樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹略5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6. 略四、算法設(shè)計(jì)題1. 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。 }//CountX數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案一、選擇題 二、填空題1. 構(gòu)造一個(gè)好的HASH函數(shù)，確定解決沖突的方法2. ++，[]=x3. 有序4. O(n2)，O(nlog2n)5. N01，2N0+N16. d/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. qllink=p。 LNode* p=HL。四、算法設(shè)計(jì)題(28分)1． 設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法。}三、應(yīng)用題(32分)1. 設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。 if(r[mid].key==k) return(mid+1)。 int others。r[j]=temp。 i++){for(exchange=0,j=0。8. 設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。4. 棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為__________表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為_________表。 (A) ni (B) n1i (C) n+1i (D) 不能確定10 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（ ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)6．設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=（ ）。 (A) 數(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)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（ ）。四、算法設(shè)計(jì)題(每題10分，共30分)1． 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。 snext=hashtable[k]。in。for(i=0。 struct node *next。13． 設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。9． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為______________________________。5． 設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個(gè)元素開始進(jìn)行篩選。 (A) log2n+1 (B) log2n1 (C) log2n (D) log2(n+1)二、填空題(每空1分共 20分)1． 設(shè)有n個(gè)無序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為________，快速排序的平均時(shí)間復(fù)雜度為_________。 (A) 3 (B) 4 (C) 5 (D) 87．設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作（ ）。 (A) 2k1 (B) 2k (C) 2k1 (D) 2k13．設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為（ ）。四、算法設(shè)計(jì)題(每題15分，共30分)1． 設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。 else_____________。}bitree。}14. 下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請?jiān)谙聞澗€處填上正確的語句。hashtable[j].flag!=0){j=(____) %m。int hashsqsearch(struct record hashtable[ ],int k){int i,j。13. 下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請?jiān)谙聞澗€處填上正確的語句。9. 不論是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為____________。5. 設(shè)哈夫曼樹中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有________個(gè)度數(shù)為1的結(jié)點(diǎn)。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 歸并排序二、填空殖(每空1分 共20分)1. 數(shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種情況。 (A) O(1) (B) O(log2n) (C) (D) O(n2)7．設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（ ）。 (A) 線性結(jié)構(gòu) (B) 樹型結(jié)構(gòu) (C) 物理結(jié)構(gòu) (D) 圖型結(jié)構(gòu)2．下面程序的時(shí)間復(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，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操
法律信息相關(guān)推薦
鄂ICP備17016276號-1