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

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

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

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

求右子樹葉子數(shù)算法的基本思想:先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點，并計數(shù)。由此，需在遍歷算法中增添一個“計數(shù)”的參數(shù)，并將算法中“訪問結(jié)點”的操作改為:若是葉子，則計數(shù)器增1。得分評卷人七、計算(每小題4分，共12分)1、對比f(n)和g(n),當(dāng)n接近無窮時，哪個函數(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個節(jié)點的滿二叉樹的葉子節(jié)點的個數(shù)是多少?解：

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