2022年2022年數(shù)據(jù)結(jié)構(gòu)練習(xí)題

1、精選學(xué)習(xí)資料 - - - 歡迎下載數(shù)據(jù)結(jié)構(gòu)練習(xí)題習(xí)題 1緒論1.1 單項(xiàng)選擇題1. 數(shù)據(jù)結(jié)構(gòu)為一門討論非數(shù)值運(yùn)算的程序設(shè)計(jì)問題中、 數(shù)據(jù)元素的.數(shù)據(jù)信息在運(yùn)算機(jī)中的以及一組相關(guān)的運(yùn)算等的課程； a 操作對象運(yùn)算方法規(guī)律結(jié)構(gòu)數(shù)據(jù)映象 a 儲(chǔ)備結(jié)構(gòu)關(guān)系運(yùn)算算法2. 數(shù)據(jù)結(jié)構(gòu)dsdata struct可以被形式地定義為ds=（ d, r）,其中 d 為的有限集合, r 為 d上的有限集合； a 算法數(shù)據(jù)元素?cái)?shù)據(jù)操作數(shù)據(jù)對象 a 操作映象儲(chǔ)備關(guān)系3. 在數(shù)據(jù)結(jié)構(gòu)中,從規(guī)律上可以把數(shù)據(jù)結(jié)構(gòu)分成；a動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)線性結(jié)構(gòu)和非線性結(jié)構(gòu)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4. 算法分析的目的為,算法分析

2、的兩個(gè)主要方面為； a.找出數(shù)據(jù)結(jié)構(gòu)的合理性b.討論算法中的輸入和輸出的關(guān)系分析算法的效率以求改進(jìn)d.分析算法的易懂性和文檔性空間復(fù)雜性和時(shí)間復(fù)雜性b.正確性和簡明性c. a.c. 可讀性和文檔性d.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性5. 運(yùn)算機(jī)算法指的為,它必具備輸入.輸出和等五個(gè)特性；a.運(yùn)算方法b.排序方法c. 解決問題的有限運(yùn)算序列d.調(diào)度方法 a.可行性.可移植性和可擴(kuò)充性b.可行性.確定性和有窮性c.確定性.有窮性和穩(wěn)固性d.易讀性.穩(wěn)固性和安全性1.2 填空題（將正確的答案填在相應(yīng)的空中）1. 數(shù)據(jù)規(guī)律結(jié)構(gòu)包括.和三種類型,樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為；2. 在線性結(jié)構(gòu)中,第一個(gè)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn),其

3、余每個(gè)結(jié)點(diǎn)有且只有個(gè)前驅(qū)結(jié)點(diǎn)；最終一個(gè)結(jié)點(diǎn)后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有個(gè)后續(xù)結(jié)點(diǎn)；3. 在樹形結(jié)構(gòu)中,樹根結(jié)點(diǎn)沒有結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有個(gè)直接前驅(qū)結(jié)點(diǎn),葉子結(jié)點(diǎn)沒有結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的直接后續(xù)結(jié)點(diǎn)可以；4. 在圖形結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以；5. 線性結(jié)構(gòu)中元素之間存在關(guān)系,樹形結(jié)構(gòu)中元素之間存在關(guān)系,圖形結(jié)構(gòu)中元素之間存在關(guān)系；6.算法的五個(gè)重要特性為、 、_ 、 、 _ ；7. 分析下面算法（程序段）,給出最大語句頻度,該算法的時(shí)間復(fù)雜度為 ；for i=0;i<n;i+ for j=0;j<n; j+aij=0;8. 分析下面算法（程序段）,給出最大語

4、句頻度,該算法的時(shí)間復(fù)雜度為；for i=0;i<n;i+ for j=0; j<i; j+aij=0;9. 分析下面算法（程序段）,給出最大語句頻度,該算法的時(shí)間復(fù)雜度為；s=0;for i=0;i<n;i+ for j=0;j<n;j+for k=0;k<n;k+ s=s+bijk; sum=s;10. 分析下面算法（程序段）給出最大語句頻度,該算法的時(shí)間復(fù)雜度為 ；i=s=0;精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載while s<n i+;s+=i;/s=s+i11. 分析下面算法（程序段）給出最大語句頻度,該算法的時(shí)間復(fù)雜度為 ；i=1;wh

5、ile i<=n i=i*2;1.3 算法設(shè)計(jì)題1. 試寫一算法 、 自大到小依次輸出次序讀入的三個(gè)數(shù)x、y 和 z 的值 .2. 試寫一算法 、 求出 n 個(gè)數(shù)據(jù)中的最大值；寫出最大語句頻度,該算法的時(shí)間復(fù)雜度；習(xí)題答案1.11. c 、 a2. b、d3. c4. c、 a5. c、b1.21.線性結(jié)構(gòu).樹形結(jié)構(gòu).圖形結(jié)構(gòu),非線性結(jié)構(gòu)2. 沒有. 1.沒有. 13. 前驅(qū). 1.后續(xù).任意多個(gè)4. 任意多個(gè)5. 一對一.一對多.多對多6. 有窮性.確定性.可行性.輸入.輸出227. 最大語句頻度：n, 時(shí)間復(fù)雜度： . o n28. 最大語句頻度：n n+1/2, 時(shí)間復(fù)雜度：. o

