哈爾濱工業(yè)大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)考研試題

來源：時間：2007-06-06 14:35:00

考試科目：數(shù)據(jù)結(jié)構(gòu) 報考專業(yè)：計算機科學(xué)與技術(shù)
一．填空（總分：10分，每一題2分）
1．對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點*p后插入一個新結(jié)點的時間復(fù)雜度為________, 在給定為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為________。
2．廣義表（a，（a，b），d，e，( (I,j,), k) ）的長度是________, 深度是________。
3．對于一個具有n個結(jié)點的二員樹，當它為一棵________二元樹時具有最小高度，當它為一棵_______時，具有最大高度。
4．在順序文件中，要存取第I個記錄，必須先存取______個記錄。
5．求最短路徑的dijkstra算法的時間復(fù)雜度為________。
二．選擇填空：（總分10分，每小題2分）
1．若某線性表最常用的操作是存取任意指定序號的元素和最后進行插入和刪除運算，則利用______存儲方式最節(jié)省時間。
（1）順序表；（2）雙鏈表；
（3）頭結(jié)點的雙循環(huán)鏈表；
（4）單循環(huán)鏈表
2．在一棵三元樹中度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為______個
（1）4 （2）5 （3）6 （4）7
3．在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)______倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的_____倍
（1） 1/2 （2）2 （3）1 （4）4
4．下列排序算法中，________,排序在某趟結(jié)束后不一定能選出一個元素放到其最終的位置上。
（1）選擇（2）冒泡（3）歸并（4）堆
5．散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計算轉(zhuǎn)化為記錄的關(guān)鍵字值計算轉(zhuǎn)化為記錄的存放地址，因為散列函數(shù)是一對一的關(guān)系，則選擇好的_______方法是散列文件的關(guān)鍵。
（1）散列函數(shù) （2）除余法中的質(zhì)數(shù)
（3）沖突處理（4）散列函數(shù)和沖突處理
三回答下列問題（總分15分，每小題3分）
1 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？
2 什么是循環(huán)隊列？
3 簡述線索二元樹的概念。
4 何為有向圖的遍歷？
5 什么是索引順序文件？
四．分別畫出和下列樹對應(yīng)的各個二元樹。

五．試設(shè)計一個算法，判斷鏈表L是否是遞減的。
六．判斷以下序列是否為堆，如果不是，則把它調(diào)整為堆。
(1) (12,24,33,65,33,56,48,92,86,70)
(2) (25,56,20,23,40,38,29,61,35,76,28,100)
七．設(shè)有兩個棧S1,S2都采用順序棧方式，并且共享一個存儲區(qū)[O…maxsize-1],為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長的存儲方式。試設(shè)計S1,S2有關(guān)入棧和出棧的操作算法。
八．假設(shè)用于通訊的電文僅有6個字母abcdef組成，字母在電文中出現(xiàn)的頻率分別為7，19，5，16，42，11。試為這6個字母設(shè)計哈夫曼編碼
九．試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在有頂點Vi到頂點Vj的路
（i<>j）。注意：算法中涉及的圖的基本操作必須在存儲結(jié)構(gòu)上實現(xiàn)。

結(jié)束

特別聲明：①凡本網(wǎng)注明稿件來源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來源：育路網(wǎng)"，違者將依法追究責(zé)任；

②部分稿件來源于網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系我們溝通解決。

: 有用

25人覺得有用

閱讀全文

97在线观看视频,很黄很色120秒试看,久久久久久久综合日本,1000部精品久久久久久久久,欧美freesex10一13

哈爾濱工業(yè)大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)考研試題

2019考研VIP資料免費領(lǐng)取