廣州大學(xué)2017-2018學(xué)年第二學(xué)期考試卷課程《數(shù)據(jù)結(jié)構(gòu)》考試形式（閉卷，考試）物理與電子工程學(xué)院電子系電子061、062、063專業(yè)學(xué)號姓名題號一二三四總分評卷人1234100分分判斷題（對打√，錯打×。每題1分，共15分）在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因此可以從頭結(jié)點進(jìn)行查找任何一個元素。()線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)。()完全二叉樹的某結(jié)點若無左孩子，則必定是葉子結(jié)點。()無向圖用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩陣元素之和的一半。()在圖結(jié)構(gòu)中，結(jié)點可以沒有任何前趨和后繼（）。在拓?fù)渑判蛐蛄兄校我鈨蓚€相繼結(jié)點vi和vj都存在從vi到vj的路徑。()結(jié)點數(shù)固定的二叉樹中，完全二叉樹具有最小路徑長度()。中序線索樹中，右線索若不為空，則一定指向其雙親結(jié)點()。有向圖用鄰接矩陣表示，容易實現(xiàn)求結(jié)點度數(shù)的操作()。二叉樹是度最大為2的有序樹()。11、按廣度優(yōu)先搜索遍歷圖時，與始點相鄰的結(jié)點先于不與始點相鄰的結(jié)點訪問()若有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓?fù)渑判蛐蛄斜囟ù嬖?)。若有向圖G中包含一個環(huán)，則G的結(jié)點間不存在拓?fù)渑判?)。圖的拓?fù)渑判蛐蛄惺俏ㄒ坏?)。網(wǎng)絡(luò)的最小代價生成樹是惟一的（）。二、選擇題（每題2分，共20分）1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。A．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C．線性結(jié)構(gòu)和非線性結(jié)構(gòu) D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2．常對數(shù)組進(jìn)行的兩種基本操作是()。A．建立與刪除 B．索引和修改C．查找和修改 D．查找和索引3．下列結(jié)論中不正確的是()。A．按廣度優(yōu)先搜索遍歷圖時，與始點相鄰的結(jié)點先于不與始點相鄰的結(jié)點訪問。B．一個圖按廣度優(yōu)先搜索法遍歷的結(jié)果是唯一的。C．無向圖的鄰接表表示法中，表中結(jié)點的數(shù)目是圖中邊的條數(shù)2倍。D．圖的多重鄰接表表示法中，表中結(jié)點的數(shù)目是圖中邊的條數(shù)。4．已知一個圖如下所示，則由該圖得到的一種拓?fù)湫蛄袨椋ǎ?123456（A）v1,v4,v6,v2,v5,v3(B)v1,v2,v3,v4,v5,v6(C)v1,v4,v2,v3,v6,v5(D)v1,v2,v4,v6,v3,v5設(shè)有一個堆棧，元素進(jìn)棧的次序為12345。不可能得到()出棧序列：A．12345 B．54321 C．45312 D．43521設(shè)n為正整數(shù)。下列程序段中前置以記號@的語句的頻度為（）。i=1;k=0;while(i<n-1){@ k+=10*i; i++; }A．n B．n-1 C．n-2 D．n-37．具有n個頂點且每一對不同的頂點之間都有一條邊的圖被稱為()。A．線性圖 B．無向完全圖 C．無向圖 D．簡單圖8．下列結(jié)論中正確的是()。A．在無向圖中，邊的條數(shù)是結(jié)點度數(shù)之和。B．用Prim算法和Kruskal算法求得的圖的最小生成樹相同。C．在圖的鄰接多重表表示中，任意一條邊只用一個表目表示。D．在拓?fù)渑判蛐蛄兄校我鈨蓚€相繼結(jié)點vi和vj都存在從vi到vj的路徑。9．循環(huán)隊列Q采用數(shù)組空間Q.base[0,n-1]存放其元素值，已知其頭尾指針分別是front和rear，則判斷此循環(huán)隊列Q為空的條件是()。A．Q.rear–Q.front==n B．Q.rear–Q.front-1==nC．Q.rear==Q.front D．Q.rear+1==Q.frontabecdabecdfA．a(chǎn)becdfB．a(chǎn)cfebdC．a(chǎn)cebfdD．a(chǎn)cfdeb三、問答題（共30分）1．指出樹和二叉樹的主要差別。對于一個有1004個結(jié)點的二叉樹，樹葉最多有多少個？最少有多少個？（4分）畫出和下列已知序列對應(yīng)的森林F（6分）：森林的先序次序訪問序列為：ABCDEFGHIJKL；森林的中序次序訪問序列為：CBEFDGAJIKLH。圖G的鄰接矩陣如下所示：試畫出該圖，并使用Kruskal算法構(gòu)造出一棵最小生成樹。（9分）4．已知一組關(guān)鍵字為（10，24，32，17，31，30，46，47，40，63，49），設(shè)哈希函數(shù)H（key）＝keyMOD13。請寫出用線性探測法處理沖突構(gòu)造所得的哈希表。（11分）程序題（第1題15分，第2題20分）1、已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一算法，刪除表中所有值大于mink且小于maxk的元素（若表中存在這樣的元素），同時釋放被刪除結(jié)點空間（注意：mink和maxk是給定的兩個參變量，它們的值可以和表中的元素相同，也可以不同）。編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。試卷答案判斷題（對打√，錯打×。每題1分，共15分）√×√√√×√×√√√√√××選擇題（每題2分，共20分）CCBACCBCCD問答題（共30分）1、（4分，每個答案給1分）答：主要差別①樹中結(jié)點的最大度數(shù)沒有限制，而二叉樹結(jié)點的最大度數(shù)為2。②樹的結(jié)點無左右之分，而二叉樹的結(jié)點有左右之分。最多是完全二叉樹的形態(tài)，即502個葉子；最少是單支樹的形態(tài)，即1個葉子。2、（6分）答：AB2CAB2CEFGHIJKLAABDCEFGHIJKL3、（11分，每個關(guān)鍵字1分）答：01234567891011124940173132304647102463237123423712345672520181215810546畫出該圖給4分112345671812158546得出最小生成樹給5分算法題（第1題15分，第2題20分）1、voiddelete(LinkListL,intmink,intmaxk){ p=L->next; while(p&&p->data<=mink) {pre=p;p=p->next;}//查找第一個值>mink的結(jié)點 if(p){ while(p&&p->data<maxk)p=p->next; //查找第一個值≥maxk的結(jié)點 q=pre->next;pre->next=p;//修改指針 while(q!=p) {s=q->next;deleteq;q=s;}//釋放結(jié)點空間 }//if}//delete2、typedefstructNode{ ElemTypedata; structNode*lchild,*rchild;}BinNode,*BinTree;方法一：intleafNum=0;voidCountLeaf(BinTreeroot){ /*preordervisitbintreeandcountthenumberofleafnode*/ if(root!=NULL){ if(root->lchild==NULL&&root->rchild==NULL)leafNum++; else{ CountLeaf(root->lchild);CountLeaf(root->rchild); } }}方法二：intCountLeaf(BinTree