華中師范大學(xué)網(wǎng)絡(luò)學(xué)院數(shù)據(jù)結(jié)構(gòu)試題庫及答案

《華中師范大學(xué)網(wǎng)絡(luò)學(xué)院數(shù)據(jù)結(jié)構(gòu)試題庫及答案》由會員分享，可在線閱讀，更多相關(guān)《華中師范大學(xué)網(wǎng)絡(luò)學(xué)院數(shù)據(jù)結(jié)構(gòu)試題庫及答案（52頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、華中師范大學(xué)網(wǎng)絡(luò)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》試題庫及答案 一、選擇題 1 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。 A． 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) ?? ?? ?? B． 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C． 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D． 內(nèi)部結(jié)構(gòu)和非內(nèi)部結(jié)構(gòu) 2． 算法分析的目的是（ ??）； Ａ. 找出數(shù)據(jù)結(jié)構(gòu)的合理性 ?? ?? B. 研究算法中的輸入和輸出的關(guān)系 C. 分析算法的效率以求改進 ?? ??D. 分析算法的易懂性和文檔性 3. 算法分析的兩個主要方面是（ ?）。 A. 空間復(fù)雜度和時間復(fù)雜度 ?? ??B. 正確性和簡單性 ?? C．可讀性和文檔性 ?? ?? ?

2、? ?? ?? ??D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 4．一個順序表（即順序存儲的線性表）第一個元素的存儲地址是100，每個元素的長度為2， 則第5個元素的地址是（ ）。 A． 100 B． 108 C． 100 D． 120 5．在一個長度為n 的順序表中，向第i個元素（1≤ i≤ n＋１）之前插入一個新元素時， 需要向后移動（ ）個元素。 A.n-i ?? ?? ?? ?? B.n-i-1 ?? ?? ?? C.n-i+1 ?? ?? ?? ??D.i 6．從一個長度為n 的順序表中刪除第i個元素（1≤ i≤ n＋１）時，需要向前移動（ ） 個元素。

3、A.n-i ?? ?? ?? ?? B.n-i-1 ?? ?? ?? C.n-i-1 ?? ?? ?? ??D.i 7．若長度為n的線性表采用順序存儲結(jié)構(gòu)，在表的第i個位置插入一個元素的算法的時間 復(fù)雜度是（ ?。? 　Ａ.O(n) ?? ?? ?? ??B.O(n*n) ?? ?? ?? ?? C.O(nlog2n) ?? ?? ?? ??D.O(log2n) 8．線性表的存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu) A． 隨機存取 B． 順序存取 C． 索引存取 D． HASH存取 9. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。 A． 隨機存取 B． 順序存取 C． 索引

4、存取 D． HASH存取 10．若線性表采用順序存儲結(jié)構(gòu)，每個元素占用4個存儲單元，第一個元素的存儲地址為100,則第12個元素的存儲地址是（ ） ?? A．112 ?? ?? ?? ?? B.144 ?? ?? ?? ?? ?? C.148 ?? ?? ?? ?? ?? D.412 11．若頻繁地對線性表進行插入和刪除操作，該線性表應(yīng)該采用（ ? ?）存儲結(jié)構(gòu)。 ?? A．散列 ?? ?? ?? ??B.順序 ?? ?? ?? ?? ??C.鏈?zhǔn)??? ?? ?? ?? ??D.任意 12．線性表若采用鏈表存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（ ）。 A． 必須是

5、連續(xù)的 B． 部分地址必須是連續(xù)的 C． 一定是不邊疆的 D． 連續(xù)不連續(xù)都可以 13．在非空線性鏈表中，在由p所指的鏈結(jié)點后面插入一個由q所指的鏈結(jié)點的過程是依次 執(zhí)行（ ） A．q->next=p; ?? p->next=q; B．q->next=p->next; p->next=q; C．q->next=p->next; p=q; D．p->next=q; q->next=p; 14．若刪除非空線性鏈表中由p所指鏈結(jié)點的直接后繼結(jié)點的過程是依次執(zhí)行( ) A．r=p->next; p->next=r; ?? ?? call RET(r)

6、 B．r=p->next; p->next=r->next; call RET(r) C．r=p->next; p->next=r->next; call RET(p) D．p->next=p->next->next; ?? call RET(p) 15．刪除一個雙鏈表中結(jié)點p(非頭結(jié)點和尾結(jié)點)的操作是( ). ?? ??A. p->left->right=p->left;p->right->left=p->right ?? ??B. p->left->right=p->right;p->right->left=p->ieft ?? ??C. p->left

7、=NULL;p->right=NULL ?? ??D. p->right->left=p;p->left->right=p 16．在一個雙鏈表中結(jié)點p之后插入一個結(jié)點s的操作是( )。 ?? ??A. s->right=p;s->left=p->right;p->right->left=s;p->right=s ?? ??B. s->right=p->right;p->right->left=s;s->right=p;p->left=s ?? ??C. s->right=p->right;s->left=p;p->left->left=s;p->right=s ?? ??D.

8、 s->right=p;p->left->left=s;p->right=s;s->right=p->right 17． 非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足（ ）。 A.p->next=NULL; ?? ?? B.p=NULL; C.p->next=head; ?? ?? ??D.p=head; 18． 在循環(huán)雙鏈表的p所指結(jié)點之后插入s的操作是（ ）。 A.p->right=s;s->left=p;p->right->left=s;s->rigth=p->right; B.p->right=s;p->right->left=s;s->left=p;s-

