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

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

2、2.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針 p指向的結(jié) 點(diǎn)，則執(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.對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（ B ）A.經(jīng)常需要隨機(jī)地存取元素B. 經(jīng)常需要進(jìn)行插入和刪除操C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變4. 4. 一個(gè)棧的輸入序列為1 2 3 ,則下列序列中不可能是棧的輸出序列的 是（C ）A. 2 3 1B.

3、 3 2 1C. 3 1 2D. 1 2 35. 5. AOV3是一種（D ）。A .有向圖 B .無(wú)向圖 C .無(wú)向無(wú)環(huán)圖 D .有向無(wú)環(huán)圖6. 6.采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度( B )。A.低于鏈接法處理沖突B.高于鏈接法處理沖突C .與鏈接法處理沖突相同D .高于二分查找7. 7.若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為(D )參數(shù)： A.值B .函數(shù) C .指針 D .引用8. 8.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的(A )。A.行號(hào)B .列號(hào) C .元素值 D .非零元素個(gè)數(shù)9. 9.快速排序在最壞情況下的時(shí)間復(fù)雜度為(

4、 C )0A. O(log 2n)B . O(nlog2n) C . 0(n) D . 0(n2)10. 10.從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為(D)。一一 一一 _2A. O(n) B. O(1) C. O(log2n)D. O(n )2、 二、 運(yùn)算題(每題6分，共24分)1. 1.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的 ，當(dāng)結(jié)點(diǎn)之間存在M對(duì)N (M N)的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為 2. 2.隊(duì)列的插入操作是在隊(duì)列的 進(jìn)行，刪除操作是在隊(duì)列的進(jìn)行。3. 3.當(dāng)用長(zhǎng)度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=N表示?？眨瑒t表示棧滿的條件是4. 4.對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表，在表

5、頭插入元素的時(shí)間復(fù)雜度為,在表尾插入元素的時(shí)間復(fù)雜度為 5. 5.設(shè)W為一個(gè)二維數(shù)組，其每個(gè)數(shù)據(jù)元素占用4個(gè)字節(jié)，行下標(biāo)i從0到7 ,列下標(biāo)j從0到3 ,則二維數(shù)組 W勺數(shù)據(jù)元素共占用 個(gè)字節(jié)。年第6行的元素和第4列的元素共占用 個(gè)字節(jié)。若按行順序存放二維數(shù)組 W其起始地址為100,則二維數(shù)組元素 W6, 3的起始地 址為。6. 6.廣義表A=(a,(a,b),(a,b),c),則它的深度為,它的長(zhǎng)度為7. 7.二叉樹(shù)是指度為2的樹(shù)。一棵結(jié)點(diǎn)數(shù)為N的二叉樹(shù)，其所有結(jié)點(diǎn)的度的總和是 8. 8. 對(duì)一棵二叉搜索樹(shù)進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè) 對(duì)一棵由算術(shù)表達(dá)式組成的二叉語(yǔ)法樹(shù)進(jìn)行后序遍歷得

6、到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的9. 9.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為個(gè),其中 個(gè)用于指向孩子，個(gè)指針是空閑的教育資料1.10. .若對(duì)一棵完全二叉樹(shù)從0開(kāi)始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存 儲(chǔ)到一維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A0中。其余類推，則A i 元素的左孩子元素為 ，右孩子元素為 2雙親元素為11. 11.在線性表的散列存儲(chǔ)中，處理沖突的常用方法有 口兇種。12. 12.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)， 宜采用 排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用排序。3、 三、 運(yùn)算題(每題6分，共24分)1

7、. 1. 已知一個(gè)6x5稀疏矩陣如下所示，0000100000|0-10000000-25000000700試：(1) (1) 寫(xiě)出它的三元組線性表；(2) (2)給出三元組線性表的順序存儲(chǔ)表示。2. 2.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80，試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹(shù)。3. 3. 對(duì)于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的 邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫(xiě)出：(1)從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹(shù)；(2)從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹(shù)；教育資料圖64. 4.已知一個(gè)

