數(shù)據(jù)結構(C語言版)復習題

1、一、單項選擇題： 1、樹形結構不具備這樣的特點：（ ）A. 每個節(jié)點可能有多個后繼（子節(jié)點）B. 每個節(jié)點可能有多個前驅（父節(jié)點）C. 可能有多個內(nèi)節(jié)點（非終端結點）D. 可能有多個葉子節(jié)點（終端節(jié)點）2、二叉樹與度數(shù)為2的樹相同之處包括（ ）。A. 每個節(jié)點都有1個或2個子節(jié)點 B. 至少有一個根節(jié)點C. 至少有一個度數(shù)為2的節(jié)點 D. 每個節(jié)點至多只有一個父節(jié)點3、一棵完全二叉樹有999 個結點，它的深度為（ ）。 A9 B10 C11 D12 4、在一個單鏈表中，若p所指結點不是最后結點，在p之后插入s所指結點，則執(zhí)行（ ） A. s->next=p;p->next=s; B

2、. s->next=p->next;p->next=s; C. s->next=p->next;p=s; D. p->next=s;s->next=p;5、對于一棵具有n個結點、度為5的樹來說，（ ）A. 樹的高度至多是n-3 B. 樹的高度至多是n-4C. 樹的高度至多是n D. 樹的高度至多是n-56、在順序隊列中，元素的排列順序（ ）。A. 由元素插入隊列的先后順序決定B. 與元素值的大小有關C. 與隊首指針和隊尾指針的取值有關D. 與數(shù)組大小有關7、串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。 A可以順序存儲 B數(shù)據(jù)元素是一個字符 C可以鏈式存

3、儲 D數(shù)據(jù)元素可以是多個字符若 8、順序循環(huán)隊列中（數(shù)組的大小為 6），隊頭指示 front 和隊尾指示 rear 的值分別為 3和 0，當從隊列中刪除1個元素，再插入2 個元素后，front和 rear的值分別為（ ）。 A5 和1 B2和4 C1和5 D4 和29、一棵完全二叉樹上有1001 個結點，其中葉子結點的個數(shù)為（ ）。 A250 B500 C254 D501 10、已知一個有向圖如下圖所示，則從頂點a出發(fā)進行深度優(yōu)先遍歷，不可能得到的DFS序列為（ ）。 Aadbefc Badcefb Cadcebf Dadefbc11、在一個帶權連通圖G 中，權值最小的邊一定包含在G 的（ ）

4、。 A最小生成樹中 B深度優(yōu)先生成樹中 C廣度優(yōu)先生成樹中 D深度優(yōu)先生成森林中 12、適用于折半查找的表的存儲方式及元素排列要求為（ ）。 A鏈式方式存儲，元素無序 B鏈式方式存儲，元素有序 C順序方式存儲，元素無序 D順序方式存儲，元素有序 13、含有27個關鍵字節(jié)點的平衡二叉樹（AVL樹）（ ）A. 有13個度數(shù)為2的節(jié)點 B. 最大高度為6C. 最低高度是6 D. 有14個度數(shù)為0的節(jié)點14、任何一個無向連通圖的最小生成樹（ ）。A. 有一棵或多棵 B. 只有一棵 C. 一定有多棵 D. 可能不存在15、下述幾種排序方法中,要求內(nèi)存量最大的是（ ）。A插入排序 B選擇排序 C快速排序

5、D歸并排序16、以下屬于邏輯結構的是（ ）A. 順序表 B. 哈希表 C. 有序表 D. 單鏈表 17、一個有n個頂點的無向圖最多有（ ）條邊。A. n B. n(n-1) C. n(n-1)/2 D. 2n18、下面（ ）算法適合構造一個稠密圖G的最小生成樹。A Prim算法 BKruskal算法 CFloyd算法 DDijkstra算法19、下面哪個術語與數(shù)據(jù)的存儲結構無關（ ）。 A順序表 B鏈表 C散列表 D隊列20、無向圖G=（V，E）， 其 中 ：V=a,b,c,d,e,f，E=（a,b），（a,e），（a,c），（b,e） ，（c,f），（f,d），（e,d），對該圖進行深度優(yōu)先

6、遍歷，得到的頂點序列正確的是（ ）。 Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b 21、如下圖所示帶權無向圖的最小生成樹的權為（ ）。 A14 B15 C17 D1822、以下排序方法中，不穩(wěn)定的排序方法是（ ）。 A直接選擇排序 B二分法插入排序 C歸并排序 D基數(shù)排序 23、下列哪一個選項不是下圖所示有向圖的拓撲排序結果（ ）。 AAFBCDE BFABCDE CFACBDE DFADBCE24、參加排序的記錄可以具有相同的關鍵碼。當一個排序方法在排序過程中不改變這種相同關鍵碼記錄的原始輸入順序時，稱之為穩(wěn)定的；反之稱為不穩(wěn)定的。

