第8章-數(shù)據(jù)結(jié)構(gòu)

第8章數(shù)據(jù)結(jié)構(gòu)與算法8.1線性結(jié)構(gòu)

考點(diǎn)：線性表的特點(diǎn)，棧和隊列的特點(diǎn)

一、線性表1.定義：（1）存在唯一的一個稱作“第一個”的元素（2）存在唯一的一個稱作“最后一個”的元素（3）除第一個和最后一個元素外，序列中的每個元素均只有一個直接前驅(qū)和直接后繼2.線性表的存儲結(jié)構(gòu)：順序存儲和鏈?zhǔn)酱鎯?/p>

二、棧和隊列1.棧的定義和基本運(yùn)算2.隊列的定義和基本運(yùn)算3.串的定義和基本運(yùn)算練習(xí)1.設(shè)有一個初始為空的棧，若輸入序列為1、2、3、…、n（n>3），且輸出序列的第一個元素是n-1，則輸入序列中所有元素都出棧后，—— 。A.元素n-2一定比n-3先出棧B.元素1～n-2在輸出序列中的排列是不確定的C.輸出序列末尾的元素一定為1D.輸出序列末尾的元素一定為n2.棧和隊列都是線性的數(shù)據(jù)結(jié)構(gòu)。以下關(guān)于棧和隊列的敘述中，正確的是——。A.棧適合采用數(shù)組存儲，隊列適合采用循環(huán)單鏈表存儲B.棧適合采用單鏈表存儲，隊列適合采用數(shù)組存儲C.棧和隊列都不允許在元素序列的中間插入和刪除元素D.若進(jìn)入棧的元素序列確定，則從棧中出來的序列也同時確定AC3.若在單向鏈表上，除訪問鏈表中所有結(jié)點(diǎn)外，還需在表尾頻繁插入結(jié)點(diǎn)，那么采用——最節(jié)省時間。A.僅設(shè)尾指針的單向鏈表B.僅設(shè)頭指針的單向鏈表C.僅設(shè)尾指針的單向循環(huán)鏈表 D.僅設(shè)頭指針的單向循環(huán)鏈表4.已知棧S初始為空，對于一個符號序列a1a2a3a4a5（入棧次序也是該次序），當(dāng)用I表示入棧、O表示出棧，則通過棧S得到符號序列a2a4a5a3a1的操作序列為—— 。A.IOIIOOIOOIB.IIOIOIOIOOC.IOOIIOIOIOD.IIOIIOIOOO5.隊列是一種按“先進(jìn)先出”原則進(jìn)行插入和刪除操作的數(shù)據(jù)結(jié)構(gòu)。若初始隊列為空，輸入序列為abcde，則可得到的輸出序列為 ——A.abcde

B.abdce

C.edcbaD.edabcAAD6.以下應(yīng)用中，必須采用棧結(jié)構(gòu)的是。A.使一個整數(shù)序列逆轉(zhuǎn)B.遞歸函數(shù)的調(diào)用和返回C.申請和釋放單鏈表中的結(jié)點(diǎn)D.裝入和卸載可執(zhí)行程序B8.2數(shù)組和矩陣考點(diǎn)：數(shù)組和矩陣的定義以及基本運(yùn)算一、數(shù)組的定義及基本運(yùn)算二、矩陣的定義及基本運(yùn)算練習(xí)1.下三角矩陣A[0…8，0…8]如下圖所示，若將其下三角元素（即行下標(biāo)不小于列下標(biāo)的所有元素）按列壓縮存儲在數(shù)組M[0…m]中，即A[0,0]存儲在M[0]、A[1,0]存儲在M[1]、A[2,0]存儲在M[2]，…，A[8,8]存儲在M[44]，則元素A[5,5]存儲在—1—。若將其下三角元素按行壓縮存儲在數(shù)組M[0…m]中，即A[0,0]存儲在M[0]、A[1,0]存儲在M[1]、A[1,2]存儲在M[2]，…，A[8,8]存儲在M[44]，則元素A[5,5]存儲在2。

