本文格式為Word版，下載可任意編輯——本科考試常見(jiàn)題型（復(fù)習(xí)提綱）第一部分：概念、線性表、棧和隊(duì)列、串、樹(shù)組與廣義表．算法的五個(gè)重要特性?

．算法的時(shí)間繁雜度、空間繁雜度?．線性表的元素關(guān)系存儲(chǔ)時(shí)如何表達(dá)？

．頭結(jié)點(diǎn)的作用？首結(jié)點(diǎn)、頭結(jié)點(diǎn)、頭指針區(qū)別？

.單鏈表、雙鏈表、循環(huán)鏈表的插入和刪除操作,以及判斷鏈表為空的條件？

．循環(huán)隊(duì)列Q[0，n-1]，頭、尾位置為f、r，隊(duì)滿、隊(duì)空的條件？隊(duì)列元素個(gè)數(shù)計(jì)算？．雙端隊(duì)列、單端受限隊(duì)列的入隊(duì)與出隊(duì)序列關(guān)系？

.元素進(jìn)棧與退棧的過(guò)程？對(duì)已知入棧序列，可能輸出結(jié)果及不可能輸出結(jié)果？.空串與空字符串的區(qū)別？

．給出串匹配算法中已知串的失敗函數(shù)next或nextval的值?

．?dāng)?shù)組A[m][n]的每一個(gè)元素占k個(gè)字節(jié)，數(shù)組總大??？某元素位置？某地址下標(biāo)？.壓縮矩陣的下標(biāo)與存儲(chǔ)地址關(guān)系？

．廣義表的運(yùn)算Gethead()、Gettail()，如從廣義表L中取出某個(gè)部分的運(yùn)算表達(dá)式?.廣義表的存儲(chǔ)結(jié)構(gòu)？如已知一個(gè)廣義表，給出它的存儲(chǔ)結(jié)構(gòu)？其次部分：樹(shù)

．樹(shù)的表示形式？二叉樹(shù)的5條性質(zhì)？二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)？二叉樹(shù)的三種遍歷？.給二叉樹(shù)加上線索（三種線索）？

.具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的最小深度？最大深度？

．n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)順序存儲(chǔ)，葉結(jié)點(diǎn)和非葉結(jié)點(diǎn)的個(gè)數(shù)、范圍？．遍歷方式不同葉結(jié)點(diǎn)的相對(duì)順序如何？，內(nèi)結(jié)點(diǎn)的相對(duì)順序又如何？

.已知二叉樹(shù)的兩種遍歷結(jié)果（一般必需包含一個(gè)中序或?qū)有颍?，?qǐng)構(gòu)造這棵二叉樹(shù)？.樹(shù)的存儲(chǔ)結(jié)構(gòu)有哪些？樹(shù)和森林與二叉樹(shù)的相互轉(zhuǎn)換？（即對(duì)一棵樹(shù)或森林給出二叉鏈表存儲(chǔ)？根據(jù)二叉鏈表存儲(chǔ)畫(huà)出該樹(shù)或森林？）

.已知電文，求哈夫曼編碼需要位數(shù)和具體編碼數(shù)？對(duì)已知序列進(jìn)行哈夫曼編碼？.設(shè)二叉樹(shù)采用二叉鏈表存儲(chǔ)，請(qǐng)編寫(xiě)算法實(shí)現(xiàn)求二叉樹(shù)高度(結(jié)點(diǎn)個(gè)數(shù)，判定是否為平衡二叉樹(shù)，是否為二叉排序樹(shù)等)？第三部分：圖

．無(wú)向圖和有向圖的存儲(chǔ)方法（4種）？十字鏈表(弧結(jié)點(diǎn)，頭結(jié)點(diǎn))的指針域?．圖的遍歷（深度優(yōu)先和廣度優(yōu)先）？圖的遍歷結(jié)果與存儲(chǔ)結(jié)構(gòu)有關(guān)！

.圖的生成樹(shù)？帶權(quán)圖的最小生成樹(shù)？

.有向圖可以進(jìn)行拓?fù)渑判虻臈l件？對(duì)一個(gè)圖進(jìn)行拓?fù)渑判颍?/p>

.對(duì)已知帶權(quán)有向圖，求關(guān)鍵路徑？計(jì)算某源點(diǎn)都其余頂點(diǎn)的最短路徑？.譬如，已知一個(gè)無(wú)向圖的鄰接表

（1）請(qǐng)畫(huà)出該無(wú)向圖；（2）根據(jù)鄰接表，分別寫(xiě)出用DFS和BFS算法從頂點(diǎn)v0開(kāi)始的遍歷該圖后所得到的遍歷序列，并畫(huà)出DFS生成樹(shù)和BFS生成樹(shù)。第四部分：查找

