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

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