9、>right=p->right; C.s->left=p;s->right=p->right;p->right->left=s; D.s->left=p; s->right=p->right; p->right->left=s; p->right=s; 19．設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為(data,link)．已知指針q所指結(jié)點是指針p所指結(jié)點的直接前驅(qū)，若在*q與*p之間插入結(jié)點*s，則應(yīng)執(zhí)行下列哪一個操作? ( ) ?? ??A. s->link=p->link;p->link=s; B. q->link=s;s->link=p; ?? ??C. p->link=s->

10、link;s->link=p; D . p->link=s;s->link=q; 20． 設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為(data,link).已知指針p所指結(jié)點不是尾結(jié)點,若在*p之后插入結(jié)點*s,則應(yīng)執(zhí)行下列哪一個操作?( ) ?? ??A. s->link＝p; ??p->link=s; B. s->link=P->link; ??P->link=s; ?? ??C. s->link＝p->link; ??p=s; D. p->link=s; ??s->link=p; 21．??設(shè)單鏈表中結(jié)點結(jié)構(gòu)為（data,link）.若想摘除

11、結(jié)點*p的直接后繼,則應(yīng)執(zhí)行下列哪個操作? ( ) A. p->link=p->link-.link; B. p=p->link=p->link->link; C. p->link=p->link; D. p=p->link->link; 22．設(shè)單循環(huán)鏈表中結(jié)點的結(jié)構(gòu)為(date，link)且rear是指向非空的帶表頭結(jié)點的單循環(huán)鏈表的尾結(jié)點指針。若想刪除鏈表的第一個結(jié)點,則應(yīng)執(zhí)行下列哪一個操作?( ) A. s=rear;rear=rear->link;delete s; B. rear=rear->link;delete rear; C.

12、rear=rear->link->link;delete rear; D. s=rear->link->link;rear->link->link=s->link;delete s; 23．?設(shè)雙向循環(huán)鏈表中結(jié)點的結(jié)構(gòu)為(data，1Link，rLink)，且不帶裹頭結(jié)點．若想在指針p所指結(jié)點之后插入指針s所指結(jié)點，則應(yīng)執(zhí)行下列哪一個操作? ( ) ?? ??A. p->rLink＝s; s->1Link＝p; p->rLink一-1Link＝s;s->rLink=p->rLink; ?? ??B. p->rLink＝s;p->rLink->1Link＝s;s->1Link

13、＝p; s->rLink＝P->rLink， ?? ??C. s->1Link＝P;s->rLink＝p->rlink; P->rLink=s;p->rlink->lLink=s; ?? ??D. s->1Link＝P;s->rLink＝p->rLink;P->rLink->1Link＝s;p->rLink＝s; 24．?dāng)?shù)組通常具有的兩種基本操作是（ ）。 ?? ??A．建立與刪除 ?? ??B．索引和修改 ?? ??C．查找和修改 ?? ??D．查找與索引 25．二維數(shù)組M的成員是6個字符(每個字符占一個存儲單元)組成的串，行下標(biāo)i的范圍從 0到8，列下標(biāo)j的范圍從1

14、到10，則存放M至少需要（ ）個字節(jié) ?? ??A．90 ?? ??B．180 ?? ??C．240 ?? ??D．540 ?26．二維數(shù)組M的元素是4個字符(每個字符占一個存儲單元)組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5,M按行存儲時元素M[3Ⅱ5]的起始地址與M按列存儲時元素（ ）的起始地址相同。 ?? ??A．M[2][4] ?? ??B．M13][4] ?? ??C．M[3][5] ??D．M14][4] 27．?dāng)?shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從 首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)

15、是（ ）。 ?? ??A．80 ?? ??B．100 ?? ??C．240 ?? ??D．270 28．?dāng)?shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為（ ）。 ?? ??A．SA+141 ?? ??B．SA+144 ?? ??C．SA+222 ?? ??D．SA+225 29．?dāng)?shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從 首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時，元素A[5]18]的起始地址為（ ）。 ?? ??A

16、．SA+141 ?? ??B．SA+180 ?? ??C．SA+222 ?? ??D．SA+225 30．下面的說法中，不正確的是（ ）。 ?? ??A．?dāng)?shù)組是一種線性表結(jié)構(gòu) ?? ??B．?dāng)?shù)組是一種定長的線性表結(jié)構(gòu)， ?? ??C．除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等 D．?dāng)?shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操作 31．設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分按行序存放在一維數(shù)組B[1..n(n-1)／2]中，對任一下三角部分元素ai,j(i)，在一組數(shù)組B的下標(biāo)位置k的值是（ ）。 ?? ??A．i(

17、i-1)／2+j-1 ?? ??B．i(i-1)／2+j ?? ??C．i(i+1)／2+j-1 ?? ??D．i(i+1)／2+i 32．下面的說法中，不正確的是（ ）。 ???? A．只須存放對稱矩陣中包括主對角線元素在內(nèi)的下(或上)三角部分的元素即可 ?? ??B．只須存放對角矩陣中的非零元素即可 ?? ??C．稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲 D．稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲 33．對一些特殊矩陣采用壓縮存儲的目的主要是為了（ ）。 ?? ??A．表達變得簡單 ?? ??B．對矩陣元素的存取變

18、得簡單 ?? ??C．去掉矩陣中的多余元素 ?? ??D．減少不必要的存儲空間的開銷 34．若將n階對稱矩陣A按照行序為主序方式將包括主對角線元素在內(nèi)的下三角形的所有元素依次存放在一個一維數(shù)組B中，則該對稱矩陣在B中占用了( )個數(shù)組元素。 ?? ?? ??A．n/2 ?? ?? B．n*(n-1) C．n*(n+1)／2 ?? ??D．n*(n-1) 35．若將對稱矩陣A按照行序為主序方式將包括主對角線元素在內(nèi)的下三角形的所有元素依次存放在一個一維數(shù)組B中，那么，A中某元素ai(i<0)在B中的位置是( )。 ?? ??A．(i*(i-1))／2+j ?? ?? ?

