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

1、福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院2009-2010學(xué)年度上學(xué)期08電信數(shù)據(jù)結(jié)構(gòu)期中試題試卷類(lèi)別：閉卷 考試時(shí)間：90分鐘 專(zhuān)業(yè)： 學(xué)號(hào)： 姓名： ZhengKen 題號(hào)一二三四五六七八總分得分 得分評(píng)卷人一、選擇題（每小題1分， 共6分）1、關(guān)于線(xiàn)性表的說(shuō)法,下面選項(xiàng)正確的是（B ） A 線(xiàn)性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼（除頭、尾元素，直接的） B 線(xiàn)性表是具有n(n=0)個(gè)元素的一個(gè)有限序列 C 線(xiàn)性表就是順序存儲(chǔ)的表 （可以是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)） D 線(xiàn)性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn) （可以是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）2、表長(zhǎng)為n的順序存儲(chǔ)的線(xiàn)性表，當(dāng)在任何一個(gè)位置上插入或者刪除一個(gè)元素的概率相等時(shí)

2、，刪除一個(gè)元素需要移動(dòng)元素的平均個(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 限制存取位置的線(xiàn)性結(jié)構(gòu) （都是一種特殊的線(xiàn)性鏈表） B 鏈?zhǔn)酱鎯?chǔ)的非線(xiàn)性結(jié)構(gòu) （可以順序存儲(chǔ)） C 順序存儲(chǔ)的線(xiàn)性結(jié)構(gòu) （可以鏈?zhǔn)酱鎯?chǔ)） D 限制存取位置的非線(xiàn)性結(jié)構(gòu)（如：樹(shù)）5、單循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為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叉樹(shù)，可能達(dá)到的最小深度為多少？（ C ） A n-k B n-k+1 C

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

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

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

7、某二叉樹(shù)的前序遍歷序列為：ABCDEFGHI，中序遍歷序列為：BCAEDGHFI。（1）試畫(huà)出該二叉樹(shù)；（2）畫(huà)出該二叉樹(shù)后序線(xiàn)索化圖。（3）試畫(huà)出該二叉樹(shù)對(duì)應(yīng)的森林。（10分） （1） （3）（四棵樹(shù)）ABCDEFGIH（2）后序序列：CBEHGIFDA體現(xiàn)到圖上便可ABCDEFGIHABCDEFGHI得分評(píng)卷人四、閱讀算法（每小題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ì)，二叉樹(shù)結(jié)點(diǎn)總數(shù)，和葉子結(jié)點(diǎn)總數(shù)。 c1為二叉樹(shù)結(jié)點(diǎn)數(shù)，c2為二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)3. 在下面的每個(gè)程序段中，假定線(xiàn)性表La的類(lèi)型為L(zhǎng)ist，e的類(lèi)型為ElemType,元素類(lèi)型ElemType為int，并假定每個(gè)程序段是連續(xù)執(zhí)行的。試寫(xiě)出每個(gè)程序段執(zhí)行后所得到的線(xiàn)性表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、 線(xiàn)性表L 已存在 , 1 i ListLength ( L )+1 。 操作結(jié)果: 在L 中第 i 個(gè)位置之前插入新的 數(shù)據(jù)元 素e , L的長(zhǎng)度加1 。ListDelete( &L , i , &e ) /刪除 初始條件: 線(xiàn)性表L 已存在且非空 , 1 i ListLength( L ) 。 操作結(jié)果: 刪除L 的第 i 個(gè)數(shù)據(jù)元素 , 并 用e 返回其值, L的長(zhǎng)度減1 。 ClearList ( &L ) /置空 初始條件:線(xiàn)性表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ù)，又稱(chēng)素?cái)?shù)。例如（10以?xún)?nèi)） 2，3，5，7 是質(zhì)數(shù)，而 4，6，8，9 則不是，后者稱(chēng)為合成數(shù)或合數(shù)。特別聲明一點(diǎn)，1既不是質(zhì)數(shù)也不是合數(shù)。為什么1不是質(zhì)數(shù)呢?因?yàn)槿绻?也算作質(zhì)數(shù)的話(huà),那么在分解質(zhì)因數(shù)時(shí),就可以隨便添上幾個(gè)1了。比如30，分解質(zhì)因數(shù)是2*3*5，因?yàn)榉纸赓|(zhì)因數(shù)是要把一個(gè)數(shù)寫(xiě)成質(zhì)數(shù)

12、的連乘積，如果把1算作質(zhì)數(shù)的話(huà)，那么在這個(gè)算式中，就可以隨便添上幾個(gè)1了，分解質(zhì)因數(shù)也就沒(méi)法分解了。從這個(gè)觀點(diǎn)可將整數(shù)分為三種，一種叫質(zhì)數(shù)，一種叫合成數(shù)，還有一個(gè)1。（1不是質(zhì)數(shù)，也不是合數(shù)）。著名的高斯唯一分解定理說(shuō)，任何一個(gè)整數(shù)?？梢詫?xiě)成一串質(zhì)數(shù)相乘的積。質(zhì)數(shù)中除2是偶數(shù)外，其他都是奇數(shù)。5. 寫(xiě)出下述算法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); 答：層次遍歷二叉樹(shù)的非遞歸算法 得分評(píng)卷人五、算法填空（每空1分，共9分）1堆分配存儲(chǔ)方式下，串連接函數(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; 得分評(píng)卷人六、編寫(xiě)算法（每小題10分，共20分）1編寫(xiě)算法，將一單鏈表逆轉(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、指針?lè)聪颉?編寫(xiě)算法計(jì)算給定二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)。 其中樹(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 +; / 對(duì)葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( T-lchild, LeafNum); / 求左子

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