《數(shù)據(jù)結(jié)構(gòu)》2020年春季學(xué)期在線作業(yè)（三）
試卷總分:100 得分:100
第1題,對(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)的取值范圍
D、計(jì)算機(jī)的硬件
正確答案:
第2題,題目和答案如下圖所示：
A、A
B、B
C、C
D、D
正確答案:
第3題,AVL樹(shù)是一種平衡的二叉排序樹(shù)，樹(shù)中任一結(jié)點(diǎn)的（ ）。
A、左、右子樹(shù)的高度均相同
B、左、右子樹(shù)高度差的絕對(duì)值不超過(guò)1
C、左子樹(shù)的高度均大于右子樹(shù)的高度
D、左子樹(shù)的高度均小于右子樹(shù)的高度
正確答案:
第4題,單鏈表中，增加頭結(jié)點(diǎn)的目的是為了（ ）。
A、使單鏈表至少有一個(gè)結(jié)點(diǎn)
B、標(biāo)示表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置
C、方便運(yùn)算的實(shí)現(xiàn)
D、說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)
正確答案:
第5題,設(shè)有一個(gè)無(wú)向圖G=（V，E）和G’=（V’，E’）如果G’為G的生成樹(shù)，則下面不正確的說(shuō)法是（ ）。
A、G’為G 的子圖
B、G’為G 的連通分量
C、G’為G的極小連通子圖且V’=V
D、G’為G的一個(gè)無(wú)環(huán)子圖
正確答案:
第6題,題目和答案如下圖所示：
A、A
B、B
C、C
D、D
正確答案:
第7題,設(shè)A是n*n的對(duì)稱矩陣，將A的對(duì)角線及對(duì)角線上方的元素以列為主的次序存放在一維數(shù)組B[1..n(n+1)/2]中，對(duì)上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置為（ ）。
A、i(i-l)/2+j
B、j(j-l)/2+i
C、j(j-l)/2+i-1
D、i(i-l)/2+j-1
正確答案:
第8題,關(guān)于算法，下面描述正確的是（ ）。
A、時(shí)間復(fù)雜度就是算法的執(zhí)行時(shí)間
B、算法必須有輸入量和輸出量
C、算法就是程序
D、時(shí)間復(fù)雜度僅反映時(shí)間關(guān)于問(wèn)題規(guī)模的增長(zhǎng)率
正確答案:
第9題,設(shè)有13個(gè)值，用它們組成一棵哈夫曼樹(shù)，則該哈夫曼樹(shù)共有（ ）個(gè)結(jié)點(diǎn)。
A、13
B、12
C、26
D、25
正確答案:
第10題,在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素的物理位置（ ），在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素的物理位置（ ）。
A、必相鄰 必相鄰
B、必相鄰 不一定相鄰
C、不一定相鄰 必相鄰
D、不一定相鄰 不一定相鄰
正確答案:
第11題,某非空二叉樹(shù)的先序和后序序列正好相反，則二叉樹(shù)一定是（ ）的二叉樹(shù)。
A、空或只有一個(gè)結(jié)點(diǎn)
B、高度等于其結(jié)點(diǎn)數(shù)
C、任一結(jié)點(diǎn)無(wú)左孩子
D、任一結(jié)點(diǎn)無(wú)右孩子
正確答案:
第12題,已知含10個(gè)結(jié)點(diǎn)的二叉排序樹(shù)是一棵完全二叉樹(shù)，則該二叉排序樹(shù)在等概率情況下查找成功的平均查找長(zhǎng)度等于（ ）。
A、1.0
B、2.9
C、3.4
D、5.5
正確答案:
第13題,樹(shù)根的層次為1，則有64個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（ ）。
A、8
B、7
C、6
D、5
正確答案:
第14題,下面關(guān)于圖的存儲(chǔ)的敘述中正確的是（ ）。
A、用相鄰矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)
B、用相鄰矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)
C、用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)
D、用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)
正確答案:
第15題,一個(gè)含n個(gè)頂點(diǎn)和e條弧的有向圖以鄰接矩陣表示法為存儲(chǔ)結(jié)構(gòu)，則計(jì)算該有向圖中某個(gè)頂點(diǎn)出度的時(shí)間復(fù)雜度為（ ）。
A、O(n)
B、O(e)
C、O(n+e)
D、O(n2)
正確答案:
第16題,線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲(chǔ)。
A、錯(cuò)誤
B、正確
正確答案:
第17題,有n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。
A、錯(cuò)誤
B、正確
正確答案:
第18題,將一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)后，根結(jié)點(diǎn)沒(méi)有左子樹(shù)。
A、錯(cuò)誤
B、正確
正確答案:
第19題,哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。
A、錯(cuò)誤
B、正確
正確答案:
第20題,二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)，當(dāng)某個(gè)結(jié)點(diǎn)只有一棵子樹(shù)時(shí)無(wú)所謂左、右子樹(shù)之分。
A、錯(cuò)誤
B、正確
正確答案:
