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