數(shù)據(jù)結(jié)構(gòu) 總結(jié)

1、命題說(shuō)明章節(jié)考核的重點(diǎn)及命題說(shuō)明第1章各種基本概念和術(shù)語(yǔ)(0分)；掌握算法描述和分析的方法(0分)第2章線性表的邏輯結(jié)構(gòu)和各種存儲(chǔ)表示方法(0分)；以及定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算及其在存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)這些基本運(yùn)算(0分)第3章棧和隊(duì)列的特點(diǎn)(0分)；棧在兩種存儲(chǔ)結(jié)構(gòu)表示時(shí)的基本操作實(shí)現(xiàn)算法(0分)；循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法(0分)第6章二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)(0分)；二叉樹(shù)各種遍歷策略的遞歸和非遞歸算法(0分)；已知先序序列和中序序列或中序序列和后序序列建立二叉樹(shù)的方法(0分)；二叉樹(shù)的線索化過(guò)程；(0分)樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及特點(diǎn)；(0分)建立最優(yōu)樹(shù)和哈夫曼編碼的方法(0分)

2、第7章圖的各種存儲(chǔ)結(jié)構(gòu)(0分)；圖的兩種搜索路徑的遍歷（深度和廣度）(0分)；最小生成樹(shù)(0分)；拓?fù)渑判?0分)；關(guān)鍵路徑(0分)；最短路徑(0分)第9章順序表和有序表的查找(0分)；二叉排序樹(shù)的構(gòu)造和查找(0分)；哈希表的構(gòu)造方法(0分)第10章各種排序方法的執(zhí)行過(guò)程和其依據(jù)的原則(0分)；各種排序方法時(shí)間復(fù)雜度的分析(0分)備注一、單項(xiàng)選擇（每題2分，共 20 分）1、分析下面程序段的時(shí)間復(fù)雜度： ( )i=1;j=1;while(i<=n) i=i*3;while(j<=n) j+;A、O(n+log3n) B、O(n) C、O(log3n) D、O(n*log3n)2、下

3、面關(guān)于串的的敘述中，哪一個(gè)是不正確的： （ ）A、串是字符的有限序列 B、空串是由空格構(gòu)成的串C、模式匹配是串的一種重要運(yùn)算 D、串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)3、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi) （ ）A動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)4、若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表5、有六個(gè)元素6，5，4，3，2，1 的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？ （ ）A. 5 4 3 6 1 2 B. 4

4、5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 66、最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)滿(mǎn)的條件是 （ ） A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front7、在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素，需向前移動(dòng)（ ）個(gè)元素。A. n B.i-1 C.n-i D.n-i+18、對(duì)一顆具有n個(gè)節(jié)點(diǎn)的樹(shù)，其中所有度之和等于（ ）。A. n B.n-1 C.n-2 D.n+19、某二叉樹(shù)的前序和后序序列正好相反，則該二叉樹(shù)一定是： ( )A、

5、高度等于其結(jié)點(diǎn)數(shù) B、任意一個(gè)二叉樹(shù) C、所有節(jié)點(diǎn)均無(wú)左孩子 D、所有節(jié)點(diǎn)均無(wú)右孩子10、已知一棵完全二叉樹(shù)的第6層（根節(jié)點(diǎn)為第一層）有8個(gè)葉子節(jié)點(diǎn)，則完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)至多是： A、39 B、52 C、111 D、119 ( )11、以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)。 A樹(shù) B字符串 C隊(duì) D棧12、設(shè)棧N和隊(duì)列M初始狀態(tài)為空，元素1,2,3,4,5,6依次通過(guò)棧N，一個(gè)元素出棧后進(jìn)隊(duì)列M，若6個(gè)元素出隊(duì)的序列是2,4,3,6,5,1,則棧N的容量至少應(yīng)該是： ( )A、2 B、3 C、4 D、513、一棵完全二叉樹(shù)上有100個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是 （ ）A 50 B 51 C

