華東交通大學數據結構歷年考試

個人收集整理僅供參考學習受華東交通大學2011—2012學年第一學期考試卷弊作因和試卷編號：（A）卷籍學數據結構課程課程類別：必除開閉卷考試日期：2012.1被將題號一二三四五六七八九十總分者累分人簽名考題分2030428100人：他名代得分或簽考生代學考生注意事項：1、本試卷共4頁，總分100分，考試時間120分鐘.人他2、考試結束后，考生不得將試卷、答題紙和草稿紙帶出考場.請3、答案必須寫在答題紙上，考試結束時請將答題紙與試卷分開上交，試卷、答題紙、草稿紙道都必須交回.知.還果一、選擇題(每題2分，共20分)，后得分評閱人性切號1.計算機算法必須具備輸入、輸出（）5個特性.重一A．可行性、可移植性和可擴充性B.有窮性、確定性、可行性嚴地學地起C.確定性、有窮性和穩(wěn)定性D.可讀性、穩(wěn)定性和安全性弊引作此2.在長度為n地順序表地第i個元素（1<=i<=n）之前插入數據元素時，需向后移動（）個元素.、由紀擔A．n-i+1B.n-iC.iD.n違承試愿3.在單鏈表指針為p地結點之后插入指針為s地結點，正確地操作是：（）.考，A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;道位級b5E2RGbCAP知學C．p->next=s;p->next=s->next;D.p->next=s->next;p->next=s;p1EanqFDPw班，士律學4.判別表達式中左、右括號是否配對出現地算法，采用（）數據結構最佳.紀予場授A．隊列B．線性表C．棧D．雙向鏈表考不守將5．包含2012個頂點地連通圖最少有（）條邊.遵分格處A.2011B.2012C.2013D.2014嚴上將以6.在有序表{4，15，26，27，38，64，81}中折半查找38地比較次數為（）.我及A．1B．2C．3D．4：過業(yè)諾記承到專7.線索鏈表中，若結點p地RTag=1，則p->rchild指向（）.A.左孩子B.右孩子C.前驅D.后繼8.對完全二叉樹按層序從1開始編號，編號為100地結點是編號為50地結點地（）.A.左孩子B.右孩子C.雙親D.根結點9．下圖AOE網絡中，要完成該工程需要（）時間.1/9個人收集整理 僅供參考學習2104261 4 19 61511553A.43B.18C.31D.3510．順序查找地時間復雜度為（）A．O(n/2)B．O(n)C．O(1)D．O(log2n)DXDiTa9E3d得分 評閱人二、填空題(每題2分，共30分)1．數據結構中評價算法地兩個重要指標是算法地 (1) 和空間復雜度.鏈接存儲地特點是利用(2)來表示數據元素之間地邏輯關系.假設有5行4列地二維數組A，每個元素占用6個字節(jié)，存儲器按字節(jié)編址.已知A[0][0]地地址為1000，按行優(yōu)先存儲時元素A[2][3]地地址是(3).RTCrpUDGiT4．帶頭結點地單鏈表 L中，L->next->next 表示第（4） 個數據元素.5．若用一個大小為8地數組來實現循環(huán)隊列，且當前rear和front地值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear地值為(5)，front地值為(6).5PCzVD7HxA6.SubString(‘HAPPYNEWYEAR’,6,3）=（7）.7．一棵具有267個結點地完全二叉樹，它地深度為(8)，有(9)個葉子結點.8．以下代碼片段中，k++地執(zhí)行次數為(10).for(inti=0;i<n;i++)for(intj=0;j<n;j++)k++;B9．若一棵二叉樹具有7個度為2地結點，3個度為1地結點，則度為0地結點個數是_(11).10．右圖地一個拓撲排序序列為A（12）EF.ACE帶頭結點地循環(huán)鏈表中最后一個結點地指針域指向（13）.DF12.順序表第(14)個數據元素地存儲位置稱為基地址.13.具有3個結點地二叉樹有（15）種不同形態(tài).填空題10圖三、綜合題（每題6分，共42分）得分評閱人1．進棧順序為12345，問能否得到45231和32451地出棧序列？以push（X）表示進棧和以pop（X）表示出棧地操作序列，說明為什么不能或如何能得到.jLBHrnAILg2/9個人收集整理 僅供參考學習已知一棵二叉樹地后序序列為IGDBEHFCA,中序序列為DIGBAECFH,直接畫出此二叉樹并畫出對應地森林.xHAQX74J0X用教材中給出地數值轉換算法將十進制數2012轉換成八進制數，并畫出轉換過程中棧地變化情況.4．給定下列網G:12 20A B C4 8 9 12 15E F G D6 10寫出用克魯斯卡爾算法構造最小生成樹過程中每一步選擇地邊 .5．假設用于通信地電文由 6個字母A,B,C,D,E,F組成，字母在電文中出現地頻率分別為 0.17,0.12,0.05,0.28,0.35, 0.03.試為這6個字母設計哈夫曼樹（權值小地作為左子樹）.LDAYtRyKfE6．記錄地關鍵字序列為：56，90，27，67，56，10，88，試構造一棵二叉排序樹，并寫出其構造過程.Zzz6ZB2Ltk7．利用迪杰斯特拉算法依次求出下圖中從頂點 v0到其他各頂點間地最短路徑 .032146517220718361735243/9個人收集整理 僅供參考學習四、算法題 （共8分）得分 評閱人實現帶頭結點地單鏈表L中，刪除第i個元素，并由e返回其值.（1）用編程語言定義單鏈表地存儲結構（ 3分）（2）用編程語言定義函數實現上述功能（ 5分）4/9個人收集整理僅供參考學習受華東交通大學2011—2012學年第一學期考試卷dvzfvkwMI1弊作因試卷編號：（A）卷和籍數據結構課程課程類別：必學除閉卷考試日期：2012.1開被題號一二三四五六七八九十總分將累分人簽名者題分2030428100考人：他得分名代或簽考生代學一、選擇題（每題人他請123道知.還果，后性切重一號嚴地學地起二、填空題（每空弊引作此、由1紀擔違承3試愿考，5道位級知學班，士7律學紀予9場授考不11守將遵分格處13嚴上將以15我及：過業(yè)諾記承到專

分，共20分）45678910得分評閱人2分，共30分）得分 評閱人2468101214三、綜合題（每題 6分，共42分）1、

得分 評閱人1/9個人收集整理 僅供參考學習2、3、(2012)=()810棧（左邊為棧底）12344、邊地頂點1 邊地頂點2 權值1234562/9個人收集整理 僅供參考學習5、6、7、路徑1234563/9個人收集整理 僅供參考學習四、算法題 （共8分）得分 評閱人版權申明本文部分內容，包括文字、圖片、以及設計等在網上搜集整理 .版權為個人所有Thisarticle includes someparts, including text, pictures, anddesign.Copyrightispersonalownership. rqyn14ZNXI用戶可將本文地內容或服務用于個人學習、研究或欣賞，以及其他非商業(yè)性或非盈利性用途，但同時應遵守著作權法及其他相關法律地規(guī)定，不得侵犯本網站及相關權利人地合法權利.除此以外，將本文任何內容或服務用于其他用途時，須征得本人及相關權利人地書面許可，并支付報酬.EmxvxOtOcoUsersmayusethecontentsorservicesofthisarticleforpersonalstudy,researchorappreciation,andothernon-commercialornon-profitpurposes,butatthesametime,theyshallabidebytheprovisionsofcopyrightlawandotherrelevantlaws,andshallnotinfringeuponthelegitimaterightsofthiswebsiteanditsrelevantobligees.Inaddition,whenanycontentorserviceofthisarticleisusedforotherpurposes,writtenpermissionandremunerationshallbeobtainedfromtheperson4/9個人收集整理 僅供參考學習concernedandtherelevantobligee. SixE2yXPq5轉載或引用本文內容必須是以新聞性或資料性公共免費信息為使用目地地合理、善意引用，不得對本文內容原意進行曲解、修改，并自負版權等法律責任.6ewMyirQFLReproductionorquotationofthecontentofthisarticlemustbereasonableandgood-faithcitation