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

1、要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學(xué)號。一、單項選擇題（每小題1.5分，20小題，共計30分）1. 以下數(shù)據(jù)結(jié)構(gòu)中 屬非線性結(jié)構(gòu)。a.棧b.串c.隊列d.平衡二叉樹2. 以下算法的時間復(fù)雜度為 。void func(int n)int i=0,s=0;while (sprior-next=p-next;p-next-prior=p-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-pr

2、ior=p-prior-prior;4. 設(shè)n個元素進棧序列是1、2、3、n，其輸出序列是p1、p2、pn，若p1=3，則p2的值為 。a.一定是2b.一定是1c.不可能是1d.以上都不對5. 在數(shù)據(jù)處理過程中常需要保存一些中間數(shù)據(jù)，如果要實現(xiàn)后保存的數(shù)據(jù)先處理，則應(yīng)采用 來保存這些數(shù)據(jù)。a.線性表b.棧c.隊列d.單鏈表6. 中綴表達式a*(b+c)-d的對應(yīng)的后綴表達式是 。a.a b c d * + -b.a b c +* d -c.a b c * + d -d.- + * a b c d7. 設(shè)棧s和隊列q的初始狀態(tài)都為空，元素a、b、c、d、e和f依次通過棧s，一個元素出棧后即進入隊

3、列q，若6個元素出隊的序列是b、d、c、f、e、a，則棧s的容量至少應(yīng)該存多少個元素？a.2b.3c.4d.58. 設(shè)循環(huán)隊列中數(shù)組的下標是0n-1，其隊頭隊尾指針分別為f和r（f指向隊首元素的前一位置，r指向隊尾元素），則其元素個數(shù)為 。a.r-fb.r-f-1c.(r-f)n+1d.(r-f+n)n9. 若將n階上三角矩陣a按列優(yōu)先順序壓縮存放在一維數(shù)組b1.n(n+1)/2中，a中第一個非零元素a1,1存于b數(shù)組的b1中，則應(yīng)存放到bk中的非零元素ai,j（1in，1ji）的下標i、j與k的對應(yīng)關(guān)系是 。a. b. c. d. 10. 一棵節(jié)點個數(shù)為n的m（m3）次樹中，其分支數(shù)是 。a

4、.nhb.n+hc.n-1d.h-111. 設(shè)森林f對應(yīng)的二叉樹為b，b中有m個節(jié)點，其根節(jié)點的右子樹的節(jié)點個數(shù)為n，森林f中第一棵樹的節(jié)點個數(shù)是 。a.m-nb.m-n-1c.n+1d. 條件不足，無法確定12. 一棵二叉樹的先序遍歷序列為abcdef，中序遍歷序列為cbaedf，則后序遍歷序列為 。a.cbefdab.fedcbac.cbedfad.不確定13. 在一個具有n個頂點的有向圖中，構(gòu)成強連通圖時至少有 條邊。a.nb.n+lc.n-1d.n/214. 對于有n個頂點的帶權(quán)連通圖，它的最小生成樹是指圖中任意一個 。a.由n-1條權(quán)值最小的邊構(gòu)成的子圖b.由n-l條權(quán)值之和最小的邊

5、構(gòu)成的子圖c.由n-l條權(quán)值之和最小的邊構(gòu)成的連通子圖d.由n個頂點構(gòu)成的極小連通子圖，且邊的權(quán)值之和最小15. 對于有n個頂點e條邊的有向圖，求單源最短路徑的dijkstra算法的時間復(fù)雜度為 。a.o(n)b.o(n+e)c.o(n2)d.o(ne)16. 一棵深度為k的平衡二叉樹，其每個非葉子節(jié)點的平衡因子均為0，則該樹共有 個節(jié)點。a.2k-1-1b.2k-1c.2k-1+1d.2k-117. 對線性表進行折半查找時，要求線性表必須 。a.以順序方式存儲b.以鏈接方式存儲c.以順序方式存儲，且節(jié)點按關(guān)鍵字有序排序d.以鏈表方式存儲，且節(jié)點按關(guān)鍵字有序排序18. 假設(shè)有k個關(guān)鍵字互為同義

6、詞，若用線性探測法把這k個關(guān)鍵字存入哈希表中，至少要進行 次探測。a.k-1b.kc.k+1d.k(k+1)/219. 以下排序算法中，某一趟排序結(jié)束后未必能選出一個元素放在其最終位置上的是 。a.堆排序b.冒泡排序c.直接插入排序d.快速排序20. 以下排序方法中， 不需要進行關(guān)鍵字的比較。a.快速排序b.歸并排序c.基數(shù)排序d.堆排序二、問答題（共3小題，每小題10分，共計30分）1. 已知一棵度為m的樹中有n1個度為1的節(jié)點，n2個度為2的節(jié)點，nm個度為m的節(jié)點，問該樹中有多少個葉子節(jié)點?2. 設(shè)數(shù)據(jù)集合d=1,12,5,8,3,10,7,13,9，試完成下列各題：（1）依次取d中各數(shù)

7、據(jù)，構(gòu)造一棵二叉排序樹bt；（2）如何依據(jù)此二叉樹bt得到d的一個有序序列；（3）畫出在二叉樹bt中刪除12后的樹結(jié)構(gòu)。3. 一個有n個整數(shù)的數(shù)組r1.n，其中所有元素是有序的，將其看成是一棵完全二叉樹，該樹構(gòu)成一個堆嗎？若不是，請給一個反例，若是，請說明理由。三、算法設(shè)計題（共計40分）1. 設(shè)a=(a1,a2,an)，b=(b1,b2,bm)是兩個遞增有序的線性表（其中n、m均大于1），且所有數(shù)據(jù)元素均不相同。假設(shè)a、b均采用帶頭節(jié)點的單鏈表存放，設(shè)計一個盡可能高效的算法判斷b是否為a的一個子序列，并分析你設(shè)計的算法的時間復(fù)雜度和空間復(fù)雜度。（15分）2. 假設(shè)二叉樹b采用二叉鏈存儲結(jié)構(gòu)存

8、儲，試設(shè)計一個算法，輸出該二叉樹中從根節(jié)點出發(fā)的第一條最長的路徑長度，并輸出此路徑上各節(jié)點的值。并分析你設(shè)計的算法的時間復(fù)雜度和空間復(fù)雜度。（15分）3. 假設(shè)一個無向圖是非連通的，采用鄰接表作為存儲結(jié)構(gòu)，試設(shè)計一個算法，輸出圖中各連通分量的節(jié)點序列。（10分）四、附加題（10分）說明：附加題不計入本次期未考試總分，但計入本課程的總分。假設(shè)一個圖g采用鄰接表作為存儲結(jié)構(gòu)，設(shè)計一個算法，判斷該圖中是否存在回路?！皵?shù)據(jù)結(jié)構(gòu)”考試試題（a）參考答案要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學(xué)號。一、單項選擇題（每小題1.5分，共計30分）1. d2. b3.

