許昌學(xué)院數(shù)據(jù)結(jié)構(gòu) 考試題庫

1、目錄一、數(shù)據(jù)結(jié)構(gòu)概念1二、線性表1三、棧和隊(duì)列4四、字符串，數(shù)組，廣義表6五、樹型結(jié)構(gòu)：8六、圖型結(jié)構(gòu)：11七、查找排序12八、算法應(yīng)用及分析：18九、2013年統(tǒng)考計(jì)算機(jī)考研真題23十、2012 年計(jì)算機(jī)統(tǒng)考真題參考答案25十一、2013 年計(jì)算機(jī)統(tǒng)考真題及 其答案27一、 數(shù)據(jù)結(jié)構(gòu)概念1. 數(shù)據(jù)結(jié)構(gòu)是指【 】，具體包含三個(gè)方面：數(shù)據(jù)的【 】，數(shù)據(jù)的【 】和數(shù)據(jù)運(yùn)算的集合。 2. 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有【 】、【 】、【 】、【 】四類基本邏輯結(jié)構(gòu)，它們反映了四類基本的數(shù)據(jù)組織形式。3. 數(shù)據(jù)結(jié)構(gòu)S中：元素的集合為：A，B，C，D，E，F(xiàn)，G，H，I，關(guān)系的集合為：<A

2、,B>，<A,C>，<B,D>，<B,E>，<B,F>，<C,G>，<E,H>，<E,I>，<D,G>，則S的邏輯結(jié)構(gòu)為（ ） （A） 集合 （B）線性 (C) 樹 (D)圖4. 數(shù)據(jù)元素之間存在一對(duì)多關(guān)系的數(shù)據(jù)結(jié)構(gòu)是（ ）（A）線性表 （B）隊(duì)列 (C)二叉樹 (D)AOV-網(wǎng)5. 以下數(shù)據(jù)結(jié)構(gòu)中，屬于線性結(jié)構(gòu)的有（ ）（A） 線性表 （B） 樹 (C) 二叉樹 (D) 圖6. 存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)。( ) 7. 非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接前驅(qū)元素。 ( )

3、8. 非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接后繼元素。 ( )9. 順序存儲(chǔ)結(jié)構(gòu)只能用來存放線性結(jié)構(gòu)；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能存放非線性結(jié)構(gòu)。 ( )10. 算法就是程序。 ( )11. 一種邏輯結(jié)構(gòu)可以采用不同的存儲(chǔ)方式存放在計(jì)算機(jī)中。 ( )二、 線性表12. 線性結(jié)構(gòu)的基本特征是:若至少含有一個(gè)結(jié)點(diǎn)，則除起始結(jié)點(diǎn)沒有直接【 】外，其他結(jié)點(diǎn)有且僅有一個(gè)直接【 】;除終端結(jié)點(diǎn)沒有直接【 】外，其它結(jié)點(diǎn)有且僅有一個(gè)直接【 】。13. 線性表的順序存儲(chǔ)結(jié)構(gòu)是指用一組【 】的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素，邏輯上相鄰的元素，其物理位置【 】_。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素，其物理位置【 】

4、 。14. 線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素，其物理位置【 】。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素，其物理位置【 】 。15. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)【 】元素，具體移動(dòng)的元素個(gè)數(shù)與【 】有關(guān)。16. 單鏈表是線性表的的【 】存儲(chǔ)結(jié)構(gòu)。17. 單鏈表表示法的基本思想是用【 】表示結(jié)點(diǎn)間的邏輯關(guān)系。18. 循環(huán)鏈表與單鏈表的區(qū)別僅僅在于循環(huán)鏈表尾結(jié)點(diǎn)的鏈域值不是【 】，而是一個(gè)指向【 】的指針。19. 如右圖所示，在單鍵表中，P指針?biāo)附Y(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)S，操作的語句是： 【 】； 【 】。20. 順序表的類型中，假定每個(gè)datatype類型的變量占用k(k>

5、=1)個(gè)內(nèi)存單元，其中，b是順序表的第一個(gè)存儲(chǔ)結(jié)點(diǎn)的第一個(gè)單元的內(nèi)存地址，那么，第i個(gè)（1in）結(jié)點(diǎn)ai的存儲(chǔ)地址為【 】。21. 在單鏈表中，刪除P 指針?biāo)赶虻慕Y(jié)點(diǎn)的后繼（S指針指向的結(jié)點(diǎn)）的操作是【 】；free(【 】)。22. 以下為順序表的插入運(yùn)算，分析算法，請(qǐng)?jiān)诳瞻滋幪钌险_的語句。void insert_seqlist(seqlist *L，datatype x，int i) /*將x插入到順序表L的位序?yàn)閕的位置*/ if( L->last = maxsize-1 ) error(“表滿”)；if(i<1)|(i>L->last+2) error(“非

6、法位置”);for(j=L->last;j>=i-1;j-)【 】;L->datai-1=x; 【 】;23. 以下為順序表的刪除運(yùn)算，分析算法，請(qǐng)?jiān)诳瞻滋幪钌险_的語句。 void delete_sqlist(sqlist *L,int i) /*刪除順序表L中的第i-1個(gè)位置上的結(jié)點(diǎn)*/ if(i<1)|(i>L->last)error(“非法位置”)； for(j=i+1;j=L->last;j+)【 】; L->last=L->last-1;24. 下列有關(guān)線性表的敘述中，正確的是（ ）。(A)一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列 (

7、B)線性表中任何一個(gè)元素有且僅有一個(gè)直接前驅(qū)(C)線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼(D)以上說法都不正確25. 順序表是線性表的（ ）。 (A)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) (B)順序存儲(chǔ)結(jié)構(gòu) (C) 索引存儲(chǔ)結(jié)構(gòu) (D) 散列存儲(chǔ)結(jié)構(gòu)26. 從一個(gè)長度為n的順序表中刪除第i個(gè)元素(1in)時(shí),需向前移動(dòng)（ ）個(gè)元素。(A)n-i(B)n-i+1(C)n-i-1(D)i27. 一個(gè)長度為n的順序表中第i個(gè)位置上插入新元素(1in+1)時(shí),需向后移動(dòng)（ ）個(gè)元素。(A)n-i(B)n-i+1(C)n-i-1(D)i28. 下面的定義是（ ）。 typedef struct node int data ;