6、52 D49 14、有關(guān)二叉樹(shù)下列說(shuō)法正確的是 （ ）A二叉樹(shù)的度為2 B一棵二叉樹(shù)的度可以小于2 C二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2 D二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為215、一棵二叉樹(shù)的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是 （ ）ACABDEFG BABCDEFG CDACEFBG DADCFEG二、填空題（每題2分，共 20 分）1、設(shè)一行優(yōu)先順序存儲(chǔ)的數(shù)組A55，A00的地址為1000，且每個(gè)元素占2個(gè)存儲(chǔ)單元，則A23的地址為 。2、設(shè)循環(huán)隊(duì)列用數(shù)組AM表示，隊(duì)首、隊(duì)尾指針?lè)謩e是front和rear，則循環(huán)隊(duì)列的元素個(gè)數(shù)為 。3、假定一棵二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為200，則它的深度

7、最少為 。4、線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_。5、帶頭結(jié)點(diǎn)的循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是：_ _三、簡(jiǎn)答題（每題5分，共1 0分）1、什么是數(shù)據(jù)的邏輯結(jié)構(gòu)？數(shù)據(jù)的邏輯結(jié)構(gòu)主要有哪幾種基本的類(lèi)型？2、線性表有哪幾種存儲(chǔ)結(jié)構(gòu)？分別有哪些優(yōu)點(diǎn)？四、綜合應(yīng)用題（每題5分，共2 0分）1、已知一棵二叉樹(shù)的先序遍歷為ABECDFGHIJ，中序遍歷為EBCDAFHIGJ。（1）給出后序遍歷序列，（2）將該二叉樹(shù)轉(zhuǎn)換為森林。2、設(shè)有正文AADBAACACCDACACAADBB,字符集為A,B,C,D,設(shè)計(jì)一套二進(jìn)制編碼

8、，使得上述正文的編碼最短。3、畫(huà)出該邏輯結(jié)構(gòu)的結(jié)構(gòu)圖。S=D,R, D=a,b,c,d,e,f,g, R=<a,b>,<b,d>,<c,d>,<e,f>,<f,g>,<c,f>,<d,g>4、已知圖如下： (1) 給出該圖的鄰接矩陣和鄰接表； (2) 若從頂點(diǎn)V1出發(fā)對(duì)該圖進(jìn)行遍歷，分別給出本圖的按深度優(yōu)先搜索和按廣度優(yōu)先搜索的頂點(diǎn)序列；(3) 給出拓?fù)渑判蛐蛄?。5、給出如下圖深度優(yōu)先和廣度優(yōu)先遍歷序列。6、應(yīng)用普里姆算法和克魯斯卡爾算法求圖的最小生成樹(shù)。（具體步驟） (v0,v4),(v0,v1),(v1,

9、v2),(v1,v3),(v1,v5)(v0,v4),(v1,v2),(v1,v3),(v1,v5),(v0,v1)7、下圖為帶權(quán)有向圖，求： （1）給出拓?fù)渑判蛐蛄?；?）從頂點(diǎn)A到頂點(diǎn)I的關(guān)鍵路徑。要求：給出具體計(jì)算過(guò)程，即列出所有事件的最早和最晚開(kāi)始時(shí)間，所有活動(dòng)的最早和最晚開(kāi)始時(shí)間。8、給出a到其他頂點(diǎn)的單源最短路徑，根據(jù)dijkstra算法給出計(jì)算步驟。 9、已知有序順序表的元素分別為：10,15,20,25,30,35,40,45,50,55,60（1）使用順序查找時(shí)查找成功情況下的平均查找長(zhǎng)度為多少？（2）使用折半查找方法，畫(huà)出二分查找樹(shù)。10、輸入一個(gè)正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），（1）畫(huà)出按元素排列順序輸入生成的一棵二叉排序樹(shù)。（2）請(qǐng)寫(xiě)出遞歸算法，從小到大輸出該二叉排序樹(shù)的所有結(jié)點(diǎn)。11、設(shè)散列函數(shù)為H(K)=K %11,解決沖突的方法分別為（1）線性探測(cè)法和（2）鏈地址法，試將下列關(guān)鍵字集合35,67,42,21,29,86,95,47依次插入到散列表中（畫(huà)出散列表的示意圖），散列表長(zhǎng)度為1