哈爾濱工業大學2001年數據結構考研試題

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

考試科目：數據結構報考專業：計算機科學與技術
一．填空（總分：10分，每一題2分）
1．對于一個具有n個結點的單鏈表，在已知的結點*p后插入一個新結點的時間復雜度為________, 在給定為x的結點后插入一個新結點的時間復雜度為________。
2．廣義表（a，（a，b），d，e，( (I,j,), k) ）的長度是________, 深度是________。
3．對于一個具有n個結點的二員樹，當它為一棵________二元樹時具有最小高度，當它為一棵_______時，具有最大高度。
4．在順序文件中，要存取第I個記錄，必須先存取______個記錄。
5．求最短路徑的dijkstra算法的時間復雜度為________。
二．選擇填空：（總分10分，每小題2分）
1．若某線性表最常用的操作是存取任意指定序號的元素和最后進行插入和刪除運算，則利用______存儲方式最節省時間。
（1）順序表；（2）雙鏈表；
（3）頭結點的雙循環鏈表；
（4）單循環鏈表
2．在一棵三元樹中度為3的結點數為2個，度為2的結點數為1個，度為1的結點數為2個，則度為0的結點數為______個
（1）4 （2）5 （3）6 （4）7
3．在一個圖中，所有頂點的度數之和等于所有邊數______倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的_____倍
（1） 1/2 （2）2 （3）1 （4）4
4．下列排序算法中，________,排序在某趟結束后不一定能選出一個元素放到其最終的位置上。
（1）選擇（2）冒泡（3）歸并（4）堆
5．散列文件使用散列函數將記錄的關鍵字值計算轉化為記錄的關鍵字值計算轉化為記錄的存放地址，因為散列函數是一對一的關系，則選擇好的_______方法是散列文件的關鍵。
（1）散列函數（2）除余法中的質數
（3）沖突處理（4）散列函數和沖突處理
三回答下列問題（總分15分，每小題3分）
1 數據結構與數據類型有什么區別？
2 什么是循環隊列？
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都采用順序棧方式，并且共享一個存儲區[O…maxsize-1],為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長的存儲方式。試設計S1,S2有關入棧和出棧的操作算法。
八．假設用于通訊的電文僅有6個字母abcdef組成，字母在電文中出現的頻率分別為7，19，5，16，42，11。試為這6個字母設計哈夫曼編碼
九．試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在有頂點Vi到頂點Vj的路
（i<>j）。注意：算法中涉及的圖的基本操作必須在存儲結構上實現。

結束

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

②部分稿件來源于網絡，如有侵權，請聯系我們溝通解決。

: 有用

25人覺得有用

閱讀全文

哈爾濱工業大學2001年數據結構考研試題

2019考研VIP資料免費領取