閩江學院2014 12級 數(shù)據(jù)結(jié)構(gòu)與算法試卷b卷

2013—2014學年第一學期閩江學院考試試卷考試課程：數(shù)據(jù)結(jié)構(gòu)與算法試卷類別：B卷考試形式：閉卷適用專業(yè)年級：12電子信息工程、12電子科學與技術(shù)、12電子信息科學與技術(shù)裝訂線裝訂線題號一二三四五總分得分一、選擇題（共15小題，每題2分）30%得分選擇題答案填寫處1234567891011121314151、棧和隊列都是（）A．限制存取點的線性結(jié)構(gòu)B．限制存取點的非線性結(jié)構(gòu)C．順序存儲的線性結(jié)構(gòu)D．鏈式存儲結(jié)構(gòu)的線性結(jié)構(gòu)2、（）又稱為FIFO表A．隊列 B．散列表 C．棧 D．哈希表3、設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（）。A．O(n) B．O(nlog2n) C．O(1) D．O(n2)4、設(shè)一數(shù)列3,5,7,9通過棧結(jié)構(gòu)，不可能的出棧序列為（）。A）7,5,3,9B）7,5,9,3C）9,7,5,3D）9,5,7,35、以順序存儲方式將完全二叉樹中的所有結(jié)點逐層存放于數(shù)組A中，結(jié)點A[i]若有左孩子，則左孩子是結(jié)點（）。A.A[2*i]B.A[2*i+1]C.A[2*i+2]D.A[idiv2]6、某二叉樹如圖所示，對該二叉樹進行先序遍歷，結(jié)點的訪問序列為（）。A.1,2,3,4,5,6,7B.1,2,4,6,7,3,5C.2,6,4,7,1,5,3D.6,7,4,2,5,3,17、在下列存儲結(jié)構(gòu)中，（）不是樹的存儲形式。A.雙親表示法B.孩子鏈表表示法C.孩子兄弟表示法D.順序存儲表示法8、已知Huffman樹的總結(jié)點數(shù)為m，葉子數(shù)為n。則m與n的關(guān)系是（）。A．m=2n+1B．m=n+1 C．m=2n–1 D．m=n–19、若從二叉樹的任意結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序，則該二叉樹是（）。A.滿二叉樹B.哈夫曼樹C.堆D.二叉排序樹10、對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣中元素的個數(shù)為（）。A.nB.(n-1)2C.(n+1)2D.n211、對圖所示的無向圖G，從頂點A開始，深度優(yōu)先遍歷，可能的頂點訪問順序為（）。A.A,B,E,C,D,FB.A,C,F,E,B,DC.A,B,C,D,E,FD.A,C,F,D,E,B12、有n個頂點的有向完全圖中，具有（）條邊。A.n(n-1)/2B.n(n-1)C.n(n+1)/2D.n213、用折半查找方法從長度為11的有序表中查找一個元素時，平均查找長度為（）。A.3B.4C.5D.614、以下序列中，（）才可能是執(zhí)行第一趟快速排序后得到的序列。A．{8，6，18}19{6，10，50}B．{6，4，8}18{81，19，36，18}C．{81，1，2}36{99，81，69}D．{2，3，4}89{78，98，68}15、以下4種排序算法中，時間復(fù)雜度最小的是（）。A.插入排序B.選擇排序C.冒泡排序D.歸并排序二、填空題（共8小題，每空2分）20%得分1、實現(xiàn)函數(shù)遞歸調(diào)用的數(shù)據(jù)結(jié)構(gòu)是。2、在一個單鏈表中，在指針p所指向的結(jié)點之后插入指針s所指向的結(jié)點時，應(yīng)執(zhí)行如下操作：s->next=；p->next=。3、棧中的第一個元素稱為。隊列的最后一個元素稱為。4、n個結(jié)點的二叉鏈表中，共有2n個指針，其中有個指針用于指向左、右孩子，剩余的個指針為空。5、深度為5的二叉樹至多有個結(jié)點。6、在n個頂點的有向圖中，每個頂點的度最大可達。7、對于一個具有n個頂點e條邊的無向圖，若采用鄰接表表示，則它的鄰接表需n個表頭結(jié)點和_______________個表結(jié)點。三、判斷題（共10小題，每題1分）10%得分1、（）線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。2、（）順序存儲結(jié)構(gòu)不僅能用于表示完全二叉樹，也能表示一般的二叉樹。3、（）逆鄰接表只能用于有向圖的存儲。4、（）n個帶權(quán)葉子結(jié)點構(gòu)成的哈夫曼樹（最優(yōu)二叉樹）是唯一的。5、（）算法就是程序。6、（）對長度為n的線性表進行分塊查找，其ASL的最小值是O()。7、（）對任意一個圖，從它的某個頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷可訪問到該圖的每個頂點。8、（）對n個元素的集合進行堆排序時，需要的輔助存儲空間為O(n)。9、（）對鏈表進行插入和刪除操作時不必移動鏈表中結(jié)點。10、（）堆是完全二叉樹，完全二叉樹不一定是堆。四、應(yīng)用題（共5小題）30%得分1、已知一棵二叉樹的層次遍歷序列為ABCDEFGHIJ，中序遍歷序列為DBGEHJACIF，試畫出該二叉樹。(5分)2、已知順序表中存儲的序列{19,14,22,1,66,21,83,27,56,13}，將元素按其在表中的次序依次插入到一棵初始為空的二叉排序樹中，要求：（1）畫出插入完成后的二叉排序樹。(5分)（2）設(shè)各數(shù)據(jù)元素的查找概率相等，給出該二叉排序樹的平均查找長度。（2分）3、設(shè)數(shù)據(jù)元素關(guān)鍵字序列為{475,137,481,219,382,674,350,326,815,506}，寫出執(zhí)行希爾排序（增量d=5,3,1）算法時，各趟排序后的關(guān)鍵字序列（最后結(jié)果為升序））。（3分）4、假設(shè)用于通信的電文僅由8個字母a，b，c，d，e，f,g,h組成，各字母的使用頻率分別為16，3，9，8，4，10,5,6請畫出本問題的哈夫曼樹，并為這8個字母設(shè)計哈夫曼編碼。（8分）5、設(shè)哈希表的長度為13，哈希函數(shù)為H(k)=k%13，關(guān)鍵字序列為（19,14,23,1,68,20,84,27,55,11,10,79）（1）試畫出用線性探查法消解地址沖突時所構(gòu)造的哈希表。（6分）（2）并求出以上哈希表的平均檢索長度。（1分）五、編程題（共2小題，每題5分）10%得分1、以二叉鏈表為存儲結(jié)構(gòu)，寫出求二叉樹中葉子結(jié)點數(shù)的算法的遞歸函數(shù)。二叉鏈表的結(jié)點定義如下：typedefstructBiTNode{//結(jié)點結(jié)構(gòu)TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;2、試寫出直接插入排序的實現(xiàn)算法（最后結(jié)果為升序）。(5分)待排序文件中記錄結(jié)構(gòu)類型定義如下：typedefstruct{in