8、 struct node * next ; linklist; (A)順序表 (B)單鏈表 (C)雙向鏈表 (D)二叉鏈表29. 下面的定義是（ ）。 typedef struct int dataMaxsize ; int last ; seqlist; (A)順序表 (B)單鏈表 (C)靜態(tài)鏈表 (D)循環(huán)隊(duì)列30. 單鏈表的一個(gè)存儲(chǔ)結(jié)點(diǎn)包含（ ）。(A)數(shù)據(jù)域或指針域(B)指針域或鏈域 (C)指針域和鏈域 (D)數(shù)據(jù)域和鏈域31. 單鏈表中，增加頭結(jié)點(diǎn)的目的是為了（ ）。(A)使單鏈表至少有一個(gè)結(jié)點(diǎn) (B) 標(biāo)示表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置(C)方便運(yùn)算的實(shí)現(xiàn) (D)說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)

9、實(shí)現(xiàn)32. 對(duì)于單鏈表表示法，以下說法錯(cuò)誤的是（ ）。(A)指向鏈表的第一個(gè)結(jié)點(diǎn)的指針，稱為頭指針 (B)單鏈表的每一個(gè)結(jié)點(diǎn)都被一個(gè)指針?biāo)?C)終端結(jié)點(diǎn)的指針域就為NULL (D)尾指針變量具標(biāo)識(shí)單鏈表的作用，故常用尾指針變量來命名單鏈表33. 有一個(gè)含頭結(jié)點(diǎn)的單鏈表，頭指針為head，則判斷其是否為空的條件是（ ）。(A) head = = NULL (B) head->next = = NULL (C) head->next = = head (D) head != NULL34. 在帶頭結(jié)點(diǎn)的非空單鏈表H中，指針p指向某的結(jié)點(diǎn)，求p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指針q的算法是（ ）。(A)

10、q=H ; while(q!=p) q=q->next; (B) q=H ; while(q->next!=p) q=q->next; (C) q=H->next ; while(q!=p) q=q->next; (D) q=H->next ; while(q->next!=p) q=q->next; 35. 在帶頭結(jié)點(diǎn)的單鏈表H中，求單鏈表長度len的算法是（ ）。(A) len=0,p=H ; while(p->next!=NULL) len + ; p=p->next;(B) len=0,p=H->next ; while

11、(p->next!=NULL) len + ; p=p->next; (C) len=1,p=H ; while(p!=NULL) p=p->next; len + ; (D) len=1,p=H->next ; while(p->next!=NULL) p=p->next; len + ;36. 假設(shè)指針p指向單鏈表中的某一結(jié)點(diǎn),s為某結(jié)點(diǎn)指針，則在p指針后面插入結(jié)點(diǎn)s的操作是（ ）。(A) p->next=s;s=p->next; (B)p->next=s;s->next=p->next; (C) s->next=p-

12、>next;p->next=s; (D)s->next=p;p->next=s;37. 假設(shè)指針p指向單鏈表中的某一結(jié)點(diǎn),s為某結(jié)點(diǎn)指針，則在p指針前面插入結(jié)點(diǎn)s的操作是（ ）。(A) s->next=p->next;p->next=s; (B)p->next=s; s->next=p->next; (C) p->next=s ; s=p->next; (D)s->next=p ; p->next=s;38. 在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除x的后繼”的語句是（ ）。(A)p=p-next; (

13、B)p-next =p-next -next ; (C)p-next =p; (D)p=p-next-next;39. 某線性表中最常用的操作是存取序號(hào)為i的元素及其前驅(qū)的值，可采用的存儲(chǔ)的方式是（ ）。(A)順序表(B)單向鏈表(C)雙向循環(huán)鏈表 (D)單向循環(huán)鏈表40. 對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為（ ）。(A)順序表 (B)用頭指針表示的單循環(huán)鏈表 (C)用尾指針表示的單循環(huán)鏈表 (D)單鏈表41. 在單鏈表中，頭結(jié)點(diǎn)是必不可少的。( ) 42. 在單鏈表中，頭結(jié)點(diǎn)的作用是簡化運(yùn)算。( ) 43. 在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素在物理位置

14、上也是相鄰的。( ) 44. 在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的數(shù)據(jù)元素在物理位置上也是相鄰的。( ) 45. 只要內(nèi)存足夠大，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表長度不受限制。( ) 三、 棧和隊(duì)列46. 僅允許在表的一端進(jìn)行插入與刪除操作的線性表稱作【 】，允許在表的一端進(jìn)行插入，另一端進(jìn)行刪除操作的線性表稱作【 】。47. 棧稱為【 】線性表。隊(duì)稱為【 】線性表。48. 隊(duì)列的操作是按【 】的原則進(jìn)行的。49. 棧的運(yùn)算特點(diǎn)是【 】。請(qǐng)將用C語言的順序棧的定義補(bǔ)充完整：typedef struct 【 】； 【 】；seqstack； 50. 以下運(yùn)算實(shí)現(xiàn)在順序棧上的進(jìn)棧，請(qǐng)?jiān)诳瞻滋幱眠m當(dāng)?shù)恼Z句

15、予以填充。typedef struct DataType datamaxsize ； int top；SeqStack； int Push(SeqStack *sq ,DataType x) if(sp->top= maxsize-1) error(“棧滿”)；return(0)； else【 】； 【 】=x；return(1)；51. 隊(duì)列的操作是按【 】原則進(jìn)行的。循環(huán)隊(duì)列Q分配Maxsize個(gè)存儲(chǔ)單元，隊(duì)頭指針為front，隊(duì)尾指針為rear，采用少用一個(gè)空間的方法處理，判斷隊(duì)列滿的條件是【 】。52. 循環(huán)隊(duì)列是隊(duì)列的【 】存儲(chǔ)結(jié)構(gòu)。53. 循環(huán)隊(duì)列Q分配Maxsize個(gè)存儲(chǔ)單

16、元，隊(duì)頭指針為front，隊(duì)尾指針為rear，采用少用一個(gè)空間的方法處理，判斷隊(duì)列滿的條件是【 】。54. 以下順序棧定義及出棧運(yùn)算實(shí)現(xiàn)，請(qǐng)?jiān)诳瞻滋幱眠m當(dāng)語句填充。typedef struct DataType datamaxsize ； int top；SeqStack； int Pop(SeqStack *sp ，DataType *x) if (sp->top=0) error(“空?！? ； return(0) ； else *x=_； _； return(1) ； 55. 棧操作的原則是（ ）。(A)先進(jìn)先出 (B)后進(jìn)先出 (C)棧頂插入 (D) 棧頂刪除56. 棧的兩種常用

17、存儲(chǔ)結(jié)構(gòu)分別為(A)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) (B)順序存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu) (C)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和索引存儲(chǔ)結(jié)構(gòu) (D)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)57. 有一棧，元素A，B，C，D依次進(jìn)棧 ,則以下出棧序列中不可能得到的是（ ）。(A) D、C、B、A (B) C、B、A、D (C) A、B、C、D (D) D、C、A、B58. 一個(gè)棧的入棧序列是A,B,C,D,E,則不可能的出棧序列是（ ）。(A)EDCBA (B)DECBA (C)DCEAB (D)ABCDE 59. 若進(jìn)棧序列為a，b，c，則通過入出棧操作可能得到的a，b，c的不同排列個(gè)數(shù)為(A)4 (B)5 (C)6 (D)760.

18、 循環(huán)隊(duì)列是隊(duì)列的（ ）。 (A)順序存儲(chǔ)結(jié)構(gòu)（B）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(C)索引存儲(chǔ)結(jié)構(gòu)(D)散列存儲(chǔ)結(jié)構(gòu) 61. 設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1n，其頭尾指針分別是f、r，則隊(duì)列中元素個(gè)數(shù)為（ ）。 (A)r - f (B)r f + 1 (C)(r f + 1)mod n(D)( r f + n ) mod n62. 在循環(huán)隊(duì)列中(少用一個(gè)存儲(chǔ)空間)，隊(duì)滿的條件是（ ）。 (A)(rear+1)%maxsize=front                  (B)raer=front (C)(front+1

19、)%maxsize=rear                  (D)rear=0 63. 循環(huán)隊(duì)列的隊(duì)滿條件為（ ）。(A) (sq.rear+1) % mazsize =(sq.front+1) % maxsize;(B) (sq.rear+1) % maxsize =sq.front+1(C) sq.(rear+1) % maxsize =sq.front(D) sq.rear =sq.front64. 設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為頭指針，rear為尾指針，執(zhí)行

