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

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