7、下面4種排序方法中，屬于不穩(wěn)定的排序方法是（ ）。A. 快速排序 B. 冒泡排序 C. 簡單選擇排序 D. 折半插入排序25、鏈式存儲設計時，結點內(nèi)的存儲單元地址（ ）A. 一定連續(xù) B. 一定不連續(xù)C. 不一定連續(xù) D. 部分連續(xù)，部分不連續(xù)26、若一個棧的進棧序列是1,2,3,n,其輸出序列是p1,p2,pn,若p1=n,則pi的值是（ ）。 A. i B. n-i C. n-i+1 D. 不確定27、以下有關二叉樹的說法正確的是（ ）。 A二叉樹的度為2 B一棵二叉樹的度可以小于2 C二叉樹中至少有一個結點的度為2 D二叉樹中任一個結點的度均為2 28、一棵具有5 層的滿二叉樹所包含的結

8、點個數(shù)為（ ）。 A15 B31 C63 D32 29、在關鍵字序列（12，23，34，45，56，67，78，89，91）中二分查找關鍵字為45、89 和 12的結點時，所需進行的比較次數(shù)分別為（ ）。 A4，4，3 B4，3，3 C3，4，4 D3，3，4 30、一個序列中有 10000 個元素，若只想得到其中前 10 個最小元素，最好采用（ ）方法。 A快速排序 B堆排序 C插入排序 D二路歸并排序31若將數(shù)據(jù)結構形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上（ ）A操作的有限集合 B映象的有限集合C類型的有限集合 D關系的有限集合32在頭指針為head且表長大于1的

9、單循環(huán)鏈表中，指針p指向表中某個結點，若p->next->next=head，則（ ）Ap指向頭結點 Bp指向尾結點C*P的直接后繼是尾結點 D *p的直接后繼是頭結點33在具有n個結點的有序單鏈表中插入一個新結點并使鏈表仍然有序的時間復雜度是（ ）AO(1) BO(n)CO(nlogn) DO(n2)34隊列和棧的主要區(qū)別是（ ）A邏輯結構不同 B存儲結構不同C所包含的運算個數(shù)不同 D限定插入和刪除的位置不同35若進棧序列為a,b,c，則通過入出棧操作可能得到的a,b,c的不同排列個數(shù)為（ ） A4 B5 C6 D736一棵含18個結點的二叉樹的高度至少為( )A3 B4 C5

10、D637在一個帶權連通圖G中，權值最小的邊一定包含在G的（）A最小生成樹中B深度優(yōu)先生成樹中C廣度優(yōu)先生成樹中D深度優(yōu)先生成森林中二、填空題： 1、 樹最適合用來表示具有（ ）性和（ ）性的數(shù)據(jù)。 2、設有一批數(shù)據(jù)元素,為了最快的存儲某元素,數(shù)據(jù)結構宜用（ ）結構,為了方便插入一個元素,數(shù)據(jù)結構宜用（ ）結構。3、在順序表的（ ）后面插入一個元素，不需要移動任何元素。4、設循環(huán)隊列的容量為40（ ），隊頭指針為front，隊尾指針為rear；現(xiàn)經(jīng)過一系列的入隊和出隊運算后，隊頭與隊尾指針分別指向front=11，rear=19，則可求出循環(huán)隊列中有（ ）個元素。5、哈夫曼樹是帶權路徑長度（ ）

11、的二叉樹，又稱最優(yōu)二叉樹。6、前序遍歷和中序遍歷結果相同的二叉樹為（ ）；前序遍歷和后序遍歷結果相同的二叉樹為（ ）。 7、在一個長度為n的順序表中刪除第i個元素（ ）時，需向前移動（ ）個元素。8、線性的數(shù)據(jù)結構包括：（ ）、（ ）、（ ）和數(shù)組、串。9、訪問單向鏈表的節(jié)點，必須順著（ ）依次進行。10、設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結構最佳。11、數(shù)據(jù)結構涉及三個方面的內(nèi)容，即( )、( )和( )。12、具有4個頂點的無向完全圖有( )條邊。三、判斷對錯題： 1、二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。 （ ）2、棧和鏈表是兩種相同的數(shù)據(jù)結構。（ ） 3、

12、在中序線索二叉樹中，每一非空的線索均指向其祖先結點。（ ）4、必須把一般樹轉換成二叉樹后才能進行存儲。（ ）5、健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（ ）6、循環(huán)鏈表不是線性表。（ ）7、一棵哈夫曼樹中不存在度為1的結點。（ ）8、線性表的邏輯順序與存儲順序總是一致的。 （ ）9、若有向圖中存在拓撲序列，則該圖不存在回路。（ ）10、有序表與數(shù)據(jù)的存儲結構無關（ ）11、單鏈表的存儲密度小于1。（ ）12、執(zhí)行廣度優(yōu)先遍歷圖時，需要使用隊列作為輔助存儲空間。（ ）13、把一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。（ ）14、在完全二叉樹中，葉子結點的雙親的左兄弟（如果存在

