數(shù)據(jù)結構試卷試題B

1、試 題 B一、填空題（18小題，40個空，每空0.5分，共20分）1、數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的 以及它們之間的 和運算等的學科。2、線性結構中元素之間存在 關系，樹形結構中元素之間存在 關系，圖形結構中元素之間存在 關系。3、在順序表中插入或刪除一個元素，需要平均移動 ，具體移動的元素個數(shù)與 有關。4、在順序表中訪問任意一結點的時間復雜度均為 ，因此，順序表也稱為 的數(shù)據(jù)結構。5、順序表中邏輯上相鄰的元素的物理位置 相鄰。單鏈表中邏輯上相鄰的元素的物理位置 相鄰。6、若n為主串長，m為子串長，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數(shù)為 。7、求下列

2、廣義表操作的結果：（1） GetHead【(a,b),(c,d)】= ; /頭元素不必加括號（2） GetHead【GetTail【(a,b),(c,d)】= ;（3） GetHead【GetTail【GetHead【(a,b),(c,d)】= ;（4） GetTail【GetHead【GetTail【(a,b),(c,d)】= ;8、一棵具有個結點的完全二叉樹，它的深度為 。9、設一棵完全二叉樹具有1000個結點，則此完全二叉樹有 個葉子結點，有 個度為2的結點，有 個結點只有非空左子樹，有 個結點只有非空右子樹。10、圖有 、 等存儲結構，遍歷圖有 、 等方法。11、n個頂點e條邊的圖采用

3、鄰接矩陣存儲，廣度優(yōu)先遍歷算法的時間復雜度為 ；若采用鄰接表存儲，該算法的時間復雜度為 。12、用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度 的次序來得到最短路徑的。13、假設在有序線性表a20上進行折半查找，則比較一次查找成功的結點數(shù)為1；比較兩次查找成功的結點數(shù)為 ；比較四次查找成功的結點數(shù)為 ；平均查找長度為 。14、在各種查找方法中，平均查找長度與結點個數(shù)n無關的查找方法是 。大多數(shù)排序算法都有兩個基本的操作： 和 。15、在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置至少

4、需比較 次。16、在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用 ；若初始數(shù)據(jù)基本反序，則選用 。17、對于n個記錄的集合進行歸并排序，所需要的平均時間是 ，所需要的附加空間是 。18、對個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數(shù)為 。二、選擇題（18小題，20個選項，每選項1分，共20分）1、算法分析的目的是： 。A） 找出數(shù)據(jù)結構的合理性 B） 研究算法中的輸入和輸出的關系C） 分析算法的效率以求改進 D） 分析算法的易懂性和文檔性2、一個順序表第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是 。A）110 B）108 C）100 D）1203、向一個有

5、127個元素的順序表中插入一個新元素，并保持原來順序不變，平均要移 動 個元素。A）8 B）63.5 C）63 D）74、單鏈表的存儲密度 。A）大于1； B）等于1； C）小于1； D）不能確定5、串是一種特殊的線性表，其特殊性體現(xiàn)在： 。 A）可以順序存儲 B）數(shù)據(jù)元素是一個字符 C）可以鏈式存儲 D）數(shù)據(jù)元素可以是多個字符6、假設有60行70列的二維數(shù)組a160, 170以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a32,58的存儲地址為 。（無第0行第0列元素） A）16902 B）16904 C）14454 D）答案A, B, C均不

6、對7、不含任何結點的空樹 。A）是一棵樹; B）是一棵二叉樹; C）是一棵樹也是一棵二叉樹; D）既不是樹也不是二叉樹8、二叉樹是非線性數(shù)據(jù)結構，所以 。A）它不能用順序存儲結構存儲; B）它不能用鏈式存儲結構存儲; C）順序存儲結構和鏈式存儲結構都能存儲; D）順序存儲結構和鏈式存儲結構都不能使用 9、樹是結點的有限集合，它（1） 根結點，記為T。其余的結點分成為m（m0）個 （2） 的集合T1，T2，Tm，每個集合又都是樹，此時結點T稱為Ti的父結點，Ti稱為T的子結點（1im）。一個結點的子結點個數(shù)為該結點的（3） 。（1）A）有0個或1個 B）有0個或多個 C）有且只有1個 D）有1個

7、或1個以上 （2）A）互不相交 B） 允許相交 C）允許葉結點相交 D）允許樹枝結點相交（3）A）權 B） 維數(shù) C）度 D）序10、在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 倍。 A）1/2 B）1 C）2 D） 4 11、有8個結點的無向連通圖最少有 條邊。 A）5 B） 6 C）7 D）8 12、用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用 來實現(xiàn)算法的。A）棧 B）隊列 C） 樹 D）圖 13、已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結點序列是 。A）0 3 2 1 B） 0 1 2 3 C）0 1 3 2 D） 0 3 1 214、深度優(yōu)先遍

8、歷類似于二叉樹的 A）先序遍歷 B）中序遍歷 C）后序遍歷 D）層次遍歷15、任何一個無向連通圖的最小生成樹 A）只有一棵 B）一棵或多棵 C）一定有多棵 D）可能不存在16、排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為 A）希爾排序 B）冒泡排序 C）插入排序 D）選擇排序17、對有n個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是 A）O(n) B）O(n2) C）O(nlog2n) D）O(n3)18、下述幾種排序方法中，要求內(nèi)存最大的是 A）插入排序 B）快速排序 C）歸并排序 D）選擇排序三、判斷題

9、（10小題，每題1分，共10分）（ ）1、鏈表的每個結點中都恰好包含一個指針。（ ）2、順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（ ）3、線性表的邏輯順序與存儲順序總是一致的（ ）4、對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。（ ）5、棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。（ ）6、二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。（ ）7、用二叉鏈表法（link-rlink）存儲包含n個結點的二叉樹，結點的2n個指針區(qū)域中有n+1個為空指針。（ ）8、有向圖G用鄰接表矩陣存儲，其第i行的所有元素之和等于頂點i的入度。（ ）9、

10、圖的逆鄰接表存儲結構適用于所有圖。（ ）10、圖的深度優(yōu)先遍歷序列不是惟一的。四、簡答題（6小題 ，共22分）1、說明線性表、棧與隊的異同點。（4分） 2、簡述以下算法的功能（棧和隊列的元素類型均為int）。（3分）void algo(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 3、下列各三元組表分別表示一個稀疏矩陣，試寫出它們的稀疏矩陣。（4分） 4、一棵度為2的樹與一棵二叉樹有何區(qū)別？（3分）5、對分（折半）查找適不適合鏈表結構的序列，為什么用二分查找的查找速度必然比線性查找的速度快，這種說法對嗎（5分）6、試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結點序列（3分）。五、計算題（4小題，每題7分，共28分）1、給定二叉樹的兩種遍歷序列，分別是：先序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I； 中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)