許昌學院數(shù)據(jù)結構 考試題庫

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

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

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

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

5、=1)個內存單元，其中，b是順序表的第一個存儲結點的第一個單元的內存地址，那么，第i個（1in）結點ai的存儲地址為【 】。21. 在單鏈表中，刪除P 指針所指向的結點的后繼（S指針指向的結點）的操作是【 】；free(【 】)。22. 以下為順序表的插入運算，分析算法，請在空白處填上正確的語句。void insert_seqlist(seqlist *L，datatype x，int i) /*將x插入到順序表L的位序為i的位置*/ 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. 以下為順序表的刪除運算，分析算法，請在空白處填上正確的語句。 void delete_sqlist(sqlist *L,int i) /*刪除順序表L中的第i-1個位置上的結點*/ if(i<1)|(i>L->last)error(“非法位置”)； for(j=i+1;j=L->last;j+)【 】; L->last=L->last-1;24. 下列有關線性表的敘述中，正確的是（ ）。(A)一個線性表是n個數(shù)據(jù)元素的有限序列 (

7、B)線性表中任何一個元素有且僅有一個直接前驅(C)線性表中任何一個元素有且僅有一個直接后繼(D)以上說法都不正確25. 順序表是線性表的（ ）。 (A)鏈式存儲結構 (B)順序存儲結構 (C) 索引存儲結構 (D) 散列存儲結構26. 從一個長度為n的順序表中刪除第i個元素(1in)時,需向前移動（ ）個元素。(A)n-i(B)n-i+1(C)n-i-1(D)i27. 一個長度為n的順序表中第i個位置上插入新元素(1in+1)時,需向后移動（ ）個元素。(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)隊列30. 單鏈表的一個存儲結點包含（ ）。(A)數(shù)據(jù)域或指針域(B)指針域或鏈域 (C)指針域和鏈域 (D)數(shù)據(jù)域和鏈域31. 單鏈表中，增加頭結點的目的是為了（ ）。(A)使單鏈表至少有一個結點 (B) 標示表結點中首結點的位置(C)方便運算的實現(xiàn) (D)說明單鏈表是線性表的鏈式存儲

9、實現(xiàn)32. 對于單鏈表表示法，以下說法錯誤的是（ ）。(A)指向鏈表的第一個結點的指針，稱為頭指針 (B)單鏈表的每一個結點都被一個指針所指(C)終端結點的指針域就為NULL (D)尾指針變量具標識單鏈表的作用，故常用尾指針變量來命名單鏈表33. 有一個含頭結點的單鏈表，頭指針為head，則判斷其是否為空的條件是（ ）。(A) head = = NULL (B) head->next = = NULL (C) head->next = = head (D) head != NULL34. 在帶頭結點的非空單鏈表H中，指針p指向某的結點，求p結點的前驅結點指針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. 在帶頭結點的單鏈表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. 假設指針p指向單鏈表中的某一結點,s為某結點指針，則在p指針后面插入結點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. 假設指針p指向單鏈表中的某一結點,s為某結點指針，則在p指針前面插入結點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的結點，實現(xiàn)“刪除x的后繼”的語句是（ ）。(A)p=p-next; (

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

14、上也是相鄰的。( ) 44. 在線性表的鏈式存儲結構中，邏輯上相鄰的數(shù)據(jù)元素在物理位置上也是相鄰的。( ) 45. 只要內存足夠大，采用鏈式存儲結構的線性表長度不受限制。( ) 三、 棧和隊列46. 僅允許在表的一端進行插入與刪除操作的線性表稱作【 】，允許在表的一端進行插入，另一端進行刪除操作的線性表稱作【 】。47. 棧稱為【 】線性表。隊稱為【 】線性表。48. 隊列的操作是按【 】的原則進行的。49. 棧的運算特點是【 】。請將用C語言的順序棧的定義補充完整：typedef struct 【 】； 【 】；seqstack； 50. 以下運算實現(xiàn)在順序棧上的進棧，請在空白處用適當?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. 隊列的操作是按【 】原則進行的。循環(huán)隊列Q分配Maxsize個存儲單元，隊頭指針為front，隊尾指針為rear，采用少用一個空間的方法處理，判斷隊列滿的條件是【 】。52. 循環(huán)隊列是隊列的【 】存儲結構。53. 循環(huán)隊列Q分配Maxsize個存儲單

16、元，隊頭指針為front，隊尾指針為rear，采用少用一個空間的方法處理，判斷隊列滿的條件是【 】。54. 以下順序棧定義及出棧運算實現(xiàn)，請在空白處用適當語句填充。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)先進先出 (B)后進先出 (C)棧頂插入 (D) 棧頂刪除56. 棧的兩種常用

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

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

19、)%maxsize=rear                  (D)rear=0 63. 循環(huán)隊列的隊滿條件為（ ）。(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ù)組datam作為循環(huán)隊列SQ的存儲空間，front為頭指針，rear為尾指針，執(zhí)行

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

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

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

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

24、，則第五個元素的地址是_。(A)110 (B)108 (C)100 (D)12085. 為了節(jié)省存儲空間，將n階對稱矩陣A(下標從1開始)中包括主對角線元素在內的下三角部分的所有元素按照行序為主序方式存放在一維數(shù)組B1:n(n+1)/2中，對任意下三角部分的元素aij(ij)在數(shù)組B的下標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. 稀疏矩陣一般的壓縮存儲有兩種，即（ ）。 (A) 二維數(shù)組和三維數(shù)組 (B) 三元組表和哈希表 (C) 三元組表和十字鏈表 (D)哈希表和十字鏈表87. 基于三元組的稀疏矩

