352098_1112B數(shù)據(jù)結(jié)果參考模板

1、四川農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育?？瓶荚嚁?shù)據(jù)結(jié)構(gòu) 試卷（課程代碼 352098）本試題一共二道大題，共2頁(yè)，滿分100分。考試時(shí)間90分鐘。注意：1、答案必須填寫在答題紙上，題號(hào)不清或無(wú)題號(hào)的以零分計(jì)。2、答題前，請(qǐng)?jiān)诖痤}紙上準(zhǔn)確、清楚地填寫各項(xiàng)目；3、學(xué)號(hào)、考點(diǎn)名稱、考室號(hào)、姓名、身份證號(hào)、課程代碼、課程名稱、培養(yǎng)層次等，不寫、亂寫及模糊不清者，答題紙作廢；4、開卷考試，若有雷同以零分計(jì)。一、填空題（每空3分，共60分）1、數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的_存儲(chǔ)結(jié)構(gòu)。2、串的長(zhǎng)度是指_串中所含字符的個(gè)數(shù)_。3、序列中有1000個(gè)元素基本按鍵值遞增順序排列，就算法的比較次數(shù)而言，應(yīng)選擇_直接插入算法_排

2、序算法。4、一棵二叉樹有67個(gè)結(jié)點(diǎn)，這些結(jié)點(diǎn)的度要么是0，要么是2。這棵二叉樹中度為2的結(jié)點(diǎn)有_33_個(gè)。5、最節(jié)省空間的串存儲(chǔ)結(jié)構(gòu)是_節(jié)點(diǎn)存儲(chǔ)6、棧又稱為_后進(jìn)先出_的線性表。7、在圖結(jié)構(gòu)中，前驅(qū)元素和后繼元素之間存在著_一對(duì)一，一對(duì)多，多對(duì)多的聯(lián)系。8、存儲(chǔ)地址與關(guān)鍵字之間存在某種映射關(guān)系的存儲(chǔ)結(jié)構(gòu)為_散列存儲(chǔ)結(jié)構(gòu)_。9、_深度優(yōu)先遍歷_可以判斷出一個(gè)有向圖中是否有環(huán)。10、若堆棧的入棧序列為1,2,3,n-1,n，輸出元素i需要進(jìn)行_ n-i+1_次出棧操作。11、在順序存儲(chǔ)的完全二叉樹中，若編號(hào)為i的結(jié)點(diǎn)有父結(jié)點(diǎn)，則其父結(jié)點(diǎn)編號(hào)為_2i_。1 / 412、具有500個(gè)結(jié)點(diǎn)的二叉樹，其深

3、度至少為_9_。13、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)_指針_來(lái)間接反映數(shù)據(jù)元素之間邏輯關(guān)系的。14、設(shè)一個(gè)散列表的容量為M，用線性探測(cè)法解決沖突.。若要查找一個(gè)鍵值，至多要進(jìn)行_ M _次比較。15、依次在初始為空的隊(duì)列中插入元素a,b,c,d,e以后，緊接著作了三次刪除操作，此時(shí)的隊(duì)首元素是_ b _。16、按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有_5_種形態(tài)。17、對(duì)于線性表（18,25,63,50,42,32,90,66）進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%9作為散列函數(shù)，則散列地址為0的元素有_3_個(gè)。18、給兩個(gè)鍵值K1K2，而散列函數(shù)值H(K1)=H(K2)，則K1和K2是_同義詞_。

4、19、一般可以利用_為遞歸問題設(shè)計(jì)出非遞歸算法。20、假設(shè)一個(gè)10階的下三角矩陣A按列優(yōu)順序壓縮存儲(chǔ)在一維數(shù)組C中，則C數(shù)組的大小應(yīng)為_55_。二、簡(jiǎn)答與應(yīng)用題（共40分）1、 以下為帶空頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列，請(qǐng)寫出該隊(duì)列的入隊(duì)和出隊(duì)算法(10分)。參考算法：/* 設(shè)數(shù)據(jù)元素的類型為DataType */struct node DataType data; /* 存儲(chǔ)元素 */ struct node *next; ;/*/* 入隊(duì) */*/EnQueue (struct node *real, DataType x) struct node *p; p = (struct node *)mall

5、oc(sizeof(struct node); p->data = x; p->next = NULL; /* 保證p是尾結(jié)點(diǎn) */ real->next = p; real = p; /* real指向隊(duì)尾 */ /*/* 出隊(duì) */*/OutQueue (struct node *front, struct node *p) if (front->next = NULL) /* 隊(duì)空 */ error("Queue is Empty!"); else p = front->next; /* 保存隊(duì)首結(jié)點(diǎn) */ /* 隊(duì)首結(jié)點(diǎn)脫鏈 */ Fr

6、ont->next = p->next; 2、 對(duì)于下面的無(wú)向網(wǎng)絡(luò)：1) 畫出表示此網(wǎng)絡(luò)的鄰接矩陣。(4分)2) 畫出用克魯斯卡爾算法構(gòu)造其最小生成樹的過(guò)程。(6分)3、 設(shè)有升序排列的線性表（2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41），用二分查找法進(jìn)行查找。完成以下各小題：3) 畫出查找關(guān)鍵字4的過(guò)程（5分）4) 計(jì)算該表在等概率的情況查找成功的平均查找次數(shù)為多少？（5分）參考答案：初態(tài)：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41第1次：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41第2次：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41第3次：2, 4, 7, 10, 12, 1