數(shù)據結構試卷B

數(shù)據結構試卷B數(shù)據結構試卷B數(shù)據結構試卷B數(shù)據結構試卷B編制僅供參考審核批準生效日期地址：電話：傳真:郵編:試題B一、填空題（18小題，40個空，每空分，共20分）1、數(shù)據結構是一門研究非數(shù)值計算的程序設計問題中計算機的以及它們之間的和運算等的學科。2、線性結構中元素之間存在關系，樹形結構中元素之間存在關系，圖形結構中元素之間存在關系。3、在順序表中插入或刪除一個元素，需要平均移動，具體移動的元素個數(shù)與有關。4、在順序表中訪問任意一結點的時間復雜度均為，因此，順序表也稱為的數(shù)據結構。5、順序表中邏輯上相鄰的元素的物理位置相鄰。單鏈表中邏輯上相鄰的元素的物理位置相鄰。6、若n為主串長，m為子串長，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數(shù)為。7、求下列廣義表操作的結果：（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條邊的圖采用鄰接矩陣存儲，廣度優(yōu)先遍歷算法的時間復雜度為；若采用鄰接表存儲，該算法的時間復雜度為。12、用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度的次序來得到最短路徑的。13、假設在有序線性表a[20]上進行折半查找，則比較一次查找成功的結點數(shù)為1；比較兩次查找成功的結點數(shù)為；比較四次查找成功的結點數(shù)為；平均查找長度為。14、在各種查找方法中，平均查找長度與結點個數(shù)n無關的查找方法是。大多數(shù)排序算法都有兩個基本的操作：和。15、在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置至少需比較次。16、在插入和選擇排序中，若初始數(shù)據基本正序，則選用；若初始數(shù)據基本反序，則選用。17、對于n個記錄的集合進行歸并排序，所需要的平均時間是，所需要的附加空間是。18、對ｎ個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數(shù)為。二、選擇題（18小題，20個選項，每選項1分，共20分）1、算法分析的目的是：。A）找出數(shù)據結構的合理性B）研究算法中的輸入和輸出的關系C）分析算法的效率以求改進D）分析算法的易懂性和文檔性2、一個順序表第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是。A）110B）108C）100D）3、向一個有127個元素的順序表中插入一個新元素，并保持原來順序不變，平均要移動個元素。A）8B）C）63D）74、單鏈表的存儲密度。A）大于1；B）等于1；C）小于1；D）不能確定5、串是一種特殊的線性表，其特殊性體現(xiàn)在：。A）可以順序存儲B）數(shù)據元素是一個字符C）可以鏈式存儲D）數(shù)據元素可以是多個字符6、假設有60行70列的二維數(shù)組a[1…60,1…70]以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為。（無第0行第0列元素）A）16902B）16904C）14454D）7、不含任何結點的空樹。A）是一棵樹;B）是一棵二叉樹;C）是一棵樹也是一棵二叉樹;D）既不是樹也不是二叉樹8、二叉樹是非線性數(shù)據結構，所以。A）它不能用順序存儲結構存儲;B）它不能用鏈式存儲結構存儲;C）順序存儲結構和鏈式存儲結構都能存儲;D）順序存儲結構和鏈式存儲結構都不能使用9、樹是結點的有限集合，它（1）根結點，記為T。其余的結點分成為m（m≥0）個（2）的集合T1，T2，…，Tm，每個集合又都是樹，此時結點T稱為Ti的父結點，Ti稱為T的子結點（1≤i≤m）。一個結點的子結點個數(shù)為該結點的（3）。（1）A）有0個或1個B）有0個或多個C）有且只有1個D）有1個或1個以上（2）A）互不相交 B）允許相交C）允許葉結點相交D）允許樹枝結點相交（3）A）權 B）維數(shù)C）度D）序10、在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍。A）1/2B）1C）2D）11、有8個結點的無向連通圖最少有條邊。A）5B）6C）712、用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用來實現(xiàn)算法的。A）棧B）隊列C）樹D）圖13、已知圖的鄰接表如下所示，根據算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結點序列是。A）A）0321B）0123C）0132D）14、深度優(yōu)先遍歷類似于二叉樹的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、下述幾種排序方法中，要求內存最大的是A）插入排序B）快速排序C）歸并排序D）選擇排序三、判斷題（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、圖的深度優(yōu)先遍歷序列不是惟一的。四、簡答題（6小題，共22分）1、說明線性表、棧與隊的異同點。（4分）2、簡述以下算法的功能（棧和隊列的元素類型均為int）。（3分）voidalgo(Queue&Q){StackS;intd;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、給定二叉樹的兩種遍歷序列，分別是：先序遍