數(shù)據(jù)結(jié)構(gòu)練習(xí)

一、單項(xiàng)選擇題(每小題2分，共20分)(1)以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？( )A)有向圖 B)隊(duì)列 C)線索二叉樹(shù) D)B樹(shù)(2)在一個(gè)單鏈表I1L中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，則執(zhí)行如下( )語(yǔ)句序列。A)p=q;p->next=q; B)p->next=q;q->next=p;C)p->next=q->next;p=q; D)q->next=p->next;p->next=q;(3)( )不是隊(duì)列的基本運(yùn)算。A)在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B)從隊(duì)頭刪除一個(gè)元素C)判斷一個(gè)隊(duì)列是否為空 D)讀取隊(duì)頭元素的值(4)字符A、B、C挨次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成()個(gè)不同的字符串。TOC\o"1-5"\h\zA)14 B)5 C)6 D)8(5)由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為()oA)11 B)35 C)19 D)53以下6-8題基于下圖：(6)該二叉樹(shù)結(jié)點(diǎn)的前序遍歷的序列為( )。A) E、G、F、A、C、D、B B) E、A、G、C、F、B、DC) E、 A、 C、 B、 D、 G、 F D) E、 G、 A、 C、 D、 F、 B(7)該二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為( )。A) A、 B、 C、 D、 E、 G、 F B) E、 A、 G、 C、 F、 B、 DC)E、A、C、B、D、G、FD)B、D、C、A、F、G、E(8)該二叉樹(shù)的按層遍歷的序列為( )oA)E、G、F、A、C、D、B B)E、A、C、B、D、G、FC)E、A、G、C、F、B、DD)E、G、A、C、D、F、B(9)下面關(guān)于圖的存儲(chǔ)的敘述中正確的是( )oA)用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)B)用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān)C)用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)D)用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)(10)設(shè)有關(guān)鍵碼序列(q,g,叫z,a,n,p,x,h),下面哪一個(gè)序列是從上述序列出發(fā)建堆的TOC\o"1-5"\h\z結(jié)果？( )B)a,g,m,h,q,n,p,x,zC)g,m,q,a,n,p,x,h,zD)(3)A (4)B (5)B(8)C (9)B (10)BB)a,g,m,h,q,n,p,x,zC)g,m,q,a,n,p,x,h,zD)(3)A (4)B (5)B(8)C (9)B (10)B一、單項(xiàng)選擇題B (2)DC (7)A一、單項(xiàng)選擇題(每小題2分，共20分)(1)設(shè)Huffman樹(shù)的葉子結(jié)點(diǎn)數(shù)為m,則結(jié)點(diǎn)總數(shù)為( )。A)2m2m-1A)2m2m+l D)m+1(2)若順序存儲(chǔ)的循環(huán)隊(duì)列的QueueMaxSize二n,則該隊(duì)列最多可存儲(chǔ)( )個(gè)元素。A)n B)n-l C)n+1 D)不確定(3)下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？( )A)存儲(chǔ)密度大 B)插入和刪除運(yùn)算方便C)獲取符合某種條件的元素方便 D)查找運(yùn)算速度快(4)設(shè)有一個(gè)二維數(shù)組A[m][n],假設(shè)A[0][0]存放位置在600(10),A[3][3]存放位置在678(10),每一個(gè)元素占一個(gè)空間，問(wèn)A[2][3](10)存放在什么位置？(腳注(10)表示用10進(jìn)制表示，m>3)( )oA)658 B)648 C)633 D)653(5)下列關(guān)于二叉樹(shù)遍歷的敘述中，正確的是()。A)若一個(gè)葉子是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)B)若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)0若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)D)若一個(gè)樹(shù)葉是某二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷最后一個(gè)結(jié)點(diǎn)(6)k層二叉樹(shù)的結(jié)點(diǎn)總數(shù)最多為( )。A)2k-l B)2k+l C)2K-1 D)2k-1(7)對(duì)線性表進(jìn)行二分法查找，其前提條件是( )。A)線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序B)線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C)線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序0)線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序(8)對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為()oA)0(log2n) B)0(n) C)0(1) D)0(n2)(9)對(duì)于線性表(7,34,77,25,64,49,20,14)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%7作為散列函數(shù)，則散列地址為0的元素有()個(gè)。A)1 B)2 C)3 D)4(10)下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是()oA)數(shù)組是不同類型值的集合B)遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C)樹(shù)是一種線性結(jié)構(gòu)D)用一維數(shù)組存儲(chǔ)一棵徹底二叉樹(shù)是有效的存儲(chǔ)方法一、單項(xiàng)選擇題(每小題2分,共20分)(1)B (2)B (3)A (4) D (5)A(6)A (7)C (8)C (9) D (10)D一、單項(xiàng)選擇題(每小題2分，共20分)(1)對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下( )方面的內(nèi)容。A)茁壯性和可讀性 B)并行性0正確性D)時(shí)空復(fù)雜度(2)在帶有頭結(jié)點(diǎn)的單鏈表HL中，耍向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行)oA)p->next=HL->next;HL->next=p B)p->next=HL;HL=pC)p->next=HL;p=HL D)HL=p;p->next=HLTOC\o"1-5"\h\z(3)對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( )A)時(shí)常需要隨機(jī)地存取元素 B)時(shí)常需要進(jìn)行插入和刪除操作C)表中元素需要占領(lǐng)一片連續(xù)的存儲(chǔ)空間 D)表中元素的個(gè)數(shù)不變一個(gè)棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是( )oA)231 B)321 0312 D)123(5)每一趟都能選出一個(gè)元素放在其最終位置上，并且不穩(wěn)定的排序算法是( )。A)冒泡排序B)簡(jiǎn)單選擇排序C)希爾排序D)直接插入排序(6)采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度( )oA)低于鏈接法處理沖突 B)高于鏈接法處理沖突0與鏈接法處理沖突相同 D)高于二分查找(7)若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為( )參數(shù)。A)值 B)函數(shù) C)指針 D)引用(8)在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每一個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的)oA)行號(hào) B)列號(hào) C)元素值 D)非零元素個(gè)數(shù)(9)快速排序在最壞情況下的時(shí)間復(fù)雜度為()oA)0(log2n) B)0(nlog2n) C)0(n) D)0(n2)(10)從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為()oA)0(n) B)0(1) C)0(log2n) D)0(n2)一、單項(xiàng)選擇題(每小題2分，共20分)B (2)A(3)B (4)C (5)BB(7)D(8)A(9)D(10)C一、單項(xiàng)選擇題(每小題2分，共20分)(1)以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？( )A)有向圖 B)棧 C)二叉樹(shù) D)B樹(shù)(2)若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用( )存儲(chǔ)方式最節(jié)省時(shí)間。A)單鏈表B)雙鏈表 C)帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D)單循環(huán)鏈表(3)()不是隊(duì)列的基本運(yùn)算。A)在隊(duì)列第i個(gè)元素之后插入一個(gè)元素 B)從隊(duì)頭刪除一個(gè)元素C)判斷一個(gè)隊(duì)列是否為空 D)讀取隊(duì)頭元素的值(4)字符A、B、C、D挨次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成( )個(gè)不同的字符串？A)15 B)14 C)16 D)21(5)由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為()oA)11 B)37 C)19 D)53以下6-8題基于下面的敘述：若某二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為A、B、C、D、E、F、G,后序遍歷的序列為B、D、C、A、F、G、EoTOC\o"1-5"\h\z(6)則該二叉樹(shù)結(jié)點(diǎn)的前序遍歷的序列為( )oA)E、G、F、A、C、D、B B)E、A、G、C、F、B、DC)E、A、C、B、D、G、F D)E、G、A、C、D、F、B(7)該二叉樹(shù)有()個(gè)葉子。A)3 B)2 C)5 D)4(8)該二叉樹(shù)的按層遍歷的序列為( )oA)E、G、F、A、C、D、B B)E、A、C、B、D、G、FC)E、A、G、C、F、B、D D)E、G、A、C、D、F、B(9)下面的二叉樹(shù)中，( )不是徹底二叉樹(shù)。(10)設(shè)有關(guān)鍵碼序列(10)設(shè)有關(guān)鍵碼序列(q,g,m,z,a),()序列是從上述序列出發(fā)建的小根堆的結(jié)A)a,g,A)a,g,m,q,zB)a,g,m,z,q C)g,m,q,a,zD)g,m,a,q,z一、單項(xiàng)選擇題(每小題2(1)一、單項(xiàng)選擇題(每小題2(1)B (2)C(6)C (7)A一、單項(xiàng)選擇題(每小題2(1)隊(duì)列的特點(diǎn)是(A)先進(jìn)后出C)任意位置進(jìn)出分，共20分)(3)A(4)B(8)C (9)C分,共20分))oB)先進(jìn)先出D)前面都不正確⑸B(10)B(2)有n個(gè)記錄的文件，如關(guān)鍵字位數(shù)為d,基數(shù)為r,則基數(shù)排序共要進(jìn)行( )遍分配與采集。A)nB)dC)rD)n-dA)nB)dC)rD)n-d(3)在二叉樹(shù)結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序)oA)都不相同 B)徹底相同C)先序和中序相同，而與后序不同 D)中序和后序相同，而與先序不同TOC\o"1-5"\h\z(4)限定在一端加入和刪除元素的線性表稱為( )。A)雙向鏈表 B)單向鏈表C)棧 D)隊(duì)列(5)快速排序執(zhí)行一遍之后，已經(jīng)到位的元素個(gè)數(shù)是( )。D)B的根為p,p的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)A)1 D)B的根為p,p的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)(6)設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為B,它有m個(gè)結(jié)點(diǎn),為n,森林F中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是()oA)m-n-1B)n+1C)mrn+lD)m-nA)m-n-1B)n+1C)mrn+lD)m-n⑺設(shè)有198個(gè)初始?xì)w并段，如采用K-路平衡歸并三遍完成排序，則K值最大為()oA)12 B)13 C)14 D)15(8)下面關(guān)于廣義表的敘述中，不正確的是( )。A)廣義表可以是一個(gè)多層次的結(jié)構(gòu) B)廣義表至少有一個(gè)元素C)廣義表可以被其他廣義表所共享 D)廣義表可以是一個(gè)遞歸表(9)設(shè)二叉樹(shù)根結(jié)點(diǎn)的層次為0,一棵深度(高度)為k的滿二叉樹(shù)和同樣深度徹底二叉樹(shù)各有f個(gè)結(jié)點(diǎn)和c個(gè)結(jié)點(diǎn)，下列關(guān)系式不正確的是()oA)f〉=cB)c>fC)f=2k+l-aD)c>sk-l(10)從L=((apple,pear),(orange,banana))中，取出banana元素的表達(dá)式為()。head(tail(L))head(head(tail(L)))tai1(head(tai1(L)))head(tail(head(tai1(L))))一、單項(xiàng)選擇題(每小題2head(tail(L))head(head(tail(L)))tai1(head(tai1(L)))head(tail(head(tai1(L))))一、單項(xiàng)選擇題(每小題2(1)B(2)B分,共20分)(3)B(4)C(6)D(7)C(8)B(9)B(10)DTOC\o"1-5"\h\z(1)下列文件的物理結(jié)構(gòu)中，不利于文件長(zhǎng)度動(dòng)態(tài)增長(zhǎng)的文件物理結(jié)構(gòu)是( )oA)順序結(jié)構(gòu) B)鏈接結(jié)構(gòu) C)索引結(jié)構(gòu)D)Hash結(jié)構(gòu)(2)在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素可由()oA)實(shí)體 B)域 C)數(shù)據(jù)項(xiàng) D)字段(3)對(duì)于有n個(gè)頂點(diǎn)的有向圖，由弗洛伊德(Floyd)算法求每一對(duì)頂之間的最短路徑的時(shí)間復(fù)雜度是( )oA)0(1) B)0(n) C)0(n) D)0(n3)(4)對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間為( )。A)0(1) B)0(log2n) C)0(n) D)0(n2)(5)哈夫曼樹(shù)中一定不存在( )。A)度為0的結(jié)點(diǎn)B)度為1的結(jié)點(diǎn)C)度為2的結(jié)點(diǎn)D)帶權(quán)的結(jié)點(diǎn)(6)設(shè)D={A,B,C,D},R={<E,A>,<A,B>,<B,D>,<D,E>,<D,A>},則數(shù)據(jù)結(jié)構(gòu)(D,{R})是( )oA)樹(shù) B)圖 B)線性表D)前面都正確(7)( )關(guān)鍵碼序列不符合堆的定義。A、C、D、G、H、M、P、Q、R、XA、C、M、D、H、P、X、G、Q、RA、D、P、R、C、Q、X、M、H、GA、D、C、M、P、G、H、X、R、Q(8)假定關(guān)鍵字K=442205883,允許存儲(chǔ)地址為四位十進(jìn)制數(shù)，并且Hash地址為6111,則所采用的構(gòu)造Hash函數(shù)的方法是( )。A)直接定址法B)平方取中法C)除留余數(shù)法，模為97D)折疊法(9)在算法的時(shí)間復(fù)雜度中，n表示問(wèn)題規(guī)模，f(n)表示基本操作重復(fù)執(zhí)行的次數(shù)，則隨問(wèn)題的規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率同( )相同。A)f(n)B)n C)0(n) D)前面都不正確(10)對(duì)線性表進(jìn)行二分法查找，其前提條件是()oA)線性表以順序方式存儲(chǔ),A)線性表以順序方式存儲(chǔ),B)線性表以順序方式存儲(chǔ),C)線性表以鏈接方式存儲(chǔ),D)線性表以鏈接方式存儲(chǔ),并且按關(guān)鍵碼值的檢索頻率排好序并且按關(guān)鍵碼值排好序并且按關(guān)鍵碼值的檢索頻率排好序一、單項(xiàng)選擇題(每小題2一、單項(xiàng)選擇題(每小題2分，(1)A (2)C (3)(6)B (7)C (8)一、單項(xiàng)選擇題(每小題2分，共20分)D (4)B (5)BD (9)A (10)A共20分)(1)若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限雙端隊(duì)列得到，也不能由輸出受限雙端隊(duì)列得到的輸出序列是( )oA)1234 B)4132 C)4231 D)4213(2)將一個(gè)A[l..100,L.100]的三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組B[298]中，A中元素a66,65(即該元素下標(biāo))在B數(shù)組中的位置k為()(假設(shè)B[0]的位置是1)。A)198 B)195 C)197 D)198【分析】如下所示，三對(duì)角矩陣第1行和最后1行非零元素個(gè)數(shù)為2個(gè)，其余各行的非零元素個(gè)數(shù)是3個(gè)，所知a66,65前面共有2+3*64=194個(gè)非零元素，a66,65本身是第195個(gè)非零元。(3)若度為m的哈夫曼樹(shù)中，其葉結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù)為()oA)n-1 B)C)D)(4)若一個(gè)有向圖具有拓?fù)渑判蛐蛄?，并且頂點(diǎn)按拓?fù)渑判蛐蛄芯幪?hào)，那末它的鄰接矩陣必然為()oA)對(duì)稱矩陣 B)稀疏矩陣 C)三角矩陣 D)普通矩陣(5)設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為有m個(gè)結(jié)點(diǎn)，此二叉樹(shù)根的左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為k,則另一棵子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為( )。A)m-k+1 B)k+1C)m-k-l D)m-k(6)假定有K個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這K個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行()次探測(cè)。A)K-1次B)K次 C)K+1次 D)K(K+l)/2次(7)一棵深度為k的平衡二叉樹(shù)，其每一個(gè)非終端結(jié)點(diǎn)的平衡因子均為0,則該樹(shù)共有( )個(gè)結(jié)點(diǎn)。A)2k-l-l B)2k-l C)2k-l+lD)2k-l(8)如表r有100000個(gè)元素，前99999個(gè)元素遞增有序，則采用( )方法比較次數(shù)較少。A)直接插入排序B)快速排序C)歸并排序D)選擇排序(9)如果只考慮有序樹(shù)的情形，那末具有7個(gè)結(jié)點(diǎn)的不同形態(tài)的樹(shù)共有( )棵。A)132B)154 C)429 D)前面均不正確(10)對(duì)ISAM文件的刪除記錄時(shí)，普通( )A)只需做刪除標(biāo) B)需挪移記錄0需改變指針 D)一旦刪除就要做整理一、單項(xiàng)選擇題(每小題2分，共20分)(1)參考答案：C)(2)【分析】如下所示，三對(duì)角矩陣第1行和最后1行非零元素個(gè)數(shù)為2個(gè)，其余各行的非零元素個(gè)數(shù)是3個(gè)，所知a66,65前面共有2+3*64=194個(gè)非零元素，a66,65本身是第195