考研計(jì)算機(jī)專業(yè)課復(fù)習(xí)之?dāng)?shù)據(jù)結(jié)構(gòu)

考研計(jì)算機(jī)專業(yè)課復(fù)習(xí)之?dāng)?shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)專業(yè)課復(fù)習(xí)之?dāng)?shù)據(jù)結(jié)構(gòu)Ⅰ考查目標(biāo)計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考試涵蓋數(shù)據(jù)機(jī)構(gòu)、計(jì)算機(jī)組成原理、操作系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)等學(xué)科專業(yè)基礎(chǔ)課程。要求考生比較系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的基本概念、基本原理和基本方法，能夠綜合運(yùn)用所學(xué)的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實(shí)際問題。Ⅱ考試形式和試卷結(jié)構(gòu)一、試卷滿分及考試時(shí)間本試卷滿分為150分，考試時(shí)間為180分鐘二、答題方式答題方式為閉卷、筆試三、試卷內(nèi)容結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)45分計(jì)算機(jī)組成原理45分操作系統(tǒng)35分計(jì)算機(jī)網(wǎng)絡(luò)25分四、試卷題型結(jié)構(gòu)單項(xiàng)選擇題80分（40小題，每小題2分）：數(shù)據(jù)結(jié)構(gòu)1-11題，共22分綜合應(yīng)用題70分：數(shù)據(jù)結(jié)構(gòu)41題,42題（算法設(shè)計(jì)題），共23分計(jì)算機(jī)專業(yè)課復(fù)習(xí)之?dāng)?shù)據(jù)結(jié)構(gòu)注重2023年考綱增加的內(nèi)容，屬必考內(nèi)容【緒論】(1小題)主要考察時(shí)間復(fù)雜的計(jì)算年份（年）單選題綜合題考查內(nèi)容20230涉及算法題中分析所寫的時(shí)間復(fù)雜度和空間復(fù)雜度20231題*2’涉及分析給定算法的時(shí)間復(fù)雜度；算法題中分析所寫的時(shí)間復(fù)雜度和空間復(fù)雜度20231題*2’涉及分析給定算法的時(shí)間復(fù)雜度；算法題中分析所寫的時(shí)間復(fù)雜度和空間復(fù)雜度1.（12,2分）求整數(shù)n(n≥0)階乘的算法如下，其時(shí)間復(fù)雜度是()intfact(intn){if(n<=l)return1;returnn*fact(n-1);}A.0(log2n)B.0(n)C.(nlog2n)D.0(n2)考點(diǎn)：分析給定算法的時(shí)間復(fù)雜度2.（11,2分）設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面的程序片段的時(shí)間復(fù)雜度是()x=2;while(x<n/2)x=2*x;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)考點(diǎn)：分析給定算法的時(shí)間復(fù)雜度【棧和隊(duì)列】（2小題）主要考察棧和隊(duì)列的入出及合法性1命題的形式比較靈活。2其中棧（出入棧的過程、出棧序列的合法性）和隊(duì)列的操作及其特征是重中之重。3此外，棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其特點(diǎn)、棧和隊(duì)列的常見應(yīng)用，以及數(shù)組和特殊矩陣的壓縮存儲(chǔ)都是讀者必須掌握的內(nèi)容。20232題*2’0隊(duì)列的常見應(yīng)用；棧的最大深度20232題*2’0出棧序列的合法性雙端隊(duì)列出隊(duì)序列的合法性20232題*2’0出棧序列的合法性循環(huán)隊(duì)列的特征20231題*2’0棧在表達(dá)式轉(zhuǎn)換中的應(yīng)用【?！織５娜氤黾皸５暮戏ㄐ裕⒅毓蚕?xiàng)５男再|(zhì)及操作1.（12,2分）已知操作符包括'+'、'/'、'('和')'。將中綴表達(dá)式a+b-a*((cd)/e-l>g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式ab+aCd+e/f-*-g+時(shí)，用棧來存放暫時(shí)還不能確定運(yùn)算次序的操作符，若棧初始時(shí)為空，則轉(zhuǎn)換過程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是()A.5B.7C.8D.11考點(diǎn)：棧在表達(dá)式轉(zhuǎn)換中的應(yīng)用2.（11,2分）元素a,b,c,d,e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是()A.3B.4C.5D.6考點(diǎn)：出棧序列的合法性3.（10,2分）若元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是()A.dcebfa

B.cbdaef

C.dbcaef

D.afedcb考點(diǎn)：出棧序列的合法性4.（09,2分）設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是bdcfeag，則棧S的容量至少是()A．1B.2C.3D.4考點(diǎn)：棧的最大深度【隊(duì)列】隊(duì)列的入出及合法性，隊(duì)列、循環(huán)隊(duì)列、雙端隊(duì)列的性質(zhì)及應(yīng)用1.（11,2分）已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A[0…n-1]中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭和隊(duì)尾元素若初始時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A[0]處，則初始時(shí)front和rear的值分別是()A.0,0B.0,n-1C.n-1,0D,n-1,n-1考點(diǎn)：循環(huán)隊(duì)列的特征2.（10,2分）某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，則不可能得到的順序是()A.bacde

B.dbace

C.dbcae

D.ecbad考點(diǎn)：雙端隊(duì)列出隊(duì)序列的合法性3.（09,2分）為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是()A.棧B.隊(duì)列C.樹D.圖考點(diǎn)：隊(duì)列的常見應(yīng)用【樹與二叉樹】（3個(gè)左右小題），注重考察實(shí)用性（如二叉樹的遍歷；最小平衡二叉樹的特點(diǎn)等），今年同時(shí)注重二叉樹的全部內(nèi)容（二叉樹的性質(zhì)、遍歷、平衡二叉樹等重要知識點(diǎn)）1本章不排除會(huì)有算法題涉及樹的遍歷。2樹和二叉樹的性質(zhì)、遍歷操作、轉(zhuǎn)換、存儲(chǔ)結(jié)構(gòu)和操作特性等，滿二叉樹、完全二叉樹、線索二叉樹、哈弗曼樹的定義和性質(zhì)，二叉排序樹和二叉平衡樹的性質(zhì)和操作等都是選擇題必然會(huì)涉及的內(nèi)容。年份（年）單選題綜合題考查內(nèi)容20234題*2’0給定結(jié)點(diǎn)序列的遍歷方式；二叉平衡樹的定義；完全二叉樹的性質(zhì)與結(jié)點(diǎn)特性；樹和二叉樹轉(zhuǎn)換的性質(zhì)20234題*2’0后續(xù)線索樹的定義；平衡二叉樹的插入操作；樹的性質(zhì)（度與結(jié)點(diǎn)數(shù)的關(guān)系）；哈弗曼樹的特點(diǎn)；20234題*2’0完全二叉樹的特性；二叉樹的各種遍歷序列的聯(lián)系；樹和二叉樹的轉(zhuǎn)換；二叉排序樹的性質(zhì)；20232題*2’0二叉樹的遍歷；最小平衡二叉樹的特點(diǎn)；二叉樹性質(zhì)1.（11,2分）若一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，則該二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)是()A.257B.258C.384D.385考點(diǎn)：完全二叉樹的特性2.（10,2分）在一棵度為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.41

