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

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

2、一個棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是（）A.231B.321C.312D.1235. AOV網(wǎng)是一種（）。A.有向圖B.無向圖C.無向無環(huán)圖D.有向無環(huán)圖7 .若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為（）參數(shù)。A.值B.函數(shù)C.指針D,引用8 .在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的（）。A.行號B.列號C.元素值D.非零元素個數(shù)二、填空題（每空1分，共28分）1 .數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的。當(dāng)結(jié)點之間存在M對N（M:N）的聯(lián)系時，稱這種結(jié)構(gòu)為。2 .隊列的插入操作是在隊列的_尾進行，刪除操作是在隊列的首進行。3 .當(dāng)用長度

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

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

5、點出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹;4. 已知一個圖的頂點集 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>若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序

6、列。inti=1;intx=(int)sqrt(n);while(+i<=x)if(n%i=0)break;if(i>x)return1;elsereturn0;指出該算法的功能;該算法的時間復(fù)雜度是多少?2.寫出下述算法的功能: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是單鏈表的頭指針，試寫出刪除頭結(jié)點的算法。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.開放定址法鏈接法12.快速歸并（或逆波蘭式）(i-1)/2運算題（每題6分，共24分）1.(1)(1,5,1),(32-1),(4,5,-2),(5,1,5),(6,3,7)(3 分)圖8(2)三元組線性表的順序存儲表示如圖7示。2. 如圖8所示。3. DFS:BFS:4. 拓樸排序為：4365721四、閱讀算法(每題7分，共14分)1. (1)判斷n是否是素數(shù)(或質(zhì)數(shù))(2) O(而)2. 功能為：從初始點Vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。六、編寫算法(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 .下列程序段的時間復(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個數(shù)據(jù)元素，則刪除表中第i個元素需要移動()個元素。(A)n-i(B)n+l-i(C)n-1-i(D)i3 .設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B,T1、T2和T3的結(jié)點數(shù)分別為N1、N2和N3,則二叉樹B的根結(jié)點的左子樹的結(jié)點數(shù)為()。(A)N1-1(B)N2-1(C)N2+N3(D)N1+N34 .利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為()。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(1og2n)5 .設(shè)指針變量p指向雙向鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后

11、面插入結(jié)點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)過棧作用后，輸出序列中的第一個元素是n,則輸出序列中的第i個輸出元素是()。(A)n-i(B)n-1-i(C)n+l-i(D)不能確定8 .設(shè)散列表中有m個存儲單元，散列函數(shù)H(key尸key%p,則p最好選擇()。(A)小于等于m的最大奇數(shù)(B)小于等于m的最大素數(shù)(C)小于等于m的最大偶數(shù)(D)小于等于m的最大合數(shù)9 .設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點數(shù)有2個，度數(shù)為2的結(jié)點數(shù)有1個，度數(shù)為1的結(jié)點數(shù)有2個，那么度數(shù)為0的結(jié)點數(shù)有()個。(A)4(B)5(C)6(D)710 .設(shè)完全無向圖中有n個頂

13、點，則該完全無向圖中有()條邊。(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/214設(shè)有向無環(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é)點A,指針s指向被插入的結(jié)點X,則在結(jié)點A的前面插入結(jié)點X時的操作序列為：1)s->next=;2)p->next=s；3)t=p->data；4)p->

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

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

16、作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的情況。（）9. 順序表查找指的是在順序存儲結(jié)構(gòu)上進行查找。（）10. 堆是完全二叉樹，完全二叉樹不一定是堆。（）五、算法設(shè)計題（20分）1. 設(shè)計計算二叉樹中所有結(jié)點值之和的算法。2. 設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。3. 設(shè)計判斷單鏈表中元素是否是遞增的算法。參考答案一、選擇題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.錯 2.對3.對 4.對5.錯6.錯 7.對8.對 9.錯10.對四、算法設(shè)計題1.設(shè)計計算二叉樹中所有結(jié)點值之和的算法voidsum(bitree*bt,int&s)if(bt!=0)s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);2. 設(shè)計將所有奇數(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è)計判斷單鏈表中元素是否是遞增的算法。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、下列程序段的時間復(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è)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列()存儲方式最節(jié)省運算時間。(A)單向鏈表(B)單向循環(huán)鏈表(C)雙向鏈表(D)雙向循環(huán)鏈表3 .設(shè)指針q指向單鏈表中結(jié)點A,指針p指向單鏈表中結(jié)點A的后繼結(jié)點B,指針s指向被插入的結(jié)點X,則在結(jié)點A和結(jié)點B插入結(jié)點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,則通過棧的作用后可以得到的輸出序列為()。(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è)有一個10階的下三角矩陣A(包括對角線)，按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A54地址與A00的地址之差為()。(A)10(B)19(C)28(D)556,設(shè)一棵m叉樹中有Ni個度數(shù)為1的結(jié)點，N2個度數(shù)為

21、2的結(jié)點，Nm個度數(shù)為m的結(jié)點，則該樹中共有()個葉子結(jié)點。%(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)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為()。(A)129(B)219(C)189(D)2299 .設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH表中需要做()次線性探測。(A)n2(B)n(n+1)(C)n(n+1)/2(D)n(n-1)/210 .設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點且度數(shù)為0的結(jié)點數(shù)為n,

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