湖南大學2002年數據結構試題（計算機應用）
來源：
時間：2007-06-06 14:42:13
湖南大學 2002 年招收攻讀碩士學位研究生
入學考試命題專用紙
招生專業：計算機科學與應用技術
考試科目：數據結構 試題編號：418
注： 答題（包括填空題、選擇題）必須答在專用答題紙上，否則無效)
－、單選題（每小題2分，共20分）
1．在一個具有n個結點的有序單鏈表中插入一個新的結點使得單鏈表仍然有序的時間復雜度為
A．O(logn) B．O(1) C．O(n2) D．O(n)
2．若線性表最常用的操作是存取第i個元素及其前驅的值，則采用 存儲方式節省時間。
A．單向鏈表 B．雙向鏈表 C．單循環鏈表 D．順序表
3．用單鏈表表示的鏈式隊列的隊頭在鏈表的 位置。
A．鏈頭 B．鏈尾 C．鏈中
4．對二叉樹的結點從1開始進行連續編號，要求每個結點的編號大于其左、右孩子的編號，同一雙親的左、右孩子中，左孩子的編號小于右孩子的編號，則可采用 順序實現編號。
A．前序遍歷 B．中序遍歷 C．后序遍歷 D．層序遍歷
5．己知一算術表達式的中綴形式為A B*C-D／E，后綴形式為ABC* DE／-，其前綴形式為 。
A．-A B*C／DE B．-A B*CD／E C．- *ABC／DE D．- A*BC／DE
6．利用逐點插入法建立序列（50，72，43，85，75，20，35，45，65，30）對的二叉排序樹以后，查找元素35要進行 次元素間的比較。
A．4 B．5 C．7 D．10
7．對于一個具有n個頂點和e條邊的圖，來用鄰接矩陣表示的空間復雜度為 。
A．O(n) B．O(e) C. O(n2) D. (n e)
8.設連通圖G的頂點數n，則G的生成樹的邊數為 。
A．n B．n-1 C．2n D，2n-1
9．下列排序算法中， 算法可能出現下面的情況：在最后一趟排序開始之前，所有元素都不在最終的位置上。
A．堆排序 B．冒泡排序 C．快速排序 D．插入排序
10．設n，m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是
A．n在m右方 B．n是m祖先 C．n在m左方 D．n是m子孫
二、判斷題（判斷下列各小題的敘述是否正確，若正確打“√”，否則打“×”，每小題1分，共10分）
1．線性表中每個元素都有一個前驅和一個后繼。
2．順序表中邏輯關系上相鄰的兩個元素在物理位置上也相鄰。
3．在棧為空的情況下，不能作出棧操作，否則會產生“下溢”。
4．對廣義表A=（a，（b，c），d）的運算head（tail（A））的結果不是b。
5．圖G的一棵最小生成樹的代價未必小于G的其他任何一棵生成樹的代價。
6．若從某頂點開始對含有n個頂點的有向圖G迸行深度優化先遍歷，所得到的遍歷序列唯一，則可斷定起弧數為n－1。
7．二叉樹不能存儲在數組中。
8．理想情況，在散列表中查找一個元素的時間復雜度為O(1)。
9．最優二叉樹是AVL樹（平衡二叉樹）
10．序列（101，88，46，70，34，39，45，58，66，10）是堆。
二、填空題（每空2分，共20分）
1．在有n個元素的順序表中，如果要刪除第i個元素（1≤i≤n）,那么有
個元素必須向表頭方向移動。
2．棧的插入和刪除只能在棧頂一端進行，后進棧的元素必定先被刪除，所以棧又被稱為 表。
3．已知一棵完全二叉樹的第八層有8個結點（根結點在第0層），則該完全二叉樹的葉結點數是 。
4．具有64個結點的完全二又樹共有 層。
5．設n行n列的下三角矩陣A已壓縮到一維數組s[1..n*(n 1)/2]中，若按行序為主存儲，則元素 A[i,j]在S中的存儲位置是 。
6．要將序列{50，16，23，68，94，70，73}建成堆，只需把16與 相互交換。
7．具有n個頂點的有向連通圖最多有 條邊，最少有 條邊。
8．冒泡排序算法在最佳情況下的元素交換次數為 。
9．插入、選擇、冒泡、快速排序算法中，排序趟數與序列的原始狀態有關的排序方法是 。
四、解析題（第1小題6分，第2、4小題各8分，第3小題10分，共32分）
1．請解答下列關于堆的一些問題：
①．堆的存儲表示是順序的還是鏈接的。
②．沒有一個最小堆，即堆中任意元素的關鍵碼均大于它的左子女和右子女的關鍵碼。其具有最大值的元素可能在什么地方？
③．對n個元素進行建初始堆的過程中，最多做多少次數據比較（不用大O表示法）？
2．一棵二叉樹的先序、中序、后序序列如下，其中一部分未標示出，請構造出該二叉樹。
先序序列： C D E G H I K
中序序列: C B F A J K I G
后序序列: E F D B J I H A
3. 一項工程P曲Pl，P2，P3，P4，P5，P6六個子工程組成，這些工程之間有下列關系：P1＞P2，Pl＞P3，Pl＞P4，P2＞P3，P2＞P5，P3＞P6，P4＞P6，P5＞P6。其中符號“＞”表示先于關系，例如：Pl＞P3表示只有Pl完成之后才能進行P3的工作。請給出工程P的四種可能的施工順序。
4．設按如下所述在有序的線性表中查我X：先將X與表中的第4j(j=1，2，3，…)項進行比較，若相等，由查找成功：否則，由某次比較求得比X大的一項
4K之后續而和4K-2，然后和4K-3或4K-1項進行比較，直到查找成功。試畫出當表長n＝16時的判定樹，并求其平均查找長度（考慮查找元素在等概率的情況下）。
五、算法設計題（可用類PASCAL、C或你所熟悉的高級語言設計算法，第1小題8分，第2小題10分，共18分）
1．設計一個函數返回指向一棵二叉樹的T的后序序列的第一個結點的指針，要求采用非遞歸形式，并且不用棧。
2.設計一算法，實現第四大題中第4小題所給出的查找方法。
結束
特別聲明：①凡本網注明稿件來源為"原創"的，轉載必須注明"稿件來源：育路網"，違者將依法追究責任；
②部分稿件來源于網絡，如有侵權，請聯系我們溝通解決。
閱讀全文
招生服務平臺始創于1999年
打開微信掃一掃，關注育路教育官方微信
