數(shù)據(jù)結(jié)構(gòu)習(xí)題與實(shí)驗(yàn)指導(dǎo)

1、真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 1 / 36 第一部分第一部分 習(xí)題習(xí)題 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 2 / 36 第一章第一章 緒論緒論 一單選題一單選題 1若一個(gè)數(shù)據(jù)具有集合結(jié)構(gòu)，則元素之間具有（若一個(gè)數(shù)據(jù)具有集合結(jié)構(gòu)，則元素之間具有（ ） 。 A線性關(guān)系線性關(guān)系 B層次關(guān)系層次關(guān)系 C網(wǎng)狀關(guān)系網(wǎng)狀關(guān)系 D無任何關(guān)系無任何關(guān)系 2下面程序段的時(shí)間復(fù)雜度為（下面程序段的時(shí)間復(fù)雜度為（ ） 。 intint i,j;i,j; for(i=0;im;i+)for(i=0;im;i+) for(j=0;jn;j+)for(j=0;jn;j+) aij=i*j

2、;aij=i*j; AO(m2) BO(n2) CO(mn) DO(m+ +n) 3執(zhí)行下面程序段時(shí)，執(zhí)行下面程序段時(shí)，S 語句被執(zhí)行的次數(shù)為（語句被執(zhí)行的次數(shù)為（ ） 。 intint i,j;i,j; for(i=1;i=n;i+)for(i=1;i=n;i+) for(j=1;j=i;j+)for(j=1;j=i;j+) S; An2 Bn2/2 Cn(n+1) Dn(n+1)/2 二填空題二填空題 1數(shù)據(jù)的邏輯結(jié)構(gòu)被分為數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、_、_ 和和_四種。四種。 2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為_、_、_ 和和_四種。四種。 3在線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)中，前驅(qū)和后繼

3、結(jié)點(diǎn)之間分別存在著在線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著 _、_和和_的的 XXX。 4在在 C 語言中，一個(gè)數(shù)組語言中，一個(gè)數(shù)組 a 所占有的存儲(chǔ)空間的大小即數(shù)組長度為所占有的存儲(chǔ)空間的大小即數(shù)組長度為 _，下標(biāo)為，下標(biāo)為 i i 的元素的元素 aiai的存儲(chǔ)的存儲(chǔ) XXXXXX 為為_。 5在下面程序段中，在下面程序段中，s=s+p 語句的執(zhí)行次數(shù)為語句的執(zhí)行次數(shù)為_，p*=j 語句的語句的 執(zhí)行次數(shù)為執(zhí)行次數(shù)為_，該程序段的時(shí)間復(fù)雜度為，該程序段的時(shí)間復(fù)雜度為_。 intint i=0,s=0;i=0,s=0; while(+i=n) int j,p=1; for(j

4、=1;j=i;j+)for(j=1;j=i;j+) p*=j;p*=j; s=s+p;s=s+p; 6某算法僅含某算法僅含 2 個(gè)語句個(gè)語句，其執(zhí)行次數(shù)分別為其執(zhí)行次數(shù)分別為 1000n2和和 0. 01n3，則該算法的則該算法的 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為_。 7一個(gè)算法的時(shí)間復(fù)雜度為一個(gè)算法的時(shí)間復(fù)雜度為(3n2+2nlog2n+4n-7)/(5n)，其數(shù)量級(jí)表示為其數(shù)量級(jí)表示為 _。 三三應(yīng)用題應(yīng)用題 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 3 / 36 有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，試畫出它們分別對應(yīng)的圖形表示，并指有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，試畫出它們分別對應(yīng)的圖形

5、表示，并指 出它們分別屬于何種結(jié)構(gòu)。出它們分別屬于何種結(jié)構(gòu)。 1A=（K，R）其中其中 K=a1,a2,a3,an R= 2B=（K，R）其中其中 K=a,b,c,d ,e,f,g,h R= , 3C=（K，R）其中其中 K=a,b,c,d ,e,f,g,h R= , 4D=（K，R）其中其中 K=1,2,3,4,5,6 R= (1,2), (2,3), (2,4), (3,4), (3,5), (3,6), (4,5), (4,6) 第二章第二章 線性表線性表 一單選題一單選題 1下列有關(guān)線性表的敘述中，正確的是（下列有關(guān)線性表的敘述中，正確的是（ ） 。 A線性表中的元素之間是線性關(guān)系線性

6、表中的元素之間是線性關(guān)系 B線性表中至少有一個(gè)元素線性表中至少有一個(gè)元素 C線性表中任何一個(gè)元素有且僅有一個(gè)直接前驅(qū)線性表中任何一個(gè)元素有且僅有一個(gè)直接前驅(qū) D線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼 2在一個(gè)長度為在一個(gè)長度為 n 的順序存儲(chǔ)的線性表中，向第的順序存儲(chǔ)的線性表中，向第 i 個(gè)元素（個(gè)元素（1in+1）位）位 置插入一個(gè)新元素時(shí)，需要從后向前依次后移（置插入一個(gè)新元素時(shí)，需要從后向前依次后移（ ）個(gè)元素。）個(gè)元素。 An-i Bn-i+1 Cn-i-1 Di 3在一個(gè)長度為在一個(gè)長度為 n 的順序存儲(chǔ)的線性表中，刪除第的順序存儲(chǔ)的線性表中

7、，刪除第 i 個(gè)元素（個(gè)元素（1in）時(shí)，）時(shí)， 需要從前向后依次前移（需要從前向后依次前移（ ）個(gè)元素。）個(gè)元素。 An-i Bn-i+1 Cn-i-1 Di 4在一個(gè)長度為在一個(gè)長度為 n 的順序表中插入一個(gè)元素的時(shí)間復(fù)雜度為（的順序表中插入一個(gè)元素的時(shí)間復(fù)雜度為（ ） 。 AO(n) BO(n/2) CO(1) DO(n2) 5不帶頭結(jié)點(diǎn)的單鏈表的頭指針為不帶頭結(jié)點(diǎn)的單鏈表的頭指針為 head，則該鏈表為空的判定條件是（，則該鏈表為空的判定條件是（ ） 。 Ahead =NULL Bhead-next=NULL Chead !=NULL Dhead-next !=NULL 6帶頭結(jié)點(diǎn)的單

8、鏈表的頭指針為帶頭結(jié)點(diǎn)的單鏈表的頭指針為 head，判定該鏈表為非空的條件是（，判定該鏈表為非空的條件是（ ） 。 Ahead =NULL Bhead-next=NULL Chead !=NULL Dhead-next !=NULL 7在一個(gè)頭指針為在一個(gè)頭指針為 ph 的單鏈表中，若要在結(jié)點(diǎn)的單鏈表中，若要在結(jié)點(diǎn)*p 之后插入一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)*s，則，則 應(yīng)執(zhí)行的語句是（應(yīng)執(zhí)行的語句是（ ） 。 As-next =p-next; p-next=s; Bp-next=s; s-next =p-next; Cp-next=s-next; s-next=p; Ds-next=p; p-ne