20、出隊(duì)操作,其頭指針的值為（ ）。 (A) front=front+1 (B) front=(front+1)%(m-1) (C) front=(front-1)%m (D) front=(front+1)%m65. 棧和隊(duì)列與線性表的邏輯結(jié)構(gòu)相同。( ) 66. 棧只能在棧頂進(jìn)行插入和刪除。( ) 67. 隊(duì)列只能在隊(duì)首進(jìn)行刪除，在隊(duì)尾進(jìn)行插入。( ) 68. 隊(duì)列只能在隊(duì)尾進(jìn)行刪除，在隊(duì)首進(jìn)行插入。( ) 四、 字符串，數(shù)組，廣義表69. 通常采用【 】存儲(chǔ)結(jié)構(gòu)來存放數(shù)組 。對(duì)二維數(shù)組可有兩種存儲(chǔ)方法：一種是以【 】為主序的存儲(chǔ)方式，另一種是以【 】為主序的存儲(chǔ)方式。70. 已知具有n個(gè)元素

21、的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素的地址為LOC(a1)，那么，LOC(ai)= 【 】。71. 在C語言中定義的二維數(shù)組int M1020，每個(gè)元素（整數(shù)）占兩個(gè)存儲(chǔ)單元，數(shù)組的起始地址為2000， M819的存儲(chǔ)值為【 】。元素M510的存儲(chǔ)位置為【 】。72. 假設(shè)有6行8列的二維數(shù)組A，每個(gè)元素占用6個(gè)字節(jié)，存儲(chǔ)器按字節(jié)編址。已知A的基地址為1000，那么元素A3，6在按行存儲(chǔ)時(shí)的地址是【 】，按列存儲(chǔ)時(shí)的地址是【 】。73. 對(duì)稱方陣采用壓縮存儲(chǔ)， 即為每一對(duì)對(duì)稱位置元素只分配一個(gè)存儲(chǔ)空間 ，則可將n2個(gè)元素壓縮存儲(chǔ)到【 】個(gè)元素的存儲(chǔ)空間中。74. 有一

