杭州電子科技大學2014年計算機考研數(shù)據(jù)結(jié)構(gòu)真題

杭州電子科技大學2014年攻讀碩士學位研究生入學考試《數(shù)據(jù)結(jié)構(gòu)》試題（試題共六大題，?共6頁，總分150分）姓名報考專業(yè)準考證號【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效】一、是非題（T正確，F(xiàn)錯誤，本大題共5小題，每小題2分，本大題共10分）.鄰接表可以用以表示無向圖,也可用以表示有向圖。（）.算法的優(yōu)劣與第法描述語言無關，但與所用計兌機有關。（）.二義樹是一棵結(jié)點的度及大為2的樹。（）.隊列是與線性去完全不同的一種數(shù)據(jù)結(jié)構(gòu)。（）.對了任何待排序序列來說，快速排序均快下起泡排序。（）二、選擇題（本大題共14小題,每小題2分，本大題共28分）.遞歸程序可借助r（）轉(zhuǎn)化為非遞出程序。A.線性表A.線性表B.棧C.隊列D.數(shù)組.對二義排序樹按（）可得到才■序序列.A,層次遍歷B.A,層次遍歷B.先序遍歷C中摩遍歷D.后序遍歷.順序存儲設計時，存儲單元的地址（ >oA.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù).已知一克術表達式的中綴形式為A』B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為（）。A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE.在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則卜列情形不可能山現(xiàn)的是（ ）0B.G中沒有弧<Vj,Vi>D.GB.G中沒有弧<Vj,Vi>D.G中有弧<Vj,Vi>C.G中沒。中沒i,Vj>.卜列說法不正確的是（ ）。A.圖的遍歷姑從圖中某?頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪同一次。B.圖的遍歷的基本算法有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索。C.圖的深度優(yōu)先搜索不適用了有向圖，.圖的深度優(yōu)先搜索是一個遞歸過程。.n個結(jié)點的有向完全圖含有弧的數(shù)日( )。A.n*n B.n(n+1)C.n/2 D.n*(n—1).在卜面的程序段中，”xr41〃語句的頻度為().for(inti巾；i<n;i什)for(intj=0:j<n;j++)x=x+l：A.0(2n)B.0(n)C：0(n2) D.0(log2n).靜態(tài)鏈表中指計用()代替，表示結(jié)點在數(shù)蛆中的相對位置。A.內(nèi)存地址B.數(shù)組卜'標 C.下一元素地址 D.左、石孩子地址10,某內(nèi)排序方法的穩(wěn)定性是指()OA.該排序并法不允許有相同的關鍵字記錄B.該排序算法允許有相同的關鍵字記錄C.平均時間為0(nlogn)的排序方法D,假設關鍵字Ki=Kj ”j?n,Mj),且在排序前的序列中Ri領先丁Rj(即i<j)，在抖序后的序列中，Ri仍領先丁Rj一組記錄的關鍵碼為(47,80,57,39,41,85),則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為().A.(39,41,47,57,80,85) B.(41,39,47,80,57,85)C.(41,39,47,57,80,85) D.(41,39,47,85,57,80).比較次數(shù)與序列的原始狀態(tài)無關的排序方法是( )排序法。A.插入B.選擇 C.起泡 D.快速.適用丁?折半杳找的表的存儲方式及元素界列要求為()A.鏈接方式存儲，元素無序 B,鏈接方式存儲，元素有序C.順序方式存儲，元素無序 D.順序方式存儲，元素有序.卜曲關丁B和B+樹的敘述中，不正確的是()B樹利樹都是平衡的多義樹。B樹和B+樹都可用于文件的索引結(jié)構(gòu)。B樹和B?樹都能有效地支持順序檢索.B樹和B+樹都能有效地支持隨機檢索。三、填空題(本大題共11空，每空2分，本大題共22分).森林的兩類遍歷方法為無序遍歷4：先根遍歷樹可以借用一義樹的遍歷算法實現(xiàn)；后根遍歷樹可以借用二叉樹的 遍歷算法實現(xiàn)..已知一無向圖G=(V,E),其中V={a,b,c,d,e)E={(atb),(a,d),(a,c),(d,c),(h,e)|現(xiàn)川某?一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd,則采用的是_遍歷方法..將整型數(shù)如A[7][7J按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，設好個整型元素占2字節(jié)，則元素的地址是：.第2臾共6頁

