數(shù)據(jù)結(jié)構(gòu)考試題4

1、要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學(xué)號。一、單項選擇題（每小題2分，共15小題，共計30分）1. 以下不屬于存儲結(jié)構(gòu)是 。A.棧B.線索樹C.哈希表D.雙鏈表2. 以下算法的時間復(fù)雜度為 。void fun(int n)int i=1;while (i<=n)i=i*3;A. O(n)B. O(n2)C. O(log2n)D. O(log3n)3. 在含有n個節(jié)點的單鏈表中查找第i個節(jié)點的平均時間復(fù)雜度是 。A.O(log2n)B.O(1)C.O(n2)D.O(n)4. 設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素a，b，c，d，e，f，g依次進入

2、棧S。若每個元素出棧后立即進入隊列Q，且7個元素出列的順序是b，d，c，f，e，a，g，則棧S的容量至少是 。A. 1B. 2C. 3D. 45. 已知循環(huán)隊列存儲在一維數(shù)組A0.n-1中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列空，且要求第一個進入隊列的元素存儲在A0處，則初始時front和rear的值分別是 。A. 0，0B. 0，n-1C. n-1，0D. n-1，n-16. 一個n×n的對稱矩陣A，如果采用以列優(yōu)先（即以列序為主序）的壓縮方式存放到一個一維數(shù)組B中，則B的容量為 。A. n2B.C. D.7. 若一棵3次樹中有a個度為1的節(jié)點，

3、b個度為2的節(jié)點，c個度為3的節(jié)點，則該樹中有 個葉子節(jié)點。A.1+2b+3cB.a+2b+3cC.2b+3cD.1+b+2c8. 一個無向連通圖中有16條邊，所有頂點的度均小于5，度為4的頂點有3個，度為3的頂點有4個，度為2的頂點有2個，則該圖有 個頂點。A.10B.11C.12D.139. 一個表示工程的AOE網(wǎng)中的關(guān)鍵路徑 。A.必須是唯一的B.可以有多條C.可以沒有D.以上都不對10. 用鄰接矩陣表示圖，對于求從某源點到其余各頂點的Dijkstra算法，在圖的頂點數(shù)為10時計算時間約為10ms，則在圖的頂點數(shù)為40時計算時間約為 ms。A.10B.80C.160D.20011. 設(shè)有

4、100個元素的有序表，用折半查找時，成功時最大的比較次數(shù)是 。A.25B.50C.10D.712. 在含有27個節(jié)點的二叉排序樹上，查找關(guān)鍵字為35的節(jié)點，則依次比較的關(guān)鍵字有可能是 。A.28,36,18,46,35B.18,36,28,46,35C.46,28,18,36,35D.46,36,18,26,3513. 采用遞歸方式對順序表進行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是 。A. 遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B. 每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)C. 每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D. 遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)14. 數(shù)據(jù)序列8,

5、9,10,4,5,6,20,1,2只能是 算法的兩趟排序后的結(jié)果。A.簡單選擇排序B.冒泡排序C.直接插入排序D.堆排序15. 對一組數(shù)據(jù)(84,47,25,15,21)排序，數(shù)據(jù)在排序過程中的變化如下：（1）84，47，25，15，21（2）21，47，25，15，84（3）15，21，25，47，84（4）15，21，25，47，84則所采用的排序方法是 。A.冒泡排序B.快速排序C.堆排序D.直接插入排序二、問答題（共3小題，每小題10分，共計30分）1. 若已知一棵完全二叉樹（所有節(jié)點值均不同）的先序、中序或后序遍歷序列中的一種，能夠唯一確定這棵二叉樹嗎？如果能，請以其中一種遍歷序列來

6、說明構(gòu)造該二叉樹的過程。如果不能，并舉一個反例予以說明。2. 對于一個帶權(quán)連通無向圖G，可以采用Prim算法構(gòu)造出從某個頂點v出發(fā)的最小生成樹，問該最小生成樹是否一定包含從頂點v到其他所有頂點的最短路徑。如果回答是，請予以證明；如果回答不是，請給出反例。3. 簡述堆和二叉排序樹的區(qū)別。三、算法設(shè)計題（共計40分）1. 用單鏈表來存儲集合，并假設(shè)這樣的單鏈表中的節(jié)點遞增有序，設(shè)計一個盡可能高效的算法求兩個集合A和B的并集C。設(shè)A、B中分別有m和n個元素，分析你設(shè)計的算法的時間和空間復(fù)雜度。（15分）2. 假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)進行存儲，假設(shè)每個節(jié)點值為單個字符且所有節(jié)點值不同，設(shè)計一個算法

7、，輸出二叉樹b中第k的所有節(jié)點值，并分析你所設(shè)計算法的時間復(fù)雜度。（15分）說明：以上兩題求算法的時間和空間復(fù)雜度只需給出結(jié)果，不必給出詳細步驟。3. 圖的鄰接表是一種圖的鏈?zhǔn)酱鎯Y(jié)構(gòu)，請給出鄰接表的完整類型定義。采用你所設(shè)計的鄰接表作為存儲結(jié)構(gòu)，設(shè)計一個算法，求出無向圖G的連通分量個數(shù)。（10分）“數(shù)據(jù)結(jié)構(gòu)”考試試題（A）參考答案一、單項選擇題（每小題2分，共15小題，共計30分）1. A2. D3. D4. C5. B6. C7. D8. D9. B10. C11. D12. D13. D14. C15. C二、問答題（共3小題，每小題10分，共計30分）1. 答：能夠。因為任一種遍歷序列