6、 n9. 最大語句頻度：n3 , 時(shí)間復(fù)雜度： . o n3112210. 最大語句頻度：n, 時(shí)間復(fù)雜度：. o n11. 最大語句頻度：log 2n, 時(shí)間復(fù)雜度： . o log2n 習(xí)題 2線性表2.1 單項(xiàng)選擇題1. 一個(gè)向量（即一批地址連續(xù)的儲(chǔ)備單元）第一個(gè)元素的儲(chǔ)備地址為100,每個(gè)元素的長度為2,就第 5 個(gè)元素的地址為 ；a. 110b. 108c. 100d. 1202. 線性表的次序儲(chǔ)備結(jié)構(gòu)為一種_ 的儲(chǔ)備結(jié)構(gòu),而鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)為一種_ 的儲(chǔ)備結(jié)構(gòu)；a隨機(jī)存取b索引存取c 次序存取d 散列存取3. 線性表的規(guī)律次序與儲(chǔ)備次序總為一樣的,這種說法_ ；a. 正確b.不正確4.

7、 線性表如采納鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)時(shí),要求內(nèi)存中可用儲(chǔ)備單元的地址_ ；a. 必需為連續(xù)的b.部分地址必需為連續(xù)的c.肯定為不連續(xù)的d.連續(xù)或不連續(xù)都可以5. 在以下的表達(dá)中,正確選項(xiàng)_ ；a. 線性表的次序儲(chǔ)備結(jié)構(gòu)優(yōu)于鏈表儲(chǔ)備結(jié)構(gòu)b. 線性表的次序儲(chǔ)備結(jié)構(gòu)適用于頻繁插入/ 刪除數(shù)據(jù)元素的情形c. 線性表的鏈表儲(chǔ)備結(jié)構(gòu)適用于頻繁插入/ 刪除數(shù)據(jù)元素的情形d. 線性表的鏈表儲(chǔ)備結(jié)構(gòu)優(yōu)于次序儲(chǔ)備結(jié)構(gòu)6. 每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入.刪除和查找,這種說法_ ；a. 正確b.不正確7. 不帶頭結(jié)點(diǎn)的單鏈表head 為空的判定條件為 ；a. head= =nullb. head->next= =

8、nullc. head->next= =headd. head.=null精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載8. 帶頭結(jié)點(diǎn)的單鏈表head 為空的判定條件為 ；a. head= =nullb. head->next= =nullc. head->next= =headd. head.=null9. 非空的循環(huán)單鏈表head 的尾結(jié)點(diǎn)（由p 所指向）滿意 ；a. p->next= =nullb. p= =nullc. p->next= =headd. p= =head10. 在雙向循環(huán)鏈表的p 所指結(jié)點(diǎn)之后插入s 所指結(jié)點(diǎn)的操作為 ；a. p->r

9、ight=s; s->left=p; p->right->left=s; s->right=p->right;b. p->right=s; p->right->left=s; s->left=p; s->right=p->right;c. s->left=p;s->right=p->right;p->right=s; p->right->left=s;d. s->left=p;s->right=p->right;p->right->left=s; p->ri

10、ght=s;11. 在一個(gè)單鏈表中,已知q 所指結(jié)點(diǎn)為p 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),如在q 和 p 之間插入s 結(jié)點(diǎn),就執(zhí)行 ；a. s->next=p->next; p->next=s;b. p->next=s->next; s->next=p;b. q->next=s;s->next=p;c. p->next=s;s->next=q;12. 在一個(gè)單鏈表中,如p 所指結(jié)點(diǎn)不為最終結(jié)點(diǎn),在p 之后插入s 所指結(jié)點(diǎn),就執(zhí)行 ；a. s->next=p; p->next=s;b. s->next=p->next; p-

11、>next=s;c. s->next=p->next; p=s;c. p->next=s; s->next=p;13. 在一個(gè)單鏈表中,如刪除p 所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn),就執(zhí)行 ；a. p->next= p->next->next；b. p= p->next; p->next= p->next->next；c. p->next= p->next;d. p= p->next->next；14. 從一個(gè)具有n 個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x 結(jié)點(diǎn)時(shí),在查找勝利的情形下,需平均比較 個(gè)結(jié)點(diǎn)；a. nb. n/

12、2c. n-1/2d. n+1/215. 在一個(gè)具有n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍舊有序的時(shí)間復(fù)雜度為 ；2a. o1b. onc. o nd. o nlog2 n16. 給定有 n 個(gè)元素的向量,建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度為；2a. o1）b. onc. o nd. o n*log2n2.2 填空題（將正確的答案填在相應(yīng)的空中）精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載1. 單鏈表可以做 的鏈接儲(chǔ)備表示；2. 在雙鏈表中,每個(gè)結(jié)點(diǎn)有兩個(gè)指針域,一個(gè)指向 ,另一個(gè)指向；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載3. 在一個(gè)單鏈表中p 所指結(jié)點(diǎn)之前插入一個(gè)s 值為 e 所

