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