9、a4. c5. b6. b7. b8. d9. d10. c11. a12. a13. a14. d15. c16. d17. c18. d19. c20. c二、問答題（共3小題，每小題10分，共計30分）1. 解：依題意，設(shè)n為總的節(jié)點個數(shù)，n0為葉子節(jié)點（即度為0的節(jié)點）的個數(shù)，則有：n=n0+n1+n2+nm又有：n-1=度的總數(shù)，即，n-1=n11+n22+nmm兩式相減得：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、1

10、0、12、13。（3）為了刪除節(jié)點12，找到其左子樹中的最大節(jié)點10（其雙親節(jié)點為8），將該節(jié)點刪除并用10代替12，刪除后的樹結(jié)構(gòu)如圖10.21所示。圖10.20 一棵二叉排序樹 圖10.21 刪除12后的二叉排序樹3. 答：該數(shù)組一定構(gòu)成一個堆，遞增有序數(shù)組構(gòu)成一個小根堆，遞減有序數(shù)組構(gòu)成一個大根堆。以遞增有序數(shù)組為例，假設(shè)數(shù)組元素為k1、k2、kn是遞增有序的，從中看出下標越大的元素值也越大，對于任一元素ki，有kik2i，kik2i+1（inext,*q=b-next;while (p!=null & q!=null)/找兩個單鏈表中第一個值相同的節(jié)點if (p-datadata)p=

11、p-next;else if (p-dataq-data)q=q-next;elsebreak;while (p!=null & q!=null & p-data=q-data)/當兩者值相等時同步后移p=p-next;q=q-next;if (q=null)/當b中節(jié)點比較完畢返回1return 1;else/否則返回0return 0;本算法的時間復(fù)雜度為o(m+n)，空間復(fù)雜度為o(1)。其中m、n分別為a、b單鏈表的長度。2.（15分）解：由于二叉樹中最長路徑一定是從根節(jié)點到某個葉子節(jié)點的路徑，可以求出所有葉子節(jié)點到根節(jié)點的逆路徑，通過比較長度得出最長路徑，可以采用多種解法。算法中用形

12、參maxpath數(shù)組存放最長路徑，maxpathlen存放最長路徑長度。解法1：對應(yīng)的算法如下：void maxpath(btnode *b,elemtype maxpath,int &maxpathlen)/maxpathlen的初值為0struct snodebtnode *node;/存放當前節(jié)點指針int parent;/存放雙親節(jié)點在隊列中的位置 qumaxsize;/定義非循環(huán)隊列elemtype pathmaxsize;/存放一條路徑int pathlen;/存放一條路徑長度int front,rear,p,i;/定義隊頭和隊尾指針front=rear=-1;/置隊列為空隊列re