9、xt=s-next; 8在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表中，若要在指針在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表中，若要在指針 p 所指向的結(jié)點(diǎn)之后插所指向的結(jié)點(diǎn)之后插 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 4 / 36 入一個(gè)入一個(gè) q 指針?biāo)赶虻慕Y(jié)點(diǎn)，則需要對指針?biāo)赶虻慕Y(jié)點(diǎn)，則需要對 q-right 賦值為（賦值為（ ） 。 Ap-left Bp-right Cp-right-right Dp- left-left 9在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表中，若要在指針在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表中，若要在指針 p 所指向的結(jié)點(diǎn)之前插所指向的結(jié)點(diǎn)之前插 入一個(gè)入一個(gè) q 指針?biāo)赶虻慕Y(jié)點(diǎn)，則需要對指針

10、所指向的結(jié)點(diǎn)，則需要對 p-left-right 賦值為（賦值為（ ） 。 Aq Bp Cp-right Dp- left 10在下列對順序表進(jìn)行的操作中，算法時(shí)間復(fù)雜度為為在下列對順序表進(jìn)行的操作中，算法時(shí)間復(fù)雜度為為 O(1)的是（的是（ ） 。 A訪問第訪問第 i 個(gè)元素的前驅(qū)（個(gè)元素的前驅(qū)（1next 指針域。指針域。 5在以在以 HL 為表頭指針的帶頭結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條為表頭指針的帶頭結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條 件分別為件分別為_和和 _。 6在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表中在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表中,在表頭插入或刪除，與在其它位置插入在表頭插入或刪

11、除，與在其它位置插入 或刪除，其操作過程是或刪除，其操作過程是_的。的。 三算法填空與應(yīng)用題三算法填空與應(yīng)用題 1在帶頭結(jié)點(diǎn)的單鏈表在帶頭結(jié)點(diǎn)的單鏈表 H 中的中的 P 結(jié)點(diǎn)前插入一個(gè)元素結(jié)點(diǎn)前插入一個(gè)元素 X。 void insert_linkst(Lnode *H, Lnode *P,elemtp X) q=H; while(q-next!=p) q= q-next; S=( Lnode * )malloc(sizeof(_); _=X;_=X; S S-next=P; _;_; 2在雙向鏈表中的在雙向鏈表中的 p 結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)前插入一個(gè) s 結(jié)點(diǎn)，假設(shè)結(jié)點(diǎn)，假設(shè) s 已生成。已生成

12、。 s-prior=_;_; 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 5 / 36 s- next=_;_; p-prior- next=_;_; p-prior =_;_; 3設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下：設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下： typedef_char DataType struct node DataType data; struct node *next; 閱讀下列算法閱讀下列算法 f，簡述算法，簡述算法 f 的功能。的功能。 int f(struct node *L) struct node *p; int n=0; p=L; while(p) if(p-next=B) n+;

13、 p= p-next; return(n); 第三章第三章 棧和隊(duì)列棧和隊(duì)列 一單選題一單選題 1棧的插入和刪除操作在（棧的插入和刪除操作在（ ）進(jìn)行。）進(jìn)行。 A棧頂棧頂 B棧底棧底 C任意位置任意位置 D指定位置指定位置 2假定利用數(shù)組假定利用數(shù)組 aN順序存儲(chǔ)一個(gè)棧，用順序存儲(chǔ)一個(gè)棧，用 top 表示棧指針，表示棧指針，top= -1 表示棧表示棧 空，則當(dāng)元素空，則當(dāng)元素 x 進(jìn)棧時(shí)所執(zhí)行的操作為（進(jìn)棧時(shí)所執(zhí)行的操作為（ ） 。 Aa-top =x Batop -=x Ca+top =x Datop +=x 3假定利用數(shù)組假定利用數(shù)組 aN順序存儲(chǔ)一個(gè)棧，用順序存儲(chǔ)一個(gè)棧，用 top

14、表示棧指針，表示棧指針，top= -1 表示棧表示棧 空，并已知棧未空，則當(dāng)退棧并返回棧頂元素時(shí)所執(zhí)行的操作為（空，并已知棧未空，則當(dāng)退棧并返回棧頂元素時(shí)所執(zhí)行的操作為（ ） 。 Areturn a-top Breturn atop - Creturn a+top Dreturn atop + 4當(dāng)利用大小為當(dāng)利用大小為 N 的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用 top=N 表示棧空，則表示?？眨瑒t 向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行（向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行（ ）語句修改）語句修改 top 指針。指針。 Atop+ Btop- Ctop=0 Dtop=N 5

15、假定一個(gè)鏈棧的棧頂指針用假定一個(gè)鏈棧的棧頂指針用 top 表示，則當(dāng)表示，則當(dāng) p 所指向的結(jié)點(diǎn)進(jìn)棧時(shí)，執(zhí)行所指向的結(jié)點(diǎn)進(jìn)棧時(shí)，執(zhí)行 的操作為（的操作為（ ） 。 Ap-next =top； top = top-next； Btop=p; p-next= top ; Cp-next= top-next; top-next =p; Dp-next= top; top =p; 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 6 / 36 6若讓元素若讓元素 1、2、3、4 依次進(jìn)棧，則不可能的出棧次序是（依次進(jìn)棧，則不可能的出棧次序是（ ） 。 A3421 B3241 C1234 D4312 7

16、當(dāng)利用大小為當(dāng)利用大小為 N 的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，若沒有隊(duì)列長度的變量，的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，若沒有隊(duì)列長度的變量， 則該隊(duì)列的最大長度為（則該隊(duì)列的最大長度為（ ） 。 AN-2 BN-1 CN D N+1 8假定一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針分別為假定一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針分別為 front 和和 rear，則判別隊(duì)空的條件，則判別隊(duì)空的條件 為（為（ ） 。 Afront=rear Bfront!=NULL Crear!= NULL Dfront= NULL 9假定一個(gè)帶頭結(jié)點(diǎn)的循環(huán)鏈隊(duì)的隊(duì)首和隊(duì)尾指針分別用假定一個(gè)帶頭結(jié)點(diǎn)的循環(huán)鏈隊(duì)的隊(duì)首和隊(duì)尾指針分別用 front 和和 rea

17、r 表表 示，則判別隊(duì)空的條件為（示，則判別隊(duì)空的條件為（ ） 。 Afront!=rear Brear =NULL Cfront = NULL Dfront= rear 10在一個(gè)長度為在一個(gè)長度為 N 的數(shù)組空間中，順序存儲(chǔ)一個(gè)隊(duì)列，該隊(duì)列的隊(duì)首和隊(duì)的數(shù)組空間中，順序存儲(chǔ)一個(gè)隊(duì)列，該隊(duì)列的隊(duì)首和隊(duì) 尾指針分別用尾指針分別用 front 和和 rear 表示，則該隊(duì)列中的元素個(gè)數(shù)為（表示，則該隊(duì)列中的元素個(gè)數(shù)為（ ） 。 A （rear front）%N B （rear front+N）%N C （rear+N）%N D （ front +N）%N 11下列說法中錯(cuò)誤的是（下列說法中錯(cuò)誤的是

