電子科技大學(xué)期末數(shù)據(jù)結(jié)構(gòu)試題及答案

1.棧和隊(duì)列的共同特點(diǎn)是(A)。2.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)(D).3.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？(D)5.樹(shù)最適合用來(lái)表示(C)。D.2k-110.設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有(A)條邊才能確保是一個(gè)連通圖。1.通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：正確性易讀性強(qiáng)壯性和_高效率。3.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};1.LinkListmynote(LinkListL)returnL；ifBT{{returnfalse;//查找失敗else{if(item==BST->data){item=BST->data;//查找成功return___________;}elseif(item<BST->data)returnFind(______________,item);elsereturnFind(_______________,item);}//if}(C)(R-F+M)％M(D)(F-R+M)％M得到序列為（）(A)n(n-1)/2(B)n(n-1)(C)n2(A)9(A)n-1(B)nif(stack.top==m-1)printf("overflow");4.快速排序的最壞時(shí)間復(fù)雜度為_(kāi)__________，平均時(shí)間復(fù)雜度為_(kāi)_________。的初始堆為_(kāi)__________________________。（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink）(A)O(n)(B)O(n2)列為（）(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)；(C)q=p->next；p->next=q->next；free(q)；(D)q=p->next；p->data=q->data；free(q)；(A)1(B)n(C)nlog2n(D)n2(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，21(A)O(1)(B)O(log2n)為（）(A)n，e(C)2n，e(D)n，2e(A)n(n-1)(D)n(n+1)4.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和inti,j;j=i=k%p;bitree*bstsearch(bitree*t,intk)if(t==0)return(0);elsewhile(t!=0)(A)O(n)(B)O(nlog2n)(A)2k-1(B)2k(C)2k-1(D)2k-1(A)n(B)e(A)O(1)(B)O(n)(C)O(log2n)(A)n(B)n-1(A)3(B)4超過(guò)（）(B)log2n-1(C)log2n(D)log2(n+1)針域分別為llink和rlink）4．深度為k的完全二叉樹(shù)中最少有____________個(gè)結(jié)點(diǎn)。則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)________個(gè)隊(duì)inti,k;lklist*s;1、畫出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表存儲(chǔ)結(jié)構(gòu)。3、設(shè)散列表的地址范圍是[0..9]，散列函數(shù)為H（key）=（key2+2）MOD9,并采用鏈(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20果為（）4．函數(shù)substr("DATASTRUCTURE"，5，9)的返回值為（）(A)"STRUCTURE"(B)"DATA"(C)"ASTRUCTUR"(A)O(log2n)(B)O(1)(A)abedfc(B)acfebd(A)n-i(B)n-1-i(C)n+1-i(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，802.在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是____________________。上元素）存放在n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中，則A[i][j]與A[0][0]之間有_______個(gè)于頂點(diǎn)i的________，第i列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的__________。voidbubble(intr[n])之和為（）(A)[41，12，34，45，27]55[72，63](B)[45，34，12，41]55[72，63，27](C)[63，12，34，45，27]55[41，72](D)[12，27，45，41]55[34，63，72](A)3(B)4(A)O(n)(B)O(n2)(C)O(n1/2)(A)O(n)(B)O(n2)(C)O(nlog2n)(A)2k-1-1(B)2k-1(D)2k-1(A)front->next=s；front=s；(B)s->next=rear；rear=s；(C)rear->next=s；rear=s；(D)s->next=front；front=s；(B)O(n2)(A)O(n)(B)O(n2)(C)O(nlog2n)二、判斷題(20分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時(shí)間復(fù)雜度為_(kāi)________。的語(yǔ)句序列為_(kāi)_________________________（設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext）四、算法設(shè)計(jì)題(20分)(B)n(C)n/2(D)n(n-1)(A)n(B)n-1(A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80(A)2i+1(B)2i(C)i/2(D)2i-1(A)O(n)(B)O(nlog2n)(D)O(n3/2)(A)1(B)2(A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next;二、判斷題(20分)10.帶權(quán)無(wú)向圖的最小生成樹(shù)是唯一的。）的后面插入結(jié)點(diǎn)X的操作序列為_(kāi)________=p；s->right=p->right；__________=s；p->right->left=s；（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right）4.解決散列表沖突的兩種方法是________________和__________________。的結(jié)果的是__________________________________。的結(jié)果的是__________________________________。while(i<j&&r[j].key>x.key)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(____________________)i=i+1;if(i<j){r[j]=r[i];j=j-1;}1.字符串的長(zhǎng)度是指（）(A)O(n)(B)O(1)(D)O(log2n)3.兩個(gè)字符串相等的充要條件是（）(A)O(n)(C)O(nlog2n)6.設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過(guò)程中比較(A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4](A)8(B)7(A)5(B)6(A)aedfcb(B)acfebd二、判斷題(20分)2.設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。）4.二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。）6.如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。）7.非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。）O(n)。）過(guò)。）一趟希爾排序結(jié)束后的結(jié)果為_(kāi)____________________________。voidbstinsert(bitree*&t,intk)中的兩個(gè)指針域分別為llink和rlink）7．設(shè)有向圖中不存在有向邊<Vi,Vj>，則其對(duì)應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等排序結(jié)束后的結(jié)果為_(kāi)____________________________。四、算法設(shè)計(jì)題(20分)for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；(A)O(m*n*t)(A)n-i(B)n+l-i(C)n-1-i(D)i(A)O(n)(B)O(nlog2n)(A)n-i(B)n-1-i(C)n+l-i(A)4(B)5(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/2(A)n(B)n/2(C)(n+1)/2(D)(n-1)/2(A)1(B)2找長(zhǎng)度為（）(A)6(D)6.5(B)2，3，4，1(C)1，4，2，3(D)1，2，4，3(A)4(B)51)s->next=___________；2)p->next=s；3)t=p->data；4)p->data=___________；5)s->data=t；用篩選法建成的初始堆為_(kāi)______________________。和為_(kāi)________________。三、判斷題(20分)5．希爾排序算法的時(shí)間復(fù)雜度為O(n2)。()數(shù)有關(guān)。()五、算法設(shè)計(jì)題(20分)(A)O(n1/2)(B)O(n1/3)(A)s->next=p->next；p->next=-s；(B)q->next=s；s->next=p；(C)p->next=s->next；s->next=p；(D)p->next=s；s->next=q；每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，A[5][4