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

1、第1頁，共5頁浙江理工大學(xué)2012018年碩士研究生招生考試初試試題年碩士研究生招生考試初試試題考試科目：數(shù)據(jù)結(jié)構(gòu)考試科目：數(shù)據(jù)結(jié)構(gòu)代碼：代碼：991991（請(qǐng)考生在答題紙上答題，在此試題紙上答題無效）（請(qǐng)考生在答題紙上答題，在此試題紙上答題無效）一、單選題：一、單選題：(每小題每小題2分，共分，共30分)1.帶頭結(jié)點(diǎn)的單鏈表simpleList為空的判定條件是。A.simpleList==nullB.simpleListnext==n

2、ullC.simpleListnext=simpleListD.simpleList!=null2.某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除第一個(gè)結(jié)點(diǎn)，故采用_______________存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.僅有頭結(jié)點(diǎn)的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表3.向一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用X保存被刪結(jié)點(diǎn)的值，則執(zhí)行_______________________。A.X=to

3、ptop=topnextB.X=topdataC.top=topnextX=topdataD.X=topdatatop=topnext4.一維數(shù)組和線性表的區(qū)別是_____________。A.前者長度固定，后者長度可變B.后者長度固定，前者長度可變C.兩者長度均固定D.兩者長度均可變5.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即______________________。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和

4、十字鏈表6.不帶頭結(jié)點(diǎn)的單鏈表simpleList為空的判定條件是。A.simpleList==nullB.simpleListnext==nullC.simpleListnext=simpleListD.simpleList!=null7.某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除第一個(gè)結(jié)點(diǎn)，故采用_______________存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.僅有頭結(jié)點(diǎn)的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)

5、鏈表8.向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)S所指結(jié)點(diǎn)時(shí)，則執(zhí)行_______________________。A.topnext=SB.Snext=topnexttopnext=SC.Snext=toptop=SD.Snext=toptop=topnext9.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的____________________。A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷10.設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)

6、省存儲(chǔ)，將其下三角部分按行序存放在一維數(shù)組B[1n(n1)2]中，對(duì)任一下三角部分中任一元素aij(ij?)在一組數(shù)組B的下標(biāo)位置K的值是______。A.i(i1)2j1B.i(i1)2jC.i(i1)2j1D.i(i1)2j11.如右圖所示的一棵二叉排序樹其不成功的平均查找長度為__________________。A.217B.287C.156D.216623074155648第3頁，共5頁三、簡答題：三、簡答題：(每小題每小題1

7、0分，共分，共20分)1.設(shè)對(duì)角線矩陣A=（行列下標(biāo)ij滿足：1≤i，j≤5）(1)若將矩陣A壓縮存儲(chǔ)到數(shù)組S中：1210121000135下標(biāo)：12345678910111213試求出A中已存儲(chǔ)之元素的行列下標(biāo)（ij）與S中元素的下標(biāo)K之間的關(guān)系。(2)若將A視為稀疏矩陣時(shí)，請(qǐng)畫出其行邏輯鏈接順序表。2.設(shè)二叉樹BTree的存儲(chǔ)結(jié)構(gòu)如下：12345678910left00237580101datajhfdbacegiright0009

8、400000其中，BTree為樹根結(jié)點(diǎn)指針，left、right分別為結(jié)點(diǎn)的左、右孩子指針域，在這里使用結(jié)點(diǎn)編號(hào)作為指針域值，0表示指針域值為空；data為結(jié)點(diǎn)的數(shù)據(jù)域。請(qǐng)完成如下問題：(1)畫出二叉樹BTree的邏輯結(jié)構(gòu)；(2)寫出按先序、中序和后序遍歷二叉樹BTree所得到的結(jié)點(diǎn)序列；(3)畫出二叉樹BTree的后線索化樹。四、解答題：四、解答題：(共80分)1.已知一棵二叉樹的先序遍歷序列為：ABDFGCE，中序遍歷序列為：BFD

9、GACE。（1）請(qǐng)畫出這棵二叉樹；（5分）（2）若采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)該二叉樹，其中0號(hào)存儲(chǔ)單元存儲(chǔ)根節(jié)點(diǎn)，用#表示二叉樹中不存在的節(jié)點(diǎn)，填寫以下數(shù)組來表示這棵二叉樹。（5分）0123456789101112131415（3）若采用鏈?zhǔn)酱鎯?chǔ)，節(jié)點(diǎn)的結(jié)構(gòu)如下圖（標(biāo)志位為0時(shí)表示指針指向孩子節(jié)點(diǎn)，為1時(shí)表示指向前驅(qū)或后繼），畫出和這棵二叉樹相對(duì)應(yīng)的中序線序二叉樹；（5分）lchildLTagdataRTagrchild（4）說說中序線索二叉