18、（ ） 。 A循環(huán)隊(duì)列空時(shí)，其循環(huán)隊(duì)列空時(shí)，其 front 與與 rear 等值等值 B循環(huán)隊(duì)列的任何元素都可隨機(jī)存取循環(huán)隊(duì)列的任何元素都可隨機(jī)存取 C循環(huán)隊(duì)列滿時(shí)，其循環(huán)隊(duì)列滿時(shí)，其 front 與與 rear 等值等值 D循環(huán)隊(duì)列有先進(jìn)先出特征循環(huán)隊(duì)列有先進(jìn)先出特征 12在具有在具有 m 個(gè)單元的循環(huán)隊(duì)列中，隊(duì)首指針為個(gè)單元的循環(huán)隊(duì)列中，隊(duì)首指針為 front，隊(duì)尾指針為，隊(duì)尾指針為 rear， 約定少用一個(gè)元素空間，則隊(duì)滿的條件是（約定少用一個(gè)元素空間，則隊(duì)滿的條件是（ ） 。 Afront=rear B （front+1）%m=rear Crear+1= front D （rear+1

19、）%m = front 二填空題二填空題 1當(dāng)用長度為當(dāng)用長度為 N 的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用 top=N 表示?？?，則表表示棧空，則表 示棧滿的條件為示棧滿的條件為_。 2向一個(gè)棧頂指針為向一個(gè)棧頂指針為 HS 的鏈棧中插入一個(gè)新結(jié)點(diǎn)的鏈棧中插入一個(gè)新結(jié)點(diǎn)*p 時(shí)，應(yīng)執(zhí)行時(shí)，應(yīng)執(zhí)行 _和和_操作。操作。 3 3中綴表達(dá)式中綴表達(dá)式 3*3*（x+2x+2）-5-5 所對應(yīng)的后綴表達(dá)式為所對應(yīng)的后綴表達(dá)式為_。 4 4后綴表達(dá)式后綴表達(dá)式 45*3245*32 +-+-的值為的值為_。 6設(shè)元素設(shè)元素 a、b、c、d 依次進(jìn)依次進(jìn) S 棧，若要在輸出端得到序

20、列棧，若要在輸出端得到序列 cbda，則應(yīng)執(zhí)行，則應(yīng)執(zhí)行 的操作序列為的操作序列為 push(S,a); push(S,b); push(S,c); _; _; _; pop(S); 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 7 / 36 pop(S); 1在一個(gè)不設(shè)隊(duì)列長度變量的順序隊(duì)列在一個(gè)不設(shè)隊(duì)列長度變量的順序隊(duì)列 Q 中，隊(duì)首和隊(duì)尾指針分別用中，隊(duì)首和隊(duì)尾指針分別用 front 和和 rear 表示，則判別隊(duì)空的條件為表示，則判別隊(duì)空的條件為_，判別隊(duì)滿的條件為，判別隊(duì)滿的條件為 _。 7用用 S 表示入棧操作，表示入棧操作，X 表示入棧操作，由輸入序列表示入棧操作，由輸入序列

21、“ABC”得到輸出序得到輸出序 列列“BCA”的操作序列的操作序列 SSXSXX，若元素入棧順序?yàn)?，若元素入棧順序?yàn)?1234，為了得到，為了得到 1342 的的 出棧順序，相應(yīng)的出棧順序，相應(yīng)的 S 和和 X 操作串為操作串為_。 8設(shè)棧設(shè)棧 S 和隊(duì)列和隊(duì)列 Q 的初始狀態(tài)為空，元素的初始狀態(tài)為空，元素 1、2、3、4、5 和和 6 依次通過一依次通過一 個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列 Q，若，若 6 個(gè)元素出隊(duì)列的順序是個(gè)元素出隊(duì)列的順序是 3、5、4、6、2 和和 1，則棧，則棧 S 至少應(yīng)該容納至少應(yīng)該容納_個(gè)元素。個(gè)元素。 三運(yùn)算題三運(yùn)算題 1有四個(gè)元

22、素有四個(gè)元素 a、b、c、d 依次進(jìn)棧，任何時(shí)候都可以出棧，請寫出所有可依次進(jìn)棧，任何時(shí)候都可以出棧，請寫出所有可 能的出棧序列和所有不存在的序列。能的出棧序列和所有不存在的序列。 2假定用一維數(shù)組假定用一維數(shù)組 a7順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列，隊(duì)首和隊(duì)尾指針分別用順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列，隊(duì)首和隊(duì)尾指針分別用 front 和和 rear 表示，當(dāng)前隊(duì)列中已有表示，當(dāng)前隊(duì)列中已有 5 個(gè)元素：個(gè)元素：23、45、67、80、34，其中，其中 23 為隊(duì)首元素，為隊(duì)首元素，front 的值為的值為 3，請畫出對應(yīng)的存儲(chǔ)狀態(tài)；當(dāng)連續(xù)做，請畫出對應(yīng)的存儲(chǔ)狀態(tài)；當(dāng)連續(xù)做 4 次出隊(duì)運(yùn)算次出隊(duì)運(yùn)算 后，再讓后，再

