算法與數(shù)據(jù)結(jié)構(gòu)期末考試試卷

1、.課程測試試題（卷）以下為教師填寫I、命題院（部）：數(shù)學(xué)與計算機科學(xué)學(xué)院II、課程名稱：數(shù)據(jù)結(jié)構(gòu)III、測試學(xué)期：2020學(xué)年度第學(xué)期IV、測試對象：學(xué)院專業(yè)級班V 、問卷頁數(shù)（A4）:頁V I、答卷頁數(shù)（A4）:頁V II、考試方式：閉卷（開卷、閉卷或課程小論文，請?zhí)顚懬宄￢III、問卷內(nèi)容：（請老師在出題時安排緊湊，填空題象征性的留出一點空格,學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號）一、一、單選題（每題2分，共20分）1. 1.對一個算法的評價，不包括如下（B）方面的內(nèi)容。A.健壯性和可讀性B.并行性C.正確性D.時空復(fù)雜度2. 2.在帶有頭結(jié)點的單鏈表HL中，

2、要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（A）。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;3. 3.對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（B）A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變4. 4.一個棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是（C）B. 3 2 1D. 1 2 3A.231C.3125. 5.AOV網(wǎng)是一種（D）。A.有向

3、圖B.無向圖C.無向無環(huán)圖D.有向無環(huán)圖6. 6.采用開放定址法處理散列表的沖突時，其平均查找長度(B)。A.低于鏈接法處理沖突B.高于鏈接法處理沖突C.與鏈接法處理沖突相同D.高于二分查找7. 7.若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為(D)參數(shù)。A.值B.函數(shù)C.指針D.引用8. 8.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的(A)。A.行號B.列號C.元素值D.非零元素個數(shù)9. 9.快速排序在最壞情況下的時間復(fù)雜度為(C)。2、A.O(log2n)B.O(nlog2n)C.0(n)D.0(n)10.10. 從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致

4、為(D)。A.O(n)B.O(1)C.O(log2n)D.O(n2)二、二、運算題(每題6分，共24分)1. 1.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的，當(dāng)結(jié)點之間存在M對N(M:N)的聯(lián)系時，稱這種結(jié)構(gòu)為2. 2.隊列的插入操作是在隊列的進(jìn)行，刪除操作是在隊列的_4行。3. 3.當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top=N表示?？?，則表示棧滿的條件是4. 4.對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為,在表尾插入元素的時間復(fù)雜度為5. 5.設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標(biāo)i從0到7,列下標(biāo)j從0到3,則二維數(shù)組W的數(shù)據(jù)元素共占用個字節(jié)。W中第6行的

5、元素和第4列的元素共占用個字節(jié)。若按行順序存放二維數(shù)組W,其起始地址為100,則二維數(shù)組元素W6,3的起始地址為。6. 6.廣義表A=(a,(a,b),(a,b),c),則它的深度為,它的長度為7. 7.二叉樹是指度為2的捌。一棵結(jié)點數(shù)為N的二叉樹，其所有結(jié)點的度的總和是8. 8.對一棵二叉搜索樹進(jìn)行中序遍歷時，得到的結(jié)點序列是一個對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點序列是該算術(shù)表達(dá)式的9. 9.對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為個,其中個用于指向孩子，個指針是空閑的。1.10. .若對一棵完全二叉樹從0開始進(jìn)行結(jié)點的編號，并按此編號把它順序存儲到

6、一維數(shù)組A中，即編號為0的結(jié)點存儲到A0中。其余類推，則Ai元素的左孩子元素為，右孩子元素為2雙親元素為11. 11.在線性表的散列存儲中，處理沖突的常用方法有口兇種。12. 12.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用排序；當(dāng)待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用排序。三、三、運算題(每題6分，共24分)1. 1.已知一個65稀疏矩陣如下所示，000010000001000000025000000700試：(1) (1)寫出它的三元組線性表；(2) (2)給出三元組線性表的順序存儲表示。2. 2.設(shè)有一個輸入數(shù)據(jù)的序列是46,25,78,62,12

7、,80,試畫出從空樹起,逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。3. 3.對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試寫出：(1)從頂點出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2)從頂點出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；4. 4.已知一個圖的頂點集V和邊集E分別為：.V=1,2,3,4,5,6,7;E=<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,&l