13、ar+;qurear.node=b;/根節(jié)點指針進進隊qurear.parent=-1;/根節(jié)點沒有雙親節(jié)點while (frontlchild=null & b-rchild=null)/*b為葉子節(jié)點p=front;pathlen=0;while (qup.parent!=-1)pathpathlen=qup.node-data;pathlen+;p=qup.parent;pathpathlen=qup.node-data;pathlen+;if (pathlenmaxpathlen)/通過比較求最長路徑for (i=0;ilchild!=null)/左孩子節(jié)點進隊rear+;qurear

14、.node=b-lchild;qurear.parent=front;if (b-rchild!=null)/右孩子節(jié)點進隊rear+;qurear.node=b-rchild;qurear.parent=front;本算法的時間復(fù)雜度為o(n)，空間復(fù)雜度為o(n)。解法2：對應(yīng)的算法如下：void maxpath1(btnode *b,elemtype path,int pathlen,elemtype maxpath,int &maxpathlen)/pathlen和maxpathlen的初值均為0int i;if (b=null)if (pathlenmaxpathlen)/通過比較求

15、最長路徑for (i=pathlen-1;i=0;i-)maxpathi=pathi;maxpathlen=pathlen;elsepathpathlen=b-data;/將當前節(jié)點放入路徑中pathlen+;/路徑長度增1maxpath1(b-lchild,path,pathlen,maxpath,maxpathlen);/遞歸掃描左子樹maxpath1(b-rchild,path,pathlen,maxpath,maxpathlen);/遞歸掃描右子樹本算法的時間復(fù)雜度為o(n)，空間復(fù)雜度為o(n)。解法3：對應(yīng)的算法如下：void maxpath2(btnode *b,elemtype

16、 maxpath,int &maxpathlen)/maxpathlen的初值為0btnode *stmaxsize;btnode *p;elemtype pathmaxsize;/存放一條路徑int pathlen;/存放一條路徑長度int i,flag,top=-1;/棧頂指針置初值if (b!=null)dowhile (b!=null)/將*b的所有左節(jié)點進棧top+;sttop=b;b=b-lchild;p=null;/p指向棧頂節(jié)點的前一個已訪問的節(jié)點flag=1;/設(shè)置b的訪問標記為已訪問過while (top!=-1 & flag)b=sttop;/取出當前的棧頂元素if (b

17、-rchild=p)/右孩子不存在或右孩子已被訪問,訪問之if (b-lchild=null & b-rchild=null) /*b為葉子節(jié)點pathlen=0;for (i=top;i=0;i-)pathpathlen=sti-data;pathlen+;if (pathlenmaxpathlen)/通過比較求最長路徑for (i=0;irchild;/b指向右孩子節(jié)點flag=0;/設(shè)置未被訪問的標記 while (top!=-1);printf(n);本算法的時間復(fù)雜度為o(n)，空間復(fù)雜度為o(n)。3. （10分）解：采用深度優(yōu)先搜索遍歷非連通圖，并輸出各連通分量節(jié)點序列的算法如下

18、：int visitedmaxv=0;dfsgraph(agraph *g)int i,j=1;/用j記錄連通分量的序號for (i=0;in;i+)if (visitedi=0)printf(第%d個連通分量節(jié)點序列:,j+);dfs(g,i);/調(diào)用前面的深度優(yōu)先遍歷算法采用廣度優(yōu)先搜索遍歷非連通圖，并輸出各連通分量節(jié)點序列的算法如下：int visitedmaxv=0;bfsgraph(agraph *g)int i,j=1;/用j記錄連通分量的序號for (i=0;in;i+)if (visitedi=0)printf(第%d個連通分量節(jié)點序列:,j+);bfs(g,i);/調(diào)用前面的廣度優(yōu)先遍歷算法四、附加題（10分）說明：附加題不計入本次期未考試總分，但計入本課程的總分。假設(shè)一個連通圖采用鄰接表作為存儲結(jié)構(gòu)，試設(shè)計一個算法，判斷其中是否存在回路。解：采用深度優(yōu)先遍歷方法，從頂點v出發(fā)，對每個訪問的頂點w做標記（visitedw=1）。若頂點w（先訪問）和i（后訪問）均已訪問過，表示從頂點w到頂點i存在一條路徑。當從頂點i出發(fā)遍歷，發(fā)現(xiàn)頂點i到頂點w有一條邊時，表示存在一個回路（該回路上包含頂點w和i）。算法cycle(g,v,has)從頂點v出發(fā)判斷圖g中是否存在回路，has