湖南大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)試題（計(jì)算機(jī)應(yīng)用）

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

湖南大學(xué) 2001 年招收攻讀碩士學(xué)位研究生
入學(xué)考試命題專用紙
招生專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)
考試科目：數(shù)據(jù)結(jié)構(gòu) 試題編號(hào)：41026
注：答題（包括填空題、選擇題）必須答在專用答題紙上，否則無(wú)效)
一、填空題（每空1.5分，共15分）
1．在有n個(gè)元素的順序表中，若想在第i個(gè)元素（1≤i≤n 1）之前插入一個(gè)元素時(shí)，需向表尾方向移動(dòng) 元素。
2．在一個(gè)循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的
3．在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向其結(jié)點(diǎn)，另一個(gè)指向其結(jié)點(diǎn)。
4．設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組s[1..n*(n 1)/2]中，若按行序?yàn)橹鞔鎯?chǔ)，則元素 A[i,j]在S中的存儲(chǔ)位置是。
5．若某二叉樹中有30個(gè)葉結(jié)點(diǎn)，另有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子結(jié)點(diǎn)，則該二叉樹中總共有個(gè)結(jié)點(diǎn)。
6．具有n個(gè)頂點(diǎn)的無(wú)向連通圖至少有條邊。
7．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則所有鄰接表中的結(jié)點(diǎn)總數(shù)為。
8．利用插入排序算法對(duì)n個(gè)記錄進(jìn)行排序，最佳情況下，對(duì)關(guān)鍵字進(jìn)行的比較次數(shù)為次。
9．在散列存儲(chǔ)中裝填因子的值越小，則。
二、判斷題（判斷下列各題是否正確，若正確打“√“，否則打“×”，每小題⒈5分，共15分）
l．線性表的唯一存儲(chǔ)形式是數(shù)組。
2．線性表的邏輯順序與存儲(chǔ)順序總是一致的。
3．二維數(shù)組是它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線性表。
4．每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找。
5．刪除二叉排序樹中的一個(gè)結(jié)點(diǎn)，再重新插人進(jìn)去，一定能得到原來(lái)的二叉排序樹。
6．若一個(gè)葉結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它也是該二叉樹的前序遍歷序列的最后一個(gè)結(jié)點(diǎn)。
7．無(wú)向圖用鄰接矩陣表示后，該矩陣一定是對(duì)稱矩陣。
8．對(duì)任意一個(gè)圖，從它的某個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷，可訪問到該圖的每一個(gè)結(jié)點(diǎn)。
9．快速排序算法在每一趟排序中都能找到一個(gè)元素放到其最終位置上。
10．理想情況下，在散列表中查找一個(gè)元素的時(shí)間復(fù)雜度為O(1)。
三、單選題（在本題的每一小題的備選答案中，只有一個(gè)答案是正確的，請(qǐng)選擇你認(rèn)為正確的答案的標(biāo)號(hào)，多選不給分。每小題⒈5分，共15分）
1．算法分析的目的是。
A．找出數(shù)據(jù)結(jié)構(gòu)的合理性 B．研究算法中的輸入和輸出關(guān)系
C．分析算法的效率以求改邀 D．分析算法的易讀性和文檔性
2．一個(gè)棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是。
A．edcba B．decba C．dceab D．a(chǎn)bcde
3．將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，最少需要比較次。
A．n -1 B．n C． 2n-1 D．2n
4．對(duì)一棵二叉排序樹進(jìn)行遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。
A．前序 B．中序 C．后序 D．層序
5．某二叉樹的前序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是。
A．空或只有一個(gè)結(jié)點(diǎn) B．完全二叉數(shù)
C．二又排序樹 D．高度等于結(jié)點(diǎn)數(shù)
6．任何一個(gè)無(wú)向連通圖的最小生成樹。
A．有一棵或多棵 B．只有一棵
C．一定有多課 D．可能不存在
7．下列排序算法中算法占用的輔助空間最多。
A．堆排序 B．shell排序 C．快速排序 D．歸并排序
8．若數(shù)據(jù)表中每個(gè)元素己距其最終位置不遠(yuǎn)，則采用算法進(jìn)行排序時(shí)間最省。
A．選擇排序 B．快速排序 C．堆排序 D．插入排序
9．有一長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，且查找每個(gè)元素的概率相同，則查找成功所需的平均比較次數(shù)為。
A．35／12 B．37／12 C．39/12 D．43/12
10．如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用
查找方法。
A．二分 B．順序 C．分塊 D．散列

解析題（1小題8分，2、3小題各10分，4小題9分，共37分）

已知樹的父結(jié)點(diǎn)表示如下，其中各兄弟結(jié)點(diǎn)是依次出現(xiàn)的，畫出該樹及對(duì)應(yīng)的二叉數(shù)。

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
A	B	C	D	E	F	G	H	I	J	K	L	M	N	O
/	0	0	0	1	1	2	2	3	3	4	5	5	6	7

結(jié)點(diǎn)下標(biāo)

結(jié)點(diǎn)標(biāo)記

父結(jié)點(diǎn)下標(biāo)

根據(jù)下面的字母/頻度表構(gòu)造一棵Huffman樹，并給出各字母的Huffman編碼。

A	B	C	D	E	F	G	H	I	J	K	L
2	3	5	7	11	13	17	19	23	31	37	41

字母

頻度值

3．若一個(gè)帶權(quán)無(wú)向圖的鄰接矩陣如下圖所示，畫出該圖，并按prim算法構(gòu)造出該圖的一棵最小生成樹（要有其構(gòu)造步驟）。

0 1 2 3 4 5

結(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人覺得有用

閱讀全文

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

免費(fèi)領(lǐng)取 :

意向?qū)W校/專業(yè) :

學(xué)生姓名 :

聯(lián)系手機(jī) :

【隱私保障】

育路為您提供專業(yè)解答


0	∞	7	∞	9	∞
∞	0	5	∞	∞	6
7	5	0	1	∞	2

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

湖南大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)試題（計(jì)算機(jī)應(yīng)用）

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