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

1、要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號(hào)。每張答題紙都要寫上姓名和學(xué)號(hào)。一、單項(xiàng)選擇題（每小題1.5分，20小題，共計(jì)30分）1. 以下數(shù)據(jù)結(jié)構(gòu)中 屬非線性結(jié)構(gòu)。A.棧B.串C.隊(duì)列D.平衡二叉樹2. 以下算法的時(shí)間復(fù)雜度為 。void func(int n)int i=0,s=0;while (s<=n)i+;s=s+i;A. O(n)B. O()C. O(nlog2n)D. O(log2n)3. 在一個(gè)雙鏈表中，刪除p所指節(jié)點(diǎn)（非首、尾節(jié)點(diǎn)）的操作是 。A.p->prior->next=p->next;p->next->prior=p-&

2、gt;prior;B.p->prior=p->prior->prior;p->prior->prior=p;C.p->next->prior=p;p->next=p->next->next;D.p->next=p->prior->prior;p->prior=p->prior->prior;4. 設(shè)n個(gè)元素進(jìn)棧序列是1、2、3、n，其輸出序列是p1、p2、pn，若p1=3，則p2的值為 。A.一定是2B.一定是1C.不可能是1D.以上都不對(duì)5. 在數(shù)據(jù)處理過程中常需要保存一些中間數(shù)據(jù)，如果要實(shí)現(xiàn)先保

3、存的數(shù)據(jù)先處理，則應(yīng)采用 來保存這些數(shù)據(jù)。A.線性表B.棧C.隊(duì)列D.單鏈表6. 中綴表達(dá)式a*(b+c)-d的對(duì)應(yīng)的后綴表達(dá)式是 。A.a b c d * + -B.a b c +* d -C.a b c * + d -D.- + * a b c d7. 設(shè)棧s和隊(duì)列q的初始狀態(tài)都為空，元素a、b、c、d、e和f依次通過棧s，一個(gè)元素出棧后即進(jìn)入隊(duì)列q，若6個(gè)元素出隊(duì)的序列是b、d、c、f、e、a，則棧s的容量至少應(yīng)該存多少個(gè)元素？A.2B.3C.4D.58. 設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)是0N-1，其隊(duì)頭隊(duì)尾指針分別為f和r（f指向隊(duì)首元素的前一位置，r指向隊(duì)尾元素），則其元素個(gè)數(shù)為 。A.r-

4、fB.r-f-1C.(r-f)N+1D.(r-f+N)N9. 若將n階上三角矩陣A按列優(yōu)先順序壓縮存放在一維數(shù)組B1.n(n+1)/2中，A中第一個(gè)非零元素a1,1存于B數(shù)組的b1中，則應(yīng)存放到bk中的非零元素ai,j（1jn，1ij）的下標(biāo)i、j與k的對(duì)應(yīng)關(guān)系是 。A. i(i+1)/2+jB. i(i-1)/2+jC. j(j+1)/2+iD. j(j-1)/2+i10. 一棵節(jié)點(diǎn)個(gè)數(shù)為n高度為h的m（m3）次樹中，其分支數(shù)是 。A.nhB.n+mC.n-1D.h-111. 設(shè)森林F對(duì)應(yīng)的二叉樹為B，B中有m個(gè)節(jié)點(diǎn)，其根節(jié)點(diǎn)的右子樹的節(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹的節(jié)點(diǎn)個(gè)數(shù)是 。A.m-n

5、B.m-n-1C.n+1D. 條件不足，無法確定12. 一棵二叉樹的先序遍歷序列為ABCDEF，中序遍歷序列為CBAEDF，則后序遍歷序列為 。A.CBEFDAB.FEDCBAC.CBEDFAD.不確定13. 在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，構(gòu)成強(qiáng)連通圖時(shí)至少有 條邊。A.nB.n+lC.n-1D.n/214. 對(duì)于有n個(gè)頂點(diǎn)的帶權(quán)連通圖，它的最小生成樹是指圖中任意一個(gè) 。A.由n-1條權(quán)值最小的邊構(gòu)成的子圖B.由n-l條權(quán)值之和最小的邊構(gòu)成的子圖C.由n-l條權(quán)值之和最小的邊構(gòu)成的連通子圖D.由n個(gè)頂點(diǎn)構(gòu)成的極小連通子圖，且邊的權(quán)值之和最小15. 對(duì)于有n個(gè)頂點(diǎn)e條邊的有向圖，采用鄰接矩陣表示

6、，求單源最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為 。A.O(n)B.O(n+e)C.O(n2)D.O(ne)16. 一棵高度為h的平衡二叉樹，其中每個(gè)非葉子節(jié)點(diǎn)的平衡因子均為0，則該樹的節(jié)點(diǎn)個(gè)數(shù)是 。A.2h-1-1B.2h-1C.2h-1+1D.2h-117. 對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須 。A.以順序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)C.以順序方式存儲(chǔ)，且節(jié)點(diǎn)按關(guān)鍵字有序排序D.以鏈表方式存儲(chǔ)，且節(jié)點(diǎn)按關(guān)鍵字有序排序18. 假設(shè)有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入哈希表中，至少要進(jìn)行 次探測(cè)。A.k-1B.kC.k+1D.k(k+1)/219. 以下排序算法中，某

