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