自考02331數(shù)據(jù)結(jié)構(gòu)試題及答案

2017年10月高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)試卷(課程代碼02331)本試卷共8頁，滿分100分，考試時間150分鐘?？忌痤}注意事項：.本卷所有試題必須在答題卡上作答。答在試卷上無效,試卷空白處和背面均可作草稿紙。第一部分為選擇題。必須對應(yīng)試卷上的題號使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。第二部分為非選擇題。必須注明大、小題號，使用0.5毫米黑色字跡簽字筆作答。合理安排答題空間,超出答題區(qū)域無效。第一部分選擇題一、單項選擇題：本大題共15小題，每小題2分，共30分。在每小題列出的備選項中只有一項是最符合題目要求的，請將其選出。下列選項中，與數(shù)據(jù)存儲結(jié)構(gòu)直接相關(guān)的是A.線性表 B?雙向鏈表C.二叉樹 D?有向圖將12個數(shù)據(jù)元素保存在順序表中，若第一個元素的存儲地址是100,第二個元素的A.111 B.144 C.155 D?156存儲地址是105,則該順序表最后一個元素的存儲地址是設(shè)棧的初始狀態(tài)為空，元素1,2,3,4,5,6依次入棧，棧的容量是3,能夠得到的出棧序列是A.1,2,6,4,3,5 B?2,4,3,6,5,1C?3,1,2,5,4,6 D?3,2,6,5,1,44?設(shè)指針變量head指向非空單循環(huán)鏈表的頭結(jié)點，指針變量p指向終端結(jié)點，next是結(jié)點的指針域，則下列邏輯表達(dá)式中，值為真的是A.p->next->next==head B?p->next==headC.p->next->next==NULL D?p->next==NULL5?已知廣義表LS=(((a,b)),((c,(d)),(e,(f))),(g,h)),LS的深度是A-2 B?3 C?4 D.5已知一棵高度為4的完全二叉樹T共有5個葉結(jié)點，則T中結(jié)點個數(shù)最少是A.9B.10C.11 D.12在一棵非空二叉樹的中序遍歷序列中，所有列在根結(jié)點前面的是A-左子樹中的部分結(jié)點 B?左子樹中的全部結(jié)點C.右子樹中的部分結(jié)點 D.右子樹中的全部結(jié)點&用鄰接矩陣表示有n個頂點和e條邊的無向圖，釆用壓縮方式存儲，矩陣中零元素的個數(shù)是A.n(n+l)/2-e B?n(n+l)/2-2e C?nxn-e D?nxn-2e無向圖G中所有頂點的度數(shù)之和是20,則G中的邊數(shù)是A?10 B.20 C?30 D?40設(shè)有向圖G含有n個頂點、e條邊，使用鄰接表存儲。對G進行廣度優(yōu)先遍歷的算法的時間復(fù)雜度是A.OM B.O(e) C.O(n+e) D.O(nAe)對數(shù)據(jù)序列(25,15,7,18,10,0,4)采用直接插入排序進行升序排序，兩趟排序后，得到的排序結(jié)果為A.0,4,7,18,10,25,15 B?0,4,25,15,7,18,10C?7,15,10,0,4,1&25 D.7,15,25,18,10,0,412?下列排序方法中，穩(wěn)定的排序方法是A?希爾排序 B.歸并排序C.堆排序 D.快速排序13?一組記錄的關(guān)鍵碼為(45,68,57,13,24,89),利用堆排序算法進行升序排序，建立的初始堆為A.6&45,57,13,24,89 B?89,6&57,13,24,45C?89,68,57,45,24,13 D?89,57,68,24,45,13—棵二叉排序樹中，關(guān)鍵字n所在結(jié)點是關(guān)鍵字m所在結(jié)點的祖先，則

