2022年中石油華東《數(shù)據(jù)結(jié)構(gòu)》2018年秋學(xué)期在線作業(yè)

1、 單項(xiàng)題 1: （ ）是指數(shù)據(jù)中的一個(gè)個(gè)的個(gè)體,是數(shù)據(jù)的基本單位；A: 數(shù)據(jù)相 B: 數(shù)據(jù)元素 C: 數(shù)據(jù)結(jié)構(gòu) D: 數(shù)據(jù)類(lèi)型 正確答案： 單項(xiàng)題 2: 二維數(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 , 5 B: A3,10 C: A5,8 D: A0,9 正確答案： 單項(xiàng)題 3: 樹(shù)根的層次為1,就有 64 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（）；A: 8 B: 7 C: 6 D: 5 正確答案

2、： 單項(xiàng)題 4: 某非空二叉樹(shù)的先序和后序序列正好相反,就二叉樹(shù)肯定是（）的二叉樹(shù)；A: 空或只有一個(gè)結(jié)點(diǎn) B: 高度等于其結(jié)點(diǎn)數(shù) C: 任一結(jié)點(diǎn)無(wú)左孩子 D: 任一結(jié)點(diǎn)無(wú)右孩子 正確答案： 單項(xiàng)題 5: 最大容量為n 的循環(huán)隊(duì)列,隊(duì)尾指針是rear ,隊(duì)頭是 front ,就隊(duì)空的條件是（ ）；A: rear+1 % n = front B: rear = front C: rear+1 = front D: rear-l % n = front 正確答案： 單項(xiàng)題 6: 已知含 10 個(gè)結(jié)點(diǎn)的二叉排序樹(shù)是一棵完全二叉樹(shù),就該二叉排序樹(shù)在等概率 情形下查找勝利的平均查找長(zhǎng)度等于（）；A: 1

3、.0 B: 2.9 C: 3.4 D: 5.5 正確答案： 單項(xiàng)題 7: 下面關(guān)于數(shù)據(jù)結(jié)構(gòu)的表達(dá)中,正確的表達(dá)是（）；A: 次序儲(chǔ)備方式的優(yōu)點(diǎn)是儲(chǔ)備密度大,且插、刪除運(yùn)算效率高 B: 鏈表中每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針 C: 包含 n 個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的最大檢索長(zhǎng)度為 log2n D: 將一棵樹(shù)轉(zhuǎn)為二叉樹(shù)后,根結(jié)點(diǎn)無(wú)右子樹(shù) 正確答案： 單項(xiàng)題 8: 在次序儲(chǔ)備（空間大小為m）的循環(huán)隊(duì)列q 中,以下判滿正確選項(xiàng)（）；A: q.front % m = 0 ; B: q.rear % m = 0 ; C: q.front = q.rear ; D: q.front+1 % m = q.rear; 正

4、確答案： 單項(xiàng)題 9: 已知廣義表LS=a,b,c,d,e,f,運(yùn)用 head 和 tail函數(shù)取出LS 中元素 e的運(yùn)算是（）；A: headtailLS B: tailheadLS C: headtailheadtailLS D: headtailtailheadLS 正確答案： 單項(xiàng)題 10: 鏈表不具有的特點(diǎn)是（）；A: 插入、刪除不需要移動(dòng)元素 B: 可隨機(jī)拜訪任一元素 C: 不必事先估量?jī)?chǔ)備空間 D: 所需空間與線性長(zhǎng)度成正比 正確答案： 單項(xiàng)題 11: 有六個(gè)元素6,5,4,3,2,1 的次序進(jìn)棧,問(wèn)以下哪一個(gè)不是合法的出棧序列？（）；A: 5 4 3 6 1 2 B: 4 5