22、個(gè)10階對(duì)稱矩陣A1010，采用壓縮存儲(chǔ)方式以行序?yàn)橹鞔鎯?chǔ)，A00的位置是1，則A85的位置是【 】。75. 三元組表是【 】的【 】存儲(chǔ)結(jié)構(gòu)。76. 字符串S=“Computer”中，以p為首字符的子串有【 】個(gè)。77. TAILHEAD(a,b),(c,d)運(yùn)算的結(jié)果是【 】。78. 廣義表L=（x,a）,(x,a,(b,c),y）的長度是【 】。79. 設(shè)廣義表A=(a,b),B=(c,d),求head( (A, B) )的值為【 】。80. 有如下稀疏矩陣，請(qǐng)寫出它的三元組表：81. 串是（ ）。(A)一些符號(hào)構(gòu)成的序列(B)有限個(gè)字母構(gòu)成的序列 (C)一個(gè)以上的字符構(gòu)成的序列(D)有

23、限個(gè)字符構(gòu)成的序列82. 已知函數(shù)Sub(s,i,j)的功能是返回串s中從第i個(gè)字符起長度為j的子串，函數(shù)Scopy(s,t)的功能為復(fù)制串t到s。若字符串S=“SCIENCESTUDY”，則調(diào)用函數(shù)Scopy(P,Sub(S,1,7)后得到（ ）。(A)P=“SCIENCE” (B)P=“STUDY” (C)S=“SCIENCE ” (D)S=“STUDY”83. 設(shè)有一個(gè)二維數(shù)組A68,假設(shè)A00存放位置在1000,每個(gè)元素占6個(gè)空間，按行優(yōu)先存儲(chǔ)，則A36的存儲(chǔ)位置是(A)1180 (B)1126 (C)126 (D)18084. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為2

24、，則第五個(gè)元素的地址是_。(A)110 (B)108 (C)100 (D)12085. 為了節(jié)省存儲(chǔ)空間，將n階對(duì)稱矩陣A(下標(biāo)從1開始)中包括主對(duì)角線元素在內(nèi)的下三角部分的所有元素按照行序?yàn)橹餍蚍绞酱娣旁谝痪S數(shù)組B1:n(n+1)/2中，對(duì)任意下三角部分的元素aij(ij)在數(shù)組B的下標(biāo)k是_。 (A)i(i-1)/2+j-1 (B)i(i-1)/2+j (C)i(i+1)/2+j-1 (D)i(i+1)/2+j 86. 稀疏矩陣一般的壓縮存儲(chǔ)有兩種，即（ ）。 (A) 二維數(shù)組和三維數(shù)組 (B) 三元組表和哈希表 (C) 三元組表和十字鏈表 (D)哈希表和十字鏈表87. 基于三元組的稀疏矩

25、陣，對(duì)每個(gè)非零元素aij,可以用一個(gè)（ ）唯一確定。(A)非零元素 (B)三元組(i,j,aij) (C) aij (D) i,j88. 廣義表A=(),(a),(b,(c,(D)的長度為_。(A)2    (B)3   (C)4   (D)5 89. 空串與由空格組成的串沒有區(qū)別。( ) 90. 對(duì)稱矩陣的壓縮存儲(chǔ)是指對(duì)矩陣中的值相同的元素只分配一個(gè)存儲(chǔ)空間。( ) 91. 對(duì)稱矩陣的壓縮存儲(chǔ)是指對(duì)矩陣中的規(guī)律元素只分配一個(gè)存儲(chǔ)空間。( ) 92. N階下三角矩陣壓縮存儲(chǔ)需要n*(n+1)/2個(gè)存儲(chǔ)空間。( ) 93. 三元組表是稀疏矩陣的順序存儲(chǔ)結(jié)構(gòu)

26、。( ) 五、 樹型結(jié)構(gòu) 94. 在二叉樹中，第i層的結(jié)點(diǎn)數(shù)最多為【 】；95. 深度為k的二叉樹的結(jié)點(diǎn)總數(shù)最多為【 】。96. 對(duì)任何二叉樹，若度為2的節(jié)點(diǎn)數(shù)為n2，則葉子數(shù)n0=【 】。97. 在一棵完全二叉樹中，若編號(hào)為i的結(jié)點(diǎn)有左孩子，則該左孩子結(jié)點(diǎn)的編號(hào)為【 】；若編號(hào)為i的結(jié)點(diǎn)有右孩子，則該右孩子結(jié)點(diǎn)的編號(hào)為【 】。98. 一棵深度為5的二叉樹最多有【 】 個(gè)結(jié)點(diǎn)。99. 深度為h且有【 】個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。(設(shè)根結(jié)點(diǎn)處在第1層)。100. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹，若按層次從上到下、從左到右對(duì)其編號(hào)（根結(jié)點(diǎn)為1號(hào)），則編號(hào)最大的分支結(jié)點(diǎn)序號(hào)是【 】，編號(hào)最小的分支結(jié)點(diǎn)序

27、號(hào)是【 】，編號(hào)最大的葉子結(jié)點(diǎn)序號(hào)是【 】，編號(hào)最小的葉子結(jié)點(diǎn)序號(hào)是【 】。101. 在有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存放，空鏈域的個(gè)數(shù)為【 】。102. 二叉樹通常有【 】存儲(chǔ)結(jié)構(gòu)和【 】存儲(chǔ)結(jié)構(gòu)兩類存儲(chǔ)結(jié)構(gòu)。103. 給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I； 中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹【 】。104. 請(qǐng)對(duì)給定的二叉樹的存儲(chǔ)結(jié)構(gòu)，將二叉樹的中序遍歷輸出結(jié)點(diǎn)遞歸算法補(bǔ)充完整：typedef struct node char data； /*元素為字符型*/struct node * Lchild，*Rchild

28、； BiTree； void Inorder(BiTree root ) if ( root != NULL ) 【 】；【 】； 【 】； 105. 請(qǐng)對(duì)給定的二叉樹的存儲(chǔ)結(jié)構(gòu)，將二叉樹的先序遍歷輸出結(jié)點(diǎn)遞歸算法補(bǔ)充完整：typedef struct node char data; /*元素為字符型*/struct node * Lchild,*Rchild; BiTree; void preorder(BiTree root ) if ( root != NULL ) 【 】;【 】; 【 】; 106. 以下程序段采用先根遍歷方法求二叉樹的葉子數(shù)，請(qǐng)?jiān)跈M線處填充適當(dāng)?shù)恼Z句。void co

29、untleaf(bitree *t,int *count)/*根指針為t，假定葉子數(shù)count的初值為0*/ if(t!=NULL) if(t->lchild=NULL)&&(t->rchild=NULL) 【 】; countleaf(t->lchild,&count); 【 】 107. 哈夫曼樹是帶權(quán)路徑長度【 】的樹，通常權(quán)值較大的結(jié)點(diǎn)離根【 】。108. 有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)總數(shù)為【 】。109. 用5個(gè)權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼樹的帶權(quán)路徑長度是【 】 。110. 按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有_種形態(tài)

