《數(shù)據(jù)結(jié)構(gòu)》單元測試(含答案)_第1頁
《數(shù)據(jù)結(jié)構(gòu)》單元測試(含答案)_第2頁
《數(shù)據(jù)結(jié)構(gòu)》單元測試(含答案)_第3頁
已閱讀5頁,還剩9頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)

文檔簡介

《數(shù)據(jù)結(jié)構(gòu)》單元測試1一、選擇題(每題2分,共40分)11.?dāng)?shù)據(jù)的最小單位是(A)。(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量棧和隊列的共同特點(A )。只允許在端點處插入和刪除元素都是先進后出 (C)都是先進先出(D)沒有共同點用鏈接方式存儲的隊列,在進行插入運算(D )。(A)僅修改頭指針 (B)頭、尾指針都要修改(C)僅修改尾指針 頭、尾指針可能都要修以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)D )隊列 (B)棧 (C)線性表 (D)二叉樹55substr(“DATASTRUCTURE”,5,9)的返回值為(A)。(A)“STRUCTURE”(B)“DATA”(C)“ASTRUCTUR”(D)“DATASTRUCTURE”6n個結(jié)點,現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序,則該操作的時間復(fù)雜度為(。(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)7m01的結(jié)點數(shù)為Nl,……mNmN0=(。(A)Nl+N2+……+Nm(B)1+N2+2N3+3N4+……+(m-1)Nm(C)(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm1000X最多需要比較(B)次。(A)25(B)10(C)7(D)1二叉樹的第k層的結(jié)點數(shù)最多( D。(A)2k-1 (B)2K+1 (C)2K-1 (D)2k-1樹最適合用來表( C )。有序數(shù)據(jù)元素 (B)無序數(shù)據(jù)元素(C)元素之間具有分支層次關(guān)系的數(shù)據(jù)(D)元素之間無聯(lián)系的數(shù)據(jù)11.n個權(quán)構(gòu)成一棵Huffman樹,其節(jié)點總數(shù)( A。(A)2n-1 (B)2n (C)2n+1 (D)不確定1212.下面程序的時間復(fù)雜為(B)i<=n;i++)(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)p需要修改指針的操作序列為(。(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);14Gne條邊,則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為(。(A)n(A)n,e(B)e,n(C)2n,e(D)n,2e15.n(條邊。(A)n(n-1)(B)n+1(C)n(D)n(n+1)下面關(guān)于線性表的敘述錯誤的是(D。線性表采用順序存儲必須占用一片連續(xù)的存儲空間線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為(B)個空指針域。(A)2m-1 (B)2m (C)2m+1 (D)4m設(shè)順序循環(huán)隊列F和RFR總是指向隊尾元素的當(dāng)前位置,則該循環(huán)隊列中的元素個數(shù)為(。(A)R-F (B)F-R (C)(R-F+M)%M(D)(F-R+M)%M設(shè)某棵二叉樹的中序遍歷序列為ABC(A。BADC (B)BCDA (C)CDAB (D)CBDA設(shè)某完全無向圖中有n個頂點則該完全無向圖中(條邊(A)n(n-1)/2 (B)n(n-1) (C)n2 (D)n2-1二、填空題(每題2分,共28分)1.在有n個結(jié)點的二叉鏈表中,空鏈域的個數(shù)n+1 。2. 2. [0..30]

中,front指向隊頭元素的前一個位置,rear指向隊尾元素。若front=25,rear=5,則該隊列的元素個數(shù)為 11 。設(shè)源串模式串按KMP算法進行模式匹配,當(dāng)“S2S3S4”=“P1P2P3”,而S5≠P4時,S5應(yīng)與 p2 比較。假設(shè)以一維數(shù)組nA的存儲空間,以行A A [6][1]

的值存儲在

S[_16__]中。單循環(huán)鏈表L中指針P所指結(jié)點為尾結(jié)點的條件 =L 。

p->next若一棵樹中度為1的結(jié)點有N1個,度為2結(jié)點有N2個,……為m的結(jié)點有Nm個,則該樹的葉結(jié)點有1+N2+2N3+…+(m-1)Nm 個。設(shè)某二叉樹的前序和中序序列均為ABCDE,則它的后序序列EDCBA 。圖的遍歷方法主要是 寬度優(yōu)先搜索深度優(yōu)先索 。一棵有n個葉子結(jié)點的哈夫曼樹共2n-1 個結(jié)點。有時在單鏈表的第一個結(jié)點之前附加一頭結(jié)"其作用 避免在插入和刪除操作中將第一個結(jié)點看作是特殊結(jié)點使程序編簡單 。求解圖的最小生成樹的算法有兩個,分別是 Prim算法Kruskal算法 。對于任意一棵二叉樹如果其葉結(jié)點數(shù)為度為1的結(jié)點數(shù)N1,度為2的結(jié)點數(shù)為N2,則N0= N2+。一棵有N個葉子結(jié)點的Huffman樹,共2n-1 個結(jié)點。14、假設(shè)用一維數(shù)組A{0..m}作為循環(huán)隊列Q的存儲空間,front和rear分別表示該隊列的隊頭和隊尾指針,則該隊列的隊空條件是 front==rear ,隊滿條件是 (rear+1)%(m+1)front 。稀疏矩陣的存儲方法主要有兩個:一個是 三元組表法 ,另一個是十字鏈表示法。三、解答題1、根據(jù)圖的鄰接表畫鄰接矩陣(12分)四、算法設(shè)計題1、設(shè)采用鄰接表作為有向圖的存儲結(jié)構(gòu),試編寫算法:計算有向圖中每個頂點的出度和入度。(20分)typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{intdata;intin;intout;ArcNode*firstarc;}VNode;typedefstruct{VNodevertices[NUM];intvexnum;intarcnum;}AlGraph;//獲得結(jié)點的入度和出度voidGetInAndOut(AlGraph&g)//開始時所有結(jié)點的入度出度為0{inti;ArcNode*p;for(i=0;i<g.vexnum;i++){p=g.vertices[i].firstarc;while(p!=NULL){g.vertices[i].out++;g.vertices[p->adjvex].in++;p=p->nextarc;}《數(shù)據(jù)結(jié)構(gòu)》各章課后作業(yè)答案第一章緒論課后作業(yè)答案簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點。答:線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的,非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是多對多的。分析下面各程序段的時間復(fù)雜度(520)(1)for(i=0;i<n;i++)

(2)s=0;for(j=0;j<m;j++) for(i=0;i<n;i++)A[i][j]=0; for(j=0;j<n;(3)x=0; (4)i=1; s+=B[i][j];for(i=1;i<n;i++) wh=n)for循環(huán)執(zhí)行n+1for循環(huán)執(zhí)行n(m+1)for(j=1;j<=n-i;j++)執(zhí)行n*m次,此程序段總的執(zhí)行次數(shù)為n+1+n*(m+1)+n*m=2nm+3。故時間復(fù)雜度為O(n*m)。x++;

答:O(n2)算法的時間復(fù)雜度是由嵌套最深層語句的執(zhí)行次數(shù)決定的,本程序段嵌套最深層語句為:s+=B[i][j];它的執(zhí)行次數(shù)為n2,所以本程序段的時間復(fù)雜度是O(n2)。該算法的基本操作是語句x++,其語句頻度為:n1ni1=n1(ni)=n(n1)2i1j1所以本程序段的時間復(fù)雜度是O(n2)。4.設(shè)語句執(zhí)行m次,則有

i03m≤nm≤logn3所以本程序段的時間復(fù)雜度為O(logn)。3第二章線性表課后作業(yè)答案填空題。個數(shù)與有關(guān)。線性表中結(jié)點的集合是有限 的,結(jié)點間的關(guān)系是一對的。向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時,需向后動 n-i+1 個元素。順序表中邏輯上相鄰的元素的物理位置必定相鄰 。單鏈表中邏輯上相鄰元素的物理位置不一定相鄰。試寫一算法,對單鏈表實現(xiàn)就地逆置。分析:將單鏈表就地逆置,即不另外開辟結(jié)點空間,而將鏈表元素翻轉(zhuǎn)順序。解:從鏈上依次取下結(jié)點,按照逆序建表的方法重新建表。voidReverse(LinkList&L){p=L->next; //原鏈表L->next=NULL; //while(p){//從原鏈表中取下結(jié)點ss=p;p=p->next;//LL->next=s;}}第三章棧和隊列課后作業(yè)答案1、填空題。棧是一種特殊的線性表,允許插入和刪除運算的一端稱為 棧頂 不允許插入和刪除運算的一端稱為 棧底 。隊列 是被限定為只能在表的一端進行插入運算,在表的另一端進行刪除算的線性表。在具有n個單元的循環(huán)隊列中,隊滿時共有n-1 個元素2.計算題。設(shè)循環(huán)隊列的容量為40(序號從0到3,現(xiàn)經(jīng)過一系列的入隊和出隊運算后,有①front=11,rear=19;②front=19,rear=11多少個?解:用隊列長度計算公式:(N+r-f)%N①L=(40+19-11)%40=8 ②L=(40+11-19)%40=32寫出下列程序段的輸出結(jié)果(棧的元素類型SElemType為charvoidmain(){StackS;charx,y;InitStack(S);x=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);}輸出結(jié)果為“stac第四章串課后作業(yè)答案算法填空題。Stt第一次出現(xiàn)在主串s返回-1。intindex(chars[],chart[]){inti=0,j=0;while( ① ){if(s[i+j]==t[j])j++;else{ ② ; ③ ;}}if( ④ )retrunelsereturn–1;}解:可以參照課本上模式匹配算法中的BF算法思想。答案為:①i<strlen(s)&&j<strlen(t)②i++③j=0④j>=strlen(t)t=”ABCABCACAB”nextnextval解:j12345678910模式串ABCABCACABnext[j]0111234512nextval[j]0110110501第五章數(shù)組和廣義表課后作業(yè)答案1、選擇題。a[1..60,1..70]20482為主序順序存儲,則元素a[32,58]的存儲地址為8950 。00i-c1)]*L得:LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2=8950一個二維數(shù)組A,行下標(biāo)的范圍是1到6,列下標(biāo)的范圍是0到7,每個數(shù)組元素用相鄰的6個字節(jié)存儲存儲器按字節(jié)編址那么這個數(shù)組的體積是 288 個字節(jié)三元素組表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素它包含有三個數(shù)據(jù)項分別表示該元素的行下標(biāo) 、列下標(biāo) 和 元素值 。求下列廣義表操作的結(jié)果:①GetHead【((a,b),(c,d))】=(a,b) ;②GetHead【GetTail【((a,b),(c,d))= (c,d) ;//頭元素不必加括號③GetHead【GetTail【GetHead【((a,b),(c,d))】= b ;④GetTail【GetHead【GetTail【((a,b),(c,d))】= (d) ;2、遞歸算法比非遞歸算法花費更多的時間,對嗎?為什么?不一定。時間復(fù)雜度與樣本個數(shù)n歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的,循環(huán)的次數(shù)也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同,遞歸用棧隱含循環(huán)次數(shù),非遞歸用循環(huán)變量來顯示循環(huán)次數(shù)而已。第六章樹和二叉樹課后作業(yè)答案1、填空題。(1)一棵完全二叉樹有1000個結(jié)點,則它必有 500個葉子結(jié)點,有499 個度為2的結(jié)點,有 1 個結(jié)點只有非空左子樹,有 0 個結(jié)點只有非空右子樹分析題意已知n=1000,求n0和n2,還要判斷末葉子是掛在左邊還是右邊?1:易求出總層數(shù)和末層葉子數(shù)??倢訑?shù)k=

n+1=10;且前9層總結(jié)點數(shù)為229-1=511(完全二叉樹的前k-1層肯定是滿的),所以末層葉子數(shù)為1000-511=489個。由于4891可能出現(xiàn)非空右子樹(0請注意葉子結(jié)點總數(shù)≠末層葉子數(shù)!還應(yīng)當(dāng)加上第k-1層(靠右邊)的0根據(jù)分析末層的489個葉子只占據(jù)了上層的245個結(jié)點(498/2)上層k=9)右邊的029-1-245=11=489(末層)+11(k-1)=5002的結(jié)點=葉子總數(shù)-1=499解2:可先求2度結(jié)點數(shù),再由此得到葉子總數(shù)。2(完全二叉。另外,末層葉子(剛才已求出為489)所對應(yīng)的雙親也是度(共有498/2=244個。所以,全部2度結(jié)255(k-2244(k-1)=499=21=500用二叉鏈表存儲n個結(jié)點的二叉(n>0),共有 n+1 個空指針域;采用三叉鏈表存儲,共有 n+2 個空指針域。2:2nn-1=2n-(n-1)=n+13nn-1n-1=n+2。由3個結(jié)點所構(gòu)成的二叉樹有 5 種形態(tài)。1n2n解2:含有n個結(jié)點的不相似的二叉樹的棵數(shù)為n1C (即為Catalan數(shù))去計算。n2n1n2n當(dāng)n=3時,n1C =5。n2n2、假設(shè)一棵二叉樹的層序序列為ABCDEFGHIJ和中序序列為DBGEHJACIF。請畫出該樹?!窘獯稹?、編寫遞歸算法,計算二叉樹中葉子結(jié)點的數(shù)目?!痉治觥繉⑵浯蛴〕鰜怼!窘獯稹縤ntLeafCount_BiTree(BitreeT){//求二叉樹中葉子結(jié)點的數(shù)if(!T) return0;//空樹沒有葉子elseif(!T->lchild&&!T->rchild) return1; //elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子樹的葉子數(shù)加上右子樹的葉子數(shù)}//LeafCount_BiTree第七章圖課后作業(yè)答案1、填空題。圖有鄰接矩陣、鄰接表深度優(yōu)先遍歷、度優(yōu)先遍歷等方法。Gii出度。如果n個頂點的圖是一個環(huán),則它有 n 棵生成樹。圖的逆鄰接表存儲結(jié)構(gòu)只適用于 有向 圖。用Dijkstra遞增次序來得到最短路徑的。拓?fù)渑判蛩惴ㄊ峭ㄟ^重復(fù)選擇具有 0 個前驅(qū)頂點的過程來完成的2、求解下圖的最小生成樹,并計算出它的權(quán)值。解:圖的最小生成樹如下:最小生成樹的權(quán)值為1+5+4+2+3=15。第九章查找課后作業(yè)答案1、填空題。具有11個元素的有序表進行折半查找,則平均查找長度為 3,3 。解:先看一個具體的情況,假設(shè)表長n=11。i為有序表中元素的位置,Ci為在折半查找過程中比較的次數(shù)。i1234567891011Ci34234134234ASL=(1×1+2×2+3×4+4×4)/11=3.3。bs在各種查找方法中,平均查找長度與結(jié)點個數(shù)n散列查找。在分塊查找方法中,首先查找 索引表,然后再查找相應(yīng)的塊表 。在散列函數(shù)H(key)=key%m中,m/r

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論