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

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