《數(shù)據(jù)結構》期中試題(有答案)

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

2、，刪除一個元素需要移動元素的平均個數(shù)為（ A） A (n-1)/2 B n/2 C n D n-13、設雙向循環(huán)鏈表中節(jié)點的結構為(data,LLink,RLink)，且不帶頭節(jié)點。若想在指針p所指節(jié)點之后插入指針s所指節(jié)點，則應執(zhí)行下列哪一個操作？（ 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、棧和隊列都是（ A ） A 限制存取位置的線性結構 （都是一種特殊的線性鏈表） B 鏈式存儲的非線性結構 （可以順序存儲） C 順序存儲的線性結構 （可以鏈式存儲） D 限制存取位置的非線性結構（如：樹）5、單循環(huán)鏈表表示的隊列長度為n，若只設頭指針，則入隊的時間復雜度為（ A ） A O(n) B O(1) C O(n*n) D O(n*logn) 在隊尾入隊，隊頭出隊6、一棵含有n個節(jié)點的k叉樹，可能達到的最小深度為多少？（ C ） A n-k B n-k+1 C

4、|logkn|+1 D |logkn| 其中|k|表示下取整 得分評卷人三、簡答（共22分）1、對于線性表的兩種存儲結構（順序存儲和鏈式存儲結構），如果線性表基本穩(wěn)定，并且很少進行插入和刪除操作，但是要求以最快速度存取線性表中的元素，則應選擇哪種存儲結構？試說明理由。（5分）答：選擇順序存儲。因為順序存儲可以通過下標隨意訪問線性表中的元素，效率較高。而鏈式存儲要訪問某個元素是，需要遍歷鏈表來找到這個元素，效率比較低。選擇順序存儲結構；理由有兩點（1）主要從插入刪除操作在移動元素的個數(shù)上分析，（2）順序存儲定位塊，可直接定位。2、哈夫曼樹在構造時，首先進行初始化存儲空間，結果如左下圖，當構造完成

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

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

7、某二叉樹的前序遍歷序列為：ABCDEFGHI，中序遍歷序列為：BCAEDGHFI。（1）試畫出該二叉樹；（2）畫出該二叉樹后序線索化圖。（3）試畫出該二叉樹對應的森林。（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)計，二叉樹結點總數(shù)，和葉子結點總數(shù)。 c1為二叉樹結點數(shù)，c2為二叉樹中葉子結點數(shù)3. 在下面的每個程序段中，假定線性表La的類型為List，e的類型為ElemType,元素類型ElemType為int，并假定每個程序段是連續(xù)執(zhí)行的。試寫出每個程序段執(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); /在最后一個位置插入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 。 操作結果: 在L 中第 i 個位置之前插入新的 數(shù)據(jù)元 素e , L的長度加1 。ListDelete( &L , i , &e ) /刪除 初始條件: 線性表L 已存在且非空 , 1 i ListLength( L ) 。 操作結果: 刪除L 的第 i 個數(shù)據(jù)元素 , 并 用e 返回其值, L的長度減1 。 ClearList ( &L ) /置空 初始條件:線性表L 已存在。 操作結果:將L重置為空表。4. int Prime(int n) int i=1; int x=(int) sqrt(n); while (+

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

12、的連乘積，如果把1算作質(zhì)數(shù)的話，那么在這個算式中，就可以隨便添上幾個1了，分解質(zhì)因數(shù)也就沒法分解了。從這個觀點可將整數(shù)分為三種，一種叫質(zhì)數(shù)，一種叫合成數(shù)，還有一個1。（1不是質(zhì)數(shù)，也不是合數(shù)）。著名的高斯唯一分解定理說，任何一個整數(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向單鏈表的末尾添加一個元素的算法。 LNode是一個包含（data，Next）的結構體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編寫算法，將一單鏈表逆轉。要求逆轉在原鏈表上進行，不允許重新構造一個鏈表（可以申明臨時變量、指針）。該鏈表帶頭節(jié)點、頭節(jié)點和數(shù)據(jù)節(jié)點的結構定義如下typedef struct LN

16、ode ElemType data; Struct LNode* next;*List, LNode;函數(shù)定義：void invert(List & L)void invert (List & L)/鏈表的就地逆置;帶頭結點的單鏈表；p=L-next; q=p-next; s=q-next; p-next=NULL;while(s!=NULL)q-next=p; p=q; / p為新表表頭結點;q=s; s=s-next; /把L的元素逐個插入新表表頭q-next=p; L-next=q; /將頭結點指向最后一個結點。/ invert本算法的思想：逐個地把L的當前元素q插入新的鏈表頭部，將元素

17、指針反向。2編寫算法計算給定二叉樹中葉結點的個數(shù)。 其中樹節(jié)點定義如下 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 +; / 對葉子結點計數(shù) CountLeaf( T-lchild, LeafNum); / 求左子

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