研究生考試題樣本及答案

一、單項(xiàng)選擇題（每題2分，共20分）1.以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先隊(duì)列？A.棧B.隊(duì)列C.堆D.鏈表答案：C2.若一棵二叉樹(shù)的前序遍歷序列為ABCDEF，中序遍歷序列為CBAEDF，則后序遍歷序列為（）A.CBEFDAB.FEDCBAC.CBEDFAD.以上都不對(duì)答案：A3.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，其地址（）A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以答案：D4.對(duì)于哈希表，沖突指的是（）A.兩個(gè)元素具有相同的序號(hào)B.兩個(gè)元素的鍵值不同，而哈希值相同C.數(shù)據(jù)元素過(guò)多D.不同鍵值對(duì)應(yīng)不同的哈希地址答案：B5.下列排序算法中，平均時(shí)間復(fù)雜度最小的是（）A.冒泡排序B.選擇排序C.插入排序D.快速排序答案：D6.已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)的邊的方法是（）A.將鄰接矩陣第i行元素全部置0B.將鄰接矩陣第i列元素全部置0C.將鄰接矩陣第i行和第i列元素全部置0D.以上都不對(duì)答案：A7.一棵完全二叉樹(shù)共有360個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中度為1的結(jié)點(diǎn)個(gè)數(shù)為（）A.0B.1C.180D.181答案：B8.以下關(guān)于算法的描述，正確的是（）A.算法可以沒(méi)有輸入，但必須有輸出B.算法必須有輸入，但可以沒(méi)有輸出C.算法必須有輸入和輸出D.算法可以既沒(méi)有輸入也沒(méi)有輸出答案：A9.若對(duì)n個(gè)元素進(jìn)行直接插入排序，在進(jìn)行第i趟排序時(shí)，假定元素r[i+1]的插入位置為r[j]，則需要移動(dòng)元素的次數(shù)為（）A.j-iB.i-jC.i-j+1D.i-j-1答案：C10.設(shè)無(wú)向圖G=(V,E)和G'=(V',E')，如果G'是G的生成樹(shù)，則下面說(shuō)法錯(cuò)誤的是（）A.G'是G的子圖B.G'是G的連通分量C.G'是G的極小連通子圖且V=V'D.G'是G的一個(gè)無(wú)環(huán)子圖答案：B二、多項(xiàng)選擇題（每題2分，共20分）1.以下屬于動(dòng)態(tài)存儲(chǔ)分配的數(shù)據(jù)結(jié)構(gòu)有（）A.棧B.堆C.鏈表D.數(shù)組答案：BC2.下列哪些操作可以在棧上進(jìn)行（）A.插入元素B.刪除元素C.取棧頂元素D.取棧底元素答案：ABC3.以下關(guān)于圖的遍歷說(shuō)法正確的是（）A.深度優(yōu)先遍歷類(lèi)似于樹(shù)的先序遍歷B.廣度優(yōu)先遍歷類(lèi)似于樹(shù)的層次遍歷C.深度優(yōu)先遍歷需要使用隊(duì)列輔助D.廣度優(yōu)先遍歷需要使用棧輔助答案：AB4.排序算法的穩(wěn)定性是指（）A.排序前相同關(guān)鍵字的元素，排序后相對(duì)次序不變B.排序算法的時(shí)間復(fù)雜度固定C.排序算法的空間復(fù)雜度固定D.排序算法在任何數(shù)據(jù)下都能正確排序答案：A5.下列數(shù)據(jù)結(jié)構(gòu)中，能高效支持查找操作的數(shù)據(jù)結(jié)構(gòu)有（）A.有序數(shù)組（二分查找）B.哈希表C.鏈表D.二叉排序樹(shù)答案：ABD6.一棵二叉樹(shù)成為二叉排序樹(shù)的條件是（）A.左子樹(shù)中結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值B.右子樹(shù)中結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值C.左、右子樹(shù)也分別是二叉排序樹(shù)D.所有結(jié)點(diǎn)的值都不相同答案：ABC7.以下哪些算法設(shè)計(jì)技術(shù)屬于貪心算法的應(yīng)用（）A.哈夫曼編碼B.迪杰斯特拉（Dijkstra）算法C.克魯斯卡爾（Kruskal）算法D.動(dòng)態(tài)規(guī)劃算法答案：ABC8.關(guān)于隊(duì)列的描述，正確的有（）A.先進(jìn)先出B.先進(jìn)后出C.插入操作在隊(duì)尾進(jìn)行D.刪除操作在隊(duì)頭進(jìn)行答案：ACD9.下列哪些是衡量算法性能的指標(biāo)（）A.時(shí)間復(fù)雜度B.空間復(fù)雜度C.正確性D.可讀性答案：ABCD10.對(duì)于線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以下說(shuō)法正確的是（）A.順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)密度大B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)便于插入和刪除操作C.順序存儲(chǔ)結(jié)構(gòu)查找速度快D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)需要額外的空間存儲(chǔ)指針答案：ABCD三、判斷題（每題2分，共20分）1.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（×）2.一棵滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)。（√）3.快速排序在任何情況下的時(shí)間復(fù)雜度都是O(nlogn)。（×）4.哈希表的平均查找長(zhǎng)度與哈希表的裝填因子有關(guān)。（√）5.圖的鄰接矩陣表示法只適用于有向圖。（×）6.棧和隊(duì)列都是特殊的線性表。（√）7.二叉樹(shù)的前序遍歷和后序遍歷可以唯一確定一棵二叉樹(shù)。（×）8.貪心算法一定能得到問(wèn)題的最優(yōu)解。（×）9.對(duì)n個(gè)元素進(jìn)行冒泡排序，最少需要比較n-1次。（√）10.平衡二叉樹(shù)的左右子樹(shù)高度差的絕對(duì)值不超過(guò)1。（√）四、簡(jiǎn)答題（每題5分，共20分）1.簡(jiǎn)述棧和隊(duì)列的主要區(qū)別。答案：棧是后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，操作在棧頂進(jìn)行；隊(duì)列是先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，插入在隊(duì)尾，刪除在隊(duì)頭。2.簡(jiǎn)述哈希表的基本原理。答案：哈希表利用哈希函數(shù)將關(guān)鍵字映射到一個(gè)有限的地址空間中。通過(guò)計(jì)算關(guān)鍵字的哈希值找到存儲(chǔ)位置，若發(fā)生沖突則采用開(kāi)放定址法、鏈地址法等方法解決。3.簡(jiǎn)述二叉排序樹(shù)的性質(zhì)。答案：二叉排序樹(shù)左子樹(shù)所有結(jié)點(diǎn)值小于根結(jié)點(diǎn)值，右子樹(shù)所有結(jié)點(diǎn)值大于根結(jié)點(diǎn)值，且左右子樹(shù)也分別是二叉排序樹(shù)。它可高效支持查找、插入和刪除操作。4.簡(jiǎn)述迪杰斯特拉（Dijkstra）算法的基本思想。答案：用于求圖中某一頂點(diǎn)到其他各頂點(diǎn)的最短路徑。從起始頂點(diǎn)開(kāi)始，逐步擴(kuò)展，每次選擇距離起始頂點(diǎn)最近且未確定最短路徑的頂點(diǎn)，更新其鄰接頂點(diǎn)的距離，直到所有頂點(diǎn)的最短路徑確定。五、討論題（每題5分，共20分）1.討論排序算法在不同應(yīng)用場(chǎng)景下的選擇。答案：數(shù)據(jù)量小且接近有序時(shí)，插入排序較合適；數(shù)據(jù)量較大且要求穩(wěn)定性，歸并排序可選；數(shù)據(jù)量極大且對(duì)穩(wěn)定性無(wú)要求，快速排序通常較好；對(duì)空間要求高，選擇原地排序算法如堆排序。2.討論圖的存儲(chǔ)結(jié)構(gòu)（鄰接矩陣、鄰接表等）的優(yōu)缺點(diǎn)。答案：鄰接矩陣優(yōu)點(diǎn)是直觀、易實(shí)現(xiàn)，適合稠密圖；缺點(diǎn)是空間復(fù)雜度高。鄰接表優(yōu)點(diǎn)是空間效率高，適合稀疏圖；缺點(diǎn)是遍歷邊效率低，不直觀。3.討論動(dòng)態(tài)規(guī)劃算法的基本要素和適用場(chǎng)景。答案：基本要素有最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問(wèn)題。適用于問(wèn)題可分解為相互關(guān)聯(lián)子問(wèn)題，且