23、讓 15、36、48 元素依次進(jìn)棧，請?jiān)俅萎嫵鰧?yīng)的存儲(chǔ)狀態(tài)。元素依次進(jìn)棧，請?jiān)俅萎嫵鰧?yīng)的存儲(chǔ)狀態(tài)。 四算法填空題四算法填空題 1在以在以 top 為棧頂指針的鏈棧中插入一個(gè)元素為棧頂指針的鏈棧中插入一個(gè)元素 x。 SNode * Push_L(SNode *top, ELEMTP x) p=(SNode * )malloc(sizeof(SNode); p-date=x; _; _;_; returnreturn top; 2鏈棧出棧的算法。鏈棧出棧的算法。 SNode * pop_L(SNode *top, ELEMTP *y, int *flag) if(top=NULL) *flag

24、 =0; else p= top ; *y =_; top =_;_; free(p);free(p); *flag =1; 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 8 / 36 _;_; 第四章第四章 數(shù)組和廣義表數(shù)組和廣義表 一單選題一單選題 1二維數(shù)組二維數(shù)組 A44 采用行優(yōu)先的存儲(chǔ)方法，數(shù)組元素采用行優(yōu)先的存儲(chǔ)方法，數(shù)組元素 A00的起始的起始 XXX 為為 1000，數(shù)組元素的長度為，數(shù)組元素的長度為 2，則元素，則元素 A22的的 XXX 是（是（ ） 。 A1000 B1010 C1008 D1020 2二維數(shù)組二維數(shù)組 A1218采用列優(yōu)先的存儲(chǔ)方法，若每個(gè)元素各占

25、采用列優(yōu)先的存儲(chǔ)方法，若每個(gè)元素各占 3 個(gè)存儲(chǔ)單個(gè)存儲(chǔ)單 元，且第一個(gè)元素元，且第一個(gè)元素 A00的的 XXX 為為 150，則元素，則元素 A97的的 XXX 為（為（ ） 。 A A429 B B432432 C C435435 D D438438 3設(shè)一個(gè)廣義表為（設(shè)一個(gè)廣義表為（a,（b,c,（d,e,f） ）,g） ，則該廣義表的長度為（，則該廣義表的長度為（ ） 。 A1 B2 C3 D6 4設(shè)一個(gè)廣義表為（設(shè)一個(gè)廣義表為（a,（b,c,（d,e,f） ）,g） ，則該廣義表的深度為（，則該廣義表的深度為（ ） 。 A1 B2 C3 D4 5已知廣義表的表頭為已知廣義表的表頭為

26、a，表尾為（，表尾為（b,c）,則此廣義表為（則此廣義表為（ ） 。 A A （a， （b,c） ） B B （a，b，c） C C （a） ，b，c） D D （a，b，c） ） 6在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)行單鏈表中的結(jié)點(diǎn)都具在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)行單鏈表中的結(jié)點(diǎn)都具 有相同的（有相同的（ ） 。 A行號(hào)行號(hào) B列號(hào)列號(hào) C元素值元素值 DXXX 二填空題二填空題 1二維數(shù)組二維數(shù)組 Aij（10i20，5j10）采用行為主序方式存儲(chǔ)，每個(gè)）采用行為主序方式存儲(chǔ)，每個(gè) 元素占元素占 4 個(gè)存儲(chǔ)單元，并且個(gè)存儲(chǔ)單元，并且 A105的存儲(chǔ)的存儲(chǔ) XXX 是是

27、 1000，則，則 A189的的 XXX 是是_。 2n 階三角矩陣的上三角元素值相等，進(jìn)行壓縮存儲(chǔ)時(shí)，該值存儲(chǔ)在下標(biāo)為階三角矩陣的上三角元素值相等，進(jìn)行壓縮存儲(chǔ)時(shí)，該值存儲(chǔ)在下標(biāo)為 _數(shù)組元素中。數(shù)組元素中。 3在一個(gè)稀疏矩陣中，每個(gè)非零元素所對應(yīng)的三元組包括該元素的在一個(gè)稀疏矩陣中，每個(gè)非零元素所對應(yīng)的三元組包括該元素的 _、_和和_三項(xiàng)。三項(xiàng)。 4在稀疏矩陣所對應(yīng)的三元組線性表中，每個(gè)三元組元素按在稀疏矩陣所對應(yīng)的三元組線性表中，每個(gè)三元組元素按 _為主序、為主序、_為輔序的次序排列。為輔序的次序排列。 5在稀疏矩陣的十字鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)的在稀疏矩陣的十字鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)的 do

28、wn 指針域指向指針域指向 _相同的下一個(gè)結(jié)點(diǎn)，相同的下一個(gè)結(jié)點(diǎn)，rightright 指針域指向指針域指向_相同的下相同的下 一個(gè)結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)。 6一個(gè)廣義表中的元素分為一個(gè)廣義表中的元素分為_元素和元素和_元素兩類。元素兩類。 7在廣義表的存儲(chǔ)結(jié)構(gòu)中，單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一個(gè)域?qū)?yīng)不同，在廣義表的存儲(chǔ)結(jié)構(gòu)中，單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一個(gè)域?qū)?yīng)不同， 各自分別為各自分別為_域和域和_域。域。 8在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)包含有在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)包含有 _個(gè)域，在相應(yīng)的十字鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)包含有個(gè)域，在相應(yīng)的十字鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)包含

29、有 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 9 / 36 _個(gè)域。個(gè)域。 三應(yīng)用題三應(yīng)用題 1已知一個(gè)已知一個(gè) 6 行行 7 列的稀疏矩陣如下圖所示：列的稀疏矩陣如下圖所示： 0 0 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3-3 0 0 0 0 1 1 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0 -7-7 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 6 6 0 0 0 0 0 0 寫出它的三元組線性表；寫出它的三元組線性表； 給出它的順序存儲(chǔ)表示；給出它

