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

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

2、第7章圖的各種存儲結(jié)構(gòu)(0分)；圖的兩種搜索路徑的遍歷（深度和廣度）(0分)；最小生成樹(0分)；拓?fù)渑判?0分)；關(guān)鍵路徑(0分)；最短路徑(0分)第9章順序表和有序表的查找(0分)；二叉排序樹的構(gòu)造和查找(0分)；哈希表的構(gòu)造方法(0分)第10章各種排序方法的執(zhí)行過程和其依據(jù)的原則(0分)；各種排序方法時間復(fù)雜度的分析(0分)備注一、單項選擇（每題2分，共 20 分）1、分析下面程序段的時間復(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)于串的的敘述中，哪一個是不正確的： （ ）A、串是字符的有限序列 B、空串是由空格構(gòu)成的串C、模式匹配是串的一種重要運算 D、串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類 （ ）A動態(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、若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運算，則利用（ ）存儲方式最節(jié)省時間。A順序表 B雙鏈表 C帶頭結(jié)點的雙循環(huán)鏈表 D單循環(huán)鏈表5、有六個元素6，5，4，3，2，1 的順序進(jìn)棧，問下列哪一個不是合法的出棧序列？ （ ）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)隊列，隊尾指針是rear，隊頭是front，則隊滿的條件是 （ ） A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front7、在一個長度為n的順序表中刪除第i個元素，需向前移動（ ）個元素。A. n B.i-1 C.n-i D.n-i+18、對一顆具有n個節(jié)點的樹，其中所有度之和等于（ ）。A. n B.n-1 C.n-2 D.n+19、某二叉樹的前序和后序序列正好相反，則該二叉樹一定是： ( )A、

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

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

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

8、，使得上述正文的編碼最短。3、畫出該邏輯結(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) 若從頂點V1出發(fā)對該圖進(jìn)行遍歷，分別給出本圖的按深度優(yōu)先搜索和按廣度優(yōu)先搜索的頂點序列；(3) 給出拓?fù)渑判蛐蛄?。5、給出如下圖深度優(yōu)先和廣度優(yōu)先遍歷序列。6、應(yīng)用普里姆算法和克魯斯卡爾算法求圖的最小生成樹。（具體步驟） (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ù)渑判蛐蛄?；?）從頂點A到頂點I的關(guān)鍵路徑。要求：給出具體計算過程，即列出所有事件的最早和最晚開始時間，所有活動的最早和最晚開始時間。8、給出a到其他頂點的單源最短路徑，根據(jù)dijkstra算法給出計算步驟。 9、已知有序順序表的元素分別為：10,15,20,25,30,35,40,45,50,55,60（1）使用順序查找時查找成功情況下的平均查找長度為多少？（2）使用折半查找方法，畫出二分查找樹。10、輸入一個正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），（1）畫出按元素排列順序輸入生成的一棵二叉排序樹。（2）請寫出遞歸算法，從小到大輸出該二叉排序樹的所有結(jié)點。11、設(shè)散列函數(shù)為H(K)=K %11,解決沖突的方法分別為（1）線性探測法和（2）鏈地址法，試將下列關(guān)鍵字集合35,67,42,21,29,86,95,47依次插入到散列表中（畫出散列表的示意圖），散列表長度為1