13、指結(jié)點(diǎn)時(shí),可執(zhí)行如下操作： q=head;while q->next.=p q=q->next;s= new node;s->data=e;q->next=;/填空s->next=;/填空4. 在一個(gè)單鏈表中刪除p 所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí),應(yīng)執(zhí)行以下操作： q= p->next;p->next= _ ;/填空delete;/填空5. 在一個(gè)單鏈表中p 所指結(jié)點(diǎn)之后插入一個(gè)s 所指結(jié)點(diǎn)時(shí),應(yīng)執(zhí)行s->next= 和 p->next=的操作；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載6. 對于一個(gè)具有n 個(gè)結(jié)點(diǎn)的單鏈表,在已知p 所指結(jié)點(diǎn)后插

14、入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為；在給定值為x 的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為；2.3 算法設(shè)計(jì)題 :1. 設(shè)次序表va 中的數(shù)據(jù)元數(shù)遞增有序；試寫一算法,將x 插入到次序表的適當(dāng)位置上,以保持該表的有序性；status insert_sqlistsqlist &va、int xifva.length+1>maxsize return error; va.length+;fori=va.length-1;va.elemi>x&&i>=0;i- va.elemi+1=va.elemi;va.elemi+1=x; return ok;精品學(xué)習(xí)資料精選學(xué)習(xí)資

15、料 - - - 歡迎下載2. 試寫一算法,實(shí)現(xiàn)次序表的就地逆置,即利用原表的儲(chǔ)備空間將線性表（a1、 a 2、 . a n）逆置為 a n、 a n- 1、 .、 a 1 ；void reverseint a、 int sizeint i、j、tmp;fori=0、 j=size-1; i<j; i+、j-tmp=ai; ai=aj; aj=tmp;3. 已知線性表中的元素以值遞增有序排列,并以單鏈表作儲(chǔ)備結(jié)構(gòu)；試寫一算法,刪除表中全部大于x 且小于 y 的元素（如表中存在這樣的元素）同時(shí)釋放被刪除結(jié)點(diǎn)空間；void dellinklist l、elemtype a、elemtype b

16、p= l;q=p->next;whileq.=l && q->data<ap=q;q=q->next;whileq.=l && q->data<br=q;q=q->next; freer;ifp.=qp->next=q;4. 試寫一算法,實(shí)現(xiàn)單鏈表的就地逆置 要求在原鏈表上進(jìn)行 ； void conversenodeptr lnodeptr p、q;p=l->next; q=p->next;l->next=null;whilep/*對于當(dāng)前結(jié)點(diǎn)p,用頭插法將結(jié)點(diǎn)p 插入到頭結(jié)點(diǎn)之后*/p->

17、next=l->next;l->next=p;p=q;q=q->next;習(xí)題答案2.11. b2. a、 c3. b4. d5. c6. a7. a8. b9. c10. d11.b12.b13.a14.d15.b16.c2.21.線性結(jié)表2.前驅(qū)結(jié)點(diǎn).后繼結(jié)點(diǎn)3. s、 p4. q->next、 q精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載5. p->next、 s6.o 1 、 o n習(xí)題 3 棧和隊(duì)列3.1 單項(xiàng)選擇題1. 一個(gè)棧的入棧序列a,b, c , d, e,就棧的不行能的輸出序列為 ；a. edcbab. decbac. dceabd. ab

18、cde2. 如已知一個(gè)棧的入棧序列為1, 2, 3, n,其輸出序列為p1, p2,p3, pn,如 p1=n,就 pi為 ；a. ib. n=ic. n-i+1d.不確定3. 棧結(jié)構(gòu)通常采納的兩種儲(chǔ)備結(jié)構(gòu)為 ；a. 次序儲(chǔ)備結(jié)構(gòu)和鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)b. 散列方式和索引方式c. 鏈表儲(chǔ)備結(jié)構(gòu)和數(shù)組d. 線性儲(chǔ)備結(jié)構(gòu)和非線性儲(chǔ)備結(jié)構(gòu)4. 判定一個(gè)次序棧st（最多元素為m0）為空的條件為 ；a. top .=0b. top= =0c. top .=m0d. top= =m0-15. 判定一個(gè)次序棧st（最多元素為m0）為棧滿的條件為 ；a. top！ =0b. top= =0c. top！ =m0d.

19、top= =m0-16. 棧的特點(diǎn)為 ,隊(duì)列的特點(diǎn)為 ；a.先進(jìn)先出b.先進(jìn)后出7. 向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s 所指結(jié)點(diǎn)時(shí),就執(zhí)行 ； 不帶空的頭結(jié)點(diǎn)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;精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載8. 從一個(gè)棧頂指針為hs的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用x 儲(chǔ)存被刪結(jié)點(diǎn)的值,就執(zhí)行 a. x=hs; hs= hs next;b. x=hs data;c. hs= hs next; x=hs data;d. x