8、圖的頂點(diǎn)集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>,<6,2> ,<6,5>若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序 號(hào)從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給 出得到的拓樸排序的序列。4、 四、 閱讀算法(每題7分，共14分)1.1. int Prime(int n)int i=1;int x=(i

9、nt) sqrt(n);while (+i<=x)if (n%i=0) break;if (i>x) return 1;else return 0;1. (1)指出該算法的功能；1.(a)(b)(c)(d)(e)(f J圖82. (1)答案： 判斷n是否是素?cái)?shù)(或質(zhì)數(shù))(2)該算法的時(shí)間復(fù)雜度是多少？答案：O( Jn)3. 2.寫(xiě)出下述算法的功能:void AJ(adjlist GL, int i, int n)Queue Q;InitQueue(Q);cout<<i<<''visitedi=true;QInsert(Q,i);while(!

10、QueueEmpty(Q) int k=QDelete(Q);edgenode* p=GLk; while(p!=NULL)int j=p->adjvex;if(!visitedj)cout<<j<<''visitedj=true;QInsert(Q,j);p=p->next;4. 2.功能為：從初始點(diǎn) Vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。5、 五、算法填空(共8分)如下為二分查找的非遞歸算法，試將其填寫(xiě)完整。Int Binsch(ElemType A ,int n,KeyType K) int low=0;int high=n-1;

11、while (low<=high) int mid= (low+high)/2 if (K=Amid.key) return mid; /查找成功，返回元素的下標(biāo)else if (K<mid.key)high=mid-1 ;/在左子表上繼續(xù)查找else low=mid+1 /在右子表上繼續(xù)查找return -1;/ 查找失敗，返回-16、 六、編寫(xiě)算法(共8分)HL是單鏈表的頭指針，試寫(xiě)出刪除頭結(jié)點(diǎn)的算法ElemType DeleFront(LNode * & HL)ElemType DeleFront(LNode * & HL)if (HL=NULL)cerr&l

12、t;<"空表"<<endl;exit(1);LNode* p=HL;HL=HL->next;ElemType temp=p->data;delete p;return temp;參考答案1.B 2.A 3.B 4.C單選題(每題2分，共20分)5.D 6.B 7.D 8.A 9.D 10.C2、 二、填空題（每空1分，共26分）1. 1.聯(lián)系 圖（或圖結(jié)構(gòu)）2. 2.尾首3. 3.top=04. 4.O (1)O (n)5. 5.128 44 1086. 6.3 365515132-145-2515637圖77. 7.有序 n-18. 8.有序

13、序列后綴表達(dá)式(或逆波蘭式)9. 9.2n n-1 n+110. 10.2i+12i+2(i-1)/211. 11.開(kāi)放定址法鏈接法12. 12.快速歸并3、 三、運(yùn)算題(每題6分，共24分)1. 1.(1)(1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3分)(b)(c)圖8（2） 三元組線性表的順序存儲(chǔ)表示如圖7示。2. 2.如圖8所示。3. 3.DFSBFS4. 4.拓樸排序?yàn)椋? 3 6 5 7 2 14、 四、閱讀算法（每題7分，共14分）4. 1.(1)判斷n是否是素?cái)?shù)(或質(zhì)數(shù))(2) 0(萬(wàn))5. 2.功能為：從初始點(diǎn) w出發(fā)廣度優(yōu)先搜索由鄰

14、接表GL所表示的圖。5、 五、算法填空(8分)(low+high)/2 high=mid-1 low=mid+16、 六、編寫(xiě)算法(8分)ElemType DeleFront(LNode * & HL) if (HL=NULL)cerr<<"空表"<<endl;exit(1);LNode* p=HL;HL=HL->next;ElemType temp=p->data;delete p; return temp;吉首大學(xué)試題庫(kù)課程測(cè)試試題（ 卷） 以下為教師填寫(xiě)I、命題院（部）：數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院II、課程名稱：數(shù)據(jù)結(jié)構(gòu)III、測(cè)

15、試學(xué)期：20 -20學(xué)年度第 學(xué)期IV、測(cè)試對(duì)象： 學(xué)院 專業(yè) 級(jí) 班V 、問(wèn)卷頁(yè)數(shù)（A4） : 頁(yè)V I、答卷頁(yè)數(shù)（A4）: 頁(yè)V II、考試方式：閉卷（開(kāi)卷、閉卷或課程小論文，請(qǐng)?zhí)顚?xiě)清楚）VIII、問(wèn)卷內(nèi)容：（請(qǐng)老師在出題時(shí)安排緊湊，填空題象征性的留出一點(diǎn)空格, 學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫(xiě)清楚大題、小題的題號(hào)）一、 單選題（每題2分，共20分）1. 1.棧和隊(duì)列的共同特點(diǎn)是（）。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒(méi)有共同點(diǎn)2. 2.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)（）.A. 僅修改頭指針B. 頭、尾指針都要修改C. 僅修改尾指針 D