30、的順序存儲(chǔ)表示； 給出它的轉(zhuǎn)置矩陣的三元組線性表和順序存儲(chǔ)表示；給出它的轉(zhuǎn)置矩陣的三元組線性表和順序存儲(chǔ)表示； 2對于廣義表對于廣義表 E（a,（a,b）,（a,b）,c） ） ） ，畫出其圖形，并求其長度和深，畫出其圖形，并求其長度和深 度。度。 第五章第五章 樹和二叉樹樹和二叉樹 一單選題一單選題 1一棵二叉樹的廣義表表示為一棵二叉樹的廣義表表示為 a(b(c),d(e(,g(h),f)，則該二叉樹的高度為（，則該二叉樹的高度為（ ） 。 A A3 3 B B4 4 C C5 5 D D6 6 2右圖中樹的度為（右圖中樹的度為（ ） 。 A 2 B 3 C5 D8 3高度為高度為 h 的完

31、全二叉樹中，結(jié)點(diǎn)數(shù)最多為（的完全二叉樹中，結(jié)點(diǎn)數(shù)最多為（ ） 。 A 2h-1 B 2h+1 C2h-1 D2h 4已知一棵含已知一棵含 20 個(gè)結(jié)點(diǎn)的二叉樹中只有一個(gè)葉子結(jié)點(diǎn)，則該樹中度為個(gè)結(jié)點(diǎn)的二叉樹中只有一個(gè)葉子結(jié)點(diǎn)，則該樹中度為 1 的的 結(jié)點(diǎn)個(gè)數(shù)為（結(jié)點(diǎn)個(gè)數(shù)為（ ） 。 A 0 B 1 C 18 D19 5在一棵具有在一棵具有 n 個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于（個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于（ ） 。 An Bn-1 Cn+1 D2n n 6在一棵深度為在一棵深度為 h 的完全二叉樹中，所有結(jié)點(diǎn)個(gè)數(shù)不小于（的完全二叉樹中，所有結(jié)點(diǎn)個(gè)數(shù)不小于（ ） 。 A A

32、2 2h h B B2 2h+1 h+1 C C 2 2h h-1-1 D D2 2h-1 h-1 7在一棵深度為在一棵深度為 h 的完全二叉樹中，所有結(jié)點(diǎn)個(gè)數(shù)不大于（的完全二叉樹中，所有結(jié)點(diǎn)個(gè)數(shù)不大于（ ） 。 A A2 2h h B B2 2h+1 h+1 C C 2 2h h-1-1 D D2 2h-1 h-1 8在一棵具有在一棵具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹中，分支結(jié)點(diǎn)的最大編號(hào)為（個(gè)結(jié)點(diǎn)的完全二叉樹中，分支結(jié)點(diǎn)的最大編號(hào)為（ ） 。 A. . ( (n+1)/2 B. . ( (n-1)/2 C. . n/2 D. . n/2 9在一棵完全二叉樹中，若編號(hào)為在一棵完全二叉樹中，若編號(hào)為

33、 i 的結(jié)點(diǎn)存在左孩子，則左孩子結(jié)點(diǎn)的編的結(jié)點(diǎn)存在左孩子，則左孩子結(jié)點(diǎn)的編 號(hào)為（號(hào)為（ ） 。 A A2i2i B B2i-12i-1 C C2i+12i+1 D D2i+22i+2 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 10 / 36 10在一棵完全二叉樹中，若編號(hào)為在一棵完全二叉樹中，若編號(hào)為 i 的結(jié)點(diǎn)存在右孩子，則右孩子結(jié)點(diǎn)的編的結(jié)點(diǎn)存在右孩子，則右孩子結(jié)點(diǎn)的編 號(hào)為（號(hào)為（ ） 。 A A2i2i B B2i-12i-1 C C2i+12i+1 D D2i+22i+2 11在一棵完全二叉樹中，對于編號(hào)為在一棵完全二叉樹中，對于編號(hào)為 i（i1）的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號(hào)為

34、）的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號(hào)為 （ ） 。 A A (i+1)/2(i+1)/2 B B (i-1)/2(i-1)/2 C C i/2i/2 D D i/2i/2 12一棵有一棵有 16 個(gè)結(jié)點(diǎn)的完全二叉樹，對它按層編號(hào)，則對編號(hào)為個(gè)結(jié)點(diǎn)的完全二叉樹，對它按層編號(hào)，則對編號(hào)為 7 的結(jié)點(diǎn)的結(jié)點(diǎn) X，它的雙親結(jié)點(diǎn)及右孩子結(jié)點(diǎn)的編號(hào)分別為（，它的雙親結(jié)點(diǎn)及右孩子結(jié)點(diǎn)的編號(hào)分別為（ ） 。 A 2，14 B 2，15 C3，14 D3，15 13由權(quán)值分別為由權(quán)值分別為 3、8、6、2、5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路 徑長度為（徑長度為（ ） 。 A

35、A2424 B B4848 C C7272 D D5353 14利用利用 n 個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有（個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有（ ）個(gè)結(jié)點(diǎn)。）個(gè)結(jié)點(diǎn)。 A An B Bn+1+1 C C2 2n D D2 2n-1 15利用利用 3、6、8、12 這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹 中所有葉子的最長帶權(quán)路徑長度為（中所有葉子的最長帶權(quán)路徑長度為（ ） 。 A A18 B B1616 C C1212 D D3030 二填空題二填空題 1在樹形結(jié)構(gòu)中，根結(jié)點(diǎn)沒有在樹形結(jié)構(gòu)中，根結(jié)點(diǎn)沒有_結(jié)點(diǎn)，其余每

36、個(gè)結(jié)點(diǎn)有且只有結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有_結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可 以以_個(gè)。個(gè)。 2若若 m 叉樹中叉樹中 A 有有 3 個(gè)兄弟，結(jié)點(diǎn)個(gè)兄弟，結(jié)點(diǎn) B 是是 A 的雙親，則結(jié)點(diǎn)的雙親，則結(jié)點(diǎn) B 的度是的度是 _。 3對于一棵具有對于一棵具有 n 個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為 _。 43 個(gè)結(jié)點(diǎn)可以組成個(gè)結(jié)點(diǎn)可以組成_種不同形態(tài)的二叉樹。種不同形態(tài)的二叉樹。 5在一棵二叉樹中，第在一棵二叉樹中，第 5 層上的結(jié)點(diǎn)數(shù)最多為層上的結(jié)點(diǎn)數(shù)最多為_個(gè)。個(gè)。 6深度

37、為深度為 5 的二叉樹至多有的二叉樹至多有_個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 7在一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為在一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為 5 個(gè)，單分支結(jié)點(diǎn)數(shù)為個(gè)，單分支結(jié)點(diǎn)數(shù)為 6 個(gè)，則個(gè)，則 葉子結(jié)點(diǎn)數(shù)為葉子結(jié)點(diǎn)數(shù)為_個(gè)。個(gè)。 8已知二叉樹有已知二叉樹有 50 個(gè)葉子結(jié)點(diǎn)，且僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為個(gè)葉子結(jié)點(diǎn)，且僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為 30，則總結(jié)點(diǎn)，則總結(jié)點(diǎn) 數(shù)為數(shù)為_個(gè)。個(gè)。 9對于一棵具有對于一棵具有 n 個(gè)結(jié)點(diǎn)的二叉樹，對應(yīng)二叉鏈表中指針總數(shù)為個(gè)結(jié)點(diǎn)的二叉樹，對應(yīng)二叉鏈表中指針總數(shù)為 _個(gè)，其中個(gè)，其中_個(gè)用于指向孩子結(jié)點(diǎn)，個(gè)用于指向孩子結(jié)點(diǎn)，_ 個(gè)指針空閑著。個(gè)指針空閑著。 10已知

38、二叉樹的前序遍歷序列為已知二叉樹的前序遍歷序列為 ABDCEFG，中序遍歷序列為，中序遍歷序列為 DBCAFEG，則后序遍歷序列為，則后序遍歷序列為_個(gè)。個(gè)。 11在哈夫曼編碼中，若編碼長度只允許小于等于在哈夫曼編碼中，若編碼長度只允許小于等于 4，則除了已對兩個(gè)字符編，則除了已對兩個(gè)字符編 碼為碼為 0 和和 10 外，還可以最多對外，還可以最多對_個(gè)字符編碼。個(gè)字符編碼。 12已知一棵哈夫曼樹含有已知一棵哈夫曼樹含有 40 個(gè)葉子結(jié)點(diǎn)，則該樹中共有個(gè)葉子結(jié)點(diǎn)，則該樹中共有_個(gè)非個(gè)非 葉子結(jié)點(diǎn)。葉子結(jié)點(diǎn)。 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 11 / 36 三應(yīng)用題三應(yīng)用題 1

39、假定一棵二叉樹的廣義表表示為假定一棵二叉樹的廣義表表示為 a(b(c),d(e,f)，分別寫出對它進(jìn)行先序、，分別寫出對它進(jìn)行先序、 中序、后序、按層遍歷的結(jié)果。中序、后序、按層遍歷的結(jié)果。 先序：先序： 中序：中序： 后序：后序： 按層：按層： 2假定一棵普通樹的廣義表表示為假定一棵普通樹的廣義表表示為 a(b(e),c(f(h,i,j),g),d)，分別寫出先根、后，分別寫出先根、后 根、按層遍歷的結(jié)果。根、按層遍歷的結(jié)果。 先根：先根： 后根：后根： 按層：按層： 3在一份電文中共使用六種字符，即在一份電文中共使用六種字符，即 a、b、c、d、e、f，它們的出現(xiàn)頻率，它們的出現(xiàn)頻率 依次

40、依次 34、5、12、23、8、18，試畫出對應(yīng)編碼哈夫曼樹（要求樹中左孩子結(jié)點(diǎn)，試畫出對應(yīng)編碼哈夫曼樹（要求樹中左孩子結(jié)點(diǎn) 的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值）的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值） ，求出每個(gè)字符的哈夫曼編碼，并求出傳送電，求出每個(gè)字符的哈夫曼編碼，并求出傳送電 文的總長度。文的總長度。 4將下圖所示的二叉樹轉(zhuǎn)換成森林。將下圖所示的二叉樹轉(zhuǎn)換成森林。 5畫出下圖所示森林轉(zhuǎn)換后所對應(yīng)的二叉樹（二叉樹畫在右邊）畫出下圖所示森林轉(zhuǎn)換后所對應(yīng)的二叉樹（二叉樹畫在右邊） 。 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 12 / 36 第六章第六章 圖圖 一單選題一單選題 1設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為設(shè)

41、無向圖的頂點(diǎn)個(gè)數(shù)為 n，則該圖最多有（，則該圖最多有（ ）條邊。）條邊。 An-1 Bn(n-1)/2 Cn(n+1)/2 Dn(n-1) 2在一個(gè)具有在一個(gè)具有 n 個(gè)頂點(diǎn)的無向圖中，每個(gè)頂點(diǎn)度的最大值是（個(gè)頂點(diǎn)的無向圖中，每個(gè)頂點(diǎn)度的最大值是（ ） 。 An Bn-1 Cn+1 D2(n-1) 3在含在含 n 個(gè)頂點(diǎn)個(gè)頂點(diǎn) e 條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（ ） 。 A e B 2e Cn2- e Dn2-2e 4n 個(gè)頂點(diǎn)的連通圖至少有（個(gè)頂點(diǎn)的連通圖至少有（ ）條邊。）條邊。 An-1 Bn Cn+1 D0 5若采用鄰接矩陣存儲(chǔ)具有

42、若采用鄰接矩陣存儲(chǔ)具有 n 個(gè)頂點(diǎn)的一個(gè)無向圖，則該鄰接矩陣是（個(gè)頂點(diǎn)的一個(gè)無向圖，則該鄰接矩陣是（ ） 。 A上三角矩陣上三角矩陣 B稀疏矩陣稀疏矩陣 C對角矩陣對角矩陣 D對稱矩陣對稱矩陣 6有向圖的一個(gè)頂點(diǎn)的度為該頂點(diǎn)的（有向圖的一個(gè)頂點(diǎn)的度為該頂點(diǎn)的（ ） 。 A入度入度 B出度出度 C入度與出度之和入度與出度之和 D （入度（入度+出度）出度）/2 7有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ ）倍。）倍。 A A1/21/2 B B4 4 C C2 2 D D1 1 8對于具有對于具有 e 條邊的無向圖，它的鄰接表中

43、有（條邊的無向圖，它的鄰接表中有（ ）個(gè)弧結(jié)點(diǎn)。）個(gè)弧結(jié)點(diǎn)。 A e-1 B e C2(e-1) D2 e 9一個(gè)連通圖的生成樹是包含圖中所有頂點(diǎn)的一個(gè)（一個(gè)連通圖的生成樹是包含圖中所有頂點(diǎn)的一個(gè)（ ）子圖。）子圖。 A極小極小 B連通連通 C極小連通極小連通 D無環(huán)無環(huán) 10設(shè)有向圖有設(shè)有向圖有 n 個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和 e 條邊，采用鄰接表作為其存儲(chǔ)結(jié)構(gòu)，在進(jìn)行拓?fù)錀l邊，采用鄰接表作為其存儲(chǔ)結(jié)構(gòu)，在進(jìn)行拓?fù)?排序時(shí)，其時(shí)間復(fù)雜度為（排序時(shí)，其時(shí)間復(fù)雜度為（ ） 。 AO(nlog2e) BO(n+e) CO(ne) DO(n2) 11已知一個(gè)圖如下所示，若從頂點(diǎn)已知一個(gè)圖如下所示，若從頂點(diǎn) a

44、 出發(fā)按廣度搜索法進(jìn)行遍歷，則可能得出發(fā)按廣度搜索法進(jìn)行遍歷，則可能得 到的一種頂點(diǎn)序列為（到的一種頂點(diǎn)序列為（ ） 。 a c b e f d Aabcedf Babcefd Caebcfd Dacfdeb 12設(shè)圖的鄰接矩陣為設(shè)圖的鄰接矩陣為 則該圖為（則該圖為（ ） 。 A有向圖有向圖 B無向圖無向圖 C強(qiáng)連通圖強(qiáng)連通圖 D完全圖完全圖 0 1 1 0 0 1 0 1 0 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 13 / 36 13下列有關(guān)圖遍歷的說法中不正確的是（下列有關(guān)圖遍歷的說法中不正確的是（ ） 。 A連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程

45、 B圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出先進(jìn)先出”的特征的特征 C非連通圖不能用深度優(yōu)先搜索法非連通圖不能用深度優(yōu)先搜索法 D圖的遍歷要求每一頂點(diǎn)僅被訪問一圖的遍歷要求每一頂點(diǎn)僅被訪問一 次次 14右圖所示帶權(quán)無向圖的最小生成樹的右圖所示帶權(quán)無向圖的最小生成樹的 權(quán)為（權(quán)為（ ） 。 A14 B15 C17 D 18 二填空題二填空題 1在一個(gè)無向圖中，所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的在一個(gè)無向圖中，所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的_倍。倍。 2在一個(gè)具有在一個(gè)具有 n 個(gè)頂點(diǎn)的無向完全圖中，包含有個(gè)頂點(diǎn)的無向完全圖中，包含有_條邊；在一條邊；在一 個(gè)具有

46、個(gè)具有 n 個(gè)頂點(diǎn)的有向完全圖中，包含有個(gè)頂點(diǎn)的有向完全圖中，包含有_條邊。條邊。 3對于一個(gè)具有對于一個(gè)具有 n 個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和 e 條邊的有向圖和無向圖，在其對應(yīng)的鄰接表?xiàng)l邊的有向圖和無向圖，在其對應(yīng)的鄰接表 中，所含弧結(jié)點(diǎn)分別為中，所含弧結(jié)點(diǎn)分別為_和和_個(gè)。個(gè)。 4在有向圖的鄰接表和逆鄰接表表示中，每個(gè)頂點(diǎn)鄰接表分別鏈接著該頂在有向圖的鄰接表和逆鄰接表表示中，每個(gè)頂點(diǎn)鄰接表分別鏈接著該頂 點(diǎn)的所有點(diǎn)的所有_和和 _結(jié)點(diǎn)。結(jié)點(diǎn)。 5對于一個(gè)具有對于一個(gè)具有 n 個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和 e 條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù) 分別為分別為_和和_。 6

47、在無向圖的鄰接矩陣在無向圖的鄰接矩陣 A 中，若中，若 Aij等于等于 1，則，則 Aji等于等于 _。 7n（n 0）個(gè)頂點(diǎn)的連通無向圖的生成樹有）個(gè)頂點(diǎn)的連通無向圖的生成樹有_條邊。條邊。 8能夠成功完成拓?fù)渑判虻膱D一定是一個(gè)能夠成功完成拓?fù)渑判虻膱D一定是一個(gè)_。 三應(yīng)用題三應(yīng)用題 1對于圖對于圖 a、b，完成下列各題：，完成下列各題： 4 0 3 1 0 3 1 4 7 2 9 2 1 2 3 5 4 求圖求圖 a 中每個(gè)頂點(diǎn)的度，圖中每個(gè)頂點(diǎn)的度，圖 b 中每個(gè)頂點(diǎn)的入度；中每個(gè)頂點(diǎn)的入度； 畫出圖畫出圖 a、b 的鄰接矩陣；的鄰接矩陣； 畫出圖畫出圖 a、b 的鄰接表；的鄰接表； 畫

