數(shù)據(jù)結(jié)構(gòu)試題及答案修2

1、試卷一、單選題（每題2分，共20分）1 .對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（）方面的內(nèi)容。A.健壯性和可讀性B.并行性C.正確性D.時(shí)空復(fù)雜度2 .在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（）。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. 對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變4.

2、一個(gè)棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是（）A.231B.321C.312D.1235. AOV網(wǎng)是一種（）。A.有向圖B.無(wú)向圖C.無(wú)向無(wú)環(huán)圖D.有向無(wú)環(huán)圖7 .若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為（）參數(shù)。A.值B.函數(shù)C.指針D,引用8 .在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（）。A.行號(hào)B.列號(hào)C.元素值D.非零元素個(gè)數(shù)二、填空題（每空1分，共28分）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 .隊(duì)列的插入操作是在隊(duì)列的_尾進(jìn)行，刪除操作是在隊(duì)列的首進(jìn)行。3 .當(dāng)用長(zhǎng)度

3、為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=N表示棧空，則表示棧滿的條件是top=0。4 .對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為,在表尾插入元素的時(shí)間復(fù)雜度為。7. 二叉樹(shù)是指度為2的樹(shù)。一棵25點(diǎn)數(shù)為N的二叉樹(shù)，其所有結(jié)點(diǎn)的度的總和是。8. 對(duì)一棵二叉搜索樹(shù)進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)。對(duì)一棵由算術(shù)表達(dá)式組成的二叉語(yǔ)法樹(shù)進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的9. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為個(gè)，其中個(gè)用于指向孩子，個(gè)指針是空閑的。10. 若對(duì)一棵完全二叉樹(shù)從0開(kāi)始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)

4、為0的結(jié)點(diǎn)存儲(chǔ)到A0中。其余類推，則Ai元素的左孩子元素為，右孩子元素為,雙親元素為11. 在線性表的散列存儲(chǔ)中，處理沖突的常用方法有兩種。運(yùn)算題(每題6分，共24分)1.已知一個(gè)6父5稀疏矩陣如下所示，試:(1)寫(xiě)出它的三元組線性表;(2)給出三元組線性表的順序存儲(chǔ)表示。四、1.0-1-2002.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 ，試畫(huà)出從空樹(shù)起,逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹(shù)。3. 對(duì)于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫(xiě)出:從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹(shù);從頂

5、點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹(shù);4. 已知一個(gè)圖的頂點(diǎn)集 V和邊集E分別為:閱讀算法(每題7分，共14分)int Prime(int n)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)行排序，試給出得到的拓樸排序的序

6、列。inti=1;intx=(int)sqrt(n);while(+i<=x)if(n%i=0)break;if(i>x)return1;elsereturn0;指出該算法的功能;該算法的時(shí)間復(fù)雜度是多少?2.寫(xiě)出下述算法的功能:voidAJ(adjlistGL,inti,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-&g

7、t;adjvex;if(!visitedj)cout<<j<<''visitedj尸true;QInsert(Q,j);p=p->next;HL是單鏈表的頭指針，試寫(xiě)出刪除頭結(jié)點(diǎn)的算法。ElemTypeDeleFront(LNode*&HL)參考答案單選題（每題2分，共20分）1.B2.A 3.B 4.C 5.D 6.B 7.D8.A9.D10.C填空題（每空1分，共26分）1.聯(lián)系 圖（或圖結(jié)構(gòu)）2.3.top=04.O (1)O (n)5.128441086.65515132-145-2515637圖7337.旬予n-18.后序序列后綴

8、表這式9.2nn-1n+110.2i+12i+211.開(kāi)放定址法鏈接法12.快速歸并（或逆波蘭式）(i-1)/2運(yùn)算題（每題6分，共24分）1.(1)(1,5,1),(32-1),(4,5,-2),(5,1,5),(6,3,7)(3 分)圖8(2)三元組線性表的順序存儲(chǔ)表示如圖7示。2. 如圖8所示。3. DFS:BFS:4. 拓樸排序?yàn)椋?365721四、閱讀算法(每題7分，共14分)1. (1)判斷n是否是素?cái)?shù)(或質(zhì)數(shù))(2) O(而)2. 功能為：從初始點(diǎn)Vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。六、編寫(xiě)算法(8分)ElemTypeDeleFront(LNode*&HL)if(

9、HL=NULL)cerr<<"空表"<<endl;exit(1);LNode*p=HL;HL=HL->next;ElemTypetemp=p->data;deletep;returntemp;試卷十三一、選擇題(30分)1 .下列程序段的時(shí)間復(fù)雜度為()。for(i=0;i<m;i+)for(j=0;j<t;j+)cij=0;for(i=0;i<m；i+)for(j=0;j<t;j+)for(k=0;k<n；k+)cij=cij+aik*bkj;(A)O(m*n*t)(B)O(m+n+t)(C)O(m+n*t

10、)(D)O(m*t+n)2 .設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)()個(gè)元素。(A)n-i(B)n+l-i(C)n-1-i(D)i3 .設(shè)F是由T1、T2和T3三棵樹(shù)組成的森林，與F對(duì)應(yīng)的二叉樹(shù)為B,T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3,則二叉樹(shù)B的根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)數(shù)為()。(A)N1-1(B)N2-1(C)N2+N3(D)N1+N34 .利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為()。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(1og2n)5 .設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后