B.82

C.113

D.122考點(diǎn)：樹的性質(zhì)（度與結(jié)點(diǎn)數(shù)的關(guān)系）3.（09,2分）已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是()A．39B.52C.111D.119考點(diǎn)：完全二叉樹的性質(zhì)與結(jié)點(diǎn)特性遍歷1.（12,2分）若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)()A.只有eB.有e、bC.有e、cD.無法確定考點(diǎn)：二叉樹的遍歷2.（11,2分）若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1，則該二叉樹的中序遍歷序列不會(huì)是()A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1考點(diǎn)：二叉樹的各種遍歷序列的聯(lián)系3.（09,2分）給定二叉樹圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3，1，7，5，6，2，4，則其遍歷方式是()A．LRNB.NRLC.RLND.RNL考點(diǎn)：給定結(jié)點(diǎn)序列的遍歷方式平衡二叉樹1.（12,2分）若平衡二叉樹的髙度為6，且所有非葉結(jié)點(diǎn)的平衡因子均為1，則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為()A.10B.20C.32D.33考點(diǎn)：最小平衡二叉樹的特點(diǎn)2.（10,2分）在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是()A.13，48

B.24，48

C.24，53

D.24，90考點(diǎn)：平衡二叉樹的插入操作3.（09,2分）下列二叉排序樹中，滿足平衡二叉樹定義的是()考點(diǎn)：二叉平衡樹的定義樹、森林與二叉樹1.（11,2分）已知一棵有2023個(gè)結(jié)點(diǎn)的樹，其葉結(jié)點(diǎn)個(gè)數(shù)為116，該樹對應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)的個(gè)數(shù)是()A.115B.116C.1895D.1896考點(diǎn)：樹和二叉樹的轉(zhuǎn)換2.（09,2分）將森林轉(zhuǎn)換為對應(yīng)的二叉樹，若在二叉樹中，結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森林中，u和v可能具有的關(guān)系是()I．父子關(guān)系II.兄弟關(guān)系III.u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系A(chǔ).只有IIB.I和IIC.I和IIID.I、II和III考點(diǎn)：樹和二叉樹轉(zhuǎn)換的性質(zhì)二叉排序樹7.（11,2分）對于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是()A.95,22,91,24,94,71B.92,20,91,34,88,35C.21,89,77,29,36,38D.12,25,71,68,33,34考點(diǎn)：二叉排序樹的性質(zhì)線索二叉樹3.（10,2分）下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是()考點(diǎn)：后續(xù)線索樹的定義哈夫曼樹6.（10,2分）對n(n大于等于2)個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的是()A.該樹一定是一棵完全二叉樹

