數(shù)據(jù)結(jié)構(gòu)導論練習題

1、一、選擇題1.在一個單鏈表HL中，若要在指針q所指結(jié)點的后面插入一個由指針p所指向的結(jié)點，則執(zhí)行。 Aq一）nextp一）next；p一）nextq； Bp一）nextq一）next；qp； Cq一）nextp一）next；p一）nextq； Dp一）nextq一）next； q一）nextp；2. 在一個順序隊列中，隊首指針指向隊首元素的位置：A前一個 B后一個 C當前3. 下列數(shù)據(jù)組織形式中，（      ）的結(jié)點按邏輯關系依次排列形成一個“鎖鏈”。A.集合       

2、  B.樹形結(jié)構(gòu) C.線性結(jié)構(gòu)     D.圖狀結(jié)構(gòu)4. 數(shù)據(jù)結(jié)構(gòu)可以形式化地定義為（S，），其中S指某種邏輯結(jié)構(gòu)，是指（      ）A.S上的算法      B.S的存儲結(jié)構(gòu) C.在S上的一個基本運算集   D.在S上的所有數(shù)據(jù)元素5. 下列說法正確的是（      ）A.線性表的邏輯順序與存儲順序總是一致的B.線性表的鏈式存儲結(jié)構(gòu)中，要求內(nèi)存

3、中可用的存儲單元可以是連續(xù)的，也可以不連續(xù)C.線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)D.每種數(shù)據(jù)結(jié)構(gòu)都具有插入、刪除和查找三種基本運算6. 設非空單鏈表的數(shù)據(jù)域為data，指針域為next，指針p指向單鏈表中第i個結(jié)點，s指向已生成的新結(jié)點，現(xiàn)將s結(jié)點插入到單鏈表中，使其成為第i個結(jié)點，下列算法段能正確完成上述要求的是（      ）A.s->next=p->next;p->next=s； B.p->next=s;s->next=p->next；C.s->next=p->next;p->nex

4、t=s;交換p->data和s->data； D.p=s;s->next=p；7. 將一棵有50個結(jié)點的完全二叉樹按層編號，則對編號為25的結(jié)點x，該結(jié)點（      ）A.無左、右孩子  B.有左孩子，無右孩子 C.有右孩子，無左孩子D.有左、右孩子8. 采用線性探測法解決沖突問題，所產(chǎn)生的一系列后繼散列地址（      ）A.必須大于等于原散列地址 B.必須小于等于原散列地址C.可以大于或小于但不能等于原散列地址 D.地址大小沒有具體限制9. 用快速排序方法對包含

5、有n個關鍵字的序列進行排序，最壞情況下執(zhí)行的時間復雜度為（      ）A.O(n)        B.O(log2n) C.O(nlog2n)       D.O(n2)10. 下列數(shù)據(jù)結(jié)構(gòu)中，(      )不都是線性結(jié)構(gòu)。A.棧和隊列         &

6、#160; B.隊列和數(shù)組 C.數(shù)組和串         D.文件和隊列11. 為了最快地對線性結(jié)構(gòu)的數(shù)據(jù)進行某數(shù)據(jù)元素的讀取操作，則其數(shù)據(jù)存儲結(jié)構(gòu)宜采用(      )方式。A.順序存儲       B.鏈式存儲 C.索引存儲    D.散列存儲12. 具有100個結(jié)點的完全二叉樹的深度為(    

7、;  )A.6               B.7              C.8                D.913. 順序查找法與二分查找法對存儲結(jié)

8、構(gòu)的要求是(      )A.順序查找與二分查找均只適用于順序表B.順序查找與二分查找既適用于順序表，也適用于鏈表C.順序查找只適用于順序表D.二分查找只適用于順序表14. 在開散列表上，每個地址單元所鏈接的同義詞表(      )A.其鍵值相同       B.其元素值相同 C.其散列地址相同      D.其含義相同15. 一組記錄的關鍵碼為(46，79，56，3

9、8，40，84)，則利用快速排序方法，以第一個記錄為基準得到的一次劃分結(jié)果為(      )A.38，40，46，56，79，84              B.40，38，46，79，56，84C.40，38，46，56，79，84              D.40，38，46，84，

