【正文】 二級(jí)VF知識(shí)點(diǎn) 第1章 基本數(shù)據(jù)結(jié)構(gòu)與算法1. 算法的基本概念 算法的指解題方案的準(zhǔn)確而完整的描述。作為一個(gè)算法，一般應(yīng)具有的特征為：1） 可行性，針對(duì)實(shí)際問題設(shè)計(jì)的算法， 考慮其可行性，應(yīng)該能夠得到滿意的結(jié)果；2） 確定性，算法中的每一個(gè)步驟都必須是明確定義的，不允許有模掕兩可的解釋，也不允許有多義性；3） 有窮性，算法必須能在執(zhí)行有限個(gè)步驟之后終止；4） 有零個(gè)或多個(gè)輸入；5） 有一個(gè)或多個(gè)輸入；綜上所述，算法是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，；這個(gè)運(yùn)算順序?qū)⒃谟邢薜拇螖?shù)下終止。2. 算法復(fù)雜度 算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。（1）算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。算法的工作量用算法在所執(zhí)行的基本運(yùn)算次數(shù)來度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)，即 算法的工作量=f（n)其中N是問題的規(guī)模。 例如，兩個(gè)N階矩陣相乘需要的基本算法次數(shù)為n3 ，即計(jì)算工作量為n3, 也就是時(shí)間復(fù)雜度為n3, 即 F（n）=O( n3 )(2) 算法的空間復(fù)雜度 算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間?！尽? 算法的時(shí)間復(fù)雜度是指（ ） A)執(zhí)行算法程序所需要的時(shí)間 B)算法程序的長(zhǎng)度 C)算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù) D)算法程序中的指令條數(shù) 答案：C 提示：2005年9月真題填空題第2題。2006年9月真題選擇題第7題。2007年4月真題選擇題第1題屬該題的類似題目2007年4月真題選擇題第11題考察算法的特征。 數(shù)據(jù)結(jié)構(gòu)的基本概念1. 數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)結(jié)構(gòu)是指反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示。 通俗地說，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。（1）數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面的信息： 1） 表示數(shù)據(jù)元素的信息； 2） 表示各數(shù)據(jù)元素之間的前后件關(guān)系。（2） 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) （也稱數(shù)據(jù)的物理結(jié)構(gòu)）。 一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)，常用的存儲(chǔ)結(jié)構(gòu)有順序。鏈接。索引等。而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的，因此，在進(jìn)行數(shù)據(jù)處理時(shí)， 選擇合適的存儲(chǔ)結(jié)構(gòu)是很重要的?！?】 與所使用的計(jì)算機(jī)系統(tǒng)無(wú)關(guān)的數(shù)據(jù)結(jié)構(gòu)是（ ） A)存儲(chǔ) B)物理 C)邏輯 D)線性表 答案： C 解析： 線性表是一種具體邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)也稱物理結(jié)構(gòu)，只是邏輯結(jié)構(gòu)是不依賴于計(jì)算機(jī)系統(tǒng)的。所以選項(xiàng)C為正確答案?！?】 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指（ ） A) 存儲(chǔ)在外存中的數(shù)據(jù) B) 數(shù)據(jù)所占的存儲(chǔ)空間量 C) 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式 D) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示 答案： D 解析：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱為數(shù)據(jù)的物理結(jié)構(gòu)，它指的是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的中的存放形式。只有選項(xiàng)D符合其定義，為本題的答案。 提示：2007年4月真題選擇題第1題與該題相關(guān)。 2007年9月真題選擇題第5題考察程序的執(zhí)行效率也數(shù)據(jù)結(jié)構(gòu)的關(guān)系。2. 數(shù)據(jù)結(jié)構(gòu)的圖形表示【】 下列敘述中，正確的是（ ） A)一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu) B)數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線性結(jié)構(gòu) C)一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 D)一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效答案：D解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)，而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。提示： 2007年9月真題選擇題第6題屬該題的類似題目。數(shù)據(jù)結(jié)構(gòu)除了可用二元關(guān)系表示外，還可以用直觀的圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對(duì)于數(shù)據(jù)集合中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素指的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)（簡(jiǎn)稱為結(jié)點(diǎn)）。為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系中的每一個(gè)元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。3. 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 根據(jù)數(shù)據(jù)結(jié)構(gòu)中個(gè)數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件： 1）有且只有一個(gè)根結(jié)點(diǎn) 2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有有一個(gè)后件。 則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱為線性表。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)。就稱為非線性結(jié)構(gòu)。 線性表及其順序存儲(chǔ)結(jié)構(gòu) 1. 線性表的基本概念 線性表是有n（n≥0）個(gè)數(shù)據(jù)元素 a1,a2,...,an 組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件，即線性表或是一個(gè)空表?；蛘呖梢员硎緸椋? （ a1 ,a2 ,...ai ,..an ）其中 ai(i=1,2,...n)是數(shù)據(jù)元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。 2. 線性表的順序存儲(chǔ)結(jié)構(gòu) 線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)： 1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的； 2）線性表中個(gè)數(shù)據(jù)元素在存儲(chǔ)空間中是邏輯順序依次存放的。 由此可以看出，在線性表的存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中的緊鄰的， 且前后元素一定存儲(chǔ)在后件元素的前面。 3. 線性表的插入、刪除運(yùn)算下面討論線性表在順序存儲(chǔ)結(jié)構(gòu)下的插入與刪除的問題。（1）線性表的插入運(yùn)算 設(shè)長(zhǎng)度為n的線性表為 （ a1 ，a2 ，… ，ai ，…，an ）現(xiàn)要在線性表的第j個(gè)元素 之前插入一個(gè)新元素b，插入后得到長(zhǎng)度為n+1的線性表為 （a′1,a′2, …，a′j，a′j+1，…，a′n，a′n+1）則插入前后兩個(gè)線性表中的元素滿足如下關(guān)系: aj 1≤j≤i1a′j= b j = i aj1 i+1≤j≤n+1一般情況下，要在第i（1≤i≤n）個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)（即第n）元素開始，知道第i 個(gè)元素之間共ni+1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第i個(gè)就被空出，然后將新元素插入到第i 個(gè)位置，插入結(jié)束后，線性表的長(zhǎng)度增加了1.（2）線性表的刪除運(yùn)算 設(shè)長(zhǎng)度為n的線性表為 （ a1 ，a2 ，… ，ai ，…，an ）現(xiàn)要?jiǎng)h除第j個(gè)元素，刪除后得到長(zhǎng)度為n1的線性表 （ a′1,a′2, …，a′j，…，a′n1 ）則刪除前后兩個(gè)線性表中的元素滿足如下關(guān)系： aj 1≤j≤i1a′j= aj+1 i+1≤j≤n+1一般情況下，要?jiǎng)h除第i （1≤i≤n ）個(gè)元素時(shí)，從第i+1個(gè)元素開始，直到第n個(gè)元素之間共n1個(gè)元素依次向前移動(dòng)一個(gè)位置，刪除結(jié)束后，線性表的長(zhǎng)度減少了1。 棧和隊(duì)列216。 棧及其基本運(yùn)算216。 隊(duì)列及其基本運(yùn)算1. 及其基本運(yùn)算 棧（stack）是限定在一端進(jìn)行插入和刪除運(yùn)算的線性表。 在棧中，允許插入與刪除的一端稱為棧頂（top），另一端稱為棧低（bottom）。棧頂元素總是最后被插入的元素；棧底元素總是最先被插入的元素，棧頂元素總是最先被刪除的元素；棧底元素總是最后被刪除的元素。即棧是按照“先進(jìn)后出”（First In Last “Out, FILO”）的原則組織數(shù)據(jù)的，因此，棧也被稱為“先進(jìn)后出”表。 棧的基本運(yùn)算有三種： 入棧、出棧、和讀棧頂元素?！尽? 下列關(guān)于棧的描述中錯(cuò)誤的是（ ） A)棧的先進(jìn)后出的線性表 B)棧只能順序存儲(chǔ) C)棧具有記憶作用 D)對(duì)棧的插入于刪除中，不需要改變棧底指針。 答案： B . 解析：棧是限定在一端進(jìn)行插入和刪除的線性表，允許插入和刪除的一端稱為棧頂，另一端稱為棧底；棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則就、組織數(shù)據(jù)的；棧既可以順序存儲(chǔ)又可以鏈?zhǔn)酱鎯?chǔ)；棧具有記憶功能。 提示：2008年4月真題選擇題第7題屬該題的類似題目。 （1） 隊(duì)列的基本概念隊(duì)列是指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。允許插入的一段稱為隊(duì)尾，通常用一個(gè)稱為隊(duì)尾指針（rear）的指針指向隊(duì)尾元素，即尾指針總是指向最后被插入的元素。允許刪除的一端稱為排頭（也稱為隊(duì)頭），通常也用一個(gè)排頭指針（front）指向排頭元素的前一個(gè)位置。因此，隊(duì)列又稱為“先進(jìn)先出”（First In First Out FIFO）的線性表。退隊(duì)←a1 a2 a3 an←入隊(duì)隊(duì)列的基本結(jié)構(gòu)如圖11所示。 圖11 隊(duì)列的基本結(jié)構(gòu)向隊(duì)列的隊(duì)尾插入一個(gè)元素稱為入隊(duì)運(yùn)算，從隊(duì)列的排頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算。（2）循環(huán)隊(duì)列及其運(yùn)算在實(shí)際應(yīng)用中，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從排頭指針front指向最后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間，所有的元素均為隊(duì)列中的元素。循環(huán)隊(duì)列的初始狀態(tài)唯恐，即rear=front【例16】 下列關(guān)于隊(duì)列的敘述正確的是（ ）。A）隊(duì)列是非線性結(jié)構(gòu) B）隊(duì)列是一種樹狀結(jié)構(gòu) C）隊(duì)列具有“先進(jìn)先出”的特征 D）隊(duì)列具有“后進(jìn)后出”的特征 答案：C。提示：2007年4月真題選擇題第5題屬該題的類似題目?！纠?7】 下列說法中，正確的是（ ）。A）棧是在兩端操作、“先進(jìn)先出”的線性表 B）棧是在一端操作、“先進(jìn)先出”的線性表 C）隊(duì)列是在一端操作、“先進(jìn)先出”的線D）隊(duì)列是在兩端操作、“先進(jìn)先出”的線性表 答案：D。 解析：棧是只允許在一端進(jìn)行插入和刪除操作的線性表，又稱“先進(jìn)后出”或“后進(jìn)先出”表；隊(duì)列是在一段進(jìn)行插入，而在另一端進(jìn)行刪除的線性表，又稱“先進(jìn)先出”或“后進(jìn)后出”表。所以只有選項(xiàng)D正確。 提示：2007年9月真題填空題第3題考察循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)。 線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表，線性鏈表分為單鏈表，雙向鏈表和循環(huán)鏈表三種類型。為了適應(yīng)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，計(jì)算機(jī)存儲(chǔ)空間被劃為一個(gè)一個(gè)小塊，每一小塊占若干字節(jié)，通常稱這些小塊為存儲(chǔ)節(jié)點(diǎn)。為了存儲(chǔ)線性表中的每一個(gè)元素，一方面要存出數(shù)據(jù)元素的值，另一方面要存儲(chǔ)各數(shù)據(jù)元素之間的前后件關(guān)系。為此目的，將存儲(chǔ)空間中的每一個(gè)存儲(chǔ)節(jié)點(diǎn)分為兩部分：一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱之為數(shù)據(jù)域；另一部分用于存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào)（即存儲(chǔ)節(jié)點(diǎn)的地址），即指向后件節(jié)點(diǎn)，稱為指針域。2. 線性鏈表的基本運(yùn)算線性鏈表的運(yùn)算主要有以下幾個(gè)：1） 在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。2） 在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。3） 將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。4） 將一個(gè)線性鏈表按要求進(jìn)行分解。5） 逆轉(zhuǎn)線性鏈表。6） 復(fù)制線性鏈表。7） 線性鏈表的排序。8） 線性鏈表的查找。 循環(huán)鏈表與線性鏈表相比，具有以下兩個(gè)特點(diǎn)：1） 在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。2） 循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不為空，而是指向表頭結(jié)點(diǎn)。即循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。a1a2圖12是一個(gè)非空循環(huán)鏈表，圖13是一個(gè)空循環(huán)鏈表。an HEAD … 圖12 非空循環(huán)鏈表 HEAD 表頭結(jié)點(diǎn)