1、數(shù)據(jù)結(jié)構(gòu)練習(xí)題(一)一選擇題：1 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除它的第i數(shù)據(jù)元素之前，需要先依次向前移動(dòng)_個(gè)數(shù)據(jù)元素。(A) A.n-i B.n+i C.n-i-1 D.n-i+12. 在單鏈表中，已知q指的結(jié)點(diǎn)是p指的結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若在q和p指的結(jié)點(diǎn)之間插入一個(gè)由s指的結(jié)點(diǎn)，則需執(zhí)行_。(B)A. q->next=p; s->next=pB. s->next=p; q->next=s;C. p->next=s; s->next=q;D. s->next=q; q->next=p;3. 某堆棧的輸入序列為a,b,c,d,下面的四個(gè)

2、序列中，_不可能是它的輸出序列。(C) A.a,c,b,d B.b,c,d,a C.d,c,a,b D.c,d,b,a4. 在一棵樹中，_沒(méi)有前驅(qū)結(jié)點(diǎn)。(C) A. 分支結(jié)點(diǎn) B. 葉結(jié)點(diǎn) C. 樹根結(jié)點(diǎn) D. 空結(jié)點(diǎn)5. 一棵深度為8（根的層次號(hào)為1）的滿二叉樹共有_個(gè)結(jié)點(diǎn)。(B)A.256B.255C.128D.1276. 下面二叉樹的中序遍歷序列為_。(A) A.DBEAFC B.DEBFCA C.BDEACF D.ABCDEF7. 連通圖G有n個(gè)頂點(diǎn),圖的生成樹有_條邊。(B)A.nB.n-1C.n(n-1)/2D.(n+1)/28. 在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的_。(C)A.

3、入度B. 出度C. 入度與出度之和D. 入度與出度之差9. 設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，采用鄰接表作為其存儲(chǔ)表示，在進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為_。（B）AO（nlog2e） BO（n+e）CO(ne) DO(n2)10. 一個(gè)對(duì)象序列的排序碼為46，79，56，38，40，84，采用快速排序以位于最左位置的對(duì)象為基準(zhǔn)而得到的第一次劃分結(jié)果為_。（C）A38，46，79，56，40，84 B38，79，56，46，40，84C40，38，46，56，79，84D38，46，56，79，40，84二填空題：1. 已知具有n個(gè)元素的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素的地

4、址為L(zhǎng)OC(a1)，那么，LOC(ai)=_LOC(a1)+(i-1)*k_。2. 若一棵二叉樹有10個(gè)葉結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)的點(diǎn)個(gè)數(shù)為_9_。3. 具有n個(gè)結(jié)點(diǎn)的非空二叉排序樹的最小深度為_。4. 廣義表（a,b,c,d）的表尾是_d_。5. 一個(gè)不帶有權(quán)的無(wú)向圖采用鄰接矩陣存儲(chǔ)方法，其鄰接是一個(gè)_矩陣。6. 二維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個(gè)數(shù)組元素最多有_個(gè)直接前驅(qū)（或直接后繼）。7. 鏈表對(duì)于數(shù)據(jù)元素的插入和刪除不需移動(dòng)結(jié)點(diǎn)，只需改變相關(guān)結(jié)點(diǎn)的_域的值。8. 在一個(gè)鏈?zhǔn)綏Ｖ校魲ｍ斨羔樀扔贜ULL則為_。9. 由樹轉(zhuǎn)化成二叉樹，其根的右孩子指針_。10. 設(shè)帶權(quán)有向圖G的鄰

5、接矩陣為A，若圖中不存在弧<vi,vj>,則Ai,j的值為_。三判斷題：1. 數(shù)組是一種沒(méi)有插入與刪除操作的線性結(jié)構(gòu)。( )2. 稀疏矩陣中值為0的元素分布有規(guī)律，因此可以采用三元組方法進(jìn)行壓縮存儲(chǔ)。( )3. 空串與由空格組成的串沒(méi)有區(qū)別。( )4. 完全二叉樹就是滿二叉樹。( )5. 有向圖是一種非線性結(jié)構(gòu)。( )6. 帶權(quán)連通圖的最小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之和。( )7. AOE 網(wǎng)是一種帶權(quán)的無(wú)環(huán)連通圖。( )8. 一個(gè)廣義表的表尾總是一個(gè)廣義表。( )9. 存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。( )10.

