數據結構試題及答案免費(編輯修改稿)

　

【文章內容簡介】 雙向循環鏈表3．設指針q指向單鏈表中結點A，指針p指向單鏈表中結點A的后繼結點B，指針s指向被插入的結點X，則在結點A和結點B插入結點X的操作序列為（ ）。(A) snext=pnext；pnext=s； (B) qnext=s； snext=p；(C) pnext=snext；snext=p； (D) pnext=s；snext=q；4．設輸入序列為6，則通過棧的作用后可以得到的輸出序列為（ ）。(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，35．設有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續的55個存儲單元中，每個數組元素占1個字節的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（ ）。 (A) 10 (B) 19 (C) 28 (D) 556．設一棵m叉樹中有N1個度數為1的結點，N2個度數為2的結點，……，Nm個度數為m的結點，則該樹中共有（ ）個葉子結點。 (A) (B) (C) (D) 7. 二叉排序樹中左子樹上所有結點的值均（ ）根結點的值。 (A) (B) (C) = (D) !=8. 設一組權值集合W=(15，3，14，2，6，9，16，17)，要求根據這些權值集合構造一棵哈夫曼樹，則這棵哈夫曼樹的帶權路徑長度為（ ）。 (A) 129 (B) 219 (C) 189 (D) 2299. 設有n個關鍵字具有相同的Hash函數值，則用線性探測法把這n個關鍵字映射到HASH表中需要做（ ）次線性探測。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n1)/2，則這棵二叉中共有（ ）個結點。 (A) 2n (B) n+l (C) 2n1 (D) 2n+l ，則最多經過（ ）趟插入排序可以得到有序序列。 (A) 6 (B) 7 (C) 8 (D) 9(Q，H，C，Y，P，A，M，S，R，D，F，X)，則按字母升序的第一趟冒泡排序結束后的結果是（ ）。(A) F，H，C，D，P，A，M，Q，R，S，Y，X(B) P，A，C，S，Q，D，F，X，R，H，M，Y(C) A，D，C，R，F，Q，M，S，Y，P，H，X(D) H，C，Q，P，A，M，S，R，D，F，X，Y二、填空題(48分，其中最后兩小題各6分)1. 1. 設需要對5個不同的記錄關鍵字進行排序，則至少需要比較_____________次，至多需要比較_____________次。2. 2. 快速排序算法的平均時間復雜度為____________，直接插入排序算法的平均時間復雜度為___________。3. 3. 設二叉排序樹的高度為h，則在該樹中查找關鍵字key最多需要比較_________次。4. 4. 設在長度為20的有序表中進行二分查找，則比較一次查找成功的結點數有_________個，比較兩次查找成功有結點數有_________個。5. 5. 設一棵m叉樹脂的結點數為n，用多重鏈表表示其存儲結構，則該樹中有_________個空指針域。6. 6. 設指針變量p指向單鏈表中結點A，則刪除結點A的語句序列為：q=pnext；pdata=qdata；pnext=___________；feee(q)；7. 7. 數據結構從邏輯上劃分為三種基本類型：___________、__________和___________。8. 8. 設無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結構進行深度優先或廣度優先遍歷時的時間復雜度為_________；用鄰接表作為圖的存儲結構進行深度優先或廣度優先遍歷的時間復雜度為_________。9. 9. 設散列表的長度為8，散列函數H(k)=k % 7，用線性探測法解決沖突，則根據一組初始關鍵字序列(8，15，16，22，30，32)構造出的散列表的平均查找長度是________。10. 10. 設一組初始關鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結束后的結果為_____________________。11. 11. 設一組初始關鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的結果為______________________。12. 12. 設有向圖G中的有向邊的集合E={1，2，2，3，1，4，4，5，5，3，4，6，6，5}，則該圖的一個拓撲序列為_________________________。13. 13. 下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內容。typedef struct node{int data。struct node *lchild。________________。}bitree。void createbitree(bitree *amp。bt){scanf(“%c”,amp。ch)。if(ch==39。39。) ___________。else{ bt=(bitree*)malloc(sizeof(bitree))。 btdata=ch。 ________。createbitree(btrchild)。}}14. 14. 下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內容。typedef struct node {int data。 struct node *next。} lklist。 void lklistcreate(_____________ *amp。head ){ for (i=1。i=n。i++){ p=(lklist *)malloc(sizeof(lklist))。scanf(“%d”,amp。(pdata))。pnext=0。if(i==1)head=q=p。else {qnext=p。____________。}} }三、算法設計題(22分)1． 1． 設計在鏈式存儲結構上合并排序的算法。2． 2． 設計在二叉排序樹上查找結點X的算法。3． 3． 設關鍵字序列(k1，k2，…，kn1)是堆，設計算法將關鍵字序列(k1，k2，…，kn1，x)調整為堆。數據結構試卷（14）參考答案一、選擇題1．A 2．D 3．B 4．B 5．B 6．D7．A 8．D 9．D 10．C 11．B 12．D二、填空題1. 1. 4，102. 2. O(nlog2n)，O(n2)3. 3. n4. 4. 1，25. 5. n(m1)+16. 6. qnext7. 7. 線性結構，樹型結構，圖型結構8. 8. O(n2)， O(n+e)9. 9. 8/310. 10. (38，13，27，10，65，76，97)11. 11. (10，13，27，76，65，97，38)12. 12. 12465313. 13. struct node *rchild，bt=0，createbitree(btlchild)14. 14. lklist，q=p三、算法設計題1. 1. 設計在鏈式存儲結構上合并排序的算法。void mergelklist(lklist *ha,lklist *hb,lklist *amp。hc){ lklist *s=hc=0。 while(ha!=0 amp。amp。 hb!=0) if(hadatahbdata){if(s==0) hc=s=ha。 else {snext=ha。 s=ha。}。ha=hanext。} else {if(s==0) hc=s=hb。 else {snext=hb。 s=hb。}。hb=hbnext。} if(ha==0) snext=hb。 else snext=ha。}2. 2. 設計在二叉排序樹上查找結點X的算法。bitree *bstsearch1(bitree *t, int key){ bitree *p=t。 while(p!=0) if (pkey==key) return(p)。else if (pkeykey)p=plchild。 else p=prchild。 return(0)。}3. 3. 設關鍵字序列(k1，k2，…，kn1)是堆，設計算法將關鍵字序列(k1，k2，…，kn1，x)調整為堆。void adjustheap(int r[ ],int n){ int j=n,i=j/2,temp=r[j1]。 while (i=1) if (temp=r[i1])break。 else{r[j1]=r[i1]。 j=i。 i=i/2。} r[j1]=temp。}數據結構（十五）一、 單選題（每題 2 分，共20分）1. 1. 對一個算法的評價，不包括如下（B ）方面的內容。 A．健壯性和可讀性 B．并行性 C．正確性 D．時空復雜度2. 2. 在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針p指向的結點，則執行( )。 A. pnext=HLnext。 HLnext=p。 B. pnext=HL。 HL=p。 C. pnext=HL。 p=HL。 D. HL=p。 pnext=HL。3. 3. 對線性表，在下列哪種情況下應當采用鏈表表示？( ) 4. 4. 一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. AOV網是一種（ ）。 A．有向圖 B．無向圖 C．無向無環圖 D．有向無環圖6. 6. 采用開放定址法處理散列表的沖突時，其平均查找長度（ ）。A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找7. 7. 若需要利用形參直接訪問實參時，應將形參變量說明為（ ）參數。A．值 B．函數 C．指針 D．引用8. 8. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有相同的（ ）。A．行號 B．列號 C．元素值 D．非零元素個數9. 9. 快速排序在最壞情況下的時間復雜度為（ ）。A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10. 10. 從二叉搜索樹中查找一個元素時，其時間復雜度大致為( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)二、 二、 運算題（每題 6 分，共24分）1. 1. 數據結構是指數據及其相互之間的______________。當結點之間存在M對N（M：N）的聯系時，稱這種結構為_____________________。2. 2. 隊列的插入操作是在隊列的___尾______進行，刪除操作是在隊列的____首______進行。3. 3. 當用長度為N的數組順序存儲一個棧時，假定用top==N表示棧空，則表示棧滿的條件是___top==0___(要超出才為滿)_______________。4. 4. 對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復雜度為_________，在表尾插入元素的時間復雜度為____________。5. 5. 設W為一個二維數組，其每個數據元素占用4個字節，行下標i從0到7 ，列下標j從0到3 ，則二維數組W的數據元素共占用＿_____＿個字節。W中第6 行的元素和第4 列的元素共占用＿_______＿個字節。若按行順序存放二維數組W，其起始地址為100，則二維數組元素W[6，3]的起始地址為＿________＿。6. 6. 廣義表A= (a,(a,b),((a,b),c)),則它的深度為____________，它的長度為____________。7. 7. 二叉樹是指度為2的____________________樹。一棵結點數為N的二叉樹，其所有結點的度的總和是_____________。8. 8. 對一棵二叉搜索樹進行中序遍歷時，得到的結點序列是一個______________。對一棵由算術表達式組成的二叉語法樹進行后序遍歷得到的結點序列是該算術表達式的__________________。9. 9. 對于一棵具有n個結點的二叉樹，用二叉鏈表存儲時，其指針總數為_____________個，其中_______________個用于指向孩子，___________