嚴蔚敏《數(shù)據(jù)結構》考研C語言版考研筆記與考研真題

嚴蔚敏《數(shù)據(jù)結構》考研C語言版考研筆記與考研真第一部分考研真題精選一、單項選擇題1若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧操作，則不可能得到的出棧序列是（ ）。［計算機統(tǒng)考（408）2010年研］【答案】D查看答案【解析】4個選項所給序列的進、出棧操作序列分別為：選項A：Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop選項B：Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop選項C：Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop選項D：Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop按照題目要求，不允許連續(xù)三次進行退棧操作，所以選項D所給序列為不可能得到的出棧）1順序。2若一棵二叉樹的前序遍歷序列為a,e,b,d,c,后序遍歷序列為b,c,d,e,a，則根結點的孩子結點（ ）。［計算機統(tǒng)考（408）2012年研］A.只有eB.有e、bC.有e、cD.無法確定【答案】A查看答案【解析】由題目可知，若一棵二叉樹的前序遍歷序列為a,e,b,d,c,后序遍歷序列為b,c,d,e,a,其中a為這棵二叉樹的根結點，接下來，在前序遍歷的第二個結點為e，而后序遍歷的倒數(shù)第二個結點為e,說明a的孩子結點只有e。3循環(huán)隊列放在一維數(shù)組A［0..M-1］中，endl指向隊頭元素，end2指向隊尾元素的后一個位置。假設隊列兩端均可進行入隊和出隊操作，隊列中最多能容納M-1個元素。初始時為空，下列判斷隊空和隊滿的條件中，正確的是（ ）。［計算機統(tǒng)考（408）2014年研］A.隊空：end1二二end2;隊滿：end1二二（end2+1）modMB.隊空：end1二二end2;隊滿：end2二二（end1+1）mod（M-1）C.隊空：end2二二（end1+1）modM;隊滿：end1==（end2+1）modMD.隊空：end1二二（end2+1）modM;隊滿：end2二二（end1+1）mod（M-1)【答案】A查看答案【解析】在循環(huán)隊列中，在少用一個元素空間的前提下，可約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等，則隊滿。而隊空的條件還是首尾指針是否相等。4已知關鍵字序列5,8,12,19,28,20，15,22是小根堆（最小堆），插入關鍵字3，調整后的小根堆是（ ）。［計算機統(tǒng)考（408）2009年研］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【答案】A查看答案【解析】在堆中插入一個元素后，將不再滿足堆的性質。為了使其成為新堆，需要重新調整剩余元素的位置。具體過程如圖（1）?（5）所示，（1）為原堆，（2）為插入3后，（3）、（4）為調整過程，（5）為調整后的小根堆。

282015222A2820C5))。［計算機統(tǒng)考(408)5下列選項中，不能構成折半查找中關鍵字比較序列的是(2015年研］282015222A2820C5))。［計算機統(tǒng)考(408)A.500,200,450,180B.500,450,200,180C.180,500,200,450D.180,200,500,450【答案】A查看答案【解析】折半查找也稱二分查找（引narySearch），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。折半查找的過程是：先確定待查找記錄所在的范圍，然后逐步縮小范圍直到找到或找不到該記錄為止。折半查找的關鍵字序列滿足：對每一個關鍵字，其后面的所有關鍵字序列或者都小于等于該關鍵字或者都大于等于該關鍵字。A項錯誤，第三次比較的關鍵字為450，說明待查關鍵字位于200?450間，所以第四次比較時不會遇到關鍵字180。6已知字符串S為"abaabaabacacaabaabcc"，模式串t為"abaabc"，采用KMP算法進行匹配，第一次出現(xiàn)“失配"（s[i]!=t[i]）時，i刁二5,則下次開始匹配時，i和j的值分別是（ ）。[計算機統(tǒng)考（408）2015年研]A.i=1,j=0B.i=5,j=0C.i=5,j=2D.i=6,j=2【答案】C查看答案【解析】模式匹配（KMP）算法對普通的暴力匹配的改進在于：每當匹配過程中匹配失敗時，主串（本題為S）的指針（i）不需要回溯，而是利用已經得到的“部分匹配”的結果將模式串（t）向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較。模式串“滑動”的距離是由模式串（t）本身決定的，即t的子串t[0…j-1］中前綴串和后綴串相等的最長長度。本題中第一次失配i=5,字串為"abaab”，其相等且最長的前后綴為“ab”，一次下一個j=2。7下列關于無向連通圖特性的敘述中，正確的是（ ）。［計算機統(tǒng)考（408）2009年研］.所有的頂點的度之和為偶數(shù).邊數(shù)大于頂點個數(shù)減1.至少有一個頂點的度為1A.只有IB.只有IIC.I和ID.I和I【答案】A查看答案【解析】在圖中，頂點的度TD（Vi）之和與邊的數(shù)目滿足關系式：