1 2 3 4 5 6 7 8.設一棵一叉樹BT的存儲結(jié)構(gòu)如F：1 2 3 4 5 6 7 8IchiIddatarchild其中Ichild.rchild分別為結(jié)點@左、右孩子指針域，data為結(jié)點的數(shù)據(jù)域.則該二叉樹的高度為；第3層有:個結(jié)點（根結(jié)點為第1層），5.當r義表中的每個元素都是原子時，廣義表便成了..棧是限定在表尾進行插入或刪除操作?的線性表.棧對數(shù)據(jù)元素的操件是按原則進行的。設有一個空棧，現(xiàn)有輸入序列為1,2,3,4,5,經(jīng)過PUSH,PUSH,POP.PUSH.POP.PUSH,PUSH之后，輸出序列是 o.對丁?個具有n個結(jié)點的單鏈表，在表中插入1個結(jié)點的時間及雜度為。四、圖示結(jié)構(gòu)題（本大題共5小題，每小題8分，本大題共40分）L已知某森林的先序遍歷次序為：A,D,E,F,G,H,B,I,C,J,K,L,M,N中序遍歷次序為：D,F,G,H,E,A,I,B,J.L,GN,K,C1）血山該森林2）畫出該森林用孩子兄弟法表示的存儲結(jié)構(gòu).根據(jù)插入次序（82,92,102,112,87,72,77,63,74）建立二義持序樹。并根據(jù)該插入次序建立平衡一義樹。.對卜?圖所示二義樹分別按前序.中序、后序遍歷,給出相應的結(jié)點序列,并畫出中序線索一叉樹。4采用哈希困數(shù)H（k）=3*kBiod13并用開放池址法處理沖突，增地序列選取采用線性探測再散列方式，在數(shù)列地址空間［0..12］中對關鍵字序列22,41,53,46,30,13,1,67,511）構(gòu)造哈希表（畫示意圖）：2）裝填因子：3）有找成功時的平均查找長度：4）存找不成功時的平均杳找K度。第3頁共6人5.已知某無向圖如卜圖所示：畫出兩類圖的存法結(jié)構(gòu)示意圖1)數(shù)蛆表示法(鄰接矩陣)存儲結(jié)構(gòu).2)鄰接表存儲結(jié)構(gòu).?'a,bz c；/、??A .?<.id),ef五、閱讀以下函數(shù)，指出算法的功能(本大題共5小題，每小題6分，本大題共30分)StatusAl(SqListUElenTypecur_e,ElemType&nexi_e)//L為循序線性表(inti=l;KlemType*p=L.elcm：while(i<l..length&&*p!=cur_e)(i"；p++；}if(i==L.length)returnINFEASIBLE：else(ncxi_e=*++p:returnOK;|IStatusA2(SqStack&S.SElemTypee)//S為順序棧Iif(S.top-S.base>=S.stacksize)]S.base二(SElemType*)real」oc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW)：S.top=S.base+S.stacksizc;第4頁共6頁S.stacksize+=STACKINCREMENT：)*(S.top)+*=e:returnOK;intA3(HreeT)〃T為雙親裊存儲的樹{intk,m.def.max=O;for(k-0;k<T.n：++k)(def=l;m=T.nodes[k].parent:while(m!=-l)(m=T.nodes[mJ.parent;def”;}if(max<def)max=def;}returnmax：)voidA4(SSTable&ST)//ST為靜態(tài)順序杏找表(intfor(i=l;i<ST.length;i")(k=i;ST.elem[0]=ST.elemCi]:foT(j-i+l;j<=ST.length;j++)ifLT(ST.elem[j].key,ST.clem[0).key)ST.elcm[01-ST.elem[j];}if(k!=i){ST.elen[k]=ST.elem[i]:第5頁共6頁ST.elcm[i]=ST.elem[O]：voidA5(Sqlist&口〃1,為順序表(inti,j：for(i=2;i<=Llength：++i)ifLT(L.r[i]