6、對(duì)于有n個(gè)對(duì)象的待排序序列進(jìn)行歸并排序，所需平均時(shí)間為O（nlog2n）。( )數(shù)據(jù)結(jié)構(gòu)練習(xí)題(二)一選擇題：1  在一個(gè)長(zhǎng)度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長(zhǎng)度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為_ 。 ( ) A n B n/2 C (n+1)/2 D (n-1)/22. 下面關(guān)于圖的存儲(chǔ)的敘述中，哪一個(gè)是正確的。 （ ） A用鄰接矩陣法存儲(chǔ)圖,占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān),而與邊數(shù)無(wú)關(guān) B用鄰接矩陣法存儲(chǔ)圖,占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān),而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān) C用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，

7、而與邊數(shù)無(wú)關(guān)D用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)3 棧的插入和刪除操作在_進(jìn)行。（ ）A 棧頂 B 棧底 C 任意位置 D 指定位置4 由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為_。（ ）A 24 B 73 C 48 D 535 若在線性表中采用折半查找法查找元素，該線性表應(yīng)該_。(    ) A元素按值有序    B采用順序存儲(chǔ)結(jié)構(gòu)    C元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)    D元素按值有序，且采用鏈

8、式存儲(chǔ)結(jié)構(gòu)6 對(duì)二叉排序樹進(jìn)行_遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的排序序列。(    )     A. 前序    B中序    C后序    D按層次7 具有n個(gè)頂點(diǎn)的有向圖最多有_條邊。(    ) An    Bn(n-1)    C. n(n+1)    D. 2n8.線性表是_。( ) A.一個(gè)以上的元素構(gòu)成的序列。

9、B.一個(gè)以上的元素構(gòu)成的集合。C.任意個(gè)有限元素構(gòu)成的集合。D.任意個(gè)有限元素構(gòu)成的序列。9 串的下列存儲(chǔ)結(jié)構(gòu)中，最節(jié)省空間的是_。( ) A.緊縮格式的順序存儲(chǔ)方式。B.非緊縮格式的順序存儲(chǔ)方式。C.結(jié)點(diǎn)大小為1的鏈?zhǔn)酱鎯?chǔ)方式。D.自定義結(jié)點(diǎn)大小的鏈?zhǔn)酱鎯?chǔ)方式。10若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左右子樹的位置，利用(   )遍歷方法最合適。A前序    B中序    C后序    D按層次二填空題：1稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即三元組和_。2主程序第一次調(diào)

10、用遞歸函數(shù)被稱為外部調(diào)用，遞歸函數(shù)自己調(diào)用自己被稱為內(nèi)部調(diào)用，它們都需要利用棧保存調(diào)用后的_地址。3在一棵樹中，_結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)。4廣義表（a,b,c,d）的表尾是_。5在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有_個(gè)元素。6在一棵二叉樹中有n0個(gè)葉結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，則n0= _。7在以Head為表頭指針的帶表頭結(jié)點(diǎn)的單鏈表中，判斷鏈表為空的條件為_。8n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有_個(gè)非零元素。9數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_和非線性結(jié)構(gòu)兩種。10. 抽象數(shù)據(jù)類型的最重要的特點(diǎn)是_和信息隱蔽。三判斷題：1 由樹轉(zhuǎn)化成二叉樹，其根的右孩子指針域?yàn)榭铡? )2 完全二叉樹可以是滿二

11、叉樹。( )3 有向圖不是一種非線性結(jié)構(gòu)。( )4 非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。( )5 深度為h的非空二叉樹的第i層最多有2 h-1 個(gè)結(jié)點(diǎn)。( )6 給定AOE網(wǎng)的關(guān)鍵路徑是唯一的。( )7 鏈?zhǔn)酱鎯?chǔ)在插入和刪除時(shí)需要保持物理存儲(chǔ)空間的順序分配，不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序。( )8 一個(gè)廣義表的表頭總是一個(gè)廣義表。( )9 數(shù)據(jù)的基本單位是數(shù)據(jù)項(xiàng)。( )10. 棧和隊(duì)列都是運(yùn)算受限的線性結(jié)構(gòu)。( )數(shù)據(jù)結(jié)構(gòu)練習(xí)題(三)一選擇題：1 采用順序查找方法查找長(zhǎng)度為n的線性表，不成功時(shí)平均查找長(zhǎng)度為。( ) A.n+1B.n/2 C.(n+1)/2D.(

12、n-1)/22. 具有65個(gè)結(jié)點(diǎn)的完全二叉樹的高度為。（）A8 B7 C6 D53. 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ ）倍。A3 B2 C1 D1/24. 線性鏈表不具有的特點(diǎn)是（ ）。A隨機(jī)訪問(wèn) B不必事先估計(jì)所需存儲(chǔ)空間大小C插入與刪除時(shí)不必移動(dòng)元素 D所需空間與線性表長(zhǎng)度成正比5. 向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（ ）。A先移動(dòng)棧頂指針，再存入元素 B先存入元素，再移動(dòng)棧頂指針C先后次序無(wú)關(guān)緊要 D同時(shí)進(jìn)行6. 在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加_。（ ） A. 2 B. 1 C. 0 D. 17. 具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)該有_條邊才能確保是一個(gè)

