1.將N個數據按照從小到大順序組織存放在一個單向鏈表中。如果采用二分查找，那么查找的平均時間復雜度是O(logN)。
F
解析：
二分查找的平均復雜度是O（logN）沒有錯，一看到這個就跳坑了。然后知道陷阱來了！按順序存放在單項鏈表中。二分查找是不可以用鏈表存儲的：
這是由鏈表的特性決定的。鏈表是很典型的順序存取結構，數據在鏈表中的位置只能通過從頭到尾的順序檢索得到，即使是有序的，要操作其中的某個數據也必須從頭開始。
這和數組有本質的不同。數組中的元素是通過下標來確定的，只要你知道了下標，就可以直接存儲整個元素，比如a[5],是直接的。鏈表沒有這個，所以，折半查找只能在數組上進行。

2. 在單鏈表中，要訪問某個結點，只要知道該結點的指針即可。因此，單鏈表是一種隨機存取結構。
F
解析：
線性表分(順序存儲和鏈式存儲)
順序存儲即數組,我們使用數組的時候申請的是連續的內存空間可以直接讀取的，a[24],a[25]
鏈式存儲即鏈表，鏈表中單個節點的內存地址不是連續的，而是散列在計算機中，通過next指針訪問下一個節點，所以所必須遍歷鏈表才能讀取數據！
總結:
順序表:順序存儲，隨機讀取
鏈式:隨機存儲,順序讀取(必須遍歷)

3. 取線性表的第i個元素的時間同i的大小有關。
F
解析：
線性表分順序表和鏈表
順序表最主要的特點是隨機訪問，即通過首地址和元素序號可以在O(1)的時間內找到指定的元素
線性表因為是按序號直接取值，所以沒有關系，但如果是鏈式存儲結構就有關系

4.在具有頭結點的鏈式存儲結構中，頭指針指向鏈表中的第一個元素結點。F
解析：
頭指針 指示鏈表中第一個結點（即第一個數據元素的存儲映像）的存儲位置。同時，由于最后一個數據元素沒有直接后繼，則線性鏈表中最后一個結點的指針為“空”（NULL）。
有時在單鏈表的第一個結點之前附設一個結點，稱之為頭結點 。 頭結點的數據域可以不存儲任何信息，也可以存儲如線性表長度等類的附加信息，頭結點的指針域存儲指向第一個結點的指針（即第一個元素結點的存儲位置）。單鏈表的頭指針指向頭結點。若線性表為空，則頭結點的指針域為“空”。

有頭結點的鏈表結構中，頭指針指向鏈表的頭結點，因為單鏈表不具有回溯性，即通過指針指向的節點不能找到該節點的前一個節點，只能找到后面的節點。

目的是便于鏈表的操作；比如刪除第一個數據節點時，讓頭結點的指針域指向第二個數據節點即可。如果頭指針指向的是第一個數據節點，那么通過此指針不能找到前一個節點，也就不能實現刪除。

5.在一個設有頭指針和尾指針的單鏈表中,執行刪除該單鏈表中最后一個元素的操作與鏈表的長度無關F
解析：
必須要遍歷到倒數第二個元素把它設為尾部（鏈表不是雙向鏈表）

6.在用數組表示的循環隊列中，front值一定小于等于rear值。F
解析：
rear在對max取余之后會從零開始，但這時front并不是零。所以會出現front>rear,（ >,=,<三種情況都有可能出現）
（可以這樣理解：因為是循環的，所以可能rear由大變小，畫個圖就知道了。）

7.若采用“隊首指針和隊尾指針的值相等”作為環形隊列為空的標志，則在設置一個空隊時只需將隊首指針和隊尾指針賦同一個值，不管什么值都可以。T
解析：
判斷隊滿的方式一：犧牲一個存儲的單元來區分空隊、滿隊

約定：當隊頭指針在隊尾指針的下一個位置時，隊滿
隊空：q.frontq.rear
隊滿：(q.rear+1)%MAXSIZEq.front
隊列中的元素個數：(q.rear-q.front+MAXSIZE)%MAXSIZE

8.存在一棵總共有2016個結點的二叉樹，其中有16個結點只有一個孩子F
解析：
沒確定是什么類型的二叉樹
二叉樹的類型：
滿二叉樹：除最后一層無任何子節點外，每一層上的所有結點都有兩個子結點二叉樹。
完全二叉樹：一棵二叉樹至多只有最下面的一層上的結點的度數可以小于2，并且最下層上的結點都集中在該層最左邊的若干位置上，則此二叉樹成為完全二叉樹
平衡二叉樹：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹

9.具有10個葉結點的二叉樹中，有9個度為2的結點。T
解析：
度為0的節點稱為葉節點
葉結點個數=度為2的結點個數+1

一棵深度為k，且有(2^k) -1個結點的二叉樹。這種樹的特點是每一層上的結點數都是最大結點數（2）。而在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且或者最后一層是滿的，或者是在右邊缺少連續若干結點，則此二叉樹為完全二叉樹

具有n個節點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個葉子節點，至多有2k-1個節點

10.在含有n個結點的樹中，邊數只能是n-1條。T
解析：
樹中是不存在環的，對于有N個節點的樹，必定是N-1條邊 。

11.完全二叉樹中，若一個結點沒有左孩子，則它必是樹葉。T
解析：
根據第9題中完全二叉樹的定義可知：
完全二叉樹如果沒有左結點，則一定沒有右結點，即沒有左孩子，它就一定是樹葉

12.一棵有n個結點的二叉樹，從上至下，從左到右用自然數依次編號，則編號為i的結點的左兒子的編號為2i(2i<n）,右兒子的編號是2i+1(2i+1<n)。F

13.一棵有124個結點的完全二叉樹，其葉結點個數是確定的。T
解析：
一棵124個葉結點的完全二叉樹，假設n0為葉子結點數，n1為度為1結點數，n2為度為2結點數，則有總結點數為n0+n1+n2;而n2=n0-1=123；且完全二叉樹中度為1的結點只能為一個或0個，所以總結點數為124+1+123=248個

14.非空的二叉樹一定滿足：某結點若有左孩子，則其中序前驅一定沒有右孩子T
解析：
所謂中序遍歷就是左子樹、根、右子樹 設某結點為A，它的中序前驅是B 按照正常中序遍歷的次序中，如果B有右子樹，則B遍歷完了后會遍歷其右子樹，而不是馬上遍歷A，但是現在是B遍歷完了就是A，因此： 某結點如果有左孩子，則其中序前驅一定沒有右孩子

15.在有N個元素的最大堆中，隨機訪問任意鍵值的操作可以在O(logN)時間完成F
解析：
堆的左右孩子沒有固定的順序，無法像平衡二叉樹那樣順著找下去。

總結

以上是生活随笔為你收集整理的数据结构判断题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。