B.樹中一定沒有度為1的結(jié)點(diǎn)C.樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)

D.樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的權(quán)值考點(diǎn)：哈弗曼樹的特點(diǎn)【圖】（3小題或1小題+1大題）今年注重圖的大題是一個(gè)方向，選擇題仍是圖本身的性質(zhì)。若不考大題，圖傾向于考選擇題，傾向于圖中知識點(diǎn)的操作過程、性質(zhì)（拓?fù)渑判?、最小生成樹、最短路徑和關(guān)鍵路徑等），弱化圖本身的概念性質(zhì)。1應(yīng)掌握圖的各種基本概念及基本性質(zhì)（度、路徑長度、回路、路徑等）、圖的存儲(chǔ)結(jié)構(gòu)（鄰接矩陣和鄰接表）及其特性、存儲(chǔ)結(jié)構(gòu)之間轉(zhuǎn)化、基于存儲(chǔ)結(jié)構(gòu)上的遍歷操作2各種應(yīng)用（拓?fù)渑判颉⒆钚∩蓸?、最短路徑和關(guān)鍵路徑等）。3圖的相關(guān)算法，通常是要求掌握其基本思想和實(shí)現(xiàn)的步驟（能動(dòng)手模擬）。年份（年）單選題綜合題考查內(nèi)容20231題*2’1題*10’無向連通圖的特性；帶權(quán)圖最短路徑的解決方法；20232題*2’0連通圖的性質(zhì)；拓?fù)渑判蛐蛄校?0231題*2’1題*8’圖的基本性質(zhì)；圖的存儲(chǔ)以及計(jì)算關(guān)鍵路徑；20234題*2’0圖（鄰接表）的廣義優(yōu)先遍歷的時(shí)間復(fù)雜度；圖鄰接矩陣與拓?fù)渑判虻年P(guān)系；Dijkstra算法求圖的最短路徑；最小生成樹的性質(zhì)；圖本身的概念性質(zhì)1.（11,2分）下列關(guān)于圖的敘述中，正確的是()①回路是簡單路徑②存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間③若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路A.僅①B僅①、②C僅③D僅①、③考點(diǎn)：圖的基本性質(zhì)2.（10,2分）若無向圖G-（V.E）中含7個(gè)頂點(diǎn)，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是()A.6

B.15

C.16

D.21考點(diǎn)：連通圖的性質(zhì)3.（09,2分）下列關(guān)于無向連通圖特性的敘述中，正確的是()I．所有頂點(diǎn)的度之和為偶數(shù)II.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1III.至少有一個(gè)頂點(diǎn)的度為1A.只有IB.只有IIC.I和IID.I和III考點(diǎn)：無向連通圖的特性拓?fù)湫蛄?.（12,2分）若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)構(gòu)是()A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一D.無法確定是否存在考點(diǎn)：圖鄰接矩陣與拓?fù)渑判虻年P(guān)系8.（10,2分）對下圖進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€(gè)數(shù)是()A.4

B.3

C.2

D.1考點(diǎn)：拓?fù)渑判蛐蛄袕V度優(yōu)先遍歷算法時(shí)間復(fù)雜度5.（12,2分）對有n個(gè)結(jié)點(diǎn)、e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是()A.0(n)B.0(e)C.0(n+e)D.0(n*e)考點(diǎn)：圖（鄰接表）的廣義優(yōu)先遍歷的時(shí)間復(fù)雜度最小生成樹性質(zhì)8.（12,2分）下列關(guān)于最小生成樹的說法中，正確的是()I.最小生成樹樹的代價(jià)唯一II.權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹中III.用普里姆（Prim)算法從不同頂點(diǎn)開始得到的最小生成樹一定相同IV.普里姆算法和克魯斯卡爾（Kmskal)算法得到的最小生成樹總不相同A.僅IB.僅IIC.僅I、IIID.僅II、IV考點(diǎn)：最小生成樹的性質(zhì)迪杰斯特拉（Dijkstra)算法7.（12,2分）如下有向帶權(quán)圖，若采用迪杰斯特拉（Dijkstra)算法求源點(diǎn)a到其他各頂點(diǎn)的最短路徑，得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b，第二條最短路徑的目標(biāo)頂點(diǎn)是C,那么到的其余各最短路徑的目標(biāo)頂點(diǎn)依次是【本題的權(quán)值和選項(xiàng)可能不準(zhǔn)確】()dbdb334fa14fa1ec5ec13A.defB.fedC.…D.…考點(diǎn)：Dijkstra算法求圖的最短路徑【查找】（1小題）性質(zhì)基本已考過，注重考察操作過程。散列（Hash）表和折半查找的操作過程，折半查找及B樹的性質(zhì)。1對于散列查找，應(yīng)掌握散列表的構(gòu)造（散列函數(shù)和裝填因子的關(guān)系）、沖突處理方法（各種方法的處理過程）、查找成功和查找失敗的平均查找長度、散列查找的特征和性能分析。2讀者還應(yīng)掌握折半查找的過程、構(gòu)造判定樹、分析查找成功和查找失敗的平均查找長度等。3B-和B+樹是本章的難點(diǎn)，考綱僅要求了解B+樹的基本概念和性質(zhì)，而B-樹則要求掌握插入、刪除和查找操作的過程（不要求掌握算法）。年份（年）單選題綜合題考查內(nèi)容20231題*2’0B樹的定義20231題*2’1題*10’折半查找的性質(zhì)；散列表的構(gòu)造和平均查找長度；20231題*2’0散列表查找的性質(zhì)；算法題中結(jié)合折半查找；20231題*2’0B樹的刪除（結(jié)點(diǎn)的合并）459.（12,2分）己知一棵3階B樹，如下圖所示。刪除關(guān)鍵字78得到一棵新B樹，其最右葉結(jié)點(diǎn)中的關(guān)鍵字是()4555651735556517357860624710372178606247103721A.60B.60,62C.62,65D.65考點(diǎn)：B樹的刪除（結(jié)點(diǎn)的合并）9.（11,2分）為提高散列（Hash）表的查找效率，可采取的正確措施是()①增大裝填因子②設(shè)計(jì)沖突少的散列函數(shù)③處理沖突時(shí)避免產(chǎn)證聚集現(xiàn)象僅①B.僅②C.僅①②D.僅②③考點(diǎn)：散列表查找的性質(zhì)9.（10,2分）已知一個(gè)長度為16的順序表L，其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個(gè)不存在的元素，則比較次數(shù)最多是()A.4