7、一趟排序結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是 。A.堆排序B.冒泡排序C.直接插入排序D.快速排序20. 以下排序方法中， 不需要進(jìn)行關(guān)鍵字的比較。A.快速排序B.歸并排序C.基數(shù)排序D.堆排序二、問答題（共4小題，每小題10分，共計(jì)40分）1. 已知一棵度為m的樹中有n1個(gè)度為1的節(jié)點(diǎn)，n2個(gè)度為2的節(jié)點(diǎn)，nm個(gè)度為m的節(jié)點(diǎn)，問該樹中有多少個(gè)葉子節(jié)點(diǎn)？（需要給出推導(dǎo)過程）2. 設(shè)關(guān)鍵字集合D=1，12，5，8，3，10，7，13，9，試完成下列各題：（1）依次取D中各關(guān)鍵字，構(gòu)造一棵二叉排序樹bt；（2）如何依據(jù)此二叉樹bt得到D的一個(gè)關(guān)鍵字遞增序列；（3）畫出在二叉樹bt中刪除12

8、后的樹結(jié)構(gòu)。3. 一個(gè)有n（n>10）個(gè)整數(shù)的數(shù)組R1.n，其中所有元素是有序的，將其看成是一棵完全二叉樹，該樹構(gòu)成一個(gè)堆嗎？若不是，請(qǐng)給一個(gè)反例；若是，請(qǐng)簡(jiǎn)要說明理由。4. 若要在N個(gè)海量數(shù)據(jù)（超過十億，不能一次全部放入內(nèi)存）中找出最大的k個(gè)數(shù)（內(nèi)存可以容納k個(gè)數(shù)），最好采用什么數(shù)據(jù)結(jié)構(gòu)和策略？請(qǐng)?jiān)敿?xì)說明你采用的數(shù)據(jù)結(jié)構(gòu)和策略，并用時(shí)間復(fù)雜度和空間復(fù)雜度來說明理由。三、算法設(shè)計(jì)題（共3小題，每小題10分，共計(jì)30分）1. 設(shè)A=(a1，a2，an)，B=(b1，b2，bm)是兩個(gè)遞增有序的線性表（其中n、m均大于1），且所有數(shù)據(jù)元素均不相同。假設(shè)A、B均采用帶頭節(jié)點(diǎn)的單鏈表存放，設(shè)計(jì)一

9、個(gè)盡可能高效的算法判斷B是否為A的一個(gè)連續(xù)子序列，并分析你設(shè)計(jì)的算法的時(shí)間復(fù)雜度和空間復(fù)雜度。（10分）2. 假設(shè)二叉樹b采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，求該二叉樹中從根節(jié)點(diǎn)出發(fā)的一條最長(zhǎng)的路徑長(zhǎng)度，并輸出此路徑上各節(jié)點(diǎn)的值。（10分）3. 假設(shè)一個(gè)無向圖是非連通的，采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法，輸出圖中各連通分量的節(jié)點(diǎn)序列。（10分）“數(shù)據(jù)結(jié)構(gòu)”考試試題（A）參考答案要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號(hào)。每張答題紙都要寫上姓名和學(xué)號(hào)。一、單項(xiàng)選擇題（每小題1.5分，共計(jì)30分）1. D2. B3. A4. C5. C6. B7. B8. D9. D10.

