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