PAGE6 2008年攻讀碩士學(xué)位研究生入學(xué)考試試題 2008年攻讀碩士學(xué)位研究生入學(xué)考試試題 PAGE5數(shù)據(jù)結(jié)構(gòu)部分（共75分）一.單項(xiàng)選擇題（2×10分，共20分）1.某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除第一個(gè)結(jié)點(diǎn)，故采用d存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表 B.循環(huán)單鏈表C.雙鏈表 D.僅有尾結(jié)點(diǎn)指針的循環(huán)單鏈表2.棧和隊(duì)列的共同點(diǎn)是c。A.都是先進(jìn)后出 B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素 D.沒有共同點(diǎn)3．對(duì)于含有n個(gè)互不相同字符的串，則真子串（不包括串自身）的個(gè)數(shù)是c。A.n B.n2C.n(n+1)/2 D.n(n-1)/24.在一棵度為3的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為2*2+1*1=5。A.4 B.5C.6 D.75.某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是d。A.空或只有一個(gè)結(jié)點(diǎn) B.完全二叉樹C.二叉排序樹 D.高度等于其結(jié)點(diǎn)數(shù)6.對(duì)圖1所示的無向圖，從頂點(diǎn)1開始進(jìn)行深度優(yōu)先遍歷；可能得到頂點(diǎn)訪問序列是a。A.1243576 B.1243567C.1245637 D.1234576圖1一個(gè)無向圖7.對(duì)于含有n個(gè)頂點(diǎn)的帶權(quán)無向連通圖，它的最小生成樹是指該圖中任意一個(gè)d。A.由n-1條權(quán)值最小的邊構(gòu)成的子圖B.由n-l條權(quán)值之和最小的邊構(gòu)成的子圖C.由n條權(quán)值之和最小的邊構(gòu)成的連通子圖D.由n個(gè)頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的連通子圖8.有一組數(shù)據(jù){15,9,7,8,20,1,7,4}，用堆排序的篩選方法建立的初始小根堆為c。A.{1,4,8,9,20,7,15,7} B.{1,7,15,7,4,8,20,9}C.{1,4,7,8,20,15,7,9} D.以上都不對(duì)9.在含有27個(gè)結(jié)點(diǎn)的二叉排序樹上，查找關(guān)鍵字為35的結(jié)點(diǎn)，則依次比較的關(guān)鍵字有可能是d。A.28,36,18,46,35 B.18,36,28,46,35C.46,28,18,36,35 D.46,36,18,28,3510.采用敗者樹進(jìn)行k路平衡歸并的外排序算法，其總的歸并效率與kb。A.有關(guān) B.無關(guān)二.問答題（共30分）1.（5分）分析以下算法的時(shí)間復(fù)雜度（要求給出求解過程）。voidfun(intn){inti,s=0;while(s<n){ i++; s+=i;}}2.（5分）設(shè)b是二叉樹（采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)）的根結(jié)點(diǎn)指針，給出以下算法的遞歸模型并說明算法的功能：intfun(BTNode*b){if(b==NULL)return0;elseif(b->lchild!=NULL&&b->rchild!=NULL)returnfun(b->lchild)+fun(b->rchild)+1;elsereturnfun(b->lchild)+fun(b->rchild);}3.（5分）有一個(gè)長(zhǎng)度為12的有序表R[0..11]，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)是多少？（要求給出求解過程）4.（8分）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA5.（4分）對(duì)于有n個(gè)頂點(diǎn)、e條邊的圖（1）若是無向圖，采用鄰接矩陣存儲(chǔ)，其非零的元素有多少？（2）若是有向圖，采用鄰接矩陣存儲(chǔ)，其非零的元素有多少？（3）若是無向圖，采用鄰接表存儲(chǔ)，其表頭結(jié)點(diǎn)和表結(jié)點(diǎn)個(gè)數(shù)是多少？（3）若是有向圖，采用鄰接表存儲(chǔ)，其表頭結(jié)點(diǎn)和表結(jié)點(diǎn)個(gè)數(shù)是多少？6．（3分）簡(jiǎn)要說明在執(zhí)行快速排序算法時(shí)，若把棧換為隊(duì)列會(huì)對(duì)最終排序結(jié)果有什么影響？三.算法設(shè)計(jì)題（共25分）1.（10分）設(shè)有一個(gè)帶頭結(jié)點(diǎn)的單鏈表hc，設(shè)計(jì)一個(gè)算法：voidsplit(LinkList*hc,LinkList*&ha,LinkList*&hb,ElemTypex,ElemTypey)將hc拆分成兩個(gè)帶頭結(jié)點(diǎn)的單鏈表ha和hb，其中ha的所有結(jié)點(diǎn)值均大于等于x且小于等于y，hb為其他結(jié)點(diǎn)。2．（15分）假設(shè)一棵二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，每個(gè)結(jié)點(diǎn)的類型如下（每個(gè)結(jié)點(diǎn)值均為正整數(shù)且大小均不同）：typedefstructnode { intdata;structnode*lchild,*rchild; /*左、右孩子結(jié)點(diǎn)指針*/}BSTNode;（1）（10分）設(shè)計(jì)一個(gè)算法intisBST(BSTNode*bt)，判斷二叉樹bt是否是一棵二叉排序樹；（2）（5分）說明你的算法的正確性。數(shù)據(jù)結(jié)構(gòu)部分參考答案一.單項(xiàng)選擇題（2×10分，共20分）1.D 2.C 3.C 4.B 5.D6.A 7.D 8.C 9.D 10.B二.問答題（共30分）1.算法中的基本操作為while語句，設(shè)while循環(huán)語句執(zhí)行T(n)次，有：s=1+2+3+…+T(n)<n即EQ\F((1+T(n))*T(n),2)<n，顯然O()所以算法時(shí)間復(fù)雜度為O()。 評(píng)分標(biāo)準(zhǔn)：只有正確結(jié)果給2分，推導(dǎo)過程為3分。2.答：對(duì)應(yīng)的遞歸模型如下：f(b)=0 b=NULLf(b)=f(b->lchild)+f(b->rchild)+1若*b為雙分支結(jié)點(diǎn)f(b)=f(b->lchild)+f(b->rchild) 其他情況該算法用于計(jì)算b二叉樹中雙分支結(jié)點(diǎn)的個(gè)數(shù)。評(píng)分標(biāo)準(zhǔn)：遞歸模型占3分，功能占2分。3.構(gòu)造相應(yīng)的判定樹如圖2所示(圖中結(jié)點(diǎn)的值對(duì)應(yīng)元素的序號(hào))，第一層1個(gè)結(jié)點(diǎn)，第二層2個(gè)結(jié)點(diǎn)，第三層個(gè)4結(jié)點(diǎn)，第四層5個(gè)結(jié)點(diǎn)，則：ASL==。 評(píng)分標(biāo)準(zhǔn)：只有正確結(jié)果給2分，推導(dǎo)過程為3分。圖2一棵判定樹4.由這些顯示部分推出二叉樹如圖3所示。則先序序列為：ABDFKICEHJG；中序序列為：DBKFIAHEJCG；后序序列為：DKIFBHJEGCA。評(píng)分標(biāo)準(zhǔn)：二叉樹、先序序列、中序序列和后序序列各占2分。圖3一棵二叉樹5.對(duì)于有n個(gè)頂點(diǎn)、e條邊的圖 （4分）（1）2e（2）e（3）n+2e（3）n+e評(píng)分標(biāo)準(zhǔn)：每小題1分6．在執(zhí)行快速排序算法時(shí)，用棧保存每趟快速排序劃分后左、右子區(qū)段的首、尾地址，其目的是為了在處理子區(qū)段未排序子序列時(shí)能夠知道其范圍，這樣才能對(duì)該子序列進(jìn)行排序(排序過程中可能產(chǎn)生新的左、右區(qū)段)，但這與處理子序列的先后順序沒什么關(guān)系，而僅僅起存儲(chǔ)作用。因此，用隊(duì)列同樣可以存儲(chǔ)子區(qū)段的首、尾地址，即可以取代棧的作用。在執(zhí)行快速排序算法時(shí)，把棧換為隊(duì)列對(duì)最終排序結(jié)果不會(huì)產(chǎn)生任何影響。評(píng)分標(biāo)準(zhǔn)：答沒有影響的給1分，說明原因的給2分。三.算法設(shè)計(jì)題（共25分）1.（10分）voidsplit(LinkList*hc,LinkList*&ha,LinkList*&hb,ElemTypex,ElemTypey){LinkList*p=hc->next,*ra,*rb;ha=hc;ra=ha;hb=(LinkList*)malloc(sizeof(LinkList));rb=hb;while(p!=NULL){if(p->data>=x&&p->data<=y){ra->next=p;ra=p;}else{rb->next=p;rb=p;}p=p->next;}R1->next=r2->next=NULL;}評(píng)分標(biāo)準(zhǔn)：有多種解法，以上是采用尾插法建表，也可以從hc中刪除滿足條件的結(jié)點(diǎn)另建表等，根據(jù)情況判分。2．解：（1）intd=0;intisBST(BSTNode*bt){intb1,b2;if(bt==NULL)return1;else{b1=isBST(bt->lchild);if(