（1）A.M[15]B.M[20]C.M[35]D.M[39]（2）A.M[15]B.M[20]C.M[35]D.M[39]CB3.設(shè)數(shù)組a[0..m,1..n]的每個元素占用1個存儲單元，若元素按行存儲，則數(shù)組元素a[i,j]（0≤i≤m，1≤j≤n）相對于數(shù)組空間首地址的偏移量為（32）。（32）A.(i+1)*n+jB.i*n+j-1C.i*m+jD.i*(m+1)+j-1

2.對于二維數(shù)組a[1..6,1..8]，設(shè)每個元素占2個存儲單元，且以列為主序存儲，則元素a[4,4]相對于數(shù)組空間起始地址的偏移量是 ———— 個存儲單元。A.28B.42C.48D.54

4.已知對稱矩陣An*n（Ai,j=Aj,i）的主對角線元素全部為0，若用一維數(shù)組B僅存儲矩陣A的下三角區(qū)域的所有元素（不包括主對角線元素），則數(shù)組B的大小為（40）。A.n(n-1)B.n2/2C.n(n-1)/2D.n(n+1)/2DBC8.3樹和圖考點(diǎn)：二叉樹的定義及基本運(yùn)算，圖的定義及基本運(yùn)算一、樹的定義二、二叉樹的定義及基本運(yùn)算三、圖的定義及基本運(yùn)算練習(xí)1.某二叉樹的先序遍歷序列為ABFCDE、中序遍歷序列為BFADCE，則該二叉樹根的左孩子和右孩子結(jié)點(diǎn)分別是—— 。A.B和FB.F和BC.B和CD.C和B2.若無向連通圖G具有n個頂點(diǎn)，則以下關(guān)于圖G的敘述中，錯誤的是——。A.G的邊數(shù)一定多于頂點(diǎn)數(shù)B.G的生成樹中一定包含n個頂點(diǎn)C.從G中任意頂點(diǎn)出發(fā)一定能遍歷圖中所有頂點(diǎn)D.G的鄰接矩陣一定是n階對稱矩陣3.若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）個數(shù)是（39）。A.不確定B.9C.11D.15CAC4.以下關(guān)于圖及其存儲結(jié)構(gòu)的敘述中，正確的是（41）。A.無向圖的鄰接矩陣一定是對稱的B.有向圖的鄰接矩陣一定是不對稱的C.無向圖采用鄰接表存儲更節(jié)省存儲空間D.有向圖采用鄰接表存儲更節(jié)省存儲空間

5.知某二叉樹的先序遍歷序列是ABDCE，中序遍歷序列是BDAEC，則該二叉樹為——

AC6.某二叉樹為單枝樹（即非葉子節(jié)點(diǎn)只有一個孩子節(jié)點(diǎn)）且具有n個節(jié)點(diǎn)）則該二叉樹_____

A.共有n層,每層只有一個結(jié)點(diǎn)

B.共有n層，相鄰兩層的結(jié)點(diǎn)數(shù)正好相差一倍

C.先序遍歷序列與中序遍歷序列相同

D.后序遍歷序列與中序遍歷序列相同

A8.4常用算法

考點(diǎn)：算法的定義，算法的常用描述工具，常用的排序算法，查找算法，以及字符串處理算法和遞歸算法一、算法概述（算法定義，算法描述工具）二、排序算法三、查找算法四、字符串處理五、遞歸算法六、圖的相關(guān)算法練習(xí)1.在直接插入排序、冒泡排序、簡單選擇排序和快速排序方法中，能在第一趟排序結(jié)束后就得到最大（或最?。┰氐呐判蚍椒ㄊ牵?3）。A.冒泡排序和快速排序B.直接插入排序和簡單選擇排序C.冒泡排序和簡單選擇排序D.直接插入排序和快速排序2.對n個元素的有序表A[1…n]進(jìn)行二分（折半）查找，則成功查找到表中的任意一個元素時，最多與A中的（39）個元素進(jìn)行比較。A.n-1B.n/2C.n(n-1)/2D.n3.以下關(guān)于程序員流程圖、N-S盒圖和決策的敘述中，錯誤的是（32）。A.N-S盒圖可以避免隨意的控制轉(zhuǎn)移B.N-S盒圖可以同時表示程序邏輯和數(shù)據(jù)結(jié)構(gòu)

C.程序流程圖中的控制流可以任意轉(zhuǎn)向

