《數據結構》2020年春季學期在線作業(yè)（三）
試卷總分:100    得分:100
第1題,對于一組結點，從空樹開始，把他們插入到二叉排序樹中，就建立了一棵二叉排序樹。這時，整個二叉排序樹的形狀取決于（   ）。
A、結點的輸入順序
B、結點的存儲結構
C、結點的取值范圍
D、計算機的硬件
正確答案:


第2題,題目和答案如下圖所示：
A、A
B、B
C、C
D、D
正確答案:


第3題,AVL樹是一種平衡的二叉排序樹，樹中任一結點的（   ）。
A、左、右子樹的高度均相同
B、左、右子樹高度差的絕對值不超過1
C、左子樹的高度均大于右子樹的高度
D、左子樹的高度均小于右子樹的高度
正確答案:


第4題,單鏈表中，增加頭結點的目的是為了（   ）。
A、使單鏈表至少有一個結點
B、標示表結點中首結點的位置
C、方便運算的實現
D、說明單鏈表是線性表的鏈式存儲實現
正確答案:


第5題,設有一個無向圖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題,設A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數組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題,關于算法，下面描述正確的是（   ）。
A、時間復雜度就是算法的執(zhí)行時間
B、算法必須有輸入量和輸出量
C、算法就是程序
D、時間復雜度僅反映時間關于問題規(guī)模的增長率
正確答案:


第9題,設有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有（   ）個結點。
A、13
B、12
C、26
D、25
正確答案:


第10題,在線性表的順序存儲結構中，邏輯上相鄰的數據元素的物理位置（   ），在鏈式存儲結構中，邏輯上相鄰的數據元素的物理位置（   ）。
A、必相鄰 必相鄰
B、必相鄰 不一定相鄰
C、不一定相鄰 必相鄰
D、不一定相鄰 不一定相鄰
正確答案:


第11題,某非空二叉樹的先序和后序序列正好相反，則二叉樹一定是（   ）的二叉樹。
A、空或只有一個結點
B、高度等于其結點數
C、任一結點無左孩子
D、任一結點無右孩子
正確答案:


第12題,已知含10個結點的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于（   ）。
A、1.0
B、2.9
C、3.4
D、5.5
正確答案:


第13題,樹根的層次為1，則有64個結點的完全二叉樹的深度為（   ）。
A、8
B、7
C、6
D、5
正確答案:


第14題,下面關于圖的存儲的敘述中正確的是（   ）。
A、用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中結點個數有關，而與邊數無關
B、用相鄰矩陣法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關
C、用鄰接表法存儲圖，占用的存儲空間大小只與圖中結點個數有關，而與邊數無關
D、用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關
正確答案:


第15題,一個含n個頂點和e條弧的有向圖以鄰接矩陣表示法為存儲結構，則計算該有向圖中某個頂點出度的時間復雜度為（   ）。
A、O(n)
B、O(e)
C、O(n+e)
D、O(n2)
正確答案:


第16題,線性的數據結構可以順序存儲，也可以鏈接存儲。非線性的數據結構只能鏈接存儲。
A、錯誤
B、正確
正確答案:


第17題,有n個頂點的無向圖，采用鄰接矩陣表示，圖中的邊數等于鄰接矩陣中非零元素之和的一半。
A、錯誤
B、正確
正確答案:


第18題,將一棵樹轉換成二叉樹后，根結點沒有左子樹。
A、錯誤
B、正確
正確答案:


第19題,哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近。
A、錯誤
B、正確
正確答案:


第20題,二叉樹中不存在度大于2的結點，當某個結點只有一棵子樹時無所謂左、右子樹之分。
A、錯誤
B、正確
正確答案: