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

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

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

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

結束

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

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

: 有用

25人覺得有用

閱讀全文

制服一区字幕精品|一二三区欧洲视频|国产无遮挡裸体女|好吊色91青青草|色欲TV亚洲国产|私人高清强伦中文字幕|国产在线自慰欧美综合图区|色欲av成人一区二区三区在线观看|九九九久久精品亚洲视频久久精品|亚洲无码中文在线

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

2019考研VIP資料免費領取