20、=hs data; hs= hs next;9. 一個(gè)隊(duì)列的數(shù)據(jù)入列序列為1, 2, 3, 4,就隊(duì)列的出隊(duì)時(shí)輸出序列為 ；a. 4, 3, 2,1b. 1,2, 3, 4c. 1, 4, 3,2d. 3, 2, 4,110. 判定一個(gè)循環(huán)隊(duì)列qu（最多元素為m0）為空的條件為 ；a. rear - front= =m0b. rear-front-1= =m0c. front= = reard. front= = rear+111. 判定一個(gè)循環(huán)隊(duì)列qu（最多元素為m0、 m0= =maxsize-1）為滿隊(duì)列的條件為 ；a. rear- front+ maxsize% maxsize = =

21、m0b. rear-front-1= =m0c. front= =reard. front= = rear+1； 不帶空的頭結(jié)點(diǎn)精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載12. 循環(huán)隊(duì)列用數(shù)組a0 ,m-1 存放其元素值, 已知其頭尾指針分別為front和 rear ,就當(dāng)前隊(duì)列中的元素個(gè)數(shù)為 ；a. rear-front+m%mb. rear-front+1 c.rear-front-1d. rear-front13. 棧和隊(duì)列的共同點(diǎn)為 ；a.都為先進(jìn)后出b.都為先進(jìn)先出c.只答應(yīng)在端點(diǎn)處插入和刪除元素d.沒有共同點(diǎn)3.2 填空題（將正確的答案填在相應(yīng)的空中）精品學(xué)習(xí)資料精選學(xué)習(xí)資料

22、- - - 歡迎下載1. 向量.棧和隊(duì)列都為 結(jié)構(gòu),可以在向量的 位置插入和刪除元素；對于棧只能在隊(duì)列只能在 插入元素和 刪除元素；2. 向一個(gè)長度為n 的向量的第i 個(gè)元素（ 1i n+1）之前插入一個(gè)元素時(shí),需向后移動(dòng)3. 向一個(gè)長度為n 的向量中刪除第i 個(gè)元素（ 1 i n）時(shí),需向前移動(dòng) 個(gè)元素； 插入和刪除元素；對于 個(gè)元素；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載4. 在具有 n 個(gè)單元的循環(huán)隊(duì)列中,隊(duì)滿時(shí)共有 個(gè)元素；習(xí)題答案1. c2. c3. a4. b5.d6. ba7.c8. b9. c 10. c11. a12. a13.c3.13.21.線性.任何.棧頂.隊(duì)尾

23、.隊(duì)首2. n-i+13. n-i 4. n-1習(xí)題 6樹和二叉樹6.1 單項(xiàng)選擇題1. 由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2,所以二叉樹為一種特別的樹,這種說法 ；a. 正確b.錯(cuò)誤2. 假定在一棵二叉樹中,雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30個(gè),就葉子結(jié)點(diǎn)數(shù)為個(gè)；a 15 b 16c 17d 47精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載3. 依據(jù)二叉樹的定義,具有3 個(gè)結(jié)點(diǎn)的不同外形的二叉樹有a. 3b. 4c. 5d. 6 種；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載4. 依據(jù)二叉樹的定義,具有3 個(gè)不同數(shù)據(jù)結(jié)點(diǎn)的不同的二叉樹有 種；a. 5b. 6c. 30d. 325. 深

24、度為 5 的二叉樹至多有 個(gè)結(jié)點(diǎn)；a. 16b. 32c. 31d. 106. 設(shè)高度為h 的二叉樹上只有度為0 和度為 2 的結(jié)點(diǎn),就此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為_；a. 2hb. 2h-1c. 2h+1d. h+17. 對一個(gè)滿二叉樹,m個(gè)樹葉, n 個(gè)結(jié)點(diǎn),深度為h,就 ；ha. n=h+mb. h+m=2nc. m=h-1d. n=2-18. 任何一棵二叉樹的葉結(jié)點(diǎn)在先序.中序和后序遍歷序列中的相對次序 ；a. 不發(fā)生轉(zhuǎn)變b.發(fā)生轉(zhuǎn)變c.不能確定d.以上都不對9. 假如某二叉樹的前根次序遍歷結(jié)果為stuwv ,中序遍歷為uwtvs ,那么該二叉樹的后序?yàn)?；a. uwvtsb. v

25、wutsc. wuvtsd. wutsv10. 二叉樹的前序遍歷序列中,任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面,這種說法 ；a.正確b.錯(cuò)誤11. 某二叉樹的前序遍歷結(jié)點(diǎn)拜訪次序?yàn)閍bdgcefh ,中序遍歷的結(jié)點(diǎn)拜訪次序?yàn)閐gbaechf ,就其后序遍歷的結(jié)點(diǎn)拜訪次序?yàn)?；a. bdgcefhab. gdbecfhac. bdgaechfd. gdbehfca12. 在一非空二叉樹的中序遍歷序列中,根結(jié)點(diǎn)的右邊 ；a.只有右子樹上的全部結(jié)點(diǎn)b.只有右子樹上的部分結(jié)點(diǎn)c.只有左子樹上的部分結(jié)點(diǎn)d.只有左子樹上的全部結(jié)點(diǎn)13. 如圖 6.1 所示二叉樹的中序遍歷序列為 ；a. abcdgefb. d

