華東交通大學(xué)數(shù)據(jù)結(jié)構(gòu)歷年考試

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

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

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