8、t;6,2>,<6,5>；若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，按主教材試給出得到的拓樸排序的序列。77分，共14分)1. 1.intPrime(intn)inti=1;intx=(int)sqrt(n);while(+i<=x)if(n%i=0)break;if(i>x)return1;圖8elsereturn0;2. (1)指出該算法的功能；1.3. (1)答案：判斷n是否是素數(shù)(或質(zhì)數(shù))(2)該算法的時間復(fù)雜度是多少？答案：O(<n)4. 2.寫出下述算法的功能:voidAJ(adjlistGL,inti

9、,intn)QueueQ;InitQueue(Q);cout<<i<<''visitedi=true;QInsert(Q,i);while(!QueueEmpty(Q)intk=QDelete(Q);edgenode*p=GLk;while(p!=NULL)intj=p->adjvex;if(!visitedj)cout<<j<<''visitedj=true;QInsert(Q,j);p=p->next;5. 2.功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。5、 五、算法填空(共8分)

10、如下為二分查找的非遞歸算法，試將其填寫完整。IntBinsch(ElemTypeA,intn,KeyTypeK)intlow=0;inthigh=n-1;while(low<=high)intmid=(low+high)/2_if(K=Amid.key)returnmid;查找成功，返回元素的下標(biāo)elseif(K<mid.key)high=mid-1;在左子表上繼續(xù)查找elselow=mid+1;/在右子表上繼續(xù)查找return-1;/查找失敗，返回-16、 六、編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點的算法ElemTypeDeleFront(LNode*&

11、HL)答案：ElemTypeDeleFront(LNode*&HL)if(HL=NULL)cerr<<"空表"<<endl;exit(1);LNode*p=HL;HL=HL->next;ElemTypetemp=p->data;deletep;returntemp;參考答案1、 一、單選題(每題2分，共20分)1.B2,A3.B4.C5.D6.B7.D8.A9.D10.C2、 二、填空題(每空1分，共26分)1. 1.聯(lián)系圖(或圖結(jié)構(gòu))2. 2.尾首3. 3.top=04. 4.O(1)O(n)5. 5.128441086. 6.

12、3365515132-145-2515637圖710. 10. 2i+111. 11.開放定址法7. 7.有序8. 8.有序序列n-1后綴表達(dá)式（或逆波蘭式）9. 9. 2n n-1n+12i+2(i-1)/2鏈接法12. 12.快速歸并三、三、運算題（每題6分，共24分）1.1.(1)(1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)(3 分)BFS:4. 4.拓樸排序為:四、四、2. 2.如圖8所示。3. 3.DFS:4365721閱讀算法（每題7分，共14分）4. 1.（1）判斷n是否是素數(shù)（或質(zhì)數(shù)）o(yn)5. 2.功能為：從初始點v出發(fā)廣度優(yōu)先搜索由

13、鄰接表GL所表示的圖。5、 五、算法填空(8分)(low+high)/2high=mid-1low=mid+16、 六、編寫算法(8分)ElemTypeDeleFront(LNode*&HL)if(HL=NULL)cerr<<"空表"<<endl;exit(1);LNode*p=HL;HL=HL->next;ElemTypetemp=p->data;deletep;returntemp;吉首大學(xué)試題庫課程測試試題（卷）以下為教師填寫I、命題院（部）：數(shù)學(xué)與計算機科學(xué)學(xué)院II、課程名稱：數(shù)據(jù)結(jié)構(gòu)III、測試學(xué)期：20-20學(xué)年度第學(xué)

14、期IV、測試對象：學(xué)院專業(yè)級班V、問卷頁數(shù)（A4）:頁VI、答卷頁數(shù)（A4）:頁VII、考試方式：閉卷（開卷、閉卷或課程小論文，請?zhí)顚懬宄￢III、問卷內(nèi)容：（請老師在出題時安排緊湊，填空題象征性的留出一點空格,學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號）單選題（每題2分，共20分）1. 1.棧和隊列的共同特點是（）。A.只允許在端點處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點2. 2.用鏈接方式存儲的隊列，在進(jìn)行插入運算時（）.A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改3. 3.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？