8、中含有節(jié)點個數(shù)n，當(dāng)n已知時就可以確定完全二叉樹的形態(tài)，以給定先序遍歷序列a1a2an為例，由該完全二叉樹形態(tài)得到的先序遍歷序列b1b2bn，則bi=ai，這樣就可以唯一構(gòu)造這棵二叉樹。評分：回答不能夠，計0分。2. 答：不是。如左圖從頂點0出發(fā)的最小生成樹為右圖，而從頂點0到頂點的2的最短路徑為0®2，而不是最小生成樹中的0®1®2。 評分：回答是，計0分?；卮鸩皇?，給5分，再依據(jù)反例另給05分。3. 答：以小根堆為例，堆的特點是雙親節(jié)點的關(guān)鍵字必然小于等于孩子節(jié)點的關(guān)鍵字，而兩個孩子節(jié)點的關(guān)鍵字沒有次序規(guī)定。而二叉排序樹中，每個雙親節(jié)點的關(guān)鍵字均大于左子樹節(jié)點

9、的關(guān)鍵字，每個雙親節(jié)點的關(guān)鍵字均小于右子樹節(jié)點的關(guān)鍵字，也就是說，每個雙親節(jié)點的左、右孩子的關(guān)鍵字有次序關(guān)系。三、算法設(shè)計題（共計40分）1. 解：由于單鏈表是遞增有序的，可以采用歸并算法提高求并集的效率，結(jié)果并集C采用尾插法建表。對應(yīng)算法如下：void Unionset(LinkList *A,LinkList *B,LinkList *&C)LinkList *pa=A->next,*pb=B->next,*s,*r;C=(LinkList *)malloc(sizeof(LinkList);/建立C的頭節(jié)點r=C;/r始終指向單鏈表C的尾節(jié)點while (pa!=NU

10、LL && pb!=NULL)if (pa->data<pb->data)/僅復(fù)制*pa節(jié)點s=(LinkList *)malloc(sizeof(LinkList);s->data=pa->data;r->next=s; r=s;pa=pa->next;else if (pa->data>pb->data)/僅復(fù)制*pb節(jié)點s=(LinkList *)malloc(sizeof(LinkList);s->data=pb->data;r->next=s; r=s;pb=pb->next;else

11、s=(LinkList *)malloc(sizeof(LinkList);s->data=pa->data;r->next=s; r=s;pa=pa->next;pb=pb->next;while (pa!=NULL)/復(fù)制A單鏈表的余下節(jié)點s=(LinkList *)malloc(sizeof(LinkList);s->data=pa->data;r->next=s; r=s;pa=pa->next;while (pb!=NULL)/復(fù)制B單鏈表的余下節(jié)點s=(LinkList *)malloc(sizeof(LinkList);s-&

12、gt;data=pb->data;r->next=s; r=s;pb=pb->next;r->next=NULL;本算法的時間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(m+n)，其中m、n分別為A、B單鏈表中的節(jié)點個數(shù)。評分：算法占11分，時間和空間復(fù)雜度各占2分。2. 解：采用先序序列，對應(yīng)的算法如下：void Dispk(BTNode *b,int k)Dispk1(b,k,1);void Dispk1(BTNode *b,int k,int h)if (b!=NULL)if (h=k) printf(“%c “,b->data);Dispk1(b->lch

13、ild,k,h+1);Dispk1(b->rchild,k,h+1);評分：采用先序、中序、后序和層次遍歷均可，算法占13分，時間復(fù)雜度占2分。3. 解：鄰接表的類型定義如下：typedef char ElemType;typedef int InfoType;typedef struct ANode/邊的節(jié)點結(jié)構(gòu)類型int adjvex;/該邊的終點位置struct ANode *nextarc;/指向下一條邊的指針I(yè)nfoType info;/該邊的相關(guān)信息，對于帶權(quán)圖可存放權(quán)值 ArcNode;typedef struct Vnode/鄰接表頭節(jié)點的類型ElemType data;

14、/頂點信息ArcNode *firstarc;/指向第一條邊 VNode;typedef VNode AdjListMAXV;/AdjList是鄰接表類型typedef structAdjList adjlist;/鄰接表int n,e;/分別為圖中頂點數(shù)和邊數(shù) AGraph;/聲明圖的鄰接表類型采用遍歷方式求無向圖G中連通分量個數(shù)?；谏疃葍?yōu)先遍歷的算法如下：int visitedMAXV=0;int Getnum(AGraph *G)/求圖G的連通分量int i,n=0,visitedMAXVEX;for (i=0;i<G->n;i+)if (visitedi=0)DFS(G,i);/對圖G從頂點i開始進行深度優(yōu)先遍歷n+;/調(diào)用DFS的次數(shù)即為連通分量數(shù)re