中石油華東《數(shù)據(jù)結(jié)構(gòu)》2020年秋季學(xué)期在線(xiàn)作業(yè)（三）答案

1、數(shù)據(jù)結(jié)構(gòu)2020年秋季學(xué)期在線(xiàn)作業(yè)（三）試卷總分:100 得分:100一、單選題 (共 15 道試題,共 75 分)1.下列說(shuō)法正確的是 （ ）。A.樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先根遍歷序列相同B.樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后根遍歷序列相同C.樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先根遍歷序列相同D.樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后根遍歷序列相同答案:A2.題目和答案如下圖所示：圖A.AB.BC.CD.D答案:B3.下列判斷正確的是（ ）。A.二叉樹(shù)是樹(shù)的特例。B.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為n/2。C.Huffman樹(shù)是帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，樹(shù)中權(quán)值越大的葉子結(jié)點(diǎn)距離根

2、結(jié)點(diǎn)越遠(yuǎn)。D.棧和隊(duì)列都是限制存取點(diǎn)的線(xiàn)性結(jié)構(gòu)。答案:D4.關(guān)于完全二叉樹(shù)，不正確的描述是（ ）。A.每個(gè)結(jié)點(diǎn)必須首先有左兒子，然后才能有右兒子。B.在具有相同結(jié)點(diǎn)的所有二叉樹(shù)中，它的高度最小。C.每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度最多相差為1。D.沒(méi)有度為1的結(jié)點(diǎn)。答案:D5.哈希查找中k個(gè)關(guān)鍵字具有同一哈希值，若用線(xiàn)性探測(cè)法將這k個(gè)關(guān)鍵字對(duì)應(yīng)的記錄存入哈希表中，至少要進(jìn)行（ ）次探測(cè)。A.kB.k-1C.k(k-1)/2D.1+k(k-1)/2答案:C6.在具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)（二叉鏈表表示）中，值為空的鏈域數(shù)為（ ）。A.n-1B.2n-1C.n+1D.2n+1答案:B7.數(shù)組A中，每個(gè)元素A的長(zhǎng)

3、度為3個(gè)字節(jié)，行下標(biāo)i從1到8。列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A58 的起始地址為（ ）。A.SA+141B.SA+180C.SA+222D.SA+225答案:C8.二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，其行下標(biāo)i=0、1、8，列下標(biāo)j=1、2、4、若A按行先存儲(chǔ)，元素A8，5的起始地址與當(dāng)A按列先存儲(chǔ)時(shí)的元素（ ）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。A.A8，5B.A3,10C.A5,8D.A0,9答案:B9.題目和答案如下圖所示：圖A.AB.BC.CD.D答案:D10.二叉查找樹(shù)的查找效率與二叉樹(shù)的樹(shù)型有關(guān), 在（ ）時(shí)其查找效率最低。

4、A.結(jié)點(diǎn)太多B.完全二叉樹(shù)C.呈單枝樹(shù)D.結(jié)點(diǎn)太復(fù)雜。答案:C11.若某線(xiàn)性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表B.單鏈表C.雙鏈表D.單循環(huán)鏈表答案:A12.假設(shè)主串的長(zhǎng)度為m，模式串的長(zhǎng)度為n，KMP算法的時(shí)間復(fù)雜度為（ ）。A.n+mB.n*mC.nD.m答案:A13.題目和答案如下圖所示：圖A.AB.BC.CD.D答案:A14.下面關(guān)于完全二叉樹(shù)的特點(diǎn)敘述不正確的是（ ）。A.只有最后一層是不滿(mǎn)的，不滿(mǎn)層的結(jié)點(diǎn)首先出現(xiàn)在左邊B.至多只有最下面的兩層結(jié)點(diǎn)的度小于2C.左子樹(shù)的高度不會(huì)小于右子樹(shù)的高度，且左、右子樹(shù)高度最大相差±1D.葉子只能出現(xiàn)在最后兩層上；答案:B15.若串S=“software”,其子串?dāng)?shù)目是（ ）。A.8B.37C.36D.9答案:C二、判斷題 (共 5 道試題,共 25 分)16.將一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)后，根結(jié)點(diǎn)沒(méi)有左子樹(shù)。答案:錯(cuò)誤17.二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)，當(dāng)某個(gè)結(jié)點(diǎn)只有一棵子樹(shù)時(shí)無(wú)所謂左、右子樹(shù)之分。答案:錯(cuò)誤18.線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。非線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲(chǔ)。答案:錯(cuò)誤19.有n個(gè)頂點(diǎn)的無(wú)向圖，