19、? ?? ?? ?? ?? ?? ?? ??B．(i*(i-1))／2-j ?? ??C．(j*(j-1))／2+i ?? ?? ?? ?? ?? ?? ?? ?? ?? ??D．(j*(j-1))/ 2-i 36．稀疏矩陣一般的壓縮存儲方法有兩種，即 ( )。 ?? ??A．二維數(shù)組和三維數(shù)組 ?? ??B．三元組和散列 ?? ??C.三元組和十字鏈表 ?? ?? ?? D．散列和十字鏈表 37. 串是一種特殊的線性表，其特殊性體現(xiàn)在( )。 ?? ??A．可以順序存儲 ?? ??B．?dāng)?shù)據(jù)元素是一個字符 ?? ??c．可以鏈接存儲 ?? ?? D．?dāng)?shù)據(jù)元素可以是多

20、個字符 38. 串是( )。 ?? ??A．不少于一個字母的序列 ?? ??B．任意個字母的序列 ?? ??C．不少于一個字符的序列 ?? ??D．任意個字符的序列 39. 串的長度是( )。 ?? ??A．串中不同字母的個數(shù) ?? ??B．串中不同字符的個數(shù) ?? ??c．串中所含字符的個數(shù)，且大于0 ?? ??D．串中所含字符的個數(shù) 40.設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作( )。 ?? ??A．連接 ?? ??B．模式匹配 ?? ??C．求子串 ?? ??D．求串長 41.設(shè)串s="ABUBG",len(s)返回串s的長度，則le

21、n(s)是( )。 ?? ??A．2 ?? ??B．4 ?? ??C．5 ?? ??D．6 42.設(shè)串s="ABCDEFG",subs(s，U)返回串s的從序號i的字符開始的j個字符組成的子串， 則 subs(s,3,3)的結(jié)果串是( )。 ?? ??A．ABC ?? ??B．CDE ?? ??C．DEF ?? ??D．EFG 43.設(shè)串sI="ABCDEFG",s2="PQRST",函數(shù)con(x,y)返回x和y串的連接串,subs(s，山)返回串s的從序號i的字符開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,1en(s2))，su

22、bs(sl,len(s2)，2))的結(jié)果串是( )。 ?? ??A．BCDEF ?? ??B．BCDEFG ?? ??C．BCPQRST ?? ??n。BCDEFEF 44.下列關(guān)于串的敘述中，正確的是( )。 ?? ??A．串長度是指串中不同字符的個數(shù) ?? ??B．串是n個字母的有限序列(nj0) ?? ??c．如果兩個串含有相同的字符，則它們相等 45． ??棧和隊列的共同點是（ ）。 ?? ??A．都是先進后出 ?? ?? ??B．都是先進先出 ?? ??C．只允許在端點處插入和刪除元素 ?? ??D．沒有共同點 ?46． ??判定一個棧ST

23、(最多元素為m0)為空的條件是( ??)。 ?? ??A．ST—>t!=0 ?? ?? B．ST—>t= =0 ?? ??C．ST—>t!=m0 ?? ??D．ST—>t= =m0 47．判定一個棧ST(最多元素為m0)為棧滿的條件是( ? ?)。 ?? ??A．ST—>top!=0 ?? ?? ?? ??B．ST—>top= =0 ?? ??C．ST—>top!=m0 ?? ?? ?? D．ST—>top= =m0 48． ??一個棧的人棧序列是a，b，c，d，e，則棧的不可能的輸出序列是( ?)。 ?? ??A．edcba ?? ??B．decba ?? ??C．d

24、ceab ?? ??D．a(chǎn)bcde 49． ??一個棧的人棧序列是l，2，3，4，則棧的可能的輸出序列是( ??)。 ?? ??A．1，4，2，3 ?? ??B．2，1，4，3 ?? ??C。4，2，1，3 ?? ??D．4，2，3，l 50．若己知一個棧的人棧序列是1，2，3，…,n，其輸出序列為p1,p2,p3, …,pn，若p1則pi為（ ） A．i ?? ??B．n=i ?? ??C．n-i+1 ?? ??D．不確定 51. 若堆棧采用順序存儲結(jié)構(gòu)，正常情況下，往堆棧中插入一個元素，棧頂指針top的變化是（ ）。 A. 不變 B.top 0 C.to

25、p top-1 D.top top+1 52．向一個棧頂指針為HS的鏈棧中插入—個s所指結(jié)點時，則執(zhí)行( ) ?? ??A．HS->next=S； ?? ?? ?? ?? ?? ?? B．S->next=HS->next；HS->next=S； ?? ??C．S->next=HS；HS=S； ?? ?? ?? D．S->next=HS；HS=HS->next； 53．從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，則執(zhí)行( )。 ?? ??A．X=HS；HS=HS->next； ?? ?? ?? ?? ?? ?? ?B．X=HS->d

26、ata； C．HS=HS->next；K=HS->data； ?? ?? ?? ??D．x=HS->data；HS=HS->next 54．中綴表達式A-(B+C／D)*E的后綴形式是( )。 ?? ??A．ABC+D／*E- ?? ??B．ABCD／+E*- C．AB-C+D／E* ?? ??D．ABC-+D/E* 55. 若堆棧采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，棧頂指針為top，向堆棧插入一個數(shù)據(jù)信息為item的新元素的過程式依次執(zhí)行：call GETNODE(p),data(p) item, ( ),top p. A. p top B.