10、56，7916. 下列說法正確的是（）A數(shù)據(jù)是數(shù)據(jù)元素的基本單位 B數(shù)據(jù)元素是數(shù)據(jù)項中不可分割的最小標識單位C數(shù)據(jù)可由若干個數(shù)據(jù)元素構(gòu)成 D數(shù)據(jù)項可由若干個數(shù)據(jù)元素構(gòu)成17. 數(shù)據(jù)結(jié)構(gòu)的基本任務是（）A邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的設計   B數(shù)據(jù)結(jié)構(gòu)的運算實現(xiàn)C數(shù)據(jù)結(jié)構(gòu)的評價與選擇    D數(shù)據(jù)結(jié)構(gòu)的設計與實現(xiàn)18. 在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點，并使插入后仍然有序，則該操作的時間復雜性量級為（）AO（1）      BO（n） CO（nlog2n）  &

11、#160;  DO(n2)19. 順序存儲的線性表（a1,a2,an）,在任一結(jié)點前插入一個新結(jié)點時所需移動結(jié)點的平均次數(shù)為（）An       Bn/2 Cn+1       D(n+1)/220. 下列數(shù)據(jù)組織形式中，（）的各個結(jié)點可以任意鄰接。A集合       B樹形結(jié)構(gòu) C線性結(jié)構(gòu)      D圖狀

12、結(jié)構(gòu)21. 在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費時間最少的是（）A單鏈表      B雙鏈表 C循環(huán)鏈表      D順序表22. 除根結(jié)點外，樹上每個結(jié)點（）A可有任意多個孩子、任意多個雙親 B可有任意多個孩子、一個雙親C可有一個孩子、任意多個雙親 D只有一個孩子、一個雙親23. 若評價算法的時間復雜性，比較對數(shù)階量級與線性階量級，通常（）A.對數(shù)階量級復雜性大于線性階量級 B.對數(shù)階量級復雜性小于線性階量級C.對數(shù)階量級復雜性等于線性階量級 D.兩者之間無法比較24.

13、下列查找中，效率最高的查找方法是（）A.順序查找       B.折半查找 C.索引順序查找      D.分塊查找25. 直接插入排序算法，其時間復雜性為（）A.O(1)        B.O(n) C.O(nlog2n)       D.O(n2)26. 數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)是指(  

14、0;  )A.數(shù)組、鏈表、樹、圖形結(jié)構(gòu)                  B.線性表、鏈表、棧隊列、數(shù)組廣義表C.線性結(jié)構(gòu)、鏈表、樹、圖形結(jié)構(gòu)           D.集合、線性結(jié)構(gòu)、樹、圖形結(jié)構(gòu)27. 數(shù)據(jù)結(jié)構(gòu)中，通常采用兩種方法衡量算法的時間復雜性，即(     )

15、A.最大時間復雜性和最小時間復雜性          B.最好時間復雜性和最壞時間復雜性C.部分時間復雜性和總體時間復雜性 D.平均時間復雜性和最壞時間復雜性28. 下列關于線性表的敘述中，不正確的是(     )A.線性表是n個結(jié)點的有窮序列 B.線性表可以為空表C.線性表的每一個結(jié)點有且僅有一個前趨和一個后繼D.線性表結(jié)點間的邏輯關系是1:1的聯(lián)系29. 在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，則刪除p所指結(jié)點的后繼結(jié)點的正確操作是(  &

16、#160;  )A.p=p->next             B.p->next=p->next C.p->next=p->next->next   D.p->next=p30. 棧和隊列(     )A.共同之處在于二者都是先進先出的特殊的線性表B.共同之處在于二者都是先進后出的特殊的線性表C.共同之處在于二者都只允許在頂端執(zhí)行刪除操作D.沒

17、有共同之處31. 要解決散列引起的沖突問題，常采用的方法有(     )A.數(shù)字分析法、平方取中法         B.數(shù)字分析法、線性探測法C.二次探測法、平方取中法 D.二次探測法、鏈地址法32. 若在長度為n的順序表中插入一個結(jié)點，則其結(jié)點的移動次數(shù)(      )A.最少為0，最多為n     B.最少為1，最多為nC.最少為0，最多為n+1  &#

18、160; D.最少為1，最多為n+133. 在一個單鏈表中，若p所指結(jié)點是q所指結(jié)點的前驅(qū)結(jié)點，則在結(jié)點p、q之間插入結(jié)點s的正確操作是(      )A.s->next=q；p->next=s->next B.p->next=q；p->next=sC.s->next=q->next；p->next=s D.s->next=q->next；p->next=s->next34. 若有一串數(shù)字5、6、7、8入棧，則其不可能的輸出序列為(  

19、0;   )A.5、6、7、8       B.8、7、6、5 C.8、7、5、6        D.5、6、8、735. 數(shù)據(jù)的四種基本存儲結(jié)構(gòu)是指（）A.順序存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、直接存儲結(jié)構(gòu)、倒排存儲結(jié)構(gòu)B順序存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、散列存儲結(jié)構(gòu)C順序存儲結(jié)構(gòu)、非順序存儲結(jié)構(gòu)、指針存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)D.順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)、圖型存儲結(jié)構(gòu)36. 有關棧的描述，正確的是（）A.棧是一種先進先出的

