X南大學(xué)2010-2011數(shù)據(jù)結(jié)構(gòu)期末試卷

1、X南大學(xué)2010-2011學(xué)年度第1學(xué)期試卷科目：數(shù)據(jù)結(jié)構(gòu)試題 B姓名： 學(xué) 號： 學(xué)院： 專業(yè)班級： 成績登記表（由閱卷教師用紅色筆填寫）大題號一二三四五總分得分 閱卷教師： 201 年 月 日得分評卷人 一、選擇題（共30分，每小題2分）1.在一個長度為n的單鏈表的第i（0=inext=NULL C. head-next=head D. head!=NULL4.若某線性表最常用的操作是在最后一個元素之后插入一個元素和刪除進(jìn)入表中的最后一個元素，則采用（ ）存儲方式最節(jié)省運(yùn)算時間和存儲空間。A.單鏈表 B.僅有頭指針的單循環(huán)鏈表C.雙向鏈表 D.有頭尾指針的單循環(huán)鏈表5.設(shè)有一個順序棧S，元

2、素a b c d e f依次進(jìn)棧，如果6個元素出棧的順序是b d c f e a，則棧的容量至少應(yīng)該是（）A.2 B.3 C.5 D.66向一個棧頂指針為top的帶頭結(jié)點(diǎn)的非空的鏈棧中刪除結(jié)點(diǎn)，則其操作步驟是（）A.top-next=s; B.s-next=top-next;top-next=s; free(s)C. s = top;top= top-next;free(s) D. s = top-next;top= top-next;free(s)7. 以下為平衡二叉排序樹的查找算法, 假設(shè)表長為N，則算法的時間復(fù)雜度為（ ）A）O（1） B） O（N） C） O（N*N） D） O（log

3、2 N）bitree *search_fsortree(t, key)bitree *t;keytype key; while(t!=NULL) if(t-data=key)return(t);if(t-datakey)t=t-lchild;else t=t-rchild;return(NULL);/* SEARCH_FSORTTREE */8. 在解決計算機(jī)主機(jī)與打印機(jī)間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個（）結(jié)構(gòu)A、數(shù)組B、線性表C、堆棧D、隊列9. 一棵有124個葉結(jié)點(diǎn)的完全二叉樹，最多有（

4、 ）個結(jié)點(diǎn)A、247B、248C、249D、25110.一棵非空的二叉樹的前序遍歷序列和后序遍歷序列正好相同，則該二叉樹一定滿足（）A.所有的結(jié)點(diǎn)均無左孩子 B.所有的結(jié)點(diǎn)均無右孩子C.只有一個孤立的結(jié)點(diǎn) D.是任意一棵二叉樹11. 已知字符A、B、C、D的使用頻率（權(quán)值）分別為22，7，9，27。對其進(jìn)行HUFFMAN編碼，各字符對應(yīng)的編碼為（ ）A） A（001）B（100）C（110） D（0）B） A（100） B（101）C（0） D（11）C） A（11） B（100）C（111） D（0）D） A（100）B（1011）C（11） D（0）12.在具有N個頂點(diǎn)和N條邊的無向圖的鄰

5、接表存儲中，鄰接表中結(jié)點(diǎn)的總數(shù)為（ ）A.N B.2N C.3N D.4N13. 由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹( )A. 其形態(tài)不一定相同，但平均查找長度相同B. 其形態(tài)不一定相同，平均查找長度也不一定相同C. 其形態(tài)均相同，但平均查找長度不一定相同D. 其形態(tài)均相同，平均查找長度也都相同D.以上都不是14.設(shè)有1000個基本有序的元素，希望用最快的速度挑選出其中前10個最大的元素，最后選用（）排序法。A.冒泡排序 B.快速排序 C. 直接插入排序 D. 歸并排序15.對序列（15，9，7，8，20，-1，4）進(jìn)行排序，進(jìn)行一趟排序后，數(shù)據(jù)的排列變?yōu)椋?，9，7，8，-1，15，20）

6、，則采用的是（）排序。A.選擇排序 B.快速排序 C.希爾排序 D.冒泡排序得分評卷人二、填空題（20分，每空2分）16.棧的邏輯特點(diǎn)是_，隊列的邏輯特點(diǎn)是 _。17、將含100個結(jié)點(diǎn)的完全二叉樹從根開始，每層從左到右依次對結(jié)點(diǎn)編號，根結(jié)點(diǎn)的編號為1，則編號為31的結(jié)點(diǎn)的雙親的編號為_，其右子的編號為_。18、設(shè)樹F由T1，T2,T3三棵子樹組成，與F對應(yīng)的二叉樹為B。已知T1,T2,T3的結(jié)點(diǎn)數(shù)分別為x，y，z，則該二叉樹B的左子樹中有_個結(jié)點(diǎn)，右子樹中有_個結(jié)點(diǎn)。（x-1,y+z）19、設(shè)鏈隊列的隊頭指針為front，隊尾指針為rear，隊列為空的條件是_，隊列為滿的條件是_。20. 在有

7、向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的_。21. 堆是一個鍵值序列 (k1,k2,kn)，對i=1,2, ，滿足_。（kik2i且kik2i+1 (2i+1n)）得分評卷人三、應(yīng)用題（共25分）22對下圖所示的樹，分別寫出其先序和后序序列，并轉(zhuǎn)換成對應(yīng)的二叉樹。（5分）先序：A B E C F G D H KI J后序：E B F G C K H I J D A 23.對下面給定的圖用克魯斯卡爾算法（從頂點(diǎn)2開始）求最小生成樹，要求畫出最小生成樹，并按構(gòu)造過程給出邊的序列。（5分）（見圖1）克魯斯卡爾算法：（0，2），（3，5），（1，4），（2，5），（1，2）普利姆算法： （2，0），（