16、. 頭、尾指針可能都要修改3. 3.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？（）A. 隊(duì)列B.棧 C. 線性表 D.二叉樹(shù)4. 4.設(shè)有一個(gè)二維數(shù)組外巾n,假設(shè)A00存放位置在644io）,A22 存放位置在676（io）,每個(gè)元素占一個(gè)空間，問(wèn)A33（io）存放在什么位置? 腳注（io）表示用10進(jìn)制表示。A5. 5.A.C.6. 6.A7. 7.中,樹(shù)最適合用來(lái)表示（ 有序數(shù)據(jù)元素.678 C）。B.元素之間具有分支層次關(guān)系的數(shù)據(jù)二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為（）.2k-1B.2K+1C.2K-1.692 D . 696無(wú)序數(shù)據(jù)元素D.元素之間無(wú)聯(lián)系的數(shù)據(jù)D. 2 k-1若有18個(gè)元素的有序表存放

17、在一維數(shù)組 A19中，第一個(gè)元素放A1現(xiàn)進(jìn)行二分查找，則查找 A 3的比較序列的下標(biāo)依次為（）A.1 ,2,3B.9 , 5, 2, 3C. 9 , 5, 3D. 9 , 4, 2, 38. 8.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為A. O （1）B. O （n） C. O （1og2n）D. O （n2）9. 9.對(duì)于線性表（7, 34, 55, 25, 64, 46, 20, 10）進(jìn)行散列存儲(chǔ)時(shí)， 若選用H （K） =K %9作為散列函數(shù)，則散列地址為1的元素有（）個(gè),A . 1 B.2 C . 3 D . 410. 10.設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（）條邊才

18、能確保是一個(gè)連通圖。A.5B.6C.7D.82、 二、 填空題（每空1分，共26分）1. 1.通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量： ? 和。2. 2. 一個(gè)算法的時(shí)間復(fù)雜度為（n3+n2|og2n+14n）/ n2,其數(shù)量級(jí)表示為3. 3.假定一棵樹(shù)的廣義表表示為A (C, D (E, F, G), H (I , J),則樹(shù)中所含的結(jié)點(diǎn)數(shù)為 個(gè)，樹(shù)的深度為,樹(shù)的度為4. 4.后綴算式9 2 3+- 102 / -的值為。中綴算式(3+4X0 -2Y/3對(duì)應(yīng)的后綴算式為5. 5.若用鏈表存儲(chǔ)一棵二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹(shù)共有 個(gè)指

19、針域，其中有 個(gè)指針域是存放了地址，有 個(gè)指針是空指針。6. 6.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有個(gè)和個(gè)。7. 7.AOVR是一種的圖。8. 8.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有 條邊。9. 9.假定一個(gè)線性表為(12,23,74,55,63,40),若按Key %4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為 口10. 10.向一棵BJM插入元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的分裂，則新樹(shù) 比原樹(shù)的高度。11. 11.在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)

20、雜度為 ,整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為 。12. 12.在快速排序、堆排序、歸并排序中， 排序是穩(wěn)定的。3、 三、 運(yùn)算題(每題6分，共24分)0 1 data next1. 1. 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為 A0.next ,試 寫(xiě)出該線性表。605078903440357204123 45 672. 2.請(qǐng)畫(huà)出圖10的鄰接矩陣和鄰接表。3. 3.已知一個(gè)圖的頂點(diǎn)集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

21、)18,(6,7)25;用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各 條邊。4. 4.畫(huà)出向小根堆中加入數(shù)據(jù)4, 2, 5, 8,3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。4、 四、閱讀算法(每題7分，共14分)1. 1. LinkList mynote(LinkList L)/L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L->next)q=L; L=L >next; p=L;S1 :while(p >next) p=p >next；S2 :p >next=q； q >next=NULL return L；請(qǐng)回答下列問(wèn)題：(1)說(shuō)明語(yǔ)

