五邑大學2014數(shù)據(jù)結(jié)構(gòu)與算法考題A

--------試卷編號試卷編號命題人： 金旺春 審批人: 試卷分類（A卷或B卷） A五邑大學試卷學期：2012至2013學年度 第一 學期課程：班級：數(shù)據(jù)結(jié)構(gòu)與算法專業(yè)：姓名：學號：題號題號一二總分得分一、得分單項選擇題(在每小題的四個備選答案中，選出一個正確答案，并將正確答案的序號填在題干的括號內(nèi)。每小題2分，共20分) 二叉樹的先序序列和后序序列正好相同，則該二叉樹一定( )的二叉樹A.任一結(jié)點無右孩子 B.高度等于其結(jié)點數(shù)C.任一結(jié)點無左孩子 D.空或只有一個結(jié)點一個棧的輸入序列為1234則下列序列中不可能是棧的輸出序列的( )A.23415 B.23145C.54132 D.15432設循環(huán)隊列中數(shù)組的下標范圍是0～n-1，其頭尾指針分別為f和則其元素個數(shù)( )r-f B.r-f+1C.(r-f) modn+1 D.(r-f+n) mod n若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除第一個結(jié)點，則采用( )存儲式最節(jié)省時間。單鏈表 B.單循環(huán)鏈表C.雙鏈表 D.帶頭結(jié)點的雙循環(huán)鏈5.在有n個結(jié)點的二叉鏈表中，非空的鏈域的個數(shù)( )A.n-1 B.2n-1C.n+1 D.2n+1對有18個元素的有序表作二分查找，則查找A［3］的比較序列的下標依次( A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，3基于鄰接表的DFS算法的時間復雜度( )A.O(n) B.O(n3)C.O(n2) D.O(n+e)8.隊列操作的原則是()A.先進先出B.后進先出C.只能進行插入D.只能進行刪除有64個結(jié)點的完全二叉樹的深度( )(根的層次為。8 B.7C.6 D.5下列數(shù)據(jù)中（ ）是非線性數(shù)據(jù)結(jié)構(gòu)。棧 B.隊列 C.完全二叉樹 D.堆二、得分 判斷題(判斷下列各題，正確的在題后括號內(nèi)打“√，錯的打“×。小題1分，共10分)1.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹( )2..隊列和棧都是操作受限的線性表( )在對帶頭結(jié)點的鏈隊列作出隊操作時，不會改變front指針的值( )若一個棧的輸入序列為123…n，其輸出序列的第一個元素為n，則其輸出序列的每個元素ai一定滿ai=n-i+1(i=1,2...,n)( )二叉樹中的葉子結(jié)點就是二叉樹中沒有左右子樹的結(jié)點( )一棵樹中的葉子結(jié)點數(shù)一定等于與其對應的二叉樹中的葉子結(jié)點數(shù)( )有向圖用鄰接矩陣表示后，頂點i的入度等于鄰接矩陣中第i行的非零元素個數(shù)( )任何一棵二叉樹中至少有一個結(jié)點的度為。( )單鏈表中的首結(jié)點就是單鏈表的第一個結(jié)點( )刪除二叉排序樹中一個結(jié)點，再重新插入上去，一定能得到原來的二叉排序樹( )三、得分 應用(每小題10分，共50分)125,(10分)33535^給定某順序字符棧，設有四個字符abcd,求出出棧序列的可能數(shù)量。 {a，b，c，d，e}135個字符設計哈夫曼編碼。要求：求出所構(gòu)造的哈夫曼樹的WPL01的規(guī)則，分別寫出與每個字符對應的編碼。對于以下二叉樹，分別寫出各種遍歷的結(jié)果。50503565545608040ABABCD--------EF GEFG四、得分 算法設計題（每小題10分,共20分）在D:\試卷文件下打開工作空間文件在Bitreelib.h中有兩個成員函intCountLeaf(BiNode<T>*bt); //求二叉樹葉子數(shù)intdept