8、2，5），（5，3），（2，1），（1，4）圖1 24.設(shè)給定的排序碼序列為（72，73，71，23，94，16，05，68），請寫出快速排序過程中每趟排序的結(jié)果。（5分）68 05 71 23 167294 73 16 05 2368 71 7294 7305162368 71 7294 73 05 16 23 68 71 72 73 9425.假定一個待存儲的線性表為 22,41,53,46,30,13,1,67 ,散列地址空間為HT8，散列函數(shù)為H（k）=key%8,若采用線性探查法處理沖突，請計算每個元素的散列地址（5分）。畫出最后得到的散列表（2分），并求出平均查找長度（3分）。（共

9、10分）0 1 2 3 4 5 6 7 8 比較次數(shù) 3 1 6 3 2 1 1 2224153463013167 平均查找長度ASL=1/8* (3+1+6+3+2+1+1+2)=19/8 得分評卷人四、算法測試（分）26. 代碼如下：（6分）下面是在遞增有序表Rn中的下標(biāo)在low到high范圍內(nèi)的區(qū)域查找鍵值為K的元素的二分查找的遞歸算法，請在劃線處填上適當(dāng)?shù)膬?nèi)容。/* 有序表R進(jìn)行二分查找遞歸算法 */ int halfsearch（R, low, high, k） int low, high ,k; /* 在順序表R上進(jìn)行二分查找, k為給定的關(guān)鍵字值 */ int; rectype

10、R; int mid; if （lowhigh） _ ; /* 檢索失敗 */ else mid=(high+low)/2; /* 設(shè)置查找的中間位置mid */ switch（k） case Rmid.keyk: return（halfsearch（R, _）; break; case Rmid.key=k: return（mid）; break; /* SWITCH */ /* ELSE */ /* HALFSEARCH */ 見書上第318頁：0；mid+1,hiht,k; low,mid-1,k27、設(shè)h是帶表頭結(jié)點(diǎn)的單鏈表的頭指針，請設(shè)計一個逆置這個單鏈表的程序。即原鏈表為(a1,a

11、2,a3an)，逆置后變?yōu)? an,an-1a2,a1)。（6分）單鏈表結(jié)點(diǎn)結(jié)構(gòu)為：typedef struct node int data; _ *link LNode; （2分） （ struct node ）void invert(LNode *h) LNode *s,*p; p=h-link; h-link=_;（2分） （0） （ h-next=NULL） while(p!=NULL) s=p; p=p-link; _（2分） （S-next=H-next;） h-link=s;10得分評卷人五、編寫算法（1分）28、試編寫算法，在一個循環(huán)單鏈表中刪除結(jié)點(diǎn)S，且要求函數(shù)返回該鏈表的一

12、個入口指針。 假設(shè)表長大于1，且表中即無頭結(jié)點(diǎn)，也無頭指針，函數(shù)原型為void delete_xyz(NODE*S)。（分）解一：void delete xyz(NODE *S) NODE *f;f=s.next;while(f.next!=s);/找到S點(diǎn)的前一結(jié)點(diǎn)f=f.next;f.next=s.next;free(s);解二：解一的問題是刪除結(jié)點(diǎn)s后，沒有再指向鏈表的指針了。NODE *delete xyz(NODE *S) NODE *f;f=s.next;while(f.next!=s);f=f.next;f.next=s.next;free(s);return f ;29、已知某

13、二叉樹BINTREE的結(jié)點(diǎn)結(jié)構(gòu)如下,根結(jié)點(diǎn)的指針為T，試編寫一算法，求該二叉樹的深度。(分) Lchild Data Rchild 函數(shù)形式（參考）： void BiTreeDepth(BiTree T, int level, int &depth)算法1：用前序遍歷的遞歸算法實(shí)現(xiàn)。int level=1;int depth=0;void BiTreeDepth(BiTree T, int level, int &depth) /T指向二叉樹的根，level為T所指結(jié)點(diǎn)所在層次， /其初值為1，depth為當(dāng)前求得的最大層次,其初值為0 if (T) if (leveldepth) depth

14、=level; BiTreeDepth(T-Lchild, level+1, depth); BiTreeDepth(T-Rchild, level+1, depth); /if/BiTreeDepth算法2： 算法思路：用遞歸實(shí)現(xiàn)該算法。如果二叉樹為空，則返回 0；如果二叉樹只有一個結(jié)點(diǎn)（根結(jié)點(diǎn)），返回 1，否則返回根結(jié)點(diǎn)的左分支的深度與右分支的深度中較大者加 1。 算法實(shí)現(xiàn)如下： int GetHeight(BINTREE T) int lh; int rh; if (T = null) return 0; else if (T.LChild = null & T.RChild = nul

15、l) return 1; else lh = GetHeight(T.LChild); rh = GetHeight(T.RChild); return (lhrh?lh:rh) + 1; 算法3：非遞歸算法(按層遍歷)，用隊列實(shí)現(xiàn)。（參閱P187例6.4）void leveltraverse(Bitreenode *T,int &level) Bitreenode *p; Queue Q; /隊列Q定義的結(jié)點(diǎn)結(jié)構(gòu)包含兩個域：Q.LINK和Q.level. 其中 Q.LINK（Bitreenode型）記錄入隊的結(jié)點(diǎn)的指針 地址，Q.level（int型）記錄該結(jié)點(diǎn)的深度 initqueue(Q); /初始化隊列 p=T; Enqueue(Q, p，1); /根結(jié)點(diǎn)入隊，