D.決策表適宜表示多重條件組合下的行為CBA4.若構(gòu)造哈希表時不發(fā)生沖突，則給定的關(guān)鍵字與其哈希地址之間的對應(yīng)關(guān)系是（43）。（其中n>1且m>1）A.1:1B.1:nC.n:1D.n:m5.

（38）并不是算法必須具備的特性。A.可行性B.可移植性C.確定性D.有窮性6.設(shè)S是一個長度為5的字符串，其中的字符各不相同，則計算S中互異的非平凡子串（非空且不同于S本身）數(shù)目的算式為 （41） 。A.5+4+3+2+1B.5+4+3+2C.4+3+2+1D.4+3+2ABB7.折半（二分）查找方法對查找表的要求是（42）。A.鏈表存儲結(jié)構(gòu)，元素有序排列B.鏈表存儲結(jié)構(gòu)，元素?zé)o序排列C.順序存儲結(jié)構(gòu)，元素有序排列D.順序存儲結(jié)構(gòu)，元素?zé)o序排列C

在以下情形中，___(35)___適合于采用隊列數(shù)據(jù)結(jié)構(gòu)。A．監(jiān)視一個火車票售票窗口等待服務(wù)的客戶D．描述一個組織中的管理機(jī)構(gòu)C．統(tǒng)計一個商場中的顧客數(shù)D．監(jiān)視進(jìn)入某住宅樓的訪客元素3、1、2依次全部進(jìn)入一個棧后，陸續(xù)執(zhí)行出棧操作，得到的出棧序列為___(36)___。A．3、2、1

B．3、1、2

C．1、2、3

D．2、1、3

AD以下各圖用樹結(jié)構(gòu)描述了7個元素之間的邏輯關(guān)系，其中___(39)___適合采用二分法查找元素。a

C

對于二維數(shù)組a[0…4,1…5]，設(shè)每個元素占1個存儲單元，且以行為主序存儲，則元素a[2,1]相對于數(shù)組空間起始地址的偏移量是___(40)___。A．5

B．10

C．15

D．25

B設(shè)數(shù)組a[1...m，1…n]（m>1,n>2）中的元素以行為主序存放，每個元素占用1個存儲單元，則最后一個數(shù)組元素a[m,n]相對于數(shù)組空間首地址的偏移量為____（35）_____。（35）A.（m-1）*n+n-1B.（m-1）*nC.m*（n-1）D.m*n●設(shè)push、pop分別為表示入棧、出棧操作，若初始棧為空，對于元素序列abc，則操作序列push、pop、pop、push、push、pop__(36)_____。(36)A.得到出棧序列為abcB.得到出棧序列為bacC.得到出棧序列為bcaD.是非法的操作序列AD在有11個元素的有序數(shù)組a[1..11]中進(jìn)行二分法查找（既折半查找），依次與___（37）___比較后，成功找到元素a[5]。（37）A.a[6]、a[2]、a[5]B.a[6]、a[4]、a[5]C.a[6]、a[3]、a[4]、a[5]D.a[6]、a[8]、a[4]、a[5]從未排序的序列中依次取出一個元素與已排序序列中的元素進(jìn)行比較，然后將其放在已排序序列的合適位置上，該排序方法為___（39）___。（39）A.插入排序B.選擇排序C.快速排序D.冒泡排序CA一個高度為h的滿二叉樹的結(jié)點(diǎn)總數(shù)為2（h次方）-1其每一層結(jié)點(diǎn)個數(shù)都達(dá)到最大值。從根結(jié)點(diǎn)開始順序編號，即根結(jié)點(diǎn)編號為1，其左、右孩子結(jié)點(diǎn)編號分別為2和3，再下一層從左到右的編號為4、5、6、7，依次類推，每一層都從左到右依次編號，直到最后的葉子結(jié)點(diǎn)層為止。那么，在一顆滿二叉樹中，對于編號m和n的兩個結(jié)點(diǎn)，若m=2n+1，則__(38)_(38)A.m是n的左孩子B.m是n的右孩子

C.n是m的左孩子D.n是m的右孩子在具有n（n>0）個頂點(diǎn)的簡單無向圖中，最多含有___（43）___條邊。（43）A.n（n-1）B.n（n+1）C.n*（n-1）/2D.n*（n+1）/2BC