2012年江西理工大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題

1、2012年江西理工大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題一、選擇題（每小題2分 共30分）1.深度為6（根的層次為1）的二叉樹至多有（）結(jié)點(diǎn)。A 64B 32C 31D632.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中的（）A原點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B.從源點(diǎn)到匯點(diǎn)C.最長(zhǎng)的回路D. 最短的回路3.對(duì)于長(zhǎng)度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長(zhǎng)度為（ ）A.20/9B. 18/9 C. 25/9D.22/94.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于A.nB.n-1C.n+l1 D.2*n5.如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)6.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須7.若讓元素A、

2、B、C、D、E依次進(jìn)棧，則出棧次序不可能出現(xiàn)的情況為（）.A.A、B、C、D、EB.B、C、D、E、A C.E、A、B、C、DD.E、D、C、B、A8.若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為（9.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是（A.便于進(jìn)行矩陣運(yùn)算B.便于輸入和輸出C.節(jié)省存儲(chǔ)空間 D.降低運(yùn)算的時(shí)間復(fù)雜度10.下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）（）A.深度優(yōu)先遍歷 B.拓?fù)渑判駽.求最短路徑 D.求關(guān)鍵路徑11.下列四個(gè)序列中，哪一個(gè)是堆（）A.75,65,30,15,25,45,20,10B.75,65,45

3、,10,30,25,20,15C.75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,1512.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)?（）A存儲(chǔ)密度大B.插入運(yùn)算方但C.刪除運(yùn)算方便 D.可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示13.有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）A.不確定B.2nC.2n+1D.2n-114. 在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是（）A. p->next=s;s->next=p->next;B. s-next=p->next;p->next=s;C. p->next=s;p->

4、;next=s->next;D. p-next=s->next;p->next=s;15.二維數(shù)組SA中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A【4】【7】的起始地址為（A.SA+141B. SA+180 C. SA+222D. SA+225二、由二叉樹的中序序列及前序序列能唯一的建立二叉樹，試問中序序列及后序序列是否也能唯一的建立二叉樹，不能則說(shuō)明理由，若能對(duì)中序序列DBEAFGC 和后序序列DEBGFCA構(gòu)造二叉樹。假定某二叉樹的前序遍歷序列為ABCDEFGHIJ，后序遍歷序列為CEFDB

5、JIHGA，據(jù)此兩個(gè)序列能否唯一確定此二叉樹?若不能，試畫出兩樣具有同樣上述遍歷序列的二叉樹.（12分）三、假設(shè)用于通信的電文由字符集a，b，c，d，e，f，g中的字母構(gòu)成。它們?cè)陔娢闹谐霈F(xiàn)的頻度分別為0.31，0.16，0.10，0.08，0.11，0.20，0.04，（15分）1）為這7個(gè)字母設(shè)計(jì)哈夫曼編碼;2）對(duì)這7個(gè)字母進(jìn)行等長(zhǎng)編碼，至少需要幾位二進(jìn)制數(shù)?哈夫曼編碼比等長(zhǎng)編碼使電文總長(zhǎng)壓縮多少?四、已知一個(gè)無(wú)向圖如圖所示，試回答以下問題（12分）1）寫出該圖的鄰接表2）請(qǐng)用克魯斯卡爾算法生成最小生成樹（畫出構(gòu)造過(guò)程）。五 如圖所示的帶權(quán)有向圖G，試回答以下問題（15分）1） 給出從結(jié)點(diǎn)

6、v1出發(fā)按深度優(yōu)先搜索遍歷G所得的結(jié)點(diǎn)序列2）給出G的一個(gè)拓?fù)湫蛄?）給出從結(jié)點(diǎn) v1到結(jié)點(diǎn)v8的關(guān)鍵路徑。六、本程序完成將二叉樹中左、右孩子交換的操作。（12分）本程序采用非遞歸的方法，設(shè)立一個(gè)堆棧stack存放還沒有轉(zhuǎn)換過(guò)的結(jié)點(diǎn)，它的棧頂指針為 tp。交換左、右子樹的算法為（1）把根結(jié)點(diǎn)放入堆棧。（2）當(dāng)堆棧不空時(shí)，取出棧頂元素，交換它的左、右子樹，并把它的左、右子樹分別入棧。（3）重復(fù)（2）直到堆棧為空時(shí)為止。七.一個(gè)棧的輸入序列是 A，B，C，則棧的輸出序列可有多少種?一一列舉出來(lái)。假如一個(gè)棧的輸入序列是1，2，3，4，5，則棧的輸出序列為4，3，5，1，2是否可以得到?為什么?（10分）八、.對(duì)于下列一組關(guān)鍵字46，58，15，45，90，18，10，62試寫出快速排序每一趟的排序結(jié)果，并標(biāo)出每一趟中各元素的移動(dòng)方向。（10分）九、設(shè)散列函數(shù)為H（k）=k%13，散列表的地址空間為0到12，用線性探查法解決沖突，將關(guān)鍵字（18，22，78，205，40，16，35，104，61）依次存入該散列表中，試構(gòu)造散列表，并計(jì)算在等概率下的搜索成功的平均搜索長(zhǎng)度 ASL （搜索成功的平均搜索長(zhǎng)度 ASLsucc 是指搜索到表中己有表項(xiàng)的平均探查次數(shù)。它是找到表中各個(gè)己有表項(xiàng)的探查次數(shù)的平