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

要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學(xué)號。一、單項選擇題〔每題1.5分，合計30分〕1.數(shù)據(jù)結(jié)構(gòu)是指。一種數(shù)據(jù)種類數(shù)據(jù)的存儲結(jié)構(gòu)一組性質(zhì)相同的數(shù)據(jù)元素的會合相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的會合2.以下算法的時間復(fù)雜度為。voidfun(intn){inti=1;while(i<=n)i++;}A.O(n)B.O(n)C.O(nlog2n)D.O(log2n)3.在一個長度為n的有序次序表中刪除元素值為x的元素時，在查找元素x時采用二分查找，此時的時間復(fù)雜度為。A.O(n)B.O(nlogn)2C.O(n2)D.O(n)4.在一個帶頭結(jié)點的循環(huán)單鏈表L中，刪除元素值為x的結(jié)點，算法的時間復(fù)雜度為。A.O(n)B.O(n)C.O(nlog2n)D.O(n2)5.假定一個棧采用數(shù)組s[0..n-1]寄存其元素，初始時棧頂指針為n，那么以下元素x進棧的正確操作是。A.top++;s[top]=x;B.s[top]=x;top++;C.top--;s[top]=x;B.s[top]=x;top--;6.中綴表達式“2*(3+4)-1〞的后綴表達式是，其中#表示一個數(shù)值的結(jié)束。A.2#3#4#1#*+-B.2#3#4#+*1#-C.2#3#4#*+1#-D.-+*2#3#4#1#7.設(shè)環(huán)形行列中數(shù)組的下標為0～N-1，其隊頭、隊尾指針分別為front和rear〔front指向行列中隊頭元素的前一個地點，rear指向隊尾元素的地點〕，那么其元素個數(shù)為。A.rear-frontB.rear-front-1C.(rear-front)％N+1D.(rear-front+N)％N8.假定用一個大小為6的數(shù)組來實現(xiàn)環(huán)形行列，隊頭指針front指向行列中隊頭元素的前一個地點，隊尾指針rear指向隊尾元素的地點。假定目前rear和front的值分別為0和3，當從行列中刪除一個元素，再參加兩個元素后，rear和front的值分別為。精選A.1和5B.2和4C.4和2D.5和19.一棵深度為h〔h≥1〕的完全二叉樹起碼有個結(jié)點。A.2h-1B.2hC.2h+1D.2h-1+110.一棵含有n個結(jié)點的線索二叉樹中，其線索個數(shù)為。A.2nB.n-1C.n+1D.n11.設(shè)一棵哈夫曼樹中有1999個結(jié)點，該哈夫曼樹用于對個字符進行編碼。A.999B.998C.1000D.100112.一個含有n個極點的無向連通圖采用毗鄰矩陣存儲，那么該矩陣一定是。A.對稱矩陣B.非對稱矩陣C.稀疏矩陣D.濃密矩陣13.設(shè)無向連通圖有n個極點e條邊，假定知足，那么圖中一定有回路。A.e≥nB.e<nC.e=n-1D.2e≥n14.關(guān)于AOE網(wǎng)的重點路徑，以下表達是正確的。任何一個重點活動提早達成，那么整個工程一定會提早達成達成整個工程的最短時間是從源點到匯點的最短路徑長度一個AOE網(wǎng)的重點路徑一定是唯一的任何一個活動持續(xù)時間的改變可能會影響重點路徑的改變15.設(shè)有100個元素的有序表，用折半查找時，不可功時最大的比較次數(shù)是。A.25B.50C.10D.716.在一棵m階B-樹中刪除一個重點字會惹起合并，那么該結(jié)點原有個重點字。A.1B.m/2C.m/2-1D.m/2+117.哈希查找方法一般合用于情況下的查找。查找表為鏈表查找表為有序表重點字會合比地點會合大得多重點字會合與地點會合之間存在著某種對應(yīng)關(guān)系。對含有n個元素的次序表采用直接插入排序方法進行排序，在最好情況下算法的時間復(fù)雜度為。A.O(n)B.O(nlog2n)C.O(n2)D.O(n)19.用某種排序方法對數(shù)據(jù)序列{24,88,21,48,15,27,69,35,20}進行遞增排序，元素序列精選的變化情況如下：1〕{24,88,21,48,15,27,69,35,20}2〕{20,15,21,24,48,27,69,35,88}3〕{15,20,21,24,35,27,48,69,88}4〕{15,20,21,24,27,35,48,69,88}那么所采用的排序方法是。A.迅速排序B.簡單項選擇擇排序C.直接插入排序D.合并排序20.以下序列是堆的是。A.{75,65,30,15,25,45,20,10}B.{75,65,45,10,30,25,20,15}C.{75,45,65,30,15,25,20,10}D.{75,45,65,10,25,30,20,15}二、問答題〔共4小題，每題10分，合計40分〕1.如果對含有n〔n>1〕個元素的線性表的運算只有4種：刪除第一個元素；刪除最后一個元素；在第一個元素前面插入新元素；在最后一個元素的后邊插入新元素，那么最好使用以下哪一種存儲結(jié)構(gòu)，并簡要說明原因。〔1〕只有尾結(jié)點指針沒有頭結(jié)點指針的循環(huán)單鏈表〔2〕只有尾結(jié)點指針沒有頭結(jié)點指針的非循環(huán)雙鏈表〔3〕只有頭結(jié)點指針沒有尾結(jié)點指針的循環(huán)雙鏈表〔4〕既有頭結(jié)點指針也有尾結(jié)點指針的循環(huán)單鏈表2.一棵度為4的樹中，其度為0、1、2、3的結(jié)點數(shù)分別為14、4、3、2，求該樹的結(jié)點總數(shù)n和度為4的結(jié)點個數(shù)，并給出推導(dǎo)過程。有人提出這樣的一種從圖G中極點u開始結(jié)構(gòu)最小生成樹的方法：假定G=(V，E)是一個擁有n個極點的帶權(quán)連通無向圖，T=(U，TE)是G的最小生成樹，其中U是T的極點集，TE是T的邊集，那么由G結(jié)構(gòu)從開端極點u出發(fā)的最小生成樹T的步驟如下：〔1〕初始化U={u}。以u到其他極點的所有邊為候選邊。〔2〕重復(fù)以下步驟n-1次，使得其他n-1個極點被參加到U中。從候選邊中精選權(quán)值最小的邊參加到TE，設(shè)該邊在V-U中的極點是v，將v參加U中。考察極點v，將v與V-U極點集中的所有邊作為新的候選邊。假定此方法求得的T是最小生成樹，請予以證明。假定不能求得最小邊，請舉出反例。4.有一棵二叉排序樹按先序遍歷獲得的序列為：(12,5,2,8,6,10,16,15,18,20)?；貜?fù)以下問題：1〕畫出該二叉排序樹。2〕給出該二叉排序樹的中序遍歷序列。3〕求在等概率下的查找成功和不可功情況下的平均查找長度。三、算法設(shè)計題〔每題10分，合計30分〕1.設(shè)A和B是兩個結(jié)點個數(shù)分別為m和n的單鏈表〔帶頭結(jié)點〕，其中元素遞增有序。精選設(shè)計一個盡可能高效的算法求A和B的交集，要求不損壞A、B的結(jié)點，將交集寄存在單鏈表C中。給出你所設(shè)計的算法的時間復(fù)雜度和空間復(fù)雜度。2.假定二叉樹b采用二叉鏈存儲結(jié)構(gòu)，設(shè)計一個算法voidfindparent(BTNode*b,ElemTypex,BTNode*&p)求指定值為x的結(jié)點的雙親結(jié)點p，提示，根結(jié)點的雙親為NULL，假定在b中未找到值為x的結(jié)點，p亦為NULL。假定一個連通圖采用毗鄰表G存儲結(jié)構(gòu)表示。設(shè)計一個算法，求起點u到終點v的經(jīng)過極點k的所有路徑。四、附加題〔10分〕說明：附加題不計入期未考試總分，但計入本課程的總分。假定某專業(yè)有假定干個班，每個班有假定干學(xué)生，每個學(xué)生包含姓名和分數(shù)，這樣組成一棵樹，如圖1所示。假定樹中每個結(jié)點的name域均不相同，該樹采用孩子兄弟鏈存儲結(jié)構(gòu)，其結(jié)點種類定義如下：typedefstructnode{charname[50];//專業(yè)、班號或姓名floatscore;//分數(shù)structnode*child;//指向最左邊的孩子結(jié)點structnode*brother;//指向下一個兄弟結(jié)點}TNode;達成以下算法：1〕設(shè)計一個算法求所有的學(xué)生人數(shù)。2〕求指定某班的平均分。name:計算機專業(yè)score:0name:計科1name:計科nscore:0score:0name:王華name:李明name:張兵name:陳強name:許源name:張山score:86score:79score:85score:92score:79score:69圖1一棵學(xué)生成績樹精選“數(shù)據(jù)結(jié)構(gòu)〞考試一試題〔A〕參照答案要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學(xué)號。一、單項選擇題〔每題1.5分，合計30分〕1.D2.A3.A4.A5.C6.B7.D8.B9.A10.C11.C12.A13.A14.D15.D16.C17.D18.A19.A20.C二、問答題〔共4小題，每題10分，合計40分〕1.答：本題答案為〔3〕，因為實現(xiàn)上述4種運算的時間復(fù)雜度均為O(1)?！驹u分說明】選擇結(jié)果占4分，原因占6分。假定結(jié)果錯誤，但對各操作時間復(fù)雜度作了剖析，可給2～5分。2.答：結(jié)點總數(shù)n=n0+n1+n2+n3+n4，即n=23+n4，又有：度之和=n-1=0×n0+1×n1+2×n2+3×n+4×n，即n=17+4n，綜合兩式得：n=2，n=25。所以，該樹的結(jié)點總數(shù)為25，度為43444的結(jié)點個數(shù)為2。【評分說明】結(jié)果為4分，過程占6分。3.答：此方法不能求得最小生成樹。比如，關(guān)于如圖5.1〔a〕所示的帶權(quán)連通無向圖，按照上述方法從極點0開始求得的結(jié)果為5.1〔b〕所示的樹，顯然它不是最小生成樹，正確的最小生成樹如圖5.1〔c〕所示。在有些情況下，上述方法無法求得結(jié)果，比如關(guān)于如圖5.1〔d〕所示的帶權(quán)連通無向圖，從極點0出發(fā)，找到極點1〔邊〔0,1〕〕，從極點1出發(fā)，找到極點3〔邊〔1,3〕〕，再從極點3出發(fā)，找到極點0〔邊〔3,0〕〕，這樣組成回路，就不能求得最小生成樹了。1021014313325352〔a〕〔b〕1010214313332425〔c〕〔d〕圖1求最小生成樹的反例說明：只要給出一種情況即可?！驹u分說明】回復(fù)不能求得最小生成樹得5分，反例為5分。假定指出可求得最小生成樹，根據(jù)證明過程給1～2分。精選答：〔1〕先序遍歷獲得的序列為：(12,5,2,8,6,10,16,15,18,20)，中序序列是一個有序序列，所以為：(2,5,6,8,10,12,15,16,18,20)，由先序序列和中序序列能夠結(jié)構(gòu)出對應(yīng)的二叉樹，如圖2所示。〔2〕中序遍歷序列為：2,5,6,8,10,12,15,16,18,20?！?〕ASL成功=(1×1+2×2+4×3+3×4)/10=29/10。ASL不可功=(5×3+6×4/11=39/11。1251628151861020圖2【評分說明】〔1〕小題占6分，〔2〕〔3〕小題各占2分。三、算法設(shè)計題〔每題10分，合計30分〕設(shè)A和B是兩個結(jié)點個數(shù)分別為m和n的單鏈表〔帶頭結(jié)點〕，其中元素遞增有序。設(shè)計一個盡可能高效的算法求A和B的交集，要求不損壞A、B的結(jié)點，將交集寄存在單鏈表C中。給出你所設(shè)計的算法的時間復(fù)雜度和空間復(fù)雜度。解：算法如下：voidinsertion(LinkList*A,LinkList*B,LinkList*&C){LinkList*p=A->next,*q=B->next,*s,*t;C=(LinkList*)malloc(sizeof(LinkList));t=C;while(p!=NULL&&q!=NULL){if(p->data==q->data){s=(LinkList*)malloc(sizeof(LinkList));s->data=p->data;t->next=s;t=s;p=p->next;q=q->next;}elseif(p->data<q->data)p=p->next;elseq=q->next;}t->next=NULL;精選}算法的時間復(fù)雜度為O(m+n)，空間復(fù)雜度為O(MIN(m,n))。【評分說明】算法為8分，算法的時間復(fù)雜度和空間復(fù)雜度各占1分。2.假定二叉樹b采用二叉鏈存儲結(jié)構(gòu)，設(shè)計一個算法voidfindparent(BTNode*b,ElemTypex,BTNode*&p)求指定值為x的結(jié)點的雙親結(jié)點p，提示，根結(jié)點的雙親為NULL，假定未找到這樣的結(jié)點，p亦為NULL。解：算法如下：voidfindparent(BTNode*b,ElemTypex,BTNode*&p){if(b!=NULL){if(b->data==x)p=NULL;elseif(b->lchild!=NULL&&b->lchild->data==x)p=b;elseif(b->rchild!=NULL&&b->rchild->data==x)p=b;else{findparent(b->lchild,x,p);if(p==NULL)findparent(b->rchild,x,p);}}elsep=NULL;}【評分說明】本題有多種解法，相應(yīng)給分。假定一個連通圖采用毗鄰表G存儲結(jié)構(gòu)表示。設(shè)計一個算法，求起點u到終點v的經(jīng)過極點k的所有路徑。解：算法如下：intvisited[MAXV]={0};//全局變量voidPathAll(ALGraph*G,intu,intv,intk,intpath[],intd)//d是到目前為止已走過的路徑長度，調(diào)用時初值為-1{intm,i;ArcNode*p;visited[u]=1;d++;//路徑長度增1path[d]=u;//將目前極點增添到路徑中if(u==v&&In(path,d,k)==l)//輸出一條路徑{printf("");for(i=0;i<=d;i++)printf("%d",path[i]);printf("\n");}p=G->adjlist[u].firstarc;//p指向極點u的第一條弧的弧頭節(jié)點while(p!=NULL)精選{m=p->adjvex;//m為u的毗鄰點if(visited[m]==0)//假定該極點未標記接見,那么遞歸接見之PathAll(G,m,v,l,path,d);p=p->nextarc;//找u的下一個毗鄰點}visited[u]=0;//恢復(fù)環(huán)境：使該極點可從頭使用}intIn(intpath[],intd,intk)//判斷極點k是否包含在路徑中{inti;for(i=0;i<=d;i++)if(path[i]==k)return1;return0;}【評分說明】本題采用DFS算法給出一條路徑時給8分，采用BFS算法給出一條路徑時給6分。四、附加題〔10分〕說明：附加題不計入期未考試總分，但計入本課程的總分。假定某專業(yè)有假定干個班，每個班有假定干學(xué)生，每個學(xué)生包含姓名和分數(shù)，這樣組成一棵樹，如圖1所示。假定樹中每個結(jié)點的name域均不相同，該樹采用孩子兄弟鏈存儲結(jié)構(gòu)，其結(jié)點種類定義如下：typedefstructnode{charname[50];//專業(yè)、班號或姓名floatscore;//分數(shù)structnode*c