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

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

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

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

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

B.abdce

C.edcbaD.edabcAAD6.以下應(yīng)用中，必須采用棧結(jié)構(gòu)的是。A.使一個(gè)整數(shù)序列逆轉(zhuǎn)B.遞歸函數(shù)的調(diào)用和返回C.申請(qǐng)和釋放單鏈表中的結(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)的所有元素）按列壓縮存儲(chǔ)在數(shù)組M[0…m]中，即A[0,0]存儲(chǔ)在M[0]、A[1,0]存儲(chǔ)在M[1]、A[2,0]存儲(chǔ)在M[2]，…，A[8,8]存儲(chǔ)在M[44]，則元素A[5,5]存儲(chǔ)在—1—。若將其下三角元素按行壓縮存儲(chǔ)在數(shù)組M[0…m]中，即A[0,0]存儲(chǔ)在M[0]、A[1,0]存儲(chǔ)在M[1]、A[1,2]存儲(chǔ)在M[2]，…，A[8,8]存儲(chǔ)在M[44]，則元素A[5,5]存儲(chǔ)在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]的每個(gè)元素占用1個(gè)存儲(chǔ)單元，若元素按行存儲(chǔ)，則數(shù)組元素a[i,j]（0≤i≤m，1≤j≤n）相對(duì)于數(shù)組空間首地址的偏移量為（32）。（32）A.(i+1)*n+jB.i*n+j-1C.i*m+jD.i*(m+1)+j-1

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

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

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

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

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

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

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

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

A8.4常用算法

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

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

D.決策表適宜表示多重條件組合下的行為CBA4.若構(gòu)造哈希表時(shí)不發(fā)生沖突，則給定的關(guān)鍵字與其哈希地址之間的對(duì)應(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是一個(gè)長(zhǎng)度為5的字符串，其中的字符各不相同，則計(jì)算S中互異的非平凡子串（非空且不同于S本身）數(shù)目的算式為 （41） 。A.5+4+3+2+1B.5+4+3+2C.4+3+2+1D.4+3+2ABB7.折半（二分）查找方法對(duì)查找表的要求是（42）。A.鏈表存儲(chǔ)結(jié)構(gòu)，元素有序排列B.鏈表存儲(chǔ)結(jié)構(gòu)，元素?zé)o序排列C.順序存儲(chǔ)結(jié)構(gòu)，元素有序排列D.順序存儲(chǔ)結(jié)構(gòu)，元素?zé)o序排列C

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

B．3、1、2

C．1、2、3

D．2、1、3

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

C

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

B．10

C．15

D．25

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

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