13、連通圖。（ ）A.8 B. 7 C. 6 D. 58. 從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（ ） 排序法。A插入    B選擇    C希爾    D二路歸并9按逐點(diǎn)插入法建立對(duì)應(yīng)于序列(54，28，16，34，73，62，95，60，26，43)的二叉排序樹后，查找62要進(jìn)行_次比較。（ ）A6次 B5次 C3次 D2次10下圖中哪一個(gè)是大根堆。（ ） A1，2，3B8，9，5C3，5，7D6，4，1二填空題：1. 廣大義表A

14、=(),(a),(b,(c,d)的長(zhǎng)度為_。2. 能夠順利完成的AOV網(wǎng)必定是一個(gè)_。3. 具有n個(gè)結(jié)點(diǎn)的非空二叉排序樹的最小深度為_。4. 對(duì)于給定的有向圖，只需了解從任意一點(diǎn)到其它各點(diǎn)是否存在著一條路徑，這是圖的_問(wèn)題。5. 將二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，那么指向結(jié)點(diǎn)的直接前驅(qū)和直接后繼結(jié)點(diǎn)的指針，稱為_。6. 用具有n個(gè)元素的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的_。7. 將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用_。8. 一棵高度為5的二叉樹中最少含有_個(gè)結(jié)點(diǎn)。 9. 由權(quán)值分別為13，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為_。10. 廣

15、義表（a）,a）的表頭是_。三判斷題：10 算法的五個(gè)重要特性為：有窮性、確定性、可行性、輸入、輸出。（ ）11 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n。（ ）12 線性表的順序存儲(chǔ)結(jié)構(gòu)是通過(guò)數(shù)據(jù)元素的存儲(chǔ)地址直接反映數(shù)據(jù)元素的邏輯關(guān)系。( ) 13 用一組地址連續(xù)的存儲(chǔ)單元存放的元素一定構(gòu)成線性表。( ) 14 若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算。（ ）15 對(duì)于具有n個(gè)頂點(diǎn)的有向圖，其弧數(shù)最多可達(dá)n (n-1)條，具有最大弧數(shù)的有向圖稱為完全有向圖。（ ）16 廣度優(yōu)先搜索是從一個(gè)給定的頂點(diǎn)出發(fā)，沿著一條路徑搜索尚未訪問(wèn)的頂

16、點(diǎn)，當(dāng)不能繼續(xù)找到新的未被訪問(wèn)的頂點(diǎn)時(shí)，再沿原路向回退，選取另外一條路徑進(jìn)行搜索。( ) 17 一個(gè)廣義表的表頭可以是一個(gè)廣義表。( )18 棧和隊(duì)列插入和刪除操作都在表的同一端進(jìn)行。( ) 19 直接選擇排序是一種穩(wěn)定的排序方法。( ) 數(shù)據(jù)結(jié)構(gòu)練習(xí)題（四）1. 數(shù)據(jù)結(jié)構(gòu)是一門研究_的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。2. 算法的5個(gè)重要特性：_、_、_、輸入和輸出。3. 長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在第i個(gè)元素之前插入一個(gè)元素時(shí)，需要將_個(gè)數(shù)據(jù)元素依次向后移動(dòng)一個(gè)位置。4. 在單鏈表中，已知q指的結(jié)點(diǎn)是p指的結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若在q和p指的結(jié)點(diǎn)之間插入

17、一個(gè)由s指的結(jié)點(diǎn)，則需執(zhí)行_。5. 設(shè)有一空棧，現(xiàn)有輸入序列A、B、C、D、E，經(jīng)過(guò)push、push、pop、push、pop、push、push 、pop、pop、pop后，得到的輸出序列是_。6. 遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為_的數(shù)據(jù)結(jié)構(gòu)。7. 在進(jìn)行圖的廣度優(yōu)先搜索過(guò)程需要用到一種稱為_的數(shù)據(jù)結(jié)構(gòu)。8. 在數(shù)組表示的循環(huán)隊(duì)列中，front、rear分別為隊(duì)列的頭、尾指針，MAXSIZE為數(shù)組的最大長(zhǎng)度，隊(duì)空的條件是_，隊(duì)滿的條件是_。9. 已知一棵完全二叉樹中共有80個(gè)結(jié)點(diǎn)，則該二叉樹中共有 _個(gè)葉子結(jié)點(diǎn)。10. 一棵深度為10 ( 根的層次號(hào)為1

18、) 的完全二叉樹最少有_個(gè)結(jié)點(diǎn)。11. 具有68個(gè)結(jié)點(diǎn)的完全二叉樹的高度為_。12. 設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非葉子結(jié)點(diǎn)，B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有_個(gè)。13. 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_倍。14. 設(shè)有電文“ABAADACC”,字符集為A、B、C、D，對(duì)其進(jìn)行哈夫曼編碼，則上述電文總長(zhǎng)_位。15. 在一棵樹中， _沒(méi)有后繼結(jié)點(diǎn)，_沒(méi)有前驅(qū)結(jié)點(diǎn)。16. 具有n個(gè)結(jié)點(diǎn)的無(wú)向圖的生成樹，有_條邊。17. 對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須_。 18. 假定查找有序表A1.10中每個(gè)元素的概率相等，則進(jìn)行折半查找時(shí)的平均查找長(zhǎng)度為_。19. 在所

19、有學(xué)習(xí)的排序算法中，其中_是不穩(wěn)定的排序方法。20. 當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為_。21. 數(shù)據(jù)元素之間的關(guān)系通常有4類基本結(jié)構(gòu)：_、_、_、_。22. 帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空的判定條件是_。23. 在順序存儲(chǔ)結(jié)構(gòu)的線性表中插入或刪除一個(gè)數(shù)據(jù)元素，若表長(zhǎng)為n，則相應(yīng)算法的時(shí)間復(fù)雜度為_。24. 若一棵二叉樹具有12個(gè)度為2的結(jié)點(diǎn)，8個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是_。25. 廣義表L1=( ( a , b ) , ( c ) , d)，那么GetHead(GetTail(GetTail (L) _。26. 廣大義表A=( ( a ) , ( b , c

20、 ) , ( d ) , ( e , f )的長(zhǎng)度為_ 。27. 由五個(gè)分別帶權(quán)值為 6，8，3，5，7 的葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，則該樹的帶權(quán)路徑長(zhǎng)度為 _。28. 一個(gè)有n個(gè)頂點(diǎn)的圖，最少有_個(gè)連通分量，最多有_個(gè)連通分量。29. n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有_個(gè)非零元素。30. 設(shè)帶權(quán)有向圖G的鄰接矩陣為A，若圖中不存在弧<vi,vj>，Aij的值為_。31. 圖G有n個(gè)頂點(diǎn)和e條邊，以鄰接表形式存儲(chǔ)，進(jìn)行深度優(yōu)先搜索的時(shí)間復(fù)雜度為 _，進(jìn)行廣度優(yōu)先搜索的時(shí)間復(fù)雜度為 _。32. 關(guān)鍵路徑是AOE網(wǎng)中從源點(diǎn)到匯點(diǎn)的_路徑。33. 設(shè)有100個(gè)數(shù)據(jù)元素，采用折半查找時(shí)，最大比較次數(shù)為_。34. _遍歷一棵二叉排序樹所得的結(jié)點(diǎn)訪問(wèn)序列是按關(guān)鍵值的遞增序列。35. 孩子-右兄弟表示法將樹轉(zhuǎn)換成對(duì)應(yīng)的二叉樹，則該二叉樹中樹根結(jié)點(diǎn)肯定沒(méi)有_孩子。36. 在一棵AVL樹（高度平衡的二叉搜索樹）中，每個(gè)結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對(duì)值不超過(guò)_。37. 順序查找如果忽略查找不成功的情況，則在等概率前提下，查找成功時(shí)的平均查找長(zhǎng)度為_。38. 哪些排序方法的時(shí)間復(fù)雜度為nlog2n。39. 索引順序查找又稱_，這是順序查找的一種改進(jìn)方法。40. 有一關(guān)鍵字序列( 22 , 89 , 21