數據結構 試題
前言
這里是 數據結構 系列文章，主要介紹計算機二級考試中的涉及到數據結構的知識點 /
數據結構在計算機科學中處處都有存在，例如編譯系統要使用棧、散列表、語法樹等；操作系統要使用隊列、存儲管理表、目錄樹等等。
關于作者：
- 小白（Libra），計算機興趣愛好者，Java，C，Hadoop，MySQL
- GitHub : https://github.com/Regel-zack
轉載請注明出處
題目
在單鏈表中，增加頭結點的目的是
- 方便運算的實現
- 使單鏈表中至少有一個節點
- 表示表節點中首節點的位置
- 說明單鏈表是線性表的鏈式存儲實現
算法分析的目的是
- 找出數據結構的合理性
- 找出算法中輸入和輸出之間的關系
- 分析算法的易懂性和可靠性
- 分析算法的效率以求改進
對于長度為n的線性表，在最壞情況下，各排序算法所對應的比較次數中正確的是
- 冒泡排序為n/2
- 冒泡排序為n
- 快速排序為n
- 快速排序為n(n-1)/2
已知數據表A中每個元素距離其最終位置不遠，為節省時間，應采用的算法是
- 堆排序
- 直接插入排序
- 快速排序
- 直接選擇排序
下列關于棧的描述中，錯誤的是
- 棧是先進后出的線性表
- 棧只能順序存儲
- 棧具有記憶功能
- 對棧的插入與刪除操作中，不需要改變棧底指針
- 試述二叉樹中前序遍歷，中序遍歷，后序遍歷的順序
解析
頭節點不僅表示了表中首節點的位置，而且根據單鏈表（包含頭節點）的結構，只要掌握了表頭，就能夠訪問整個鏈表，因此增加頭節點目的是為了便于運算的實現。
算法分析是指對一個算法的運行時間和占用空間做定量的分析，一般計算出相應的數量級，常用時間復雜度和空間復雜度表示。分析算法的目的就是要降低算法的時間復雜度和空間復雜度，提高算法的執行效率。
假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往后和n/2遍的從后往前掃描，需要比較次數為n(n-1)/2。快速排序的最壞情況比較次數也是n(n-1)/2。
當數據表中每個元素距離其最終位置不遠，意味著數據表中元素基本有序，在待排序序列基本有序的情況下，采用插入排序所用時間最少。
棧是一種特殊的線性表，這種線性表只能在固定的一端進行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。所以棧又被稱為先進后出表(FILO-First In LastOut)。線性表可以順序存儲，也可以鏈式存儲，棧是線性表，因此也可以采用鏈式存儲結構。
- 根據先左后右的原則下，根據訪問根結點的次序，二叉樹的遍歷分為3種：前序遍歷、中序遍歷和后序遍歷。
- 前序遍歷指，先訪問根結點，再遍歷左子樹，最后遍歷右子數，并且在遍歷左、右子樹的時候，仍然按先訪問根結點，再遍歷左子樹，最后遍歷右子數的順序。
- 中序遍歷指，先遍歷左子樹，再訪問根結點，最后遍歷右子數，并且在遍歷左、右子樹的時候，仍然按先遍歷左子樹，再訪問根結點，最后遍歷右子數的順序。
后序遍歷指，先遍歷左子樹，再遍歷右子數，最后訪問根結點，并且在遍歷左、右子樹的時候，仍然是按先遍歷左子樹，再遍歷右子樹，最后訪問根結點的順序。
圖表復盤
| 題目數量 | 錯誤數量 | 錯誤率 |
|---|---|---|
| 20 | 6 | 30% |
| 涉及知識點 | 出現次數 | 占比 |
|---|---|---|
| 鏈表 | 1 | 14% |
| 算法分析 | 1 | 14% |
| 排序算法 | 3 | 42% |
| 棧 | 1 | 14% |
| 二叉樹 | 1 | 14% |
精度自小數點后兩位
小結
目前來看，排序算法頻率較為突出，占比最大，其他例如鏈表、棧也各占14%，二叉樹雖只有14%，但涉及到的點確實更為復雜，考了前中后序遍歷。
但也不排除有樣本數量過少，分析不夠準確的點