．順序查找方法適合于存儲(chǔ)結(jié)構(gòu)？

．線性表順序查找不成功時(shí)關(guān)鍵字的比較次數(shù)?.有序表的折半查找過(guò)程？查找過(guò)程的判定樹(shù)？．分塊查找(索引表查找)的T(n)的組成及意義？

.二叉排序樹(shù)的形成與查找？如：對(duì)同一組數(shù)據(jù)而言二叉排序樹(shù)是否唯一的?對(duì)二叉排序樹(shù)先刪去x再插入x，新舊二叉排序樹(shù)一致？構(gòu)建二叉排序樹(shù)，請(qǐng)畫(huà)出第i步?.平衡二叉樹(shù)的平衡調(diào)整（4種）？如：對(duì)已知序列構(gòu)造平衡二叉樹(shù)，如有旋轉(zhuǎn)請(qǐng)畫(huà)出旋轉(zhuǎn)前、后的樹(shù)形結(jié)構(gòu)并標(biāo)注旋轉(zhuǎn)類(lèi)型?

．B樹(shù)的元素插入與刪除？如：對(duì)已知序列，畫(huà)出一個(gè)m階Ｂ-樹(shù)？.高為3的5階B-樹(shù)（連葉層在內(nèi)）最少的關(guān)鍵字總數(shù)目?

.哈希表（散列表）中散列函數(shù)構(gòu)造與沖突解決方法？如：已知序列，設(shè)散列函數(shù)H(k)=kmod7，用線性探測(cè)法解決沖突。請(qǐng)建散列表存儲(chǔ)及查找次數(shù)？第五部分：排序

．排序算法的穩(wěn)定性？對(duì)各種排序法中“排序趟〞的概念？

.五類(lèi)排序中主要排序方法有哪些？對(duì)已知序列，可按給定排序方法給出第i趟結(jié)果？.不穩(wěn)定的排序算法有那些？.冒泡排序算法的主要工作量是什么？

．用篩法建堆則必需從什么位置開(kāi)始？堆是一個(gè)數(shù)據(jù)結(jié)構(gòu)嗎？.判斷已知序列是否為堆？如不是，請(qǐng)用篩選建堆？．初始數(shù)據(jù)假使已有序，花費(fèi)的時(shí)間反而最多的算法？．對(duì)已知序列找出前5個(gè)最小的元素用什么算法？.做快速排序，請(qǐng)給出第i趟的結(jié)果及元素交換次數(shù)?.做Shell排序，步長(zhǎng)已知，請(qǐng)給出第i趟結(jié)果?

第一章一

(3)inti=1,j=1;

while(i2->3->1->4->6->5

而B(niǎo)FS的程序?qū)崿F(xiàn)一般是采用隊(duì)列，即對(duì)當(dāng)前訪問(wèn)的節(jié)點(diǎn)，將鄰接節(jié)點(diǎn)進(jìn)行先進(jìn)

先出，進(jìn)的序列也應(yīng)當(dāng)為該節(jié)點(diǎn)的鄰接鏈表的序列。

BFS序列的唯一結(jié)果為:

0->2->5->6->1->3->4

三．拓?fù)渑判颉?/p>

此題同學(xué)的錯(cuò)誤也均為不細(xì)致，題目中描述各頂點(diǎn)的鄰接表均從小至大排列，因此當(dāng)訪問(wèn)某節(jié)點(diǎn)時(shí)，入隊(duì)和入棧的順序均為從小到大。

對(duì)于以棧實(shí)現(xiàn)的，拓?fù)淞鞒倘缦拢?/p>

當(dāng)前訪問(wèn)節(jié)點(diǎn)0070780781078140781490781495078149560781495620781495623

對(duì)于以隊(duì)列實(shí)現(xiàn)，拓?fù)淞鞒倘缦?

當(dāng)前訪問(wèn)節(jié)點(diǎn)0010170172017240172480172485017248590172485930172485936

棧(棧底->棧頂)17

18124259252623(隊(duì)首->隊(duì)尾)

17

72248488559936366隊(duì)列（一）

1．（1）n^3(2)(n(n+1)(n+2))/6(3)

?3?1?8n?1?1?8n?m?，其中m為整數(shù)

22[?1?1?8n][x]表示不超過(guò)x的最大整數(shù)

2?2(100?n)]步，1?n?14?n[n(n?1)（4）??n步，n?15?2．2n?1?o(2n)成立，22n?o(2n)不成立

23．（1）o(nlogn)（2）o(N)

(二)1．刪除：

StatusListDelete_L(LinkListj=1;

while(P++j;}

if(!P||j>i)

returnERROR;//刪除位置不合理q=P->next;e=q->data;

P->next=q->