20、特殊的線性表 B.只能從棧頂執(zhí)行插入、刪除操作C.只能從棧頂執(zhí)行插入、棧底執(zhí)行刪除 D.棧頂和棧底均可執(zhí)行插入、刪除操作37. 關于二叉樹性質(zhì)的描述，正確的是（）A.二叉樹結(jié)點的個數(shù)可以為0B.二叉樹至少含有一個根結(jié)點C.二叉樹若存在兩個結(jié)點，則必有一個為根，另一個為左孩子D.二叉樹若存在三個結(jié)點，則必有一個為根，另兩個分別為左、右孩子38. 具有4個結(jié)點的二叉樹可有（）A.4種形態(tài)  B.7種形態(tài) C.10種形態(tài)  D.11種形態(tài)39. 下列四種基本的邏輯結(jié)構(gòu)中，結(jié)構(gòu)結(jié)點間不存在任何邏輯聯(lián)系的是（）A.集合  B.線性結(jié)構(gòu) C.樹形結(jié)構(gòu) D.圖形結(jié)構(gòu)40. 計算

21、機算法指的是(      )。  A.計算方法       B.排序方法  C.解決某一問題的有限運算序列     D.調(diào)度方法41. 循環(huán)隊列用數(shù)組A0.m-1存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數(shù)是(      )。  A.(rear-front+m) MOD m      B.rea

22、r-front+1 C.rear-front-1      D.rear-front42. 棧和隊列的共同特點是(      )。  A.都是先進后出      B.都是先進先出   C.只允許在端點處插入和刪除元素      D.沒有共同點43. 深度為n的二叉樹中所含葉子結(jié)點的個數(shù)最多為(      )個。  A.2n  &

23、#160;   B.n      C.2n-1      D.2n-144. 對線性表進行二分查找時，要求線性表必須(      )。   A.以順序方式存儲    B.以鏈接方式存儲   C.以順序方式存儲，且結(jié)點按關鍵字有序排序   D.以鏈接方式存儲，且結(jié)點按關鍵字有序排序2008-12-5添加1下列關于數(shù)據(jù)結(jié)構(gòu)的敘述中，錯誤的是（ ）A、數(shù)據(jù)結(jié)構(gòu)是相關數(shù)據(jù)元素的集合 B

24、、數(shù)據(jù)元素是由若干數(shù)據(jù)項構(gòu)成的C、數(shù)據(jù)結(jié)構(gòu)就是文件 D、數(shù)據(jù)結(jié)構(gòu)分邏輯結(jié)構(gòu)和物理結(jié)構(gòu)2數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之間的關系是（ ）A、邏輯結(jié)構(gòu)反映物理結(jié)構(gòu) B、物理結(jié)構(gòu)反映邏輯結(jié)構(gòu)C、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)相互反映 D、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)無任何關系3在數(shù)據(jù)的存儲結(jié)構(gòu)中，結(jié)點（ ）A、就是數(shù)據(jù)元素 B、不是數(shù)據(jù)元素 C、就是系統(tǒng)數(shù)據(jù) D、元素數(shù)據(jù)和系統(tǒng)數(shù)據(jù)的組合體4關于算法效率，下面說法正確的是（ ）A、執(zhí)行時間越快越好 B、占用空間越少越好 C、既要執(zhí)行快又要空間少D、時空折中5向順序表插入結(jié)點時，（ ）A、一定要移動結(jié)點 B、一定不要移動結(jié)點 C、不一定要移動結(jié)點D、不知道是否要移動結(jié)點6單鏈表的