15、（）A.隊列B.棧C.線性表D.二叉樹692D. 696B.無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)D. 2k-14. 4.設(shè)有一個二維數(shù)組Amn,假設(shè)A0存放位置在644（1%A22存放位置在676（10）,每個元素占一個空間，問A33（10）存放在什么位置？腳注（10）表示用10進(jìn)制表示。A.688B.678C.5. 5.樹最適合用來表示（）。A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)6. 6.二叉樹的第k層的結(jié)點數(shù)最多為（）.A.2k-1B.2K+1C.2K-17. 7.若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為

16、（）A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,38. 8.對n個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為A.0（1）B.O（n）C.O（1og2n）D.O（n2）9. 9.對于線性表（7,34,55,25,64,46,20,10）進(jìn)行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（）個，A.1B.2C.3D.410.10.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有（）條邊才能確保是一個連通圖。A.5B.6C.7D.8二、二、填空題（每空1分，共26分）1. 1.通常從四個方面評價算法的質(zhì)量：>和02. 2.一個算法的時間復(fù)雜度為（n3+n2l

17、og2n+14n）/n2,其數(shù)量級表示為.3. 3.假定一棵樹的廣義表表示為A(C,D(E,F,G),H(I,J),則樹中所含的結(jié)點數(shù)為個，樹的深度為,樹的度為4. 4.后綴算式923+-102/-的值為中綴算式(3+4X)-2Y/3對應(yīng)的后綴算式為5. 5.若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共有個指針域，其中有個指針域是存放了地址，有個指針是空指針。6. 6.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點分別有個和個。7. 7.AOV網(wǎng)是一種的圖。8. 8.在一個具有n個頂點的無向完

18、全圖中，包含有條邊，在一個具有n個頂點的有向完全圖中，包含有條邊。9. 9.假定一個線性表為(12,23,74,55,63,40),若按Key%4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為口10. 10.向一棵B樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度。11. 11.在堆排序的過程中，對任一分支結(jié)點進(jìn)行篩運算的時間復(fù)雜度為,整個堆排序過程的時間復(fù)雜度為。12. 12.在快速排序、堆排序、歸并排序中，排序是穩(wěn)定的。運算題(每題6分，共24分)1. 1.在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A0.next,試寫出該線性表。605078903

19、4403572041datanextA01234562. 2.請畫出圖10的鄰接矩陣和鄰接表。3. 3.已知一個圖的頂點集V和邊集E分別為:V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4. 4.畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時，每加入一個數(shù)據(jù)后堆的變化4、 四、閱讀算法(每題7分，共14分)1. 1.LinkListmynote(LinkList

20、L)/L是不帶頭結(jié)點的單鏈表的頭指針if(L&&L->next)q=L;L=L>next;p=L;51: while(p>next)p=p>next；52: p>next=q；q>next=NULL;returnL；請回答下列問題：(1)說明語句S1的功能；(2)說明語句組S2的功能；(3)設(shè)鏈表表示的線性表為(a1,a2,)，寫出算法執(zhí)行后的返回值所表示的線性表。2. 2.voidABC(BTNode*BT)ifBTABC(BT->left);ABC(BT->right);cout<<BT->data<&

21、lt;''該算法的功能是：5、 五、算法填空(共8分)二叉搜索樹的查找一一遞歸算法：boolFind(BTreeNode*BST,ElemType&item)if(BST=NULL)returnfalse;/查找失敗elseif(item=BST->data)讓em=BST->data;/叱找成功return;elseif(item<BST->data)returnFind(,item);elsereturnFind(,item);/if6、 六、編寫算法(共8分)統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。intCountX(LNode*H

22、L,ElemTypex)參考答案單選題(每題2分，共20分)1 .A2,D3.D4.C5.C6.D7.D8.C9.D10.A二、二、填空題(每空1分，共26分)強壯性高效率1. 1.正確性易讀性2. 2.O(n)3. 3.9334. 4.-15. 5. 2n n-1n+16. 6. e 2e7. 7.有向無回路8. 8. n(n-1)/2n(n-1)9. 9.(12, 40)( )(74)(23,55, 63)10. 10.增加 111. 11. O(log 2n) O(nlog 2n)12. 12.歸并三、運算題(每題6分，共24分)1. 1.線性表為：(78, 50, 40, 60, 34

23、, 90)0 111010 10 12. 2.鄰接矩陣:110 1110 10 10 1110鄰接表如圖11所示:圖113. 3.用克魯斯卡爾算法得到的最小生成樹為:.4. 4. 見圖12四、14分)（1）查詢鏈表的尾結(jié)點將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點返回的線性表為（a2,a3,，an,a）(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20四、1. 1.(2)(3)2. 2.遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄洹?分，共8分）5、 五、算法填空（每空trueBST->leftBST->right6、 六、編寫算法（8分）intCountX

24、(LNode*HL,ElemTypex)inti=0;LNode*p=HL;/i為計數(shù)器while(p!=NULL)if(P->data=x)i+;p=p->next;/while,出循環(huán)時i中的值即為x結(jié)點個數(shù)returni;/CountX吉首大學(xué)試題庫課程測試試題（卷）以下為教師填寫I、命題院（部）：數(shù)學(xué)與計算機科學(xué)學(xué)院II、課程名稱：數(shù)據(jù)結(jié)構(gòu)III、測試學(xué)期：2020學(xué)年度第學(xué)期IV、測試對象：學(xué)院專業(yè)級班V、問卷頁數(shù)（A4）:頁VI、答卷頁數(shù)（A4）:頁VII、考試方式：閉卷（開卷、閉卷或課程小論文，請?zhí)顚懬宄￢III、問卷內(nèi)容：（請老師在出題時安排緊湊，填空題象征性的留