之煙匕）=2?2=1其中，n為圖的總結點數(shù),e為總邊數(shù)。因此，I項正確。對于I、I項中的特性不是一般無向連通圖的特性，可以輕松地舉出反例。“至少有一個頂點的度為1”的反例如下圖（1）所示，“邊數(shù)大于頂點個數(shù)減1”的反例如下圖（2）所示。8下列敘述中，不符合m階B樹定義要求的是（ ）。［計算機統(tǒng)考（408）2009年研］A.根結點最多有m棵子樹B.所有葉結點都在同一層上C.各結點內關鍵字均升序或降序排列D.葉結點之間通過指針鏈接【答案】D查看答案【解析】B樹就是指B-樹。根據(jù)B-樹的定義，m階B-樹中每個結點最多有m個分支，因此，根結點最多有m棵子樹，A項正確；B-樹中所有葉結點都在最底層，位于同一層，B項正確；結點內各關鍵字互不相等且有序排列，C項正確。但是，所有葉子結點之間通過指針鏈接，是B+樹的定義，而B-樹中沒有。因此，D項是錯誤的。9排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結束時都至少能夠確定一個元素最終位置的方法是（）。［計算機統(tǒng)考（408）2012年研］.簡單選擇排序.希爾排序.快速排序W.堆排V.二路歸并排序A.僅I、I、WB.僅I、II、IC.僅I、I、WD.僅I、MV【答案】A查看答案【解析】其中簡單選擇排序、堆排序屬于選擇類排序，每一趟排序結束時將確定最大（或最?。╆P鍵字所在的位置?？焖倥判蛎恳惶伺判蚪Y束時將確定基準關鍵字所在的位置。希爾排序、二路歸并排序每一趟排序結束時不一定能確定一個元素的最終位置。第1章緒論1.1復習筆記一、什么是數(shù)據(jù)結構數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等的學科。二、基本概念和術語1數(shù)據(jù)數(shù)據(jù)是對客觀事物的符號表示，是計算機科學中所有能輸入到計算機中并能被計算機程序處理的符號的總稱。2數(shù)據(jù)元素數(shù)據(jù)元素是數(shù)據(jù)的基本單位。3數(shù)據(jù)對象數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。4數(shù)據(jù)結構數(shù)據(jù)結構是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。（1）數(shù)據(jù)結構的基本結構根據(jù)數(shù)據(jù)元素之間關系的不同特性，通常有下列四類基本結構：①集合。數(shù)據(jù)元素屬于“同一個集合”，并無其他復雜關系。②線性結構。數(shù)據(jù)元素之間存在一個對一個的關系。③樹形結構。數(shù)據(jù)元素之間存在一個對多個的關系。④圖狀結構或網(wǎng)狀結構。數(shù)據(jù)元素之間存在多個對多個的關系?！咀⒁狻繀^(qū)分這四種基本結構可以根據(jù)元素間的對應關系。如圖1-1所示為上述四類基本結構的關系圖。

(2)數(shù)據(jù)結構的形式定義數(shù)據(jù)結構的形式定義為：Data_Structure=(D,S)其中：D表示數(shù)據(jù)元素的有限集，S表示D上關系的有限集。(3)數(shù)據(jù)結構在計算機中的表示數(shù)據(jù)結構包括數(shù)據(jù)元素的表示和關系，在計算機中稱為數(shù)據(jù)的物理結構(又稱存儲結構)。其中，關系有兩種表示方法：JI順序映象和非JI順序映象。這兩種表示方法對應兩種存儲結構：)1順序存儲結構和鏈式存儲結構。a.順序映象：用相對位置來表示數(shù)據(jù)元素之間的邏輯關系。b.非順序映象：用指針表示數(shù)據(jù)元素之間的邏輯關系。5數(shù)據(jù)類型數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。6抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（ADT）由一個值域和定義在該值域上的一組操作組成。【注意】抽象數(shù)據(jù)類型是對數(shù)據(jù)類型架構的一種全局體現(xiàn)，使我們能夠更加清晰地看待某一數(shù)據(jù)類型。7多形數(shù)據(jù)類型多形數(shù)據(jù)類型是指其值的成分不確定的數(shù)據(jù)類型。8數(shù)據(jù)操作的類型基本的操作主要有：（1）插入（2）刪除（3）更新（4）查找（5）排序從操作的特性來分，所有的操作可以歸結為兩類：加工型操作：改變了（操作之前的）結構的值；引用型操作：即不改變結構的值，只是查詢或求得結構的值。上述5種操作中除“查找”為引用型操作外，其余都是加工型操作。9算法【定義】算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每條指令表示一個或多個操作。【特性】（1）有窮性（2）確定性（3）可行性（4）輸入（5）輸出【注意】在考試中這五個特性可能出現(xiàn)在選擇或者填空題中（通常直接考察其名稱）。三、抽象數(shù)據(jù)類型的表示與實現(xiàn)四、算法和算法分析1算法的描述算法需要用一種語言來描述，程序框圖，程序設計語言等都能對算法進行描述?！咀⒁狻靠佳泄P試中，如果在對應語法不確定的情況下，使用偽碼通常也是可以的。2算法設計的要求（1）正確性（2）可讀性（3）健壯性（4）效率與低存儲量需求3算法效率的度量算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行時所消耗的時間來度量，度量一個程序的執(zhí)行時間通常有兩種方法：(1)事后統(tǒng)計(2)事前分析估算①事先考慮消耗時間的因素②時間復雜度時間復雜度是關于問題規(guī)模的函數(shù)，通常用O表示，常見