22、句S1的功能；(2)說(shuō)明語(yǔ)句組S2的功能；(3)設(shè)鏈表表示的線性表為(a1,a2,an),寫(xiě)出算法執(zhí)行后的返回值 所表示的線性表。2. 2. void ABC(BTNode * BT) if BT ABC (BT->left);ABC (BT->right); cout<<BT->data<<'' 該算法的功能是：5、 五、算法填空(共8分)二叉搜索樹(shù)的查找一一遞歸算法：bool Find(BTreeNode* BST,ElemType& item) if (BST=NULL) return false; /查找失敗else i

23、f (item=BST->data)item=BST->data;/查找成功return ; else if(item<BST->data)return Find(,item); else return Find(,item); /if6、 六、編寫(xiě)算法(共8分)統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù) int CountX(LNode* HL,ElemType x)參考答案一、 一、單選題1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C填空題（每題2分，共20分）9.D 10.A（每空1分，共26分）1.2.3.4.5.6.7.8.9.1.2.3.

24、4.5.6.7.8.9.正確性 易讀性 強(qiáng)壯性 高效率O（n）9-1 2n e3 33 4 X * + 2 Y * 3 / - n-1n+12e10.10.11.11.12.12.有向無(wú)回路n(n-1)/2n(n-1)(12, 40)()增加1O(log 2n)歸并O(nlog2n)運(yùn)算題（每題1.1.線性表為:(780150, 402.2.鄰接矩陣:(74)(23,55, 63)6分，共24分)60, 34, 90)011鄰接表如圖11所示:圖113. 3.用克魯斯卡爾算法得到的最小生成樹(shù)為:(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204.

25、 4. 見(jiàn)圖12圖124、 四、閱讀算法(每題7分，共14分)1. 1.(1)查詢鏈表的尾結(jié)點(diǎn)(2)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)(3)返回的線性表為(a2,a 3,，a n,a 1)2. 2.遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)。5、 五、算法填空(每空2分，共8分)true BST->left BST->right6、 六、編寫(xiě)算法(8分)int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i為計(jì)數(shù)器while(p!=NULL) if (P->data=x) i+;p=p->next;/while,出

26、循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)return i;/CountX吉首大學(xué)試題庫(kù)課程測(cè)試試題(卷)以下為教師填寫(xiě)I、命題院（部）：數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院II、課程名稱：數(shù)據(jù)結(jié)構(gòu)III、測(cè)試學(xué)期：20 20學(xué)年度第學(xué)期IV、測(cè)試對(duì)象： 學(xué)院 專業(yè) 級(jí) 班V、問(wèn)卷頁(yè)數(shù)（A4） : 頁(yè)VI、答卷頁(yè)數(shù)（A4）: 頁(yè)VII、考試方式：閉卷（開(kāi)卷、閉卷或課程小論文，請(qǐng)?zhí)顚?xiě)清楚）VIII、問(wèn)卷內(nèi)容：（請(qǐng)老師在出題時(shí)安排緊湊，填空題象征性的留出一點(diǎn)空格,學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫(xiě)清楚大題、小題的題號(hào)）1、 一、 單選題（每小題2分，共8分）1、1、在一個(gè)長(zhǎng)度為n的順序線性表中順序查找值為 x的元素時(shí)

27、，查找成功時(shí)的 平均查找長(zhǎng)度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率 都相等）為（）。A n B n/2 C （n+1）/2 D （n-1）/22、2、在一個(gè)單鏈表中，若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間 插入一個(gè)s所指的結(jié)點(diǎn)，則執(zhí)行（）。A s Tink=p flink; p Tink=s; B p Tink=s; s Tink=q;C p Tink=s flink; s Tink=p; D qTink=s; s flink =p;3、 3、棧的插入和刪除操作在（）進(jìn)行。A棧頂 B 棧底 C任意位置D指定位置4、 4、由權(quán)值分別為11, 8, 6, 2, 5的葉子結(jié)點(diǎn)

