數據結構 試題
前言
這里是 數據結構 系列文章，主要介紹計算機二級考試中的涉及到數據結構的知識點 /
數據結構在計算機科學中處處都有存在，例如編譯系統要使用棧、散列表、語法樹等；操作系統要使用隊列、存儲管理表、目錄樹等等。
關于作者：
- 小白（Libra），計算機興趣愛好者，Java，C，Hadoop，MySQL
- Email : hewei20031009@163.com
- GitHub : https://github.com/Regel-zack
轉載請注明出處
題目
冒泡排序在最壞情況下的比較次數是
- n(n+1)/2
- nlogn
- n(n-1)/2
- n/2
某二叉樹有5個度為2的節點，則該二叉樹中的葉子節點數是
- 10
- 8
- 6
- 4
對于循環隊列，下列敘述中正確的是
- 隊頭指針是固定不變的
- 隊頭指針一定大于隊尾指針
- 隊頭指針一定小于隊尾指針
- 隊頭指針可以大于隊尾指針，也可以小于隊尾指針
某二叉樹中有n個度為2的結點，則該二叉樹中的葉子節點數為
- n+1
- n-1
- 2n
- n/2
- 支持子程序調用的數據結構是
- 棧
- 樹
- 隊列
- 二叉樹
解析
- 冒泡排序法是一種最簡單的交換類排序方法，它是通過相鄰數據元素的交換逐步將線性表變成有序。
- 假設線性表的長度為n，則在最壞的情況下，冒泡排序需要經過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數為n(n-1)/2。
- 在任意一顆二叉樹中，度為0的節點，總是比度為2的節點多一個。
- 所謂循環隊列，就是將隊列空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。
- 在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置。
- 循環隊列主要有兩種基本運算：入隊運算與退隊運算，每進行一次入隊運算，隊尾指針就進一。
- 每進行一次退隊運算，排頭指針就進一。
- 當rear或front的值等于隊列的長度+1時，就將rear或front的值置為1。一般情況下，rear大于front，因為入隊的元素肯定比出隊的元素多。特殊的情況是rear到達數組的上限后又從數組的低端開始，此時，rear是小于front的。
- 在任意一顆二叉樹中，度為0的節點，總是比度為2的節點多一個。
- 棧是一種只能在一端進行插入或刪除的線性表。在主程序調用子程序時，要首先保存主程序當前的狀態，然后去執行子程序，最終把子程序的執行結果返回到主程序調用子程序時的位置，繼續往下執行，這種調用符合棧的“先進后出”的功能。
圖表復盤
| 題目數量 | 錯誤數量 | 錯誤率 |
|---|---|---|
| 20 | 5 | 25% |
| 20 | 6 | 30% |
| 40 | 11 | 27.5% |
第一行為今日的錯誤數量占比分析 /
第二行開始是前幾日的錯誤數量占比分析 /
最后一行是總的錯誤數量占比分析
今日知識點分布圖
| 涉及知識點 | 出現次數 | 占比 |
|---|---|---|
| 排序算法 | 1 | 20% |
| 二叉樹 | 2 | 40% |
| 隊列 | 1 | 20% |
| 棧 | 1 | 20% |
總知識點分布圖
| 涉及知識點 | 出現次數 | 占比 |
|---|---|---|
| 排序算法 | 4 | 36% |
| 二叉樹 | 3 | 27% |
| 隊列 | 1 | 9% |
| 棧 | 2 | 18% |
| 鏈表 | 1 | 9% |
| 算法分析 | 1 | 9% |
精度取自小數點后兩位
小結
分為兩部分。
先看今日的，今日出現最多的是二叉樹，其余各占20%，當然了，這跟不了解二叉樹的性質有關，而之前一日占比最大的排序算法在今天仍然是錯誤了，其主要原因可能因為，八大排序算法都會被歸為排序算法中，其范圍大，自然錯其中一個也就會增加數量了。
其次是總的，從排名上來看，仍然是排序算法占據榜首，其次是二叉樹，雖然僅僅只有40道題目的樣本，但大概反映了情況，100道題會是一個意義比較大的樣本數量，期待吧。
