(完整word版)2007~2008學(xué)年《數(shù)據(jù)結(jié)構(gòu)》B

1、華僑大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷（B）系別：班級(jí)：學(xué)號(hào)：姓名：考試日期：年月日題號(hào)一二三四五總分得分一、選擇填空題（每題 1.5 分，共 15 分）1、 在一個(gè)長(zhǎng)度為n 的順序線性表中順序查找值為x 的元素時(shí)，查找成功時(shí)的平均查找長(zhǎng)度（即x 與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為（）。A nBn/2C(n+1)/2D(n-1)/22、已知單鏈表 A 長(zhǎng)度為 m，單鏈表 B 長(zhǎng)度為 n，若將B 聯(lián)接在 A 的末尾，其時(shí)間復(fù)雜度應(yīng)為（）。A O(1)BO(m)CO(n)DO(m+n)3、 若進(jìn)棧序列為a,b,c，則通過入出棧操作可能得到的a,b,c 的不同排列個(gè)數(shù)為（）。A 4B5C6D74、

2、 由權(quán)值分別為11， 8， 6，2， 5 的葉子結(jié)點(diǎn)生成一棵赫夫曼樹，它的帶權(quán)路徑長(zhǎng)度WPL 為（）。A 24B71C48D535、已知函數(shù) Sub(s,i,j) 的功能是返回串 s 中從第 i 個(gè)字符起長(zhǎng)度為 j 的子串，函數(shù) Scopy(s,t)的功能為復(fù)制串 t 到 s。若字符串 S=SCIENCESTUDY ，則調(diào)用函數(shù) Scopy(P,Sub(S,1,7)后得到（ ）。AP= SCIENCEBP= STUDYCS= SCIENCEDS= STUDY6、二維數(shù)組A47 按列優(yōu)先存儲(chǔ)方法存儲(chǔ)在內(nèi)存中，若每個(gè)元素占2 個(gè)存儲(chǔ)單元，且數(shù)組中第一個(gè)元素的存儲(chǔ)地址為120，則元素 A34 的存儲(chǔ)

3、地址為（）。A139B145C158D1627、下列陳述中正確的是() 。A 二叉樹是度為2 的有序樹B 二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分C 二叉樹中必有度為 2 的結(jié)點(diǎn)D 二叉樹中最多只有兩棵子樹，并且有左右之分8、 n 個(gè)頂點(diǎn)的無向完全圖中含有向邊的數(shù)目最多為()。An-1BnCn(n-1)/2Dn(n-1)9、假定一個(gè)鏈?zhǔn)疥?duì)列的隊(duì)頭和隊(duì)尾指針分別為front 和 rear，則判斷隊(duì)空的條件為()。Afront = =rearBfront !=NULLCrear != NULLDfront NULL10、下列排序方法中，哪一種方法的比較次數(shù)與紀(jì)錄的初始排列狀態(tài)無關(guān)？()A直接插入排序B

4、冒泡排序C快速排序D簡(jiǎn)單選擇排序二、填空題（每空1 分，共 10 分）1、若一個(gè)算法中的語句頻度之和為T(n)=3720n+4nlogn ，則算法的時(shí)間復(fù)雜度為。2、數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)包括順序、索引和散列等四種。13 、假設(shè)一個(gè)10 階的下三角矩陣A ，按行優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組C 中，則C 數(shù)組的大小應(yīng)為_ 。4、一棵高度為4 的二叉樹中最少含有個(gè)結(jié)點(diǎn)，最多含有個(gè)結(jié)點(diǎn)；一棵高度為 4 的完全二叉樹中，最少含有個(gè)結(jié)點(diǎn)，最多含有個(gè)結(jié)點(diǎn)。5、在對(duì)長(zhǎng)度為n 的關(guān)鍵字序列進(jìn)行堆排序的過程中，對(duì)堆頂元素進(jìn)行堆調(diào)整的篩選運(yùn)算的時(shí)間復(fù)雜度為，整個(gè)堆排序過程的時(shí)間復(fù)雜度為。6 、若對(duì)序列49 ， 38，

