《數(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é)號： 姓名： ZhengKen 題號一二三四五六七八總分得分 得分評卷人一、選擇題（每小題1分， 共6分）1、關(guān)于線性表的說法,下面選項(xiàng)正確的是（B ） A 線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼（除頭、尾元素，直接的） B 線性表是具有n(n=0)個(gè)元素的一個(gè)有限序列 C 線性表就是順序存儲的表 （可以是鏈?zhǔn)酱鎯Y(jié)構(gòu)） D 線性表只能用順序存儲結(jié)構(gòu)實(shí)現(xiàn) （可以是鏈?zhǔn)酱鎯Y(jié)構(gòu)）2、表長為n的順序存儲的線性表，當(dāng)在任何一個(gè)位置上插入或者刪除一個(gè)元素的概率相等時(shí)

2、，刪除一個(gè)元素需要移動元素的平均個(gè)數(shù)為（ A） A (n-1)/2 B n/2 C n D n-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 ） A p-RLink=s; s-LLink=p; p-RLink-LLink=s; s-RLink=p-RLink; B p-RLink=s; p-RLink-LLink=s;s-LLink=p; s-RLink=p-RLink; C s-LLink=p; s-RLink=p-RLink; p-RLink=s; p-RLink-LLink

3、=s; D s-LLink=p; s-RLink=p-RLink; p-RLink-LLink=s; p-RLink=s;4、棧和隊(duì)列都是（ A ） A 限制存取位置的線性結(jié)構(gòu) （都是一種特殊的線性鏈表） B 鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu) （可以順序存儲） C 順序存儲的線性結(jié)構(gòu) （可以鏈?zhǔn)酱鎯Γ?D 限制存取位置的非線性結(jié)構(gòu)（如：樹）5、單循環(huán)鏈表表示的隊(duì)列長度為n，若只設(shè)頭指針，則入隊(duì)的時(shí)間復(fù)雜度為（ A ） A O(n) B O(1) C O(n*n) D O(n*logn) 在隊(duì)尾入隊(duì)，隊(duì)頭出隊(duì)6、一棵含有n個(gè)節(jié)點(diǎn)的k叉樹，可能達(dá)到的最小深度為多少？（ C ） A n-k B n-k+1 C

4、|logkn|+1 D |logkn| 其中|k|表示下取整 得分評卷人三、簡答（共22分）1、對于線性表的兩種存儲結(jié)構(gòu)（順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)），如果線性表基本穩(wěn)定，并且很少進(jìn)行插入和刪除操作，但是要求以最快速度存取線性表中的元素，則應(yīng)選擇哪種存儲結(jié)構(gòu)？試說明理由。（5分）答：選擇順序存儲。因?yàn)轫樞虼鎯梢酝ㄟ^下標(biāo)隨意訪問線性表中的元素，效率較高。而鏈?zhǔn)酱鎯σL問某個(gè)元素是，需要遍歷鏈表來找到這個(gè)元素，效率比較低。選擇順序存儲結(jié)構(gòu)；理由有兩點(diǎn)（1）主要從插入刪除操作在移動元素的個(gè)數(shù)上分析，（2）順序存儲定位塊，可直接定位。2、哈夫曼樹在構(gòu)造時(shí)，首先進(jìn)行初始化存儲空間，結(jié)果如左下圖，當(dāng)構(gòu)造完成

5、后，請?zhí)顚懽詈鬆顟B(tài)表，如右下圖。（6分）（見課本P148）weightParentLchildRchildweightParentLchildRchild123456789101112131415500029000700080001400023000300011000-000-000-000-000-000-000-00012345678910111213141559002914007100081000141200231300390011110081117151234191389291451042156115815212100013143、內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m）提供給兩個(gè)棧

