數(shù)據(jù)結構期中試卷及答案(編輯修改稿)
2024-11-19 01:34 本頁面
【文章內(nèi)容簡介】 該算法的功能是：將開始結點摘下鏈接到終端結點之后成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鏈表的頭指針。四、算法設計題（每題14分，共42分），且表中既無頭結點也無頭指針，已知p為指向鏈表中某結點的指針，設計在鏈表中刪除p所指結點的前趨結點的算法。解：可引入一個指針q，當qnext=p時，說明此時q所指的結點為p所指結點的前趨結點，從而可得算法如下：void delete(LinkList *p){ //在鏈表中刪除p所指結點的前趨結點 LinkList *q,*t。q=p。while(qnextnext!=p)//qnext不是p的前趨結點（第2頁，共3頁）q=qnext。t=qnext。//t指向要刪除結點qnext=p。//刪除t結點free(t)。｝，且以帶頭結點的單鏈表作為存儲結構。設計一個刪除表中所有值小于max但大于min的元素的算法。2．算法描述如下：delete(LinkList *head, int max, int min){ LinkList *p,*q。q=head。p=headnext。while(p!=NULL)if((pdatadata=max)){ q=p。p=pnext。} else { qnext=pnext。free(p)。p=qnext。} }。試寫一個算法，對一個通常書寫形式且書寫正確的表達式求值。（第3頁，共3頁）第三篇：數(shù)據(jù)結構試卷(一)及答案數(shù)據(jù)結構試卷（一）一、選擇題（20分）1．組成數(shù)據(jù)的基本單位是（）。(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量2．設數(shù)據(jù)結構A=(D，R)，其中D={1，2，3，4}，R={r}，r={，，}，則數(shù)據(jù)結構A是（）。(A)線性結構(B)樹型結構(C)圖型結構(D)集合 3．數(shù)組的邏輯結構不同于下列（）的邏輯結構。(A)線性表(B)棧(C)隊列(D)樹 4．二叉樹中第i(i≥1)層上的結點數(shù)最多有（）個。ii1(A)2i(B)2(C)2(D)2i1 5．設指針變量p指向單鏈表結點A，則刪除結點A的后繼結點B需要的操作為（）。(A)pnext=pnextnext(B)p=pnext(C)p=pnextnext(D)pnext=p 6．設棧S和隊列Q的初始狀態(tài)為空，元素EEEEE5和E6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出列的順序為EEEEE5和E1，則棧S的容量至少應該是（）。(A)6(B)4(C)3(D)2 7．將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為（）。(A)100(B)40(C)55(D)80 8．設結點A有3個兄弟結點且結點B為結點A的雙親結點，則結點B的度數(shù)數(shù)為（）。(A)3(B)4(C)5(D)1 9．根據(jù)二叉樹的定義可知二叉樹共有（）種不同的形態(tài)。(A)4(B)5(C)6(D)7 ，則（）的空間復雜度最大。(A)冒泡排序(B)快速排序(C)堆排序(D)希爾排序二、填空題(30分)[0：m1]的隊頭指針和隊尾指針分別為F和R，其中隊頭指針F指向當前隊頭元素的前一個位置，隊尾指針R指向當前隊尾元素所在的位置，則出隊列的語句為F =____________。，則在順序存儲結構上實現(xiàn)順序查找的平均時間復雜度為___________，在鏈式存儲結構上實現(xiàn)順序查找的平均時間復雜度為___________。，則當用二叉鏈表作為其存儲結構時，該二叉鏈表中共有________個指針域，__________個空指針域。，指針變量s指向被插入的結點B，則在結點A的后面插入結點B的操作序列為______________________________________。，則其對應的鄰接表中有_________個表頭結點和_________個表結點。，所有頂點的度數(shù)之和為m，則e和m有______關系。，則該二叉樹的后序遍歷序列為__________。，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結點的編號是___________，編號為8的左孩子結點的編號是_____________。，要求在下劃線處填上正確語句。int index(char s[ ], char t[ ]){ i=j=0。while(i三、應用題（30分）1．設完全二叉樹的順序存儲結構中存儲數(shù)據(jù)ABCDE，要求給出該二叉樹的鏈式存儲結構并給出該二叉樹的前序、中序和后序遍歷序列。2．設給定一個權值集合W=(3，5，7，9，11)，要求根據(jù)給定的權值集合構造一棵哈夫曼樹并計算哈夫曼樹的帶權路徑長度WPL。3．設一組初始記錄關鍵字序列為(19，21，16，5，18，23)，要求給出以19為基準的一趟快速排序結果以及第2趟直接選擇排序后的結果。4．設一組初始記錄關鍵字集合為(25，10，8，27，32，68)，散列表的長度為8，散列函數(shù)H(k)=k mod 7，要求分別用線性探測和鏈地址法作為解決沖突的方法設計哈希表。5．設無向圖G（所右圖所示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。四、算法設計題(20分)。數(shù)據(jù)結構試卷（一）參考答案一、選擇題 二、填空題 1.(F+1)% m (n)，O(n)，n+1 next=pnext。snext=s , 2e =2e ，16 +1，0 三、應用題，前序ABDEC，中序DBEAC，后序DEBCA。，WPL=78 3.(18,5,16,19,21,23)，(5，16，21，19，18，23)h0h1： 鏈地址法：h310L8L1025322768h42532h568h6：125364，廣度：123456，最小生成樹T的邊集為E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)}四、算法設計題
范文總結相關推薦
鄂ICP備17016276號-1