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

蝸牛在線更多免費(fèi)學(xué)習(xí)資料等待您的光臨！蝸牛在線更多免費(fèi)學(xué)習(xí)資料等待您的光臨！2009—2010學(xué)年“算法與數(shù)據(jù)結(jié)構(gòu)(I)”期末試題與參考答案一、單項(xiàng)選擇題（本題共20分，每小題各分）1．一個(gè)完整算法應(yīng)該具備的特性之一是有窮性，這里的有窮性是指。A．算法必須寫得簡(jiǎn)明扼要B．算法必須在有限的時(shí)間內(nèi)能夠結(jié)束C．算法的每一步必須有清晰明確的含義2．datalinkqp指結(jié)點(diǎn)的的直接前qps所指結(jié)點(diǎn)的過程是依次執(zhí)行A．s->link=p->link;p->link=s;B．p->link=s->link;s->link=p;C．q->link=s;s->link=p;D．p->link=s;s->link=q;下列A．判斷堆棧是否為空C．D．將堆棧置為空棧10個(gè)葉結(jié)點(diǎn)，則該完全二叉樹結(jié)點(diǎn)總數(shù)最多是。A．107B．108C．234D．235ne元素的數(shù)目是。A．n+eB．2(n+e)C．n2+2eD．n2-2eG1=(V1,E1)和G2=(V2,E2)，若G2是錯(cuò)誤的是。A．G2是G1的連通分量B．G2是G1的子圖C．G2是G1的極小連通子圖，且V1=V2D．G2是G1的一個(gè)無環(huán)子圖93的元素分別是。A．第2,4,7,9個(gè)元素2,4,7,8個(gè)元素C．第1,3,6,8個(gè)元素D1,4,6,9個(gè)元素8．評(píng)A．函數(shù)是否是一個(gè)解析式子BCD．函數(shù)的計(jì)算是否快(11,12,13,7,8,9,23,4,5)2果，則該排序方法只能是。A．泡排序法B．插入排序法C．選擇排序法D．二路歸并排序法2)(shi,deng,an,wang,tang,bai,fang,liu)是。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)二、簡(jiǎn)答題（本題共20分，每小題各5分）相對(duì)于線性表的順序存儲(chǔ)結(jié)構(gòu)而言，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有什么優(yōu)點(diǎn)？若度為且有nm+1個(gè)域，其中1個(gè)數(shù)據(jù)域個(gè) 指針域，則該鏈表中空指針的數(shù)目是多少？這存儲(chǔ)結(jié)構(gòu)有何利弊？3儲(chǔ)結(jié)構(gòu)，導(dǎo)致遍歷序列不惟一的主要因素有哪些？4．若選擇當(dāng)前參加排序的第1個(gè)元素作為分界元素，什么情況下，快速排序法的時(shí)間效率會(huì)退化到簡(jiǎn)單排序法的程度？請(qǐng)說明理由。三、綜合題（本題共20分，每小題各5分）1．若已知在長(zhǎng)度為n的順序表(a1,a2,?,an)的第i個(gè)位置(1≤i≤n+1)插入一個(gè)新的數(shù)據(jù)元素的概率pi=(1)2(1)nni(均次數(shù)是多少？2．已知有向圖采用鄰接表存儲(chǔ)，鄰接表如圖3-2所示。請(qǐng)分別寫出其所有可能的拓?fù)湫蛄小D3-23．已知對(duì)一棵二叉排序樹進(jìn)行前序遍歷得到的遍歷序列為50,45,35,15,40,46,65,75,70，請(qǐng)畫出該二叉排序樹。4．請(qǐng)畫出在圖3-4所示的3階B-樹中依次插入關(guān)鍵字值55和69以后B-樹的狀態(tài)。圖3-40ABCDEF132441254^^^^^^407085602050656880903四、算法設(shè)計(jì)題（本題20分）listdatalink，請(qǐng)寫一算法，該算法用盡可能高的時(shí)間效率找到鏈表的倒數(shù)第k個(gè)結(jié)點(diǎn)。若找到這樣的結(jié)點(diǎn)，算法給出該結(jié)點(diǎn)的地址，否則，算法給出NULL。限制：算法中不得求出鏈表長(zhǎng)度，也不允許使用除指針變量和控制變量以外的其他輔助空間。要求：分）根據(jù)算法的基本思想寫出相應(yīng)算法。分）五、算法設(shè)計(jì)題（本題20分）lchilddatarchild，其中，葉結(jié)點(diǎn)的data域中存放該葉結(jié)點(diǎn)對(duì)應(yīng)的權(quán)值。請(qǐng)寫出計(jì)算根結(jié)點(diǎn)指針為T的哈夫曼樹帶權(quán)路徑長(zhǎng)度(WPL)的非遞歸算法。要求：分）根據(jù)算法的基本思想寫出相應(yīng)算法。分）參考答案一、選擇題1．B2．C3．C4．A5．D6．A7．C8．C9．B10．D二、簡(jiǎn)答題答：相對(duì)于線性表的順序存儲(chǔ)結(jié)構(gòu)而言，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)在于：首先，在表中進(jìn)行插入和刪除操作不需要移動(dòng)其他元素答nm-(n-1)=n(m-1)+1個(gè)。采用這種存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是結(jié)構(gòu)統(tǒng)一，便于操作，缺點(diǎn)是空的指針域較多，造成存儲(chǔ)效率低。答：（1）開始遍歷的頂點(diǎn)的不同；存儲(chǔ)結(jié)構(gòu)的不同，即鄰接表中邊結(jié)點(diǎn)鏈接的次序不同；使用的遍歷方法的不同。答：在待排序的原始序列中元素已經(jīng)按值從小到大排好序的情況下，快速排序法的()1n-1趟排序才能把所有元素定位，而且第in-1i個(gè)元素定位，因此，總的排序時(shí)間達(dá)到O(n2)。4三、綜合題．1 ．11(1)nipini=(1)2nn11(1)nini2=(1)2nn6n(n1)(2n1)=32n12．拓?fù)湫蛄校篈DFBCEADBCFEADBFCE3階B-四、算法設(shè)計(jì)題算法的基本思想：①設(shè)置一個(gè)指針變量p（初始時(shí)指向鏈表的第1個(gè)結(jié)點(diǎn)），然后讓其后移指向鏈表的第k個(gè)結(jié)點(diǎn)（不是倒數(shù)第k個(gè)結(jié)點(diǎn)）；②再設(shè)置另外一個(gè)指針變量r，初始時(shí)也指向鏈表的第1個(gè)結(jié)點(diǎn)；③利用一個(gè)循環(huán)讓p與r同步沿鏈表向后移動(dòng)；當(dāng)p指向鏈表最后那個(gè)結(jié)點(diǎn)時(shí)，r指向鏈表的倒數(shù)第k個(gè)結(jié)點(diǎn)。顯然，算法的時(shí)間開銷主要在第①步和第③步。若用n表示鏈表中鏈結(jié)點(diǎn)的個(gè)數(shù)，對(duì)于任意k（1≤k≤n），k-1n-kn-1因此，算法的時(shí)間復(fù)雜度為(n)。算法：LinkListSEARCHNODE(LinkListlist,intk){LinkListp,r;inti;if(list!=NULL&&k>0){p=list;for(i=1;i<k;i++){/*k*/p=p->link;if(p==NULL){printf("鏈表中不存在倒數(shù)第k個(gè)結(jié)點(diǎn)！")returnNULL;}}r=list;while(p->link!=NULL){p=p->link;r=r->link;}/*循環(huán)結(jié)束時(shí)，p指向鏈表最后那個(gè)結(jié)點(diǎn)，r指向倒數(shù)第k個(gè)結(jié)點(diǎn)*/returnr;/*給出鏈表倒數(shù)第k個(gè)結(jié)點(diǎn)(r指向的那個(gè)結(jié)點(diǎn))的地址*/}}504565354670751540ABDEC6070505540688520656980905五、算法設(shè)計(jì)題算法的基本思想：本題宜采用二叉樹的后序遍歷的非遞歸算法完成。在遍歷過程中，訪問一個(gè)葉結(jié)點(diǎn)時(shí)，將該葉結(jié)點(diǎn)的數(shù)據(jù)域值(該葉結(jié)點(diǎn)的權(quán)值)與該葉結(jié)點(diǎn)的路徑長(zhǎng)度(即當(dāng)前棧頂指針值加1)相乘，并進(jìn)行WPL值的累加。遍歷結(jié)束時(shí)便求的該哈夫曼樹的WPL。算法：#defineMaxNum50/*定義二叉樹中結(jié)點(diǎn)最大數(shù)目*/intPOSTORDER_WPL(BTREET){/*T為二叉樹根結(jié)點(diǎn)所在鏈結(jié)點(diǎn)的地址*/BTREESTACK1[MaxNum],p=T;intSTACK2[MaxNum],flag,top=1;WPL=0;if(T!=NULL)do{while(p!=NULL){STACK1[++top]=p;/*當(dāng)前p*/STACK2[top]=0;/*標(biāo)志0進(jìn)棧*/p=p>lchild;/*將p}p=STACK1[top];flag=STACK2[top];/*退棧*/if(flag==0){STACK1[++top]=p;