11、面插入結(jié)點(diǎn)X的操作序列為()。(A) p->right=s;s->left=p;p->right->left=s;s->right=p->right；(B) s->left=p;s->right=p->right；p->right=s；p->right->left=s；(C) p->right=s；p->right->left=s；s->left=p；s->right=p->right；(D) s->left=p;s->right=p->right;p->righ

12、t->left=s;p->right=s;7 .設(shè)輸入序列1、2、3、n經(jīng)過(guò)棧作用后，輸出序列中的第一個(gè)元素是n,則輸出序列中的第i個(gè)輸出元素是()。(A)n-i(B)n-1-i(C)n+l-i(D)不能確定8 .設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key尸key%p,則p最好選擇()。(A)小于等于m的最大奇數(shù)(B)小于等于m的最大素?cái)?shù)(C)小于等于m的最大偶數(shù)(D)小于等于m的最大合數(shù)9 .設(shè)在一棵度數(shù)為3的樹(shù)中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有()個(gè)。(A)4(B)5(C)6(D)710 .設(shè)完全無(wú)向圖中有n個(gè)頂

13、點(diǎn)，則該完全無(wú)向圖中有()條邊。(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/214設(shè)有向無(wú)環(huán)圖G中的有向邊集合E=<1,2>,<2,3>,<3,4>,<1,4>,則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖?)。(A)1,2,3,4(B)2,3,4,1(C)1,4,2,3(D)1,2,4,3二、填空題(30分)1 .設(shè)指針p指向單鏈表中結(jié)點(diǎn)A,指針s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為：1)s->next=;2)p->next=s；3)t=p->data；4)p->

14、data=;5)s->data=t;2 .設(shè)某棵完全二叉樹(shù)中有100個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中有個(gè)葉子結(jié)點(diǎn)。3 .設(shè)某順序循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中最多存儲(chǔ)隊(duì)列元素。6. 設(shè)一組初始記錄關(guān)鍵字序列為(20,12,42,31,18,14,28),則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹(shù)的平均查找長(zhǎng)度是。7. 設(shè)一棵二叉樹(shù)的中序遍歷序列為BDCA,后序遍歷序列為DBAC,則這棵二叉樹(shù)的前序序列為。8.設(shè)用于通信的電文僅由 8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7、 19、 2、 6、 32、3、21、10,根據(jù)這

15、些頻率作為權(quán)值構(gòu)造哈夫曼樹(shù)，則這棵哈夫曼樹(shù)的高度為。10.設(shè)無(wú)向圖G（如右圖所示），則其最小生成樹(shù)上所有邊的權(quán)值之和為三、判斷題（20分）1. 有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。（）2. 對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。（）3. 子串“ABC在主串“AABCABCD中的位置為2。（）4. 若一個(gè)葉子結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。（）6. 用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，則其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)無(wú)關(guān)而與圖中邊數(shù)有關(guān)。（）7. 中序遍歷一棵二叉排序樹(shù)可以得到一個(gè)有序的序列。（）8. 入棧操作和入隊(duì)列操

16、作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。（）9. 順序表查找指的是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行查找。（）10. 堆是完全二叉樹(shù)，完全二叉樹(shù)不一定是堆。（）五、算法設(shè)計(jì)題（20分）1. 設(shè)計(jì)計(jì)算二叉樹(shù)中所有結(jié)點(diǎn)值之和的算法。2. 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。3. 設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。參考答案一、選擇題1. A 2, A3. A 4, C5. D6. D 7, C 8. B 9. C10. A11. C12. C 13. D 14. A 15. A精選范本，供參考!、填空題1. p->next,s->data2.503.m-14.6,85.快速，堆6.19/