26、febagcc. dbaefcgd. defbagc精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載abcdge圖 6.1f14.一 棵abcdef gh二叉樹如圖6.2 所示,其中序遍歷的序列為 ；a精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載abcdefgha. 圖 6.2abdgcefhb.dgbaechfc.gdbehfcad.精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載15設(shè) a、b 為一棵二叉樹上的兩個(gè)結(jié)點(diǎn),在中序遍歷時(shí),a 在 b 前的條件為；aa 在 b 的右方b a 在 b 的左方ca 為 b 的祖先d a 為 b 的子孫16. 已知某二叉樹的后序遍歷序列為dabec ,中

27、序遍歷序列為debac,它的前序遍歷序列為 ；a.acbedb. decabc. deabcd. cedba17. 實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu),正確方案為二叉樹采納 儲(chǔ)備結(jié)構(gòu)；a. 二叉鏈表b.廣義表儲(chǔ)備結(jié)構(gòu)c.三叉鏈表d.次序儲(chǔ)備結(jié)構(gòu)18. 如圖 6.3 所示的 4 棵二叉樹, 不為完全二叉樹；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載abcd圖 6.320.b.21.錯(cuò)誤22.a.正確23.24.在線索化二叉樹中,t 所指結(jié)點(diǎn)沒有左子樹的充要條件為 ；a. t left=nullb. t ltag=1c. t ltag=1且t left=nulld.以上都不對二

28、叉樹按某種次序線索化后,任一結(jié)點(diǎn)均有指向其前驅(qū)和后續(xù)的線索,這種說法 ；a.正確二叉樹為二叉排序樹的充分必要條件為其任一結(jié)點(diǎn)的值均大于其左孩子的值.小于其右孩子的值；這種說法 ；b. 錯(cuò)誤具有五層結(jié)點(diǎn)的二叉平穩(wěn)樹至少有 個(gè)結(jié)點(diǎn)；a. 10b. 12c. 15d. 17樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷.中序遍歷和后序遍歷；這里,我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對應(yīng)的二叉樹；結(jié)論 為正確的；a. 樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同b. 樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同c.樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列

29、相同d.以上都不對25. 樹最適合用來表示 ；a. 有序數(shù)據(jù)元素b.無序數(shù)據(jù)元素c. 元素之間具有分支層次關(guān)系的數(shù)據(jù)d.元素之間無聯(lián)系的數(shù)據(jù)6.2 填空題（將正確的答案填在相應(yīng)的空中）精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載1. 有一棵樹如圖6.5 所示,回答下面的問題： 這棵樹的根結(jié)點(diǎn)為 ； 這棵樹的葉子結(jié)點(diǎn)為 ； 結(jié)點(diǎn) k3 的度為 ； 這棵樹的度為 ； 這棵樹的深度為 ； 結(jié)點(diǎn) k3 的子女為 ； 結(jié)點(diǎn) k3 的父結(jié)點(diǎn)為 k12kkk3k4 k56精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載2. 指出樹和二叉樹的三個(gè)主要差別 . . ； ；圖 6.5一棵樹k7精品學(xué)習(xí)資料精選學(xué)習(xí)

30、資料 - - - 歡迎下載3. 從概念上講,樹與二叉樹為兩種不同的數(shù)據(jù)結(jié)構(gòu),將樹轉(zhuǎn)化為二叉樹的基本目的為 _；4. 一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采納次序儲(chǔ)備結(jié)構(gòu),儲(chǔ)備于數(shù)組t 中, 如圖 6.6 所示, 就該二叉樹的鏈接表示形式為 ；5. 深度為 k 的完全二叉樹至少有 個(gè)結(jié)點(diǎn)；至多有 個(gè)結(jié)點(diǎn),如按自上而下,從左到右次序給結(jié)點(diǎn)編號(hào)（從1 開始）,就編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)為 ；89101112131415161718192021cjlhb1234567eafdg圖 6.6一棵二叉樹的次序儲(chǔ)備數(shù)組t6. 在一棵二叉樹中,度為零的結(jié)點(diǎn)的個(gè)數(shù)為n 0,度為 2 的結(jié)點(diǎn)的個(gè)數(shù)為n2,就有 n0 = ；7. 一