6、s1和s2使用，怎樣分配這部分存儲空間，使得對任一棧，僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢。如何判斷棧滿，棧空，并對兩個(gè)棧的容量進(jìn)行分析。（7分）答：把兩個(gè)棧的棧底分別設(shè)定為空間的兩頭，也就是1，m。其中一個(gè)棧從低地址向高地址增長，另外一個(gè)從高地址往低地址存放。這樣可以保證空間利用更好。空、滿、容量分析將s1,s2棧底分別設(shè)在連續(xù)內(nèi)存空間的兩端，棧頂向內(nèi)存中間進(jìn)發(fā)；注：棧頂=0，或棧頂=m+1當(dāng)|s1.top-s2.top|=1時(shí)，棧滿；當(dāng)一個(gè)棧頂為0，另一個(gè)棧頂為m+1時(shí)，棧空；容量分析：從低地址向高地址增長時(shí)，容量為棧頂top的值；從高地址往低地址存放時(shí)，容量為m+1-（棧頂top的值）。4、設(shè)

7、某二叉樹的前序遍歷序列為：ABCDEFGHI，中序遍歷序列為：BCAEDGHFI。（1）試畫出該二叉樹；（2）畫出該二叉樹后序線索化圖。（3）試畫出該二叉樹對應(yīng)的森林。（10分） （1） （3）（四棵樹）ABCDEFGIH（2）后序序列：CBEHGIFDA體現(xiàn)到圖上便可ABCDEFGIHABCDEFGHI得分評卷人四、閱讀算法（每小題5分，共25分）1. void AE(Stack& S) InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a5=1,5,8,12,15; for(i=0;i5;

8、i+) Push(S,2*ai); while(!StackEmpty(S) coutPop(S)left,c1,c2); c1+; if (BT-left=NULL&BT-right=NULL) c2+; ABC(BT-right,c1,c2); /if 該函數(shù)執(zhí)行的功能是什么？ 答：該函數(shù)的功能是統(tǒng)計(jì)，二叉樹結(jié)點(diǎn)總數(shù)，和葉子結(jié)點(diǎn)總數(shù)。 c1為二叉樹結(jié)點(diǎn)數(shù)，c2為二叉樹中葉子結(jié)點(diǎn)數(shù)3. 在下面的每個(gè)程序段中，假定線性表La的類型為List，e的類型為ElemType,元素類型ElemType為int，并假定每個(gè)程序段是連續(xù)執(zhí)行的。試寫出每個(gè)程序段執(zhí)行后所得到的線性表La。（1）InitLis

9、t(La); Int a=100,26,57,34,79;（1）79 34 57 26 100 For (i=0;i5;i+) ListInsert(La,1,ai); /逆序；（2）ListDelete(La,1,e); /e=79; （2）34 57 26 100 79ListInsert(La,ListLength(La)+1,e); /在最后一個(gè)位置插入e；（3）ClearList(La); For (i=0;i5;i+)（3）100 26 57 34 79 ListInsert(La,i+1,ai); /順序；ListInsert( &L , i , e ) /前插(入) 初始條件:

10、 線性表L 已存在 , 1 i ListLength ( L )+1 。 操作結(jié)果: 在L 中第 i 個(gè)位置之前插入新的 數(shù)據(jù)元 素e , L的長度加1 。ListDelete( &L , i , &e ) /刪除 初始條件: 線性表L 已存在且非空 , 1 i ListLength( L ) 。 操作結(jié)果: 刪除L 的第 i 個(gè)數(shù)據(jù)元素 , 并 用e 返回其值, L的長度減1 。 ClearList ( &L ) /置空 初始條件:線性表L 已存在。 操作結(jié)果:將L重置為空表。4. int Prime(int n) int i=1; int x=(int) sqrt(n); while (+

11、ix) return 1; /不能被2中的數(shù)整除，為素?cái)?shù)； else return 0; /為合數(shù)； (1)指出該算法的功能；(2)該算法的時(shí)間復(fù)雜度是多少？答：（1）求素?cái)?shù)（該算法的功能是判斷n是否為素?cái)?shù)，是返回1，否則返回0） （2）O（）；一個(gè)數(shù)，如果只有1和它本身兩個(gè)因數(shù)，這樣的數(shù)叫做質(zhì)數(shù)，又稱素?cái)?shù)。例如（10以內(nèi)） 2，3，5，7 是質(zhì)數(shù)，而 4，6，8，9 則不是，后者稱為合成數(shù)或合數(shù)。特別聲明一點(diǎn)，1既不是質(zhì)數(shù)也不是合數(shù)。為什么1不是質(zhì)數(shù)呢?因?yàn)槿绻?也算作質(zhì)數(shù)的話,那么在分解質(zhì)因數(shù)時(shí),就可以隨便添上幾個(gè)1了。比如30，分解質(zhì)因數(shù)是2*3*5，因?yàn)榉纸赓|(zhì)因數(shù)是要把一個(gè)數(shù)寫成質(zhì)數(shù)

