杭州電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)2011-2019年考研專業(yè)課真題

杭州電子科技大學(xué)2019年攻讀碩士學(xué)位研究生招生考試《數(shù)據(jù)結(jié)構(gòu)》試題(試題共五大題，共6頁，總分150分)姓名報考專業(yè)準考證號【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效！】一、判斷題(本大題共10小題，每小題1分，本大題共10分)1.數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系.它依賴于計算機的存儲結(jié)構(gòu).()2,對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。().循環(huán)隊列通常用指針來實現(xiàn)隊列的頭尾相接.().若棧的入棧序列為1,2,3,4,5,6,則其出棧序列可以是3,2,5,6,14().用鄰接矩陣法存儲一個圖所需的存儲單元數(shù)目與圖的邊數(shù)有關(guān).().取廣義表的表尾就是返回廣義表中最后一個元素。().稀疏矩陣壓縮存儲后，必會失去隨機存取功能。().關(guān)鍵路徑是AOE網(wǎng)中從源點到終點的最長路徑。()9,對一棵二叉樹進行層次遍歷時，應(yīng)借助于一個棧。()10.在用弗洛伊德算法求解各頂點的最短路徑時，每個表示兩點間路徑的pathkpj一定是pathk[LJ]的子集(k=l,2,3，.…n).()二、單項選擇題(本大題共15小題，每小題2分，本大題共30分).從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()大類A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈式結(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu) D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu).在一個二維數(shù)組A中，假設(shè)每個數(shù)組元素在長度為3個存儲單元，行下標i為。?8,列下標j為。?9,從首地址SA開始連續(xù)存放。在這種情況下，元素A[8][5]的起始地址為()A.SA+141 B.SA+144C.SA+222D.SA+255.在雙向域表指針p的結(jié)點前插入一個指針q的結(jié)點操作是()p->Llink=q;q->Rlink=p;p->Llink->Rlink=q:q->Llink=q;p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;.在一個長為n的順序表中刪除第i個元素和第i個位置插入一個元素的時間復(fù)雜度為()A.n B.i-1 C.n-iD,n-i+1

.對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是()A.head=NULLB.head—?next—NULLC.head—?next==headD.head!=NULL.一個棧的輸入序列為1,2,3,…若輸出序列的第一個元素是n,輸出第i(l<=i<=n)個元素是( )A.不確定 B.n-i+1 C.i D.n-i.設(shè)表頭不帶頭結(jié)點且所有操作均在表頭進行，則下列最不適合作為鏈棧的是()A.只有表頭結(jié)點指針，沒有表尾指針的雙向循環(huán)鏈表B.只有表尾結(jié)點指針，沒有表頭指針的雙向循環(huán)鏈表C.只有表頭結(jié)點指針，沒有表尾指針的單向循環(huán)鏈表D.只有表尾結(jié)點指針，沒有表頭指針的單向循環(huán)鏈表.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間top[i]代表第i個棧(i=1,2)棧頂，棧1的底在V[l],棧2的底在V[m],則棧滿的條件是( ).A.|top[2]-top[l]|=0 B.top[l]+l=top[2]C.top[l]+top[2]=m D.top[lj=top[2].表達式a*(b+c)-d的后綴表達式是()A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd.已知操作符包括和")”。將中綴表達式a+b-a*((c+d)/e-f)+g轉(zhuǎn)換為等價的后綴表達式ab+acd+e/f-*-g+時，用棧來存放哲時還不能確定運算次序的操作符.若棧初始時為空，則轉(zhuǎn)換過程中同時保存在棧中的操作符的最大個數(shù)是()A.5 B.7 C.8 D.11.若將關(guān)犍字1,2,3,4,5,6,7依次插入到初始為空的平衡二叉樹r中，則r中平衡因子為0的分支結(jié)點的個數(shù)是().A.0 B.1C.2 D.312.設(shè)無向圖G=(V,E)和G，=(V，，E'),如果G，是G的生成樹，則下面說法中錯誤的是()A.G，是G的子圖 B.G，是G的連通分量C.G'是G的極小連通子圖且V=V' D.G，是G的一個無環(huán)子圖.設(shè)給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點總數(shù)為( )A.不確定B.2n C.2n+l D.2n-l.用相鄰矩陣A表示圖，判定任意兩個頂點Vi和Vj之間是否有長度為m的路徑相連，則只要檢查( )的第i行第j列的元素是否為零即可。A.mAB.A C.Am D.Am-1

15.下圖中給出由7個頂點組成的無向圖。從頂點1出發(fā)，對它進行深度優(yōu)先遍歷得到的序列可能是（）A.1354267B.1347652C.1534276D.1247653三、填空題（本大題共15小題，每小題2分，本大題共30分）.N個頂點的連通圖的生成樹含有條邊。.假定有K個關(guān)鍵字互為同義詞，若用線性探測法把這K個關(guān)鍵字填入散列表中，至少要進行次探測。.對序列｛98.36,-9.0.47,23,1,8.10.7｝采用增量為4的希爾排序，第一趟的排序結(jié)果是O.一組記錄的關(guān)鍵碼是（46,79,56,38,40,84）,以第一個記錄為基準，從小到大得到的快速排序第一次劃分結(jié)果是。.對數(shù)據(jù)序列（8,9,10,4,5,6,20,1,2）采用冒泡排序（從后向前升序進行），需要進行趟完成排序。.若一棵完全二叉樹有768個結(jié)點，則該二叉樹中葉結(jié)點的個數(shù)是。.已知一棵二叉樹的層序排列是ABCDEF,中序序列為BADCFE,則先序序列為。.下圖中的強連通分量的個數(shù)為個。

.已知字符集{41),“1?￡&11},若各字符的哈夫曼編碼依次是0100,10,0000,0101,001,011,11,0001,則編碼序列0100011001001011110101的譯碼結(jié)果是?.使用迪杰斯特拉(Dijkstra)算法求下圖中從頂點1到其他各頂點的最短路徑,依次得到的各最短路徑的目標頂點是 。.對于一個非連通無向圖,共有28條邊.則該圖至少有個頂點。.n個頂點的無向圖的鄰接表最多有個表結(jié)點。.對n階對稱矩陣壓縮存儲時，需要表長為的順序表。.若無向圖G=(VE)中含有7個頂點，要保證G在任何情況下都是連通的,則需要的邊數(shù)最少是條..對下圖進行拓撲排序，可以得到不同的拓撲序列的個數(shù)是=

四、簡答題(本大題共5小題，每小題8分，本大題共40分).某帶權(quán)有向圖及其鄰接表如F:寫出從A寫出從A點開始深度優(yōu)先的訪問序列(鄰接邊的順序按鄰接表鏈表順序);畫出深度優(yōu)先生成樹；(1)(2)(3)該圖為AOE網(wǎng)絡(luò)，求頂點C的最早發(fā)生時間和及活動FC的母晚開始時間。.將關(guān)鍵字序列(7,8,30,11,18,9,14)散列存儲到散列表中，散列表的存儲空間是一個下標從0開始的一位數(shù)組，散列函數(shù)為：H(key)=(key*3)MOD7,處理沖突采用線性探測再散列法，要求裝填因子為0.7。(1)請畫出所構(gòu)造的散列表。(2)分別計算等概率情況下，查找成功和查找不成功的平均查找長度。.設(shè)計一個算法，求出指定結(jié)點在給定二叉排序樹中的層次。節(jié)點結(jié)構(gòu)：structTree(intdata;structTree*left;structTree*right;)；intfindLevel(Treeroot,intdata).給定一個二叉樹和其中的一個結(jié)點，請找出中序遍歷順序中該節(jié)點的下一個結(jié)點并且返回。注意，樹中的結(jié)點不僅包含左右子結(jié)點，同時包含指向父結(jié)點的拒針節(jié)點%構(gòu)如下：structTreeLinkNode{intval;structTreeLinkNode*left;structTreeLinkNode*right;structTreeLinkNode*next;TreeLinkNode(intx):val(x),left(NULL),right(NULL),next(NULL){)};TreeLinkNode*GetNext(TreeLinkNode*pNode)五、程序題(本大題共4小題，每小題10分，本大題共40分).編寫算法，實現(xiàn)在單向鏈表上刪除具有重復(fù)值的多余節(jié)點，使得表中每個節(jié)點的數(shù)值均保持不同。.假設(shè)?個算數(shù)表達式中包括圓括號()，方括號門，和花括號{},編寫?個算法來判別表達式中的括號是否配對，以字符'\0'作為算數(shù)表達式的結(jié)束符boolBracketsCheck(char*str)?已知圖的鄰接矩陣的存儲結(jié)構(gòu)說明為：TypedefStruct{intvertex[m];intedge[m];}gadjmatrix;圖的鄰接表的存儲結(jié)構(gòu)說明為TypedefStructnodel{int info;int adjvertex;structnodel*nextarc;}glinklistnode;TypedefStructnode2{intvertexinto;glinklistnode*firstarc:}glinkheadnode:請設(shè)計計算法MatToList,將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)的鄰接表。voidMatToList(gadjmatrixgl[],glinkheadnodeg2[]){).在n個元素中，找出第k大的元素，用C語言寫出數(shù)據(jù)結(jié)構(gòu)，設(shè)計算法實現(xiàn)上述要求，并分析時間復(fù)雜性，最好是平均時間復(fù)雜性為O(n)。杭州電子科技大學(xué)2018年攻讀碩士學(xué)位研究生招生考試