B.5

C.6

D.7考點(diǎn)：折半查找的性質(zhì)8.（09,2分）下列敘述中，不符合m階B樹定義要求的是()A．根節(jié)點(diǎn)最多有m棵子樹B.所有葉結(jié)點(diǎn)都在同一層上C．各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.葉結(jié)點(diǎn)之間通過指針鏈接考點(diǎn)：B樹的定義【排序】（2小題）傾向于排序的比較、性質(zhì)，弱化排序過程，但麻煩容易出錯(cuò)的仍會(huì)考。外部排序通常采用歸并排序方法。出題方向可能是12年大題的思路或者外排的性質(zhì)、思想、比較的總體把握。1堆排序（建堆、插入和調(diào)整）和快速排序（劃分、過程特征）是重點(diǎn)。2讀者應(yīng)深入掌握各種排序算法的思想、排序過程（能動(dòng)手模擬）和特征（初態(tài)的影響、時(shí)空復(fù)雜度、穩(wěn)定性、適用性等）。3此外，對某特定序列，讀者應(yīng)具有選擇最優(yōu)排序算法（根據(jù)排序算法特征）的能力。年份（年）單選題綜合題考查內(nèi)容20232題*2’0堆的插入和調(diào)整；各種排序算法的排序過程和特征；20232題*2’0快速排序的特征；各種排序算法的排序過程和特征；20232題*2’0快速排序的特征；堆的插入和調(diào)整；20232題*2’1題*10’各種排序算法的特征；折半插入排序和直接插入排序的比較；最佳歸并的過程（歸并排序與哈弗曼樹的綜合）；10.（12,2分）在內(nèi)部排序過程中，對尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束都至少能夠確定一個(gè)元素最終位置的方法是()I.簡單選擇排序II.希爾排序III.快速排序IV堆排序V.二路歸并排序A.僅I、III、IVB.僅I、III、VC.僅II、III、IVD.僅III、IV、V考點(diǎn)：各種排序算法的特征11.（12,2分）對一待排序序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同之處是()A.排序的總趟數(shù)B.元素的移動(dòng)次數(shù)C.使用輔助空間的數(shù)量D.元素之間的比較次數(shù)考點(diǎn)：折半插入排序和直接插入排序的比較10.（11,2分）為實(shí)現(xiàn)快速排序算法，待排序序列宜采用的存儲(chǔ)方式是()順序存儲(chǔ)B.散列存儲(chǔ)C鏈?zhǔn)酱鎯?chǔ)D索引存儲(chǔ)考點(diǎn)：快速排序的特征11.（11,2分）已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，將其再調(diào)整為大根堆，調(diào)整過程中元素之間進(jìn)行的比較次數(shù)是()A.1B.2C.4D.5考點(diǎn)：堆的插入和調(diào)整10.（10,2分）采用遞歸方式對順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是()A.遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B.每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)C.每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D.遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)考點(diǎn)：快速排序的特征11.（10,2分）對一組數(shù)據(jù)（2，12，16，88，5，10）進(jìn)行排序，若前三趟排序結(jié)果如下（）第一趟.2，12，16，5，10，88第二趟.2，12，5，10，16，88第三趟.2，5，10，12，16，88則采用的排序方法可能是()A.起泡排序

B.希爾排序C.歸并排序

