考研《數(shù)據(jù)結(jié)構(gòu)》嚴蔚敏C語言版配考研真題庫

考研《數(shù)據(jù)結(jié)構(gòu)》嚴蔚敏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所給序列為不可能得到的出棧順序。2若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點的孩子結(jié)點（）。[計算機統(tǒng)考（408）2012年研]A．只有eB．有e、bC．有e、cD．無法確定【答案】A查看答案【解析】由題目可知，若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，其中a為這棵二叉樹的根結(jié)點，接下來，在前序遍歷的第二個結(jié)點為e，而后序遍歷的倒數(shù)第二個結(jié)點為e，說明a的孩子結(jié)點只有e。3循環(huán)隊列放在一維數(shù)組A[0..M－1]中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設(shè)隊列兩端均可進行入隊和出隊操作，隊列中最多能容納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已知關(guān)鍵字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后的小根堆是（）。[計算機統(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查看答案【解析】在堆中插入一個元素后，將不再滿足堆的性質(zhì)。為了使其成為新堆，需要重新調(diào)整剩余元素的位置。具體過程如圖（1）～（5）所示，（1）為原堆，（2）為插入3后，（3）、（4）為調(diào)整過程，（5）為調(diào)整后的小根堆。5下列選項中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是（2015年研]）。[計算機統(tǒng)考（408）A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，450【答案】A查看答案【解析】折半查找也稱二分查找（BinarySearch），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。折半查找的過程是：先確定待查找記錄所在的范圍，然后逐步縮小范圍直到找到或找不到該記錄為止。折半查找的關(guān)鍵字序列滿足：對每一個關(guān)鍵字，其后面的所有關(guān)鍵字序列或者都小于等于該關(guān)鍵字或者都大于等于該關(guān)鍵字。A項錯誤，第三次比較的關(guān)鍵字為450，說明待查關(guān)鍵字位于200～450間，所以第四次比較時不會遇到關(guān)鍵字180。6已知字符串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”，采用KMP算法進行匹配，第一次出現(xiàn)“配失”（s[i]!＝t[i]）時，i＝j(luò)＝5，則下次開始匹配時，i和j的值分別是（A．i＝1，j＝0）。[計算機統(tǒng)考（408）2015年研]B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝2【答案】C查看答案【解析】模式匹配（KMP）算法對普通的暴力匹配的改進在于：每當匹配過程中匹配失敗時，主串（本題為S）的指針（i）不需要回溯，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式串（t）向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較。模式串“滑動”的距離是由模式串（t）本身決定的，即t的子串t[0…j－1]中前綴串和后綴串相等的最長長度。本題中第一次失配i＝5，字串為“abaab”，其相等且最長的前后綴為“ab”，一次下一個j＝2。7下列關(guān)于無向連通圖特性的敘述中，正確的是（）。[計算機統(tǒng)考（408）2009年研]Ⅰ．所有的頂點的度之和為偶數(shù)Ⅱ．邊數(shù)大于頂點個數(shù)減1Ⅲ．至少有一個頂點的度為1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ【答案】A查看答案【解析】在圖中，頂點的度TD（Vi）之和與邊的數(shù)目滿足關(guān)系式：其中，n為圖的總結(jié)點數(shù)，e為總邊數(shù)。因此，Ⅰ項正確。對于Ⅱ、Ⅲ項中的特性不是一般無向連通圖的特性，可以輕松地舉出反例?！爸辽儆幸粋€頂點的度為1”的反例如下圖（1）所示，“邊數(shù)大于頂點個數(shù)減1”的反例如下圖（2）所示。8下列敘述中，不符合m階B樹定義要求的是（年研]）。[計算機統(tǒng)考（408）2009A．根結(jié)點最多有m棵子樹B．所有葉結(jié)點都在同一層上C．各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列D．葉結(jié)點之間通過指針鏈接【答案】D查看答案【解析】B樹就是指B－樹。根據(jù)B－樹的定義，m階B－樹中每個結(jié)點最多有m個分支，因此，根結(jié)點最多有m棵子樹，A項正確；B－樹中所有葉結(jié)點都在最底層，位于同一層，B項正確；結(jié)點內(nèi)各關(guān)鍵字互不相等且有序排列，C項正確。但是，所有葉子結(jié)點之間通過指針鏈接，是B＋樹的定義，而B－樹中沒有。因此，D項是錯誤的。9排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時都至少能夠確定一個元素最終位置的方法是（[計算機統(tǒng)考（408）2012年研]）。Ⅰ．簡單選擇排序Ⅱ．希爾排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．