數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識總結(jié) 1算法?? 算法：是指解題方案的準確而完整的描述。? 算法不等于程序，也不等計算機方法，程序的編制不可能優(yōu)于算法的設(shè)計。? 算法的基本特征：是一組嚴謹?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括：?（1）可行性；? （2）確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；? （3）有窮性，算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止，包括合理的執(zhí)行時間的含義；?（4）擁有足夠的情報。? 算法的基本要素：一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。?指令系統(tǒng)：一個計算機系統(tǒng)能執(zhí)行的所有指令的集合。? 基本運算和操作包括：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。?算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。? 算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。?算法復(fù)雜度：算法時間復(fù)雜度和算法空間復(fù)雜度。?算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。?算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。?? 2數(shù)據(jù)結(jié)構(gòu)的基本基本概念?? 數(shù)據(jù)結(jié)構(gòu)研究的三個方面：? （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；? （2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；?（3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。? 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。?數(shù)據(jù)的邏輯結(jié)構(gòu)包含：?（1）表示數(shù)據(jù)元素的信息；? （2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。?數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。?線性結(jié)構(gòu)條件：? （1）有且只有一個根結(jié)點；? （2）每一個結(jié)點最多有一個前件，也最多有一個后件。?非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。?? 3線性表及其順序存儲結(jié)構(gòu)?? 線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。? 在復(fù)雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個記錄構(gòu)成的線性表又稱為文件。? 非空線性表的結(jié)構(gòu)特征：? （1）且只有一個根結(jié)點a1，它無前件；?（2）有且只有一個終端結(jié)點an，它無后件；? （3）除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。結(jié)點個數(shù)n稱為線性表的長度，當n=0時，稱為空表。?線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：?（1）線性表中所有元素的所占的存儲空間是連續(xù)的；? （2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。? ai的存儲地址為：adr(ai)=adr(a1)+(i-1)k,，adr(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。? 順序表的運算：插入、刪除。 （詳見14--16頁）?? 4棧和隊列?? 棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。? 棧按照“先進后出”（filo）或“后進先出”（lifo）組織數(shù)據(jù)，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。? 棧的基本運算：（1）插入元素稱為入棧運算；（2）刪除元素稱為退棧運算；（3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。? 隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。rear指針指向隊尾，front指針指向隊頭。? 隊列是“先進行出”（fifo）或“后進后出”（lilo）的線性表。? 隊列運算包括（1）入隊運算：從隊尾插入一個元素；（2）退隊運算：從隊頭刪除一個元素。?循環(huán)隊列：s=0表示隊列空，s=1且front=rear表示隊列滿?? 5線性鏈表?? 數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。?結(jié)點由兩部分組成：（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。? 在鏈式存儲結(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。?鏈式存儲方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。? 線性鏈表，head稱為頭指針，head=null（或0）稱為空表，如果是兩指針：左指針（llink）指向前件結(jié)點，右指針（rlink）指向后件結(jié)點。?線性鏈表的基本運算：查找、插入、刪除。?? 6樹與二叉樹?? 樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。? 在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。 在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。? 二叉樹的特點：（1）非空二叉樹只有一個根結(jié)點；（2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。?二叉樹的基本性質(zhì)：? （1）在二叉樹的第k層上，最多有2k-1(k≥1)個結(jié)點；?（2）深度為m的二叉樹最多有2m-1個結(jié)點；? （3）度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個；? （4）具有n個結(jié)點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分；?（5）具有n個結(jié)點的完全二叉樹的深度為[log2n]+1；? （6）設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1，2，….n給結(jié)點進行編號（k=1,2….n），有以下結(jié)論：? ①若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>1，則該結(jié)點的父結(jié)點編號為int(k/2)；?②若2k≤n，則編號為k的結(jié)點的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（也無右子結(jié)點）；? ③若2k+1≤n，則編號為k的結(jié)點的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。?滿二叉樹是指除最后一層外，每一層上的所有結(jié)點有兩個子結(jié)點，則k層上有2k-1個結(jié)點深度為m的滿二叉樹有2m-1個結(jié)點。? 點擊文本外關(guān)閉彈框

數(shù)據(jù)結(jié)構(gòu)與算法(一)

(總分：78.00，做題時間：90分鐘)

一、{{B}}選擇題{{/B}}(總題數(shù)：28，分數(shù)：56.00)

1.計算機算法指的是 ______，它必須具備輸入、輸出，可執(zhí)行性、確定性和有窮性。（分數(shù)：2.00）A.計算方法B.排序方法C.解決問題的有限運算序列√D.調(diào)度方法解析：2.設(shè)計一個“判別在表達式中左、右括號是否配對出現(xiàn)”的算法，采用 ______ 數(shù)據(jù)結(jié)構(gòu)最佳。（分數(shù)：2.00）A.線性表的順序存儲結(jié)構(gòu)B.?！藽.隊列D.線性表的鏈式存儲結(jié)構(gòu)解析：3.若對一棵二叉樹進行中序遍歷得到的結(jié)果是(B，D，A，G，H，E，C，F(xiàn))，進行后序遍歷的結(jié)果是DBHGEFCA，那么這棵二叉樹進行前序遍歷得到的結(jié)果是 ______。（分數(shù)：2.00）A.(A， B， D， C， E， G， H，√B.(A， B， D， C， E， H， G，C.(D，B，A，C，E，G，H，D.無法確定解析：4.一個隊列的入列序號是1，2，3，4，則隊列的輸出系列是 ______。（分數(shù)：2.00）A.4，3，2，1 B.1，2，3，4 √C.1，4，3，2 D.3，2，4，1 解析：5.對關(guān)鍵字序列(11，12，13，14，15)采用對半查找算法查找關(guān)鍵字11，則關(guān)鍵字之間比較次數(shù)為______。（分數(shù)：2.00）A.1 B.2 √C.3 D.4 解析：6.如果以鏈表為棧的存儲結(jié)構(gòu)，則出棧操作是 ______。（分數(shù)：2.00）A.必須判別棧是否為滿B.必須判別棧是否為空√C.判別棧元素的類型D.對棧不作任何判別解析：7.在算法設(shè)計基本方法中， ______ 是從初始條件出發(fā)，逐次推出所需求的結(jié)果。

（分數(shù)：2.00）?A.遞推 √?B.遞歸?C.列舉法?D.歸納法 解析：

8.分析算法的目的是 ______。

（分數(shù)：2.00）

?A.找出數(shù)據(jù)結(jié)構(gòu)的合理性?B.研究算法中的輸入和輸出的關(guān)系?C.分析算法的效率以求改進 √?D.分析算法的易懂性和文檔 解析：

9.若完全二叉樹共有n個結(jié)點，且從根結(jié)點開始，按層序(每層從左到右)用正整數(shù) 0，1，2，…，n-1，從小到大對結(jié)點編號，則對于編號為k的結(jié)點，錯誤的是 ______。

（分數(shù)：2.00）

?A.若k＞0，則該結(jié)點的父結(jié)點編號為[k/2]([]表示取整)?B.若2k＞n-1，則編號為k的結(jié)點無右子樹，但可能有左子樹 √?C.若2k+1＜=n-1，則編號為k的結(jié)點的右子結(jié)點編號為2k+1?D.若k=0，則該結(jié)點肯定沒有父結(jié)點 解析：

10.用數(shù)組A[0…m-1]存放循環(huán)隊列的元素值，若其頭尾指針分別為front和rear，則循環(huán)隊列中當前元素的個數(shù)為 ______。

（分數(shù)：2.00）

?A.(rear-front+rmod m √?B.(rear-front+m+1)mod m?C.(rear-front+m-1)mod m?D.(rear-front-m-1)mod m 解析：

11.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為 ______。

（分數(shù)：2.00）?A.n?B.n/2?C.(n+1)/2 √?D.(n-1)/2 解析：

12.設(shè)有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用 ______ 排序法。

（分數(shù)：2.00）?A.希爾排序?B.冒泡排序?C.堆排序 √?D.快速排序 解析：

13.鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是 ______。

（分數(shù)：2.00）?A.插入操作更加方便

?B.通常不會出現(xiàn)棧滿情況 √?C.不會出現(xiàn)棧空的情況

?D.刪除操作更加方便 解析：

14.對線性表進行二分法檢索。其前提條件是 ______ 。

（分數(shù)：2.00）

?A.線性表以順序方式存儲，并且按關(guān)鍵碼值排好序 √?B.線性表以順序方式存儲，并且按關(guān)鍵碼的檢索頻率排好序?C.線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序

?D.線性表以鏈接方式存儲，并且按關(guān)鍵碼的檢索頻率排好序 解析：

15.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是 ______。

（分數(shù)：2.00）

?A.實際應(yīng)用中，隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式 √?B.遞推算法結(jié)構(gòu)程序一般比遞歸算法結(jié)構(gòu)程序更精練?C.樹是一種線性結(jié)構(gòu)

?D.用一維數(shù)組存儲二叉樹，總是以先序遍歷的順序存儲各結(jié)點 解析：

16.完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒有 ______。

（分數(shù)：2.00）?A.左子結(jié)點?B.右子結(jié)點

?C.左子結(jié)點和左子結(jié)點 √?D.左子結(jié)點、右子結(jié)點和兄弟結(jié)點 解析：

17.下面關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是 ______。

（分數(shù)：2.00）

?A.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高?B.鏈表中的每一個結(jié)點都包含恰好一個指針

?C.包含n個結(jié)點的二叉排序樹的最大檢索長度為log2n?D.將一棵樹轉(zhuǎn)換為二叉樹后，根結(jié)點沒有右子樹 √ 解析：

18.一組記錄的排序碼為(46，79，56，38，40，84)，則利用堆排序的方法建立的初始堆為 ______。

（分數(shù)：2.00）

?A.79，46，56，38，40，84?B.84，79，56，38，40，46 √?C.84，79，56，46，40，38?D.84，56，79，40，46，38 解析：

19.下述幾種排序方法中， ______ 是最簡單的交換類排序方法。

（分數(shù)：2.00）?A.冒泡排序 √?B.插入排序?C.快速排序?D.選擇排序 解析：

20.在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是 ______。

（分數(shù)：2.00）?A.希爾排序?B.冒泡排序?C.插入排序

?D.選擇排序 √ 解析：

21.二分法查找 ______ 存儲結(jié)構(gòu)。

（分數(shù)：2.00）?A.只適合于鏈式?B.只適合于順序 √

?C.既適合于順序也適合于鏈式?D.既不適合于順序也不適合于鏈式 解析：

22.對含有n個關(guān)鍵詞的序列進行冒泡法排序，最少的比較次數(shù)是 ______ 。

（分數(shù)：2.00）?A.n?B.n-1 √?C.n/2?D.n-2 解析：

23.下面關(guān)于二叉樹的敘述中正確的是 ______。

（分數(shù)：2.00）

?A.度為2的樹稱為二叉樹?B.二叉樹的度肯定是2

?C.二叉樹中所有結(jié)點的度都是2

?D.由3個結(jié)點可以構(gòu)造出5種不同的二叉樹 √ 解析：

24.對給定的整數(shù)序列(541，132，984，746，518，181，946，314，205，827)進行從小到大的排序時，采用快速排序(以中間元素518為基準)的第一趟掃描結(jié)果是 ______ 。

（分數(shù)：2.00）

?A.(181，132，314，205，541，518，946，827，746，984)?B.(541，132，827，746，518，181，946，314，205，984)?C.(205，132，314，181，518，746，946，984，541，827) √?D.(541，132，984，746，827，181，946，314，205，518) 解析：

25.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5，e6依次通過棧S，一個元素出棧后即進入棧隊列Q，若6個元素出隊的順序是e2，e4，e3，e6，e5，e1，則棧S的容量至少應(yīng)該是 ______。

（分數(shù)：2.00）?A.6?B.4?C.3 √?D.2 解析：

26.按照二叉樹的定義，深度為5的二叉樹至多有 ______ 個結(jié)點。

（分數(shù)：2.00）?A.16?B.32?C.10?D.31 √ 解析：

27.采用二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為 ______。

（分數(shù)：2.00）?A.O(log2 √

?B.O(?C.O(nlog2?D.O(n2) 解析：

28.以下敘述正確的是 ______。

（分數(shù)：2.00）

?A.線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)?B.在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)結(jié)點 √?C.棧的操作方式是先進先出?D.隊列的操作方式是先進后出 解析：

二、{{B}}填空題{{/B}}(總題數(shù)：11，分數(shù)：22.00)

29.一個算法通常由對數(shù)據(jù)對象的運算和操作以及算法的{{U}} 【1】 {{/U}}兩種基本要素組成。

（分數(shù)：2.00）

填空項1:__________________ （正確答案：控制結(jié)構(gòu)） 解析：

30.算法復(fù)雜度包括時間復(fù)雜度和空間復(fù)雜度。對空間復(fù)雜度一般可以用平均態(tài)和最壞情況復(fù)雜性來衡量：而對于空間復(fù)雜度，一般指執(zhí)行該算法所需要的{{U}} 【2】 {{/U}}。

（分數(shù)：2.00）

填空項1:__________________ （正確答案：內(nèi)存空間） 解析：

31.在數(shù)據(jù)結(jié)構(gòu)的圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以{{U}} 【3】 {{/U}}個。

（分數(shù)：2.00）

填空項1:__________________ （正確答案：任意多） 解析：

32.在樹中，一個結(jié)點的直接子結(jié)點的個數(shù)稱為該結(jié)點的{{U}} 【4】 {{/U}}。

（分數(shù)：2.00）

填空項1:__________________ （正確答案：一次數(shù)/度） 解析：

33.設(shè)只包含根結(jié)點的二叉樹的高度為0，則高度為k的二叉樹的最小結(jié)點數(shù)為{{U}} 【5】 {{/U}}。

（分數(shù)：2.00）

填空項1:__________________ （正確答案：k+1） 解析：

34.已知一棵二叉樹前序序列和中序序列分別為A，B，D，E，G，C，F(xiàn)，H和D，B， G，E，A，C，H，F(xiàn)，則該二叉樹的后序序列為{{U}} 【6】 {{/U}}。

（分數(shù)：2.00）

填空項1:__________________ （正確答案：D，G，E，B，H，P，C，A） 解析：

35.從未排序序列中依次取出元素與已排序序列(初始時為空)中的元素進行比較，將其放入已排序序列正確位置上的方法，稱為{{U}} 【7】 {{/U}}。

（分數(shù)：2.00）

填空項1:__________________ （正確答案：希爾排序） 解析：

36.從未排序序列中挑選元素，將其依次放入已排序序列(初始時為空)的一端，這種排序方法稱為{{U}} 【8】 {{/U}}。

（分數(shù)：2.00）

填空項1:__________________ （正確答案：選擇排序） 解析：

37.在表為n的順序表中，實施順序查找，在查找不成功時，與關(guān)鍵字比較的次數(shù)為{{U}} 【9】 {{/U}}。

（分數(shù)：2.00）

填空項1:__________________ （正確答案：n+1） 解析：

38.在插入排序、希爾排序、選擇排序、堆排序和快速排序中，平均比較次數(shù)最少的排序是{{U}} 【10】 {{/U}}。

（分數(shù)：2.00）

填空項1:__________________ （正確答案：快速排序） 解析：

39.在堆排序和快速排序中，若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選擇{{U}} 【11】 {{/U}}方法。

?

（分數(shù)：2.00）

填空項1:__________________ （正確答案：堆排序） 解析：

?