湖南大學2001年數據結構試題（計算機應用）

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

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