《數(shù)據(jù)結(jié)構(gòu)》試題（試題共五大題，共5頁，總分150分）姓名報考專業(yè) 準考證號【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效！】一、判斷題（本大題共10小題，每小題2分，本大題共20分）.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系.（）.單鏈表中設(shè)置的頭結(jié)點只具有標識的作用.（）.隊列是一種能分別在表的兩端進行插入與刪除操作的線性表結(jié)構(gòu)，具有先進后出的特性。（）4采用順序存儲方式存儲，兩個棧共享一個存儲區(qū)V[0..maxsize-1],為提高空間利用率，減少溢出的可能，應(yīng)把兩個棧的棧底分別設(shè)在向量空間的兩端.（）5.哈夫曼樹是帶權(quán)路徑長度最短的樹，帶權(quán)路徑長度等于所有結(jié)點的權(quán)值之和.（）.顆有n個結(jié)點的二叉樹,采用鏈友（llink-rlink）存儲結(jié)構(gòu)，則樹中共有n+1個空指針.（）.強連通分量是無向圖的極大強連通了圖。（）.有向圖和無向圖可以采用鄰接矩陣存儲，但帶權(quán)的有向圖和無向圖，不能采用鄰接矩陣存儲，只能使用鄰接表存儲。（）.設(shè)T為一棵二叉平衡樹，向樹中插入一個結(jié)點n,然后立即刪除該結(jié)點，則不會破壞樹的結(jié)構(gòu).（）】0.歸并排序在任何情況卜,都比所有簡單排序速度快.（）二、單項選擇題（本大題共10小題，每小題2分，本大題共20分）.下面關(guān)于算法說法正確的是（ ）.A.算法最終必須由計算機程序?qū)崿F(xiàn)B.算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個操作.C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（ ）.A.存儲密度大 B.插入運算方便C.刪除運算方便 D.可方便地用于各種邏輯結(jié)構(gòu)的存儲表示.設(shè)1、2、…、n-1、n共n個數(shù)按順序入棧，若第一個出棧的元素是n,則第三個出棧的元素是：.A.3 B.n-2 C.n-3D.任何元素均可能.若一棵二叉樹具有7個度為2的結(jié)點，6個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（A.9 B.8C.15D.不確定棵二叉樹的前序遍歷序列為ABCDEFG,它的中序遍歷序列可能是（ ）.A.CABDEFG B.ABCDEFGC.DACEFBG D.ADCFEG.連通一個n個頂點的無向圖，其邊的個數(shù)至少為（ ）,如果是有向圖則邊數(shù)至少為（）.A.n-l>n B,n,n-1C.n*2-l,n'2D.n,n+1.已知有向圖G=（V,E）,其中V={V1,V2,V3,V4,V5,V6,V7,V8）.E={<V1,V2>,<V1,V4>,<V2,V7>,<V4,V7>,<V7,V8>,<V3,V4>,<V3,V5>,<V4,V6>,<V5,V6>},下列哪個序列不是G的拓撲有序序列（）。A.VI,V2,V3,V4,V5,V6,V7,V8 B.V3,VI,V2,V4,V5,V6,V7,V8C.V1,V3,V2,V4,V5,V6,V7,V8 D.VI,V3.V4,V2,V5,V6,V7,V8.對線性表進行折半查找，表中元素的存儲方式及元素排列要求為（）.A.鏈接方式存儲，元素?zé)o序B.鏈接方式存儲，元素有序C.順序方式存儲，元素?zé)o序D.順序方式存儲，元素有序.設(shè)哈希表長為15,哈希函數(shù)是H（key）=key機3,表中已有數(shù)據(jù)的關(guān)鍵字為15,22,50,13,20,36,28,現(xiàn)要將關(guān)鍵字為48的結(jié)點加到表中，用二次探測再散列法解決沖突，則放入的位置是（）.A.8 B.3 C.5 D.910.對序列｛16,8,6,7,21,-2,4｝進行排序，進行一趟后數(shù)據(jù)的排列變?yōu)椋?,8,-2,7,21.6,16｝t則采用的是（ ）排序.A.選擇 8.快速 C.希爾 D.冒泡三、填空題（本大題共15空，每空2分，本大題共30分）.元素總數(shù)基本穩(wěn)定的線性表，采用存儲結(jié)構(gòu)，能在很少進行插入和刪除操作的情況下，以最快的速度存取表中元素..長度為n的列表，被等分為n/k段，每段長度為k,不同段之間的元素不存在逆序。對該列表進行插入排序的最壞時間復(fù)雜度為..順序棧用datatl..n］存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作ft..樹在計算機內(nèi)的表示方式有一（1）_，.一棵度為仇的樹有n個節(jié)點。若每個節(jié)點直接用垃個鏈指向相應(yīng)的兒子，則表示這個樹所需要的總空間是n*（m+l）（假定每個鏈以及表示節(jié)點的數(shù)據(jù)域都是一個單位空間）.當(dāng)采用兒子/兄弟（FirstChild/NextSibling）表示法時，所需的總空間是 .設(shè)深度為d（只有一個根結(jié)點時，d為1）的二叉樹只有度為0和2的結(jié)點，則此類二叉樹的結(jié)點數(shù)至少為..如果一個完全二叉樹最底下一層為第六層（根為第一層）且該層共有8個葉結(jié)點，那么該完全二叉樹共有 個結(jié)點。.G是一個非連通無向圖，共有30條邊，則該圖至少有個頂點..Dijkstra短路徑算法從源點到其余各頂點的短路徑的路徑長度按次序依次產(chǎn)生，該算法弧上的權(quán)出現(xiàn)情況時，不能正確產(chǎn)生最短路徑..在一個大小為K的空散列表中，按照線性探測沖突解決策略連續(xù)插入散列值相同的N個元素（N<K）=問：此時，該散列表的平均成功查找次數(shù)是..設(shè)用希爾排序?qū)?shù)組歸7,35,-10,0,48,22,1.8,9,7｝進行排序，給出的步長（也稱增量序列）依次是4,2,1則排序需趟，寫出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序.四、簡答題（本大題共5題，本大題共40分）.（本題5分）斐波那契數(shù)列Fn定義如下:F0=0,Fl=l,Fn=Fn-l+Fn-2,n=2,3...,如果用大0表示法，試給出遞歸計算Fn時遞歸函數(shù)的時間復(fù)雜度是多少..（本題8分）假設(shè)一棵二叉樹的層次次序（按層次遞增順序排列，同一層次自左向右）為ECRAHXMS,中序序列為ACEHMRSX.請畫出該二叉樹，并將其轉(zhuǎn)換為對應(yīng)的森林..（本題8分）下圖是帶權(quán)的有向圖G的鄰接表表示法，求：（1）以結(jié)點VI出發(fā)深度遍歷圖G所得的結(jié)點序列；（2）從結(jié)點VI到結(jié)點V8的最短路徑；4.（本題10分）對輸入關(guān)鍵字序列501,89,513,60,906,170,879,245,653,460進行：（1）建立堆排序的初始堆（小頂堆），要求畫出主要過程.（2）輸出最小值后，如何得到次小值.（并畫出相應(yīng)結(jié)果圖）5.（本題9分）設(shè)一組數(shù)據(jù)為{1,13,27,30,56,70,9,12,23},現(xiàn)采用的哈希函數(shù)是H（key）=keyM0D13,即關(guān)鍵字對13取模，沖突用鏈地址法解決，設(shè)哈希表的大小為13（0..12）,試畫出插入上述數(shù)據(jù)后的哈希表.五、程序題（本大題共3題，本大題共40分）.（本題10分）設(shè)單鏈表的表頭指針為h,結(jié)點結(jié)構(gòu)由data和next兩個域構(gòu)成，其中data域為字符型.寫出算法dc（h,n）,判斷該鏈表的前n個字符是否中心對稱.例如xyx,xyyx都是中心對稱..（本題15分）在二叉樹中查找值為x的結(jié)點，試編寫算法（用C語言）打印值為x的結(jié)點的所有祖先，假設(shè)值為x的結(jié)點不多于一個，后試分析該算法的時間復(fù)雜度..（本題15分）設(shè)有順序n個盒子，每個盒子有一個小球，每個小球的顏色是紅，白，藍之一.要求重新安排這些小球，使得所有紅色小球在前，所有白色小球居中，所有藍色小球居后，重新安排時對每個小球的顏色只能看一次，并且只允許交換操作來調(diào)整小球的位置.杭州電子科技大學(xué)2011年攻讀碩士學(xué)位研究生入學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》試題(試題共五大題，5頁，150分)姓名報考專業(yè)準考證號【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效！】一、選擇題(每小空2分，共28分).在下列數(shù)據(jù)結(jié)構(gòu)中具有先進先出特性，具有先進后出特性.a：線性表b：棧c：隊列出串.如下關(guān)于串的陳述中，正確的是、.a：串是數(shù)據(jù)元素類型特殊的線性表 b：串中的元素是字母c：串中若干個元素構(gòu)成的子序列稱為子串 d：空串即為空格串.對廣義表A=(((a),(b)),((c)))執(zhí)行操作gettail(gethead(gettaiMA)))的結(jié)果是：.執(zhí)行操作gethead(getlail(gethead(A)))的結(jié)果是：.a：()b：((5)c：(a)d：(b)e：(c).任何一個連通網(wǎng)的最小生成樹.a：只有一棵b:有一棵或多棵c:一定有多棵 d:可能不存在.在有n個結(jié)點的二叉樹的三叉捱表表示中,空指針數(shù)為.a:不確定b:nc:n+1d:n+2.關(guān)鍵路徑是指在只有一個源點和一個匯點的有向無環(huán)網(wǎng)中源點至匯點的路徑.a:瓠的數(shù)目最多b:弧的數(shù)日最少c:權(quán)值之和最大d:權(quán)值之和最小.設(shè)無向B8G=(丫5)和&(V；E),若G.是G的生成樹，則下面不正確的說法是.a:G'是G的子圖 b:G,是G的連通分量?c:G'是G的無環(huán)子圖 d:G,是G的極小連通子圖且V'=V.下列杳找方法中適用于查找單鏈表.a:順序查找 b:折半查找c:分塊查找d:hash查找.卜列排序方法中，是穩(wěn)定的；具有最好的平均性能；當(dāng)待排序序列的關(guān)鍵字次序為倒序時，若需為之進行正序排序，下列方案中以為佳.a:堆排序b:快速排序c:直接插入排序 d:簡單選擇排序.數(shù)據(jù)結(jié)構(gòu)通常有下列4類基本結(jié)構(gòu)：線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖型結(jié)構(gòu)、..線性表的存儲結(jié)構(gòu)是以物理位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系的.而線性表的存儲結(jié)構(gòu)是通過指針保持數(shù)據(jù)元素之間的邏輯關(guān)系的..n個頂點的強連通圖至少有條狐，至多有條孤..若某一二叉樹按中序遍歷可得到有序序列，則該二叉樹是.若某一二叉樹從根結(jié)點到其它任一結(jié)點的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字遞增有序，則該二叉樹是..若對完全二叉樹中的結(jié)點從1開始按層進行編號，設(shè)最大編號為n,則編號為i的結(jié)點(l<i￡n)的父結(jié)點編號為;所有編號的結(jié)點為葉子結(jié)點..壓棧次序為a、b、c.則不可能得到的輸出序列是..已知待排序序列為：33,34,7,28,38,11,65,15,37,20.則：以第一個元素為樞軸的快速排序一趟分劃的結(jié)果是.堆排序初始建堆(小頂堆)的結(jié)果是.希爾排序第一趟(增量為3)的結(jié)果是.三、圖示結(jié)構(gòu)題(每小題8分，共40分).已知某二叉樹的先序遍歷次序為：ABCDEFG.中序遍歷次序為：BADCFEG.畫出該二叉樹形.給出該二叉樹的后序遍歷次序.TOC\o"1-5"\h\z3)畫出中序線索化后的二叉樹形. g.已知某無向圖如右圖所示：(1)畫出該圖的鄰接表存儲結(jié)構(gòu).(2)畫出該圖的鄰接矩陣存儲結(jié)構(gòu). <7(3)根據(jù)你所繪制的鄰接表給出DFS OKD及BFS次序..依序?qū)㈥P(guān)鍵字20、40.30、80、70、50,60、10插入到一棵2-3樹中(初始狀態(tài)為空)，(1)請畫出該B-樹.(2)再先后刪除關(guān)鍵字40、60,畫出刪除后的B一樹..設(shè)哈希函數(shù)為H(key)=keymod7,用鏈地址法處理沖突，若依次在哈希表中插入12個元素32、65、83、25、74、21、33、18,61、27、47、28.畫出它們在表中的分布情形.計算其平均成功的查找長度.5.假設(shè)用于通訊的電文僅由8個字符A、B、C、D、E、F、G、H組成，字符在電文中出現(xiàn)的頻率分別為3、12,9、23、2、17,2k13(I)畫出你所建的哈夫曼樹，(2)給出每一字符的哈夫曼編碼.StatusAl(SqListL,ElemTypecur_e,ElcmType&next_e)(//初始條件：順序線性表L已存在inti=l;ElemType*p=Lelcm;whiled<L.length&&*p!=cur_e)(ifp++:)if(i=L.length)returnINFEASIBLE;else(next_e=*++p;returnOK;StatusA2(LinkListL,inti,ElemTypee)(〃初始條件：帶頭結(jié)點的單鏈表L已存在intj=0;LinkListp=L,s;while(p&&j<i-1){p=p->next;jf)if(!pIIj>i-1)returnERROR：s=(LinkList)malloc(sizeof(LNode));s->data=e:s->next=p->next;p->next=s;returnOK：}intA3(LinkQueueQ)(//初始條件：鏈隊列Q已存在inti=0;QueuePtrp：P=Q.front：while(Q.rear!=p){i++；p=p->next：}returni;}voidA4(BiTreeT,Status(*Visit)(TEleraType)){//初始條件：二叉樹T已存在if(T){A4(T->lchild,Visit);A4(T->rchiId,Visit);Visit(T->data);intA5(SSTableST,KeyTypekey)(〃初始條件:順序表ST已存在inti;ST.elem[0].key二key;for(i=ST.length;!EQ(ST.elem[i].key,key);-i);returni;)intA6(SqListL,inti)I〃初始條件:順序表L已存在intmin;intj,k;k=i;min=L.r[i].key;for(j=i+l;j<=Llength：j++)if(L.r[j].key<min)(k=j；min=L.r[j].key;Ireturnk:.設(shè)單鏈表結(jié)點結(jié)構(gòu)為：typedefstructLNode{intdata;structLnode*next:[?LinkList:寫一函數(shù)voidA7(LinkListL)試采用直接插入排序的方法將單鏈表2(帶頭結(jié)點)中的結(jié)點按非遞減次序排列。.設(shè)二叉鏈表結(jié)構(gòu)為：typedefstructBiTNode{TEleraTypedata：structBiTNode*lchild,*rchild;}*BiTree;寫一函數(shù)voidA8(BiTreeT)求二叉樹7的深度。杭州電子科技大學(xué)2012年攻讀碩士學(xué)位研究生入學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》試題（試題共五大題，共四頁，總分150分）姓名報考專業(yè)準考證號【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效！】一、判斷題（本大題共10小題,每小題2分.本大題共20分）.數(shù)據(jù)的違輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的..數(shù)據(jù)對象是數(shù)據(jù)元素的有限集合..順序存儲結(jié)構(gòu)要求存儲單元地址連續(xù),而鏈式存儲結(jié)構(gòu)要求存儲單元地址不連續(xù)..若某完全二叉樹中共有121個結(jié)點，則第68個結(jié)點的度為0..一個連通圖必定是一個無向完全圖..平衡二義樹必定是完全二叉樹..只要精心設(shè)計,總是可以設(shè)計出無沖突的哈希函數(shù)..在最壞情況下，堆排序的時間性能是0（nlogn）,比快速排序爆壞情況好..通常，在一棵非空的二叉排序樹中,“刪除某個元素后乂將其插入.則所得的一叉持序樹與刪除前的二叉排序樹相同..若哈希表采用線性探測法處理沖突,同義詞在表中不一定相鄰存儲.二、單項選擇題（本大題共9小題，12個選項，每個選項2分，本大題共24分）.線性表的順序存儲結(jié)構(gòu)是一種的存儲結(jié)構(gòu).A.散列存取 B.索引存取 C.隨機存取D.順序存取.循環(huán)隊列用數(shù)組A[m]存放其元素值，已知隊列的頭和尾分別用front和rear來指示，初始化時置front=rear=0,則當(dāng)前隊列長度是.A.（rear-frcmt+m）%m B.rear-front+irear-rear-front-1rear-front可隨機存取表中任可隨機存取表中任一元素便丁杳找線性表中的元素.線性表的鏈式存貯結(jié)構(gòu)的優(yōu)點為.A.存儲空間可充分利用 B.C.插入刪除操作較為方便 D..折半插入排序是對百接插入持序算法的改進，它看眼丁?減少A.移動元素的次數(shù) C.揖序的塔數(shù)C.與關(guān)鍵字比較的次數(shù) 0.空間復(fù)雜度.設(shè)有向圖的頂點個數(shù)為n,則該有向圖最多有條弧.A.n-1 B.n(n~l) C.n(n+l) 0.nl.如果二義樹中任何一個非終端結(jié)點的值都人了其左子樹上所有結(jié)點的值而小丁其右于樹上所有結(jié)點的侑，要得到各結(jié)點值的遞增序列，應(yīng)按遍歷次序撲列結(jié)點.A.先序 B,中序 C.后序 D.層序.具有n個結(jié)點的Huffman樹有個葉子結(jié)點. .A.n-1 B.rn/21 C.Ln/2j D.不定.己知廣義表L=((x,y.z),a,(u,t.?))，從L中取出原子項y的運算是.A.head(tai1(head(L))) B.tail(head(head(taiI(L))))C.tai1(tai1(head(tai1(L)))) D.head(tail(head(head(L)))).已知待排序的關(guān)鍵字序列為：36,21,78,63.6.52,15,39,48.70.10.需按非遞減次序排序，則希爾排序第一趟(增量為5)的結(jié)果為 (I):起泡排序第一趟的結(jié)果為(2):快速排序第一趟(以第一個元素為支點)的結(jié)果為 (3)；堆排序初始建堆(大頂堆)的結(jié)果為 (4).21.36,63,6.52,0,10,7878,70,52,63,21,36,15,39.48.6,1078,52,63.70,21,15,36,39,48.6,1010,21,15,6,36,52,63,810,15,39,48.6,36,21,78,63,70.5221,36,78,63,6,52,15,39.48.70,10三、填空題(本大題共12小題，20個填空項，每個填空項2分，本大題共40分)1.一個隊列的入隊序列是1,2,3,4,則隊列可能的憐出序列是..判斷不帶頭結(jié)點的單循環(huán)鏈表L為空的條件是..設(shè)一維數(shù)組A?”以行序為主序存儲，每個元素占4個字節(jié)，存儲器按字節(jié)編址.已知A的起始存儲位置(即數(shù)組元素A?的存儲地址)為1000,則數(shù)組元素標的存儲地址是(D,數(shù)組A的存儲址是(2)字節(jié)..含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過?.若無向圖有100個頂點、200條邊，用鄰接矩陣存儲，則該鄰接矩陣有(1)個矩陣元素.(2)個非零元素..高度為5的完全二叉樹至少有 (D個葉f結(jié)點,至多行(2)個葉子結(jié)點..將一個森林F轉(zhuǎn)換為一果樹B,則F的先序遍歷是B的遍歷?.一個算法的語句頻度之和為T(n)=(3n,+2n,logm+4n-7)/(5n).用時間復(fù)雜度表示為0()..在一棵m階B樹中，每個非終端結(jié)點至多有棵于樹。

.根據(jù)數(shù)據(jù)元素之間的關(guān)系的不同特征，可以分成集合、 ⑴ 、(2)和圖狀結(jié)構(gòu)4類基本結(jié)構(gòu)..statusDeleteRear(LinkListArear,ElemType&e)(〃rear是帶頭結(jié)點的單循環(huán)鏈表的尾指針(指向循環(huán)璉表的表尾元素結(jié)點).〃本算法刪除首元結(jié)點.并由e返回其值.if(rear->next=rear)returnERROR; (1):rear->next->next=p->next:e=p->data:if(p==rear)⑵： (3) ：returnOK;).BiTreeSearchBST(BiTreet,KeyTypekey)(〃在根指針t所指的一義排序樹中遞！H地杳找某關(guān)鍵字等于key的數(shù)據(jù)元素.〃若有找成功，則返回該元素結(jié)點的指針，否則返回空指針if(!t) (1) ：elseif(t->data.key=key)returnt;elseif(t->data.key<key) (2) ;else⑶：四、簡答題(本大題共6小題,每小題6分，本大題共36分).某二叉樹的先序遍歷序列為：JCBADEFIGH,中序遍歷序列為ABCEDFJGIH.(1)請畫出該二叉樹：(2)畫出其中序線索二叉樹..對如心所示的有向圖，(1)畫出其鄰接表；(2)針對⑴的鄰接號寫出從頂點1開始的深度優(yōu)先和廣晟優(yōu)先遍歷序列..設(shè)數(shù)據(jù)元素的美鍵字序列為(10,14.7,23,80,65,54,90,36,47.23),依次輸入這些元素，創(chuàng)建一棵平衡的一叉排序樹(AVL啊)，請逐畫出每插入一個元素后的AVL樹的形態(tài)..什么是穩(wěn)定抻序方法？拈爾排序是不是穩(wěn)定持序方法？簡單選打揖序是不是稔定格序方法？.設(shè)哈希表長度是16,哈希函數(shù)為H(key)=keymod13,用線性探測再散列法處理沖突，依次在哈依次中插入12個元素(47,38,80,45,14,51.31.18,63,72.9,581.(1)畫出它們在表中的分布情形.(2)計算等概率時責(zé)找成功的平均齊找K度ASL?.假設(shè)用于通訊的電文僅由8個字符組成,字符在電文中出現(xiàn)的妝率及現(xiàn)有的一進制前綴編碼如卜所示：字符ABCDEFGH續(xù)率41372422023!5編碼11110111010000mu11001101請問這套編碼是不是最優(yōu)的前綴編碼？為什么？如果不是，請給出更高效的編碼.五、算法設(shè)計題(本大題共3小題，每小題10分，本大題共30分)1.設(shè)有一個不帶頭結(jié)點的單鏈表，表中元素值均不相同.試編寫一個算法，刪除該單鏈表中元素值為x的數(shù)據(jù)元素.若刪除成功,則返問irue.否則返問false.單鏈表的結(jié)點定義為：typedefstructLNode(ElemTypedata;structLNode?next;}LNode,?LinkList;【以卜兩膝均假設(shè)一叉樹采用二叉鏈表存儲結(jié)構(gòu)，結(jié)點定義如卜：typedefstructBiTNodeITElemTypedata;structBiTNode*lchiId,*rchiid;IBiTNode.?BiTree;]2.設(shè)計一算法,計算給定二義樹T中度為2的結(jié)點個數(shù).3.設(shè)指針p(材空)指向一義樹中的某個結(jié)點.且該結(jié)點的左4f將均1F空，試寫出求p所指結(jié)點的中序后繼的算法.杭州電子科技大學(xué)2013年攻讀碩士學(xué)位研究生入學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》試題(試題共六大題，6頁，150分)姓名報考專業(yè) 準考證號【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效！】一、是非題(每小題2分，共10分).對「插入、刪除操作，，電鏈衣和順序表的時間乂雜及都“J"計為(7n)..隊列是種操作受限的線性表，所疔對數(shù)據(jù)元素的操作僅限--端進行..II線性結(jié)構(gòu)的遍歷過程姑對結(jié)構(gòu)中的每數(shù)據(jù)元素訪川1僅訪川次.9結(jié)構(gòu)中數(shù)據(jù)元案之間的美系無關(guān).1.對「求地小代價生成樹的方法，Kruskal方法優(yōu)『Prim〃法.5.哈布夫的件找效率與音找表的K度無關(guān).二、選擇題(每空2分，共28分).線性表在的情況卜適「使用能友結(jié)構(gòu)實現(xiàn),ns表中含市人地結(jié)點 L需經(jīng)常修改衣中結(jié)山:位e：需經(jīng)常對&進行刪除、插入出表中數(shù)據(jù)兒素依關(guān)鍵字花序.如卜?關(guān)丁,內(nèi)的陳述中，錯促的是.a：串是數(shù)據(jù)對象為字符集的線性表 b：中的長度為字符的個數(shù)c：串中若干個連續(xù)字符構(gòu)成的子序列稱為「中 d:串中的數(shù)據(jù)元索是？W.收一：維數(shù)組A[6l[5],每一數(shù)組元索所用存儲空間為1個？個存儲器按字—址.已知A在存體器中的起始地址為100.則按行俘體時,元素A⑶⑶的第一個字”的地址是:按列存儲時，尤索人⑶⑶的第一個,rit的地址是.a:128 b:152 c:180 d:200.對廣義表A=(((a.b).<c)),(d))執(zhí)行操作geltail(gciheud(geltai[(A)))的結(jié)果止： ,執(zhí)行操作geihead(getlaiI(gethcaiKA)))的結(jié)果足:.a：O h*(a)r? (h) (I：(()e；(<|).小枝次序為I、2、3、4則不可能得別的輸出序列處。a：1432h:2113c:3421 d:1321.設(shè)任意無向圖G=(V,E)和G'=(V,E),普G.是G的連通分址，則卜列說法中不正確的姑oa:G'是G的子圖 b:CMG的連通子圖c:G.是G的極大連通f圖d:。是G的極人連通;圖11『方『V.卜列件找方法中針對關(guān)鍵字有序的順序表介找效率較低。a：順序代找 b：折半質(zhì)找 C：分塊杳找 d：史波那央臺找.卜列排序方法中,是穩(wěn)定的：具有法好的平均性能;所需的輔存空間最大。面對不同的初始數(shù)據(jù)，的時間發(fā)雜度恒為0(nlogn)：而的時間復(fù)雜度恒為0(if)：a:快速打序b:簡單選擇排序 c:希爾排序d:心并排序三、填空題(每空2分，共22分).以物理位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系的存儲結(jié)構(gòu)被稱為：通過指計來保持數(shù)據(jù)元素之間的邏輯關(guān)系的存儲結(jié)構(gòu)被稱為；.對完全二義樹中的結(jié)點從1開始按層進行連續(xù)編號。設(shè)編號為i的結(jié)點的父結(jié)點存在，則編號為的結(jié)點為其父結(jié)點；電編號為i的左修f結(jié)點存在，則編號為的結(jié)點為其左孩子結(jié)點；設(shè)編號為i的八孩f結(jié)點存在，則編號為的結(jié)點為其6孩子結(jié)點..己知髭.義樹的先序遍歷次序為：人,及(?,1),￡,1：,(；.心中序遍歷次序為：及1),C.F,E,A,H,G.則其后序遍歷次序為：層次遍歷次序為<.n個頂點的強連通圖至少仃條弧,至多有條弧。.?棵m階的B樹，第一層至少有一個結(jié)點：第二層至少仃2個結(jié)點,除根之外的所有北終端結(jié)點至少有棵/樹，樹中所不j11終端結(jié)皮至多TF 棵.樹。四、圖示結(jié)構(gòu)題(每小題8分，共40分).已知某森林的先序遍歷次序為：A,D,E,F,G,II,B.I,C,J,K.L,M,、?中序遍歷次序為：D,I-,G.H,l-.A,l,B,J.LM.K,3<1) 畫出該森林。(2) 畫出該森林用孩子兄弟法表示的存儲結(jié)構(gòu)，

已知某無向圖如右圖所示:(1)(2)b(1)(2)b c<3)根據(jù)你所繪制的鄰接表給出DFS及BI；S次序,,并畫出深度優(yōu)先生成樹和廣深處優(yōu)先生成樹.，、e- ，fj.依序?qū)㈥P(guān)鍵字65,50,30,20,10.45,fiO,55.25.70插入到,棵-：義排球樹中(初始狀態(tài)為空).清畫出該二義排序樹.若之后刪除關(guān)鍵字65,岫出刪除用的.義排序樹.以同樣的關(guān)犍字插入次序建立平?御二義排摩樹.請畫出該平衡一義樹..設(shè)哈希函數(shù)為H(kcy)=keymod13,哈帶衣長為15.用開放定址法處理沖突,增城序列使用二次探測再散列*若依次在哈布表中插入il個兀點：34,12,67,43,98,23,51,86.05.37.22.畫出它們在我中的分布情形.求其等概率情況卜平均成功的先我K度..假設(shè)用丁,通訊的電文僅由8個字符A,B,C,D,E,F,G,HfUJfi,字符住電文中出現(xiàn)的頻率分別為6.25,3,17,8,15.10,16畫出你所建的哈大蟄樹，給山每字符的哈夫曼編碼.五、閱讀以下函數(shù)，指出算法的功能(每小題6分，共30分)boo】Al(LinkListL.inti.ElemTypec){//L為帶頭結(jié)點的單鏈衣intj=0;LinkListp=L,s：while(p&&j<i-1)fp=rp->next：j-；returnERROR:s=(LinkList)ma11oc(sizeof(LNode));s->data=e:s->next=p->next;p->next=s;returnOK;voidA2(LinkQucue&Q)//Q為帶頭結(jié)點的鏈隊列、Q.front,Q.rear分別為隊頭和隊尾指針Qnodc*p.*q:Q.rear=Q.front:P-Q.front">next;Q.front->nexl=NULL:while(p){q=P；尸p->ncxl;frce(q);iniA3(BiTreeT)//T為一只鏈友表示的：又樹inti,j;if(!T)return0:if(T->lchild)i=A3(T-〉lchild)：elsei=0;if(T->rchild)j=A3(T->rrhiId):elsej=0:returni>j?i+l:j+1:intA4(SSTablcST,KeyTypekey)(//ST為順序表，表中數(shù)據(jù)元素依關(guān)鍵字有序intlow,high,mid;)ow=0：high=ST.length-1:whi1e(1ow<=high)(mid=(low+high)/2:if(key==ST.elem[mid].key)returnmid;elseif(key<ST.elvmfmidj.key)high=mid-l;elselow-mid*l：)returnT:(工iniA5(SqList&L,inilow,inihigh)(〃L為喉序表。其中：卜林為0的單元未存數(shù)據(jù)，KeyTypepivotkey:L.clcm[0]=L.elcm[low：:Pivotkey=L.elem[low],key;whileOow<high)(while(low<high&&L.clem[high].key>=Pivolkey)一high:I.,elem[low]=L.elem[high]：whilc(low<high&&L.elem[low],key<=Pivolkey)++low;I.,elem[high]=Lelem[low];IL.eiem[low]=L.elem[0]：returnlow；}六、算法設(shè)計題(每小題10分，共20分).已知集合A和集合B存在，且分別用帶頭結(jié)點的單鏈表LI和L2我東.編與算法：DiffdinkLisl&LI.LinkListL2)實現(xiàn)集合運算：A=A-B.設(shè)單鏈表結(jié)點結(jié)構(gòu)為：typedefstructINode(ElemTypcdata;structLNodenext;|LNode?-LinkList:.設(shè)樹的存儲結(jié)構(gòu)為孩/鏈友&東法?其中：孩子結(jié)點結(jié)構(gòu)為：lypedefsirueICTNode<ini child:structCTNode*nexi;1*ChiIdPtr;雙親結(jié)點結(jié)構(gòu)為：typedefstructIElemTypcdata：ChiIdPtrfirstchiId;被F鏈的頭指計ICTBox;例結(jié)構(gòu)為：typedefstruet(CTBoxnodes[MAX_TREE_SIZE];intn,r;”結(jié)點數(shù)和根結(jié)點的位置>CTree：試編寫?遞歸的先根遍歷樹的算法。P0TT(CTree&T,intv,void(?visit)(BlcraTypce))〃已知樹T作空,v的初值為T.r(根結(jié)點的位置)，visil為訪問困數(shù).杭州電子科技大學(xué)2014年攻讀碩士學(xué)位研究生入學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》試題（試題共六大題，■共6頁，總分150分）姓名報考專業(yè)準考證號【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效】一、是非題（T正確，F(xiàn)錯誤，本大題共5小題，每小題2分，本大題共10分）.鄰接表可以用以表示無向圖，也可用以表示有向圖.（）.算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān).（）.二義樹是一棵結(jié)點的度最大為2的樹.（）.隊列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。（）.對丁任何待排序序列來說，快速揖序均快丁起泡排序.（）二、選擇題（本大題共14小題，每小題2分，本大題共28分）.遞歸程序可借助丁“ ）轉(zhuǎn)化為計遞D」程序.A.線性表B.棧C.隊列D.數(shù)卯.對一叉排序樹按（）可得到TF序序列.A.層次遍歷B.先序遍歷C.中序遍歷 D.后序遍歷.順序存儲設(shè)計時，存儲單元的地址（ ）.A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù),部分不連續(xù).已知一算術(shù)表達式的中綴形式為A*B*CD/E.后綴形式為ABC*+DE/-,其前綴形式為（）.A.-A+B*C/DEB.-A+B+CD/EC.-+*ABC/DED.-+A+BC/DE.在仃向圖G的拓撲序列中,若頂點Vi在頂點Vj之前，則卜.列情形不可能出現(xiàn)的是（ ）.A.G中有弧<Vi,Vj> B.G中沒有弧<Vj,Vi>C.G中沒有弧D.G中有弧<Vj,Vi>6.卜列說法不正確的是（ ）.A.圖的遍歷是從圖中某?頂點出發(fā)訪遍圖中其余頂點，LL使每一個頂點僅被訪問一次。B.圖的遍歷的基本算法有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索。C.圖的深度優(yōu)先搜索不適用丁仃向圖.I）.圖的深度優(yōu)先搜索是一個遞歸過程-7.n個結(jié)點的有向完全圖含有弧的數(shù)目( ).A.n*n B.n(n+1)C.n/2 D.n*(n-1)&在下面的程序段中，'"r""語句的頻度為()。for(inti=O;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.左、右孩f地址.某內(nèi)排序方法的穩(wěn)定性是指()。A.該排序算法不允許有相同的關(guān)鍵字記錄B.該排序算法允許有相同的關(guān)鍵字記錄C.平均時間為0(nlogn)的排序方法D.假設(shè)關(guān)鍵字Ki=Kj 】<j",i*j),且在排序前的序列中Ri領(lǐng)先丁Rj(即i<j)，在排序后的序列中，Ri仍領(lǐng)先丁Rj一組記錄的關(guān)鍵碼為(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)無關(guān)的排序方法是( )排序法。A.插入B.選擇 C.起泡 D.快速.適用丁折半杳找的表的存儲方式及元素排列要求為()A,鏈接方式存儲，元素?zé)o序B.鏈接方式存儲，元素有序C.順序方式存儲，元素?zé)o序D.順序方式存儲，元素有序.卜面關(guān)TB和B+樹的敘述中，不正確的是( )B樹和B卜樹都是平衡的多義樹。B樹和B+樹都可用丁?文件的索引結(jié)構(gòu)。B樹和B+樹都能有效地支持順序檢索。B樹和B+樹都能有效地支持隨機檢索。三、填空題(本大題共11空，每空2分，本大題共22分).森林的兩類遍歷方法為先序遍歷。:先根遍歷樹可以借用一義樹的遍歷算法實現(xiàn)；后根遍歷樹可以借用一叉樹的 遍歷算法實現(xiàn)C.已知一無向圖G=(V,E),其中V={a,b,c,d,e)E={(a,b),(a,d),(a,c),(d,c),(b,e))現(xiàn)川某?一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abccd,則采用的是一 遍歷方法。.將整M數(shù)組A[7][7]按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，設(shè)每個播型元素32字優(yōu)則元素的地址是：

1 2 3 4 5 6 7 8.設(shè)一棵-又樹BT1 2 3 4 5 6 7 8Ichilddatarchild其中Ichild.rchild分別為結(jié)點跑左、右孩子指針域，data為結(jié)點的數(shù)據(jù)域.則該二叉樹的高度為；第3層有^ 個結(jié)點（根結(jié)點為第I層）..當(dāng)廣義表中的每個元素都是原子時，廣義表便成了..找是限定在表尾進行插入或刪除操作的線性表，棧對數(shù)據(jù)元素的操作是按原則進行的。設(shè)有一個空棧,現(xiàn)有輸入序列為1,2,3,4.5,經(jīng)過PUSH,PUSH,POP.PUSH,POP,PUSH,PUSH之后，諭出序列姑..對丁??個具有n個結(jié)點的單鏈衣，在表中插入】個結(jié)點的時間及雜度為.四、圖示結(jié)構(gòu)題（本大題共5小題，每小題8分，本大題共40分）.已知某森林的先序遍歷次序為：A,D,E,F,C,H,B,I,C,J,K,L,M,N中序遍歷次序為：D,F.G,H,E,A,I,B,J,L,M,N,K,CD畫山該森林2）畫出該森林用孩子兄弟法表示的存儲結(jié)構(gòu).根據(jù)插入次序（82,92,102,112,87,72,77,63,74）建立一義抖序樹。并根據(jù)該插入次序建立平衡,義樹。.對卜圖所示二叉樹分別按前序,中序.后序遍歷,給山相應(yīng)的結(jié)點序列，并畫出中序線索一叉樹,.采用哈希函數(shù)H（k）=3*kmod13并用開放地址法處理沖突，增量序列選取采用線性探測再散列方式，在數(shù)列地址空間［0..12］中對關(guān)犍字序列22,41,53,46,30,13,1,67,51I）構(gòu)造哈希表（畫示意圖）；2）裝填閃子；3）杳找成功時的平均查找長度；4）有找不成功時的平均杳找k度..已知某無向圖如下圖所示：畫出兩類圖的存儲結(jié)構(gòu)示意圖1)數(shù)組表示法〈鄰接矩陣)存儲結(jié)構(gòu).2)鄰接表存儲結(jié)構(gòu)./_ab c>?,,\ J，def,W、.J %J五、閱讀以下函數(shù)，指出算法的功能(本大題共5小題，每小題6分，本大題共30分)StatusAl(SqListL,ElemTypecur_e,ElemType&next_e)//L為循序線性表(inti=l;ElemType*p=L.elem：while(i<L.length&&*p!=cur_e){i++；p++；)if(i==L.length)returnINFEASIBLE：else{nexl_e=*++p;returnOK;StatusA2(SqStack&S,SElemTypee)〃S為順序棧(if(S.topS.base>=S.stacksize)(S.base3(SElemType*)real1oc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SEIemType)):if(IS,base)exit(OVERFLOW):S.top=S.base+S.stacksize;S.stacks!ze+=STACKJNCREMENT;I*(S.top)++=e:returnOK：IintA3(PTreeT)〃T為雙親衾存儲的樹(intk,m,def,max=0;for(k=0;k<T,n;++k)(def=l;m=T.nodes[k].parent:while(m!=-l)(m-T.nodes[m].parent;def++;}if(max<def)max=def;(returnmax;voidA4(SSTable&ST)//ST為靜態(tài)順序杳找表Iinti,j,k;for(i=l;i<ST.length;i++)(k=i；ST.elem[0]=ST.elemti];for(j-i+l;j<=ST.length;j++)ifLT(ST.elem[j].key,ST.elerntO].key)(k=j;ST.elem[0]=ST.;)if(k!=i)(ST.elem[k]=ST.elem[i]:ST.elem[i]=ST.elcm[O];}}voidA5(SqList&L)〃L為順序表(inti,j;for(i=2：i<=L.length：++i)ifLT(L.r[i].key,L.key)(L.r[0]=L.r[i]：for(j=i-l;LT(L.r[0].key,Lr[j].key):—j)L.r[j+l]=Lr[j]：0];))六、算法設(shè)計題(本大題共2小題，每小題10分，本大題共20分).實現(xiàn)順序線性表基本操作獲取1個數(shù)據(jù)兀素的前驅(qū)。.實現(xiàn)圖遍歷穿法中的深度優(yōu)先搜索算法。杭州電子科技大學(xué)2015年攻讀碩士學(xué)位研究生招生考試《數(shù)據(jù)結(jié)構(gòu)》試題(試題共六大題，共11頁，總分150分)姓名報考專業(yè) 準考證號【所有答案必須寫在答短紙上，做在試卷或草稿紙上無效！】一、是非胤(正確填T,幡謨填F,本大?共6小每小?1分,本大?共6分)TOC\o"1-5"\h\z(1)從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類《 )(2)數(shù)據(jù)結(jié)構(gòu)基本操作設(shè)It的最重耍準則是,實現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨立?( )(3)線性表的特點是每個兀素都有一個前驅(qū)和一個后端.( )(4)用將的前序遍歷和中序電歷可以導(dǎo)出樹的后序遍歷.( )(5)一個有向圖的鄰接表和逆鄰接表中結(jié)點的個數(shù)可能不等.( )(6)歸并排序在任何情況下都比所有簡單排序速度快.( )二、單項選擇題(本大題共23小題,每小題2分，本大?共46分)(!)下列程序段的時間復(fù)雜值墾()count=0fbr<k=l;k<-n;k*-2)coum-+-+;AOtbgjn)BO(n)COfnlo&n)D0(nJ)(2)某線性表常發(fā)生的操作為胴除第一個數(shù)據(jù)元素和在?后?個元素后添加新元素，采用()作為存儲結(jié)構(gòu)，能使其存儲效率和時間效率最高.A電鏈表B僅用頭結(jié)點的循環(huán)單演奏C雙向循環(huán)舞表D僅用尾指針的橢環(huán)單健表(3)在非空雙向循環(huán)性嶷中q所指的舞結(jié)點前面插入一個有p指的鐮結(jié)點

