2017年北京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)考研題

1、2017 年北京郵電大學(xué)數(shù)據(jù)結(jié)構(gòu)考研題一、選擇1、在數(shù)據(jù)結(jié)構(gòu)中， 與計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)稱為_(kāi)；單鏈表是一種_存儲(chǔ)結(jié)構(gòu)的線性表，適合于_查找。2、二叉樹(shù)最常用的_是二叉鏈表。3、 一棵二叉樹(shù)的前序遍歷是FCABED中序遍歷是ACBFED則后序遍歷是_。4、設(shè)樹(shù)的度為5，其中度為15的結(jié)點(diǎn)數(shù)分別為6、5、4、3、2個(gè)，則該樹(shù)共有_個(gè)葉子。5、11個(gè)頂點(diǎn)的無(wú)向圖，最多能有_條邊。6、某索引順序表共有元素275個(gè)，平均分成5塊。若先對(duì)索引表采用順序查找，再對(duì)塊中元素進(jìn)行順序查找，則等概率情況下，分塊查找成功的平均查找長(zhǎng)度是_。7、交換排序適用于_存儲(chǔ)結(jié)構(gòu)的表。8、由AF六個(gè)字母構(gòu)成的堆序列是_(1)9(

2、2) 28(3)31(4)36(5)50(6) 51(7) 55(8) 110(9)138(10)邏輯結(jié)構(gòu)(11)存儲(chǔ)結(jié)構(gòu)(12)順序(13)鏈?zhǔn)?14) DBCAEF(15) ABCDEF(16) ABCEDF(17) BACDEF二、判斷1、抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無(wú)關(guān)；2、線性表的插入和刪除總是伴隨著大量數(shù)據(jù)的移動(dòng)；3、隊(duì)列在程序調(diào)用是必不可少，因此遞歸離不開(kāi)隊(duì)列；4、字符串a(chǎn)ababaaaba的改進(jìn)函數(shù)nextval數(shù)組值是0020200320;5、二叉樹(shù)中有雙子女的父結(jié)點(diǎn)，在中序遍歷中后繼一定是其中一個(gè)子女結(jié)點(diǎn)；6、不用遞歸就不能實(shí)現(xiàn)二叉樹(shù)的前序遍歷；7、若有向圖有n個(gè)頂點(diǎn)

3、，則其強(qiáng)連通分量最多有n個(gè)；8、平衡二叉樹(shù)一定是一棵完全二叉樹(shù)；9、若某內(nèi)部排序算法不穩(wěn)定，則該算法沒(méi)有使用價(jià)值；10、 倒排文件的目的是為了多關(guān)鍵字查找；三、 已知一組關(guān)鍵字為(112，213，305，46，57，86，72，162，95)，用散列表函數(shù)H(k)=k%10將它們散列到表HT(0.9)中，用線性探測(cè)法H(k),H(k)+1,H(k)-1解決沖突，畫(huà)出最后 的散列表，并計(jì)算產(chǎn)生沖突的次數(shù)。四、 簡(jiǎn)述Prim和Kruskal算法求最小生成樹(shù)的算法思想，分析他們的時(shí)間復(fù)雜度及分別適用于什么樣的網(wǎng)五、 算法1、 閱讀下面的程序，根據(jù)輸入寫(xiě)出輸出結(jié)果#include“iostream.h

4、”viod swap(int &x, int &y)int z=x;x=y;y=z;void change(int a100, int I, int j)if(in;for(int i=0;imi; change(m,0,n-1);for(i=0;in;i+) coutmi coutlc,isbbt);int hr=Post(t-rc,isbbt); if(hl-hr1) isbbt=0; if(hlhr) hl=hr; return hl;int bbt(bitptr t)int isbbt;Post(t,isbbt);Return isbbt;3、 已知圖的鄰接表、逆鄰接表定義如下：是給出算法將用鄰接表表示的圖轉(zhuǎn)換為用逆鄰 接表表示，存儲(chǔ)空間仍利用原空間typedef struct arcnodeint adjvex;arctype info;arcnode *nextarc;arcnode;1，否返回0typedef structcertype data;arcnode *firstarc;vernode, ad