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

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

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

3、topnexttopnext=SC.Snext=toptop=SD.Snext=toptop=topnext4.一維數(shù)組和線性表的區(qū)別是_____________。A.前者長度固定，后者長度可變B.后者長度固定，前者長度可變C.兩者長度均固定D.兩者長度均可變5.設矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分按行序存放在一維數(shù)組B[1n(n1)2]中，對任一下三角部分中任一元素aij(ij?)在一組數(shù)組B的下標位置K的值是____

4、__。A.i(i1)2j1B.i(i1)2jC.i(i1)2j1D.i(i1)2j6.在線索化二叉樹中，P所指的結(jié)點沒有左子樹的充要條件是_______________________。A.Pleft==nullB.Pltag=1C.Pltag==1且Pleft==nullD.以上都不對7.如果Tree2是由有序樹Tree1轉(zhuǎn)換而來的二叉樹，那么Tree1中結(jié)點的后序就是Tree2中結(jié)點的____________________。A.先

5、序B.中序C.后序D.層次序8.判定一個有向圖上是否存在回路除了可以利用拓撲排序方法外，還可以用_____________。A.求關(guān)鍵路徑的方法B.求最短路徑的Dijkstra方法C.廣度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法第3頁，共4頁1532463.向一個長度為n的順序表中的第i個元素(01in???)之前插入一個元素時，需向后移動_____________個元素。4設有一個背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為W1，W2

6、，...，Wn。問能否從這n件物品中選擇若干件放入背包，使得放入的重量之和正好是S。設布爾函數(shù)Knap(S，n)表示背包問題的解，Wi(i=1，2，...，n)均為正整數(shù)，并已順序存儲地在數(shù)組W中。請在下列算法的下劃線處填空，使其正確求解背包問題。Knap(S，n)若S=0則Knap←true否則若（S0且n1)則Knap←false否則若Knap(1)=true則print(W[n])；Knap←true否則Knap←Knap(2)5

7、下列程序判斷字符串s是否對稱，對稱則返回1，否則返回0；如f(“abba“)返回1，f(“abab“)返回0；intf((1)________)inti=0j=0while(s[j])(2)________f(jijij)return((3)_______)6.一個有n個頂點的無向圖最多有_________條邊。7.在堆排序和快速排序中，若原始記錄接近正序或反序，則選用_________比較好。三、簡答題三、簡答題：(每題15分，共分，