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

1、一、單項(xiàng)選擇題： 1、樹形結(jié)構(gòu)不具備這樣的特點(diǎn)：（ ）A. 每個(gè)節(jié)點(diǎn)可能有多個(gè)后繼（子節(jié)點(diǎn)）B. 每個(gè)節(jié)點(diǎn)可能有多個(gè)前驅(qū)（父節(jié)點(diǎn)）C. 可能有多個(gè)內(nèi)節(jié)點(diǎn)（非終端結(jié)點(diǎn)）D. 可能有多個(gè)葉子節(jié)點(diǎn)（終端節(jié)點(diǎn)）2、二叉樹與度數(shù)為2的樹相同之處包括（ ）。A. 每個(gè)節(jié)點(diǎn)都有1個(gè)或2個(gè)子節(jié)點(diǎn) B. 至少有一個(gè)根節(jié)點(diǎn)C. 至少有一個(gè)度數(shù)為2的節(jié)點(diǎn) D. 每個(gè)節(jié)點(diǎn)至多只有一個(gè)父節(jié)點(diǎn)3、一棵完全二叉樹有999 個(gè)結(jié)點(diǎn)，它的深度為（ ）。 A9 B10 C11 D12 4、在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(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、對(duì)于一棵具有n個(gè)結(jié)點(diǎn)、度為5的樹來說，（ ）A. 樹的高度至多是n-3 B. 樹的高度至多是n-4C. 樹的高度至多是n D. 樹的高度至多是n-56、在順序隊(duì)列中，元素的排列順序（ ）。A. 由元素插入隊(duì)列的先后順序決定B. 與元素值的大小有關(guān)C. 與隊(duì)首指針和隊(duì)尾指針的取值有關(guān)D. 與數(shù)組大小有關(guān)7、串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。 A可以順序存儲(chǔ) B數(shù)據(jù)元素是一個(gè)字符 C可以鏈?zhǔn)酱?/p>

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

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

5、D歸并排序16、以下屬于邏輯結(jié)構(gòu)的是（ ）A. 順序表 B. 哈希表 C. 有序表 D. 單鏈表 17、一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有（ ）條邊。A. n B. n(n-1) C. n(n-1)/2 D. 2n18、下面（ ）算法適合構(gòu)造一個(gè)稠密圖G的最小生成樹。A Prim算法 BKruskal算法 CFloyd算法 DDijkstra算法19、下面哪個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)（ ）。 A順序表 B鏈表 C散列表 D隊(duì)列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），對(duì)該圖進(jìn)行深度優(yōu)先

6、遍歷，得到的頂點(diǎn)序列正確的是（ ）。 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、如下圖所示帶權(quán)無向圖的最小生成樹的權(quán)為（ ）。 A14 B15 C17 D1822、以下排序方法中，不穩(wěn)定的排序方法是（ ）。 A直接選擇排序 B二分法插入排序 C歸并排序 D基數(shù)排序 23、下列哪一個(gè)選項(xiàng)不是下圖所示有向圖的拓?fù)渑判蚪Y(jié)果（ ）。 AAFBCDE BFABCDE CFACBDE DFADBCE24、參加排序的記錄可以具有相同的關(guān)鍵碼。當(dāng)一個(gè)排序方法在排序過程中不改變這種相同關(guān)鍵碼記錄的原始輸入順序時(shí)，稱之為穩(wěn)定的；反之稱為不穩(wěn)定的。

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

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

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

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

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

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

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

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

15、4）這棵二叉樹的深度為多少？ （5）試對(duì)該二叉樹進(jìn)行前（中、后）序線索化； 3、 如右圖所示的是個(gè)無向圖的鄰接表，試： （1）畫出此圖； （2）從頂點(diǎn)A 開始的DFS 遍歷結(jié)果； （3）從頂點(diǎn)A 開始的BFS 遍歷結(jié)果。 4、分析下列語(yǔ)句執(zhí)行次數(shù)，并給出它們的時(shí)間復(fù)雜度T(n)。 （1） i+; （2）for(i=0;i<n;i+) for(j=0;j<n;j+) printf(“%d”,i+j); 5、分析下列語(yǔ)句的執(zhí)行次數(shù)，并給出它們的時(shí)間復(fù)雜度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、分析下列語(yǔ)句的執(zhí)行次數(shù)，并給出它們的時(shí)間復(fù)雜度T(n)。 7第 頁(yè) 共 9 頁(yè)（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算法構(gòu)造其最小生成樹。 8、 分別畫出具有3個(gè)結(jié)點(diǎn)的樹和具有3個(gè)結(jié)

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

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