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

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

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

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

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

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

6、省存儲，將其下三角部分按行序存放在一維數(shù)組B[1n(n1)2]中，對任一下三角部分中任一元素aij(ij?)在一組數(shù)組B的下標位置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.設對角線矩陣A=（行列下標ij滿足：1≤i，j≤5）(1)若將矩陣A壓縮存儲到數(shù)組S中：1210121000135下標：12345678910111213試求出A中已存儲之元素的行列下標（ij）與S中元素的下標K之間的關系。(2)若將A視為稀疏矩陣時，請畫出其行邏輯鏈接順序表。2.設二叉樹BTree的存儲結構如下：12345678910left00237580101datajhfdbacegiright0009

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

9、GACE。（1）請畫出這棵二叉樹；（5分）（2）若采用順序存儲結構存儲該二叉樹，其中0號存儲單元存儲根節(jié)點，用#表示二叉樹中不存在的節(jié)點，填寫以下數(shù)組來表示這棵二叉樹。（5分）0123456789101112131415（3）若采用鏈式存儲，節(jié)點的結構如下圖（標志位為0時表示指針指向孩子節(jié)點，為1時表示指向前驅或后繼），畫出和這棵二叉樹相對應的中序線序二叉樹；（5分）lchildLTagdataRTagrchild（4）說說中序線索二叉