13、）一定不是葉子結點。（ ）15、數(shù)據(jù)的機內(nèi)表示稱為數(shù)據(jù)的存儲結構。（ ） 16、深度優(yōu)先遍歷類似于二叉樹的先序遍歷。（ ）17、某算法的時間復雜度為O（n2）,表明該算法的問題規(guī)模是n2。（ ）18、一個順序表所占用的存儲空間大小與元素的類型無關。（ ）19、消除遞歸一定要使用棧。（ ）20、一個有n個頂點和n條邊的無向圖一定是有環(huán)的。（ ）21、調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（ ）22、二叉樹是一般樹的特殊情形。( )23、數(shù)據(jù)的邏輯結構是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。( ) 24、歸并排序要求內(nèi)存量比較大。( )25、數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。( )

14、26、對任何數(shù)據(jù)結構鏈式存儲結構一定優(yōu)于順序存儲結構。( )27、拓撲排序是一種內(nèi)部排序的算法。 （ ） 28、棧和隊列的存儲方式只能是鏈接方式。（ ）29、棧是實現(xiàn)過程和函數(shù)等子程序所必需的結構。( )30、線性表在物理存儲空間中也不一定是連續(xù)的。( )四、綜合應用題：（共40分）1、兩個數(shù)據(jù)結構的邏輯結構和存儲結構都相同，但是它們的運算集合中有一個運算的定義不一樣，它們是否可以認作是同一個數(shù)據(jù)結構？為什么？ 2、 已知一棵二叉樹如右圖所示，試求：6第 頁 共 9 頁（1）該二叉樹前序、中序和后序遍歷的結果； （2）該二叉樹是否滿二叉樹？是否完全二叉樹？ （3）將它轉換成對應的樹或森林； （

15、4）這棵二叉樹的深度為多少？ （5）試對該二叉樹進行前（中、后）序線索化； 3、 如右圖所示的是個無向圖的鄰接表，試： （1）畫出此圖； （2）從頂點A 開始的DFS 遍歷結果； （3）從頂點A 開始的BFS 遍歷結果。 4、分析下列語句執(zhí)行次數(shù)，并給出它們的時間復雜度T(n)。 （1） i+; （2）for(i=0;i<n;i+) for(j=0;j<n;j+) printf(“%d”,i+j); 5、分析下列語句的執(zhí)行次數(shù)，并給出它們的時間復雜度T(n)。 （1） for(i=0;i<n;i+) if (ai<x) x=ai; （2）for (i=1;i<=n

16、-1;i+) k=i; for(j=i+1;j<=n;j+) if(aj>aj+1) k=j; t=ak; ak=ai; ai=t; 6、分析下列語句的執(zhí)行次數(shù)，并給出它們的時間復雜度T(n)。 7第 頁 共 9 頁（1）for(i=0;i<n;i+) for(j=0;j<n;j+) +x;s=s+x; （2）、for(i=0;i<=2;i+) for(j=0;j<=2;j+) for(s=0;s<=2;s+) t=ais*bsj;cij=cij+t; 7、如右圖所示的連通圖，用Prim算法構造其最小生成樹。 8、 分別畫出具有3個結點的樹和具有3個結

17、點的二叉樹的所有不同形態(tài)。 8第 頁 共 9 頁9、對于如下圖所示的無向圖，試給出：（1）圖中每個頂點的度； （2）該圖的鄰接矩陣； （3）該圖的鄰接表； 10、 如右圖所示的連通圖，用Kruskal，算法構造其最小生成樹。 11、試寫出如右圖所示的AOV 網(wǎng)的 4個不同的拓撲序列。12、 算法有哪些特點？它和程序的主要區(qū)別是什么？13、 若一棵二叉樹的左、右子樹均有3個結點，其左子樹的前序序列與中序序列相同，右子樹的中序序列與后序序列相同，試畫出該二叉樹。 14、 試述樹和二叉樹的主要區(qū)別。 15、 已知一棵二叉樹的中序遍歷的結果為 ABCEFGHD，后序遍歷的結果為ABFHGEDC，試畫出

18、此二叉樹。 16、設有正文AADBAACACCDACACAAD,字符集為A,B,C,D,設計一套二進制編碼，使得上述正文的編碼最短。 17、試回答下列關于圖的一些問題。 （1）有 n個頂點的有向強連通圖最多有多少條邊？最少有多少條邊？ （2）表示一個有500 個頂點，500 條邊的有向圖的鄰接矩陣有多少個非零元素？ （3）G是一個非連通的無向圖，共有28條邊，則該圖至少有多少個頂點？18、請畫出初始序列（212，26，172，126，8，56，23，2，6）的初始堆形，判斷其是否是堆，如果不是請將其調(diào)整成堆（寫出調(diào)整的過程）。19、假設用迪杰斯特拉(Dijkstra)算法求下列圖中從頂點a到其余各頂點的最短路徑，按求解過程依次寫出各條最短路徑及其長度。20、 給出初始待排序碼27，46，5，18，16，51，32，26使用下面各種排序算法的狀態(tài)變化示意圖：（1）直接插入排序；（2）直接選擇排序；（3）冒泡排序；（4）快速排序；（5）堆（大?。┡判颍?9第 頁 共 9 頁五、算法設計題：1、設計一個算法，求順序表中值為x的結點的個數(shù)。2