5、3 1 2 6 C: 3 4 6 5 2 1 D: 2 3 4 1 5 6 正確答案： 單項(xiàng)題 12: 如某線性表中最常用的操作是取第i 個(gè)元素和找第i 個(gè)元素的前趨元素,就采納（）儲(chǔ)備方式最節(jié)約時(shí)間；A: 次序表 B: 單鏈表 C: 雙鏈表 D: 單循環(huán)鏈表 正確答案： 單 選 題 13: 已 知 廣 義 表 : A=a,b, B=A,A, C=a,b,A,B, 求 下 列 運(yùn) 算 的 結(jié)果:tailheadtailC = （ ）；A: （a）B: A C: b D: A 正確答案： 單項(xiàng)題 14: 關(guān)于完全二叉樹(shù),不正確的描述是（）；A: 每個(gè)結(jié)點(diǎn)必需第一有左兒子,然后才能有右兒子；B:

6、在具有相同結(jié)點(diǎn)的全部二叉樹(shù)中,它的高度最??；C: 每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度最多相差為 1；D: 沒(méi)有度為 1 的結(jié)點(diǎn)；正確答案： 單項(xiàng)題 15: 假設(shè)主串的長(zhǎng)度為 m,模式串的長(zhǎng)度為 n,BF 算法在一般和最壞情形下的時(shí) 間復(fù)雜性分別為（ ）,所以仍是一個(gè)常用算法；由于有回溯,所以主串輸入后必需儲(chǔ)存；A: n+m n*m B: n m C: n*m n+m D: m n 正確答案： 單項(xiàng)題 16: 假設(shè)主串的長(zhǎng)度為m,模式串的長(zhǎng)度為n,KMP算法的時(shí)間復(fù)雜度為（）；A: n+m B: n*m C: n D: m 正確答案： 單項(xiàng)題 17: 題目和答案如下圖所示：A: A B: B C: C D

7、: D 正確答案： 單項(xiàng)題 18: 判定“ 帶頭結(jié)點(diǎn)的鏈隊(duì)列為空” 的條件是（）；A: Q.front=NULL B: Q.rear=NULL C: Q.front=Q.rear D: Q.front.=Q.rear 正確答案： 單項(xiàng)題 19: 題目和答案如下圖所示：A: A B: B C: C D: D 正確答案： 單項(xiàng)題 20: 對(duì)于一組結(jié)點(diǎn),從空樹(shù)開(kāi)頭,把他們插入到二叉排序樹(shù)中,就建立了一棵二 叉排序樹(shù)；這時(shí),整個(gè)二叉排序樹(shù)的外形取決于（）；A: 結(jié)點(diǎn)的輸入次序 B: 結(jié)點(diǎn)的儲(chǔ)備結(jié)構(gòu) C: 結(jié)點(diǎn)的取值 X 圍 D: 運(yùn)算機(jī)的硬件 正確答案： 單項(xiàng)題 1: （ ）是指數(shù)據(jù)中的一個(gè)個(gè)的個(gè)體,