25、出一點空格,學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號）1、 一、單選題（每小題2分，共8分）1、1、在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為（）。AnBn/2C（n+1）/2D（n-1）/22、2、在一個單鏈表中，若q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q與p之間插入一個s所指的結(jié)點，則執(zhí)行（）。Asflink=pflink;pTink=s;Bp-link=s;sflink=q;CpTink=sTink;sflink=p;DqTink=s;sTink=p;3、 3、棧的插入和

26、刪除操作在（）進(jìn)行。A棧頂B棧底C任意位置D指定位置4、 4、由權(quán)值分別為11,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）A24B71C48D532、 二、填空題（每空1分，共32分）1、1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為?、和四種。2、2、一種抽象數(shù)據(jù)類型包括?口網(wǎng)個部分。456783、3、在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為ao.next,則該線性表為6056423874254376201a0123datanext4、4、在以HL為表頭指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為5、5、用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總

27、是指向隊首元素的,該循環(huán)隊列白最大長度為。6、6、當(dāng)堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用表示;當(dāng)堆棧采用鏈接存儲結(jié)構(gòu)時,棧頂元素的值可用表示。7、7、一棵高度為5的二叉樹中最少含有個結(jié)點，最多含有個結(jié)點；一棵高度為5的理想平衡樹中，最少含有個結(jié)點，最多含有個結(jié)點。8、8、在圖的鄰接表中，每個結(jié)點被稱為2通常它包含三個域：_是;二是;三是9、9、在一個索引文件的索引表中，每個索引項包含對應(yīng)記錄的和兩項數(shù)據(jù)。10、 10、假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J),則樹中所含的結(jié)點數(shù)為個，樹的深度為,樹的度為,結(jié)點H的雙親結(jié)點為，孩子結(jié)點為11、 11、在堆排序的過程中

28、，對任一分支結(jié)點進(jìn)行篩運算的時間復(fù)雜度為，整個堆排序過程的時間復(fù)雜度為12、 12、在對m階的B樹插入元素的過程中，每向一個結(jié)點插入一個索引項(葉子結(jié)點中的索引項為關(guān)鍵字和空指針)后，若該結(jié)點的索引項數(shù)等于個，則必須把它分裂為個結(jié)點。3、 運算題(每小題6分，共24分)1、1、已知一組記錄的排序碼為(46,79,56,38,40,80,95,24),寫出對其進(jìn)行快速排序的每一次劃分結(jié)果。2、2、一個線性表為B=(12,23,45,57,20,03,78,31,15,36),設(shè)散列表為HT0.12,散列函數(shù)為H(key)=key%13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成

29、功的平均查找長度。3、3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ,中序遍歷的結(jié)果是EBCDAFHIGJ,試寫出這棵二叉樹的后序遍歷結(jié)果。4、4、已知一個圖的頂點集V各邊集G如下：V=0,1,2,3,4,5,6,7,8,9;E=(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3,8),(5,6),(5,8),(5,9),(6,7),(7,8),(8,9)當(dāng)它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V。出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷等到的頂點序列。假定每個頂點鄰接表中的結(jié)點是按頂點序號從大到小的次序鏈接的。深度優(yōu)先序列廣度優(yōu)

30、先序列鄰接矩陣表示時鄰接表表示時4、 四、閱讀算法，回答問題(每小題8分，共16分)1、假定從鍵盤上輸入一批整數(shù)，依次為：786345309134-1,請寫出輸出結(jié)果。# include<iostream.h># include<stdlib.h>consstintstackmaxsize=30;typedefintelemtype;structstackelemtypestackstackmaxsize;inttop;#include“stack.h"Voidmain()stacka;initstack(a);intx;cin>>x;while(

31、x!=-1)push(a,x);cin>>x;while(!stackempty(a)cout<<pop(a)<<"”;cout<<end1;該算法的輸出結(jié)果為：2、閱讀以下二叉樹操作算法，指出該算法的功能.Template<calsstype>voidBinTree<Type>:unknown(BinTreeNode<Type>*t)BinTreeNode<Type>*p=t,*temp;if(p!=NULL)temp=pleftchild;pleftchild=pfrightchild

32、;pfrightchild=temp;unknown(pTeftchild);undnown(pfrightchild);該算法的功能是：5、 算法填空，在畫有橫線的地方填寫合適的內(nèi)容(10分)對順序存儲的有序表進(jìn)行二分查找的遞歸算法。intBinsch(ElemTypeA,intlow,inthigh,KeyTypeK)if(low<=high)intmid=1if(K=Amid.key)returnmid;elseif(K<Amid.key)return2elsereturn3elsereturn46、 六、編寫算法(10分)編寫算法，將一個結(jié)點類型為Lnode的單鏈表按逆序鏈

33、接，即若原單鏈表中存儲元素的次序為a1,nn-1,an,則逆序鏈接后變?yōu)?an,an-1,a1。Voidcontrary(Lnode*&HL)數(shù)據(jù)結(jié)構(gòu)試題（答案）、單選題（每小題2分，共8分）題號1234答案CDAB二、填空題（每空1分，共32分）1:集合、線性、樹、圖；2:數(shù)據(jù)描述、操作聲名；3:（38,56,25,60,42,74）;4：HLfnext=NULL;HL=HLfnext;5:前一個位置；n-1;6:S.stackS.top;HSdata;7:5318:邊結(jié)點、鄰接點域、權(quán)域、鏈域；9:索引值域、開始位置域；10:10、3、3、B、I和J;11:O（log2n）、O（n

34、log2n）;12：m、m-1三、運算題（每小題6分，共24分）1、劃分次序劃分結(jié)果%L、次3824404656809579第二次2438404656809579第三次2438404656809579第四次2438404656809579第五次2438404656798095第六次24384046567980952、012345678910111278150357452031233612查找成功的平均查找長度：ASLsucc=14/10=1.43、此二叉樹的后序遍歷結(jié)果是：EDCBIHJGFA4、圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時0,1,2,8,3,4,5,6,7,90,1,4,2,7,

35、3,8,6,5,9鄰接表表示時0,4,3,8,9,5,6,7,1,20,4,1,3,7,2,8,6,9,5四、閱讀算法，回答問題（每小題8分，共16分）1、1、該算法的輸入結(jié)果是：3491304563782、2、該算法的功能是：交換二叉樹的左右子樹的遞歸算法。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(10分)1、1是：(low+high)/2;2 是：Binsch(A,low,mid-1,K);3 是:Binsch(A,mid+1,high,K);4 是：-1;六、編寫算法(10分)根據(jù)編程情況，酌情給分。Lnode*P=HL;HL=NULL;While(p!=null)Lnode*q=p

36、;P=p-next;qfnext=HL;HL=q;吉首大學(xué)試題庫課程測試試題（卷）以下為教師填寫I、命題院（部）：數(shù)學(xué)與計算機科學(xué)學(xué)院II、課程名稱：數(shù)據(jù)結(jié)構(gòu)III、測試學(xué)期：2020學(xué)年度第學(xué)期IV、測試對象：學(xué)院專業(yè)級班V、問卷頁數(shù)（A4）:頁VI、答卷頁數(shù)（A4）:頁VII、考試方式：閉卷（開卷、閉卷或課程小論文，請?zhí)顚懬宄￢III、問卷內(nèi)容：（請老師在出題時安排緊湊，填空題象征性的留出一點空格，學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號）第一部分選擇題（30分）一、一、項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項中只有一個選項是符合題

37、目要求的，請將正確選項前的字母填在題B.解決問題的計算方法D.解決問題的有限運算序列2.線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（3.A.必須是不連續(xù)的B.連續(xù)與否均可C.必須是連續(xù)的D.和頭結(jié)點的存儲地址相連續(xù)將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為A. O (1)B. O (n)C. O (m)D. O (m+n)后的括號內(nèi)。算法指的是（A.計算機程序C排序算法4.由兩個棧共享一個向量空間的好處是：（）A.減少存取時間，降低下溢發(fā)生的機率B.節(jié)省存儲空間，降低上溢發(fā)生的機率C.減少存取時間，降低上溢發(fā)生的機率D.節(jié)省存儲空間，降低下溢發(fā)生的機率5.設(shè)數(shù)組datam作為循

38、環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾6.指針，則執(zhí)行出隊操作后其頭指針A. front=front+1C. front=（front-1）%m如下陳述中正確的是（）A.用是一種特殊的線性表C.用中元素只能是字母front值為(B.D.B.front=(front+1)%(m-1) front=(front+1)%m用的長度必須大于零D.空用就是空白申7.若目標(biāo)用的長度為n,模式用的長度為n/3,則執(zhí)行模式匹配算法時，在最壞情況下的時間復(fù)雜度是（）A. O ( 3)B. O (n)C. O (n2)D. O (n3)8.一個非空廣義表的表頭（A.不可能是子表C.尺能考原Jc

39、08 0 6B.只能是子表D0可8以篙表或原子9.假率消崎* 組表表示稀疏矩陣，翎1秒勵09A.L0 I 20l 30 制 5305稀毓娜酶是(05 0 0 000 0 0B. 5D. 070500000303400 0000 0040 00 010 .在一棵度為3的樹中，度為3的結(jié)點個數(shù)為2,度為2的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為（）.A. 4B. 5C. 6D. 711 .在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（）A.eB.2eC.n2eD.n22e12 .假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除與某個頂點vi相關(guān)的所有弧的時間復(fù)雜度是（）A.O（n）B

40、.O（e）C.O（n+e）D.O（n*e）13 .用某種排序方法對關(guān)鍵字序列（25,84,21,47,15,27,68,35,20）進(jìn)行排序時，序列的變化情況如下：20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84則所采用的排序方法是（）A.選擇排序B.希爾排序C.歸并排序D.快速排序14 .適于對動態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（）A.有序表B.分塊有序表C.三叉排序樹D.線性鏈表15 .不定長文件是指（）A.文件的長度不固定B.記錄的長度不固定C.字段的長度不固定D.關(guān)鍵字項的長度

41、不固定第二部分非選擇題（共70分）、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分,共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。16 .數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的無關(guān)，是獨立于計算機的17 .在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head=。18 .棧頂?shù)奈恢檬请S著操作而變化的。19 .在用S="structure”中，以t為首字符的子用有個。20 .假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B0存儲矩陣中第1個元素a1,1，則B31中存

42、放的元素是。21 .已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有個葉子結(jié)點。22.已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相應(yīng)的廣度優(yōu)先遍歷序列為。23 .在單鏈表上難以實現(xiàn)的排序方法有和24 .在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時所需進(jìn)行的關(guān)鍵字比較次數(shù)為。25 .多重表文件和倒排文件都?xì)w屬于文件。三、解答題(本大題共4小題，每小題5分，共20分)26 .畫出下列廣義表的共享結(jié)構(gòu)圖形表示P=(z),(x,y),(x,y),x),(z)27 .請畫出與下列二叉樹對應(yīng)的森林。01001100100001128 .已知團(tuán)份無向圖的頂點集為a,b,c,d

