1.將N個數據按照從小到大順序組織存放在一個單向鏈表中。如果采用二分查找，那么查找的平均時間復雜度是O(logN)。
F

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

? ? 在單鏈表中，要訪問某個結點，只要知道該結點的指針即可。因此，單鏈表是一種隨機存取結構。
? ? F

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

? ? 取線性表的第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

在這里插入圖片描述

? ? 答案：T
? ? 解析：注意題目中的字眼：“任一指定序號”“最后”，說明已經確定了位置，此時根據時間復雜度，順序線性表的查找為 O(1) ,因為實在最后進行插入和刪除的，所以不涉及元素的移動，（如果插入和刪除的位置不在最后，則刪除過后刪除位置之后的元素要全部往前移，插入時要先將插入位置之后的元素全部往后移來騰出空間插入，所以這是插入和刪除操作的時間復雜度就為 O(n) ）。 如果時線性鏈表，則每次取相應的元素時都要進行遍歷，此時的時間復雜度為 O(n) 。插入和刪除如果指明位置時時間復雜度為 O(1) ,如果沒有指明位置則仍需要先遍歷找到位置再操作，此時的時間復雜度為 O(n) 。