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

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

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

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

4、19、一般可以利用_為遞歸問題設(shè)計出非遞歸算法。20、假設(shè)一個10階的下三角矩陣A按列優(yōu)順序壓縮存儲在一維數(shù)組C中，則C數(shù)組的大小應(yīng)為_55_。二、簡答與應(yīng)用題（共40分）1、 以下為帶空頭結(jié)點的鏈?zhǔn)疥犃校垖懗鲈撽犃械娜腙牶统鲫犓惴?10分)。參考算法：/* 設(shè)數(shù)據(jù)元素的類型為DataType */struct node DataType data; /* 存儲元素 */ struct node *next; ;/*/* 入隊 */*/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é)點 */ real->next = p; real = p; /* real指向隊尾 */ /*/* 出隊 */*/OutQueue (struct node *front, struct node *p) if (front->next = NULL) /* 隊空 */ error("Queue is Empty!"); else p = front->next; /* 保存隊首結(jié)點 */ /* 隊首結(jié)點脫鏈 */ Fr

6、ont->next = p->next; 2、 對于下面的無向網(wǎng)絡(luò)：1) 畫出表示此網(wǎng)絡(luò)的鄰接矩陣。(4分)2) 畫出用克魯斯卡爾算法構(gòu)造其最小生成樹的過程。(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的過程（5分）4) 計算該表在等概率的情況查找成功的平均查找次數(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