28、生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（）A 24 B 71 C 48 D 532、 二、 填空題（每空1分，共32分）1、1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 ? 、和四種。2、2、一種抽象數(shù)據(jù)類型包括 網(wǎng)個(gè)部分。3、3、在下面的數(shù)組a中鏈接存儲(chǔ)著一個(gè)線性表，表頭指針為 ao.next , 則該線性表為6056423874254376201a 012345678data next4、4、在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，判 斷鏈表為空的條件分別為?口5、5、用具有n個(gè)元素的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指 向隊(duì)首元素的,該循環(huán)隊(duì)列白最大長(zhǎng)度為 6、6、當(dāng)堆棧采用順序存儲(chǔ)

29、結(jié)構(gòu)時(shí)，棧頂元素的值可用表示；當(dāng)堆棧采用鏈接存儲(chǔ)結(jié)構(gòu)時(shí),棧頂元素的值可用 表示。7、7、一棵高度為 5的二叉樹(shù)中最少含有 個(gè)結(jié)點(diǎn)，最多含有個(gè)結(jié)點(diǎn)；一棵高度為5的理想平衡樹(shù)中，最少含有 個(gè)結(jié)點(diǎn)，最多含有個(gè)結(jié)點(diǎn)。8、8、在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱為 2通常它包含三個(gè)域：_是;二是;三是9、9、在一個(gè)索引文件的索引表中，每個(gè)索引項(xiàng)包含對(duì)應(yīng)記錄的 和兩項(xiàng)數(shù)據(jù)。10、 10、假定一棵樹(shù)的廣義表表示為 A (B (C, D (E, F, G), H (I ,J),則樹(shù)中所含的結(jié)點(diǎn)數(shù)為 個(gè)，樹(shù)的深度為 ，樹(shù)的度為,結(jié)點(diǎn) H的雙親結(jié)點(diǎn)為,孩子結(jié)點(diǎn)為11、 11、在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)

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

31、畫(huà)出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng) 度。3、3、已知一棵二叉樹(shù)的前序遍歷的結(jié)果序列是 ABECKFGH|J中序遍歷的結(jié)果是EBCDAFHIGJ試寫(xiě)出這棵二叉樹(shù)的后序遍歷結(jié)果4、4、已知一個(gè)圖的頂點(diǎn)集 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)它用鄰接矩陣表示和鄰接表表示時(shí)，分別寫(xiě)出從頂點(diǎn)Vo出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。

32、假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號(hào)從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí)鄰接表表示時(shí)4、 四、閱讀算法，回答問(wèn)題(每小題8分，共16分)1、假定從鍵盤(pán)上輸入一批整數(shù)，依次為：78 63 45 30 91 34- 1,請(qǐng)寫(xiě)出輸出結(jié)果。# include < iostream.h># include < stdlib.h >consst int stackmaxsize = 30;typedef int elemtype;struct stack elemtype stack stackmaxsize;int top;# include “sta

33、ck.h "Void main ()stack a;initstack(a);int x;cin >>x;while (x! = -1) push (a, x );cin >>x;while (!stackempty (a)cout <<pop (a) << cout <<end1;該算法的輸出結(jié)果為:2、閱讀以下二叉樹(shù)操作算法，指出該算法的功能Template <calss type > void BinTree <Type> unknown (BinTreeNode<Type>*t)

34、BinTreeNode< Type> *p =t, *temp; if (p!=NULL) temp = p Teftchild;p leftchild = pfrightchild;pfrightchild = temp;unknown(p leftchild);undnown(p frightchild);該算法的功能是：五、算法填空，在畫(huà)有橫線的地方填寫(xiě)合適的內(nèi)容（10分）對(duì)順序存儲(chǔ)的有序表進(jìn)行二分查找的遞歸算法。int Binsch( ElemType A ,int low ,int high,KeyType K )if (low <= high)int mid =

35、1if ( K= = A mid .key ) return mid;else if ( K < Amid.key) return 2elsereturn 3 elsereturn 4六、 六、編寫(xiě)算法（10分）編寫(xiě)算法，將一個(gè)結(jié)點(diǎn)類型為L(zhǎng)node的單鏈表按逆序鏈接，即若原單鏈表中 存儲(chǔ)元素的次序?yàn)閍i, an-i, an,則逆序鏈接后變?yōu)?an, an-i, a1。Void contrary （Lnode * & H L）數(shù)據(jù)結(jié)構(gòu)試題（答案）一、單選題（每小題 2分，共8分）題號(hào)1234答案CDAB二、填空題（每空1分，共32分）1:集合、線性、樹(shù)、圖；2:數(shù)據(jù)描述、操作聲名；