10、 C11. A12. A13. A14. D15. C16. D17. C18. D19. C20. C二、問答題（共3小題，每小題10分，共計(jì)30分）1. 解：依題意，設(shè)n為總的節(jié)點(diǎn)個(gè)數(shù)，n0為葉子節(jié)點(diǎn)（即度為0的節(jié)點(diǎn)）的個(gè)數(shù)，則有：n=n0+n1+n2+nm又有：n-1=度的總數(shù)，即，n-1=n1×1+n2×2+nm×m兩式相減得：1=n0-n2-2n3-(m-1)nm則有：n0=1+n2+2n3+(m-1)nm=。2. 答：（1）本題構(gòu)造的二叉排序樹如圖10.20所示。（2）D的有序序列為bt的中序遍歷次序，即：1、3、5、7、8、9、10、12、13。（3

11、）為了刪除節(jié)點(diǎn)12，找到其左子樹中的最大節(jié)點(diǎn)10（其雙親節(jié)點(diǎn)為8），將該節(jié)點(diǎn)刪除并用10代替12，刪除后的樹結(jié)構(gòu)如圖10.21所示。圖10.20 一棵二叉排序樹 圖10.21 刪除12后的二叉排序樹3. 答：該數(shù)組一定構(gòu)成一個(gè)堆，遞增有序數(shù)組構(gòu)成一個(gè)小根堆，遞減有序數(shù)組構(gòu)成一個(gè)大根堆。以遞增有序數(shù)組為例，假設(shè)數(shù)組元素為k1、k2、kn是遞增有序的，從中看出下標(biāo)越大的元素值也越大，對(duì)于任一元素ki，有ki<k2i，ki<k2i+1（i<n/2），這正好滿足小根堆的特性，所以構(gòu)成一個(gè)小根堆。3. 有一棵二叉排序樹按先序遍歷得到的序列為：(12,5,2,8,6,10,16,15,1

12、8,20)。回答以下問題：（1）畫出該二叉排序樹。（2）給出該二叉排序樹的中序遍歷序列。（3）求在等概率下的查找成功和不成功情況下的平均查找長(zhǎng)度。4. 首先讀入k個(gè)數(shù)，假設(shè)第一次讀取的k個(gè)數(shù)就是前k個(gè)最大的數(shù)，然后把k個(gè)數(shù)建成小頂堆。然后從第k+1個(gè)數(shù)開始，每個(gè)數(shù)都與堆頂?shù)臄?shù)值進(jìn)行比較，如果數(shù)字d大于堆頂元素，則把堆頂?shù)脑氐脑靥鎿Q成d，再將其調(diào)整成為小頂堆。當(dāng)所有數(shù)據(jù)都讀入并比較完之后，這個(gè)小頂堆里面的所有元素就是最大的k個(gè)數(shù)。時(shí)間復(fù)雜度為O(NlogK)，空間復(fù)雜度為O(K)。三、算法設(shè)計(jì)題（共計(jì)40分）1.（15分）解：采用二路歸并思路，用p、q分別掃描有序單鏈表A、B，先找到第一個(gè)兩

13、者值相等的節(jié)點(diǎn)，然后在兩者值相等時(shí)同步后移，如果B掃描完畢返回1，否則返回0。對(duì)應(yīng)的算法如下：int SubSeq(LinkList *A,LinkList *B)LinkList *p=A->next,*q=B->next;while (p!=NULL && q!=NULL)/找兩個(gè)單鏈表中第一個(gè)值相同的節(jié)點(diǎn)if (p->data<q->data)p=p->next;else if (p->data>q->data)q=q->next;elsebreak;while (p!=NULL && q!=NU

14、LL && p->data=q->data)/當(dāng)兩者值相等時(shí)同步后移p=p->next;q=q->next;if (q=NULL)/當(dāng)B中節(jié)點(diǎn)比較完畢返回1return 1;else/否則返回0return 0;本算法的時(shí)間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(1)。其中m、n分別為A、B單鏈表的長(zhǎng)度。2.（15分）解：由于二叉樹中最長(zhǎng)路徑一定是從根節(jié)點(diǎn)到某個(gè)葉子節(jié)點(diǎn)的路徑，可以求出所有葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的逆路徑，通過比較長(zhǎng)度得出最長(zhǎng)路徑，可以采用多種解法。算法中用形參maxpath數(shù)組存放最長(zhǎng)路徑，maxpathlen存放最長(zhǎng)路徑長(zhǎng)度。解法1：對(duì)應(yīng)的算法

