數(shù)據(jù)結(jié)構(gòu)試卷

數(shù)據(jù)結(jié)構(gòu)試卷B（總7頁）-本頁僅作為文檔封面，使用時(shí)請(qǐng)直接刪除即可---內(nèi)頁可以根據(jù)需求調(diào)整合適字體及大小-試題B一、填空題(18小題，40個(gè)空，每空分，共20分)1、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的以及它們之間的和運(yùn)算等的學(xué)科。2、線性結(jié)構(gòu)中元素之間存在—關(guān)系，樹形結(jié)構(gòu)中元素之間存在—關(guān)系，圖形結(jié)構(gòu)中元素之間存在—關(guān)系。3、在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)，具體移動(dòng)的元素個(gè)數(shù)與有關(guān)。4、在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為，因此，順序表也稱為的數(shù)據(jù)結(jié)構(gòu)。5、順序表中邏輯上相鄰的元素的物理位置相鄰。單鏈表中邏輯上相鄰的元素的物理位置相鄰。6、若n為主串長，m為子串長，則串的古典(樸素)匹配算法最壞的情況下需要比較字符的總次數(shù)為。7、求下列廣義表操作的結(jié)果：⑴GetHead【((a,b),(c,d))】===; //頭元素不必加括號(hào)GetHead【GetTail【((a,b),(c,d))】】===;GetHead[GetTail[GetHead【((a,b),(c,d))】】】===;GetTail[GetHead[GetTail[((a,b),(c,d))】】】===;8、一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為。9、設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有—個(gè)葉子結(jié)點(diǎn)，有一個(gè)度為2的結(jié)點(diǎn)，有一個(gè)結(jié)點(diǎn)只有非空左子樹，有一個(gè)結(jié)點(diǎn)只有非空右子樹。10、圖有、等存儲(chǔ)結(jié)構(gòu)，遍歷圖有、等方法。11、n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為—；若采用鄰接表存儲(chǔ)，該算法的時(shí)間復(fù)雜度為—。12、用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長度—的次序來得到最短路徑的。13、假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為—；比較四次查找成功的結(jié)點(diǎn)數(shù)為—；平均查找長度為—。14、在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是—。大多數(shù)排序算法都有兩個(gè)基本的操作：—和—。15、在對(duì)一組記錄(54,38,96,23,15,72,60,45,83)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置至少需比較一次。16、在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用—；若初始數(shù)據(jù)基本反序，則選用。17、對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間是，所需要的附加空間是。18、對(duì)n個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為一。二、選擇題（18小題，20個(gè)選項(xiàng)，每選項(xiàng)1分，共20分）1、算法分析的目的是：。A）找出數(shù)據(jù)結(jié)構(gòu)的合理性 B）研究算法中的輸入和輸出的關(guān)系C）分析算法的效率以求改進(jìn) D）分析算法的易懂性和文檔性2、一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的地址是—。A）110 B）108 C）100 D）1203、向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素，并保持原來順序不變，平均要移動(dòng)個(gè)元素。A）8B）C）63 D）74、單鏈表的存儲(chǔ)密度。A）大于1；B）等于1；C）小于1；D）不能確定5、串是一種特殊的線性表，其特殊性體現(xiàn)在：—。A）可以順序存儲(chǔ)B）數(shù)據(jù)元素是一個(gè)字符C）可以鏈?zhǔn)酱鎯?chǔ) D）數(shù)據(jù)元素可以是多個(gè)字符6、假設(shè)有60行70列的二維數(shù)組a[1—60,1-70]以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000,每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a[32,58]的存儲(chǔ)地址為—。（無第0行第0列元素）A）16902B）16904C）14454D）答案A,B,C均不對(duì)7、不含任何結(jié)點(diǎn)的空樹。A）是一棵樹； B）是一棵二叉樹；C）是一棵樹也是一棵二叉樹； D）既不是樹也不是二叉樹8、二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以—。A）它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)； B）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)；C）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)；D）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用9、樹是結(jié)點(diǎn)的有限集合，它（1）根結(jié)點(diǎn)，記為丁。其余的結(jié)點(diǎn)分成為m（m20）個(gè)⑵的集合T1,T2,…，Tm,每個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（1WiWm）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的（3）。A）有0個(gè)或1個(gè)B）有0個(gè)或多個(gè)C）有且只有1個(gè)D）有1個(gè)或1個(gè)以上A）互不相交B）允許相交C）允許葉結(jié)點(diǎn)相交D）允許樹枝結(jié)點(diǎn)相交A）權(quán) B）維數(shù)C）度D）序10、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的一倍。

A)1/2 B)1 C)2D)411、有8個(gè)結(jié)點(diǎn)的無向連通圖最少有一條邊。A)5B)6 C)7D)812、用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用—來實(shí)現(xiàn)算法的。A)棧B)隊(duì)列C)樹D)圖13、已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列A)0321B)C)0132D)14、深度優(yōu)先遍歷類似于二叉樹的A)先序遍歷 B)中序遍歷C)后序遍歷D)層次遍歷15、任何一個(gè)無向連通圖的最小生成樹A)只有一棵B)一棵或多棵C)一定有多棵D)可能不存在16、排序方法中，從未排序序列中依次取出元素與已排序序列(初始時(shí)為空)中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為A)希爾排序 B)冒泡排序 0插入排序 D)選擇排序17、對(duì)有n個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是A)O(n)B)O(n2)C)O(nlog2n)D)O(n3)18、下述幾種排序方法中，要求內(nèi)存最大的是人)插入排序 B)快速排序C)歸并排序 D)選擇排序三、判斷題(10小題，每題1分，共10分)()1、鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。()2、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。()3、線性表的邏輯順序與存儲(chǔ)順序總是一致的()4、對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。()5、棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。()6、二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。()7、用二叉鏈表法(link-rlink)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。()8、有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)1的入度。()9、圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)適用于所有圖。()10、圖的深度優(yōu)先遍歷序列不是惟一的。

四、簡答題（6小題，共22分）1、說明線性表、棧與隊(duì)的異同點(diǎn)。（4分）2、簡述以下算法的功能(棧和隊(duì)列的元素類型均為int)0(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、下列各三元組表分別表示一個(gè)稀疏矩陣，試寫出它們的稀疏矩陣。（3、下列各三元組表分別表示一個(gè)稀疏矩陣，試寫出它們的稀疏矩陣。（4分）2112(1)31344453661162112(1)31344453661164551112493283564374、一棵度為2的樹與一棵二叉樹有何區(qū)別？（3分）5、對(duì)分（折半）查找適不適合鏈表結(jié)構(gòu)的序列，為什么用二分查找的查找速度必然比線性查找的速度快，這種說法對(duì)嗎（5分）6、試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列（3分）。

五、計(jì)算題 （4小題，每題7分，共28分）1、給定二叉樹的兩種遍歷序列，分別是：先序遍歷序列：D,A,C,E,B,H,F,G,I；中序遍歷序列：D,C,B,E,H,A,G,I,