1、XXX職業(yè)學(xué)院2016-2017學(xué)年第二學(xué)期期末考試數(shù)據(jù)結(jié)構(gòu)試卷E(閉卷)一、單項(xiàng)選擇題（每小題2分，共 20分）1靜態(tài)查找表可以做以下哪組操作( )。（低）A、插入、刪除 B、刪除、查詢(xún)C、查詢(xún)、檢索 D、查詢(xún)、插入2對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須( )。（低）A、以順序方式存儲(chǔ)B、以鏈接方式存儲(chǔ)C、順序存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序D、鏈?zhǔn)酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序3下列查找方法中，不屬于動(dòng)態(tài)的查找方法是( )。（低）A、二分查找法 B、平衡樹(shù)法 C、散列法 D、二叉排序樹(shù)法4當(dāng)在一個(gè)有序的順序表上查找一個(gè)數(shù)據(jù)時(shí)，既可用折半查找，也可用順序查找，但前者比后者的查找速度（）。（低）A

2、必定快 B不一定C在大部分情況下要快D取決于表遞增還是遞減5平衡二叉樹(shù)中平衡因子只可能是:( )。（低）A、-1,0,+1 B、-1,+1 C、0,+1 D、-1,06對(duì)二叉排序樹(shù)進(jìn)行( )，可以得到各結(jié)點(diǎn)鍵值的遞增序列。（中）A、先序遍歷 B、中序遍歷 C、后序遍歷 D、層次遍歷 7關(guān)于靜態(tài)查找和動(dòng)態(tài)查找，說(shuō)法正確的是：( )。（中）A、靜態(tài)查找表上可以做一般的查找和插入操作B、動(dòng)態(tài)查找表上不僅可以做查找和檢索操作，還可以做插入和刪除操作C、所謂靜態(tài)查找表，是指待查的表以順序存儲(chǔ)方式存儲(chǔ)D、所謂動(dòng)態(tài)查找表，是指待查的表以動(dòng)態(tài)方式存儲(chǔ)8在對(duì)查找表的查找過(guò)程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)

3、據(jù)元素插到集合中，這種方式主要適合于（）。（中）A、靜態(tài)查找表 B、動(dòng)態(tài)查找表C、靜態(tài)查找表和動(dòng)態(tài)查找表 D、兩種表都不適合91、已知一個(gè)有序表為（11，22，33，44，55，66，77，88，99），則折半查找55需要比較（ ）次。（高）A、1 B、2 C、3 D、410在各種查找方法中，平均查找承擔(dān)與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是（ ）。（高）A、順序查找 B、折半查找 C、分塊查找 D、哈希查找二、填空題。（每空1分，共10分）1在一個(gè)查找表中，能夠唯一地確定一個(gè)記錄的關(guān)鍵字稱(chēng)為_(kāi)。（低）2如果對(duì)查找表只進(jìn)行查詢(xún)某個(gè)特定的數(shù)據(jù)元素是否在查找表中，以及查找某個(gè)特定數(shù)據(jù)元素的各種屬性?xún)煞N類(lèi)型的

4、基本操作，而不進(jìn)行插入和刪除操作數(shù)據(jù)元素的查找表稱(chēng)為_(kāi)。（低）3二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的一棵二叉樹(shù)：（1）若左子數(shù)不空，則左子樹(shù)所有結(jié)點(diǎn)的值_根結(jié)點(diǎn)的值。（2）若右子數(shù)不空，則右子樹(shù)所有結(jié)點(diǎn)的值均_根結(jié)點(diǎn)的值。（3）左右子樹(shù)又分別是二叉排序樹(shù)。（小于或大于）（中）4在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為_(kāi)。（高）三、判斷對(duì)錯(cuò)，對(duì)的劃“”，錯(cuò)的劃“”（每小題2分，共20分）1折半查找法的查找速度一定比順序查找快。 ( )（低）2連通圖的各頂點(diǎn)間均可達(dá)。 ( )（低）3有序的線性表不論如何存儲(chǔ)，都能采用折半查找。

5、( ) （低）4任何圖都能得到拓?fù)湫蛄小?( )（低）5查找分為靜態(tài)查找和動(dòng)態(tài)查找。 ( )（低）6滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。 ( )（中）7哈希查找不需要任何比較。 ( )（中）8裝填因子是哈希表的一個(gè)重要參數(shù)，它反映了哈希表的裝滿(mǎn)程度。 ( )（中）9已知一棵二叉樹(shù)的中序和后序序列能夠確定出該二叉樹(shù)的形狀。( )（高）10必須把一般樹(shù)轉(zhuǎn)換成二叉樹(shù)后才能進(jìn)行存儲(chǔ)。 ( )（高）四.簡(jiǎn)答題。（每小題8分，共16分）1、列舉幾種排序的方法（至少四種）。（低）2、簡(jiǎn)述二叉排序樹(shù)查找的過(guò)程。（中）五、應(yīng)用題。（共34分）1、給出4個(gè)葉子結(jié)點(diǎn)，設(shè)其權(quán)值分別為3、5、7、9，試構(gòu)造出哈夫曼樹(shù)，并求其帶權(quán)路徑長(zhǎng)度WPL。（8分）（低）2、設(shè)有一組初始記錄關(guān)鍵字為45,30,20,76,13,50，給出用冒泡排序法對(duì)其排序的過(guò)程。（8分）（低）3、已知一組待排序的記錄的初始序列為36, 45, 60, 92, 78, 12, 25, 45，用直接插入排序法對(duì)其進(jìn)行排序并給出排序