數(shù)據(jù)結(jié)構(gòu)與算法-模擬試題3及答案

數(shù)據(jù)結(jié)構(gòu)與算法-模擬試題3一、單項選擇題（每個題只有一個答案是正確的，請將正確的答案填寫到括號內(nèi)。本題共15個小題，每小題3分，共45分）1.下面的說法正確的是（）。A.數(shù)據(jù)結(jié)構(gòu)可以分成邏輯結(jié)構(gòu)和線性結(jié)構(gòu)B.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示C.從邏輯結(jié)構(gòu)角度數(shù)據(jù)結(jié)構(gòu)可以分為集合、線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)四類D.數(shù)據(jù)的存儲結(jié)構(gòu)是從具體問題抽象出來的數(shù)學模型2.線性表采用鏈式存儲時，存儲空間（）。A．必須是不連續(xù)的B．連續(xù)與否均可C．必須是連續(xù)的D．和頭結(jié)點的存儲地址相連續(xù)3.順序循環(huán)隊列容量為20，隊頭表示第一個元素的位置，隊尾表示最后一個元素的下一個位置，當隊頭為12，隊尾為5的時候，隊列中共有（）個元素。A.15B.14C.12D.134.設(shè)計一個判別表達式中括號是否配對的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A.順序表 B.鏈表 C.隊列 D.棧5.下列有關(guān)串的操作中，（）不是串的常用操作。A.連接（concat）B.求子串（substring）C.插入（insert）D.求長度(length)6.廣義表GL=(a,(a))的表頭是（）。A.a B.(a) C.() D.((a))7.二叉樹高度為k，第1層到第k-1層每層都是滿的，第k層結(jié)點數(shù)不滿，但該層結(jié)點從左到右滿放，則該二叉樹為（）。A.斜樹 B.有序樹 C.滿二叉樹 D.完全二叉樹8.將一棵樹轉(zhuǎn)換為二叉樹后，該轉(zhuǎn)換后的二叉樹的特點是（）。A.沒有右子樹 B.沒有左子樹 C.左右子樹都有 D.每層上只有一個結(jié)點9.關(guān)于有向圖的的說法錯誤的是（）。A.有向圖中頂點v的入度(indegree)是以頂點v為終點（弧頭）的弧的數(shù)目B.有向圖中頂點v的出度(outdegree)是以頂點v為始點（弧尾）的弧的數(shù)目C.有向圖中各頂點的入度之和等于各頂點的出度之和D.有向圖中各頂點入度之和等于弧數(shù)e的2倍10.在無向圖的鄰接表存儲結(jié)構(gòu)中插入一個頂點和一條邊，不需要進行的操作是（）。A.在頂點表最后插入頂點信息B.找到邊的第一個頂點的對應邊鏈表，插入邊信息C.找到邊的第二個頂點的對應邊鏈表，再次插入邊信息D.把頂點表重新排序 11.如下圖一棵平衡二叉排序樹插入元素10后發(fā)生失衡，則對其應作（）型調(diào)整以使其平衡。A.LLB.LRC.RLD.RR12.設(shè)一組初始記錄關(guān)鍵字序列為(15，18，83，35，24，47，50，62，90)，則利用順序查找方法查找關(guān)鍵字24需要比較的關(guān)鍵字個數(shù)為（）。 A.1 B.5 C.9 D.1013.下面有關(guān)排序的說法正確的是（）。A.所有的排序算法都是穩(wěn)定的B.排序算法中冒泡排序性能最好C.堆排序是不穩(wěn)定的排序算法D.簡單選擇排序是穩(wěn)定的排序算法14.對n個元素序列進行排序，如果利用二路歸并方法進行排序，其時間復雜度和空間復雜度分別是（）。A.O(nlog2n)，O(1)B.O(n)，O(1)C.O(nlog2n)，O(n)D.O(n2)，O(n)15.當整體最優(yōu)解可以通過局部最優(yōu)選擇得到時，該問題一般可以采用（）來求解。A.貪心算法B.回溯算法C.分治算法D.折半查找算法二、判斷題（正確的在括號內(nèi)打上“√”，錯誤的打上“╳”。本題共15個小題，每小題2分，共30分）16.一般來說，遞歸只需要有遞歸方程就行了。（）17.棧只能在棧底端進行插入刪除。（）18.順序表在進行插入元素時不需要移動元素。（）19.隊列的存儲結(jié)構(gòu)只有順序存儲結(jié)構(gòu)。（）20.稀疏矩陣壓縮存儲時需要存儲非零元素及其位置信息，不需要存儲零元素。（）21.空串的長度為零。（）22.二叉樹沒有順序存儲結(jié)構(gòu)。（）23.線索二叉樹只能加中序線索。（）24.連通圖的最小生成樹可以有不同的形態(tài)。（）25.帶環(huán)圖進行拓撲排序后，序列中不能包含所有頂點。（）26.折半查找是在有序順序表上進行的查找。（）27.散列查找中沖突處理方法有開放地址法和鏈地址法。（）28.當序列已經(jīng)排好序時，快速排序退化為冒泡排序。（）29.直接插入排序是不穩(wěn)定的排序算法。（）30.回溯法是在搜索過程中逐步構(gòu)造解空間樹的。（）綜合題（本題共5個小題，每題5分，共25分）31.請根據(jù)程序注釋為下面程序中空缺的①和②位置選擇正確的語句。List<String>list=newLinkedList<String>();//創(chuàng)建鏈表list.add("AAA");//添加數(shù)據(jù)AAA到線性表中l(wèi)ist.①;//添加數(shù)據(jù)BBB到線性表中l(wèi)ist.②;//獲?。ú⒉粍h除）下標為1的元素A.remove(1);B.add("BBB")C.set(“BBB”)D.get(1)32.請根據(jù)程序注釋為下面程序中空缺的①和②位置選擇正確的語句。voidinOrder(BinaryNode<E>p)//中序次序遍歷以p結(jié)點為根的子二叉樹{if(p!=null){inOrder(①);//中序次序遍歷左子樹System.out.print(p.data+"");inOrder(②);//中序次序遍歷右子樹}}A.p.leftB.pC.p.rightD.root33.如下圖所示有向圖，從1頂點開始，其深度優(yōu)先遍歷序列為①，廣度優(yōu)先遍歷序列為②。A.(123456)B.(123564)C.(125346)D.(125634)34.設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用折半查找過程中第一個比較的關(guān)鍵字是①，查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為②。① A.13 B.50 C.47 D.90②A.1 B.2 C.3 D.435.設(shè)一組初始記錄關(guān)鍵字序列為{49，27，38，13，97，76，47}，對其進行堆排序（最小堆），則調(diào)整好的初始堆為（）。數(shù)據(jù)結(jié)構(gòu)與算法-模擬試題3-參考答案及評分標準一、單項選擇題（每個題只有一個答案是正確的，請將正確的答案填寫到括號內(nèi)。本題共15個小題，每小題3分，共45分）1C2B3D4D5C6A7D8A9D10D11A12B13C14C15A二、判斷題（正確的在括號內(nèi)打上“√”，錯誤的打上“╳”。本題共15個小題，每小題2分，共30分）16╳1