36、3:（38, 56, 25, 60, 42, 74）;4： HL fnext =NULL ; HL=HLfnext ;5: 前一個(gè)位置；n-1 ;6: S.stack S.top; HS data;7: 5 318: 邊結(jié)點(diǎn)、鄰接點(diǎn)域、權(quán)域、鏈域；9: 索引值域、開(kāi)始位置域；10: 10、3、3、B、I 和 J;11: O （log 2n）、O（nlog 2n）;12: m、 m - 1三、運(yùn)算題（每小題 6分，共24分）1、劃分次序劃分結(jié)果A次38 24 40 46 56 80 95 79第二次24 38 40 46 56 80 95 79第三次24 38 40 46 56 80 95 79

37、第四次24 38 40 46 56 80 95 79第五次24 38 40 46 56 79 80 95第六次24 38 40 46 56 79 80 952、012345678910111278150357452031233612查找成功的平均查找長(zhǎng)度：ASLsuc（=14/10= 1.43、此二叉樹(shù)的后序遍歷結(jié)果是：EDCBIHJGFA4、圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí)0, 1, 2, 8, 3, 4, 5, 6, 7, 90, 1, 4, 2, 7, 3, 8, 6, 5, 9鄰接表表示時(shí)0, 4, 3, 8, 9, 5, 6, 7, 1, 20, 4, 1 , 3, 7, 2

38、, 8, 6, 9, 5四、閱讀算法，回答問(wèn)題（每小題8分，共16分）1、1、 該算法的輸入結(jié)果是：34 91 30 45 63 782、2、該算法的功能是：交換二叉樹(shù)的左右子樹(shù)的遞歸算法。五、算法填空，在畫(huà)有橫線的地方填寫(xiě)合適的內(nèi)容(10分)1、1 是：(low + high ) /2;2 是：Binsch(A,low,mid - 1,K);3 是：Binsch(A,mid+1,high,K);4 是：-1 ;六、編寫(xiě)算法(10分)根據(jù)編程情況，酌情給分。Lnode *P=HL;HL=NULL;While (p!=null)Lnode*q=p;P=p - next;q f next=HL;H

39、L=q;吉首大學(xué)試題庫(kù)課程測(cè)試試題（卷） 以下為教師填寫(xiě)I、命題院（部）：數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)除II、課程名稱：數(shù)據(jù)結(jié)構(gòu)III、測(cè)試學(xué)期：20 20學(xué)年度第學(xué)期IV、測(cè)試對(duì)象： 學(xué)院 專業(yè) 級(jí)班V 、問(wèn)卷頁(yè)數(shù)（A4） : 頁(yè)V I、答卷頁(yè)數(shù)（A4）: 頁(yè)V II、考試方式：閉卷（開(kāi)卷、閉卷或課程小論文，請(qǐng)?zhí)顚?xiě)清楚）VIII、問(wèn)卷內(nèi)容：（請(qǐng)老師在出題時(shí)安排緊湊，填空題象征性的留出一點(diǎn)空格,學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫(xiě)清楚大題、小題的題號(hào)）第一部分選擇題（30分）一、項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的 四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的， 請(qǐng)將正確選

40、項(xiàng)前的字母填在題后的括號(hào)內(nèi)。1 .算法指的是（）.解決問(wèn)題的計(jì)算方法.解決問(wèn)題的有限運(yùn)算序列A .計(jì)算機(jī)程序BC .排序算法D2 .線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）A .必須是不連續(xù)的B .連續(xù)與否均可C .必須是連續(xù)的D .和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)3 .將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（）A . O （1） B . O （n）C . O （n）D . O （m+r）4 .由兩個(gè)棧共享一個(gè)向量空間的好處是：（）A .減少存取時(shí)間，降低下溢發(fā)生的機(jī)率B .節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率C .減少存取時(shí)間，降低上溢發(fā)生的機(jī)率D .節(jié)省存儲(chǔ)空間，降低下溢發(fā)生