5、65， 97， 76， 13， 27， 50 采用冒泡排序法排序，則第二趟結(jié)束后序列的狀態(tài)是。三、解答題（每題5 分，共 30 分）1、指出下面算法中，帶下劃線的語句的語句頻度，并估計(jì)該算法的時(shí)間復(fù)雜度。int fun(int n)s=0;t=0;for(i=1;i=i;j-)t+;return s+t;2、設(shè)循環(huán)隊(duì)列的總長(zhǎng)度為 5，入隊(duì)的序列為 A1 ，A2 ，A3 ，A4 ，然后 A1 ， A2 出隊(duì)，最后 A5 ， A6 入隊(duì)，請(qǐng)畫出最后的循環(huán)隊(duì)列，并寫出在循環(huán)隊(duì)列中判斷隊(duì)空和隊(duì)滿的條件。3、某二叉樹 bt 中序遍歷序列為： ABCEFGHD ，后序遍歷序列為： ABFHGEDC ，請(qǐng)構(gòu)

6、造該二叉樹（畫出樹形），并畫出對(duì)應(yīng)的先序線索（不帶頭結(jié)點(diǎn)） 。4、試畫出如下圖的無向圖G 的鄰接表表示，要求鄰接表中的各頂點(diǎn)的鄰接鏈表中的表結(jié)點(diǎn)按頂點(diǎn)序號(hào)從小到大排列。 根據(jù)你所給出的鄰接表，給出從 A 出發(fā)的深度優(yōu)先搜索序列，并給出其深度優(yōu)先搜索dfs 生成樹。ABCDE無向圖 G25、設(shè)有一個(gè)關(guān)鍵字輸入序列 31 ，55， 11，37，46，73， 7 ，試從空樹開始構(gòu)造平衡二叉排序樹，畫出每加入一個(gè)結(jié)點(diǎn)時(shí)二叉樹的形態(tài)，若發(fā)生不平衡，請(qǐng)指出平衡調(diào)整的類型和調(diào)整結(jié)果。最后，計(jì)算在等概率情況下，查找成功的平均查找長(zhǎng)度ASL 。6、判別序列 12 ，2， 16， 30， 8， 28， 4， 10

7、， 20， 6， 18 是否為大頂堆，如果不是，則寫出將其調(diào)整為大頂堆的過程（用樹形表示） 。四、算法閱讀題（每題5 分，共 15 分）1、 head 為不帶頭結(jié)點(diǎn)的單鏈表頭指針，鏈表中結(jié)點(diǎn)的域有數(shù)據(jù)域data 和指針域next，閱讀下面算法，指出該算法的功能。voidfun1( Linklist &head )p=head;while ( p!= NULL )q=p; r= p-next;while( r!=NULL )if(r-data data )q=r;r= r-next;temp=q-data; q-data=p-data; p-data=temp; p= p-next ;2、閱讀下

8、面算法，指出該算法的功能。voidfun2(char str )Stack T;int i=0;InitStack(T);/初始化棧Twhile(stri != 0 )Push(T, stri);i+;i = 0;while(!StackEmpty(T) /判斷棧 T 是否為空棧Pop(T, stri);i+;3、設(shè)二叉樹t 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，閱讀下面算法，指出該算法的功能。intfun3(BiTreet)if(t=NULL)return 0;else if(t-lchild=NULL)&(t-rchild=NULL)return 1;elsereturn （ fun3(t-lchild)

9、+algo3(t-rchild)） ;3五、算法設(shè)計(jì)題（共30 分）（說明：你所設(shè)計(jì)算法中若需調(diào)用基本操作，需給出實(shí)現(xiàn)該基本操作的算法）1、 L 為帶頭結(jié)點(diǎn)的單鏈表頭指針且鏈表長(zhǎng)度大于2，試設(shè)計(jì)算法刪除鏈表L 的尾結(jié)點(diǎn)，并將該結(jié)點(diǎn)插入到鏈表 L 的首結(jié)點(diǎn)之前（即頭結(jié)點(diǎn)之后）。（10 分）2、設(shè)二叉排序樹bt 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)算法刪除二叉排序樹bt 中值最小的結(jié)點(diǎn)。 （ 8 分）3、試設(shè)計(jì)算法Create_dg(algraph &g1 ，Mgraphg2)，將鄰接表表示的有向圖g1，轉(zhuǎn)換成數(shù)組表示的有向圖g2。（ 12 分）#defineINFINITYINT_MAX/圖的鄰接表存儲(chǔ)

10、表示：#defineMAX_NUM20typedef structArcNode/ 圖的數(shù)組（鄰接矩陣）存儲(chǔ)表示：intadjvex;typedef structArcCellstruct ArcNode*nextarc;VRTypeadj;ArcNode;InfoType*info;typedefstructVNode ArcCell;VertexTypedata;typedefstructArcNode*firstarc;VertexTypevexsMAX_NUM ;VNode;ArcCellarcsMAX_NUM MAX_NUM;typedefstructintvexnum , arcn