31、棵二叉樹的第i （ i 1）層最多有 個(gè)結(jié)點(diǎn)；一棵有n（ n>0）個(gè)結(jié)點(diǎn)的滿二叉樹共有 個(gè)葉子和 個(gè)非終端結(jié)點(diǎn)；8. 結(jié)點(diǎn)最少的樹為 ,結(jié)點(diǎn)最少的二叉樹為 ；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載9. 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc,問有 種不同外形的二叉樹可以得到這一遍歷結(jié)果,這些二叉樹分別為 ；10. 由如圖 6.7 所示的二叉樹,回答以下問題： 其中序遍歷序列為 ；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載 其前序遍歷序列為 ； 其后序遍歷序列為 ；abcdef精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載h精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載6.3 簡答

32、題1. 依據(jù)二叉樹的定義,具有三個(gè)結(jié)點(diǎn)的二叉樹有5 種不同的外形,請將它們分別畫出；i圖 6.7 一棵二叉樹精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載2. 假設(shè)一棵二叉樹的先序序列為ebadcfhgik和j請畫出該樹；3. 由如圖 6.7 所示的二叉樹,回答以下問題：（ 1）畫出該二叉樹的中序線索二叉樹；（ 2）畫出該二叉樹的后序線索二叉樹；中序序列為abcdefghij；ka精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載（ 3）畫出該二叉樹對應(yīng)的森林；bcd4. 已知一棵樹如圖6.8 所示, 轉(zhuǎn)化為一棵二叉樹,表示為 ；efg圖 6.8 一棵樹5. 以數(shù)據(jù)集 4 , 5, 6, 7,10

33、, 12,18 為結(jié)點(diǎn)權(quán)值,畫出構(gòu)造huffman 樹的每一步圖示,運(yùn)算其帶權(quán)路徑長度為；6. 一棵含有n 個(gè)結(jié)點(diǎn)的k 叉樹 、 可能達(dá)到的最大深度和最小深度各為多少.7. 證明 : 一棵滿 k 叉樹上的葉子結(jié)點(diǎn)數(shù)n 0 和非葉子結(jié)點(diǎn)數(shù)n1 之間滿意以下關(guān)系: n0 =k-1n1 +16.4 算法設(shè)計(jì)題1. 編寫按層次次序（同一層自左至右）遍歷二叉樹的算法；2試編寫算法,對一棵二叉樹、 統(tǒng)計(jì)葉子的個(gè)數(shù)；3試編寫算法,對一棵二叉樹根結(jié)點(diǎn)不變,將左.右子樹進(jìn)行交換,樹中每個(gè)結(jié)點(diǎn)的左.右子樹進(jìn)行交換；7. 假設(shè)用于通訊的電文僅有八個(gè)字母a、b、c、d、e、f、g、h組成,字母在電文中顯現(xiàn)的頻率分別為

34、0.07、0.19、0.02、0.06、 0.32、 0.03、 0.21、 0.10；試為這八個(gè)字母設(shè)計(jì)哈夫曼編碼；使用 0-7 的二進(jìn)制表示形式為另一種編碼方案；對于上述實(shí)例,比較兩種方案的優(yōu)缺點(diǎn)；8. 試編寫算法,對一棵以孩子- 兄弟鏈表表示的樹統(tǒng)計(jì)葉子的個(gè)數(shù)；假設(shè)一棵二叉樹的先序序列為ebadcfhgikj和中 序序列為abcdefghij；k 請畫出該樹；習(xí)題答案6.11. b2. b3. c4. c5. c6. a7. d8. a9. c 10. a11. d2. a13. b14. b15. b 16. d 17. c18. c19. b20. b 21. b22. b23. b

35、 24. a 25. c6.21. k1 k2、k5、k7、k4 2 3 4 k5、k6 k12. 樹的結(jié)點(diǎn)個(gè)數(shù)至少為1 不同教材規(guī)定不同 ,而二叉樹的結(jié)點(diǎn)個(gè)數(shù)可以為0；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載樹中結(jié)點(diǎn)的最大度數(shù)沒有限制,而二叉樹結(jié)點(diǎn)的最e樹的結(jié)點(diǎn)無左.右之分,而二叉樹的結(jié)點(diǎn)有左.右af大度數(shù)為2； 之分；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載3. 樹可采納孩子 - 兄弟鏈表（二叉鏈表）做儲(chǔ)備結(jié)構(gòu),目的并利用二叉樹的已有算法解精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載決樹的有關(guān)問題；4. 如圖 6.9 所示k-1kk-25. 2. 2-1. 2+16. n2+

36、1dgcjlh精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載7. 2i-12 logn+1-1log22n+1 1b精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載28. 只有一個(gè)結(jié)點(diǎn)的樹；空的二叉樹9. 5；如圖 6.10 所示圖 6.9精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載ccaabbabcac abcb圖 6.10 樹形 5 種10. dgbaechif. abdgcefhi. gdbeihfca.6.31. 5種、圖 6.112. 二叉樹如圖6.12 所示；e圖 6.11 樹 形 5 種bfadh3. 中序線索二叉樹如圖6.13 （左）所示；后序線索二叉樹如圖6.13（右） 所示

