線性表是又窮序列,由0或者多個元素組成,長度為零的稱為空表

線性表的順序存儲結構:數組
線性表的鏈式存儲結構:鏈表
數組可以實現隨機訪問,和隨機存儲,簡稱隨機存取的存儲結構
鏈表必須按照順序從頭節點開始尋找,簡稱順序存取的存儲結構
索引存取的存儲結構:Map,節點維護一個索引表,按照索引來進行存取
線性表是邏輯結構,而數組和鏈表是線性表的兩種實現,是存儲結構(具體實現)

ABD
二叉樹的順序存儲結構:將二叉樹當做一個完全二叉樹,或者滿二叉樹,按照層次遍歷的方式將二叉樹存儲在數組中,對于二叉樹中的空節點,使用某種空標志來替代,浪費大量空間
邏輯上相鄰的,物理存儲不一定相鄰
棧和隊列就具有查找操作
D選項有問題

O(1)是指常數時間
單鏈表,單向循環鏈表,雙向鏈表,都是O(n)

線性表是具有相同數據類型的n個數據元素構成的有限序列
數據項構成了數據元素
頭結點,就是為了操作上的方便,也就是方便運算的實現,不是為了表明表節點中首節點的位置(使用頭指針也可以表明)

鏈表,如果需要在最后插入和刪除的話, 需要 從頭結點,一直順序找到尾節點

D
循環單鏈表的最后一個元素的指針指向頭結點,如果循環單鏈表只設頭指針,那么如果需要找到尾節點進行操作,需要遍歷整個鏈表
循環鏈表的尾指針,只要next一下,就是頭結點,所以,如果只是對最后一個元素和第一個元素進行操作,可以使用僅有頭指針的單循環鏈表,這樣,如果對最后一個元素進行操作(刪除),只需要直接使用尾指針進行操作,而如果需要對頭指針進行操作(插入),僅僅需要將尾指針next一線即可

如果使用帶尾指針的單循環鏈表,在刪除尾節點的時候,需要遍歷整個線性表,找到尾節點的前一個節點,而是使用帶有頭結點的雙循環鏈表,可以使得頭結點直接退一步會這兩個節點,找到對應的節點

D ,同上

B,存儲結構能反映數據之間的邏輯關系,應該用鏈表,而不是線性表

A,線性表可以實現隨機讀取,所以讀取時間最少

D

指針
鏈表中的指針不是指向數據元素的,而是指向包裝了數據元素和指針的節點的,所以,屬于之間的關系是通過指針來實現的,而不是通過指示數據元素的指針來實現的

C
靜態鏈表是借助數組來描述線性表的鏈式存儲結構,結點也有數據域和指針域,與鏈表中的指針不同的是,這里的指針是節點的相對地址(數組下標,也成為游標),靜態鏈表在使用前也需要分配一塊連續的內存空間
適用于不支持指針的語言中

B

A

B

C,靜態鏈表需要提前分配空間,如果只有少量的數據,則會有浪費的存儲空間

C

好題

由于1<= i <= n+1,所以,概率為(1/(n+1)), 平均移動次數為:
(1/(n+1)) * (n(n+1)/2) == n/2

A

C

C

D

D

以下是帶有頭結點的循環單鏈表,Header指向頭結點,線性表的長度,指的是不算頭結點的長度

1,不含任何元素,只有一個頭結點,則head->next->next->next還是head
2,含有兩個元素

C
單鏈表默認為只有頭指針,那么需要將長度為m的鏈表的頭指針,移動到鏈表的尾部,也就是需要O(m)的時間復雜度

D

轉載于:https://juejin.im/post/5b67b57f6fb9a04fb8776e64

總結

以上是生活随笔為你收集整理的算法与数据结构1800题 之线性表 (一)的全部內容，希望文章能夠幫你解決所遇到的問題。

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