11、um;VNodeverticesMAX_NUM;MGraph;intvexnum , arcnum;ALGraph;4B 卷 參考答案一、選擇題（共15 分，每小題 1.5 分）題號(hào)12345答案題號(hào)678910答案二、填空題（共10 分，每小題 1 分）1.2.3.4.5.6.三、解答題（共30 分，每小題 5 分）1. s+=2;的語句頻度是 n-1-（ 1分）t+;的語句頻度是 (n-1)(n+2)/2-(2分 )該算法的時(shí)間復(fù)雜度是 O(n-1)(n+2)/2)=O(n2分 )-(22. 最后的循環(huán)隊(duì)列如下圖所示： （ 2 分）Q.rear Q.frontA6A3A4A501234隊(duì)空

12、的條件（1.5分）： Q.rear 等于 Q.front隊(duì)滿的條件（1.5分）： (Q.rear+1) mod 5等于 Q.front3.該二叉樹先序序列為 CBADEGFH(2分 ) ，對(duì)應(yīng)的中序線索二叉樹（不帶頭結(jié)點(diǎn)）為：（3 分）CNULLNULLDBAE5G4. 無向圖 G的鄰接表表示如下 :(2 分 )從 A 出發(fā)的深度優(yōu)先搜索序列：A,D,E,B,C （ 1.5 分），相應(yīng)的深度優(yōu)先搜索生成樹為：（ 1.5 分）ADEBC深度優(yōu)先搜索樹dfs5. 構(gòu)造過程如下： （ 3.5 分）0-131310550-13131600+105555111131+21155LR 型-1370-246

13、310-11146RR 型0-13755073+146+131+101137007-1310011460037550460-13155000113773-155073ASLsucc=1/7(1*1+2*2+3*3+4*1)=18/7(1.5分 )76.按照層次遍歷方法寫成二叉樹（1 分）：12/216/308284/1020618序列一共有11 個(gè)值應(yīng)該從 11/2處開始交換，即第5 個(gè)值 8 處開始建堆操作將該子樹調(diào)整為大根堆：（4分）1、12/216/3018284/1020682 、對(duì) 30 進(jìn)行操作發(fā)現(xiàn)該子樹已是大根堆不用調(diào)整接著對(duì)16 進(jìn)行操作12/228/3018164/10206

14、83 、對(duì) 2 進(jìn)行操作12/3028/2018164/102684 、對(duì)根結(jié)點(diǎn)12 進(jìn)行操作30/2028/1218164/102688四、算法閱讀題（共15 分，每小題 5 分）1.用鏈表表示的數(shù)據(jù)的簡(jiǎn)單選擇排序，結(jié)點(diǎn)的域?yàn)閿?shù)據(jù)域data ，指針域next ；鏈表首指針為 head ，鏈表無頭結(jié)點(diǎn)。 p 指向無序區(qū)第一個(gè)記錄，q 指向最小值結(jié)點(diǎn)，一趟排序結(jié)束，p 和 q 所指結(jié)點(diǎn)值交換，同時(shí)向后移 p 指針。2.字符串倒序存放。3.求二叉樹 t 中的葉子結(jié)點(diǎn)個(gè)數(shù)五、算法設(shè)計(jì)題（共30 分）1 void def_l_ins_f(Linklist &l)-1分/ 刪除尾結(jié)點(diǎn)，插入在首結(jié)點(diǎn)之前q

15、 = l;p = l-next;-2分while ( p-nexet)q = p;p = p-next; /p指向尾結(jié)點(diǎn) ,q 相隨 -4分q-next = NULL；/ 刪除-1分p-next = l-next;/ 插入-1分l-next = p;-1分/del_l_ins_f2.Status del_min(BiTree &bt)-1分/ 刪除二叉排序樹 bt 中值最小的結(jié)點(diǎn)if (!bt) return ERROR;/ 空樹p = bt;if (bt-lchild = NULL) /根無左子樹-2分bt = bt-rchild;p-rlchild = NULL;/此語句可不要free(p);elsewhile(p-lchild != NULL)/p移至最左下結(jié)點(diǎn)q = p;p = p-lchild;if(p-rchild != NULL)/有右子樹-5分q-lchild = p-rchild;elseq-lchild = NULL;/無右子樹free(p);/del_min3.Status Create_dg(Algraph g1，Mgraph &g2)-1分/ 將鄰接表表示的有向圖 g1 轉(zhuǎn)換成數(shù)組表示的有向圖 g2g2.vexnum =