《數(shù)據(jù)結(jié)構(gòu)》期中試題(有答案)資料1

福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院

2009--2010學(xué)年度上學(xué)期08電信

《數(shù)據(jù)結(jié)構(gòu)》期中試題試卷類別：閉卷考試時(shí)間：90分鐘專業(yè)：學(xué)號(hào)：姓名：ZhengKen題號(hào)二三四五六七八總分得分得分評(píng)卷人一、選擇題（每小題1分，共6分）i關(guān)于線性表的說法，下面選項(xiàng)正確的是（B）A線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼（除頭、尾元素，直接的）B線性表是具有n（n>=0）個(gè)元素的一個(gè)有限序列C線性表就是順序存儲(chǔ)的表（可以是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）D線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)（可以是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）2、表長為n的順序存儲(chǔ)的線性表，當(dāng)在任何一個(gè)位置上插入或者刪除一個(gè)元素的概率相等時(shí)，刪除一個(gè)元素需要移動(dòng)元素的平均個(gè)數(shù)為（A）A（n-1）/2Bn/2CnDn-13、設(shè)雙向循環(huán)鏈表中節(jié)點(diǎn)的結(jié)構(gòu)為（data,LLink,RLink），且不帶頭節(jié)點(diǎn)。若想在指針p所指節(jié)點(diǎn)之后插入指針s所指節(jié)點(diǎn)，則應(yīng)執(zhí)行下列哪一個(gè)操作？（D）Ap->RLink=s;s->LLink=p;p->RLink->LLink=s;s->RLink=p->RLink;Bp->RLink=s;p->RLink->LLink=s;s->LLink=p;s->RLink=p->RLink;Cs->LLink=p;s->RLink=p->RLink;p->RLink=s;p->RLink->LLink=s;Ds->LLink=p;s->RLink=p->RLink;p->RLink->LLink=s;p->RLink=s;4、棧和隊(duì)列都是（A）A限制存取位置的線性結(jié)構(gòu)（都是一種特殊的線性鏈表）B鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)（可以順序存儲(chǔ)）C順序存儲(chǔ)的線性結(jié)構(gòu)（可以鏈?zhǔn)酱鎯?chǔ)）D限制存取位置的非線性結(jié)構(gòu)（如：樹）5、單循環(huán)鏈表表示的隊(duì)列長度為n，若只設(shè)頭指針，則入隊(duì)的時(shí)間復(fù)雜度為（AAO（n）BO（1）CO（n*n）DO（n*logn）在隊(duì)尾入隊(duì)，隊(duì)頭出隊(duì)（共9頁第-1-頁）（共（共9頁第--頁)得分評(píng)卷人六、編寫算法(每小題10分，共20分)i編寫算法，將一單鏈表逆轉(zhuǎn)。要求逆轉(zhuǎn)在原鏈表上進(jìn)行，不允許重新構(gòu)造一個(gè)鏈表(可以申明臨時(shí)變量、指針)。該鏈表帶頭節(jié)點(diǎn)、頭節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)的結(jié)構(gòu)定義如下typedefstructLNode{ElemTypedata;StructLNode*next;}*List,LNode;函數(shù)定義：voidinvert(List&L)void()〃鏈表的就地逆置;帶頭結(jié)點(diǎn)的單鏈表；{p=L->next;q=p->next;s=q->next;p->next=NULL;while(s!=NULL){q->next=p;p=q;//p為新表表頭結(jié)點(diǎn)；q=s;s=s->next;〃把L的元素逐個(gè)插入新表表頭}q->next=p;L->next=q;〃將頭結(jié)點(diǎn)指向最后一個(gè)結(jié)點(diǎn)。}//本算法的思想：逐個(gè)地把的當(dāng)前元素插入新的鏈表頭部，將元素指針反向。2.編寫算法計(jì)算給定二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。其中樹節(jié)點(diǎn)定義如下typedefstructBiTNode{DataTypedata;StructBiTNode*LChild,*RChild;}BiTNode,*BiTree;函數(shù)定義：CountLeaf(BiTreeT,int&LeafNum)對(duì)葉子結(jié)點(diǎn)計(jì)數(shù)求左子樹葉子數(shù)

求右子樹葉子數(shù)算法的基本思想:先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問結(jié)點(diǎn)”的操作改為:若是葉子，則計(jì)數(shù)器增1。得分評(píng)卷人七、計(jì)算(每小題4分，共12分)1、對(duì)比f(n)和g(n),當(dāng)n接近無窮時(shí)，哪個(gè)函數(shù)增長更快。Af(n)=(ln(n!)+5)2g(n)=13n2.5g(n)增長速度快Bf(n)=2(n*n*n)+(2n)2g(n)=n(n*n)+n5F(n)增長速度快2、具有n個(gè)節(jié)點(diǎn)的滿二叉樹的葉子節(jié)點(diǎn)的個(gè)數(shù)是多少?解：

法一：設(shè)葉子結(jié)點(diǎn)數(shù)為、，非葉子結(jié)點(diǎn)數(shù)為n1；2n1+1=n2n1+1=n0+n1則可得n0=n1+1n=no+no-1所以葉子結(jié)點(diǎn)個(gè)數(shù)為(n+1)/2.法二：設(shè)該滿二叉樹高度為h,則總的節(jié)點(diǎn)個(gè)數(shù)為N=1+2+4+…+2h-1=2*2h-1-1由于滿二叉樹中葉子節(jié)點(diǎn)集中在最底層，所以該滿二叉樹葉子個(gè)數(shù)為2h-1=(n+1)/2。3、試寫出遞歸函數(shù)F(n)的遞歸算法，并畫出F(