綿職院計(jì)科系計(jì)應(yīng)班軟件班數(shù)據(jù)結(jié)構(gòu)期末試卷001a1.doc

數(shù)據(jù)結(jié)構(gòu)一、選擇題：(151分)1. 設(shè)有二維數(shù)組A09，019其中每個(gè)元素占兩個(gè)字節(jié)。數(shù)組按列優(yōu)先順序存貯。第一個(gè)元素的存貯地址為100。則元素A6，6的存貯地址為（ ）。A126 B132 C226 D2322. 數(shù)據(jù)項(xiàng)的集合的集合稱為（ ）。A文件 B記錄 C索引 D關(guān)鍵字3. 設(shè)元素的長度為1，則對(duì)隊(duì)列q施以出隊(duì)delq(q)運(yùn)算后（ ）。A隊(duì)頭指針增量1 B隊(duì)尾指針增量1 C隊(duì)尾元素出隊(duì) D隊(duì)頭、隊(duì)尾指針不動(dòng)4. 在下列排序方法中，哪一個(gè)是穩(wěn)定的排序方法（ ）。A堆排序 B直接選擇排序C希爾排序 D快速排序5. 設(shè)有一棵三叉樹（樹的度為3的樹）。其葉子結(jié)點(diǎn)數(shù)為N。度為1的結(jié)點(diǎn)數(shù)為N1，度為2的結(jié)點(diǎn)為N2，度為3 的結(jié)點(diǎn)數(shù)為N3，則N0與N1、N2、N3的關(guān)系滿足（ ）。AN0=N2+1 BN0=N2+2*N3+1CN0=N2+N3+1 DN0=N1+N2+N36. 有6個(gè)元素按6，5，4，3，2，1的順序進(jìn)棧，入棧過程允許棧頂元素出找。問下列哪一個(gè)不是合法的出棧序列（ ）。A5 4 3 6 1 2 B4 5 3 1 2 6C3 4 6 5 2 1 D2 3 1 4 5 67. 下面關(guān)于串的敘述中，哪一個(gè)是不正確的（ ）。A串是字符的有限序列 B空串是由空格構(gòu)成的串 C模式匹配是串的一種重要的運(yùn)算D串既是可采用順序存貯，也可采用鏈?zhǔn)酱尜A裝 訂. 線8. 對(duì)包含n個(gè)元素的散列表進(jìn)行檢索，平均檢索長度為（ ）。A0（log2n） B0(n)C0(nlog2n) D不直接依賴于n9. 在堆排序中，當(dāng)初堆建成后，該堆根的記錄必是（ ）。A.文件中的第一個(gè)記錄B.文件中具有最大（或最?。╆P(guān)鍵字的記錄C.文件中的一個(gè)記錄D.文件中的最后一個(gè)記錄10. 下面有向圖可以排成不同的拓?fù)湫蛄校渲胁徽_的序列為（ ）。A. 1 2 3 4 5 6 B. 1 2 4 3 6 5C. 1 4 2 3 6 5 D. 1 2 3 4 6 511. 樹形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)（ ）A、無直接前驅(qū) B、可有多個(gè)直接前驅(qū)C、至多只能有一個(gè)直接前驅(qū) D、有三個(gè)以上的直接前驅(qū)12. 設(shè)有向圖G有n個(gè)頂點(diǎn),它的鄰接矩陣為A，G中第i個(gè)頂點(diǎn)Ui的度為( )。A、Ai，i B、Ai，jC、（Ai，j+Aj，i） D、Ai，j+Ai，j13. m叉樹的后序遍歷結(jié)果和該樹轉(zhuǎn)換所得二叉樹的_結(jié)果完全相同（）A、前序遍歷 B、中序遍歷C、后序遍歷 D、層次遍歷14. 設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為1，則高度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為（）A、2k-1-1 B、2k-1C、2k-1 D、2k15. 對(duì)n個(gè)排序碼進(jìn)行排序，具有平均時(shí)間復(fù)雜度為O(n2)的排序方法是（）A、合并排序 B、堆排序C、快速排序 D、直接插入排序二、填空：(53分+35分)1. 在順序表（5，13，17，42，46，55，70，94）中，用二分法查找關(guān)鍵碼值為12，需做的關(guān)鍵碼比較次數(shù)為 _。2. 對(duì)某非空二叉樹進(jìn)行前序、中序遍歷時(shí)，所得的結(jié)果完全相同（即結(jié)點(diǎn)序列一致），則這棵二叉樹必定是_。3. 對(duì)于有n個(gè)頂點(diǎn)的連通圖，至少有_條邊。由此而構(gòu)成的生成樹有_條邊。有_條邊的無向圖為完全圖。4. 設(shè)有一個(gè)用線性探測法解決沖突得到的Hash表（Hash函數(shù)為H(k)=K Mod 11）有一組數(shù)（13,25,80,16,17,6,14），則探測元素14的地址值為_（填入上Hash表中）5. 二叉樹的前根遍歷為：ABCDEFGHI，中根遍歷：BCAEDGHFI，這棵二叉樹的后根遍歷序列為_。以下是算法填空6. 該算法實(shí)現(xiàn)折半查找，查找表中的數(shù)據(jù)按遞增次序排列int BinSearch(DataType list,int low,int high,DataType key) int mid; DataType midvalue; while(low=high) mid=(low+high)/2; midvalue=listmid; if (key=midvalue) return mid; else if(keydata); inorder(tree-rlink); 三、簡答題：(40分)1. 設(shè)電文中出現(xiàn)字字母A,B,C,D,每個(gè)字母在電文中出現(xiàn)的次數(shù)分別是2,7,4,5按哈夫曼編碼求A,B,C,D的編碼,請(qǐng)作出哈夫曼樹.并求WPL.2. 己知如圖所示的一棵樹，寫出此樹的先根遍歷序列，并畫出其孩子鏈表表示法的存儲(chǔ)結(jié)構(gòu)圖。3. 已知如下帶權(quán)圖，請(qǐng)給出該圖的鄰結(jié)表，并用C語言描述起存儲(chǔ)結(jié)構(gòu)。（將其結(jié)構(gòu)填充完整）A卷 第7頁 共7 頁 #define MAXtypedef struct ArcNode ArcNode; /邊typedef struct VnodeVnode,AdjlistMAX; /結(jié)點(diǎn)typedfe stru int kind /圖的種類標(biāo)志ALGrph /圖4. 求圖的最小生成樹（描述過程）四、算法設(shè)計(jì)(15分)在一維數(shù)組An中，從下標(biāo)1到n-1的單元中，存放著n-1個(gè)整數(shù)，使用插入法排序，將數(shù)組遞增排列。插入法排序的基本操作是將一個(gè)個(gè)數(shù)據(jù)不斷地插入到已