30、。(A)3 (B)4 (C)5 (D)6111. 3個(gè)結(jié)點(diǎn)可構(gòu)成（ ）個(gè)不同形態(tài)的二叉樹。(A)2 B 3 C 4 D 5112. 二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，它（ ）。(A)不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ); (B)不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ); (C)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ); (D)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用 113. 下列陳述中正確的是（ ）。(A)二叉樹是度為2的樹 (B)二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分(C)二叉樹中必有度為2的結(jié)點(diǎn) (D)二叉樹中最多只有兩棵子樹，并且有左右之分114. 設(shè)有一棵22個(gè)結(jié)點(diǎn)的完全二叉樹，那么整棵二叉樹有（ ）個(gè)度為0的結(jié)點(diǎn)? (A)6 (B)7

31、 (C)8 (D)11115. 某非空二叉樹共有葉結(jié)點(diǎn)15個(gè)，沒有度為1的結(jié)點(diǎn)，則該樹共有（ ）個(gè)結(jié)點(diǎn)。(A)29             (B)28           (C)27            (D)不能確定116. 已知完全二叉樹有26個(gè)結(jié)點(diǎn)，則整棵二叉樹有（ ）個(gè)度為1的結(jié)點(diǎn)？ (A)1 (B)0 (C)2 (D)不確定117. 將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹編號(hào)，根結(jié)點(diǎn)為1，每層從左到右依次編號(hào)，則編號(hào)為49

32、的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)是（ ）。 (A)23 (B) 24 (C) 25 (D)26118. 對(duì)二叉樹從1開始編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編號(hào)，同一個(gè)結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，則可采用（ ）方法實(shí)現(xiàn)編號(hào)。(A) 前序遍歷 (B) 中序遍歷 (C) 后序遍歷 (D) 從根開始進(jìn)行層次遍歷FEDBAC圖119. 一棵二叉樹有n個(gè)結(jié)點(diǎn)，要按某順序?qū)υ摱鏄渲械慕Y(jié)點(diǎn)編號(hào)，（號(hào)碼為1-n），編號(hào)須具有如下性質(zhì)：二叉樹中任一結(jié)點(diǎn)V，其編號(hào)等于其左子樹中結(jié)點(diǎn)的最大編號(hào)加1。而其右子樹中結(jié)點(diǎn)的最小編號(hào)等于V的編號(hào)加1。試問應(yīng)按（）遍歷順序編號(hào)。(A)前根 B中根 C后根

33、D層次120. 已給如圖的二叉樹，它的中序遍歷序列是（ ）。 (A)ABECDF (B)ABCDEF (C)CBDAEF (D)CDBFEA121. 某二叉樹的中序遍歷為：BDAEC，后序遍歷為：DBECA，則前序遍歷為（ ）。(A)ABDCE     (B)ADBCE         (C)ABDEC           (D)BDACE 122. 已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為（ ）。(A)DEBAFC (B)DEFBCA (C)DEBCF

34、A (D)DEBFCA123. 在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為（ ）。(A)不確定 (B)2n (C)2n+1 (D) 2n-1 124. 哈夫曼樹的帶權(quán)路徑長度是（ ）。 (A) 所有結(jié)點(diǎn)權(quán)值之和 (B) 所有葉結(jié)點(diǎn)帶權(quán)路徑長度之和(C) 權(quán)結(jié)點(diǎn)的值 (D) 除根以外所有結(jié)點(diǎn)權(quán)值之和125. 下列說法正確的是（ ）。 (A) 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先根遍歷序列相同(B) 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的后根遍歷序列相同(C) 樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的先根遍歷序列相同(D) 樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后根遍歷序列相同126. 對(duì)于一棵任意二叉樹，若葉

35、子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則有n2= n0+1。( ) 127. 對(duì)于一棵任意二叉樹，若葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則有n0= n2+1。( ) 128. 深度為n的非空二叉樹的第i層最多有2n-1 個(gè)結(jié)點(diǎn)。( ) 129. 非空二叉樹的第i層最多有2i-1 個(gè)結(jié)點(diǎn)。( ) 130. 二叉樹中，任何一個(gè)結(jié)點(diǎn)的度為2。( ) 131. 二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。( ) 132. 具有12個(gè)結(jié)點(diǎn)的完全二叉樹有4層深。( ) 133. 具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。( ) 134. 線索二叉樹是在二叉樹的所有結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)中增加先驅(qū)和后繼指針得到

36、的。( ) 135. 已知一棵二叉樹的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹。( ) 136. 已知一棵二叉樹的前序序列和后序序列可以唯一地構(gòu)造出該二叉樹。( ) 137. 哈夫曼樹中不存在度為1的分支結(jié)點(diǎn)。( ) 12345圖138. 有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)。( ) 六、 圖型結(jié)構(gòu)139. 在無向圖中，如果從頂點(diǎn)v到頂點(diǎn)v有路徑，則稱v和v是【 】的。140. 圖的存儲(chǔ)結(jié)構(gòu)主要有【 】和【 】兩種。141. 遍歷圖的基本方法有【 】優(yōu)先搜索和【 】優(yōu)先搜索兩種。142. 有如圖所示的圖的鄰接矩陣，從1頂點(diǎn)出發(fā)對(duì)該圖進(jìn)行深度優(yōu)先搜索的結(jié)點(diǎn)序列是【 】，廣度優(yōu)先搜索的結(jié)點(diǎn)

