數(shù)據(jù)結(jié)構(gòu)期末試題參考

1、文檔供參考，可復(fù)制、編制，期待您的好評與關(guān)注！ 專業(yè) 年級 學(xué)號_ 姓 名 _密封線期末考試考試試卷（6）（ 至 學(xué)年第 學(xué)期） 課程名稱： 數(shù)據(jù)結(jié)構(gòu) 題目一二三四五六七八總分得分一、判斷選擇填空 (10分)1、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面。.( )2、用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷；.( ) 3、單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。.( )4、外部排序是在排序過程中，只使用外存儲(chǔ)器的排序。.( )5、設(shè)串S的長度為n,則S的子串個(gè)數(shù)為n(n+1)/2。.( )6、若二叉樹中的一個(gè)葉子結(jié)點(diǎn)是某子樹中序序列的最后一個(gè)結(jié)點(diǎn)

2、，則它必是該子樹的先序序列的最后一個(gè)結(jié)點(diǎn)。. ( ) 7、設(shè)h是一散列函數(shù)，key1和key2為關(guān)鍵碼值，且 key1<>key2，但h（key1）=h（key2），這種現(xiàn)象稱為（ ）。8、若入棧序列的元素順序是A、B、C、D、E，判斷下列哪一個(gè)出棧序列是不可能的（ ） . A、B、C、D、E . B、C、D、E、A .E、A、B、C、D.D、C、B、A、E9、設(shè)i為n個(gè)結(jié)點(diǎn)的完全二叉樹結(jié)點(diǎn)編，i=1，2，3.n；若i（n-1）/2時(shí)，結(jié)點(diǎn)i的右孩子為（ ） . 2i . 2i+1 . 2i-1 . i+110、若S1=China'，S2='$Beijing'

3、;,則S1/S2=( )。二、（5分）簡述順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。三、（5分）簡述使用順序存儲(chǔ)表示循環(huán)隊(duì)列時(shí)，判定隊(duì)列“空”和“滿”的方法。四、（5分）編寫子串位置定位函數(shù)Index(S,T,pos)；五、（5分）假設(shè)字符a,b,c,d,e,f的使用頻度分別是0.07,0.09,0.12,0.22,0.23,0.27，畫出相應(yīng)的Huffman樹，并寫出a,b,c,d,e,f的Huffman編碼。六、（5分）假設(shè)一棵二叉樹的后序序列為GDBEHFCA和中序序列為DGBAECHF，請畫出該二叉樹，并寫出先序遍歷序列。七、（5分）將六題中的二叉樹轉(zhuǎn)換為森林。八、（5分）畫出圖1所示圖的深

4、度優(yōu)先生成樹和廣度優(yōu)先生成樹。九、（5分）對于圖2，寫出它的四個(gè)不同的拓樸有序序列。 圖1 圖2 十、（5分）求圖3所示圖的關(guān)鍵路徑。 專業(yè) 年級 學(xué)號_ 姓 名 _密封線圖3十一、（5分）設(shè)一個(gè)哈希表為下表，請簡述查找84和38的過程。0123456789101112140168275519208479231110十二、（5分）已知含有12個(gè)關(guān)鍵字的有序表及其相應(yīng)權(quán)值為： 關(guān)鍵字 A B C D E F G H I J K L 權(quán)值 8 2 3 4 9 3 2 8 7 1 1 4試構(gòu)造次優(yōu)二叉查找樹。十三、（5分）寫出用堆排序(heap sort)算法對序列F=(12，3，15，30，9，28)進(jìn)行排序時(shí),初始堆及以后每挑好一個(gè)元素重新調(diào)整后堆的狀態(tài)。以下四題任選三題。十四、（10分）編寫算法刪除線性表中所有值相同的多余元素。（使用順序存儲(chǔ)結(jié)構(gòu)或單鏈表存儲(chǔ)結(jié)構(gòu)均可）十五、（10分）編寫中序遍歷二