湖南大學(xué)2003年數(shù)據(jù)結(jié)構(gòu)試題

來源：時(shí)間：2007-06-06 14:42:08

湖南大學(xué) 2003 年招收攻讀碩士學(xué)位研究生
入學(xué)考試命題專用紙
招生專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)、計(jì)算機(jī)軟件與理論、軟件工程碩士
考試科目：數(shù)據(jù)結(jié)構(gòu) 試題編號(hào)：418(450)
注：答題（包括填空題、選擇題）必須答在專用答題紙上，否則無效
一、單項(xiàng)選擇題（每小題1分，共15分）
1．兩個(gè)各有n個(gè)元素的有序列表并成一個(gè)有序表，其最少的比較次數(shù)是
。
A.n B.2n-1 C.2n D.n-1
2.設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是0~ n-1，f表示隊(duì)首元素的前驅(qū)位置，r表示隊(duì)尾元素的位置，則隊(duì)列中元素個(gè)數(shù)為。
A.r-f B.r-f 1 C.(r-f 1)mod n D.(r-f n)mod n
3.一個(gè)5行6列的二維數(shù)組s采用從最后一行開始，每一行的元素從右至左的方式映射到一維數(shù)組a中，s和a的下標(biāo)均從0開始，則s[3][3]在a中的下標(biāo)是。
A．7 B. 8 C. 9 D. 10
4．設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為1，則高度為n的二叉樹中所含葉子結(jié)點(diǎn)的個(gè)數(shù)最多為個(gè)。
A．2n B.n C.2n -1 D.2n-1
5．設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為個(gè)（設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為1）。
A.2h B 2h-1 C.2h 1 D.h 1
6.對一棵二叉檢索樹進(jìn)行得到的結(jié)點(diǎn)序列是一個(gè)有序序列。
A．前序周游 B. 中序周游 C.后序周游 D. 層次周游
7．一棵前序序列為1，2，3，4的二叉樹，其中序序列不可能是。
A．4,1,2,3 B.4,3,2,1 C.2,4,3,1 D.3,4,2,1
8．下列編碼中不是前綴碼。
A．{00，01，10，11} B．{0,1,00,11}
C．{0，10，110，111} D．{10，110，1110，1111}
9．在含n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，零元素的個(gè)數(shù)為 .
A．e B．2e C．n2-e D．n2-2e
10．具有n個(gè)頂點(diǎn)和e條邊的圖的深度優(yōu)先搜索算法的時(shí)間復(fù)雜度為 A．O(n) B．O(n3) C．O(n2) D．O(n e)
11.如果具有n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有棵生成樹。
A．n B．n l C．n-l D．2n
12堆排序算法在平均情況下的時(shí)間復(fù)雜度為。 A．O(n) B．O(nlogn) C．O(n2) D．O(logn)
13．在待排序數(shù)據(jù)已基本有序的前提下，下述排序方法中效率最高的是。 A．直接插入排序 B．直接選擇排序 C．快速排序 D．歸并排序
14．在理想情況下，散列表中查找元素所需的比較次數(shù)為。
A．n B．O C．n／2 D．1
15．在一棵m階B樹中，若在某結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是。
A．m B．m 1 C．m—l D．m／2
二、判斷題(判斷下列各題是否正確，若正確，在括號(hào)內(nèi)打“√”，否則打“╳”；每小題1分，共10分)
1．已知指針curr指向鏈表中的某結(jié)點(diǎn)，執(zhí)行語句curr=curr->next；不會(huì)刪除該鏈表中的結(jié)點(diǎn)。 ( )
2．若二叉樹的葉結(jié)點(diǎn)數(shù)為1，則其高度等于結(jié)點(diǎn)數(shù)(僅含根結(jié)點(diǎn)的二叉樹高度為1)。（）
3．按中序周游二叉樹時(shí)，某個(gè)結(jié)點(diǎn)的直接后繼是它的右子樹中第一個(gè)被訪問的結(jié)點(diǎn)。 ( )
4．完全二叉樹的某結(jié)點(diǎn)若無左孩子，則它必是葉結(jié)點(diǎn)。 ( )
5．向二叉檢索樹中插入一個(gè)新結(jié)點(diǎn)，需要比較的次數(shù)不可能大于此二叉樹的高度。 ( )
6．對一個(gè)堆按層次周游，一定能得到一個(gè)有序序列。 ( )
7．一棵樹中的葉子結(jié)點(diǎn)數(shù)一定等于其對應(yīng)的二叉樹中的葉子結(jié)點(diǎn)數(shù)。 ( )
8．將一棵樹轉(zhuǎn)換為二叉樹表示后，該二叉樹的根結(jié)點(diǎn)沒有右子樹。 ( )
9．任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)湫蛄校彝負(fù)湫蛄胁晃ㄒ弧? ( )
10．快速排序在最差情況下的時(shí)間復(fù)雜度是0(n2)，此時(shí)它的性能并不比冒泡排序更好。 ( )
三、填空題（每空2分，共20分）
1．具有100個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)樹為。
2．由權(quán)值分別為3，9，6，2，8的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的外部帶權(quán)路徑長度為＿＿＿。
3．對含n個(gè)結(jié)點(diǎn)的完全二叉樹按自上而下，從左到右的順序結(jié)點(diǎn)編號(hào)（從0
開始），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是。
4．n個(gè)頂點(diǎn)的連通無向圖的鄰接矩陣至少有個(gè)非零元素。
5．在有序表A[1..20]中，若需查找的元素位于A[12]，則采用折半查找算法所比較的元素的下標(biāo)依次為
6．要將序列{60，10，8，40，90，70，100}建成堆，只需把8與相
交換。
7．從一維數(shù)組a[n]中順序查找出一個(gè)最大值元素的時(shí)間復(fù)雜度為。
8．已知廣義表L=（（a，b，c），（d，e，f）），則運(yùn)算head(tail(head(tail(L))))
的結(jié)果是 .
9.模式串P=“abaa”的next函數(shù)值序列為。
10．一個(gè)兩層100階的B 樹，最多可以有條記錄
四、解析題（共55分）
1．對二叉樹中結(jié)點(diǎn)進(jìn)行按層次順序（每一層從左至右）的訪問操作稱為二叉樹的層次遍歷，遍歷所得到的結(jié)點(diǎn)序列稱為二叉樹的層次序列。現(xiàn)已知一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列為DBGEHJACIF，請畫出該二叉樹。
（7分）
2．證明若二叉排序樹中的一個(gè)結(jié)點(diǎn)存在兩個(gè)孩子，則（8分）
①它的中序后繼結(jié)點(diǎn)沒有左孩子。
②它的中序前趨結(jié)點(diǎn)沒有右孩子。
3．對下面的帶權(quán)無向圖采用prim算法從頂點(diǎn)①開始構(gòu)造最小生成樹。（寫出假如生成樹頂點(diǎn)集合S和選擇邊Edge的順序）（10分）

