考研計算機專業(yè)基礎(chǔ)綜合815之嚴蔚敏《數(shù)據(jù)結(jié)構(gòu)》考研復(fù)習(xí)重點筆記及考研真題詳解

?

?

復(fù)習(xí)筆記【節(jié)選自識庫學(xué)習(xí)網(wǎng)，如需轉(zhuǎn)載請注明出處】

?

　復(fù)習(xí)筆記

一、什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等的學(xué)科。

二、基本概念和術(shù)語

1數(shù)據(jù)

數(shù)據(jù)是對客觀事物的符號表示，是計算機科學(xué)中所有能輸入到計算機中并能被計算機程序處理的符號的總稱。

2數(shù)據(jù)元素

數(shù)據(jù)元素是數(shù)據(jù)的基本單位。

3數(shù)據(jù)對象

數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。

4數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

（1）數(shù)據(jù)結(jié)構(gòu)的基本結(jié)構(gòu)

根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有下列四類基本結(jié)構(gòu)：

①集合。數(shù)據(jù)元素屬于“同一個集合”，并無其他復(fù)雜關(guān)系。

②線性結(jié)構(gòu)。數(shù)據(jù)元素之間存在一個對一個的關(guān)系。

③樹形結(jié)構(gòu)。數(shù)據(jù)元素之間存在一個對多個的關(guān)系。

④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。數(shù)據(jù)元素之間存在多個對多個的關(guān)系。

【注意】區(qū)分這四種基本結(jié)構(gòu)可以根據(jù)元素間的對應(yīng)關(guān)系。

如圖1-1所示為上述四類基本結(jié)構(gòu)的關(guān)系圖。

圖1-1　四類基本結(jié)構(gòu)的關(guān)系圖

（2）數(shù)據(jù)結(jié)構(gòu)的形式定義

數(shù)據(jù)結(jié)構(gòu)的形式定義為：

Data_Structure=(D,S)

其中：D表示數(shù)據(jù)元素的有限集，S表示D上關(guān)系的有限集。

（3）數(shù)據(jù)結(jié)構(gòu)在計算機中的表示

數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和關(guān)系，在計算機中稱為數(shù)據(jù)的物理結(jié)構(gòu)（又稱存儲結(jié)構(gòu)）。

其中，關(guān)系有兩種表示方法：順序映象和非順序映象。這兩種表示方法對應(yīng)兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。

a．順序映象：用相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

b．非順序映象：用指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。

5數(shù)據(jù)類型

數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。

6抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型（ADT）由一個值域和定義在該值域上的一組操作組成。

【注意】抽象數(shù)據(jù)類型是對數(shù)據(jù)類型架構(gòu)的一種全局體現(xiàn)，使我們能夠更加清晰地看待某一數(shù)據(jù)類型。

7多形數(shù)據(jù)類型

多形數(shù)據(jù)類型是指其值的成分不確定的數(shù)據(jù)類型。

8數(shù)據(jù)操作的類型

基本的操作主要有：

（1）插入

（2）刪除

（3）更新

（4）查找

（5）排序

從操作的特性來分，所有的操作可以歸結(jié)為兩類：

加工型操作：改變了（操作之前的）結(jié)構(gòu)的值；

引用型操作：即不改變結(jié)構(gòu)的值，只是查詢或求得結(jié)構(gòu)的值。

上述5種操作中除“查找”為引用型操作外，其余都是加工型操作。

9算法

【定義】算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。

【特性】

（1）有窮性

（2）確定性

（3）可行性

（4）輸入

（5）輸出

【注意】在考試中這五個特性可能出現(xiàn)在選擇或者填空題中（通常直接考察其名稱）。

考研真題精選

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．只有e

B．有e、b

C．有e、c

D．無法確定

【答案】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）mod M

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

C．隊空：end2＝＝（end1＋1）mod M；隊滿：end1＝＝（end2＋1） mod M

D．隊空：end1＝＝（end2＋1）mod M；隊滿：end2＝＝（end1＋1） mod （M－1）

【答案】A查看答案

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

? ? ? ? ? ? ??更多完整版考研資料可轉(zhuǎn)識庫學(xué)習(xí)網(wǎng)