41、的機(jī)率5 .設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針A . front=front+1BC . front=（front-1）%m D6 .如下陳述中正確的是（）A .用是一種特殊的線性表BC .用中元素只能是字母 D7 .若目標(biāo)用的長(zhǎng)度為n,模式用的長(zhǎng)度為壞情況下的時(shí)間復(fù)雜度是（）A . O （3） B . O （n）C .front 值為（）.front=（front+1）%（m-1）.front=（front+1）%m.用的長(zhǎng)度必須大于零.空用就是空白申n/3,則執(zhí)行模式匹配算法時(shí)，在最O （n2）D . O （n3）

42、教育資料8. 一個(gè)非空廣義表的表頭（）A .不可能是子表B .只能是子表C9.A.白柒D元組表表示稀疏矩陣須附稀毓婚陶是生 0 0 0.00 0 0500400 00700000 0053004 0 0.030 0B.D.10 .在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1,則度 為0的結(jié)點(diǎn)個(gè)數(shù)為（）A . 4 B .5 C . 6 D .711 .在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（）A . e B . 2e C . n2 e D . n2 2e12 .假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是（）A

43、 . O(n) B . O(e) C.O(n+e) D . O(n*e)13.用某種排序方法對(duì)關(guān)鍵字序列（行排序時(shí)，序列的變化情況如下:25, 84, 21, 47, 15, 27, 68, 35, 20)進(jìn)20, 15, 21, 25,15, 20, 21, 25,15, 20, 21, 25,47, 27, 68, 35, 8435, 27, 47, 68, 8427, 35, 47, 68, 84則所采用的排序方法是（）A .選擇排序B .希爾排序C .歸并排序D .快速排序14 .適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（）A.有序表 B .分塊有序表 C .三叉排序樹(shù) D .線性鏈

44、表15 .不定長(zhǎng)文件是指（）.記錄的長(zhǎng)度不固定關(guān)鍵字項(xiàng)的長(zhǎng)度不固定A.文件的長(zhǎng)度不固定BC.字段的長(zhǎng)度不固定D第二部分非選擇題（共70分）二、填空題（本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分， 共20分）不寫(xiě)解答過(guò)程，將正確的答案寫(xiě)在每小題的空格內(nèi)。錯(cuò)填或不填 均無(wú)分。16 .數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。17 .在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn) 的指針 head可用p表示為 head=。18 .棧頂?shù)奈恢檬请S著 操作而變化的。19 .在用S= "structure ”中，以t為首字符的子用

45、有 個(gè)。20 .假設(shè)一個(gè)9階的上三角矩陣A按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，其中B0存儲(chǔ)矩陣中第1個(gè)元素au，則B31中存放的元素是 。21 .已知一棵完全二叉樹(shù)中共有768結(jié)點(diǎn)，則該樹(shù)中共有 個(gè)葉子結(jié)點(diǎn)22.已知一個(gè)圖的廣度優(yōu)先生成樹(shù)如右圖所示，則與此相 應(yīng)的廣度優(yōu)先遍歷序列為 。23 .在單鏈表上難以實(shí)現(xiàn)的排序方法有 和。24 .在有序表( 12, 24, 36, 48, 60, 72, 84)中二分查找關(guān)鍵字72時(shí)所需進(jìn) 行的關(guān)鍵字比較次數(shù)為。25 .多重表文件和倒排文件都?xì)w屬于 文件。三、解答題(本大題共4小題，每小題5分，共20分)26 .畫(huà)出下列廣義表的共享結(jié)構(gòu)圖形表示P=(z)

