數(shù)據(jù)結(jié)構(gòu)試題-數(shù)據(jù)結(jié)構(gòu)09

09數(shù)據(jù)結(jié)構(gòu)試卷1一個算法必須滿足的條件不包括以下選項中的A終止性B由正確步驟組成C無歧義性D正確性2選擇當(dāng)N變大時所對應(yīng)的增長率最有效率的算法專A2N2B30LOGNC5ND2N共濟(jì)網(wǎng)3下面說法不對的是A3個節(jié)點(diǎn)的二叉樹有5種不同形狀B在一個非空二叉樹中，空子樹的個數(shù)等于這個樹的節(jié)點(diǎn)數(shù)C非空完全二叉樹中，葉子結(jié)點(diǎn)只可能出現(xiàn)在最下兩層同濟(jì)D一個非空滿二叉樹中葉子的個數(shù)比內(nèi)部節(jié)點(diǎn)個數(shù)多1336260384一個基于磁盤請求的程序運(yùn)行時間最有效的節(jié)省方法是同濟(jì)大學(xué)四平路A減少遞歸調(diào)用次數(shù)B將磁盤訪問次數(shù)最小化C改進(jìn)基本操作D減少主存使用0215樹的索引方法能克服哈希方法的哪個缺點(diǎn)48號A不能處理范圍查詢B不能處理大數(shù)據(jù)集合021C不能處理更新D以上都不是彰武6有一個占4字節(jié)的指針和一個需要12字節(jié)的數(shù)據(jù)元素，當(dāng)數(shù)組在什么狀態(tài)下鏈表實(shí)現(xiàn)比基于數(shù)組的實(shí)現(xiàn)要求的空間更少A少于一半滿B少于2/3滿C少于1/3滿D少于3/4滿正門7給定數(shù)組AMN若A00位于64410，A22存儲在67610,且每個元素占一個空間“10”為十進(jìn)制表示那么元素A3310的位置是研A692B695C650D7088堆排序的時間復(fù)雜性為（N為元素的個數(shù)）。（A）ONBOLOGNCONLOGNDON29在鏈表中進(jìn)行以下哪類操作比在順序表中進(jìn)行操作效率高。（A）順序查找（B）折半查找（C）分塊查找（D）插入10廣義表（B,C），A）的表頭和表尾分別是。（A）B和A（B）B,C和ACB,C和ADB,C和A11排序方法中，依次比較未排序序列中相鄰兩個元素，如果大小關(guān)系與排序趨勢相反則交換，這樣的排序法，稱為（A）希爾排序（B）起泡排序（C）插入排序（D）選擇排序12以下數(shù)據(jù)結(jié)構(gòu)中_是非線性結(jié)構(gòu)（A）串（B）棧（C）隊列（D）無向圖13線性表采用鏈接結(jié)構(gòu)存儲時，要求內(nèi)存中可用存儲單元的地址_。（A）必須是連續(xù)的（B）可以連續(xù)，也可以不連續(xù)（C）必須是不連續(xù)的（D）要求部分連續(xù)14一棵深度為5的完全二叉樹，最少有_個結(jié)點(diǎn)。（A）16（B）15（C）31（D）6215一個棧的入棧序列是A,B,C,D,E,在任何時刻都可以出棧，則不可能的出棧順序是_。（A）ABCDE（B）ACBDE（C）EDCAB（D）CBADE二、填空30分1給定一個值排序好的整數(shù)數(shù)組，修改二叉查詢子算法，返回比K小的第一個最大整數(shù)所在的位置，K不出現(xiàn)在數(shù)組中如果數(shù)組的最小值比K大，則返回ERROR。請用C代碼填空/RETURNPOSITIONOFGREATESTELEMENTARRAYI_/在右半/數(shù)組中未發(fā)現(xiàn)_/L在小于K的第一個位置/L1,沒有值小于K2在有N個節(jié)點(diǎn)的樹中，最矮樹的高度為_,最高樹的高度為_假設(shè)一個節(jié)點(diǎn)的樹高度為1三、判斷正誤題（30分）1二叉樹只能用鏈接方式存儲。2雙向鏈表使用方便，但從存儲信息的角度來說是冗余的。3強(qiáng)連通圖就是任何兩個頂點(diǎn)之間都有路徑的有向圖。4用樹的后序遍歷和前序遍歷可以導(dǎo)出樹的中序遍歷。5存在有偶數(shù)個結(jié)點(diǎn)的非空滿二叉樹。6稀疏矩陣的常用存儲方法有三元組法和十字鏈表法。7線索二叉樹結(jié)點(diǎn)的左右指針不一定都是線索。8在順序表中，邏輯上相鄰的元素的物理位置不一定緊鄰。9隊列可視為一種先進(jìn)先出的線性表。10圖中任一個頂點(diǎn)VI的度等于其鄰接表中第I個表的結(jié)點(diǎn)個數(shù)。11堆的存儲方式是完全二叉樹的順序存儲。12圖的鄰接表是順序存儲和鏈接存儲的結(jié)合。13任何圖從其中一個給定頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷都可訪問到每一個結(jié)點(diǎn)。14B樹是平衡樹。15簡單插入排序的特點(diǎn)是關(guān)鍵字基本有序時排序速度快。四、解答題（40分）1某個二叉樹前序序列為ABECDFGHIJ且中序序列為EBCDAFHIGJ試畫出這棵二叉樹（要求寫出詳細(xì)過程）5分2已有如下值存在數(shù)組中4,2,5,8,3,6,10,14運(yùn)行建堆算法BUILDHEAP，最后得到什么樣的最小堆5分3字母及其權(quán)重的集合如下，建立哈夫曼編碼樹并對字母編碼ABCDEFGH525361011364以此頻率分布的一條含有N個字母的信息平均位長為多少10分4將8個關(guān)鍵字22,41,53,46,30,13,1,67插入到一個長度為11的哈希表中編號0到10，使用再哈希法解決沖突，要使用的哈希函數(shù)為H1和H2定義為H1K3KMOD11，H2K7KMOD101畫出所有8個關(guān)鍵字已被插入后的哈希表，描述如何使用H1和H2進(jìn)行哈希。10分5給定一個碼值為整數(shù)的記錄序列記錄到達(dá)的順序?yàn)镃,S,D,T,A,M,P,I,B,W,N,G,U,R,K,E,