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

1、要求： 所有的題目的解答均寫在答題紙上，需寫清楚題目的序號(hào)。每張答題紙都要寫上姓名和學(xué)號(hào)。一、單項(xiàng)選擇題(選擇最準(zhǔn)確的一項(xiàng)，共15 小題，每小題2 分，共計(jì)30 分)1. 數(shù)據(jù)結(jié)構(gòu)是指。A. 一種數(shù)據(jù)類型B. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C. 一組性質(zhì)相同的數(shù)據(jù)元素的集合D. 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2. 以下算法的時(shí)間復(fù)雜度為。void fun(int n)3. int i=1,s=0;while (i<=n)s+=i+100; i+;A. O(n)B. O( n )C. O(nlog 2n)D. O(log 2n)3. 在一個(gè)長度為n 的有序順序表中刪除其中第一個(gè)元素值為x的

2、元素時(shí)，在查找元素x時(shí)采用二分查找方法，此時(shí)刪除算法的時(shí)間復(fù)雜度為。A. O(n)B. O(nlog 2n)C. O(n2)D. O( n )4. 若一個(gè)棧采用數(shù)組s0.n- 1存放其元素，初始時(shí)棧頂指針為n，則以下元素x 進(jìn)棧的正確操作是。A.top+;stop= x;B.stop= x;top+;C.top- ;stop=x;B.stop= x;top- ;5. 設(shè)環(huán)形隊(duì)列中數(shù)組的下標(biāo)為0 N- 1，其隊(duì)頭、隊(duì)尾指針分別為front 和rear( front指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，rear 指向隊(duì)尾元素的位置)，則其元素個(gè)數(shù)為。A. rear- frontB. rear-front

3、- 1C. (rear- front) N+1D. (rear - front+N) N6. 若用一個(gè)大小為6 的數(shù)組來實(shí)現(xiàn)環(huán)形隊(duì)列，隊(duì)頭指針front 指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置。若當(dāng)前rear 和 front 的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear 和 front 的值分別為。A. 1 和5B. 2 和4C. 4 和2D. 5 和17. 一棵高度為h（ h 1）的完全二叉樹至少有個(gè)結(jié)點(diǎn)。A. 2 h-1B. 2hC. 2h+1D. 2h-1+18. 設(shè)一棵哈夫曼樹中有999 個(gè)結(jié)點(diǎn)，該哈夫曼樹用于對(duì)個(gè)字符進(jìn)行編碼。A.

4、999B.499C. 500D.5019. 一個(gè)含有n 個(gè)頂點(diǎn)的無向連通圖采用鄰接矩陣存儲(chǔ)，則該矩陣一定是A. 對(duì)稱矩陣B.非對(duì)稱矩陣C. 稀疏矩陣D.稠密矩陣10. 設(shè)無向連通圖有n 個(gè)頂點(diǎn) e 條邊，若滿足，則圖中一定有回路。A. e nB. e<n- 1C. e=n- 1D. 2e n11. 如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次廣度優(yōu)先遍歷即可訪問所有頂點(diǎn)，則該圖一定是。A. 完全圖B.連通圖C. 有回路D.一棵樹12. 設(shè)有 100 個(gè)元素的有序表，用折半查找時(shí)，不成功查找時(shí)最大的比較次數(shù)是。A. 25B.50C. 10D. 713. 從 100 個(gè)元素確定的順序表中查找其中某個(gè)元

5、素（關(guān)鍵字為正整數(shù)），如果最多只進(jìn)行 5 次元素之間的比較，則采用的查找方法只可能是。A. 折半查找B.順序查找C. 哈希查找D. 二叉排序樹查找14. 有一個(gè)含有n（ n>1000） 個(gè)元素?cái)?shù)據(jù)序列，某人采用了一種排序方法對(duì)其按關(guān)鍵字遞增排序，該排序方法需要關(guān)鍵字比較，其平均時(shí)間復(fù)雜度接近最好的情況，空間復(fù)雜度為 O（1），該排序方法可能是。A. 快速排序B.堆排序C. 二路歸并排序D. 都不適合排序方法。15. 對(duì)一個(gè)線性序列進(jìn)行排序，該序列采用單鏈表存儲(chǔ)，最好采用A. 直接插入排序B.希爾排序C. 快速排序D. 都不適合二、問答題（共3 小題，每小題10 分，共計(jì)30 分）1. 如

