數(shù)據(jù)結構試題1(有答案)

1、..1.2.3.試題1 一、單選題（每題1. 對一個算法的評價，不包括如下（A .健壯性和可讀性B .并行性分，共20分）方面的內(nèi)容。C.正確性D.時空復雜度2. 在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針 P指向的結 點，則執(zhí)行（）。A. p-n ext=HL-n ext; HL-n ext=p;B. p-n ext=HL; HL=p;C. p- next=HL; p=HL;D. HL=p; p- next=HL;3. 對線性表，在下列哪種情況下應當采用鏈表表示？（）A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲

2、空間D.表中元素的個數(shù)不變一個棧的輸入序列為1 2 3,則下列序列中不可能是棧的 輸出序列的是 C ）A. 2 3 1C. 3 1 2AOV網(wǎng)是一種（4.(5.B. 3 2 1D. 1 2 3A.有向圖B.無向圖6. 采用開放定址法處理散列表的沖突時，其平均查找長度（A .低于鏈接法處理沖突B.高于鏈接法處理沖突C.與鏈接法處理沖突相同D .高于二分查找7. 若需要利用形參直接訪問實參時，應將形參變量說明為（A .值 B.函數(shù)C.指針8. 在稀疏矩陣的帶行指針向量的鏈接存儲中， 有相同的（）。A .行號 B.列號C.元素值9. 快速排序在最壞情況下的時間復雜度為（A. O（log2n）B. O

3、（nIog2n）C.C.無向無環(huán)圖D .有向無環(huán)圖）。）參數(shù)。D .引用每個單鏈表中的結點都具D .非零元素個數(shù) ）。0（n）10.10.從二叉搜索樹中查找一個元素時，其時間復雜度大致為A. O（ n）B. O（1） C. O（log2 n）D. O（ n2）D . 0(n2)()。運算題（每題6分，共24分）1. 數(shù)據(jù)結構是指數(shù)據(jù)及其相互之間的. 對N （ M: N ）的聯(lián)系時，稱這種結構為2. 隊列的插入操作是在隊列的 _尾首行。3. 當用長度為N的數(shù)組順序存儲一個棧時，假定用top=N表示?？眨瑒t表示棧滿的條件是 top=0（要超出才為滿）。4. 對于一個長度為n的單鏈存儲的線性表，在表

4、頭插入元素的時間復雜度。當結點之間存在M進行，刪除操作是在隊列的4.5.6.為 在表尾插入元素的時間復雜度為5. 設W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標i從0到7，列下標j從0到3，則二維數(shù)組W的數(shù)據(jù)元素共占用個字節(jié)。W中第6行的元素和第4列的元素共占用個字節(jié)。若按行順序存放二維數(shù)組 W，其起始地址為100,則二維數(shù)組元素 W6，3的起始 地址為。6. 廣義表A= (a,(a,b),(a,b),c),則它的深度為,它的長度為0.7. 二叉樹是指度為2的_ 樹，其所有結點的度的總和是8. 對一棵二叉搜索樹進行中序遍歷時，得到的結點序列是一個 。對一棵由算術表達式組成

5、的二叉語法樹進行后序遍歷得到的結點序列是該算術表達式的。9. 對于一棵具有n個結點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為個，其中個用于指向孩子， 指針是空閑的。10. 若對一棵完全二叉樹從0開始進行結點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結點存儲到A0中。其余類推，貝U Ai 元素的左孩子元素為 ，右孩子元素為，雙親元素為樹。一棵結點數(shù)為N的二叉11.12.11. 在線性表的散列存儲中，處理沖突的常用方法有和 種。12. 當待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用 卡序；當待排序的記錄數(shù)較大，存儲空間允許且要求排序 是穩(wěn)定時，宜采用 卡序。1.1.已

6、知一個運算題(每題6分，共24分)6 5稀疏矩陣如下所示，000050000007000000122.3.4.試：（1）（ 1）寫出它的三元組線性表；（2）（ 2）給出三元組線性表的順序存儲表示。2. 設有一個輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80，試畫出從空樹起, 逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。3. 對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的 邊結點都是按照終點序號從小到大的次序鏈接的，試寫出：從頂點出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；從頂點出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 已知一個圖的頂點集V和邊集(1)4.E分別為：V

7、=1,2,3,4,5,6,7;E=v2,1,若存儲它采用鄰接表，并且每個頂 點鄰接表中的邊結點都是按照終點序 號從小到大的次序鏈接的，按主教材 中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列。1.閱讀算法（每題7分，共14分）int P nme（i nt n）2.四、1.int i=1;int x=(i nt) sqrt (n);while (+ix) retur n 1;else return 0;(1) 指出該算法的功能；(2) 該算法的時間復雜度是多少？2.寫出下述算法的功能:void AJ(adjlist GL, i nt i, i nt n)Queue Q;Ini tQue

8、ue(Q);coutvvivv; visitedi=true;QIn sert(Q,i); while(!QueueE mp ty(Q) int k=QDelete(Q); edge no de* p=GLk; while( p!=NULL) int j=p-adjvex;if(!visitedj)coutvvjvv; visitedj=true; QI nsert(Q,j);p=p-n ext;算法填空(共8分) 如下為二分查找的非遞歸算法，試將其填寫完整。Int Bin sch(ElemT ype A ,i nt n ,KeyTy pe K)int low=0;int high=n-1;w

9、hile (low=high)int mid=if (K=Amid.key) return mid;else if (Kmid.key)四、五、查找成功，返回元素的下標/在左子表上/在右子表II查找失敗，返回-1繼續(xù)查找else上繼續(xù)查找return -1;五、八、編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結點的算法。ElemT ype DeleFro nt（LNode * & HL）參考答案、單選題（每題2 分,共20分）1.B2.A3.B4.C5.D6.B7.D8.A9.D10.C、填空題（每空1 分,共26分）1.1.聯(lián)系圖（或圖結構）2.2.尾 首3.3.top=O4.4.O

10、 (1)O (n)5.5.128441086.6.337.7.有,序n-165515132-145-25156371.圖7&0.11.12.有序序列2n n-12i+1開放定址法 快速后綴表達式（或逆波蘭式）n+1 2i+2鏈接法 歸并運算題（每題6分，共24分）(i-1)/2(1)1.（1,5,1）,（3,2,-1）,（4,5,-2）,（5,1,5）,（6,3,7）(3分)2.2.如圖8所示。3.3.DFS:BFS:4.4.拓樸排序為：43 65721四、四、閱讀算法（每題7分，共14分）1.1.（1）判斷n是否是素數(shù)（或質數(shù)）(2)O（石）2.2.功能為：從初始