數(shù)據(jù)結(jié)構(gòu)總結(jié)試題5[教育試題]

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

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

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

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

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