6、果對(duì)含有n（ n>1 ）個(gè)元素的線性表的運(yùn)算只有4 種：刪除第一個(gè)元素；刪除最后一個(gè)元素；在第一個(gè)元素前面插入新元素；在最后一個(gè)元素的后面插入新元素，則最好使用以下哪種存儲(chǔ)結(jié)構(gòu)，并簡(jiǎn)要說明理由。（ 1 ）只有尾結(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)指針的循環(huán)單鏈表（ 2）只有尾結(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)指針的非循環(huán)雙鏈表（ 3）只有頭結(jié)點(diǎn)指針沒有尾結(jié)點(diǎn)指針的循環(huán)雙鏈表（ 4）既有頭結(jié)點(diǎn)指針也有尾結(jié)點(diǎn)指針的循環(huán)單鏈表2. 對(duì)于一個(gè)帶權(quán)連通無向圖G， 可以采用Prim 算法構(gòu)造出從某個(gè)頂點(diǎn)v 出發(fā)的最小生成樹，問該最小生成樹是否一定包含從頂點(diǎn)v 到其他所有頂點(diǎn)的最短路徑。如果回答是，請(qǐng)予以證明；如果回答不是，請(qǐng)給出反例

7、。3. 有一棵二叉排序樹按先序遍歷得到的序列為：（12,5,2,8,6,10,16,15,18,20） ?；卮鹨韵聠栴}：（ 1 ）畫出該二叉排序樹。（ 2）給出該二叉排序樹的中序遍歷序列。（ 3）求在等概率下的查找成功和不成功情況下的平均查找長度。三、算法設(shè)計(jì)題（共3 小題，共計(jì)40 分）4. （ 15分）假設(shè)二叉樹b采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法void findparent（BTNode*b,ElemType x,BTNode *&p） 求指定值為x 的結(jié)點(diǎn)的雙親結(jié)點(diǎn)p。提示，根結(jié)點(diǎn)的雙親為NULL ，若在二叉樹b 中未找到值為x的結(jié)點(diǎn)，p 亦為 NULL 。5. （ 10 分）

8、假設(shè)一個(gè)有向圖G 采用鄰接表存儲(chǔ)。設(shè)計(jì)一個(gè)算法判斷頂點(diǎn)i 和頂點(diǎn) j（ i j）之間是否相互連通，假設(shè)這兩個(gè)頂點(diǎn)均存在。6. （ 15 分）有一個(gè)含有n 個(gè)整數(shù)的無序數(shù)據(jù)序列，所有的數(shù)據(jù)元素均不相同，采用整數(shù)數(shù)組R0.n- 1存儲(chǔ)，請(qǐng)完成以下任務(wù)：（ 1 ）設(shè)計(jì)一個(gè)盡可能高效的算法，輸出該序列中第k（ 1 k n）小的元素，算法中給出適當(dāng)?shù)淖⑨屝畔?。提示：利用快速排序的思路。?2）分析你所設(shè)計(jì)的求解算法的平均時(shí)間復(fù)雜度，并給出求解過程?！皵?shù)據(jù)結(jié)構(gòu)”考試試題（ A）參考答案要求： 所有的題目的解答均寫在答題紙上，需寫清楚題目的序號(hào)。每張答題紙都要寫 上姓名和學(xué)號(hào)。一、單項(xiàng)選擇題（共15 小題，

