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

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