嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)》（C語言版）配套題庫【考研真題精選（部分視頻講解）＋章節(jié)題庫】

第一部分考研真題精選（部分視頻講解）

一、單項(xiàng)選擇題

1若元素a，b，c，d，e，f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行退棧操作，則不可能得到的出棧序列是（）。[計(jì)算機(jī)統(tǒng)考（408）2010年研]

A．d，c，e，b，f，a

B．c，b，d，a，e，f

C．b，c，a，e，f，d

D．a(chǎn)，f，e，d，c，b

【答案】D查看答案

【解析】4個選項(xiàng)所給序列的進(jìn)、出棧操作序列分別為：

選項(xiàng)A：Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop

選項(xiàng)B：Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop

選項(xiàng)C：Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop

選項(xiàng)D：Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop

按照題目要求，不允許連續(xù)三次進(jìn)行退棧操作，所以選項(xiàng)D所給序列為不可能得到的出棧順序。

2若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。[計(jì)算機(jī)統(tǒng)考（408）2012年研]

A．只有e

B．有e、b

C．有e、c

D．無法確定

【答案】A查看答案

【解析】由題目可知，若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，其中a為這棵二叉樹的根結(jié)點(diǎn)，接下來，在前序遍歷的第二個結(jié)點(diǎn)為e，而后序遍歷的倒數(shù)第二個結(jié)點(diǎn)為e，說明a的孩子結(jié)點(diǎn)只有e。

3循環(huán)隊(duì)列放在一維數(shù)組A[0..M－1]中，end1指向隊(duì)頭元素，end2指向隊(duì)尾元素的后一個位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M－1個元素。初始時為空，下列判斷隊(duì)空和隊(duì)滿的條件中，正確的是（）。[計(jì)算機(jī)統(tǒng)考（408）2014年研]

A．隊(duì)空：end1＝＝end2；隊(duì)滿：end1＝＝（end2＋1）modM

B．隊(duì)空：end1＝＝end2；隊(duì)滿：end2＝＝（end1＋1）mod（M－1）

C．隊(duì)空：end2＝＝（end1＋1）modM；隊(duì)滿：end1＝＝（end2＋1）modM

D．隊(duì)空：end1＝＝（end2＋1）modM；隊(duì)滿：end2＝＝（end1＋1）mod（M－1）

【答案】A查看答案

【解析】在循環(huán)隊(duì)列中，在少用一個元素空間的前提下，可約定入隊(duì)前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等，則隊(duì)滿。而隊(duì)空的條件還是首尾指針是否相等。

4已知關(guān)鍵字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后的小根堆是（）。[計(jì)算機(jī)統(tǒng)考（408）2009年研]

A．3，5，12，8，28，20，15，22，19

B．3，5，12，19，20，15，22，8，28

C．3，8，12，5，20，15，22，28，19

D．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下列選項(xiàng)中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是（）。[計(jì)算機(jī)統(tǒng)考（408）2015年研]

A．500，200，450，180

B．500，450，200，180

C．180，500，200，450

D．180，200，500，450

【答案】A查看答案

【解析】折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。折半查找的關(guān)鍵字序列滿足：對每一個關(guān)鍵字，其后面的所有關(guān)鍵字序列或者都小于等于該關(guān)鍵字或者都大于等于該關(guān)鍵字。A項(xiàng)錯誤，第三次比較的關(guān)鍵字為450，說明待查關(guān)鍵字位于200～450間，所以第四次比較時不會遇到關(guān)鍵字180。

6已知字符串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”，采用KMP算法進(jìn)行匹配，第一次出現(xiàn)“失配”（s[i]!＝t[i]）時，i＝j(luò)＝5，則下次開始匹配時，i和j的值分別是（）。[計(jì)算機(jī)統(tǒng)考（408）2015年研]

A．i＝1，j＝0

B．i＝5，j＝0

C．i＝5，j＝2

D．i＝6，j＝2

【答案】C查看答案

【解析】模式匹配（KMP）算法對普通的暴力匹配的改進(jìn)在于：每當(dāng)匹配過程中匹配失敗時，主串（本題為S）的指針（i）不需要回溯，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式串（t）向右“滑動”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。模式串“滑動”的距離是由模式串（t）本身決定的，即t的子串t[0…j－1]中前綴串和后綴串相等的最長長度。本題中第一次失配i＝5，字串為“abaab”，其相等且最長的前后綴為“ab”，一次下一個j＝2。

7下列關(guān)于無向連通圖特性的敘述中，正確的是（）。[計(jì)算機(jī)統(tǒng)考（408）2009年研]

Ⅰ．所有的頂點(diǎn)的度之和為偶數(shù)

Ⅱ．邊數(shù)大于頂點(diǎn)個數(shù)減1

Ⅲ．至少有一個頂點(diǎn)的度為1

A．只有Ⅰ

B．只有Ⅱ

C．Ⅰ和Ⅱ

D．Ⅰ和Ⅲ

【答案】A查看答案

【解析】在圖中，頂點(diǎn)的度TD（Vi）之和與邊的數(shù)目滿足關(guān)系式：

其中，n為圖的總結(jié)點(diǎn)數(shù)，e為總邊數(shù)。因此，Ⅰ項(xiàng)正確。對于Ⅱ、Ⅲ項(xiàng)中的特性不是一般無向連通圖的特性，可以輕松地舉出反例?！爸辽儆幸粋€頂點(diǎn)的度為1”的反例如下圖（1）所示，“邊數(shù)大于頂點(diǎn)個數(shù)減1”的反例如下圖（2）所示。

8下列敘述中，不符合m階B樹定義要求的是（）。[計(jì)算機(jī)統(tǒng)考（408）2009年研]

A．根結(jié)點(diǎn)最多有m棵子樹

B．所有葉結(jié)點(diǎn)都在同一層上

C．各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列

D．葉結(jié)點(diǎn)之間通過指針鏈接

【答案】D查看答案

【解析】B樹就是指B－樹。根據(jù)B－樹的定義，m階B－樹中每個結(jié)點(diǎn)最多有m個分支，因此，根結(jié)點(diǎn)最多有m棵子樹，A項(xiàng)正確；B－樹中所有葉結(jié)點(diǎn)都在最底層，位于同一層，B項(xiàng)正確；結(jié)點(diǎn)內(nèi)各關(guān)鍵字互不相等且有序排列，C項(xiàng)正確。但是，所有葉子結(jié)點(diǎn)之間通過指針鏈接，是B＋樹的定義，而B－樹中沒有。因此，D項(xiàng)是錯誤的。

9排序過程中，對尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時都至少能夠確定一個元素最終位置的方法是（）。[計(jì)算機(jī)統(tǒng)考（408）2012年研]

Ⅰ．簡單選擇排序

Ⅱ．希爾排序

Ⅲ．快速排序

Ⅳ．堆排

Ⅴ．二路歸并排序

A．僅Ⅰ、Ⅲ、Ⅳ

B．僅Ⅰ、Ⅱ、Ⅲ

C．僅Ⅱ、Ⅲ、Ⅳ