9、每小題2 分，共計(jì)30 分）1.D2.B3.A4. C5. D6. B7. A8. C9. A10. A11. B12. D13.C14.B15.A二、問答題（共3 小題，每小題10 分，共計(jì)30 分）1. 答：本題答案為（3） ，因?yàn)閷?shí)現(xiàn)上述4 種運(yùn)算的時(shí)間復(fù)雜度均為O（1）。2. 答：不是。如圖1 所示的圖G 從頂點(diǎn) 0 出發(fā)的最小生成樹如圖2 所示，而從頂點(diǎn)0到頂點(diǎn)的2 的最短路徑為0 2，而不是最小生成樹中的0 1 2。圖 1 一個(gè)帶權(quán)連通無向圖G圖 2 圖 G 的一棵最小生成樹3. 答： （ 1）先序遍歷得到的序列為：（12,5,2,8,6,10,16,15,18,20） ，中序序列

10、是一個(gè)有序序列，所以為：（2,5,6,8,10,12,15,16,18,20），由先序序列和中序序列可以構(gòu)造出對(duì)應(yīng)的二叉樹，如圖3 所示。 4 分（ 2）中序遍歷序列為：2,5,6,8,10,12,15,16,18,20。 4分（ 3） ASL 成功 =（1 × 1+2× 2+4× 3+3×4）/10=29/10。 1 分ASL 不成功 =（5 ×3+6×4/11=39/11 。 1 分圖33 小題，共計(jì)40 分)1 .( 15分)解：算法如下：void findparent(BTNode *b,ElemType x,BTNode *

11、&p) if (b!=NULL) if (b->data=x) p=NULL;else if (b->lchild!=NULL && b->lchild->data=x) p=b;else if (b->rchild!=NULL && b->rchild->data=x) p=b;else findparent(b->lchild,x,p);if (p=NULL)findparent(b->rchild,x,p);else p=NULL; 2 . （ 10 分）解：算法如下：/深度優(yōu)先遍歷算法/置已訪

12、問標(biāo)記/p指向頂點(diǎn)v的第一個(gè)鄰接點(diǎn)/若 p->adjvex頂點(diǎn)未訪問,遞歸訪問它/p指向頂點(diǎn)v的下一個(gè)鄰接點(diǎn)int visitedMAXV;void DFS(ALGraph *G,int v) ArcNode *p;visitedv=1;p=G->adjlistv.firstarc;while (p!=NULL) if (visitedp->adjvex=0)DFS(G,p->adjvex);p=p->nextarc;bool DFSTrave(ALGraph *G,int i,int j) int k;bool flag1=false,flag2=false;f

13、or (k=0;k<G->n;k+)visitedk=0;DFS(G,i);/從頂點(diǎn)i開始進(jìn)行深度優(yōu)先遍歷if (visitedj=1)flag1=true;for (k=0;k<G->n;k+)visitedk=0;DFS(G,j);/從頂點(diǎn)j開始進(jìn)行深度優(yōu)先遍歷if (visitedi=1)flag2=true;if (flag1 && flage2) return true;elsereturn false;3 .（ 15分）（1）采用快速排序的算法如下：（ 12 分）int QuickSelect(int R,int s,int t,int k)

14、 /在 Rs.t序列中找第k小的元素 int i=s,j=t;int tmp;if (s<t)/區(qū)段內(nèi)至少存在2個(gè)元素的情況 tmp=Rs;/用區(qū)段的第1個(gè)記錄作為基準(zhǔn)while (i!=j)/從區(qū)段兩端交替向中間掃描,直至i=j 為止 while (j>i && Rj>=tmp)j-;/從右向左掃描, 找第 1個(gè)小于tmp的 RjRi=Rj;/將 Rj 前移到 Ri的位置while (i<j && Ri<=tmp)i+;/從左向右掃描,找第1個(gè)大于 tmp的 RiRj=Ri;/將 Ri 后移到 Rj 的位置Ri=tmp;if (k-1=i) return Ri;else if (k-1<i) return QuickSelect(R,s,i-1,k);/在左區(qū)段中遞歸查找else return QuickSelect(R,i+1,t,k);/在右區(qū)段中遞歸查找else if (s=t && s=k-1)/區(qū)段內(nèi)只有一個(gè)元素且為Rk-1return Rk-1;void Mink(int R,int n,int k) /輸出整數(shù)數(shù)組R0. n-1中第k小的元素 if (k>=1 && k<=n)printf("%dn&quo