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

數(shù)據(jù)結(jié)構(gòu)總結(jié)數(shù)據(jù)結(jié)構(gòu)總結(jié)數(shù)據(jù)結(jié)構(gòu)總結(jié)數(shù)據(jù)結(jié)構(gòu)總結(jié)編制僅供參考審核批準生效日期地址：電話：傳真:郵編:命題說明章節(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分)第7章圖的各種存儲結(jié)構(gòu)(0分)；圖的兩種搜索路徑的遍歷（深度和廣度）(0分)；最小生成樹(0分)；拓撲排序(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、下面關(guān)于串的的敘述中，哪一個是不正確的：（）A、串是字符的有限序列 B、空串是由空格構(gòu)成的串C、模式匹配是串的一種重要運算 D、串既可以采用順序存儲，也可以采用鏈式存儲3、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類（）A．動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B．順序結(jié)構(gòu)、鏈式結(jié)構(gòu)C．線性結(jié)構(gòu)、非線性結(jié)構(gòu) D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)4、若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。A．順序表 B．雙鏈表 C．帶頭結(jié)點的雙循環(huán)鏈表D．單循環(huán)鏈表5、有六個元素6，5，4，3，2，1的順序進棧，問下列哪一個不是合法的出棧序列（）A.543612 B.453126 C.346521 D.2341566、最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊滿的條件是（）A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front7、在一個長度為n的順序表中刪除第i個元素，需向前移動（）個元素。A.n-1C+18、對一顆具有n個節(jié)點的樹，其中所有度之和等于（）。A.n-1C+19、某二叉樹的前序和后序序列正好相反，則該二叉樹一定是：() A、高度等于其結(jié)點數(shù)B、任意一個二叉樹C、所有節(jié)點均無左孩子D、所有節(jié)點均無右孩子10、已知一棵完全二叉樹的第6層（根節(jié)點為第一層）有8個葉子節(jié)點，則完全二叉樹的節(jié)點個數(shù)至多是：A、39B、52C、111D、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，一個元素出棧后進隊列M，若6個元素出隊的序列是2,4,3,6,5,1,則棧N的容量至少應(yīng)該是：() A、2B、3C、4D、513、一棵完全二叉樹上有100個結(jié)點，其中葉子結(jié)點的個數(shù)是（）A．50 B．51 C．52D．4914、有關(guān)二叉樹下列說法正確的是（） A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結(jié)點的度為2D．二叉樹中任何一個結(jié)點的度都為215、一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG二、填空題（每題2分，共20分）1、設(shè)一行優(yōu)先順序存儲的數(shù)組A[5][5]，A[0][0]的地址為1000，且每個元素占2個存儲單元，則A[2][3]的地址為。2、設(shè)循環(huán)隊列用數(shù)組A[M]表示，隊首、隊尾指針分別是front和rear，則循環(huán)隊列的元素個數(shù)為。3、假定一棵二叉樹的結(jié)點個數(shù)為200，則它的深度最少為。4、線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是________。5、帶頭結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是：________三、簡答題（每題5分，共10分）1、什么是數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)主要有哪幾種基本的類型2、線性表有哪幾種存儲結(jié)構(gòu)分別有哪些優(yōu)點四、綜合應(yīng)用題（每題5分，共20分）1、已知一棵二叉樹的先序遍歷為ABECDFGHIJ，中序遍歷為EBCDAFHIGJ。（1）給出后序遍歷序列，（2）將該二叉樹轉(zhuǎn)換為森林。2、設(shè)有正文AADBAACACCDACACAADBB,字符集為A,B,C,D,設(shè)計一套二進制編碼，使得上述正文的編碼最短。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ā)對該圖進行遍歷，分別給出本圖的按深度優(yōu)先搜索和按廣度優(yōu)先搜索的頂點序列；(3)給出拓撲排序序列。5、給出如下圖深度優(yōu)先和廣度優(yōu)先遍歷序列。。6、應(yīng)用普里姆算法和克魯斯卡爾算法求圖的最小生成樹。（具體步驟）(v0,v4),(v0,v1),(v1,v2),(v1,v3),(v1,v5) (v0,v4),(v1,v2),(v1,v3),(v1,v5),(v0,v1)7、下圖為帶權(quán)有向圖，求：（1）給出拓撲排序序列；（2）從頂點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)