15、如下：void MaxPath(BTNode *b,ElemType maxpath,int &maxpathlen)/maxpathlen的初值為0struct snodeBTNode *node;/存放當(dāng)前節(jié)點(diǎn)指針int parent;/存放雙親節(jié)點(diǎn)在隊(duì)列中的位置 QuMaxSize;/定義非循環(huán)隊(duì)列ElemType pathMaxSize;/存放一條路徑int pathlen;/存放一條路徑長(zhǎng)度int front,rear,p,i;/定義隊(duì)頭和隊(duì)尾指針front=rear=-1;/置隊(duì)列為空隊(duì)列rear+;Qurear.node=b;/根節(jié)點(diǎn)指針進(jìn)進(jìn)隊(duì)Qurear.parent=

16、-1;/根節(jié)點(diǎn)沒有雙親節(jié)點(diǎn)while (front<rear)/隊(duì)列不為空front+;b=Qufront.node;/隊(duì)頭出隊(duì)列if (b->lchild=NULL && b->rchild=NULL)/*b為葉子節(jié)點(diǎn)p=front;pathlen=0;while (Qup.parent!=-1)pathpathlen=Qup.node->data;pathlen+;p=Qup.parent;pathpathlen=Qup.node->data;pathlen+;if (pathlen>maxpathlen)/通過比較求最長(zhǎng)路徑for (i

17、=0;i<pathlen;i+)maxpathi=pathi;maxpathlen=pathlen;if (b->lchild!=NULL)/左孩子節(jié)點(diǎn)進(jìn)隊(duì)rear+;Qurear.node=b->lchild;Qurear.parent=front;if (b->rchild!=NULL)/右孩子節(jié)點(diǎn)進(jìn)隊(duì)rear+;Qurear.node=b->rchild;Qurear.parent=front;本算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。解法2：對(duì)應(yīng)的算法如下：void MaxPath1(BTNode *b,ElemType path,int pat

18、hlen,ElemType maxpath,int &maxpathlen)/pathlen和maxpathlen的初值均為0int i;if (b=NULL)if (pathlen>maxpathlen)/通過比較求最長(zhǎng)路徑for (i=pathlen-1;i>=0;i-)maxpathi=pathi;maxpathlen=pathlen;elsepathpathlen=b->data;/將當(dāng)前節(jié)點(diǎn)放入路徑中pathlen+;/路徑長(zhǎng)度增1MaxPath1(b->lchild,path,pathlen,maxpath,maxpathlen);/遞歸掃描左子樹M

19、axPath1(b->rchild,path,pathlen,maxpath,maxpathlen);/遞歸掃描右子樹本算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。解法3：對(duì)應(yīng)的算法如下：void MaxPath2(BTNode *b,ElemType maxpath,int &maxpathlen)/maxpathlen的初值為0BTNode *StMaxSize;BTNode *p;ElemType pathMaxSize;/存放一條路徑int pathlen;/存放一條路徑長(zhǎng)度int i,flag,top=-1;/棧頂指針置初值if (b!=NULL)dowhile (b!=NULL)/將*b的所有左節(jié)點(diǎn)進(jìn)棧top+;Sttop=b;b=b->lchild;p=NULL;/p指向棧頂節(jié)點(diǎn)的前一個(gè)已訪問的節(jié)點(diǎn)flag=1;/設(shè)置b的訪問標(biāo)記為已訪問過while (top!=-1 && flag)b=Sttop;/取出當(dāng)前的棧頂元素if (b->rchild=p)/右孩子不存在或右孩子已被訪問,訪問之if (b->lchild=NULL && b->rchild=NULL) /*b為葉子節(jié)