37、；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載該二叉樹轉(zhuǎn)換后的的森林如圖6.14 所示；cgi精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載aak精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載bcdefbcnulldefa cjf圖 6.12b ehi精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載4. 圖 6.8 的樹轉(zhuǎn)化為一棵二叉樹如下,圖6.15d ：jjhjha精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載nullii圖 6.14b對應(yīng)的森林c精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載6.13圖8.18中序和后序線索樹圖edig圖6.15一棵樹的孩子兄弟表5. 畫出構(gòu)造huffma

38、n 樹如圖 6.16 所示,運(yùn)算其帶權(quán)路徑長度為；6. 一棵含有n 個(gè)結(jié)點(diǎn)的k 叉樹 、 可能達(dá)到的最大深度h=n-k+1,最小深度各為 : logk n+1；623725191813121096745圖 6.16huffman 樹精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載習(xí)題 7圖7.1 單項(xiàng)選擇題1在一個(gè)圖中,全部頂點(diǎn)的度數(shù)之和等于全部邊數(shù)的 倍；a. 1/2b. 1c. 2d. 42任何一個(gè)無向連通圖的最小生成樹；a. 只有一棵b. 有一棵或多棵c. 肯定有多棵d. 可能不存在 3在一個(gè)有向圖中,全部頂點(diǎn)的入度之和等于全部頂點(diǎn)的出度之和的 倍；a. 1/2b. 1c. 2d. 44一

39、個(gè)有n 個(gè)頂點(diǎn)的無向圖最多有 條邊；a. nb. nn-1c. nn-1/2d. 2n5具有 4 個(gè)頂點(diǎn)的無向完全圖有 條邊；a. 6b. 12c. 16d. 20精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載6具有 6 個(gè)頂點(diǎn)的無向圖至少應(yīng)有 a. 5b. 6c. 7d. 8 條邊才能確保為一個(gè)連通圖；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載7在一個(gè)具有n 個(gè)頂點(diǎn)的無向圖中,要連通全部頂點(diǎn)至少需要a. nb. n+1c. n-1d. n/2 條邊；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載228對于一個(gè)具有n 個(gè)頂點(diǎn)的無向圖,如采納鄰接矩陣表示,就該矩陣的大小為 ；a. nb. n

40、-1c. n-1d. n9對于一個(gè)具有n 個(gè)頂點(diǎn)和e 條邊的無向圖,如采納鄰接表表示,就表頭向量的大小為_ ；全部鄰接表中的接點(diǎn)總 數(shù) 為 _ ； a. nb. n+1c. n-1d. n+e a. e/2b. ec.2ed. n+e10已知一個(gè)圖如圖7.1 所示,如從頂點(diǎn)a 動(dòng)身按深度搜尋法進(jìn)行遍歷,就可能得到的一種頂點(diǎn)序列為 ；按寬度搜尋法進(jìn)行遍歷,就可能得到的一種頂點(diǎn)序列為 ； a. a、b、e、c、d、fb. e、c、f、e、b、dc. a、e、b、c、f、dd. a、e、d、f、c、b精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載 a. a、b、c、e、d、fb. a、b、c、e、f

41、、dc. a、e、b、c、f、dd. a、c、f、d、e、ba精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載becdf圖 7.1一個(gè)無向圖11已知一有向圖的鄰接表儲(chǔ)備結(jié)構(gòu)如圖7.2 所示；13223454 524圖 7.2一個(gè)有向圖的鄰接表儲(chǔ)備結(jié)構(gòu) 依據(jù)有向圖的深度優(yōu)先遍歷算法,從頂點(diǎn)v1 動(dòng)身,所得到的頂點(diǎn)序列為 ；a. v1、v2、v3、v5、v4b. v1、v2、v3、v4、v5精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載c. v1、v3、v4、v5、v2d. v1、v4、v3、v5、v2 依據(jù)有向圖的寬度優(yōu)先遍歷算法,從頂點(diǎn)v1 動(dòng)身,所得到的頂點(diǎn)序列為 ；a. v1、v2、v3、v

42、4、v5b. v1、v3、v2、v4、v5c. v1、v2、v3、v5、v4d. v1、v4、v3、v5、v2 12采納鄰接表儲(chǔ)備的圖的深度優(yōu)先遍歷算法類似于二叉樹的 ；a. 先序遍歷b.中序遍歷c.后序遍歷d.按層遍歷13采納鄰接表儲(chǔ)備的圖的寬度優(yōu)先遍歷算法類似于二叉樹的 ；a.先序遍歷b.中序遍歷c.后序遍歷d.按層遍歷14判定一個(gè)有向圖為否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?仍可以利用 ；a.求關(guān)鍵路徑的方法b.求最短路徑的dijkstra方法c.寬度優(yōu)先遍歷算法d.深度優(yōu)先遍歷算法15關(guān)鍵路徑為大事結(jié)點(diǎn)網(wǎng)絡(luò)中；a. 從源點(diǎn)到匯點(diǎn)的最長路徑b.從源點(diǎn)到匯點(diǎn)的最短路徑c. 最長的回路d.最