的過程是依次執(zhí)行爆句h>rlinkRi：h>Mnk=q*Hink：q->Hinkhp;()Aq*>rlink->llink?7>:Bq->llink->rltnk?p;Cp->riink->llink-p;Dp->IHnk->rfink^;(4)執(zhí)行完下列語句段后，i值為()intRintx){mum((x>0)?x*Rx?【):2)inti;FfUMA2 B4 C8 D無限通白(5)射于MB序循環(huán)隊列，正確的是()A無法判斷隊列是否為空 B無法判斷隊列是否為滿C隊列不可能淌 D以上說法都不對(6)元素a.b,c,d,e依次進入初始為空的棧中,直到所有元素都出枚.則在所有可能的出棧序列中,以元素d開頭的序列個數(shù)是()A3B4C5D6(7)順序彼環(huán)隊列放在維數(shù)峭A[0MJ]中，endl指向隊頭元素，end2指向隊尾元素的后一個位置?假設(shè)隊列兩端均可進行入隊和出隊操作,隊列或者能容納M?l個元素,初始時為空,F列判斷隊空和隊滿的條件中，正確的是().A隊空：endl=end2;隊滿：endirend2+1)modM：B隊空；endl=?end2;隊滿:endZ^tendI+1)mod(M-1);C隊空】end2=(endl+l}modM;隊滿:endl?=(end2+l)modM;D隊空：endl=(end2+1)modM;隊滿：end2==(endl+l)mod(M")；(?)已知一棵有2011個結(jié)點的料,其葉子結(jié)點個數(shù)為116,該樹對應(yīng)的二叉樹中無右孩子的結(jié)點個數(shù)是().A115B116C1895D1896(9)若X是后序線索二叉樹中的葉結(jié)點,?且X存在左兄弟結(jié)點Y.則X的右線索指向的是().AX的父結(jié)點B以Y為根的子制的最左下結(jié)點CX的左兄弗納點YD以丫為根的子例的最右下站點(10)將森林F轉(zhuǎn)換為對應(yīng)的二叉樹T?F中葉子結(jié)點的個數(shù)等于().AT中葉結(jié)點的個數(shù)BT中度為1的結(jié)點個數(shù)CT中左核子指針為空的結(jié)點個數(shù)DT中右孩子指針為空的站點個數(shù)(II) 棵哈夫曼期共有215個站點,對其進行哈夫曼編碼,共能糊到()個不同的碼字.A107B108C214D215(12)若平衡二叉鞘的高度為6,且所有非葉節(jié)點的平衡因子均為I.則諛平衡二夏樹的結(jié)點總數(shù)為().A10B20C32D33(13)若用鄰接矩陣存借有向圖.矩陣中主時角線以下的兀素均為本，則關(guān)于讀圖拓撲序列的結(jié)論是().A存在.且唯一B存在,且不唯C存在.可能不唯一D無法確定是否存在(14)下列關(guān)于圖的敘述中，正確的是《).1)網(wǎng)路是商單路校2)存儲稀俄圖，用鄰接矩陣比鄰接表更省空間3)若有向圖中存在拓撲序列,則該圖不存在回路A僅2》B僅l)、2)C僅3)D僅1)、3)(15)對于有n個頂點、。條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍歷，其算法的時間復(fù)雜度是().AO(n)BO(e)CO(n+e)D(Xn><e)(16)下列關(guān)于最小生成期的說法中.正確的是().I)■小生成樹的代價唯一2)權(quán)值?小的邊一定會出現(xiàn)在所有的最小生成樹中3)用育里姆(Prim)算法從不同頂點開始得到的?小生成柯?定相同?39(ftIIff4）使用普里嫦和克?斯卡爾（Kruskal）解法得到的?小生成樹總小相同A僅I〉B僅2）C僅I）、3）D僅2）、4）（17）用哈希（散列）方法處理沖突（碰橙）時可能出現(xiàn)堆職（聚集）睨象.下列堆項中，會受惟稅現(xiàn)飲自接彩響的是（）.A存儲效率B散列函數(shù)C裝填因子 D平均查找長度（18）對一個長度為50的有序費進行折半責(zé)找，?多比較《）次就能強找出結(jié)果.A6B7C8D9（19）在一棵m階的B?樹腫,若在某結(jié)點插入一個新關(guān)鍵字而引起該結(jié)點的分裂,則此結(jié)點中原有的關(guān)倭字的個數(shù)是（）AmBm+lCm-lDm/2（20）設(shè)二叉排序樹關(guān)鍵字由1/000的學(xué)數(shù)構(gòu)成,現(xiàn)嚶杳找關(guān)慢字為363的結(jié)點.下述關(guān)■字序列中,不可能是在二叉排序樹匕宜找的序列是（）?A2.252.401,398,330.344,397.363B 924, 220,911.244.898. 258. 362. 263C 925, 202,911.240,912. 245, 363D2.399.387.219.266.382，381.278.363（21）荷量置找算法性能好壞的主要標準是（）.A參加比較的關(guān)鍵字值的多少B被15找的關(guān)例字值在關(guān)鍵字序列中的位置C關(guān)植字值序列中是否存在被責(zé)找關(guān)鍵字值D關(guān)幢字值的平均比較次數(shù)的多少（22）下列捧序算法中，（）算法可能出現(xiàn)下面的情況1在■后他開始前,所有元素都不在?終的位置上.A堆排序B臂泡排序C快速拷序D插入排序（23）基于比較的排序算法時間復(fù)雜度最好的是O（）.AlogjnBnCnlog2nDn2三、填空題（本大?共14空，誨空2分.本大?共28分）（I）已知棵完全二叉期的第6層（設(shè)根為第一層）有8個葉子結(jié)點，則讀完全二叉軻的結(jié)點個數(shù)最務(wù)是

(2)以下程序的功能般實現(xiàn)帶附加頭結(jié)點的單卷收數(shù)據(jù)結(jié)點逆序連接，請培空完善之.voidreverse(pointerh)/?h為附加頭結(jié)點指針?/{pointerp.q;p=h->next:h->next^NULL;while()(q-p;pp=p->nexl;q->next?h->next;h->next?; })(3)是限定儀在表尾進行插入或刪除操作的線性表.(4)設(shè)有一個空枝.棧頂指針為I000H(七六進制),現(xiàn)有輸入序列為I,2..4.5.經(jīng)過PUSH.PUSH.PORPUSH.POP.PUSH.PUSH之后,輸出序列是 ?而枝頂指針值是H,設(shè)槿為順序棧.每個元素占4個字節(jié).(5)已知廣義表：AFaMBTAAICMMbAXB).求下列運算的結(jié)果:uul(head(uul(C)))(6)已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的緒點.則該樹有個葉子結(jié)點.(7)森林的兩類幽歷方法為先序遍歷與^ ：先根遍歷樹可以借用二叉樹的 遍歷算法實現(xiàn);后根也歷樹可以借用二叉料的 也歷算法實現(xiàn).(?)實現(xiàn)圖中廣度優(yōu)先搜索算法時，使用的數(shù)據(jù)結(jié)構(gòu)是(9)求解最短路徑的Floyd算法的時間I［雜度為(10)具有6個璐點的無向圖,當(dāng)?少有條邊時能確保是一個連通四、圖示結(jié)構(gòu)題(本大?共5小題，軸小題4分.本大星共20分)<1)將下圖所示的三棵樹組成的萩林轉(zhuǎn)換為二叉料.(2)給定集合(.6.9,16.17).I）用燧形衰示外部結(jié)點.用圓胭衰示內(nèi)部結(jié)點，構(gòu)造相應(yīng)的哈夫曼網(wǎng):2）計算帶權(quán)路徑長度：3）寫出哈夫曼娘碼.（3）已知2櫬2?3B-樹如F（省略外結(jié)點》：I）對樹（?）.請分別畫出先后插入26,85兩個新結(jié)點后的例形:2）對樹（b）.請分別瓶出先后刪除53,37兩個結(jié)點后的鞘形.(a)(b)（4）己知?有向圖如下圖所示I）耳出該圖的鄰接矩陣喪示并據(jù)此給出從頂點I出發(fā)的深度優(yōu)先遍歷序列;2）求謨有向圖的強連通分■數(shù)目；3）給出讀圖的兩個拓撲序列.《5）設(shè)散列函數(shù)H（K）=3Kmod11.散列地址空間為％10,對關(guān)鍵字序列（32,49.24.38,21,4.12)按照F述兩種孵決沖突的方法構(gòu)造散列莪：I)線性探測再般列：2)蓋地址法：3)并分別求出等概率下查找成功時和查找失敗時的平均查找長度ASLsucr和ASUjnsucC*五、閱讀以下函敬、指出*法的功能(本大?扶5小愿，每小國4分，本大?共20分)<I)StatusAKLinkLtst衣Lintn)//L為單域線性表(intj;LinkListp.q禺il(n<a0)returnERROR;InitList(L);printfC請輸入%d個元素VmXsa<LinkList)malloc(sizeofrLNode));scanfl*%d",fts->data)：5->ncxr=NULL;L->ncxt?s;(s"(LinkList)malloc(stzeof(LNode));scanfl"%d",&s->di?a);q-L;p5sL->next;while(p&&p->dau<s->data){*TP；p?p->next;)anekq-Anext;q->next=s;IreturnOK;StatusA2(LinkQueue量Q.QElenHype&e)ffQ為愜隊列

