數據結構(C語言版)知識點復習資料數據結構(C語言版)知識點復習資料數據結構(C語言版)知識點復習資料xxx公司數據結構(C語言版)知識點復習資料文件編號：文件日期：修訂次數：第1.0次更改批準審核制定方案設計，管理制度數據結構復習資料一、填空題1.數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和運算等的學科。2.數據結構被形式地定義為（D,R），其中D是數據元素的有限集合，R是D上的關系有限集合。3.數據結構包括數據的邏輯結構、數據的存儲結構和數據的運算這三個方面的內容。4.數據結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構。5.線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。6．在線性結構中，第一個結點沒有前驅結點，其余每個結點有且只有1個前驅結點；最后一個結點沒有后續結點，其余每個結點有且只有1個后續結點。7.在樹形結構中，樹根結點沒有前驅結點，其余每個結點有且只有1個前驅結點；葉子結點沒有后續結點，其余每個結點的后續結點數可以任意多個。8.在圖形結構中，每個結點的前驅結點數和后續結點數可以任意多個。9．數據的存儲結構可用四種基本的存儲方法表示，它們分別是順序、鏈式、索引和散列。10.數據的運算最常用的有5種，它們分別是插入、刪除、修改、查找、排序。11.一個算法的效率可分為時間效率和空間效率。12.在順序表中插入或刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數與表長和該元素在表中的位置有關。13.線性表中結點的集合是有限的，結點間的關系是一對一的。14.向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動n-i+1個元素。15.向一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動n-i個元素。16.在順序表中訪問任意一結點的時間復雜度均為O(1)，因此，順序表也稱為隨機存取的數據結構。17.順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。18．在單鏈表中，除了首元結點外，任一結點的存儲位置由其直接前驅結點的鏈域的值指示。19．在n個結點的單鏈表中要刪除已知結點*p，需找到它的前驅結點的地址，其時間復雜度為O（n）。20.向量、棧和隊列都是線性結構，可以在向量的任何位置插入和刪除元素；對于棧只能在棧頂插入和刪除元素；對于隊列只能在隊尾插入和隊首刪除元素。21.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂。不允許插入和刪除運算的一端稱為棧底。22.隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。23.不包含任何字符（長度為0）的串稱為空串；由一個或多個空格（僅由空格符）組成的串稱為空白串。24.子串的定位運算稱為串的模式匹配；被匹配的主串稱為目標串，子串稱為模式。25.假設有二維數組A6×8，每個元素用相鄰的6個字節存儲，存儲器按字節編址。已知A的起始存儲位置（基地址）為1000，則數組A的體積（存儲量）為288B；末尾元素A57的第一個字節地址為1282；若按行存儲時，元素A14的第一個字節地址為(8+4)×6+1000=1072；若按列存儲時，元素A47的第一個字節地址為(6×7＋4)×6＋1000）＝1276。26．由３個結點所構成的二叉樹有5種形態。27.一棵深度為6的滿二叉樹有n1+n2=0+n2=n0-1=31個分支結點和26-1=32個葉子。注：滿二叉樹沒有度為1的結點，所以分支結點數就是二度結點數。28．一棵具有２５７個結點的完全二叉樹，它的深度為9。注：用[log2(n)]+1=[]+1=929．設一棵完全二叉樹有700個結點，則共有350個葉子結點。答：最快方法：用葉子數＝[n/2]＝35030．設一棵完全二叉樹具有1000個結點，則此完全二叉樹有500個葉子結點，有499個度為2的結點，有1個結點只有非空左子樹，有0個結點只有非空右子樹。答：最快方法：用葉子數＝[n/2]＝500，n2=n0-1=499。另外，最后一結點為2i屬于左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數＝0.31．在數據的存放無規律而言的線性表中進行檢索的最佳方法是順序查找（線性查找）。32.線性有序表（a1，a2，a3，…，a256)是從小到大排列的，對一個給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索8次。設有100個結點，用二分法查找時，最大比較次數是7。33.假設在有序線性表a[20]上進行折半查找，則比較一次查找成功的結點數為1；比較兩次查找成功的結點數為2；比較四次查找成功的結點數為8；平均查找長度為。解：顯然，平均查找長度＝O（log2n）<5次（25）。但具體是多少次，則不應當按照公式來計算（即（21×log221）/20＝次并不正確！）。因為這是在假設n＝2m-1的情況下推導出來的公式。應當用窮舉法羅列：全部元素的查找次數為＝（1＋2×2＋4×3＋8×4＋5×5）＝74；ASL＝74/20=?。?！34．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素28，6，12，20比較大小。35.在各種查找方法中，平均查找長度與結點個數n無關的查找方法是散列查找。36.散列法存儲的基本思想是由關鍵字的值決定數據的存儲地址。二、判斷正誤（在正確的說法后面打勾，反之打叉）（×）1.鏈表的每個結點中都恰好包含一個指針。答：錯誤。鏈表中的結點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結點的指針。（×）2.鏈表的物理存儲結構具有同鏈表一樣的順序。錯，鏈表的存儲結構特點是無序，而鏈表的示意圖有序。（×）3.鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續的各個單元向前移動。錯，鏈表的結點不會移動，只是指針內容改變。（×）4.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。錯，混淆了邏輯結構與物理結構，鏈表也是線性表！且即使是順序表，也能存放記錄型數據。（×）5.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜”（×）6.順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優點。順序存儲方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除一個數據元素，平均需移動表長一半個數的數據元素。（×）7.線性表在物理存儲空間中也一定是連續的。錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。后者不要求連續存放。（×）8.線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。（×）9.順序存儲方式只能用于存儲線性結構。錯誤。順序存儲方式不僅能用于存儲線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬于非線性結構，但其最佳存儲方式是順序存儲方式。（后一節介紹）（×）10.線性表的邏輯順序與存儲順序總是一致的。錯，理由同7。鏈式存儲就無需一致。（×）11.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。錯，線性表是邏輯結構概念，可以順序存儲或鏈式存儲，與元素數據類型無關。（×）12.在表結構中最常用的是線性表，棧和隊列不太常用。錯，不一定吧調用子程序或函數常用，CPU中也用隊列。（√）13.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。（√）14.對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。正確，都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（×）15.棧和鏈表是兩種不同的數據結構。錯，棧是邏輯結構的概念，是特殊殊線性表，而鏈表是存儲結構概念，二者不是同類項。（×）16.棧和隊列是一種非線性數據結構。錯，他們都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（√）17.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。（√）18.兩個棧共享一片連續內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。（×）19.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。錯，后半句不對。（×）20.一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。錯，有可能。（√）21.若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n—1個非空指針域。（×）22.二叉樹中每個結點的兩棵子樹的高度差等于1。（√）23.二叉樹中每個結點的兩棵子樹是有序的。（×）24.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。（×）25.二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。（應當是二叉排序樹的特點）（×）26.二叉樹中所有結點個數是2k-1-1，其中k是樹的深度。（應2i-1）（×）27.二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。（×）28.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2i—1個結點。（應2i-1）（√）29.用二叉鏈表法（link-rlink）存儲包含n個結點的二叉樹，結點的2n個指針區域中有n+1個為空指針。（√）30.具有12個結點的完全二叉樹有5個度為2的結點。三、單項選擇題1.非線性結構是數據元素之間存在一種：A）一對多關系B）多對多關系C）多對一關系D）一對一關系2.數據結構中，與所使用的計算機無關的是數據的結構；A)存儲B)物理C)邏輯D)物理和存儲3.算法分析的目的是：A)找出數據結構的合理性B)研究算法中的輸入和輸出的關系C)分析算法的效率以求改進D)分析算法的易懂性和文檔性4.算法分析的兩個主要方面是：A)空間復雜性和時間復雜性B)正確性和簡明性C)可讀性和文檔性D)數據復雜性和程序復雜性5.計算機算法指的是：A)計算方法B)排序方法C)解決問題的有限運算序列D)調度方法6.計算機算法必須具備輸入、輸出和等5個特性。A)可行性、可移植性和可擴充性B)可行性、確定性和有窮性C)確定性、有窮性和穩定性D)易讀性、穩定性和安全性7．數據在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續的，稱之為：（A）存儲結構（B）邏輯結構（C）順序存儲結構（D）鏈式存儲結構8.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（A）110（B）108（C）100（D）1209.在n個結點的順序表中，算法的時間復雜度是O（1）的操作是：訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n）在第i個結點后插入一個新結點（1≤i≤n）刪除第i個結點（1≤i≤n）將n個結點從小到大排序10.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動個元素（A）8（B）（C）63（D）711.鏈接存儲的存儲結構所占存儲空間：分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針只有一部分，存放結點值(C）只有一部分，存儲表示結點間關系的指針（D）分兩部分，一部分存放結點值，另一部分存放結點所占單元數12.鏈表是一種采用存儲結構存儲的線性表；（A）順序（B）鏈式（C）星式（D）網狀13.線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址:（A）必須是連續的（B）部分地址必須是連續的（C）一定是不連續的（D）連續或不連續都可以14．線性表Ｌ在情況下適用于使用鏈式結構實現。（Ａ）需經常修改Ｌ中的結點值（Ｂ）需不斷對Ｌ進行刪除插入（Ｃ）Ｌ中含有大量的結點（Ｄ）Ｌ中結點結構復雜15.棧中元素的進出原則是Ａ．先進先出Ｂ．后進先出Ｃ．?？談t進Ｄ．棧滿則出16.若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不確定17.判定一個棧ST（最多元素為m0）為空的條件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m018.在一個圖中，所有頂點的度數之和等于圖的邊數的倍。A．1/2