數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)復(fù)習(xí)資料全

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料一、填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系 和運(yùn)算等的學(xué)科。2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D, R )，其中D是 數(shù)據(jù)元素的有限集合,R是D上的關(guān)系有限集合。3. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算 這三個(gè)方面的容。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu) 和非線性結(jié)構(gòu)。5. 線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多 關(guān)系。6. 在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒有后續(xù)結(jié)點(diǎn)，其余

2、每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。7. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。8. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè) 。9 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序、鏈?zhǔn)?、索引和散?。10. 數(shù)據(jù)的運(yùn)算最常用的有 5種，它們分別是 插入、刪除、修改、 查找、排序。11. 一個(gè)算法的效率可分為時(shí)間 效率和 空間 效率。12. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與表長(zhǎng)和該元素在表中的位置 有關(guān)。13. 線性表中結(jié)點(diǎn)的集合是有限

3、的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一 的。14. 向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素(1 i n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)n-i+1個(gè)元素。15. 向一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素(1 i n)時(shí)，需向前移動(dòng)n-i個(gè)元素。16. 在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為0(1)，因此，順序表也稱為隨機(jī)存取 的數(shù)據(jù)結(jié)構(gòu)。17. 順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置_不一定相鄰。18在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指示。19. 在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的 前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為 0(n

4、)。20. 向量、棧和隊(duì)列都是線性 結(jié)構(gòu)，可以在向量的 任何位置插入和刪除元素；對(duì)于棧只能在_棧頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾 插入和_隊(duì)首刪除元素。21. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂。不允許插入和刪除運(yùn)算的一端稱為棧底。22. 隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。23. 不包含任何字符（長(zhǎng)度為0）的串稱為空串；由一個(gè)或多個(gè)空格（僅由空格符）組成的串稱為空白串。24. 子串的定位運(yùn)算稱為串的模式匹配；被匹配的主串稱為目標(biāo)串， 子串稱為模式。25假設(shè)有二維數(shù)組A6x8,每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知

5、A的起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A的體積（存儲(chǔ)量）為 288 B ；末尾元素 A的第一個(gè)字節(jié)地址為1282;若按行存儲(chǔ)時(shí)，元素 Ai4的第一個(gè)字節(jié)地址為（8+4） X 6+1000=1072;若按列存儲(chǔ)時(shí)，元素陽(yáng)的第一個(gè)字節(jié)地址為（6 X 7+ 4） X 6+ 1000 ）= 1276_。26. 由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有5種形態(tài)。27. 一棵深度為6的滿二叉樹有 n1+ n2=0+ n2= n0-仁31個(gè)分支結(jié)點(diǎn)和2 6-1 =32 個(gè)葉子。注：滿二叉樹沒有度為 1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。28. 一棵具有2 5 7個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為9。注：用Iog2（n

6、）+仁8.xx+1=929. 設(shè)一棵完全二叉樹有 700個(gè)結(jié)點(diǎn)，則共有 350個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)=n/2 = 35030. 設(shè)一棵完全二叉樹具有 1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有500 個(gè)葉子結(jié)點(diǎn)，有 499 個(gè)度為2的結(jié)點(diǎn)，有1個(gè)結(jié)點(diǎn)只有非空左子樹，有0個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)=n/2 = 500 , n2=n0-仁499。另外，最后一結(jié)點(diǎn)為 2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左子樹。完全二叉樹的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹數(shù)=0.31 在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是順序查找（線性查找） 。32. 線性有

7、序表（a1, a2, a3,，a256）是從小到大排列的，對(duì)一個(gè)給定的值 k，用二分法檢索表中與 k相等的元素，在查找不成功的情況下，最多需要檢索 8 次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是 7。33. 假設(shè)在有序線性表 a20上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1 ;比較兩次查找成功的結(jié)點(diǎn)數(shù)為2;比較四次查找成功的結(jié)點(diǎn)數(shù)為8;平均查找長(zhǎng)度為3.7。解：顯然，平均查找長(zhǎng)度=O（log2n ） top0B. ST-top=0C. ST-topm0棧滿則出,pn,若 p1= n,貝pi 為D. ST-top=m0在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的.1/2B. 1C.

8、 2倍。D. 4在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的.1/2B. 1C. 2D. 4倍。有8個(gè)結(jié)點(diǎn)的無向圖最多有條邊。14B. 28C. 56D. 11221. 有8個(gè)結(jié)點(diǎn)的有向完全圖有 條邊。A. 14 B. 28C. 56D. 11222. 在表長(zhǎng)為n的鏈表中進(jìn)行線性查找，它的平均查找長(zhǎng)度為A. ASL=n ;B .ASL=(n+l)/2;C . ASL= . n + l ; D . ASLlog 2(n+l)l23. 折半查找有序表(4, 6, 10, 12, 20, 30,50 , 70, 88, 100 )。若查找表中元素 58,則它將依次與表中 比較大小，查找結(jié)果是失敗。A. 20, 70, 30, 50 B . 30, 88