關(guān)鍵字：

棧、線索樹、B樹、直接查找、快速排序、基數(shù)排序

循環(huán)隊列、DFS和BFS、堆和二叉排序樹

一、單選

*（怪題）

**（未學習）

二、簡答

1.循環(huán)隊列是如何提出的？如何判別它的空和滿？

為了解決順序隊列的假溢出問題，提出了循環(huán)隊列，即把存儲隊列的表從邏輯上看成一個環(huán)。

判別隊列空和滿有三種方法：

1）采用計數(shù)器判斷，空時，計數(shù)器為0，滿時，計數(shù)器為maxsize；

2）另設(shè)一個布爾變量以匹配隊列的空和滿；

3）少用一個元素的空間，約定入隊前，測試尾指針rear在循環(huán)意義下加1后是否等于頭指針front，若相等則認為隊滿。

空：Q.front==Q.rear

滿：(Q.rear+1)%maxsize==Q.front

隊列元素個數(shù)：(Q.rear-Q.front+maxsize)%maxsize

3.簡要說明深度優(yōu)先遍歷（DFS）和廣度優(yōu)先遍歷（BFS）的不同之處。

DFS深度優(yōu)先遍歷（遞歸，棧）

????類似樹的先序遍歷

????首先訪問圖中某一起始頂點v，接著由v出發(fā)，訪問與v鄰接且未被訪問的任一頂點w1，再訪問與w1鄰接且未被訪問的頂點w2...

????重復(fù)上述過程，當不能再繼續(xù)向下訪問時，依次退回到最近被訪問的頂點

????若它還有鄰接頂點未被訪問過，則從該點開始繼續(xù)上述搜索過程，直到圖中所有頂點被訪問過為止

BFS廣度優(yōu)先遍歷（非遞歸，隊列）

????類似二叉樹的層次遍歷

????首先訪問起始頂點v，接著由v出發(fā)，依次訪問v的各個未訪問過的鄰接頂點w1，w2...wi

????然后再依次訪問w1，w2...wi的所有未被訪問過的鄰接頂點，再從這些訪問過的頂點出發(fā)，再訪問它們所有未被訪問過的鄰接頂點...

????依次類推，直到圖中所有頂點都被訪問過為止

4.簡述堆和二叉排序樹的區(qū)別。

1）結(jié)構(gòu)上：

二叉排序樹的所有左子樹的結(jié)點都小于根結(jié)點，根結(jié)點又小于所有右子樹的結(jié)點。

而堆（小根堆）：根結(jié)點小于左右子樹，但是左右子樹沒有大小之分。

2）作用上：

二叉排序樹是用來做查找的，而堆是用來做排序的。