數據結構試題及答案免費(存儲版)

　　

【正文】 個算法的時間復雜度為(n3+n2log2n+14n)/n2，其數量級表示為________。 假定一棵樹的廣義表表示為A（C，D（E，F，G），H（I，J）），則樹中所含的結點數為__________個，樹的深度為___________，樹的度為_________。 后綴算式9 2 3 + 10 2 / 的值為__________。三、 三、四、 四、Lnext){ q=L；L=L－next；p=L； S1： while(p－next) p=p－next； S2： p－next=q；q－next=NULL； } return L； } 請回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設鏈表表示的線性表為（a1,a2, …,an）,寫出算法執行后的返回值所表示的線性表。 39。} else if(itemBSTdata) return Find(______________,item)。數據結構16參考答案一、 一、 O(log2n) O(nlog2n)12. 12.圖12四、 四、 編寫算法（8分）int CountX(LNode* HL,ElemType x) { int i=0。 數據結構（十七）一、 一、 s→link=q。 由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ） A 24 B 71 C 48 D 53二、 二、 74 25 在一個索引文件的索引表中，每個索引項包含對應記錄的_________和___________兩項數據。 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_________,整個堆排序過程的時間復雜度為________________。 已知一個圖的頂點集V各邊集G如下：V = {0，1，2，3，4，5，6，7，8，9}；E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}當它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V0出發按深度優先搜索遍歷得到的頂點序列和按廣度優先搜索遍歷等到的頂點序列。假定從鍵盤上輸入一批整數，依次為：78 63 45 30 91 34 –1，請寫出輸出結果。 三、 三、 一棵高度為5的二叉樹中最少含有_________個結點，最多含有________個結點；一棵高度為5的理想平衡樹中，最少含有_________個結點，最多含有_________個結點。 a 0 1 2 3 4 5 6 7 8 p→link=s。五、 五、 見圖124444422255285283452843 鄰接矩陣： 鄰接表如圖11所示：圖113. 3. 運算題（每題6分，共24分）1. 1. （12，40） （ ） （74） （23,55，63）10. 10. 有向無回路8. 8. 2n n1 n+16. 6. 9 3 34. 4. 正確性 易讀性 強壯性 高效率2. 2. int CountX(LNode* HL,ElemType x) //查找失敗 else { if (item==BSTdata){ item=BSTdata。 ABC (BTright)。 LinkList mynote(LinkList L) {//L是不帶頭結點的單鏈表的頭指針 if(Lamp。 畫出向小根堆中加入數據4, 2, 5, 8, 3時，每加入一個數據后堆的變化。 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。 在快速排序、堆排序、歸并排序中，_________排序是穩定的。 向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度___________。 單選題（每題 2 分，共20分）1. 1.HL=HLnext。 HL) //查找成功，返回元素的下標 else if (K[mid].key) ______________________________________。 } p=pnext。 QInsert(Q,i)。 已知一個圖的頂點集V和邊集E分別為： 圖6 V={1,2,3,4,5,6,7}。5稀疏矩陣如下所示， 運算題（每題6分，共24分）1. 1. 在線性表的散列存儲中，處理沖突的常用方法有________________________和_____________________________兩種。10. 10.9. 9. A. O(n) B. O(1) C. O(log2n) D. O(n2)A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找7. 7. B. pnext=HL。 對一個算法的評價，不包括如下（B ）方面的內容。 i=i/2。else if (pkeykey)p=plchild。 s=hb。amp。3． 3．三、算法設計題(22分)1． 1．i++){ p=(lklist *)malloc(sizeof(lklist))。) ___________。struct node *lchild。11. 11. 數據結構從邏輯上劃分為三種基本類型：___________、__________和___________。 設指針變量p指向單鏈表中結點A，則刪除結點A的語句序列為：q=pnext；pdata=qdata；pnext=___________；feee(q)；7. 7.6. 6. (A) 6 (B) 7 (C) 8 (D) 9(Q，H，C，Y，P，A，M，S，R，D，F，X)，則按字母升序的第一趟冒泡排序結束后的結果是（ ）。(A) snext=pnext；pnext=s； (B) qnext=s； snext=p；(C) pnext=snext；snext=p； (D) pnext=s；snext=q；4．設輸入序列為6，則通過棧的作用后可以得到的輸出序列為（ ）。elsefor(q=head,p=headnext。 r[i]%2==1) i=i+1。void quickpass(int r[], int s, int t){ int i=s,j=t,x=r[s]。 設計計算二叉樹中所有結點值之和的算法。一、選擇題1．A 2．A 3．A 4．C 5．D6．D 7．C 8．B 9．C 10．A11．C 12．C 13．D 14．A 15．A（ ）10． 10．堆是完全二叉樹，完全二叉樹不一定是堆。( )8． 8．( )6． 6．( )4． 4．( )2． 2．10． 10． 設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為13210，根據這些頻率作為權值構造哈夫曼樹，則這棵哈夫曼樹的高度為________________。 設指針p指向單鏈表中結點A，指針s指向被插入的結點X，則在結點A的前面插入結點X時的操作序列為：1) snext=___________；2) pnext=s；3) t=pdata；4) pdata=___________；5) sdata=t；2． 2． (A) 6 (B) 11 (C) 5 (D) ={1，2，2，3，3，4，1，4}，則下列屬于該有向圖G的一種拓撲排序序列的是（ ）。 (A) pright=s； sleft=p； prightleft=s； sright=pright； (B) sleft=p；sright=pright；pright=s； prightleft=s； (C) pright=s； prightleft=s； sleft=p； sright=pright； (D) sleft=p；sright=pright；prightleft=s； pright=s；6．下列各種排序算法中平均時間復雜度為O(n2)是（ ）。pnextarc=g[j].firstarc。i++) for(j=0。}glinkheadnode。 int edge[m][m]。 50 CABD6. 6. 設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。 設計一個在鏈式存儲結構上統計二叉樹中結點個數的算法。 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結束后的結果為_____________________________。6． 6． 設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X需要執行的語句序列：snext=pnext。void bstinsert(bitree *amp。 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結束后的結果為_____________________________。（ ）10. 10. 設初始記錄關鍵字基本有序，則快速排序算法的時間復雜度為O(nlog2n)。（ ）2. 2. 設無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發進行深度優先遍歷可以得到的一種頂點序列為（ ）。 設一棵三叉樹中有2個度數為1的結點，2個度數為2的結點，2個度數為3的結點，則該三叉鏈權中有（ ）個度數為0的結點。 設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為（ ）。 設一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為( )。 在二叉排序樹中插入一個關鍵字值的平均時間復雜度為（ ）。 設某散列表的長度為100，散列函數H(k)=k % P，則P通常情況下最好選擇（ ）。 兩個字符串相等的充要條件是（ ）。 else level(btrchild,x)。 設計求結點在二叉排序樹中層次的算法。}}3. 3.void substring(char s[ ], long start, long count, char t[ ]){ long i,j,length=strlen(s)。 for(p=qnext。void simpleselectsorlklist(lklist *amp。 510. 10. (12，18，24，27，35，26)9. 9. (12，24，35，27，18，26)8. 8. 2h1，2h17. 7. 146. 6. 開放定址法，鏈地址法5. 5. n/24. 4. n(n1)，n(n1)/23. 3. sleft=p，pright2. 2.三、填空題1. 1.}amp。struct record {int key。（ ）9．線性表中的所有元素都有一個前驅元素和后繼元素。二、判斷題(20分)1．不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。 (A) head==0 (B) headnext==0