D.基數(shù)排序考點(diǎn)：各種排序算法的排序過程和特征9.（09,2分）已知關(guān)鍵序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后得到的小根堆是()A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，19考點(diǎn)：堆的插入和調(diào)整10.（09,2分）若數(shù)據(jù)元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是()A．起泡排序B.插入排序C.選擇排序D.二路歸并排序考點(diǎn)：各種排序算法的排序過程和特征大題第一題：今年注重圖的大題，棧和隊(duì)列結(jié)合其他章節(jié)的大題及其他考過大題的章節(jié)的重要知識點(diǎn)和不同知識點(diǎn)【排序】最佳歸并的過程（歸并排序與哈弗曼樹的綜合）外部排序41.(12，10分）設(shè)有6個(gè)有序表A、B、C、D、E、F，分別含有10、35、40、50、60和200,個(gè)數(shù)據(jù)元素，各表中元素按升序排列。要求通過5次兩兩合并，將6個(gè)表最終合并成1個(gè)升序表，并在最壞情況下比較的總次數(shù)達(dá)到最小。請問答下列問題。(1)請寫出合并方案，并求出最壞情況下比較的總次數(shù)。(2)根據(jù)你的合并過程，描述N(N≥2)個(gè)不等長升序表的合并策略，并說明理由?？键c(diǎn)：最佳歸并的過程（歸并排序與哈弗曼樹的綜合）【圖】圖的存儲(chǔ)以及計(jì)算關(guān)鍵路徑；41.(11，8分)已知有一個(gè)6個(gè)頂點(diǎn)（頂點(diǎn)編號0～5）的有向帶權(quán)圖G，其鄰接矩陣A為上三角矩陣，它的壓縮存儲(chǔ)如下：46∞∞∞5∞∞∞43∞∞33題41表要求：(1)寫出圖G的鄰接矩陣A；(2)畫出有向帶權(quán)圖G；(3)求圖G的關(guān)鍵路徑，并計(jì)算關(guān)鍵路徑的長度。考點(diǎn)：圖的存儲(chǔ)以及計(jì)算關(guān)鍵路徑【查找】散列表的構(gòu)造和平均查找長度；41.（10，10分）將關(guān)鍵字序列（7、8、11、18、9、14）散列存儲(chǔ)到散列列表中，散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開始的一個(gè)一維數(shù)組，散列函數(shù)為：H（key）=（key×3）MODT，處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7。問題：（1）請畫出所構(gòu)造的散列表；（2）分別計(jì)算等概率情況下，查找成功和查找不成功的平均查找長度。考點(diǎn)：散列表的構(gòu)造和平均查找長度【圖】帶權(quán)圖最短路徑的解決方法；41.（09，10分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問題的方法.①設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)；②選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v，加入到最短路徑中，修改當(dāng)前頂點(diǎn)u=v；③重復(fù)步驟②，直到u是目標(biāo)頂點(diǎn)時(shí)為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明?？键c(diǎn)：帶權(quán)圖最短路徑的解決方法第二大題：【線性表】，同時(shí)注重樹的遍歷年份（年）單選題綜合題考查內(nèi)容202301題*15’查找鏈表中倒數(shù)第K個(gè)結(jié)點(diǎn)202301題*13’將數(shù)組中的序列循環(huán)左移202301題*15’求兩個(gè)有序順序表的中位數(shù)202301題*13’求兩個(gè)單鏈表的公共結(jié)點(diǎn)線性表是考研中的重中之重，近4年的算法設(shè)計(jì)題都是基于線性表的（順序表和單鏈表），這類算法題往往要求具有最優(yōu)的性能（時(shí)間和空間復(fù)雜度最優(yōu)），才能能獲得滿分。因此，應(yīng)牢固掌握線性表的各種基本操作（基于兩種存儲(chǔ)結(jié)構(gòu)），讀者在平時(shí)的學(xué)習(xí)中應(yīng)多注重積累和培養(yǎng)動(dòng)手能力。另外，需要提醒的是，算法最重要的是思想，在考場上的時(shí)間有限，在試卷上答題不一定要求結(jié)果具有實(shí)際的可執(zhí)行性。因此不必過于拘泥每一個(gè)細(xì)節(jié)。【單鏈表】42.(12，13分）假定釆用帶頭結(jié)點(diǎn)的單鏈表，如果有共同后綴，…則可共享相同的后綴存儲(chǔ)空間，例如：“l(fā)oading”和“being”，如下圖所示。題4