浙大城院數(shù)據(jù)結構期末模擬2

浙大城院數(shù)據(jù)結構期末模擬2浙大城院數(shù)據(jù)結構期末模擬2浙大城院數(shù)據(jù)結構期末模擬2V:1.0精細整理，僅供參考浙大城院數(shù)據(jù)結構期末模擬2日期：20xx年X月模擬2得分一．選擇題(本大題共15題，每題1分，共15分)1．數(shù)據(jù)在計算機內存中的表示是指。A.數(shù)據(jù)的存儲結構B.數(shù)據(jù)結構C.數(shù)據(jù)的邏輯結構D.數(shù)據(jù)元素之間的關系2.對線性表，在下列情況下應當采用鏈表表示的是。A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中的元素個數(shù)不變3．與單鏈表相比，雙鏈表的優(yōu)點之一是。A．插入、刪除操作更加簡單。B．可隨機訪問。C．可以省略表頭指針或表尾指針D．訪問前驅結點更加方便4．如果最常用的操作是取第i個結點及前驅，則采用存儲方式最節(jié)省時間。A．順序表B．雙鏈表C．單循環(huán)鏈表D．單鏈表5．可以用帶表頭附加結點的鏈表表示線性表，也可以用不帶表頭附加結點的鏈表表示線性表，前者最主要的好處是。A．可以加快對表的遍歷B.使空表和非空表的處理統(tǒng)一C．節(jié)省存儲空間D.可以提高存取表元素的速度6.一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,17．棧和隊列的共同點是。A．都是先進先出B．都是先進后出C．屬于非線性結構D．只允許在端點處插入和刪除元素8．以下不是棧的基本運算的是。A．刪除棧頂元素B.刪除棧底元素C．判斷棧是否為空D.將棧置為空棧9．一個遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，若從運行時間來看，通常__________。A．非遞歸算法比遞歸算法快 B．非遞歸算法比遞歸算法慢C．非遞歸算法與遞歸算法時間一樣 D．非遞歸算法與遞歸算法時間不一定10.在一個非空二叉數(shù)的中序遍歷序列中，根結點的右邊。A.只有右子樹上的所有結點B.只有右子樹上的部分結點C.只有左子樹上的部分結點D.只有左子樹上的所有結點11.有關樹和二叉樹的敘述錯誤的有。A.樹中的最大度數(shù)沒有限制，而二叉樹結點的最大度數(shù)為2；B.樹的結點無左右之分，而二叉樹的結點有左右之分；C.樹的每個結點的孩子數(shù)為0到多個,而二叉樹每個結點均有兩個孩子；D.樹和二叉樹均為樹形結構。12．深度為k的完全二叉樹至少有個結點，至多有個結點。A.(2k-1,2k-1)B.(2k-1,2k)C.(2k-1,2k)D.(2k-1-1,2k-1)13.具有4個頂點的無向完全圖，有條邊。A.3B.6C.12D14．一個具有n個頂點的無向圖，要確保是一個連通圖，至少需要條邊。A.n-1B.nC.n+1D.n/215．在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍。A.4B.2C得分二．填空題(本大題共10個空，每個空2分，共20分)1.數(shù)據(jù)的邏輯結構被分為集合、、、圖形結構四種。2.數(shù)據(jù)的存儲結構主要分為和兩種。3.不同形式的時間復雜度O(logn)、O(nlogn)、O(n)、O(n2)、O(2n)，隨著n的增長，其增長速度關系為（按從小到大排列）。4．在單鏈表中，要刪除某一指定的結點，必須找到該結點的。5.在一個長度為n的順序表中刪除表中的第i個元素（0≤i≤n-1）時，需向前移動元素。6.已知某無向圖的二元組表示為DS=(K,R),K={a,b,c,d,e}，R={r}，r={(a,b),(a,c),(a,d),(b,e),(d,e),(c,d),<c,b>}，則頂點b的度為。7.已知一棵樹用廣義表表示為a(b,c(d(e(f),g,h),i),j)，則此樹的度為，深度為。得分三．解答題(本大題共3題，每題6分，共18分)1．設有字符串3*a-b/4，試利用棧寫出將此次序改變?yōu)?a*b4/-的操作步驟。例如:ABC變BCA，操作步驟為Push;Push;Pop;Push;Pop;Pop。2．已知一棵二叉樹的中序遍歷序列是abcdjefhgi，前序遍歷序列是eadcbjfghi，請畫出這棵二叉樹，并寫出這棵二叉樹的后序遍歷序列。3.設有向圖G=(V,E)，V={V1,V2,V3,V4,V5,V6}，G的鄰接矩陣如下：011000000011000100100000000000000110①請畫出圖G的強連通分量;②請根據(jù)鄰接矩陣存儲結構有向圖的廣度優(yōu)先遍歷算法，寫出從頂點V1出發(fā)所得到的頂點序列。得分四．程序閱讀題(本大題共2題，每題5分，共10分)設head為非遞減有序的單鏈表的頭指針，單鏈表中各結點的值依次為(2,3,3,3,4,7,8,8,9,10,10)，閱讀下列算法，寫出運行該算法后單鏈表中各結點的值。voidfun1(LNode*&head){ LNode*p=head,*q; while(p!=NULL&&p->next!=NULL){ if(p->data==p->next->data){q=p->next;p->next=q->next; free(q); }elsep=p->next;} }閱讀下列程序，說明該算法的功能。ElemTypefun2(Queueq){ElemTypex;Queuetemp;InitQueue(temp);while(!QueueEmpty(q)){x=OutQueue(q);EnQueue(temp,x);}while(!QueueEmpty(temp)){x=OutQueue(temp);EnQueue(q,x);}returnx;}得分五．程序填空題(本大題共6個空，每空2分，共12分)閱讀下列程序，在空白處填入適當?shù)恼Z句，使算法完整。1．設有一個順序表L，其元素為整型數(shù)據(jù)，下列算法將L中所有小于0的整數(shù)放在前半部分，大于0的整數(shù)放在后半部分。提示：從L的兩端查找，前端找大于0的數(shù)據(jù)，后端找小于0的數(shù)據(jù)，然后將兩位置的數(shù)據(jù)交換。順序表結構定義如下：structList{ ElemType*list;//動態(tài)存儲空間的基地址，指針 intsize;//線性表當前實際長度 intMaxSize;//當前動態(tài)數(shù)組分配的長度};算法如下：voidMove(List&L){ inti=0,j=L.size-1,temp; while(i<j) { while(i<j&&L.list[i]<0)i++; while(i<j&&L.list[j]>0)①; if(②){ temp=L.list[i]; L.list[i]=L.list[j]; ③; } }}2.下列算法用于輸出鄰接表表示的無向圖中序號為num的頂點的所有鄰接點。鄰接表結構定義如下：typedefstructnode{intadjvex;structnode*next;}edgenode;typedefedgenode*adjlist[MaxVertexNum];算法如下：voidOutAdjVex(adjlistGL,intnum){edgenode*p;p=④;while(⑤){cout<<⑥;p=p->next;}}得分六．程序設計題(本大題共2題，第1題10分，第2題15分，共25分)根據(jù)下列函數(shù)聲明編寫求二叉樹BT中所有結點數(shù)和葉子結點數(shù)的遞歸算法，其值分別由引用參數(shù)C1和C2帶回，C1和C2的初值均為0。函數(shù)聲明為：voidCount(BTreeNode*BT,int&C1,int&C2)結點結構定義如下：structBTreeNode{ ElemTypedata; BTreeNode*left; BTree