43、,e，其鄰接矩陣如下所示a10110b(1)畫出該圖的圖形；c(2)根據(jù)鄰接矩陣從頂點a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷,d寫出相應(yīng)的遍歷序列。e29.已知一個散列表如下圖所示：35203348590123456789101112其散列函數(shù)為h(key尸key%13,處理沖突的方法為雙重散列法，探查序列為:hi=(h(key)+i*h1(key)%mi=0,1，m1其中h1(key)=key%11+1回答下列問題：(1)對表中關(guān)鍵字35,20,33和48進(jìn)行查找時，所需進(jìn)行的比較次數(shù)各為多少？(2)該散列表在等概率查找時查找成功的平均查找長度為多少？四、算法閱讀題(本大題共4小題，褥小題5分

44、，共20分)30.下列算法的功能是比較兩個鏈即白諛小S2其返回值為：comstr(si,s2)=1當(dāng)s1s2請在空白處填入適當(dāng)?shù)膬?nèi)容。intcomstr(LinkStrings1,LinkStrings2)/s1和s2為兩個鏈用的頭指針while(s1&&s2)if(s1>date<s2>date)return1；if(s1>date>s2>date)return1；if()return1；if()return1；31.閱讀下面的算法LinkListmynote(LinkListL)/L是不帶頭結(jié)點的單鏈表的頭指針if(L&&

45、L->next)q=L;L=L>next;p=L;51: while(p>next)p=p>next；52: p>next=q；q>next=NULL;returnL；請回答下列問題：(1)說明語句S1的功能；(2)說明語句組S2的功能；(3)設(shè)鏈表表示的線性表為(a1,a2,ar),寫出算法執(zhí)行后的返回值所表示的線性表。32.假設(shè)兩個隊列共享一個循環(huán)向量空間(參見右下圖)，其類型Queue2定義如下：typedefstructDateTypedataMaxSize；intfront2,rear2；Queue2；對于i=0或1,fronti和reari分別為

46、第i個隊列的頭指針和尾指針。請對以下算法填空，實現(xiàn)第i個隊列的入隊操作intEnQueue(Queue2*Q,inti,DateTypex)若第i個隊列不滿，則元素x入隊列，并返回1；否則返回0if(i<0|i>1)return0；if(Q>reari=Q>frontreturn0；Q>data=x；Q>reari=;returnl；33.已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法。typedefstructnodeDateTypedataStructnode*next；ListNode;typedefListNode*LinkList；LinkListL

47、eafhead=NULL；VoidInorder(BinTreeT)LinkLists；If(T)Inorder(T>lchild);If(!T>lchild)&&(!T>rchild)s=(ListNode*)malloc(sizeof(ListNode);s>data=T>data；s>next=Leafhead;Leafhead=s；Inorder(T>rchild);對于如下所示的二叉樹.(1)畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)；(2)說明該算法的功能。五、算法設(shè)計題(本題共10分)34.閱讀下列函數(shù)arran

48、ge(inta口,int1,inth,intx)/1和h分別為數(shù)據(jù)區(qū)的下界和上界inti,j,t;i=1；j=h；while(i<j)while(i<j&&aj>=x)j-；while(i<j&&aj>=x)i+；if(i<j)t=aj；aj=ai；ai=t；if(ai<x)returni；elsereturni-1;(1)寫出該函數(shù)的功能；(2)寫一個調(diào)用上述函數(shù)實現(xiàn)下列功能的算法：對一整型數(shù)組bn中的元素進(jìn)行重新排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若有零值，則置于兩者之間，并返回

49、數(shù)組中零元素的個數(shù)。數(shù)據(jù)結(jié)構(gòu)試題參考答案、一、1.D2單項選擇題(本大題共15小題，每小題2分，共30分).B3.C4.B5.D6.A7.C8,D9,A10.C11.D12.C13.D14.C15.B1ASL4小題，每小題5分，共20分）3 2 112955（2 ）平均查找長度 四、算法閱讀題（本大題共 30. S1=S1>nextZs2=s2 >next28.該圖的圖形為:深度優(yōu)先遍歷序列為: 廣度優(yōu)先遍歷序列為:29.（1 ）對關(guān)鍵字35、20、33和48進(jìn)行查找的比較次數(shù)為3、2、1、s2域 s2!=NULL 或 s2&&!s1)s1域 s1!=NULL 或