12、的連乘積，如果把1算作質(zhì)數(shù)的話，那么在這個(gè)算式中，就可以隨便添上幾個(gè)1了，分解質(zhì)因數(shù)也就沒法分解了。從這個(gè)觀點(diǎn)可將整數(shù)分為三種，一種叫質(zhì)數(shù)，一種叫合成數(shù)，還有一個(gè)1。（1不是質(zhì)數(shù)，也不是合數(shù)）。著名的高斯唯一分解定理說，任何一個(gè)整數(shù)?？梢詫懗梢淮|(zhì)數(shù)相乘的積。質(zhì)數(shù)中除2是偶數(shù)外，其他都是奇數(shù)。5. 寫出下述算法A的功能： 其中BiTree定義如下: Typedef struct BiTNode TElemType data; struct BiTNode *LChild, *RChild;BiTNode, *BiTree;Status A(BiTree T) Queue Q; InitQueu

13、e(Q); ENQueue(Q,T); While(not QueueEmpty(Q) DeQueue(Q,e); If(e=NULL) break; Else Print(e.data);ENQueue(Q,e.LChild); ENQueue(Q.e.RChild); 答：層次遍歷二叉樹的非遞歸算法 得分評卷人五、算法填空（每空1分，共9分）1堆分配存儲方式下，串連接函數(shù)。typedef struct char * ch； int len； HString； HString *s， t; Status StrCat(s， t) /* 將串t連接在串s的后面 */ int i; char *

14、temp; temp=(char*)malloc(s-len+t.len); if (temp=NULL) return(0); for (i=0; ilen ;i+) tempi=s-chi; for ( i=s-len ;ilen + t.len;i+) tempi=t.chi-s-len; s-len+=t.len; free(s-ch); s-ch=temp; return(1); 2向單鏈表的末尾添加一個(gè)元素的算法。 LNode是一個(gè)包含（data，Next）的結(jié)構(gòu)體Void InsertRear(LNode*& HL,const ElemType& item)LNode* newp

15、tr;newptr=new LNode;If (_newptr=NULL_)cerrMemory allocation failare!data=item; _newptr-next=NULL;if (HL=NULL) HL=_newptr_;elseLNode* P=HL;While (P-next!=NULL) _p=p-next_;p-next=newptr; 得分評卷人六、編寫算法（每小題10分，共20分）1編寫算法，將一單鏈表逆轉(zhuǎn)。要求逆轉(zhuǎn)在原鏈表上進(jìn)行，不允許重新構(gòu)造一個(gè)鏈表（可以申明臨時(shí)變量、指針）。該鏈表帶頭節(jié)點(diǎn)、頭節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)的結(jié)構(gòu)定義如下typedef struct LN

16、ode ElemType data; Struct LNode* next;*List, LNode;函數(shù)定義：void invert(List & L)void invert (List & L)/鏈表的就地逆置;帶頭結(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)。/ invert本算法的思想：逐個(gè)地把L的當(dāng)前元素q插入新的鏈表頭部，將元素

17、指針反向。2編寫算法計(jì)算給定二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。 其中樹節(jié)點(diǎn)定義如下 typedef struct BiTNode DataType data; Struct BiTNode *LChild, * RChild; BiTNode, *BiTree; 函數(shù)定義：CountLeaf (BiTree T, int & LeafNum)void CountLeaf (BiTree T, int& LeafNum) if ( T ) if (!T-lchild)& (!T-rchild) LeafNum +; / 對葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( T-lchild, LeafNum); / 求左子

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