《數(shù)據(jù)結(jié)構(gòu)》單元測(cè)試(含答案)

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

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

的值存儲(chǔ)在

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

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

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

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

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