4．已知一組關(guān)鍵字序列為：（17，31，13，11，20，35，25，8，4，11，24，40， 27），按照依次插入結(jié)點(diǎn)的方法生成一棵平衡二叉排序樹。（10分）

5．設(shè)散列函數(shù)為H（k）=k％13，散列表的地址空間為0到12，用線性探查法解覺沖突，將關(guān)鍵字（18，22，78，205，40，16，35，104，61）依次存入該散列表中，試構(gòu)造散列表，并計(jì)算在等概率下的搜索成功的平均搜索長度ASL（搜索成功的平均搜索長度 ASLsucc 是指搜索到表中己有表項(xiàng)的平均探查次數(shù)。它是找到表中各個(gè)己有表項(xiàng)的探查次數(shù)的平均值）（10分）
6．給出一組關(guān)鍵字T=（20，3，18，40，9，30，5，11，32，7，28），設(shè)內(nèi)存工作區(qū)可容納4個(gè)記錄，寫出用置換-選擇排序得到的全部初始?xì)w并段。若某文件經(jīng)內(nèi)排序后得到50個(gè)初始?xì)w并段（初始順串），若使用多路歸并排序算法算法，并要求三趟歸并完成排序，歸并路數(shù)最少為多少？（10分）
五、算法設(shè)計(jì)題（共50分）
1．請寫一算法，在順序表中查找指定的數(shù)據(jù)，查找成功則將該記錄放到順序表的最前面，而把其他記錄后退到有個(gè)位置。（10分）
2．有一個(gè)由自然數(shù)構(gòu)成的序列采用單鏈表存儲(chǔ)，試編寫算法判斷該序列是否是fibonacci序列（fibonacci序列是1，1，2，3，5，8，13，21，34，…）。
（10分）
3．定義二叉樹中兩個(gè)結(jié)點(diǎn)之間的最小距離為：這兩個(gè)結(jié)點(diǎn)的最近公共祖先結(jié)點(diǎn)分別到這兩個(gè)結(jié)點(diǎn)的路徑長度之和。請?jiān)O(shè)計(jì)一個(gè)算法，找出給定二叉樹中任意兩個(gè)結(jié)點(diǎn)之間的最小距離。（15分）
4．設(shè)有n個(gè)待排序元素存放在一個(gè)不帶表頭結(jié)點(diǎn)的單鏈表中，每個(gè)鏈表結(jié)點(diǎn)只存放一個(gè)元素，頭指針為head。試設(shè)計(jì)一個(gè)算法，對其進(jìn)行自然歸并排序（按照下面的提示進(jìn)行）。要求不移動(dòng)個(gè)結(jié)點(diǎn)中的元素，只修改結(jié)點(diǎn)中的指針。排序完成后，head仍指示結(jié)果鏈表的第一個(gè)結(jié)點(diǎn)。（15分）
提示：先對待排序的單鏈表進(jìn)行一次掃描，將它劃分為若干有序的子鏈
表，然后反復(fù)進(jìn)行二路歸并，直到將所有子鏈表歸并為一個(gè)有序鏈表為止。

結(jié)束

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

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

: 有用

25人覺得有用

閱讀全文

湖南大學(xué)2003年數(shù)據(jù)結(jié)構(gòu)試題

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