總分所在班級注意核分人數據結構試題題號一二三總分所在班級注意核分人數據結構試題題號一二三四五總分題分2030428得分（10計算機本科）（120分鐘）一、密封線內不準答題。二、姓名、學號、班級不許涂改，否則試卷無效。三、考生在答題前應先將姓名、學號和班級填寫在在指定的方框內。四、試卷印刷不清楚，可舉手向監考教師詢問。卷號?湖北工業大學二。。一一/二。一二學年第一學期模擬考試注意：學號、姓名和所在班級不寫、不寫全或寫在密封線外者，試卷作廢。一、填空題（每小題2分，共20分）1、設連通圖G中的邊集E={（a，b），（a，e），（a，c），（b，e），（e，d），（d，f），（f，c）}，則從頂點a出發可以得到一種深度優先遍歷的頂點序列為abedfc。（結果不唯一）2、設一組記錄關鍵字序列為（80，70，33，65，24，56，48），則用篩選法建成的初始堆為（24，65，33，80，70，56，48）。3、對一組初始關鍵字序列（40，50，95，20，15，70，60，45，10）進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數為__8，在整個排序過程中最多需要進行6―趟排序才可以完成。4、設一組初始記錄關鍵字序列為（49,38，65，97，76，13，27，50），則以d=4為增量的一趟希爾排序結束后的結果為（49,13,27,50，76,38,65,97）__。5、設一組初始記錄關鍵字序列為（20,18,22,16,30,19）,則根據這些初始關鍵字序列建成的初始堆為（16,18,19,20,32,22）。6、設有向圖G的存儲結構用鄰接矩陣A來表示，則A中第i行中所有非零元素個數之和等于頂點i的—出度,第i列中所有非零元素個數之和等于頂點i的入度。7、在快速排序、堆排序、歸并排序中，―歸并排序是穩定的。（冒泡、插入、歸并和基數排序是穩定的；選擇、快速、希爾和堆排序是不穩定的。）8、設查找表中有100個元素，如果用二分法查找方法查找數據元素X,則最多需要比較7次就可以斷定數據元素X是否在查找表中。9、簡單選擇排序和直接插入排序算法的平均時間復雜度為一O（n2）10、解決散列表沖突的兩種方法是開放地址法—和—鏈地址法二、選擇題（每題2分，共30分）1、下列程序段的時間復雜度為（）。i=0,s=0；while（s<n）{s=s+i；i++；}A.O（n1/2）B.O（n1/3）C.O（n）D.O（n2）2、設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B,T1、T2和T3的結點數分別為N1、N2和N3，則二叉樹B的根結點的左子樹的結點數為（）。A.N1-1B.N2-1C.N2+N3D.N1+N33、設有一個二維數組A[m][n]，假設A[0][0]存放位置在644,A⑵⑵存放位置在TOC\o"1-5"\h\z676,每個元素占一個空間，問A[3][3]存放位置是（）A.688B.678C.692D.6964、設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為（）。A.9B.10C.11D.125、設一組初始記錄關鍵字序列（5,2,6,3,8）,以第一個記錄關鍵字5為基準進行一趟快速排序的結果為（）。A.2,3,5,8,6B.3,2,5,8,6C.3,2,5,6,8D.2,3,6,5,86、對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為（）A.O（1）B.O（n）C.O（1og2n）D.O（n2）7、若有18個元素的有序表存放在一維數組A[19]中，第一個元素放A[1]中，現進行二分查找，則查找A[3]的比較序列的下標依次為（）A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,38、設某哈夫曼樹中有199個結點，則該哈夫曼樹中有（）個葉子結點。A.99B.100C.101D.1029、設順序表的長度為99,則順序查找的平均比較次數為（）。A.99B.49.5C.50D.4910、設有序表中的元素為（13,18,24,35,47,50,62），則在其中利用二分法查找值為24的元素需要經過（）次比較。A.1B.2C.3D.411、設順序線性表的長度為30,分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為（）。A.6B.11C.5D.6.512、設無向圖中有n個頂點，則該無向圖中最多有（）條邊。A.n（n-1）/2B.n（n-1）C.n（n+1）/2D,（n-1）/213、設某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。A.BADCB.BCDAC.CDABD.CBDA14、設有向無環圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓撲排序序列的是（）。A,1，2，3，4B.2，3，4，1深度優先遍歷序列和寬度優先遍歷序列應是唯一的。（3）由于本題的圖不好畫，C,1，4，2，3D.1，2，4，315、設一組初始關鍵字記錄關鍵字為（20，15，14，18，21，36，40，10），則以20為基準記錄的一趟快速排序結束后的結果為（）。A.10，15,14,18,20,36,40,21B.10，15,14,18,20,40,36,21C.10，15,14,20,18,40,36,2lD.15,10，14,18,20,36,40,21我給一個相似的題目的答案，三、應用題（本大題共7小題，每小題6分，共42分）1、設無向圖G（如圖所示），要求：（1）求該圖的深度優先遍歷序列。（2）求該圖的寬度優先遍歷序列。（3）根據Prim算法求該圖的最小生成樹。（4）根據克魯斯卡爾算法求該圖的最小生成樹。（5）以上算法都可得到生成樹，各有什么特點？（4）由于本題的圖不好畫，我給一個相似的題目的答案，大家參考一下，抱歉。(c)（1）假設以1為起點：1>2>3>4>5（或1>4>3>5>2,1>5>4>3>2等等）（2）假設以1為起點：12543或1XXX3,三個X為2、5、4任意的一個序列，3必須在最后）注意：（1）、（2）兩個問題在不要求畫鄰接表或鄰接矩陣時，其結果可以不唯一，但一旦要求畫鄰接表或鄰接矩陣時，根據你畫的鄰接表或鄰接矩陣所得到的（5）深度優先遍歷序列和寬度優先遍歷序列得到的生成樹不一定是最小生成樹，普里姆和克魯斯卡爾算法可以得到最小生成樹，克魯斯卡爾算法構造最小生成樹的時間復雜度降為O（elog2e）。由于它與n無關，只與e有關，所以說克魯斯卡爾算法適合于稀疏圖。Prim（）算法中有兩重for循環，所以時間復雜度為O（n2），由于它與它與n有關，只與e無關，故適合稠密網。2、設有一組初始記錄關鍵字為（45,80,48,40,22,78）,要求:（1）構造一棵二叉排序樹并給出構造過程；（2）插入結點44,41,70,66，畫出每插入一個結點的二叉排序樹。（3）刪除結點45,40,78，畫出每刪除一個結點的二叉排序樹。（4）計算該二叉排序樹的平衡因子。3、如下圖所示，要求：（1）寫出該樹的前序、中序、后序遍歷。（2）樹的度是多少？樹的深度是多少？以結點B為根的子樹的深度是多少?（3）度為0、1、2的結點分別是哪些？（4）畫出與下列二叉樹對應的森林。（5）求該森林的前序遍歷和后序遍歷。后序：GJIKFDCABE（2）樹的度為2,深度為5,（3）度為0的結點有G、K、以結點B為根的子樹的深度是4。F、D；度為1的結點有I、J、A；度為2的結點有=3，H（78）=0,H（31）=5,H（15）=2,H（36）=10利用線性探查法造表：E、B、C。0123456789101112781503574520312336121111114121（5）該森林的前序遍歷：EIJGBKACFD該森林的后序遍歷：IGJEKBFCDA寫出下面程序的結果。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=p;q!=0;)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{s=q,q=q->next;}}}答：在不帶頭結點的單鏈表中刪除值相同數據元素的算法。(原始卷中s=q要改為s=p，另外標注紅色的0其實就是NULL）5、設散列表為HT[13],散列函數為H（key）=key%13。用閉散列法解決沖突，對下列關鍵碼序列12,23,45,57,20,03,78,31,15,36造表。（1）采用線性探查法尋找下一個空位，畫出相應的散列表。（2）計算等概率下搜索成功的平均搜索長度和搜索不成功的平均搜索長度。答案：使用散列函數H（key）二keymod13有：H（12）=12，H（23）=10，H（45）=6,H（57）=5,H（20）=7,H（03）搜索成功的平均搜索長度為：ASL=1/10（1+1+1+1+1+1+4+1+2+1）=14/10搜索不成功的平均搜索長度為：AS、。=1/13（2+1+3+2+1+5+4+3+2+1+5+4+3）=36/136、假設用于通信的電文由字符集｛a,b,c,d,e,f,g｝中的字母構成。它們在電文中出現的頻度分別為｛0.31,0.16,0.10,0.08,0.11,0.20,0.04｝,（1）畫出哈夫曼樹。（2）求WPL。（3）為這7個字母設計哈夫曼編碼；（4）對這7個字母進行等長編碼，至少需要幾位二進制數？（5）哈夫曼編碼比等長編碼使電文總長壓縮多少？a:11;b:101;c:010;d:1001;e:011;f:00;g:1000對這7個字母進行等長編碼，至少需要3位二進制數。0.31+0.08+0.10+0.11+0.16+0.04+0.20=1

(0.31*2+0.20*2+0.10*3+0.11*3+0.16*3+0.04*4+0.08*4)/3=87%壓縮了13%7、設有序順序表中的元素依次為017,094,154,170,275,503,509,512,553,612,677,765,897,908。試畫出對其進行折半搜索時的判定樹。并計算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。若有n個有序數據元素，則查找不成功最大查找深度為多少？答案：折半搜索時的判定樹為：ASL=1/14(1+2*2+3*4+4*7)=45/14ASL；\=1/15(3*1+4*14)=59/15

elseif(p->data>='0'&&p->data<='9'){p->next=hb;hb=p;}{p->next=hc;hc=p;}}else}else若有N個有序數據元素，則查找不成功最大查找深度為ceiling(log2N)+1,ceiling()表示天花板函數，也可以是floor(log2(N+1))+1，floor()是地板函數四、算法設計題(本大題共1小題，每小題8分，共8分)1、設單鏈表中有僅三類字符的數據元素(大寫字母、數字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。type