QueuePtrp：ifl-Q.front—Q.rear)returnERROR;p?Q.front->r>ext;e=p->data;Q.front>>next?p->next;iKQ.rear=p)Qreaf?Q.front;fre?p);returnOK;defineMAXSIZE20typedefintKeyType；typedefintInfbType;typedefSqListB;structRedType(KeyTypekey;InfbTypeotherinfb;structSqList{RedTyperfMAXSIZE+IJ;intlength;)；voidF(Bsjntm)(RedTyperc;intj;rc?H.r(sJ;for(j=2*sj<?iny*?2){ifl[j<m&<(H.rO].key,H.rg+1J.key))

if(!LT(rckeyJljtiJ.keyJ)break,方；)H.rfsjF；}voidA3(B￡H)(RcdTypct；int匕F(Hu,H.length);for(i?H.lcngth;i>l;-i)(FHjUI；H.甲E<4>SumisA4(RiThrTreeT.Status(*Vi?ifXTFIemTypee))//T為一叉幡的一叉線索存儲結(jié)構(gòu)(BiThrTreep;尸T-'Ichild;while(p??T)(while(p->LTag!=s=Link)p?P">lchild;if(!Visit(p->dma))returnERROR;while(p>>RT^=ThreadA&p->rchild!=T)(p°T>->rchiW; -Visil(p?>data);

)kp?>rchild;)returnOK;)(5)voidA5(BiTrec盤p)//BiTree為二叉樹的二叉母衣存儲表示(BiTreeq禺iR!p->rchild)(<rp；p?p->lchild;free(q);)elsei1(!p->lchild)(<TP；p*T>>rchild;Eq)；)else(<TP：s-p->lchild;while(s->rchild)(q*3：s*s->rchild;}p->dau?s->data;iRq!pq->rchild*s>>lchild;elseq>>lchildIBs->lchild;freed);六、算法設(shè)計題（本大副共3小昆,每小愿10分.本大篇共30分）（1）嫂寫一法求有向圖G中距離頂點v0筒手路徑長度為ten的所有頂點.<2>二叉樹的帶權(quán)結(jié)點路徑長度（WPL）是二叉網(wǎng)中所有叫子結(jié)點的帶權(quán)路徑長度之和.給定一棵二叉樹T,采用二叉鐮表存儲,結(jié)點結(jié)構(gòu)為leftweightright其中葉子結(jié)點的weight域保存該結(jié)點的非負權(quán)值.設(shè)root為指向T的根節(jié)點的指針,請設(shè)計求T的WPL的鐮法，要求：I）給出算法的基本設(shè)計思想：2）使用C或C-逼宮,蛤出二叉樹結(jié)點的數(shù)據(jù)類型定義；3）根據(jù)設(shè)計思想,采用C或CHS聲描述算法,關(guān)鍵之處給出注釋.<3）設(shè)育一個數(shù)組中存放了一個無序的關(guān)鍵序列KI、K2?….Kn.現(xiàn)要求將Kn放在元索排序后的正確位置上,試編寫實現(xiàn)饃功能的算法.要求比較關(guān)健字的次數(shù)不超過n.第II員共“貝杭州電子科技大學(xué)2016年攻讀碩士學(xué)位研究生招生考試《數(shù)據(jù)結(jié)構(gòu)》試題（試題共六大題，共11頁，總分150分）姓名報考專業(yè)準考證號【所有答案必須寫在答題紙上，做在試卷或草稿紙上無效！】一、是非題（答題要求說明，T正確，F(xiàn)錯誤，本大題共6小題，每小題1分，本大題共6分）一個