C?C?n—定等于mD?n與m的大小關(guān)系不確定設(shè)散列表長m=14，散列函數(shù)H(key)=key%llo表中己保存4個關(guān)鍵字:addr(15>4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址均為空。保存關(guān)鍵字49時存在沖突，采用線性探查法來處理。則查找關(guān)鍵字49時的探查次數(shù)是A?1 B?2 C.4 D.8第二部分非選擇題二、填空題：本大題共10小題，每小題2分，共20分。TOC\o"1-5"\h\z數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)元素的存儲結(jié)構(gòu) 。指針p和指針q分別指向單鏈表L中的兩個相鄰結(jié)點，即q->next=p，且p所指結(jié)點不是終端結(jié)點。若要刪除p所指結(jié)點，則執(zhí)行的語句是 。18?一個直接或間接調(diào)用自己的函數(shù)稱為 ?！?9.廣義表(a,(b,c,d),e,f,(g,h))的表尾是 。20?二叉樹的前序遍歷序列和后序遍歷序列中，葉結(jié)點之間的相對次序 。21?如果圖G存在拓?fù)渑判蛐蛄?，則G必為 。22-將一棵樹T轉(zhuǎn)換為一棵二叉樹T1,在T1中結(jié)點A是結(jié)點B的父結(jié)點，則在T中，A可能是B的父結(jié)點或 。23.對含n個元素的數(shù)據(jù)序列釆用快速排序算法進行排序，在最壞情況下的時間復(fù)雜度是 O24?散列方法中，表示散列表裝滿程度的指標(biāo)Q稱為 。25-假設(shè)順序存儲的有序表R含有12個關(guān)鍵字，進行二分査找時，平均査找長度為三、解答題：本大題共4小題，每小題5分，共20分。設(shè)電文字符集是｛ebe2,e3,e4,e5),它們出現(xiàn)的次數(shù)分別為：｛50,10,16,&12｝?，F(xiàn)要為該字符集設(shè)計哈夫曼編碼。請回答下列問題。畫出得到的哈夫曼樹。給出各符號的哈夫曼編碼。已知圖G釆用鄰接矩陣存儲，鄰接矩陣如題27圖所示。題27圖寫出從頂點A開始圖G的3個不同的深度優(yōu)先搜索遍歷序列。寫出從頂點A開始圖G的2個不同的廣度優(yōu)先搜索遍歷序列。有以下數(shù)據(jù)序列(19,14,23,01,68,20,84,27,55,11,10,79,12),使用希爾排序方法將其排成升序序列。請回答下列問題。寫出增量為4時對上述數(shù)據(jù)序列進行一趟希爾排序的結(jié)果。題29圖題29圖設(shè)有二叉排序樹如題29圖所示。請回答下列問題。假定二叉排序樹初始為空，寫出一個數(shù)據(jù)輸入序列，按序插入時能得到題29圖所示的二叉排序樹。能得到題29圖所示的二叉排序樹的不同的輸入數(shù)據(jù)序列有幾個？四、算法閱讀題：本大題共4小題，每小題5分，共20分。'30順序表類型定義如下：#defineListSize100typedefstruct{intdata[ListSize];intlength;}SeqList;閱讀下列算法，并回答問題。voidchange(SeqList*SL1,SeqList*SL2){intminlength;intk=0,temp;if(SLl->lengthvSL2->length)return;minlength=SL2->Iength;while(k<miniength){if(SLl->data[k]<SL2->data[k]){temp=SLl->data[k];SLl->data[k]=SL2->data[k];SL2->data[k]=temp;}k卄;voidf30(SeqList*SL1,SeqList*SL2)if(SLl->length>SL2->length)change(SL1,SL2);elsechange(SL2,SL1);return;}若SLl->data中的數(shù)據(jù)為{25,4,256,9,-38,47,128,256,64}，SL2->data中的數(shù)據(jù)為{22,4,63,15,29,34,42,3},則執(zhí)行算法f30(&SL1,&SL2)后SLl->data和SL2->data中的數(shù)據(jù)各是什么？該算法的功能是什么？燈二叉樹的存儲結(jié)構(gòu)類型定義如下：typedefcharDatalype;typedefstructnode{DataTypedata; //data是數(shù)據(jù)域structnode*lchild,*rchild;//分別指向左右孩子JBinTNode;typedefBinTNode*BinTree;閱讀下列算法，并回答問題。voidA31(BinTreeT){if(T!=NULL){printR”％c”,T->data);A31(T->rchild);printf(”％c”,T->data);A31(G>lchild);}return;}(1)設(shè)二叉樹T如題31圖所示，給出執(zhí)行A31(T)的輸出結(jié)果。題31圖（2）給出該算法的時間復(fù)雜度32.待排序記錄的數(shù)據(jù)類型定義如下：#defineMAXSIZE100typedefintKeyType;typedefstruct{Keylypekey;}RecType;typedefRecTypeSeqList[MAXSIZE];下列算法實現(xiàn)自底向上、自頂向下交替進行的雙向掃描冒泡排序，請在空白處填上適當(dāng)內(nèi)容使算法完整。voidf32(SeqListR,intn){-inti=0,j;RecTypet;intNoSwap=l;while(NoSwap){NoSwap=0;fbr(j=n-i-1;(1) )if(Rlj].key<R[j.l].key){t=RUJ；RU]=RD-1];NoSwap=l;}for((2) :i++)if(R[j].key>R[j+l].key){t=RUl；R[j]二Rb+1]；RU+l]=t;NoSwap=l;—⑶；//data是數(shù)據(jù)域////data是數(shù)據(jù)域//分別指向左右孩子Datalypekey;typedefintDataType;typedefstructnodestructnode*lchild,*rchild;}BinTNode;typedefBinTNode*BinTree;閱讀下列算法，并回答問題。voidA33(BinTreeroot,intkl,intk2,intend)if(root==NULL)return;A33(root->Ichild,kl,k2,end);if(end)return;if(root->key>k2){end=1;return;}if(root->key>=kl)prinfd”root->key);A33(root->rchild,kl,k2,end);}⑴設(shè)二叉排序樹T如題33圖所示，bt是指向根結(jié)點的指針。給出執(zhí)行A33(bt,6,100,0)的輸出結(jié)果。100,0)的輸出結(jié)果。題33圖(2)給出該算法的功能。五、算法設(shè)計題：本題10分。34已知二叉樹的存儲結(jié)構(gòu)類型定義如下:typedefstructnode{intdata;structnode*lchild,rchild;}BinNode;typedefBinNode*BinTree;編寫遞歸算法，對于給定的一棵二叉樹T,將其修改為鏡像二叉樹。例如，題34圖所示的兩棵二叉樹互為鏡像二叉樹。函數(shù)的原型為：voidf34(BinTreeT);絕密★啟用前2017年10丿J高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)試題答案及評分參考（課程代碼02331）―、單項選擇題：本大題共】5小題，毎小題2分，共孔分。1.R2.(:3.B4.B5.C6.A7?B&A9.A10.V1LD12.B13.BM.D15.C二、填空昭本大題共10小題，每小題2分，共20分.16.無關(guān)〔或不同）1816.無關(guān)〔或不同）18?遞歸浙數(shù)20.不變22.兄弟24?裝填岡了17.q->ncxl=p->next19.伽c.d).e.f.(屮h))21.符向無環(huán)圖23.O(n2)25.37/12,約為3.08三、解答題：本大題共彳小餉每小題三、解答題：本大題共彳小餉每小題5分，共20分.26-（I）自芳包過C016786N51 （3分）Z1 t2:1 Lv/\a.. 1'1■■%1(2分)字符己3e4編碼1001Oil000010【評分說明】△題答案人唯。若考生洽出的答案正同樣給分。

〈3分)(2〈3分)(2分)〈3分〉〈2分〉fl最茹一個噌星定1?同樣給分,〈4分)(1分)(2)ARCDFH-(iA[X：?hEG【評分說明】木題答英不唯一〈若考生給出的答案止誦，P7Hr分。2&(1)12?II.10r()L19?14.23.27.55.20.84>79,68⑵4.2,1【評分說明】培城序列答案不唯若占生給出的増誑宇列足逼減序列29.(I)agebfile (或其乜專價答案)(2)4個四、算法閱讀題：本大題共4小題，每小題5分.共2()分。(1)SLI->data中的數(shù)據(jù)JA{25,4,256.15.29,47,12&256.64}.SL2->data中的TOC\o"1-5"\h\z數(shù)據(jù)是{22.4,-63,9.-3&34.42,3} (4分)(2)該竺仏比枚新人線灶表中相同下標(biāo)位進的兩個兀農(nóng)，較大占敬到較氏的線性表中，較小咅放到較短的線性農(nóng)中. (I分)⑴ACCABB (3分)〈2分)(