數(shù)據(jù)結(jié)構(gòu)本科A.doc

數(shù)據(jù)結(jié)構(gòu)試題3武漢大學(xué)計(jì)算機(jī)學(xué)院 “數(shù)據(jù)結(jié)構(gòu)”考試試題（A）要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號(hào)。每張答題紙都要寫上姓名和學(xué)號(hào)。一、單項(xiàng)選擇題（共20小題，每小題2分，共40分）1. 下列各選項(xiàng)中屬于邏輯結(jié)構(gòu)的是 。A.哈希表B.有序表C.單鏈表D.順序表2. 對(duì)于數(shù)據(jù)結(jié)構(gòu)，以下敘述中不正確的是 。A.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式和內(nèi)容無關(guān)B.數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系C.數(shù)據(jù)元素是數(shù)據(jù)的基本單位D.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位3. 某算法的時(shí)間復(fù)雜度為O(n2)，表明該算法的 。A.問題規(guī)模是n2B.執(zhí)行時(shí)間等于n2C.執(zhí)行時(shí)間與n2成正比D.問題規(guī)模與n2成正比4. 通常在單鏈表中增加一個(gè)頭節(jié)點(diǎn)，其目的是為了 。A.使單鏈表至少有一個(gè)節(jié)點(diǎn)B.標(biāo)識(shí)表節(jié)點(diǎn)中首節(jié)點(diǎn)的位置C.方便單鏈表運(yùn)算的實(shí)現(xiàn)D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)5. 刪除某個(gè)雙鏈表中的一個(gè)節(jié)點(diǎn)（非首、尾節(jié)點(diǎn)），需要修改 個(gè)指針域。A.1B.2C.3D.46. 棧和隊(duì)列是兩種不同的數(shù)據(jù)結(jié)構(gòu)，但它們中的元素具有相同的 。A.抽象數(shù)據(jù)類型B.邏輯結(jié)構(gòu)C.存儲(chǔ)結(jié)構(gòu)D.運(yùn)算7. 元素a、b、c、d、e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直到所有的元素都出棧，則所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是 。A.3B.4C.5D.68. 設(shè)環(huán)形隊(duì)列中數(shù)組的下標(biāo)是0N-1，其頭尾指針分別為f和r（f指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，r指向隊(duì)尾元素的位置），則其元素個(gè)數(shù)為 。A.r-fB.r-f-1C.(r-f)N+1D.(r-f+N)N9. 已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A0.n-1中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時(shí)隊(duì)列空，且要求第一個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A0處，則初始時(shí)front和rear的值分別是 。A.0，0B.0，n-1C.n-1，0D.n-1，n-110. 對(duì)于n階（n2）對(duì)稱矩陣，采用壓縮方法以行序優(yōu)先存放到內(nèi)存中，則需要 個(gè)存儲(chǔ)單元。A.n(n+1)/2B.n(n-1)/2C.n2D.n2/211. 一棵度為4的樹T中，若有20個(gè)度為4的節(jié)點(diǎn)，10個(gè)度為3的節(jié)點(diǎn)，1個(gè)度為2的節(jié)點(diǎn)，10個(gè)度為1的節(jié)點(diǎn)，則樹T的葉子節(jié)點(diǎn)個(gè)數(shù)是 。A.41B.82C.113D.12212. 一個(gè)具有n（n2）個(gè)頂點(diǎn)的無向圖，至少有 個(gè)連通分量，最多有 個(gè)連通分量。A.0B.1C.n-1D.n13. 含有n（n2）個(gè)頂點(diǎn)的無向圖的鄰接矩陣必然是一個(gè) 。A.對(duì)稱矩陣B.零矩陣C.上三角矩陣D.對(duì)角矩陣14. 對(duì)如圖1所示的無向圖，從頂點(diǎn)A出發(fā)得到的廣度優(yōu)先序列可能是 。A.ABECDB.ACBDEC.ACDBED.ABDEC圖1 一個(gè)無向圖15. 設(shè)有100個(gè)元素的有序順序表，用折半查找時(shí)，成功時(shí)最大的比較次數(shù)是 。A.25B.50C.10D.716. 已知一個(gè)長(zhǎng)度為16的順序表，其元素按關(guān)鍵字有序排序，若采用折半查找法查找一個(gè)不存在的元素，則平均關(guān)鍵字比較的次數(shù)是 。A.70/17B.70/16C.60/17D.60/1617. 以下關(guān)于m階B-樹的敘述中正確的是 。A.每個(gè)節(jié)點(diǎn)至少有兩棵非空子樹B.樹中每個(gè)節(jié)點(diǎn)至多有m/2-1個(gè)關(guān)鍵字C.所有葉子節(jié)點(diǎn)均在同一層上D.當(dāng)插入一個(gè)關(guān)鍵字引起B(yǎng)-樹節(jié)點(diǎn)分裂時(shí)，樹增高一層18. 為提高散列（哈希）表的查找效率，可以采取的正確措施是 。.增大裝填（載）因子.設(shè)計(jì)沖突（碰撞）少的散列函數(shù).處理沖突（碰撞）時(shí)避免產(chǎn)生聚集（堆積）現(xiàn)象A.僅B.僅C.僅、D.僅、19. 數(shù)據(jù)序列8,9,10,4,5,6,20,1,2只能是 的兩趟排序后的結(jié)果。A.簡(jiǎn)單選擇排序B.冒泡排序C.直接插入排序D.堆排序20. 用某種排序方法對(duì)順序表24,88,21,48,15,27,69,35,20進(jìn)行排序，各趟元素序列的變化情況如下：（1）24,88,21,48,15,27,69,35,20（2）20,15,21,24,48,27,69,35,88（3）15,20,21,24,35,27,48,69,88（4）15,20,21,24,27,35,48,69,88則所采用的排序方法是 。A.快速排序B.簡(jiǎn)單選擇排序C.直接插入排序D.歸并排序二、問答題（共3小題，每小題10分，共30分）1. 一棵二叉排序樹按先序遍歷得到的關(guān)鍵字序列為：(50,38,30,45,40,48,70,60,75,80)?；卮鹨韵聠栴}： （1）畫出該二叉排序樹。（2）求在等概率條件下的查找成功的平均查找長(zhǎng)度。2. 有一個(gè)無向帶權(quán)圖如圖2所示，采用Dijkstra算法求頂點(diǎn)0到其他頂點(diǎn)的最短路徑和最短路徑長(zhǎng)度，要求給出求解過程（即給出求最短路徑中各步驟的S、dist和path值）。圖2 一個(gè)無向圖3. 簡(jiǎn)要敘述堆和二叉排序樹的區(qū)別，并給出關(guān)鍵字序列3,26,12,61,38,40,97,75,53,87調(diào)整為大根堆后的結(jié)果（直接畫出調(diào)整后的大根堆）。三、算法設(shè)計(jì)題（共3小題，每小題10分，共30分）1有一個(gè)線性表(a1,a2,an)，采用帶頭節(jié)點(diǎn)的單鏈表L存儲(chǔ)，設(shè)計(jì)一個(gè)就地算法將其所有元素逆置。所謂就地算法是指算法的空間復(fù)雜度為O(1)。2假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)