25、結(jié)點中含有一個（ ）指針A、向前 B、向后 C、空 D、任意7下列關于查找的說法中，正確的是（ ）A、只要給定了查找值，就一定能找到一個結(jié)點B、如果給定值是關于查找表主關鍵字的，就一定能找到一個結(jié)點C、查找表可以是關于關鍵字的有序表，或無序表D、查找過程是對結(jié)點進行比較和交換的過程8棧是一種特殊的（ ）表，其插入、刪除操作在表的同一端進行A、鏈表 B、順序表 C、線性表 D、循環(huán)鏈表9判斷一個順序棧是否為空棧的依據(jù)是（ ）A、棧頂指針棧底指針 B、棧頂指針< 棧底指針 C、棧頂指針> 棧底指針D、測試棧的每一個元素是否都是空棧10出棧操作的結(jié)果是（ ）A、取出并返回棧頂元素值 B、

26、將棧頂元素清空 C、移動棧頂指針指向下一個元素 D、向棧頂方向依次移動一個元素11設一個棧存儲在一維數(shù)組stackm中，并設棧底為第m個數(shù)組元素，棧頂指針為top。在執(zhí)行壓棧操作中，首先執(zhí)行（ ）A、top=top+1 B、top=top-1 C、top=m D、top=m-112對于一個用一維數(shù)組存儲一個順序隊列的情況，當（ ）時隊列為空A、隊頭指針隊尾指針 B、隊頭指針隊尾指針0C、隊尾指針0 D、隊頭指針013下列關于子串的的說法中，錯誤的是（ ）A、一個串是自身的子串 B、空串是任何串的子串 C、子串的長度一定小于主串的長度 D、子串是包含在主串中的串14若樹的度為3，則（ ）A、每個

27、結(jié)點都有3個分支 B、根結(jié)點有3個分支 C、每個結(jié)點有不超過3個分支 D、樹最多有3層15已知一棵二叉樹的（ ），就可畫出這棵二叉樹A、先根遍歷和后根遍歷序列 B、先根遍歷序列 C、后根遍歷序列D、先根遍歷和中根遍歷序列16下列關于樹的說法中，錯誤的是（ ）A、樹的葉子結(jié)點沒有后繼結(jié)點 B、樹的任何一個結(jié)點必在一個層子上C、一棵非空樹必有一個根結(jié)點，它沒有前驅(qū)結(jié)點，但有多個后繼結(jié)點D、一般樹都是無序樹17對一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則鄰接表中所用結(jié)點個數(shù)為（ ）A、e/2 B、e C、2e D、ne18在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（ ）倍

28、A、1/2 B、1 C、2 D、419具有5個頂點的無向圖至少應有（ ）條邊，才能確保圖是一個連通的A、5 B、6 C、4 D、820存儲在散列表中的結(jié)點的順序是（ ）的A、時間順序 B、關鍵字順序 C、隨機順序 D、不可預測順序21散列的查找效率與（ ）有關A、結(jié)點個數(shù) B、散列表大小 C、散列函數(shù) D、散列函數(shù)和解決沖突的方法二、填空題1數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、_、_和_四種。2對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度_為，在表尾插入元素的時間復雜度為_。3在廣義表的存儲結(jié)構(gòu)中，每個結(jié)點均包含有_個域。4當用長度為N的數(shù)組順序存儲一個棧時，假定角topN表示?？?，則表

29、示棧滿的條件為_。5.在一棵二叉樹中，第5層上的結(jié)點數(shù)最多為_。6. 在線性表的散列存儲中，處理沖突有_和_兩種方法。7.快速排序在平均情況下的空間復雜度為_，在最壞情況下的空間復雜度為_。8. 線性表(a0,a1,a2,an)(n1)中，每個元素占c個存儲單元，m為a0的首地址，則按順序存儲方式存儲線性表，an的存儲地址是_。9. 在棧的順序?qū)崿F(xiàn)中，設棧頂指針為top，?？盏臈l件為_。10. 隊列中允許進行插入的一端稱為_。11. 深度為90的滿二叉樹上，第11層有_個結(jié)點。12. 通常采用拉鏈法、線性探測法、多重散列法、二次探測法、公共溢出區(qū)法等解決散列地址沖突問題，若要避免“堆積”現(xiàn)象發(fā)