27、top p C.link(p) top D.link(top) p 56．若某堆棧的輸入序列為1，2，3，…，n-1，n，輸出序列的第1個元素為n，則第i個輸出元素為( )。 ?? ??A. n-i+l ?? ??B．n-i ?? ??C．i ?? ??D．哪個元素?zé)o所謂 57． 一個隊列的人列序列是1，2，3，4，則隊列的輸出序列是( ?)。 A．4，3，2，1 ?? ??B．1，2，3，4 ?? ??C。1，4，3，2 ?? ??D．3，2，4，l 58． 判定一個隊列QU(最多元素為m0)為空的條件是( ??)。 ?? ??A

28、．QU—>rear-QU—>front= =m0 ?? ??B．QU—>rear—QU—>front—1= =m0 ?? ??C．QU—>front= =QU—>rear ?? ??D．QU—>front= =QU—>rear+l 59．判定一個隊列QU(最多元素為m0)為滿隊列的條件是( ?)。 ?? A．QU->rear-QU->front==mO ?? ??B．QU->rear-QU->front-1==m0 ?? ??C．QU->front==QU->rear ?? ?? ?? D．QU->front==QU->rear+l 60．判定一個循環(huán)隊列QU(最多元素為m0

29、)為空的條件是( )。 ?? ??A．QU->front==QU->rear ?? ?? ?? ?? ?? B．QU->front!=QU->rear ?? ??C．QU->front=(QU->rear+1)％m0 ?? ??D．QU->front!=(QU->rear+1)％m0 61．判定一個循環(huán)隊列QU(最多元素為m0)為滿隊列的條件是( ) ?? ??A．QU->front==QU->rear ?? ?? ?? ?? ?? B．QU->front!=QU->rear ?? ??C．QU->front==(QU->rear+1)％m0 ?? D．QU->fron

30、t!=(QU->rear+1)％m0 62．表達式a*(b+c)-d的中綴表達式是( ) ?? ??A. abcd*+- ?? ?? ??B．a(chǎn)bc+*d C．a(chǎn)bc*+d- ?? ?? ??D．-+*abcd 63．在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個( ) 結(jié)構(gòu)。 A．線性表 ?? ??B．?dāng)?shù)組 ?? ??C．堆棧 ?? ??D．隊列 64．設(shè)計一個遞歸問題的非遞歸算法通常需要設(shè)置( )結(jié)構(gòu)。 A．線性表 ?? ?

31、?B．?dāng)?shù)組 ?? ??C．堆棧 ?? ??D．隊列 65. 隊列是限定在( ?)處進行插入操作的線性表 A. 任意端點 ?? ?? ?? ??B. 隊頭 C. 隊尾 ?? ?? ?? ?? ?? ?? D. 中間 66. 隊列是限定在( ?)處進行刪除操作的線性表 A. 任意端點 ?? ?? ?? ??B. 隊頭 C. 隊尾 ?? ?? ?? ?? ?? ?? D. 中間 67. 隊列中元素的個數(shù)是( ??) A. 不變的 ?? ?? ?? B. 可變的 C. 任意的 ?? D. 0 68．遞歸函數(shù)f(n)=f(n-

32、1)十n(n>1)的遞歸出口是( )。 ?A．f(1)=0 ?? ?? ??B．f(1)=1 C．f(0)=1 ?? ??D．f(n)=n 69． 廣義表中元素分為（ ） A．原子元素 ?? ?? ?? B.表元素 C．原子元素 ?? ?? ?? D.任意元素 70． 廣義表的長度是指（ ??） ??A，廣義表中元素的個數(shù) ?? ?? ??B。廣義表中原子元素的個數(shù) ??C．廣義表中表元素的個數(shù) ?? ??D．廣義表中括號嵌套的層數(shù) 71. 廣義表的深度是指 ??( ? ) ??A．廣義表中元素的個數(shù) ?? ?? ?? B．廣義表中原子元素甜

33、個數(shù) ??C.廣義表中表元素的個數(shù) ?? ?? ??D．廣義表中括號嵌套的層數(shù) 72．廣義表A：<<)，(a)，

34、根的層次為1) ( ) A．8 ?? ??B．7 ?? ??C．6 ?? ??D． 76. 在一棵樹中，若結(jié)點A有3個兄弟，結(jié)點B是結(jié)點A的雙親結(jié)點，那么結(jié)點B的度為( )。 ?? A．3 ?? ??B．1 ?? ??C．4 ?? ??D．5 77. 如圖17．2所示的t2是由有序樹t1轉(zhuǎn)換而來的二叉樹，那么樹t1有( )個葉結(jié)點。 A．4 ?? ??B．5 ?? ??C．6 ?? ??D．7 78. 在m叉樹中，度為0的結(jié)點稱為( )。 A．兄弟 ?? ??B．樹葉 ?? ??C．樹根 ?? ??D．分支結(jié)點 79．對二叉樹從1開始進行連續(xù)編號，要

35、求每個結(jié)點的編號大于其左右孩子的編號，同一個結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用( )次序的遍歷實現(xiàn)編號。 A．前序 ?? ??B．中序 ?? ?? C．后序 ?? ??D.從根開始的層次遍歷 80．某非空二叉樹的前序序列和后序序列正好相反，則二叉樹-定是( )的二叉樹。 A.空或只有一個結(jié)點 ?? ??B．高度等于其結(jié)點數(shù) C.任一結(jié)點無左孩子 ?? ??D．任一結(jié)點無右孩子 81．非空二叉樹在線索化后，仍不能有效求解的問題是( )。 A．前序線索二叉樹中求前序后繼 ?? ??B．中序線索二叉樹中求中序后繼 c.中序線索二叉樹中求