46、 ,(x,y) ) ,(x,y),x),(z)27 .請(qǐng)畫(huà)出與下列二叉樹(shù)對(duì)應(yīng)的森林。ba, b, c, d, e,cd其鄰接矩陣如下所示(1) 畫(huà)出該圖的圖形；(2)根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷, 寫(xiě)出相應(yīng)的遍歷序列。29.已知一個(gè)散列表如下圖所示:35203348590 1 2 3 4 5 6 7 8 9 10 11 12其散列函數(shù)為h(key)=key%13,處理沖突的方法為雙重散列法，探查序列為:h i=(h(key)+ i*h1(key)%m i =0,1，,m- 1其中h1(key)=key%11+1回答下列問(wèn)題：(1)對(duì)表中關(guān)鍵字35, 20, 33和48

47、進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各 為多少？(2)該散列表在等概率查找時(shí)查找成功的平均查找長(zhǎng)度為多少？四、算法閱讀題(本大題共4小此14咂為分，共20分)30 .下列算法的功能是比較兩個(gè)鏈用0勺耳共返回值為：comstr(si,s 2)= 11 當(dāng) s1 >s2請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。int comstr(LinkString s1,LinkString s2)/si和s2為兩個(gè)鏈用的頭指針while(s1&&s2)if(s1 >date<s2 >date)return 1;if(s1 >date>s2 >date)return1 ;i

48、f()return- 1;if()return1 ；31 .閱讀下面的算法LinkList mynote(LinkList L)/L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L->next)q=L; L=L >next; p=L;S1 :while(p >next) p=p >next；S2 :p >next=q； q >next=NULLreturn L；請(qǐng)回答下列問(wèn)題：(1)說(shuō)明語(yǔ)句S1的功能；(2)說(shuō)明語(yǔ)句組S2的功能；(3)設(shè)鏈表表示的線性表為(ai,a2,an),寫(xiě)出算法執(zhí)行后的返回值所表示的線性表。32.假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量

49、空間(參見(jiàn)右 下圖)，其類型Queue2定義如下：typedef structDateType dataMaxSize ；int front2,rear2；Queue2 ；對(duì)于i=0或1, fronti 和reari分別為第i個(gè)隊(duì)列的頭指針和尾指針 請(qǐng)對(duì)以下算法填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。int EnQueue (Queue2*Q,int i,DateType x)/ 若第i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1；否則返回0if(i<0|i>1)return 0；if(Q >reari=Q >front return0 ；Q >data =x；Q >rea

50、ri= ;return1 ；33.已知二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，閱讀下面算法。typedef struct node DateType data ;Struct node * next ；ListNode ;typedef ListNode * LinkList;LinkList Leafhead=NULL ；Void Inorder (BinTree T)LinkList s；If(T)Inorder(T >lchild);If (!T >lchild)&&(!T >rchild)s=(ListNode*)malloc(sizeof(ListNode) s

51、 >data=T >data ；s >next=Leafhead ;Leafhead=sInorder(T>rchild);(1)畫(huà)出執(zhí)行上述算法后所建立的結(jié)構(gòu)；(2)說(shuō)明該算法的功能。五、算法設(shè)計(jì)題(本題共10分)34.閱讀下列函數(shù)arrange。int arrange(int a口,int 1,int h,int x)/1和h分別為數(shù)據(jù)區(qū)的下界和上界int i,j,t ;i=1； j=h ；while(i<j)while(i<j && aj>=x)j-;while(i<j && aj>=x)i+；if(i

52、<j) t=aj； aj=ai； ai=t ； if(ai<x) return i；else return i 1 ；(1)寫(xiě)出該函數(shù)的功能；(2)寫(xiě)一個(gè)調(diào)用上述函數(shù)實(shí)現(xiàn)下列功能的算法：對(duì)一整型數(shù)組 bn中的元素 進(jìn)行重新排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整 到數(shù)組的高下標(biāo)端，若有零值，則置于兩者之間，并返回?cái)?shù)組中零元素的 個(gè)數(shù)。數(shù)據(jù)結(jié)構(gòu)試題參考答案單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）1. D 2 . B.A 7 . C11.填空題（本大題共3 . C8 , D12. C10小題，每小題4 . B9 , A13. D2分，共20分）D10. C1

53、4. C 15. B16.存儲(chǔ)（或存儲(chǔ)結(jié)構(gòu)）17.p > next > next18.進(jìn)棧和退棧19. 1220. a”21.22.23.24.384abefcdg快速排序、堆排序、希爾排序2解答題（本大題共26.25.多關(guān)鍵字o27.28. 該圖的圖形為:深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc29. ( 1 )對(duì)關(guān)鍵字35、20、33和48進(jìn)行查找的比較次數(shù)為3、2、1、1;(2)平均查找長(zhǎng)度ASL 二號(hào)上K四、算法閱讀題(本大題共4小題，每小題5分，共20分)30. S1=S">next s2=s2 >next s2(或 s2!=NULL或 s2&&!s1)si(或 s1!=NULL或 s1&&!s2) return 031. (