湖南大學2003年數據結構試題

來源：時間：2007-06-06 14:42:08

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

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

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

結束

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

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

: 有用

25人覺得有用

閱讀全文

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

湖南大學2003年數據結構試題

2019考研VIP資料免費領取