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

來(lái)源：時(shí)間：2007-06-06 14:35:00

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

五．試設(shè)計(jì)一個(gè)算法，判斷鏈表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è)有兩個(gè)棧S1,S2都采用順序棧方式，并且共享一個(gè)存儲(chǔ)區(qū)[O…maxsize-1],為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長(zhǎng)的存儲(chǔ)方式。試設(shè)計(jì)S1,S2有關(guān)入棧和出棧的操作算法。
八．假設(shè)用于通訊的電文僅有6個(gè)字母abcdef組成，字母在電文中出現(xiàn)的頻率分別為7，19，5，16，42，11。試為這6個(gè)字母設(shè)計(jì)哈夫曼編碼
九．試寫(xiě)一算法，判斷以鄰接表方式存儲(chǔ)的有向圖中是否存在有頂點(diǎn)Vi到頂點(diǎn)Vj的路
（i<>j）。注意：算法中涉及的圖的基本操作必須在存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。

結(jié)束

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

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

: 有用

25人覺(jué)得有用

閱讀全文

奶昔直播官方版-奶昔直播直播视频在线观看免费版下载-奶昔直播安卓版本免费安装

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

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