36、中序前趨 ?? ?? ??D．后序線索二叉樹中求后序后繼 82．對于一組結(jié)點，從空樹開始，把它們插入到二叉排序樹中，就建立了一棵二叉排序樹。這時，整個二叉排序樹的形狀取決于( )。 ?A．結(jié)點的輸入順序 ?? ??B．結(jié)點的存儲結(jié)構(gòu) C.結(jié)點的取值范圍 ?? ?? ??D．計算機的硬件 83．一棵左子樹不空的二叉樹在前序線索化后，其空鏈域數(shù)為( )。 ?? ??A．0 ?? ?? ?? ??B．1 ?? ?? ?? C．2 ?? ?? ?? D．不確定 84. 在具有n個結(jié)點的二叉樹(鏈表表示)中，值為非空的鏈域數(shù)為( )。 A．n-l ?? ??

37、??B．2n-1 ?? ??C．n+l ?? ?? D．2n+l 85．如圖所示二叉樹的中序遍歷序列是( )。 A．a(chǎn)bcdgef ?? ??B．dfebagc ?? ??C．dbaefcg ?? ??D．defbagc ?? ?? ?? 86．已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是( )。 ?? ??A．a(chǎn)cbed ?? ??B．decab ?? ??C．deabc ?? ??D．cedba 87．設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為( )。 A．2h

38、 ?? ?? ?? B．2h-1 ?? ??C．2h+l ?? ??D．h+l 88．在m叉樹中，度為0的結(jié)點稱為( )。 ?? ??A．兄弟 ?? ??B．樹葉 ?? ??C．樹根 ?? ??D．分支結(jié)點 89．有一棵二叉排序樹，對它進行( )的結(jié)果是按碼值大小從小到大排好的序列。 ?A．前序遍歷 ?? ??B．中序遍歷 ?? ??c．后序遍歷 ?? ??D．水平遍歷 90．下列說法正確的是( )。 A． 二叉樹中任何一個結(jié)點的度都為2 B． 二叉樹的度為2 C． ??任何二叉樹中至少有一個結(jié)點的度為2 D． 二叉樹中結(jié)點的度可以小于2 91．在

39、二叉樹的前序遍歷、中序遍歷和后序遍歷算法中，所有葉子結(jié)點的先后順序( )。 ?? ??A．都不相同 ?? ??B．完全相同 ?? ??C．前序遍歷和中序遍歷相同，而與后序遍歷不同 ?? ??D．前序遍歷和后序遍歷相同，而與中序遍歷不同 92．若一棵二叉樹其前序遍歷結(jié)果為ABCDEGFIA,中序遍歷結(jié)果為CBEDAFIGH,則其后序遍歷結(jié)果為( )。 A．ABCDEFGHI ?? B．CEDBIFHGA ??C．CEDBFIHGA ?? D．ECDBIFHGA 93．判斷線索二叉樹中t所指結(jié)點具有左子樹的條件是( )。 A．t!=NULL ??

40、 ?? ?? ?? ?? ?? B．t->left!=NULl C．t->ltag==0 ?? ?? ?? ?? ?? ??D．t->ltag==1 94．在線索二叉樹中，t所指結(jié)點沒有左子樹的充要條件是( )。 A．t->left==KTULL ?? ?? ?? ?? ?? ?? ?? ?? ?? ??B．t->ltag==1 C．t->ltag==1且t->left=NULL ?? ?? ?? ?? ?? D．以上都不對 95. 若由樹轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是（ ?） A 根點無右子樹的二叉樹 B 根結(jié)點無左子樹的二叉樹

41、C根結(jié)點可能有左二叉樹和右二叉樹 D 各結(jié)點只有一個兒子的二叉樹 96. 若由森林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是（ ?） A 根結(jié)點無右子樹的二叉 B 根結(jié)點無左子樹的二叉樹 C 根結(jié)點可能有左二叉樹和右二叉樹 D 各結(jié)點只有一個兒子的二叉樹 97. 判定樹中僅（ ?。┙Y(jié)點包含一個條件。 A　非終端　 B 終端 C 根 D 所有 98. 哈夫曼樹是訪問葉子結(jié)點的外部路徑長（ ）的二叉樹 ?。? 最短 Ｂ. 最長 Ｃ. 可變 Ｄ. 不定 99. 若TD(vi)表示具有n個頂點、e條邊的圖中頂點vi的度，那么，TD(v

42、i)與n和e者之間的關(guān)系為( )。 ?? ? n ?? ??A. e=nxTD(vi) ?? ??B．e=nx∑TD(vi) ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? i=1 ?? ?? ?? ?? ?? n ?? ?? ?? ?? ?? ?? ?? ??n ?? ??C. e=2x∑TD(vi) ??D．2xe=∑TD(v1) ?? ?? ?? ?? ??i=1 ?? ?? ?? ?? ?? ?? ??i=1 100．一個具有n個頂點的無向圖最多有( )條邊。 ?? A．nx(n-1)／2 ?? ??B．nx(

43、n-1) ?? C．nx(n+1)／2 ?? ??D．nxn 101．一個具有n個頂點的有向圖最多有( )條邊。 ?? A．nx(n-1)／2 ?? ??B．nx(n-1) ?? C．nx(n+1)／2 ?? ??D．nxn 102．具有6個頂點的無向圖至少應(yīng)該有( )條邊才能保證是一個連通圖。 ?? A．4 ?? ??B．5 ?? ??C．6 ?? ??D．7 103，一個有n個頂點的無向圖最多有( )條邊。 ?? A．n ?? ??B．n(n一1) ?? ??C．n(n一土)／2 ?? ??D．2n ?? ??' 104. 具有4個頂點的無向完全圖