48、出圖畫出圖 b 的逆鄰接表和十字鏈表。的逆鄰接表和十字鏈表。 2已知圖已知圖 G 的鄰接表如下圖所示，請按如下鄰接表及遍歷算法寫出深度優(yōu)的鄰接表如下圖所示，請按如下鄰接表及遍歷算法寫出深度優(yōu) 先和廣度優(yōu)先遍歷的頂點(diǎn)序列。先和廣度優(yōu)先遍歷的頂點(diǎn)序列。 V0 2 1 3 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 14 / 36 V1 0 V2 0 1 V3 3 3分別用普里姆和克魯斯卡爾算法構(gòu)造下圖所示網(wǎng)絡(luò)的最小生成樹。分別用普里姆和克魯斯卡爾算法構(gòu)造下圖所示網(wǎng)絡(luò)的最小生成樹。 V2 4 7 8 V5 V1 6 V3 4 6 2 9 V4 4寫出下圖所示的所有拓?fù)湫蛄小懗鱿聢D所示的所有拓

49、撲序列。 1 2 3 5 6 4 5已知帶權(quán)圖已知帶權(quán)圖 G 如下圖所示，畫出圖如下圖所示，畫出圖 G 的一棵最小生成樹。的一棵最小生成樹。 6對于下圖，試給出：對于下圖，試給出： 鄰接矩陣鄰接矩陣 鄰接表鄰接表 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 15 / 36 7已知無向圖已知無向圖 G 的鄰接表如下圖所示，請寫出從頂點(diǎn)的鄰接表如下圖所示，請寫出從頂點(diǎn) V2開始的深度優(yōu)先搜開始的深度優(yōu)先搜 索序列。索序列。 0 V1 2 1 1 V2 4 3 2 0 2 V3 1 0 3 4 3 V4 1 2 4 4 V5 1 2 3 第七章第七章 查找查找 一單選題一單選題 1在一個(gè)長度為

