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

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

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