2010年算法與數(shù)據(jù)結(jié)構(gòu)(I)期末試題與參考答案

1、蝸牛在線更多免費學(xué)習(xí)資料等待您的光臨！20092010學(xué)年“算法與數(shù)據(jù)結(jié)構(gòu)(I)”期末試題與參考答案一、單項選擇題(本題共20分，每小題各2分)1一個完整算法應(yīng)該具備的特性之一是有窮性，這里的有窮性是指。A.算法必須寫得簡明扼要B.算法必須在有限的時間內(nèi)能夠結(jié)束C.算法的每一步必須有清晰明確的含義D.算法的每一步必須具有可執(zhí)行性2設(shè)非空單鏈表的結(jié)點構(gòu)造為datalink。若已知q指結(jié)點是p指結(jié)點的的直接前驅(qū)，則在q和p之間插入s所指結(jié)點的過程是依次執(zhí)行As->link=p->link;p->link=s;Bp->link=s->link;s->link=p;

2、C.q->link=s;s->link=p;D.p->link=s;s->link=q;3下列4種操作中，不是堆棧的基本操作的是。A.判斷堆棧是否為空B.刪除棧頂元素C.刪除棧底元素D.將堆棧置為空棧4.若完全二叉樹的第6層有10個葉結(jié)點，則該完全二叉樹結(jié)點總數(shù)最多是。A.107B.108C.234D.2355若具有n個頂點e條邊且不帶權(quán)的無向圖采用鄰接矩陣存儲，則鄰接矩陣中零元素的數(shù)目是。A.n+eB.2(n+e)C.n2+2eD.n2-2e6. 對于無向圖G=(V,E)和G2=(V2,E2),若G2是G的生成樹，貝I下面的說法中，錯誤的是。A.G2是G1的連通分量B

3、.G2是G1的子圖C.G2是G1的極小連通子圖，且V=V2D.G2是G的一個無環(huán)子圖7. 在表長為9的有序表中進行折半查找，經(jīng)過3次元素之間的比較以后查找成功的元素分別是。A.第2,4,7,9個元素B.第2,4,7,8個元素C.第1,3,6,8個元素D.第1,4,6,9個元素8. 評價一個“好”的散列函數(shù)的主要指標(biāo)是。A.函數(shù)是否是一個解析式子B.函數(shù)的形式是否簡單C.函數(shù)的取值是否均勻D.函數(shù)的計算是否快9. 若序列(11,12,13,7,8,9,23,4,5)是采用下列排序方法之一得到的第2趟排序后的結(jié)果，則該排序方法只能是。A.泡排序法B.插入排序法C.選擇排序法D.二路歸并排序法210

4、. 根據(jù)(大頂)堆積的定義，序列(shi,deng,an,wang,tang,bai,fang,liu)對應(yīng)的堆積是。A.(tang,wang,fang,shi,deng,bai,an,liu)B.(tang,shi,fang,wang,deng,bai,an,liu)C.(wang,tang,fang,deng,shi,bai,an,liu)D.(wang,tang,fang,liu,shi,bai,an,deng)二、簡答題(本題共20分，每小題各5分)1相對于線性表的順序存儲結(jié)構(gòu)而言，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)有什么優(yōu)點？2若度為m且有n個結(jié)點的樹采用多重鏈表存儲結(jié)構(gòu)，即每個鏈結(jié)點設(shè)置m+1個

5、域，其中有1個數(shù)據(jù)域，m個指針域，則該鏈表中空指針的數(shù)目是多少？這種存儲結(jié)構(gòu)有何利弊？3一般情況下，對一個圖進行遍歷可以得到不同的遍歷序列。若圖采用鄰接表存儲結(jié)構(gòu)，導(dǎo)致遍歷序列不惟一的主要因素有哪些？4若選擇當(dāng)前參加排序的第1個元素作為分界元素，什么情況下，快速排序法的時間效率會退化到簡單排序法的程度？請說明理由。三、綜合題(本題共20分，每小題各5分)1若已知在長度為n的順序表(a,a2,an)的第i個位置(1WiWn+1)插入一個新的數(shù)據(jù)元素的概率pi=(1)2(1)，nnni，則平均插入一個元素時所需要移動元素次數(shù)的期望值(平均次數(shù))是多少？2已知有向圖采用鄰接表存儲，鄰接表如圖3-2所

6、示。請分別寫出其所有可能的拓?fù)湫蛄小D3-23已知對一棵二叉排序樹進行前序遍歷得到的遍歷序列為50,45,35,15,40,46,65,75,70,請畫出該二叉排序樹。4請畫出在圖3-4所示的3階B-樹中依次插入關(guān)鍵字值55和69以后B-樹的狀態(tài)。圖3-40A1 B2 C3 D4 E5 F1 32 441254A407085602050656880903四、算法設(shè)計題（本題20分）已知線性鏈表第1個結(jié)點的指針為1ist，鏈結(jié)點構(gòu)造為datalink，請寫一算法，該算法用盡可能高的時間效率找到鏈表的倒數(shù)第k個結(jié)點。若找到這樣的結(jié)點，算法給出該結(jié)點的地址，否則，算法給出NULL。限制：算法中不得求

7、出鏈表長度，也不允許使用除指針變量和控制變量以外的其他輔助空間。要求：1用文字簡要給出算法的基本思想；（5分）2根據(jù)算法的基本思想寫出相應(yīng)算法。（15分）五、算法設(shè)計題（本題20分）已知哈夫曼樹采用二叉鏈表存儲結(jié)構(gòu)，鏈結(jié)點構(gòu)造為1childdatarchild，其中，葉結(jié)點的data域中存放該葉結(jié)點對應(yīng)的權(quán)值。請寫出計算根結(jié)點指針為T的哈夫曼樹帶權(quán)路徑長度（WPL）的非遞歸算法。要求：1用文字簡要給出算法的基本思想；（5分）2根據(jù)算法的基本思想寫出相應(yīng)算法。（15分）參考答案一、選擇題1B2C3C4A5D6A7C8C9B10D二、簡答題1答：相對于線性表的順序存儲結(jié)構(gòu)而言，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

8、的優(yōu)點在于：首先，在表中進行插入和刪除操作不需要移動其他元素，當(dāng)指針指向合適結(jié)點后只需修改指針就能達到目的；其次，不需要預(yù)先分配存儲空間，而是根據(jù)實際需要進行空間的動態(tài)申請，可使得存儲空間得到充分利用；其三，由于表的容量僅受到可用空間的限制，表的容量擴充相對比較容易。2. 答：整個鏈表一共有nm個指針域，由于除根結(jié)點外，每一個結(jié)點都有一個指針指向它，故鏈表中空的指針域數(shù)目為nxm-（n-1）=nx（m-1）+1個。采用這種存儲結(jié)構(gòu)的優(yōu)點是結(jié)構(gòu)統(tǒng)一，便于操作，缺點是空的指針域較多，造成存儲效率低。3. 答：（1）開始遍歷的頂點的不同；（2）存儲結(jié)構(gòu)的不同，即鄰接表中邊結(jié)點鏈接的次序不同；（3）使

9、用的遍歷方法的不同。4. 答：在待排序的原始序列中元素已經(jīng)按值從小到大排好序的情況下，快速排序法的時間效率會變得很差，因為在排序過程中，每次選取的“分界元素”都是當(dāng)前序列的最小值（最前那個元素），經(jīng)過一趟排序后，將原序列分解成為一個空序列和一個原序列長度僅減1的子序列，這樣，對于長度為n的原始序列，必須經(jīng)過n-1趟排序才能把所有元素定位，而且第i趟排序需要經(jīng)過n-1次元素之間的比較才能為第i個元素定位，因此，總的排序時間達到O（n2）。三、綜合題1+11(1)nipini=(1)2nn+厶+11(1)nini2=(1)2nn+6n(n+l)(2n+1)32n+12拓?fù)湫蛄校?1) ADFBCE

10、(2) ADBCFE(3) ADBFCE3.二叉排序樹4.3階B-樹四、算法設(shè)計題(1)算法的基本思想： 設(shè)置一個指針變量p(初始時指向鏈表的第1個結(jié)點)，然后讓其后移指向鏈表的第k個結(jié)點(不是倒數(shù)第k個結(jié)點)； 再設(shè)置另外一個指針變量r,初始時也指向鏈表的第1個結(jié)點； 利用一個循環(huán)讓p與r同步沿鏈表向后移動；當(dāng)p指向鏈表最后那個結(jié)點時，r指向鏈表的倒數(shù)第k個結(jié)點。顯然，算法的時間開銷主要在第步和第步。若用n表示鏈表中鏈結(jié)點的個數(shù)，對于任意k(lWkWn)，第步要執(zhí)行k-1次，第步要執(zhí)行n-k次，兩個部分總計執(zhí)行n-1次,因此，算法的時間復(fù)雜度為O(n)。(2)算法：LinkListSEARC

11、HNODE(LinkListlist,intk)LinkListp,r;inti;if(list!=NULL&&k>0)p=list;for(i=1;ivk;i+)/*循環(huán)結(jié)束時，p指向鏈表的第k個結(jié)點*/p=p->link;if(p=NULL)printf("鏈表中不存在倒數(shù)第k個結(jié)點！”)returnNULL;r=list;while(p->link!=NULL)p=p->link;r=r->link;/*循環(huán)結(jié)束時，p指向鏈表最后那個結(jié)點，r指向倒數(shù)第k個結(jié)點*/returnr;/*給出鏈表倒數(shù)第k個結(jié)點(r指向的那個結(jié)點)的地址*

12、/504565354670751540ABDFEC6070505540688520656980905五、算法設(shè)計題(1)算法的基本思想：本題宜采用二叉樹的后序遍歷的非遞歸算法完成。在遍歷過程中，訪問一個葉結(jié)點時，將該葉結(jié)點的數(shù)據(jù)域值(該葉結(jié)點的權(quán)值)與該葉結(jié)點的路徑長度(即當(dāng)前棧頂指針值加1)相乘，并進行WPL值的累加。遍歷結(jié)束時便求的該哈夫曼樹的WPL。(2)算法：#defineMaxNum50/*定義二叉樹中結(jié)點最大數(shù)目*/intPOSTORDER_WPL(BTREET)/*T為二叉樹根結(jié)點所在鏈結(jié)點的地址*/BTREESTACK1MaxNum,p=T;intSTACK2MaxNum,flag,top=1;WPL=0;if(T!=NULL)dowhile(p!=NULL)STACKl+top=p;/*當(dāng)前p指結(jié)點的地址進棧*/STACK2top=0;/*標(biāo)志0進棧*/p=p->lchild;/*將p移到其左孩子結(jié)點*/p=STACKltop;flag=STACK2top;/*退棧*/if(flag=0)STACK1+top=p;/*當(dāng)前p指結(jié)