網(wǎng)絡(luò)工程數(shù)據(jù)結(jié)構(gòu)試卷及答案

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