37、序列是【 】。143. 若連通圖G的頂點(diǎn)個(gè)數(shù)為n，則G的生成樹的邊數(shù)為【 】。144. 有向圖G用鄰接矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的【 】 度 。145. 有向圖G用鄰接矩陣存儲(chǔ)，其第i列的所有元素之和等于頂點(diǎn)i的【 】 度 。146. 無向圖的鄰接矩陣是一個(gè)【 】矩陣；在鄰接矩陣上，無向圖中頂點(diǎn)vi的度為【 】； 鄰接表上，無向圖中頂點(diǎn)vi的度為【 】。147. 一個(gè)具有n個(gè)頂點(diǎn)的簡單無向圖最多（ ）條邊。(A)n (B)n(n-1) (C)n(n-1)/2 (D)2n148. 有8個(gè)結(jié)點(diǎn)的無向連通圖最少有（ ）條邊。 (A)5 (B) 6 (C)7 (D)8149. 一個(gè)具有

38、n個(gè)頂點(diǎn)的無向完全圖的邊數(shù)為badcef圖(A) n(n+1)/2 (B) n(n-1)/2 (C) n(n-1) (D) n(n+1)150. 任何一個(gè)帶權(quán)的無向連通圖的最小生成樹(A)只有一棵 (B)有一棵或多棵 (C)一定有多棵 (D) 可能不存在151. 已知一個(gè)有向圖，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷，不可能得到的DFS序列為(A) a d b e f c B .a d c e f bC .a d c b f e (D) a d e f c b152. 對(duì)下圖1所示的帶權(quán)有向圖，從頂點(diǎn)1到5 的最短路徑為（ ）。(A)1,4,5 (B)1,2,3,551234圖(C)1,4,3,5 (

39、D)1,2,4,3,5153. 已給圖，哪一項(xiàng)是該圖的拓?fù)渑判颍?(A)1，2，3，4，5 (B)1，3，2，4，5(C)1，2，4，3，5 (D)1，2，3，5，4154. 某有向圖由m個(gè)頂點(diǎn)和n條邊組成，使用鄰接表進(jìn)行存儲(chǔ)，則該鄰接表由m個(gè)頭結(jié)點(diǎn)和n個(gè)表結(jié)點(diǎn)組成。( ) 155. 用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。( ) 156. 有n個(gè)結(jié)點(diǎn)的無向完全圖有n*(n-1)/2條邊。( ) 157. 有n個(gè)結(jié)點(diǎn)的有向完全圖有n*(n-1)/2條邊。( ) 158. 某無向圖由m個(gè)頂點(diǎn)和n條邊組成，使用鄰接表進(jìn)行存儲(chǔ)，則

40、該鄰接表由m個(gè)頭結(jié)點(diǎn)和n個(gè)表結(jié)點(diǎn)組成。( ) 159. 有向圖中所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和。( ) 160. 普里姆算法是采用“加邊法”構(gòu)造最小生成樹的。( ) 161. AOE 網(wǎng)是一種帶權(quán)的無環(huán)連通圖。( ) 162. AOE 網(wǎng)是一種帶權(quán)的有向無環(huán)圖。( ) 163. AOE網(wǎng)所表示的工程至少所需要的時(shí)間等于從源點(diǎn)到匯點(diǎn)的最長路徑長度。( ) 164. AOE網(wǎng)來表示工程計(jì)劃時(shí)，從源點(diǎn)到匯點(diǎn)的最短路徑表示了關(guān)鍵路徑。( ) 165. AOV網(wǎng)的拓?fù)湫蛄惺俏ㄒ坏摹? ) 166. 帶權(quán)連通圖的最小生成樹的權(quán)值之和是它的生成樹的權(quán)值之和中最小的。( ) 167. 帶權(quán)連通圖的最

41、小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之和。( ) 168. 迪杰斯特拉（Dijkstra）算法是按照最短路徑長度遞增的順序產(chǎn)生所有的最短路徑。( )七、 查找排序169. 折半查找對(duì)待查找的列表有兩個(gè)要求：（1）采用【 】存儲(chǔ)結(jié)構(gòu)（2）關(guān)鍵字【 】排列。170. 在線性表中采用折半查找法查找一個(gè)數(shù)據(jù)元素，線性表中元素應(yīng)該按值有序，并且采用【 】存儲(chǔ)結(jié)構(gòu)。171. 在表示一棵二叉排序樹的二叉鏈表上，要找鍵值比某結(jié)點(diǎn)X的鍵值【 】的結(jié)點(diǎn)，只需通過結(jié)點(diǎn)X的左指針到它的左子樹中去找。172. 中根遍歷一棵二叉排序樹所得的結(jié)點(diǎn)訪問序列是鍵值的【 】序列。173. 在一棵空的二叉排序樹中依次插入