17、77. CBDA 8.69.(24,65,33,80,70,56,48)10.8三、判斷題1.錯(cuò) 2.對(duì)3.對(duì) 4.對(duì)5.錯(cuò)6.錯(cuò) 7.對(duì)8.對(duì) 9.錯(cuò)10.對(duì)四、算法設(shè)計(jì)題1.設(shè)計(jì)計(jì)算二叉樹(shù)中所有結(jié)點(diǎn)值之和的算法voidsum(bitree*bt,int&s)if(bt!=0)s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);2. 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。voidquickpass(intr,ints,intt)inti=s,j=t,x=rs;while(i<j)while(i<j&&

18、amp;rj%2=0)j=j-1;if(i<j)ri=rj;i=i+1;while(i<j&&ri%2=1)i=i+1;if(i<j)rj=ri;j=j-1;ri=x;3. 設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。intisriselk(lklist*head)if(head=0|head->next=0)return(1);elsefor(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)return(0);return。)；試卷十四一、選擇題(24分)1 .

19、下列程序段的時(shí)間復(fù)雜度為()。i=0,s=0;while(s<n)s=s+i；i+;(A)O(n1/2)(B)O(n1/3)(C)O(n)(D)O(n2)2 .設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列()存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。(A)單向鏈表(B)單向循環(huán)鏈表(C)雙向鏈表(D)雙向循環(huán)鏈表3 .設(shè)指針q指向單鏈表中結(jié)點(diǎn)A,指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B,指針s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A和結(jié)點(diǎn)B插入結(jié)點(diǎn)X的操作序列為()。(A)s->next=p->next；p->next=-s；(B)q->next=s；s->next=p；

20、(C)p->next=s->next；s->next=p；(D)p->next=s；s->next=q；4.設(shè)輸入序列為1、2、3、4、5、6,則通過(guò)棧的作用后可以得到的輸出序列為()。(A)5,3,4,6,1,2(B)3,2,5,6,4,1(C)3,1,2,5,4,6(D)1,5,4,6,2,35.設(shè)有一個(gè)10階的下三角矩陣A(包括對(duì)角線)，按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，則A54地址與A00的地址之差為()。(A)10(B)19(C)28(D)556,設(shè)一棵m叉樹(shù)中有Ni個(gè)度數(shù)為1的結(jié)點(diǎn)，N2個(gè)度數(shù)為

21、2的結(jié)點(diǎn)，Nm個(gè)度數(shù)為m的結(jié)點(diǎn)，則該樹(shù)中共有()個(gè)葉子結(jié)點(diǎn)。%(i1)Nj工Ni"M1%(i1)Nj(A)i4(B)il(C)i(D)i=28 .設(shè)一組權(quán)值集合W=(15,3,14,2,6,9,16,17),要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹(shù)，則這棵哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度為()。(A)129(B)219(C)189(D)2299 .設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測(cè)法把這n個(gè)關(guān)鍵字映射到HASH表中需要做()次線性探測(cè)。(A)n2(B)n(n+1)(C)n(n+1)/2(D)n(n-1)/210 .設(shè)某棵二叉樹(shù)中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n,

22、則這棵二叉中共有()個(gè)結(jié)點(diǎn)。(A)2n(B)n+l(C)2n-1(D)2n+l二、填空題(48分，其中最后兩小題各6分)1. 設(shè)需要對(duì)5個(gè)不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較次，至多需要比較次。5. 設(shè)一棵m叉樹(shù)脂的25點(diǎn)數(shù)為n,用多重鏈表表示其存儲(chǔ)結(jié)構(gòu)，則該樹(shù)中有個(gè)空指針域。6. 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的語(yǔ)句序列為：q=p->next；p->data=q->data；p->next=；feee(q)；7. 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：、和。8. 設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，則用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷時(shí)的時(shí)間復(fù)雜度為;用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時(shí)間復(fù)雜度為。.12.設(shè)有向圖G中的有向邊的集合E=<1,2>,<2,3>,<1,4>,<4,5>,<5,3>,<4,6>,<6,5>,則該圖的一個(gè)拓?fù)湫蛄袨椤?3. 下面程序段的功能是建立二叉樹(shù)的算法，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。typedefstructnodeintdata;stru