30、生應采用_。13. 對有序表(25,30,32,38,47,54,62,68,90,95)用二分查找法查找32，則所需的比較次數(shù)為 _。14. 樹型結(jié)構(gòu)結(jié)點間通過“父子”關系相互關聯(lián)，這種相互關聯(lián)構(gòu)成了數(shù)據(jù)間的_關系。15. 下列程序段的時間復雜性的量級為_。   for (i=1;i<n;i+)      for(j=i;j<n;j+)         t=t+116. 設某非空單鏈表，其結(jié)點形式為  

31、             ， 若要刪除指針q所指結(jié)點的直接后繼結(jié)點，則需執(zhí)行下列語句序列：   p=q->next;_;free(p);17. 隊列可以看成是一種運算受限制的線性表，也稱為_線性表。18. 表示邏輯關系的存儲結(jié)構(gòu)可以有四種方式，即順序存儲方式、鏈式存儲方式、_和散列存儲方式。19. 隊列中允許進行刪除的一端為_。20. 在順序存儲的線性表（a1,a2，an）中的第i (1in)個元素之前插入一個元素，則需向后移動_個元素。21. 在棧

32、的順序?qū)崿F(xiàn)中，若棧不滿，則進棧操作可以用下列算法片斷實現(xiàn)：_；sq -> datasq -> top=x；22. 對于有10個元素的有序表采用二分查找，需要比較3次方可找到其對應的鍵值，則該元素在有序表中的位置可能是_。23. 快速排序法在待排序數(shù)據(jù)_的情況下最不利于發(fā)揮其長處。24. 從數(shù)據(jù)結(jié)構(gòu)的觀點，數(shù)據(jù)通?？煞譃槿齻€層次，即：數(shù)據(jù)、數(shù)據(jù)元素和_。25. 對順序表執(zhí)行插入操作，其插入算法的平均時間復雜性為_。26. 在具有n個單元、且采用順序存儲的循環(huán)隊列中，隊滿時共有_個元素。27. 若front和rear分別表示循環(huán)隊列Q的頭指針和尾指針，m0表示該隊列的最大容量，則循環(huán)隊

33、列為空的條件是_。28. 樹的遍歷主要有先根遍歷、后根遍歷和_三種。29. 在最好的情況下，對于具有n個元素的有序序列，若采用冒泡排序，所需的比較次數(shù)為_次。30. 判斷帶頭結(jié)點head的單鏈表為空的條件是_。31. 若順序表每個元素長度均為5，其中第一個元素的存儲地址為30，則第6個元素的存儲地址為_。32若front和rear分別表示循環(huán)隊列Q的頭指針和尾指針，m0表示該隊列的最大容量，則判斷循環(huán)隊列為滿的條件是_。33. 若某二叉樹的先根遍歷序列為CEDBA，中根遍歷序列為DEBAC，則其后根遍歷序列為_。34. 圖主要采用_兩種存儲結(jié)構(gòu)存放。35. 對順序表執(zhí)行刪除操作，其刪除算法的平

34、均時間復雜性為_。36. 若head表示循環(huán)鏈表的頭指針，t表示尾結(jié)點，則頭指針head與尾結(jié)點t之間的關系可表示為_。37. 一個算法通?？蓮恼_性、易讀性、健壯性和_等四個方面評價、分析。38. 對于具有n個元素的有序序列，若采用冒泡排序，最多需要進行_趟起泡。39. 通常從四個方面評價算法的質(zhì)量：_、_、_和_。40. 設head為單鏈表的頭結(jié)點，則判斷單鏈表為空的條件是：_。41. 直接插入排序需要_個記錄的輔助空間。42. 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用_；若初始數(shù)據(jù)基本反序，則選用_。43.三、算法閱讀1Void AA (List&L) InitList(L); InsertRear(L,30); InsertFront(L,50); Int a4 = 5, 8, 12, 15; For (int I=0; i<4; i+) InsertRear