太原理工大學(xué)　數(shù)據(jù)結(jié)構(gòu)(A)　試卷.docx

考試類型：閉卷太原理工大學(xué)數(shù)據(jù)結(jié)構(gòu)(A)試卷適用專業(yè)：計本04 考試日期： 06.7.14 時間： 120 分鐘 共 8 頁題 號一二三四五六七八九總分得分一判斷題：（每小題2分，共20分） 1鏈棧的初始化是指開辟足夠多的結(jié)點，然后置棧頂指針為 NULL。 （ ） 2數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)的組織形式，基本運算規(guī)定了數(shù)據(jù)的基本操作方式 。 （ ） 3線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。 （ ） 4在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。 （ ） 5數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計算機(jī)的儲存結(jié)構(gòu)。 （ ） 6完全二叉樹的某結(jié)點若無左孩子，則它必是葉結(jié)點。 （ ） 7用鄰接矩陣表示圖時，矩陣元素的個數(shù)與邊的條數(shù)有關(guān)。 （ ） 8二叉樹有五種基本形態(tài)。 （ ） 9圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是唯一的。 （ ） 10用簡單選擇排序算法，只需一趟掃描即可選出鍵值最大（或最小）的元素 。（ ）二選擇題：（每小題2分，共10分） 1二維數(shù)組A的成員是6個字符（每個字符占一個存儲單元）組成的串，行下標(biāo) i的范圍從0到8，列下標(biāo)j的范圍從1到10，A的第8列和第5行共占 ( ）個字節(jié)。 （1）108 （2）60 （3）54 （4）114 2表達(dá)式a*(bc)+d的后綴表達(dá)式是( ）。 （1）abcd*+ （2）abc*d+ （3）abc*d+ （4）+*abcd 3對于有N個結(jié)點高度為K的滿二叉樹(結(jié)點編號為1到N，根結(jié)點的層數(shù)為1)，其第K層上最后1個結(jié)點的編號為 ( )。 （1）2K （2）2K1 （3）2K11 （4）2K1 4一個有N個頂點的無向圖最多有（ ）條邊。 （1）N （2）N*(N1) （3）N*(N1)/2 （4）2*N 5有一個長度為12的有序表，按二分查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找 成功所需的平均比較次數(shù)為（ ）。 （1）43/12 （2）39/12 （3）37/12 （4）35/12 三填空題：（每空2分，共10分）1對于一個具有N個結(jié)點的單鏈表，在已知P所指結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是_；在給定值為X的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度是_。2有如下遞歸過程：Void print(int w) int i; if (w!=0) print(w1);for (i=1;i=w;i+) printf(“%3d”,w);printf(“n”);調(diào)用語句print(4)的結(jié)果是_。3深度為5的二叉樹最多有_個結(jié)點（根結(jié)點層數(shù)為1）。4對N個元素的序列進(jìn)行起泡排序時，最少的比 較次數(shù)是_。四應(yīng)用題：（每小題6分，共30分）1已知一棵二叉樹T的先序序列為：EBADCFHGIKJ，中序序列為：ABCDEFGHIJK，試畫出該二叉樹及其對應(yīng)的樹。2設(shè)散列表長度為11，散列函數(shù)H（k）（k的第一個字母在英文字母表中的序號） MOD 11，若輸入順序為（Blue，Dark，Red，White，Yellow，Green，Purple），（1） 用線性探測開發(fā)定址法解決沖突構(gòu)造散列表；（2） 求在等概率情況下查找成功的平均查找長度。3假設(shè)用于通信的電文由6個字母組成，字母在電文中出現(xiàn)的頻率分別為5，7，9，16，23，18，試為這6個字母設(shè)計哈夫曼編碼。4給定一組關(guān)鍵碼18，31，16，22，51，30，24，畫出執(zhí)行直接插入排序的過程及堆排序過程。5已知帶權(quán)的無向圖的鄰接矩陣如下：畫出該圖及其最小生成樹。五算法設(shè)計：（每小題10分，共30分）1編寫算法,求二叉樹中度為2結(jié)點個數(shù)。2試寫一算法,對n個關(guān)鍵字取非零整數(shù)的記錄序列進(jìn)行整理，使得在盡可能少的時間內(nèi)將所有取奇數(shù)的關(guān)鍵 字放在所有取偶數(shù)的關(guān)鍵字之前，要求所寫算法的時間復(fù)雜度為O(