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

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