44、有( )條邊。 A．6 ?? ??B．12 ?? ??C．16 ?? ??D．20 105. 具有6個頂點的無向圖至少應(yīng)有( )條邊才能確保是一個連通圖。 A．5 ?? ??B．6 ?? ??C．7 ?? ??D。8 106.以下敘述中正確的是( )。 A．圖G的某一最小生成樹的代價一定小于其他生成樹的代價 B．若圖G的最小生成樹不唯一，則G的邊數(shù)一定多于n-1，并且權(quán)值最小的邊有多條 C 任一AOE網(wǎng)中至少有一條關(guān)鍵路徑，且是從源點到匯點的路徑中最長的一條 D．有向圖用鄰接矩陣表示后，頂點i的入度等于鄰接矩陣中第主列的元素個數(shù) 107.

45、對于有n個頂點的無向圖，采用鄰接矩陣表示，如何判斷以下問題： 圖中有多少條邊？任意兩個頂點i和j之間是否有邊相連？任意一個頂點的度是多少3．一個無向圖采用鄰接矩陣存儲方法，其鄰接矩陣一定是一個( )。 ??A．對稱矩陣 ?? ??B．對角矩陣 ??C．三角矩陣 ?? ??D．稀疏矩陣 108. 對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是( )。 ??A．n ?? ??B．(n一1)*(n一土) ?? ??C．n一1 ?? ??D．n*n 109.?對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為( )。 ??

46、A．n ?? ??B．n+1 ?? ??C．n-l ?? ??D．n十e 110．圖的深度優(yōu)先搜索算法類似于二叉樹的( )。 ?? ??A．前序遍歷 ?? ??B．中序遍歷 ?? ??C．后序遍歷 ?? ??D．按層次遍歷 111．圖的廣度優(yōu)先搜索算法類似于二叉樹的( )。 ?? ??A．前序遍歷 ?? ??B．中序遍歷 ?? ??C．后序遍歷 ?? ??D．按層次遍歷 112．導(dǎo)致圖的遍歷序列不惟一的因素是( )。 ?? ??A．出發(fā)點的不同、遍歷方法的不同 ?? ??B．出發(fā)點的不同、存儲結(jié)構(gòu)的不同 ?? ??C．遍歷方法的不同、存儲結(jié)構(gòu)的不同

47、 ?? ??D．出發(fā)點的不同、存儲結(jié)構(gòu)的不同、遍歷方法的不同 113．已知帶權(quán)連通無向圖G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7}，E={(v1，??v2)l0，(v1，v3)2，(v3，v4)2，(v3，v6)11，(v2，v5)1，(v4，v5)4，(v4，v6)6，(v5,v7)7，(v6，v7)3}(注：頂點偶對右下角的數(shù)據(jù)為邊上的權(quán)值)，從源點v1到頂點v7的最短路徑上經(jīng)過的頂點序 列是( )。 ?? ??A. v1，v2，v5，v7 ?? ?? ?? ??B．v1，v3，v4，v6，v7 ?? ??C. V1，V3，V4，V5，V7 ?? ?

48、?D．V1，V2，V5，V4，V6，V7 114. 采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的( )。 A．先序遍歷 ?? ??B．中序遍歷 ?? ??C．后序遍歷 ?? ??D．按層遍歷 115. 采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的( )。 A．先序遍歷 ?? ??B．中序遍歷 ?? ??巳后序遍歷 ?? ??D；按層遍歷 ? 116．任何一個帶權(quán)無向連通圖的最小生成樹( )。 ?? ??A．是唯一的 ?? ?? ?? ??B．是不唯一的 C．有可能不惟一 ?? ??D．有可能不存在 117 ．帶權(quán)連通圖G=(V，E)，其

49、中V={v1，v2，v3，v4，v5},E={(v1，v2)7，(v1，v3)6 ,(v1 ?? v4)9，(v2，v3)8，(v2，v4)4，(v2，v5)4，(v3，v4)6，(v4，v5)2}(注：頂點偶對右下角的數(shù)據(jù)為邊上的權(quán)值)，G的最小生成樹的權(quán)值之和( )。 ?A．16 ?? ??B．17 ?? ??C．18 ?? ??D.19 118．判定一個有向圖中是否存在回路可以利用( )方法。 ?A. 求最小生成樹 ?? ??B．求最短路徑 ?C．拓?fù)渑判??? ?? ?? ??D．圖的遍歷 119. 任何一個無向連通圖的最小生成樹( )。 A．只

50、有一棵 ?? ??B．有一棵或多棵 ??C．一定有多棵 ?? ??D．可能不存在 120. 最小生成樹的構(gòu)造可使用（ ?）算法。 A. 普里姆算法 B. 克魯斯卡爾算法 C. 迪杰斯特拉算法 D. 哈夫曼算法 121. 任何一個帶權(quán)的無向連通圖的最小生成樹（ ） （A） 只有一棵 （B） 有一棵或多棵 （C） 一定有多棵 （D） 可能不存在 122. 含N個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過（ ?） A. 1 B. N/2 C. N-1 D. N 123．判定一個有向圖中是否存在回路除了利用拓?fù)渑判蚍椒ㄒ酝?，還可

51、以利用( )方法。 ?A. 圖的遍歷 ?? ??B．求最小生成樹 C．最短路徑 ?? ??D．求關(guān)鍵路徑 124. 在一個具有N個頂點的無向完全圖中，包含的邊的總數(shù)是（ ） （A） N（N-1）/2 （B） N（N-1） （C） N（N+1） （D） N（N+1）/2 125. 一個具有N個頂點的有向圖最多有（ ??）條邊 （A） N（N-1）/2 （B） N（N-1） （C） N（N+1） （D） N（N+1）/2 126．下面的說法中，不正確的是( )。 ??A．AOE網(wǎng)是一個帶權(quán)的有向圖 ??B．AOE網(wǎng)是一個帶權(quán)且無環(huán)路的有向