42、關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，所得到的二叉排序樹是【 】。174. 已知序列(34，76，45，18，26，54，92，65)，按照逐點(diǎn)插入法建立一棵二叉排序列樹，該樹的深度是【 】。175. 平衡因子是【 】。平衡的二叉排序樹的平衡因子的值只能是【 】。176. 哈希法中影響關(guān)鍵字比較次數(shù)的三個(gè)因素是：（1）【 】（2）【 】（3）哈希表的裝填因子。哈希表的裝填因子是：【 】。的值越小，發(fā)生沖突的可能性越小，的值越大，發(fā)生沖突的可能性越大。177. 在數(shù)值無規(guī)律的線性表中進(jìn)行檢索的方法是【 】 。178. 按照排序過程涉及的存儲(chǔ)設(shè)備的不同，排序可分為【 】排

43、序和【 】排序。179. 排序過程中一般進(jìn)行兩個(gè)基本操作（）【 】（）【 】。其中（）是必要的，（）可以采用適當(dāng)?shù)拇鎯?chǔ)方式避免。180. 給定關(guān)鍵字（48，62，35，77，55，14，35，98）進(jìn)行一趟快速排序的結(jié)果是【 】。181. 若對(duì)序列(49，38，65，97，76，13，27，50)采用快速排序，則第一趟排序后序列的狀態(tài)是【 】。182. 設(shè)有散列函數(shù)H(k)=k mod 13散列表為T012，用線性探測再散列。假定在某一時(shí)刻T的狀態(tài)為：T0123456789101112808534183. 下一個(gè)被插入的關(guān)鍵碼是42，其插入的位置是: 【 】。184. 請(qǐng)將直接選擇排序算法補(bǔ)充

44、完整：void SelectSort(RecordType R,int length) n = length; for(i=1;i<=【 】;i+) k=【 】; for(j=i+1;j<=n;j+) if(Rj.key < Rk.key ) k=【 】; if (【 】) x=Ri;Ri=Rk;Rk=x; 185. 以下簡單選擇排序算法，請(qǐng)將算法補(bǔ)充完整: void SelectSort(RecordType R , int length) n=length; for ( i=1 ; i<= n-1 ; i+) 【 】; for ( j=i+1; j<=n ;

45、j+ ) if ( Rj.key < R【 】.key ) k=j; if (k!=i) x=Ri ; Ri=Rk ; Rk=x; 186. 以下是直接選擇排序的算法。請(qǐng)分析算法，并在橫線上填充適當(dāng)?shù)恼Z句。 void select(seqlist r,int n) for(i=1;i<=【 】;i+)/*每次循環(huán)，選擇出一個(gè)最小鍵值*/ k=i; for(j=i+1;j<=n;j+) if(rj.key<rk.key) 【 】; if(【 】)swap(rk,ri）;/*函數(shù)swap(rk,ri）交換rk和ri的位置*/ 187. 以下為直接插入排序的算法。請(qǐng)分析算法，

46、并在_上填充適當(dāng)?shù)恼Z句。 void straightsort(seqlist r,int n) for(i=【 】;i<=n;i+) r0=ri; j=i-1; while(r0.key<rj.key) rj+1= 【 】; j-; rj+1= 【 】;188. 直接插入排序的基本操作是：將第i個(gè)記錄插入到前i-1個(gè)已排好序的記錄中。請(qǐng)將如下的直接插入排序算法補(bǔ)充完整：void InsSort ( RecordType R , int length) for(i=2 ; i<=length ; i+) R0= 【 】; for(j = i-1; 【 】; j-) Rj+1=R

47、j ; R【 】=R0; 189. 請(qǐng)將如下的折半查找算法補(bǔ)充完整：int BinSrch （SqList L,  KeyType k）        low=1 ;   high=L.length;/*置區(qū)間初值*/       while( low<=high)          mid=【 】;    &#

48、160;       if  (k= =L.rmid. key)  return（mid）;             else  if (【 】)   high=mid-1;             else 【 】;    &#

49、160;            return (0);190. 如下算法是折半查找算法，請(qǐng)將算法補(bǔ)充完整：typedef struct KeyType key; OtherType other_data; RecordType;typedef struct RecordType rMaxsize; int length; RecordList;int BinSrch (RecordList L,KeyType k) Low=1; High=【 】; while (【 】) mid = (Low

50、+ High)/2; if ( k= L.rmid.key) return (mid); else if ( k< L.rmid.key) 【 】; else Low=mid+1; return (0);191. 如下算法是設(shè)置監(jiān)視哨的順序查找法，請(qǐng)將算法補(bǔ)充完整:typedef struct KeyType key; OtherType other_data; RecordType;typedef struct RecordType rMaxsize; int length; RecordList;int SeqSearch(RecordList L,KeyType k) 【 】=k; i=L.length; while(L.ri.key!= 【 】) i-; return(【 】);192