25、陣，對每個非零元素aij,可以用一個（ ）唯一確定。(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. 對稱矩陣的壓縮存儲是指對矩陣中的值相同的元素只分配一個存儲空間。( ) 91. 對稱矩陣的壓縮存儲是指對矩陣中的規(guī)律元素只分配一個存儲空間。( ) 92. N階下三角矩陣壓縮存儲需要n*(n+1)/2個存儲空間。( ) 93. 三元組表是稀疏矩陣的順序存儲結構

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

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

28、； BiTree； void Inorder(BiTree root ) if ( root != NULL ) 【 】；【 】； 【 】； 105. 請對給定的二叉樹的存儲結構，將二叉樹的先序遍歷輸出結點遞歸算法補充完整：typedef struct node char data; /*元素為字符型*/struct node * Lchild,*Rchild; BiTree; void preorder(BiTree root ) if ( root != NULL ) 【 】;【 】; 【 】; 106. 以下程序段采用先根遍歷方法求二叉樹的葉子數(shù)，請在橫線處填充適當?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. 哈夫曼樹是帶權路徑長度【 】的樹，通常權值較大的結點離根【 】。108. 有m個葉子結點的哈夫曼樹，其結點總數(shù)為【 】。109. 用5個權值3, 2, 4, 5, 1構造的哈夫曼樹的帶權路徑長度是【 】 。110. 按照二叉樹的定義，具有3個結點的二叉樹有_種形態(tài)

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

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

32、的結點的雙親結點的編號是（ ）。 (A)23 (B) 24 (C) 25 (D)26118. 對二叉樹從1開始編號，要求每個結點的編號大于其左右孩子的編號，同一個結點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用（ ）方法實現(xiàn)編號。(A) 前序遍歷 (B) 中序遍歷 (C) 后序遍歷 (D) 從根開始進行層次遍歷FEDBAC圖119. 一棵二叉樹有n個結點，要按某順序對該二叉樹中的結點編號，（號碼為1-n），編號須具有如下性質：二叉樹中任一結點V，其編號等于其左子樹中結點的最大編號加1。而其右子樹中結點的最小編號等于V的編號加1。試問應按（）遍歷順序編號。(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個葉子結點的哈夫曼樹中，其結點總數(shù)為（ ）。(A)不確定 (B)2n (C)2n+1 (D) 2n-1 124. 哈夫曼樹的帶權路徑長度是（ ）。 (A) 所有結點權值之和 (B) 所有葉結點帶權路徑長度之和(C) 權結點的值 (D) 除根以外所有結點權值之和125. 下列說法正確的是（ ）。 (A) 樹的先根遍歷序列與其對應的二叉樹的先根遍歷序列相同(B) 樹的先根遍歷序列與其對應的二叉樹的后根遍歷序列相同(C) 樹的后根遍歷序列與其對應的二叉樹的先根遍歷序列相同(D) 樹的后根遍歷序列與其對應的二叉樹的后根遍歷序列相同126. 對于一棵任意二叉樹，若葉

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

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

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

38、n個頂點的無向完全圖的邊數(shù)為badcef圖(A) n(n+1)/2 (B) n(n-1)/2 (C) n(n-1) (D) n(n+1)150. 任何一個帶權的無向連通圖的最小生成樹(A)只有一棵 (B)有一棵或多棵 (C)一定有多棵 (D) 可能不存在151. 已知一個有向圖，則從頂點a出發(fā)進行深度優(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. 對下圖1所示的帶權有向圖，從頂點1到5 的最短路徑為（ ）。(A)1,4,5 (B)1,2,3,551234圖(C)1,4,3,5 (

39、D)1,2,4,3,5153. 已給圖，哪一項是該圖的拓撲排序？ (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個頂點和n條邊組成，使用鄰接表進行存儲，則該鄰接表由m個頭結點和n個表結點組成。( ) 155. 用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結點個數(shù)有關，而與圖的邊數(shù)無關。( ) 156. 有n個結點的無向完全圖有n*(n-1)/2條邊。( ) 157. 有n個結點的有向完全圖有n*(n-1)/2條邊。( ) 158. 某無向圖由m個頂點和n條邊組成，使用鄰接表進行存儲，則

40、該鄰接表由m個頭結點和n個表結點組成。( ) 159. 有向圖中所有頂點的入度之和等于所有頂點的出度之和。( ) 160. 普里姆算法是采用“加邊法”構造最小生成樹的。( ) 161. AOE 網(wǎng)是一種帶權的無環(huán)連通圖。( ) 162. AOE 網(wǎng)是一種帶權的有向無環(huán)圖。( ) 163. AOE網(wǎng)所表示的工程至少所需要的時間等于從源點到匯點的最長路徑長度。( ) 164. AOE網(wǎng)來表示工程計劃時，從源點到匯點的最短路徑表示了關鍵路徑。( ) 165. AOV網(wǎng)的拓撲序列是唯一的。( ) 166. 帶權連通圖的最小生成樹的權值之和是它的生成樹的權值之和中最小的。( ) 167. 帶權連通圖的最

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

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

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

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. 以下簡單選擇排序算法，請將算法補充完整: 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. 以下是直接選擇排序的算法。請分析算法，并在橫線上填充適當?shù)恼Z句。 void select(seqlist r,int n) for(i=1;i<=【 】;i+)/*每次循環(huán)，選擇出一個最小鍵值*/ 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. 以下為直接插入排序的算法。請分析算法，

46、并在_上填充適當?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個記錄插入到前i-1個已排好序的記錄中。請將如下的直接插入排序算法補充完整：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. 請將如下的折半查找算法補充完整：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. 如下算法是折半查找算法，請將算法補充完整：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. 如下算法是設置監(jiān)視哨的順序查找法，請將算法補充完整: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