52、圖 ??C. AOE網(wǎng)是一個帶權(quán)且無環(huán)路的有向連通圖 D．正常情況下，AOE網(wǎng)中只有一個源點和一個終點 127. 有拓?fù)渑判虻膱D，一定是（ ?） A 有圈圖 B 圈圖任意圖 C 無向 D 強連通圖 128. 設(shè)圖G采用鄰接表存儲，則拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度為（ ?） A. O（n） B. O(n+e) C. O(n*n) D. O(n*e) 129. 判斷一個有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒?，還可以利用（ ??） A 求關(guān)鍵路徑的方法 B 求最短路徑的Dijkstra方法 C 廣度優(yōu)先遍歷方法 D 深度優(yōu)先遍歷方

53、法 130．AOE網(wǎng)中的關(guān)鍵路徑是該網(wǎng)中的( ). ?A．從源點到終點的最長路徑 ?B. 從源點到終點的最短路徑 C. 最長的回路 ?? ? ?D．最短的回路 131．帶權(quán)連通圖G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7，v8，v9，v10}，E={(v1，v2)5，(v1，v3)6，(v2，v5)3，(v3，v5)6，(v3，v4)3，(v4，v5)3，(v4，v7)1，(v4，v8)4,(v5，v6)4，(v5，v7)2，(v6，vl0)4，(v7，v9)5，(v8，v9)2，(v9，V10)2}(注：頂點偶對右下角的數(shù)據(jù)為邊上的權(quán)值)，G的關(guān)鍵

54、路徑的長度為( )。 ?? ??A．19 ?? ??B．20 ?? ??C．21 ?? ??D。22 132．下面的說法中，正確的是( )。 ?? ?? A.帶權(quán)連通圖的某最小生成樹的權(quán)值之和一定小于其它生成樹的權(quán)值之和 B.從源點到終點的最短路徑是唯一的 C.任意一個AOV網(wǎng)不一定存在拓?fù)湫蛄? D.任意一個AOV網(wǎng)中的關(guān)鍵路徑是唯一的 133. 排序是根據(jù)（ ? ??）的大小重新安排各元素的順序。 ?? A ??數(shù)組 ??B ??關(guān)鍵字 ?? C 元素 ?? D ?? 結(jié)點 134. 內(nèi)部排序是根據(jù)關(guān)鍵字的大小重新安排各（ ? ? ??

55、）的順序。 ?? A 關(guān)鍵字 ??B 數(shù)據(jù)項 ??C 文件 ??D ??數(shù)據(jù)元素 135. 穩(wěn)定的排序法是指在排序中，關(guān)鍵字值相等的不同記錄間的前后位置（ ?） ?? A ??保持不變 ??B ??保持相反 ??C ??不定 ??D 無關(guān) 136. 不穩(wěn)定的排序法是指在排序中，關(guān)鍵院子值相等的不同記錄間前后相對位置（ ?? ） ?? A 保持不變 ??B ??保持相反 ?? C不定 ?? D無關(guān) 137. 內(nèi)部排序是指在排序的整個過程中，全部數(shù)據(jù)都在計算機的（ ? ）中完成的排序。 ?? A內(nèi)存儲器 ?? B外存儲器 ?? C ??內(nèi)存儲器和外存儲器 ??

56、 D ??寄存器 138. 外部排序是指在排序的整個過程中，全部數(shù)據(jù)在計算機的（ ??）中完成的排序。 ?? A ??內(nèi)存儲器 ?? ??B ??外存儲器 ?? C ??內(nèi)存儲器和外存儲器 ?? D ??寄存器 139. 直接插入排序的方法是（ ?? ）的排序方法。 ?? A穩(wěn)定 ?? ?? B不穩(wěn)定 ?? C外部 ?? ??D選擇 140. 直接插入排序的方法是從第（ ?）個元素開始，插入前邊適當(dāng)位置的排序方法。 ?? A ??1 ?? B ??2 ?? C ?? 3 ?? D ??n 141. 冒泡排序的方法是（ ??）排序方法。 ?? A穩(wěn)定 ?

57、? B不穩(wěn)定 ??C外部 ?? D選擇 142. 用冒泡排序的方法對n個數(shù)據(jù)進行排序，第一趟共比較（ ?）對元素。 ?? A ?? 1 ?? ??B ??2 ?? C ??n-1 ?? D ??n 143. ?下列排序法中，( )可能會出現(xiàn)這樣的情況在最后一趟開始之前，所有元素都不在其最終位置上。 ?? ??A．堆排序 ????B．冒泡排序 ?? ??C．快速排序 ?? ??D. 插入排序 144. ??依次將待排序膨0中的元素和有序子序列合并為一個新的有序子序列的是( )。 A．插入排序 ?? ??。B．冒泡排序 ?? ??c快速排序 ?? ??

58、·D．堆排序 145.在參加排序的序列已經(jīng)基本按值有序的前提下，排序的效率最好的排序方法應(yīng)該是( )。 ?? ??A.插入排序法 ?? ?? B.選擇排序法 C.快速排序法 ?? ?? D.堆積排 146．在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是( )。 ?? ??A．希爾排序 ?? ??B．冒泡排序 ?? ??巳插入排序 ?? ??D．選擇排序 147．每趟排序都從序列的未排好序的序列中挑選一個值最小(或最大)的元素，然后將其與未排好序的序列的第一個元素交換位置。這種排序法稱為( )。 ?? ??A．插入排序法 ?? ??B．選擇排序法

