華東交通大學數據結構試卷

1、華東交通大學20112012 學年第一學期考試卷試卷編號：（A）卷數據結構課程題號一二題號一二三42四8五六七八九十題分得分2030總分累分人簽名100課程類別：必考試日期：考生注意事項：一、本試卷共4 頁，總分100分，考試時刻120二、考試終止后，考生不得將試卷、答題紙和草稿紙帶出考場。3、答案必需寫在答題紙上，考試終止時請將答題紙與試卷分開上交，試卷、答題紙、草稿紙都必需交回。得分評閱人一、選擇題(每題2分，共20分)得分評閱人運算機算法必需具有輸入、輸出（）5 個 特 性 。A可行性、可移植性和可擴充性B. 有窮性、確信性、可行C.確信性、有窮性和穩(wěn)固性D. 可讀性、穩(wěn)固性和平安性在長

2、度為n的順序表的第i個元素（1=inext=s;s-next=p-next;Bs-next=p-next;p-next=s;Cp-next=s;p-next=s-next;D. p-next=s-next;p-next=s;判別表達式中左、右括號是不是配對顯現的算法，采納（）數據結構最正確A隊列B線性表C棧D雙向鏈表包括2021個極點的連通圖最少有（）條邊。A.2020B.2012C.2013D.20146.在有序表4，15，26，27，38，64，81中折半查找38的比較次數為（。A1B2C3D4線索鏈表中，假設結點p的RTag=1，那么p-rchild指向（。左小孩B.右小孩C.前驅D.后

3、繼對完全二叉樹按層序從1開始編號，編號為100的結點是編號為50的結點的（。左小孩B.右孩子C. 雙親D.根結點102426110242614196153115543C. 31D. 35順序查找的時刻復雜度為（）AO(n/2)BO(n)CO(1)DO(log2n)得分評閱人二、填空題(每題2分，共30分)得分評閱人數據結構中評判算法的兩個重要指標是算法的(1)和空間復雜度。鏈接存儲的特點是利用(2)來表示數據元素之間的邏輯關系。假設有5行4列的二維數組每一個元素占用6個字節(jié)存儲器按字節(jié)編址已知A00 的地址為1000，按行優(yōu)先存儲時元素A23的地址是(3)。帶頭結點的單鏈表L中，L-next-

4、next表示第（4）個數據元素。假設用一個大小為8的數組來實現循環(huán)隊列且當前rear和front的值別離為0和當隊列中刪除一個元素，再加入兩個元素后，rear的值為(5)，front的值為(6)。SubString(HAPPYNEWYEAR,6,3）=（7）。267(8) ，有(9) 個葉子結點。以下代碼片段中，k+的執(zhí)行次數為(10) 。BABACEDF72，31那么度為0的結點個數是_(11)。右圖的一個拓撲排序序列為A（12）EF。帶頭結點的循環(huán)鏈表中最后一個結點的指針域指向（13）。順序表第(14)個數據元素的存儲位置稱為基地址。具有3個結點的二叉樹有（15）種不同形態(tài)。填空題10圖得

5、分評閱人三、綜合題 （每題 6 分，共 42 分）得分評閱人12345，4523132451push（X） IGDBEHFCA,DIGBAECFH,對應的叢林。2021變情形。A12BA12B20C4891215EFGD610寫出用克魯斯卡爾算法構造最小生成樹進程中每一步選擇的邊。假設用于通信的電文由 6 個字母 A,B,C,D,E,F 組成，字母在電文中顯現的頻率別離為,。試為這6個字母設計哈夫曼樹（權值小的作為左子樹。v00320321465127718361735624得分評閱人四、算法題 （共 8 分）得分評閱人L ie返回其值。用編程語言概念單鏈表的存儲結構（3分）用編程語言概念函數實現上述功能（5分）華東交通大學20112012 學年第一學期考試卷試卷編號：（A數據結構課程課程類別：必閉卷考試日期：題號一題分20得分三428五六七八九十總累分人簽名一、選擇題（2 20 分）12345678910得分評閱人二、填空題（每空 2 分，共 30 分）得分評閱人123456789101112131415三、綜合題（6