2018年浙江理工大學(xué)938數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫技術(shù)考研專業(yè)課真題分享

1、第1頁，共7頁浙江理工大學(xué)20182018年碩士研究生招生考試初試試題年碩士研究生招生考試初試試題考試科目：數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫技術(shù)考試科目：數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫技術(shù)代碼：代碼：938（請(qǐng)考生在答題紙上答題，在此試題紙上答題無效）（請(qǐng)考生在答題紙上答題，在此試題紙上答題無效）第一部分：數(shù)據(jù)結(jié)構(gòu)（本部分共第一部分：數(shù)據(jù)結(jié)構(gòu)（本部分共9090分）分）一、單項(xiàng)選擇題一、單項(xiàng)選擇題（每小題每小題3分，本題共分，本題共36分)1.下列程序段所代表的算法的

2、時(shí)間復(fù)雜度為。i=1while(irearnext==HQfront(B)HQfrontnext==HQrear(C)HQfront==HQrear(D)HQfrontnext==HQrearnext5.在一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行的操作為。(A)HSnext=ssnext=HSnext(B)snext=HSnextHSnext=s(C)snext=HSHS=s(D)snext=HSHS=HSnext6.有一組數(shù)

3、值1321321726，用以構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度WPL值為。(A)241(B)248(C)252(D)2707.假設(shè)結(jié)點(diǎn)序列為5030906095704818，以此構(gòu)成一棵二叉排序樹，則在該二叉排序樹上查找一個(gè)結(jié)點(diǎn)的平均查找長度為。(A)114(B)214(C)198(D)528.假定對(duì)共有144個(gè)元素的線性表進(jìn)行分塊查找，若將表均勻地分為x塊（每塊元素個(gè)數(shù)相同）。假設(shè)塊查找和塊內(nèi)查找均采用順序查找法，則在等概率情況下，若要使

4、分塊查找的平均查找長度ASL最小，則分塊數(shù)x的值應(yīng)為。(A)11(B)12(C)13(D)149.已知一個(gè)帶權(quán)圖的頂點(diǎn)集V和邊集G分別如下，則該圖的最小生成樹的權(quán)值為。第3頁，共7頁2.下列程序在單鏈表head上實(shí)現(xiàn)簡單選擇排序算法，其中調(diào)用函數(shù)GetMinKey，試在下列空白處填入正確語句。typedefstructnodeintdata數(shù)據(jù)域structnodenext指針域linklistlinklistGetMinKey(lin

5、klistr)linklistminpminp是較小值的指針minp=rwhile(rnext!=null)if(minpdatarnextdata)minp=rnextr=rnextreturnminp返回較小值的指針voidSt(linklisthead)linklistqp=headnextinttempf(pnext!=NULLp=pnext)(5)=GetMinKey((6))if(pdata!=qdata)temp=pdat