59、 ?? ??C．謝爾排序法 ?? ??D．快速排序法 148．對數(shù)據(jù)元素序列（49，72，68，13，38，50，97，27）進行排序，前三趟排序結(jié)束時的結(jié)果依次為：第一趟：13，72，68，49，38，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72。該排序采用的方法是( )。 ?? ??A．插入排序法 ?? ??B．選擇排序法 ?? ??C．泡排序法 ?? ?? ??D．堆積排序法 149．對具有n個元素的任意序列采用選擇排序法進行排序，排序趟數(shù)為( )。 ?? ?? A．n-1 ?? ?

60、?B．n ?? ??C．n+l ?? ??D． ?? 150．下列排序方法中，排序的比較次數(shù)與序列的初始排列狀態(tài)無關(guān)的是( )。 ?? ??A．選擇排序法 ?? ??B．插人排序法 ?? ??C．泡排序法 ?? ?? ??D．快速排序法 151．快速排序在最好的情況下的時間復(fù)雜度是( )。 A．O(n) ?? ??B．0(nlog2n) ?? ??C．O(n2) ?? ??D．0(10g2n) 152.一組記錄的關(guān)鍵碼為(46,79,56,38,40,84)，則利用快速排序的方法，以第一個記錄為基得到的一次劃分結(jié)果為( )。 A．38，40，46，56，79

61、，84 ?? ??B．40，]8，46，79，56，84 C．40，38，46，56，79，84 ?? ??D．40，38，46，84，56，79 153.用某種排序方法對線性表(25,84；21,47,15,27,68,35,20)進行排序時，元素序列的變化情況如下： ?? ?? (1)25，84，21，47，15，27，68，35，20 ?? ?? (2)20，15，21，25，47，27，68，35，84 ?? ? ?? (3)15，20，21，25，35，27，47，68，84 ??(4)15，20，21，25，27，35，47，68，84 ?? ?? ??

62、 則所采用的排序方法是( )。 ??A．選擇排序 ?? ??B．希爾排序 ?? ??巳歸并排序 ?? ??D．快速排序 154．第i趟排序?qū)π蛄械那皀-i+1個元素做如下工作：從第一個元素開始，相鄰兩個元素比較，若前者大于后者，這兩個元素交換位置，否則，這兩個元素不交換位置。?這種排序法稱為( )。 ?? ??A．插入排序法 ?? ??B.選擇排序法 ?? ??C．泡排序法 ?? ?? ??D．堆積排序法 155．對具有n個元素的任意序列采用泡排序法進行排序，排序趟數(shù)為( )。 ??A．n-1 ?? ??B．n ?? ??C．[1，n] ?? ??D．[

63、1，n-1] 156．泡排序方法的排序趟數(shù)是一個區(qū)間范圍[1，n-1]，當(dāng)參加排序的序列( )時，要進行n-1趟排序。 ?? ??A．按照值的大小從小到大排列 ?? ??B．按照值的大小從大到小排列 ?? ??C．最小的元素處在序列的最后 ?? ??D．序列中元素的排序次序任意 157.一組記錄的排序碼為（25，，48，16，35，79，82，23，40，36，72），其中含有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結(jié)果為（ ）。 A. 16,25,35,48,23,40,79,82,36,72 B. 16,25,35,48,79,82,23

64、,36,40,72 C. 16,25, 48,35,79,82,23,36,40,72 D. 16,25,35,48,79, 23,36,40,72,82 158. 已知兩個有序表，若要將它們組合成一個新的有序表，最好的方法是（ ）。 A.希爾排序 B.二分插入排序 C. 歸并排序 D.冒泡排序 159．通過依次將序列中位置相鄰已經(jīng)按值有序的子序列兩兩合并為一個按值有序的序列的方式來達到排序目的的排序方法是（ ）。 A.冒泡排序 B. 希爾排序 C.堆排序 D.二路歸并排序 160．下述幾種內(nèi)排序方法中，要求輔助空間最大的方法是（ ）。 A

65、．希爾排序 B.快速排序 C.堆排序 D. 二路歸并排序 161. 一個長度為10的有序表，按照二分查找法對該表進行查找，在表內(nèi)各元素等概率的情況下，查找成功所需要的平均比較次數(shù)為（ ??） ?? A. 25/10 B. 27/10 C. 29/10 D. 31/10 162. 已知一個有序表為{12，15，21，30，31，35，40，45，55，67，99，131}，則采用二分查找值為 99的元素所需要進行（ ）比較 ??A. 1 B. 2 C. 3 D. 4 163. 下面查找方式中，可以對無序表進行查找的是（ ??） ??

66、 A. 順序查找 ?? B. 二分查找 ?? C. 二叉排序樹 ?? D. B-樹上的查找 164. 如果要求一個線性表適應(yīng)動態(tài)變化要求，又必須能盡快進行查找，則可以選擇采用（ ??）查找方法。 ??A. 分塊 B. 二分 C. 順序 D. 散列 165. 長度為n的線性表，若各個結(jié)點的查找的概率相同，則在查找成功的情況下，其平均查找長度為（ ??） ??A. n B. n(n+1)/2 C. (n-1)/2 D. (n+1)/2 166.順序查找法適合于存儲結(jié)構(gòu)是（ ）的線性表 A． 三列存儲 B. 順序存儲 C. 壓縮存儲 D. 索引存儲 167． 對線性表進行二分查找時，要求線性表必須 （ ）。 A. 以順序方式存儲 B. 以鏈接方式存儲 C. 以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序 D. 以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序 168．采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度是（ ）。 A. n B