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

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