數(shù)據(jù)結(jié)構(c語言版)期末考試復習試題

1、 二、填空題。數(shù)據(jù)邏輯結(jié)構包括線性結(jié)構、樹形結(jié)構和圖狀結(jié)構三種類型,樹形結(jié)構和圖狀結(jié)構合稱非線性結(jié)構。數(shù)據(jù)的邏輯結(jié)構分為集合、線性結(jié)構、樹形結(jié)構和圖狀結(jié)構4種。在線性結(jié)構中，第一個結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。線性結(jié)構中元素之間存在一對一關系,樹形結(jié)構中元素之間存在一對多關系，圖形結(jié)構中元素之間存在多對多關系。在樹形結(jié)構中，樹根結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；葉子結(jié)點沒有后續(xù)結(jié)點,其余每個結(jié)點的后續(xù)結(jié)點可以任意多個。數(shù)據(jù)結(jié)構的基本存儲方法是順序、鏈式、索引和散列存儲。衡量一個算法的優(yōu)劣主要考慮

2、正確性、可讀性、健壯性和時間復雜度與空間復雜度。評估一個算法的優(yōu)劣，通常從時間復雜度和空間復雜度兩個方面考察。算法的5個重要特性是有窮性、確定性、可行性、輸入和輸出。在一個長度為n的順序表中刪除第i個元素時，需向前移動n-i-1個元素。11.在單鏈表中，要刪除某一指定的結(jié)點，必須找到該結(jié)點的衛(wèi)結(jié)點。在雙鏈表中，每個結(jié)點有兩個指針域，一個指向前驅(qū)結(jié)點,另一個指向后繼結(jié)點。在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動n個數(shù)據(jù)元素,移動數(shù)據(jù)元素的個數(shù)與位置有關。當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應采用順序存儲結(jié)構。15根據(jù)線性表的鏈式存儲結(jié)

3、構中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成和雙鏈表。順序存儲結(jié)構是通過下標表示元素之間的關系的；鏈式存儲結(jié)構是通過指針表示元素之間的關系的。帶頭結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是L-next-next=L。棧是限定僅在表尾進彳丁插入或刪除操作的線性表，其運算遵循后進先出的原則?？沾橇銈€字符的串,其長度等于蘭。空白串是由一個或多個空格字符組成的串，其長度等于其包含的空格個數(shù)。組成串的數(shù)據(jù)元素只能是單個字符。一個字符串中任意個連續(xù)字符構成的部分稱為該串的子串。子串”str”在主串”datastructure”中的位置是5。二維數(shù)組M的每個元素是6個字符組成的串，丁下標i的范圍從0到8，

4、列下標j的范圍從1到10,則存放M至少需要540個字節(jié);M的第8列和第5行共占108個字節(jié)。稀疏矩陣一般的壓縮存儲方法有兩種，即三元組表和十字鏈表。廣義表(a),(b),c),(d)的長度是3，深度是4。在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0,度為2的結(jié)點的個數(shù)為n2,則有n0=n2+1。在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為_n+1一棵有n個葉子結(jié)點的哈夫曼樹共有_2n-1_個結(jié)點。深度為5的二叉樹至多有31個結(jié)點。若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點個數(shù)為69。某二叉樹的前序遍歷序列是abdgcefh，中序序列是dgbaechf，其后序序列為gdbe

5、hfca。線索二叉樹的左線索指向其,右線索指向其遍歷序列中的后繼。在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關的查找方法是散列查找法。在分塊索引查找方法中，首先查找索引表，然后查找相應的塊表。一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。36.具有10個頂點的無向圖，邊的總數(shù)最多為_45已知圖G的鄰接表如圖所示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為_vlv2v3v6v5v4_，其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為_vlv2v5v4v3v6_。索引是為了加快檢索速度而引進的一種數(shù)據(jù)結(jié)構。一個索引隸屬于某個數(shù)據(jù)記錄集，它由若干索引項組成，索引

6、項的結(jié)構為關鍵字和關鍵字對應記錄的地址。Prim算法生成一個最小生成樹每一步選擇都要滿足邊的總數(shù)不超過n-1,當前選擇的邊的權值是候選邊中最小的，選中的邊加入樹中不產(chǎn)生回路三項原則。在一棵m階B樹中，除根結(jié)點外，每個結(jié)點最多有m棵子樹，最少有m/2棵子樹。三、判斷題。在決定選取何種存儲結(jié)構時，一般不考慮各結(jié)點的值如何。（V）抽象數(shù)據(jù)類型（ADT）包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現(xiàn)。（V）抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關。（V）順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（X）線性表采用鏈式存儲結(jié)構時，結(jié)

7、點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（X）對任何數(shù)據(jù)結(jié)構鏈式存儲結(jié)構一定優(yōu)于順序存儲結(jié)構。（X）順序存儲方式只能用于存儲線性結(jié)構。（X）集合與線性表的區(qū)別在于是否按關鍵字排序。（X）線性表中每個元素都有一個直接前驅(qū)和一個直接后繼。（X）線性表就是順序存儲的表。（X）11.取線性表的第i個元素的時間同i的大小有關。(X)12循環(huán)鏈表不是線性表。(X)13鏈表是采用鏈式存儲結(jié)構的線性表，進行插入、刪除操作時，在鏈表中比在順序表中效率高。(V)雙向鏈表可隨機訪問任一結(jié)點。(X)在單鏈表中，給定任一結(jié)點的地址p,則可用下述語句將新結(jié)點s插入結(jié)點p的后面：p-next=s;s-next=p-next;

8、(X)隊列是一種插入和刪除操作分別在表的兩端進行的線性表,是一種先進后出的結(jié)構。(X)串是一種特殊的線性表,其特殊性體現(xiàn)在可以順序存儲。(X)長度為1的串等價于一個字符型常量。(X)空串和空白串是相同的。(X)數(shù)組元素的下標值越大,存取時間越長。(X)用鄰接矩陣法存儲一個圖時,在不考慮壓縮存儲的情況下,所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關,而與圖的邊數(shù)無關。(V)一個廣義表的表頭總是一個廣義表。(X)一個廣義表的表尾總是一個廣義表。(V)廣義表(a),b),c)的表頭是(a),b),表尾是(c)。(V)二叉樹的后序遍歷序列中,任意一個結(jié)點均處在其孩子結(jié)點的后面。(V)度為2的有序樹是二叉樹

9、。(X)二叉樹的前序遍歷序列中,任意一個結(jié)點均處在其孩子結(jié)點的前面。(V)用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點。(X)若已知一棵二叉樹的前序遍歷序列和后序遍歷序列,則可以恢復該二叉樹。(X)在哈夫曼樹中，權值最小的結(jié)點離根結(jié)點最近。(X)強連通圖的各頂點間均可達。（V）32對于任意一個圖，從它的某個結(jié)點進行一次深度或廣度優(yōu)先遍歷可以訪問到該圖的每個頂點。（X）33在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，稱這種排序為穩(wěn)定排序。（V）34在平衡二叉樹中，任意結(jié)點左右子樹的高度差（絕對值）不超過1。（V）35拓撲排序是按AOE網(wǎng)中每個結(jié)點事件的最早發(fā)生時間對結(jié)點進行排序。（X）36冒泡排序算法關鍵字比較的次數(shù)與記錄的初始排列次序無關。（X）37對線性表進行折半查找時，要求線性表必須以鏈式方式存儲，且結(jié)點按關鍵字有序排列