50、在一個(gè)長度為 n 的順序表中順序查找值為的順序表中順序查找值為 x 的元素時(shí)，在等概率情況下，的元素時(shí)，在等概率情況下， 查找成功時(shí)的平均查找長度為（查找成功時(shí)的平均查找長度為（ ） 。 An Bn/2 C(n+1)/2 D(n-1)/2 2對長度為對長度為 10 的順序表進(jìn)行查找，若查找前面的順序表進(jìn)行查找，若查找前面 5 個(gè)元素的概率相同，均為個(gè)元素的概率相同，均為 1/8，查找后面，查找后面 5 個(gè)元素的概率相同，均為個(gè)元素的概率相同，均為 3/40，則查找任一元素的平均查找長，則查找任一元素的平均查找長 度為（度為（ ） 。 A5.5 B5 C39/8 D19/4 3對長度為對長度為

51、n 的單鏈有序表，若查找每個(gè)元素的概率相等，則查找任一元的單鏈有序表，若查找每個(gè)元素的概率相等，則查找任一元 素的平均查找長度為（素的平均查找長度為（ ） 。 An/2 B(n+1)/2 C(n-1)/2 Dn/4 4采用二分查找法，若當(dāng)前取得的中間位置采用二分查找法，若當(dāng)前取得的中間位置 mid 的元素值小于被查找值，的元素值小于被查找值， 則表明待查元素可能在表的后半部分，下次查找的起始位置通常應(yīng)（則表明待查元素可能在表的后半部分，下次查找的起始位置通常應(yīng)（ ） 。 A從從 mid/2 位置開始位置開始 B從從 mid 位置開始位置開始 C從從 mid-1 位置開始位置開始 D從從 mid

52、 +1 位置開始位置開始 5對于長度為對于長度為 n 的順序存儲(chǔ)的有序表，若采用二分查找，則對所有元素的的順序存儲(chǔ)的有序表，若采用二分查找，則對所有元素的 最長查找長度為（最長查找長度為（ ）的值的向下取整加）的值的向下取整加 1。 Alog2(n+1) Blog2n Cn/2 D(n+1)/2 6對于長度為對于長度為 9 的順序存儲(chǔ)的有序表，若采用二分查找，在等概率情況下的順序存儲(chǔ)的有序表，若采用二分查找，在等概率情況下 的平均查找長度為（的平均查找長度為（ ） 。 A20/9 B18/9 C25/9 D22/9 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 16 / 36 7對于順序存

53、儲(chǔ)的有序表（對于順序存儲(chǔ)的有序表（5、12、20、26、37、42、46、50、64） ，若采，若采 用二分查找，則查找元素用二分查找，則查找元素 26 的查找長度為（的查找長度為（ ） 。 A2 B3 C4 D5 8對具有對具有 n 的順序存儲(chǔ)的有序表，若采用二分查找，則算法的時(shí)間復(fù)雜度的順序存儲(chǔ)的有序表，若采用二分查找，則算法的時(shí)間復(fù)雜度 為（為（ ） 。 AO(n) BO(n2) CO(1) DO(log2n) 9在索引查找中，若用于保存數(shù)據(jù)元素的主表的長度為在索引查找中，若用于保存數(shù)據(jù)元素的主表的長度為 n，它被均分為，它被均分為 k 個(gè)個(gè) 子表，每個(gè)子表的長度均為子表，每個(gè)子表的長度

