數(shù)據(jù)結(jié)構(gòu)總結(jié)_第1頁
數(shù)據(jù)結(jié)構(gòu)總結(jié)_第2頁
數(shù)據(jù)結(jié)構(gòu)總結(jié)_第3頁
數(shù)據(jù)結(jié)構(gòu)總結(jié)_第4頁
數(shù)據(jù)結(jié)構(gòu)總結(jié)_第5頁
已閱讀5頁,還剩2頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、、命題說明 章節(jié)'x考核的重點及命題說明第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)樹和哈

2、夫曼編碼的方法(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分);各種排序方法時間復雜度的分析(0分)備注一、單項選擇(每題2分,共20分)1、分析下面程序段的時間復雜度: ( )i=1;j=1;while(i<=n)while(j<=n)A、O(n+log 3n)O(n *log 3n)i=i*3; j+;B、0(n)C、O(l

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

4、下列哪一個不是合法的出棧 )B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 36、(7、8、最大容量為n的循環(huán)隊列,隊尾指針是rear,隊頭是front,則隊滿的條件是 )A. (rea葉1) MOD n=fro ntB. rear=fro ntC. rea葉仁fro ntD. (rear-l) MOD n=fro nt在一個長度為n的順序表中刪除第i個元素,需向前移動()個元素。A. nB.i-1C.n-i對一顆具有n個節(jié)點的樹,其中所有度之和等于(A. nB. n-1C.n-2某二叉樹的前序和后序序列正好相反,)D.n-i+1)。D.n+1則該二叉樹一定是:A、高度等于其

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

6、棵二叉樹的前序遍歷序列為(D.)A . CABDEFGADCFEGC、4個結(jié)點,其中葉子結(jié)點的個數(shù)是49列說法正確的是B .一棵二叉樹的度可以小于 2D .二叉樹中任何一個結(jié)點的度都ABCDEFG,它的中序遍歷序列可能是B. ABCDEFGC. DACEFBG填空題(每題2分,共20分)設(shè)一行優(yōu)先順序存儲的數(shù)組 A55,A00的地址為1、個存儲單元,則A23的地址為2、設(shè)循環(huán)隊列用數(shù)組AM表示,隊首、隊尾指針分別是隊列的元素個數(shù)為3、假定一棵二叉樹的結(jié)點個數(shù)為 200,則它的深度最少為。4、線性表L= (a1,a2,an用數(shù)組表示,假定刪除表中任一元素的概率相同,則刪除一個元素平均需要移動元素

7、的個數(shù)是 。帶頭結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是: 5、1000,且每個元素占2front和rear,則循環(huán)簡答題(每題5分,共1 0分)1、2、什么是數(shù)據(jù)的邏輯結(jié)構(gòu)?數(shù)據(jù)的邏輯結(jié)構(gòu)主要有哪幾種基本的類型?線性表有哪幾種存儲結(jié)構(gòu)?分別有哪些優(yōu)點?四、綜合應用題(每題5分,共2 0分)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,

8、D=a,b,c,d,e,f,g, R=va,b>vb,d><c,d><e,f>,vf,g><c,f>,vd,g> 4、已知圖如下:(1) 給出該圖的鄰接矩陣和鄰接表;(2) 若從頂點V1出發(fā)對該圖進行遍歷,分別給出本圖的按深度優(yōu)先搜索和按廣度優(yōu)先搜索的頂點序列;(3)給出拓撲排序序列 ©5、給出如下圖深度優(yōu)先和廣度優(yōu)先遍歷序列。15126應用普里姆算法和克魯斯卡爾算法求圖的最小生成樹。(具體步驟)31対5(v0,v4),(v0,v1),(v1,v2),(v1,v3),(v1,v5)(v0,v4),(v1,v2),(v1,v3

9、),(v1,v5),(v0,v1)7、下圖為帶權(quán)有向圖,求:(1)給出拓撲排序序列;(2)從頂點A到頂點I的關(guān)鍵路徑。要求:給出具體計算過程,即列出所有事 件的最早和最晚開始時間,所有活動的最早和最晚開始時間。8、給出a到其他頂點的單源最短路徑,根據(jù)dijkstra算法給出計算步驟。a5 /y3廠79、 已知有序順序表的元素分別為: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依次插入到散列表中(畫出散列表的示意圖),散列表長度為11。畫出兩種沖突解

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論