2013數(shù)據(jù)結(jié)構(gòu)語言版復(fù)習(xí)

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機 操作對 以及它們之間 關(guān)數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R，其中D是 的有限集合，R是D上的 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié) 、數(shù)據(jù) 結(jié) 非線性結(jié) 沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點 后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū) 數(shù)據(jù)的結(jié)構(gòu)可用四種基本的方法表示，它們分別是順序、鏈式、索引和散列5插入、刪除、修改、查找、排序 時 效率 空 在順序表中插入或刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數(shù)與表長和該元 線性表中結(jié)點的集合是有 一對 的向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動n- 個元素向一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動n- 在順序表中任意一結(jié)點的時間復(fù)雜度均為 因此順序表也稱為隨機存 順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定在單鏈表中，除了首元結(jié)點外，任一結(jié)點的位置由其直接前驅(qū)結(jié)點的鏈域的 在O（n 不包含任何字（長度為0）的串 子串的定位運算稱為串的模式匹配；被匹配的主 子 稱為模式假設(shè)有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)，器按字節(jié)編址。已知A的起始置（址）為1000，則數(shù)組A的體積（量）為288B；末尾元素A57的第一個字節(jié)地址為1282；若按行時，元素A14的第一個字節(jié)地址為(8+4)×6=1072；若按列時，元素A47的第一個字節(jié)地址為(6×7＋4)×6＋1000）＝1276。由３個結(jié)點所構(gòu)成的二叉樹有5種形態(tài)。6的滿二叉樹有n1+n2=0+n2n0-1=31個分支結(jié)點和26-1=32個葉子。1一棵具有２５７個結(jié)點的完全二叉樹，它的深度為9。（注：用log2(n)+1=8.xx設(shè)一棵完全二叉樹有700個結(jié)點，則共有 設(shè)一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有 個葉子結(jié)點， 個度為的結(jié)點， 答：最快方法：用葉子數(shù)＝[n/2]＝500，n2=n0-1=499。另外，最后一結(jié)點為2i屬于左葉子，右葉子 線性有序表（a1，a2，a3a256)是從小到大排列的，對一個給定的值k，用二分法檢索表中與相等的元素，在查找不成功的情況下，最多需要檢 次。設(shè)有100個結(jié)點，用二分法查找時最大比較次數(shù) 次（25ASLn1log2(n1來計算（即（21×log221）/20＝4.6次并不正確。因為這是在假設(shè)n＝2m-n全部元素的查找次數(shù)為＝（1＋2×2＋4×3＋8×4＋5×5）＝74； （4612202838507088100表中元 在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法 關(guān)鍵字的 二、判斷正誤（在正確的說法后面打勾，反之打叉（× ）1（ （× ）3.鏈表的刪除算法很簡單，因為當(dāng)刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向（× ）4錯，了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)（× ）5（ ）6.順序方式的優(yōu)點是密度大，且插入、刪除運算效率高在表長為n（ ）7.線性表在物理空間中也一定是連續(xù)的錯，線性表有兩種方式，順序和鏈式。后者不要求連續(xù)存放（ ）8.線性表在順序時，邏輯上相鄰的元素未必在的物理位置次序上相鄰錯誤。線性表有兩種方式，在順序時，邏輯上相鄰的元素在的物理位置次序上也相鄰（ ）9.順序方式只能用于線性結(jié)構(gòu)（ ）10.線性表的邏輯順序與順序總是一致的錯，理由同7。鏈式就無需一致（× ）11錯，線性表是邏輯結(jié)構(gòu)概念，可以順序或鏈式，與元素數(shù)據(jù)類型無關(guān)（× ）12錯，不一定吧？調(diào)用子程序或函數(shù)常用，CPU（√ ）13（√ ）14（× ）15錯，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是結(jié)構(gòu)概念，二者不是同類項（× ）16（ ）17.棧和隊列的方式既可是順序方式，也可是方式（√ ）18.兩個棧共片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應(yīng)把兩個棧的棧底（× ）19（× ）2012345，12345（√）21nn—1（×）22.二叉樹中每個結(jié)點的兩棵的高度差等于1（√）23.二叉樹中每個結(jié)點的兩棵是有序的（×）24.二叉樹中每個結(jié)點有兩棵非空或有兩棵空（×）25.二叉樹中每個結(jié)點的關(guān)鍵字值大于其空（若存在的話）所有結(jié)點的關(guān)鍵字值，且小于 （×）262k-1-1，k（2i-（×）27.二叉樹中所有結(jié)點，如果不存在非空左，則不存在非空右（×）28.對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i—1（（√）29.用二叉鏈表法（link-rlink）包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個（√）301252 ）1.非線性結(jié)構(gòu)是數(shù)據(jù)元間存在一種 ）2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù) 結(jié)構(gòu)A)B)物 C)邏 D)物理 ）3.算法分析的目的是：A)找出數(shù)據(jù)結(jié)構(gòu)的合理 B)研究算法中的輸入和輸出的關(guān)C)分析算法的效率以求改 D)分析算法的易懂性和 ）4A)空間復(fù)雜性和時間復(fù)雜 B)正確性和簡明C)可讀性和文D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜 ）5.計算機算法指的是：A)計算方 B)排序方 C)解決問題的有限運算序 D)調(diào)度方 ）6.計算機算法必須具備輸入、輸出 等5個特性A)可行性、可移植性和可擴充 B)可行性、確定性和有窮C)確定性、有窮性和穩(wěn)定 D)易讀性、穩(wěn)定性和安全（ （A）結(jié) （C）順序結(jié) ）8.一個向量第一個元素的地址是100，每個元素的長度為2，則第5個元素的地址 ）9.在nO（1）（A）第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤i（1≤i≤i（1≤i≤n ）10.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 （A(C）只有一部分，表示結(jié)點間關(guān)系的指（D） ）12.鏈表是一種采 結(jié)構(gòu)的線性表 ）13.線性表若采用鏈式結(jié)構(gòu)時，要求內(nèi)存中可用單元的地址（A）必須是連續(xù) （C）一定是不連續(xù) ）14．線性表Ｌ （Ａ）需經(jīng)常修改Ｌ中的結(jié)點 （Ｃ）Ｌ中的結(jié) ）161，2，3，…，np1，p2，p3，…，pnp1=n，pi ）17.判定一個棧ST（m0）Ａ．ST- Ｂ．ST- Ｃ．ST- C）18.在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù) 倍 ）19.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和 倍 ）20.有8個結(jié)點的無向圖最多 條邊