8、是數(shù)據(jù)的基本單位；A: 數(shù)據(jù)相B: 數(shù)據(jù)元素 C: 數(shù)據(jù)結(jié)構(gòu) D: 數(shù)據(jù)類(lèi)型正確答案： 單項(xiàng)題 2: 二維數(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 , 5 B: A3,10 C: A5,8 D: A0,9 正確答案： 單項(xiàng)題 3: 樹(shù)根的層次為1,就有 64 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（）；A: 8 B: 7 C: 6 D: 5 正確答案： 單項(xiàng)題 4: 某非空二叉樹(shù)的先序和后序序列正好相反

9、,就二叉樹(shù)肯定是（）的二叉樹(shù)；A: 空或只有一個(gè)結(jié)點(diǎn) B: 高度等于其結(jié)點(diǎn)數(shù) C: 任一結(jié)點(diǎn)無(wú)左孩子 D: 任一結(jié)點(diǎn)無(wú)右孩子正確答案： 單項(xiàng)題 5: 最大容量為n 的循環(huán)隊(duì)列,隊(duì)尾指針是rear ,隊(duì)頭是 front ,就隊(duì)空的條件是（ ）；A: rear+1 % n = front B: rear = front C: rear+1 = front D: rear-l % n = front 正確答案： 單項(xiàng)題 6: 已知含 10 個(gè)結(jié)點(diǎn)的二叉排序樹(shù)是一棵完全二叉樹(shù),就該二叉排序樹(shù)在等概率 情形下查找勝利的平均查找長(zhǎng)度等于（）；A: 1.0 B: 2.9 C: 3.4 D: 5.5 正確答案

10、： 單項(xiàng)題 7: 下面關(guān)于數(shù)據(jù)結(jié)構(gòu)的表達(dá)中,正確的表達(dá)是（）；A: 次序儲(chǔ)備方式的優(yōu)點(diǎn)是儲(chǔ)備密度大,且插、刪除運(yùn)算效率高 B: 鏈表中每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針 C: 包含 n 個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的最大檢索長(zhǎng)度為 log2n D: 將一棵樹(shù)轉(zhuǎn)為二叉樹(shù)后,根結(jié)點(diǎn)無(wú)右子樹(shù)正確答案： 單項(xiàng)題 8: 在次序儲(chǔ)備（空間大小為m）的循環(huán)隊(duì)列q 中,以下判滿正確選項(xiàng)（）；A: q.front % m = 0 ; B: q.rear % m = 0 ; C: q.front = q.rear ; D: q.front+1 % m = q.rear; 正確答案： 單項(xiàng)題 9: 已知廣義表LS=a,b,c,d,e

11、,f,運(yùn)用 head 和 tail函數(shù)取出LS 中元素 e的運(yùn)算是（）；A: headtailLS B: tailheadLS C: headtailheadtailLS D: headtailtailheadLS 正確答案： 單項(xiàng)題 10: 鏈表不具有的特點(diǎn)是（）；A: 插入、刪除不需要移動(dòng)元素 B: 可隨機(jī)拜訪任一元素 C: 不必事先估量?jī)?chǔ)備空間 D: 所需空間與線性長(zhǎng)度成正比 正確答案： 單項(xiàng)題 11: 有六個(gè)元素6,5,4,3,2,1 的次序進(jìn)棧,問(wèn)以下哪一個(gè)不是合法的出棧序列？（）；A: 5 4 3 6 1 2 B: 4 5 3 1 2 6 C: 3 4 6 5 2 1 D: 2 3

12、 4 1 5 6 正確答案： 單項(xiàng)題 12: 如某線性表中最常用的操作是取第i 個(gè)元素和找第i 個(gè)元素的前趨元素,就采納（）儲(chǔ)備方式最節(jié)約時(shí)間；A: 次序表 B: 單鏈表 C: 雙鏈表 D: 單循環(huán)鏈表 正確答案： 單 選 題 13: 已 知 廣 義 表 : A=a,b, B=A,A, C=a,b,A,B, 求 下 列 運(yùn) 算 的 結(jié)果:tailheadtailC = （ ）；A: （a）B: A C: b D: A 正確答案： 單項(xiàng)題 14: 關(guān)于完全二叉樹(shù),不正確的描述是（）；A: 每個(gè)結(jié)點(diǎn)必需第一有左兒子,然后才能有右兒子；B: 在具有相同結(jié)點(diǎn)的全部二叉樹(shù)中,它的高度最?。籆: 每個(gè)結(jié)點(diǎn)

13、的左右子樹(shù)的高度最多相差為 1；D: 沒(méi)有度為 1 的結(jié)點(diǎn)；正確答案： 單項(xiàng)題 15: 假設(shè)主串的長(zhǎng)度為 m,模式串的長(zhǎng)度為 n,BF 算法在一般和最壞情形下的時(shí)間復(fù)雜性分別為（ ）,所以仍是一個(gè)常用算法；由于有回溯,所以主串輸入后必需儲(chǔ)存；A: n+m n*m B: n m C: n*m n+m D: m n 正確答案： 單項(xiàng)題 16: 假設(shè)主串的長(zhǎng)度為m,模式串的長(zhǎng)度為n,KMP算法的時(shí)間復(fù)雜度為（）；A: n+m B: n*m C: n D: m 正確答案： 單項(xiàng)題 17: 題目和答案如下圖所示：A: A B: B C: C D: D 正確答案： 單項(xiàng)題 18: 判定“ 帶頭結(jié)點(diǎn)的鏈隊(duì)列為空” 的條件是（）；A: Q.front=NULL B: Q.rear=NU