《算法與數(shù)據(jù)結(jié)構(gòu)》模擬試題3-答案

1、算法與數(shù)據(jù)結(jié)構(gòu)模擬試題3(參考答案)一、填空題（每小題2分，共18分）1、 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖（或網(wǎng)）狀結(jié)構(gòu)2、 時(shí)間復(fù)雜度 空間復(fù)雜度3、 (直接)前驅(qū)結(jié)點(diǎn) (直接)后繼結(jié)點(diǎn)4、 零個(gè)字符組成的串 0 5、 3006、 只有右子樹上的所有結(jié)點(diǎn)7、 先序遍歷8、 索引 塊9、 操作系統(tǒng) 數(shù)據(jù)庫二、單項(xiàng)選擇題（請將答案寫在題目后的括號中。每題2分，共18分）題號123456789答案ABCBDBBCD三、分析題（每題6分，共30分）fabcehidgNULLfabcehidg圖(a) 二叉樹圖(b) 后序線索化樹1、 解：所畫出的二叉樹如圖(a)所示。樹的后序遍歷序列是gdhiebfca，其

2、后序線索化樹如圖(b)所示。2、 解：該網(wǎng)的鄰接鏈表如下圖所示：0123412345293758193441351124174321333532114318從頂點(diǎn)V1出發(fā)的廣度優(yōu)先搜索的頂點(diǎn)序列是12354，相應(yīng)的生成樹如下：1524389137從頂點(diǎn)V1出發(fā)廣度優(yōu)先搜索生成樹從頂點(diǎn)V5出發(fā)的最小生成樹1524333473、 解：將關(guān)鍵字序列（14，9，18，7，4，13，25，19，6）依此插入到初態(tài)為空的二叉排序樹中所得到的二叉排序樹T如圖(a)所示；刪除18之后的二叉排序樹T1如圖(b)所示；最后再插入18之后的二叉排序樹T2。149197134256圖(b) 刪除18的二叉排序樹149

3(a) 生成的二叉排序樹14919713418256圖(c) 插入18后的二叉排序樹4、 解：根據(jù)所給定的散列函數(shù)和處理沖突方法，得到的散列表結(jié)構(gòu)如下：0123456789103356 25477117 298 4295 69成功查找的平均查找長度：ASL=(18+22+31)/11=17/115、 解：做非遞減排序時(shí)的每一趟結(jié)果如下：初始關(guān)鍵字：35，29，52，60，17，9，38，27，13，45第一趟： 29，35 52，60 9，17 27，38 13，45第二趟： 29，35，52，60 9，17，27，38 13，45第三趟： 29，35，52，60 9，

4、13，17，27，38，45第四趟： 9，13，17，27，29，35，38，45，52，60第四趟歸并完畢，排序結(jié)束。四、算法填空（每空2分，共20分）請?jiān)谙旅娓鱾€(gè)算法的空白處填上相應(yīng)的語句，以實(shí)現(xiàn)算法功能。每個(gè)空白處只能填一個(gè)語句。1、 循環(huán)隊(duì)列Q的隊(duì)首元素出隊(duì)操作算法。Q.front=Q.rearQ.front=(Q.front+1)%Max_Queue_Size ;2、 二叉樹中序遍歷的非遞歸算法。p=stacktop-p=p-Rchildbool!=0 3、 折半查找算法。Mid=(Low+High)/2return(0)4、 簡單選擇排序算法。L-Rn.keyRk.keyk!=mL

5、-Rk=L-R0五、編寫算法（要求給出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)說明，14分）解：結(jié)點(diǎn)類型定義及算法如下：#define int ElemType typedef struct Lnode ElemType data; /* 數(shù)據(jù)域，保存結(jié)點(diǎn)的值 */struct LNode *next; /* 指針域 */LNode; /* 結(jié)點(diǎn)的類型 */void Delete_LinkList_Value(LNode *L) LNode *p=L-next, *q, *ptr ;ElemType k ;while ( p-next!=NULL) k=p-data ; ptr=p ; q=ptr-next ;while (q!=NULL) if (q-data=k) ptr-next=q-next ; free(q) ; /* 刪除值相同的結(jié)點(diǎn) */ptr=ptrnext ; q=ptrnext ; /* 繼續(xù)檢查后續(xù)結(jié)點(diǎn) */p=p-next ; /* 繼續(xù)檢查下一結(jié)點(diǎn)，是否有值相同的結(jié)點(diǎn) */算法分析：設(shè)單鏈表長度為n，若指針p指向第i(i1,n-1)個(gè)