54、均為 n/k，則索引查找的平均查找長度為（，則索引查找的平均查找長度為（ ） 。 An+k Bk+n/k C(k+n/k)/2 D(k+n/k)/2+1 10在一棵深度為在一棵深度為 h 且具有且具有 n 個(gè)元素的二叉排序樹中，搜索一個(gè)元素的最大個(gè)元素的二叉排序樹中，搜索一個(gè)元素的最大 搜索長度（即經(jīng)比較的結(jié)點(diǎn)數(shù)）為（搜索長度（即經(jīng)比較的結(jié)點(diǎn)數(shù)）為（ ） 。 A n Blog2n Ch/2 Dh 11在由在由25，30，16，48按照依次插入結(jié)點(diǎn)的方法生成的一棵二叉排序樹中，按照依次插入結(jié)點(diǎn)的方法生成的一棵二叉排序樹中， 在等概率情況下成功搜索一個(gè)元素的平均搜索長度為（在等概率情況下成功搜索一

55、個(gè)元素的平均搜索長度為（ ） 。 A 2 B2.5 C3 D4 12在下列各棵二叉樹中，二叉排序樹是（在下列各棵二叉樹中，二叉排序樹是（ ） 。 13若根據(jù)數(shù)據(jù)集合若根據(jù)數(shù)據(jù)集合23，44，36，48，52，73，64，58建立散列表，采用建立散列表，采用 h(K)=K%7 計(jì)算散列計(jì)算散列 XXX，則同義詞元素的個(gè)數(shù)最多為（，則同義詞元素的個(gè)數(shù)最多為（ ）個(gè)。）個(gè)。 A1 B2 C3 D4 14對于哈希函數(shù)對于哈希函數(shù) H（key）=key%13，被稱為同義詞的關(guān)鍵字是（，被稱為同義詞的關(guān)鍵字是（ ） 。 A35 和和 41 B23 和和 39 C15 和和 44 D25 和和 51 15若

56、根據(jù)數(shù)據(jù)長度為若根據(jù)數(shù)據(jù)長度為 m 的閉散列表，采用線性探測法處理沖突，假定對一的閉散列表，采用線性探測法處理沖突，假定對一 個(gè)元素第一次計(jì)算的散列個(gè)元素第一次計(jì)算的散列 XXX 為為 d，則下一次的散列，則下一次的散列 XXX 為（為（ ） 。 Ad Bd+1 C(d+1)/m D(d+1)%m 二填空題二填空題 1長度為長度為 n 的順序表，采用設(shè)置崗哨方法順序查找，若查找不成功，其查的順序表，采用設(shè)置崗哨方法順序查找，若查找不成功，其查 找長度為找長度為_。 2以順序查找方法從長度為以順序查找方法從長度為 n 的順序表中查找一個(gè)元素時(shí)，平均查找長度的順序表中查找一個(gè)元素時(shí)，平均查找長度

57、為為_，時(shí)間復(fù)雜度為，時(shí)間復(fù)雜度為_。 真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。 17 / 36 3以二分查找方法從長度為以二分查找方法從長度為 12 的有序表中查找一個(gè)元素時(shí)，平均查找長度的有序表中查找一個(gè)元素時(shí)，平均查找長度 為為_。 4在索引表中，每個(gè)索引項(xiàng)至少包含有在索引表中，每個(gè)索引項(xiàng)至少包含有_域和域和_ 域這兩項(xiàng)。域這兩項(xiàng)。 5假定對長度假定對長度 n=100 的數(shù)據(jù)表進(jìn)行索引查找，并假定每個(gè)子表的長度均為的數(shù)據(jù)表進(jìn)行索引查找，并假定每個(gè)子表的長度均為 ，則進(jìn)行索引查找的平均查找長度為，則進(jìn)行索引查找的平均查找長度為_。n 6在線性表的散列存儲(chǔ)中，裝填因子在線性表的散列存

58、儲(chǔ)中，裝填因子 又稱為裝填系數(shù)，若用又稱為裝填系數(shù)，若用 m 表示散列表示散列 表的長度，表的長度，n 表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則 等于等于_。 7在線性表的散列存儲(chǔ)中，處理沖突有在線性表的散列存儲(chǔ)中，處理沖突有_和和_兩兩 種方法。種方法。 三應(yīng)用題三應(yīng)用題 1已知一組元素為（已知一組元素為（46，25，78，62，12，37，70，29）,試畫出按元素排試畫出按元素排 列順序輸入生成的一棵二叉排序樹的過程。列順序輸入生成的一棵二叉排序樹的過程。 2對長度為對長度為 12 的有序表進(jìn)行二分查找，試畫出它的一棵判定樹。的有序表進(jìn)行二分查找，試畫出它的一棵判定樹

59、。 3已知一棵二叉排序樹的廣義表表示為已知一棵二叉排序樹的廣義表表示為(28(12(,16),49(34(30),72(63)，若從，若從 中依次刪除中依次刪除 72、12、49、28 結(jié)點(diǎn)，試分別畫出每刪除一個(gè)結(jié)點(diǎn)后得到的二叉結(jié)點(diǎn)，試分別畫出每刪除一個(gè)結(jié)點(diǎn)后得到的二叉 排序樹。排序樹。 第八章第八章 排序排序 一單選題一單選題 1若對若對 n 個(gè)元素進(jìn)行直接插入排序，在進(jìn)行第個(gè)元素進(jìn)行直接插入排序，在進(jìn)行第 i 趟（趟（1in-1in-1）排序時(shí)，）排序時(shí)， 為尋找插入位置最多需要進(jìn)行（為尋找插入位置最多需要進(jìn)行（ ）次元素的比較。）次元素的比較。 Ai+1 Bi-1 Ci D1 2在對在對

60、 n 個(gè)元素進(jìn)行快速排序的過程中，最好情況下需要進(jìn)行（個(gè)元素進(jìn)行快速排序的過程中，最好情況下需要進(jìn)行（ ）層劃）層劃 分。分。 An Bn/2 Clog2n D2n 3若對若對 n 個(gè)元素進(jìn)行直接選擇排序，則進(jìn)行任一趟排序的過程中，尋找最個(gè)元素進(jìn)行直接選擇排序，則進(jìn)行任一趟排序的過程中，尋找最 小值元素的時(shí)間復(fù)雜度為（小值元素的時(shí)間復(fù)雜度為（ ） 。 AO(1) BO(log2n) CO(n2) DO(n) 4若對若對 n 個(gè)元素進(jìn)行歸并排序，則進(jìn)行歸并的趟數(shù)為（個(gè)元素進(jìn)行歸并排序，則進(jìn)行歸并的趟數(shù)為（ ） 。 An Bn-1 Cn/2 D log2n 5若一個(gè)元素序列基本有序，則選用（若一個(gè)