50、s1&&!s2) return 0、填空題（本大題共10小題，每小題16.存儲（或存儲結(jié)構(gòu)）18.進(jìn)棧和退棧2分，共20分)17.p) > next > next19. 12圖1圖2abdceabedc20. a4,821, 38423.快速排序、堆排序、希爾排序24. 225.多關(guān)鍵字三、解答題（本大題共4小題，每小題5分，共20分）22. abefcdg26.31 .(1)查詢鏈表的尾結(jié)點(2)將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點(3)返回的線性表為(a2,a3,an,ai)32 .(i+1)%2(或1i)Q>reari(Q>reari+)%

51、Maxsize33.(1)Leafhead(2)中序遍歷二叉樹，按遍歷序列中葉子結(jié)點數(shù)據(jù)域的值構(gòu)建一個以Leafhead為頭指針的逆序單鏈表(或按二叉樹中葉子結(jié)點數(shù)據(jù)自右至左鏈接成一個鏈表)。五、算法設(shè)計題(本題共10分)34.(1)該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a口中的元素并返回分界值i,使所有<x的元素均落在a1.i上，使所有方x的元素均落在ai+1.h上。(2)intf(intb口,intn)或intf(intb口,intn)intp,q；intp,q；p=arrange(b,0,n-1,0)；p=arrange(b,0,n-1,1)；q=arrange(b,p+1,n-1,1)；q

52、=arrange(b,0,p,0)；returnqp；returnpq;吉首大學(xué)試題庫課程測試試題(卷)以下為教師填寫I、命題院(部)：數(shù)學(xué)與計算機科學(xué)學(xué)除II、課程名稱：數(shù)據(jù)結(jié)構(gòu)III、測試學(xué)期：20-20學(xué)年度第學(xué)期IV、測試對象：學(xué)院專業(yè)級班V 、問卷頁數(shù)(A4):頁V I、答卷頁數(shù)(A4):頁V II、考試方式：閉卷(開卷、閉卷或課程小論文，請?zhí)顚懬宄?VIII、問卷內(nèi)容：(請老師在出題時安排緊湊，填空題象征性的留出一點空格,學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號)一、選擇題(20分)1 .組成數(shù)據(jù)的基本單位是()。(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D

53、)數(shù)據(jù)變量2 .設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D,R),其中D=1,2,3,4,R=r,r=<1,2>,<2,3>,<3,4>,<4,1>,則數(shù)據(jù)結(jié)構(gòu)人是()。(A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)圖型結(jié)構(gòu)(D)集合3 .數(shù)組的邏輯結(jié)構(gòu)不同于下列()的邏輯結(jié)構(gòu)。(A)線性表(B)棧(C)隊列(D)樹4 .二叉樹中第i(i>屋)±的結(jié)點數(shù)最多有()個。(A)2i(B)2i(C)2i-1(D)2i-15 .設(shè)指針變量p指向單鏈表結(jié)點A,則刪除結(jié)點A的后繼結(jié)點B需要的操作為()。(A)p->next=p->next->next(B)p=

54、p->next(C)p=p->next->next(D)p->next=p6 .設(shè)棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S,一個元素出棧后即進(jìn)入隊列Q,若6個元素出列的順序為E2、E4、E3、E6、E5和E1,則棧S的容量至少應(yīng)該是()。(A)6(B)4(C)3(D)27 .將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為()。(A)100(B)40(C)55(D)80(D) 1)種不同的形態(tài)。(C) 6(D) 7)的空間復(fù)雜度最大。(C)堆排序(D)希爾排序8 .設(shè)結(jié)點A有3個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙親結(jié)點，則結(jié)點B的度數(shù)數(shù)為()。(A)3