43、短的回路16下面不正確的說法為；（ 1）在 aoe網(wǎng)中,減小一個(gè)關(guān)鍵活動(dòng)上的權(quán)值后,整個(gè)工期也就相應(yīng)減??；（ 2） aoe網(wǎng)工程工期為關(guān)鍵活動(dòng)上的權(quán)之和；（ 3）在關(guān)鍵路徑上的活動(dòng)都為關(guān)鍵活動(dòng),而關(guān)鍵活動(dòng)也必在關(guān)鍵路徑上；a. （1）b. （2）c. （3）d. （ 1）.（ 2）17用 dfs遍歷一個(gè)無環(huán)有向圖,并在dfs算法退棧返回時(shí)打印出相應(yīng)的頂點(diǎn),就輸出的頂點(diǎn)序列為；a. 逆拓樸有序的b. 拓樸有序的c. 無序的 18在圖 7.3 所示的拓樸排列的結(jié)果序列為；a.125634b.516234c.123456d.52163419一個(gè)有n 個(gè)頂點(diǎn)的無向圖連7通.3 有圖向,圖它所包含的連通

44、重量個(gè)數(shù)為；a.0b.1c.nd.n+120對于一個(gè)有向圖,如一個(gè)頂點(diǎn)的入度為k1、 .出度為k2,就對應(yīng)鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為；a.k1b.k2c.k1-k2d.k1+k221對于一個(gè)有向圖,如一個(gè)頂點(diǎn)的入度為k1、 .出度為k2,就對應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的結(jié)點(diǎn)數(shù)為；a.k1b.k2c.k1-k2d.k1+k27.2 填空題（將正確的答案填在相應(yīng)餓空中）1 n 個(gè)頂點(diǎn)的連通圖至少 條邊；2在無權(quán)圖 g的鄰接矩陣a 中,如vi、vj或 vi、vj屬于圖g的邊集合,就對應(yīng)元素aij等于 ,否就等于 ；3在無向圖g的鄰接矩陣a 中,如 aij等于 1,就 aji 等于 ；精品學(xué)習(xí)資

45、料精選學(xué)習(xí)資料 - - - 歡迎下載4已知圖g 的鄰接表如圖7.4所示,其從頂點(diǎn)v1 動(dòng)身的深度有限搜尋序列為序列為 ； ,其從頂點(diǎn)v1 動(dòng)身的寬度優(yōu)先搜尋精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載v1 v2 v3v4v5v6v2v5v4v3v5v6v4v6v3圖 7.4圖 g的鄰接表精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載5已知一個(gè)有向圖的鄰接矩陣表示,運(yùn)算第i 個(gè)結(jié)點(diǎn)的入度的方法為 ；6已知一個(gè)圖的鄰接矩陣表示,刪除全部從第i 個(gè)結(jié)點(diǎn)動(dòng)身的邊的方法為 ；精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載7假如含n 個(gè)頂點(diǎn)的圖形成一個(gè)環(huán),就

46、它有棵生成樹；8一個(gè)非連通無向圖,共有28 條邊,就該圖至少有個(gè)頂點(diǎn)；9遍歷圖的過程實(shí)質(zhì)上為；bfs 遍歷圖的時(shí)間復(fù)雜度為, dfs 遍歷圖的時(shí)間復(fù)雜度為,兩者不同之處在于,反映在數(shù)據(jù)結(jié)構(gòu)上的差別為；10一個(gè)圖的表示法為唯獨(dú)的,而表示法為不唯獨(dú)的；11有向圖中的結(jié)點(diǎn)前驅(qū)后繼關(guān)系的特點(diǎn)為；12如無向圖g的頂點(diǎn)度數(shù)最小值大于等于時(shí), g至少有一條回路；13依據(jù)圖的儲(chǔ)備結(jié)構(gòu)進(jìn)行某種次序的遍歷,得到的頂點(diǎn)序列為的；7.3 綜合題1已知如圖7.5 所示的有向圖,請給出該圖的:（ 1）每個(gè)頂點(diǎn)的入/ 出度；15（ 2）鄰接距陣；（ 3）鄰接表；（ 4）逆鄰接表；6（ 5）強(qiáng)連通重量；243圖 7；5 一個(gè)

47、有向圖2請用克魯斯卡爾和普里姆兩種算法分別為圖7.6 .圖 7.7 構(gòu)造最小生成樹：精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載（ 1）a161115精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載b15c15d精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載1316e141221f精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載圖 7.6精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載（ 2）62121216131524716592010354圖 7.7精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載3試列出圖7.8 中全部的拓?fù)渑判蛐蛄校?23456圖 7.8精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載4請用圖示說明圖7.9 從頂點(diǎn) a 到其余各頂點(diǎn)之間的最短路徑；5bd36a232f35ce圖 74.95已知 aoe網(wǎng)有 9 個(gè)結(jié)點(diǎn)： v1, v2,v3, v4,v5, v6, v7, v8, v9,其鄰接矩陣如下：(1) 請畫出該aoe圖；(2) 運(yùn)算完成整個(gè)方案需