數(shù)據(jù)結(jié)構(gòu)2018年10月自考題目

數(shù)據(jù)結(jié)構(gòu)2018年10月自考題目第一部分選擇題一、單項選擇題：本大題共15小題，每小題2分，共30分。在每小題列出的備選項中只有一項是最符合題目要求的。請將其選出。1.下列數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)不同的是()A.線性表B.棧C.隊列D.二叉樹2.將16個數(shù)據(jù)元素的線性表按順序存儲方式存儲在數(shù)組中，若第一個元素的存儲地址是1000，第6個元素的存儲地址是1040，則最后一個元素的存儲地址是()A.1112B.1120C.1124D.11283.設(shè)棧的初始狀態(tài)為空，元素1，2，3，4，5依次入棧，不能得到的出棧序列是()A.1，2，3，4，5B.4，5，3，2，1C.1，2，5，4，3D.1，2，5，3，44.設(shè)指針變量P指向非空單鏈表中的結(jié)點，next是結(jié)點的指針域，則判斷P所指結(jié)點為尾結(jié)點前一個結(jié)點的邏輯表達(dá)式中，正確的是()A.p->next！=NULL&&p->next->next->next==NULLB.p->next！=NULL&&p->next->next-NULLC.p->next->next==NULLD.p->next-NULL5.已知廣義表LS=（（（a，b，c），d），（e，（fg，（hi））），LS的深度是()A.2B.3C.4D.56.已知一棵完全二叉樹T的第5層上共有5個葉結(jié)點，則T中葉結(jié)點個數(shù)最少是()A.5B.8C.10D.277.已知二叉樹T的前序遍歷序列為a，b，c，e，d，中序遍歷序列為C，e，b，d，a，則T的后序遍歷序列為()A.c，e，d，b，aB.d，e，c，b，aC.e，c，d，b，aD.e，c，b，a，d8.有向圖G有個頂點和e條邊，G保存在鄰接矩陣M中，M中0與1的個數(shù)差是()A.n（n+1）/2-eB.n（n+1）/2-2eC.nXn-eD.nXn-2e9.有向圖G中所有頂點的度數(shù)之和是24，則G中弧的數(shù)量是()A.10B.12C.14D.1610.設(shè)有向圖G含有n個頂點、e條邊，使用鄰接表存儲。對G進(jìn)行深度優(yōu)先搜索遍歷算法的時間復(fù)雜度是()A.0（n）B.0（口）C.0（n+e）D.0（n×e）11.對數(shù)據(jù)序列（26，14，17，12，7，4，3）采用二路歸并排序進(jìn)行升序排序，兩趟排序后，得到的排序結(jié)果為()A.14，26，17，12，4，7，3B.12，14，17，26，3，4，7C.14，26，12，17，3，4，7D.14，26，12，17，3，7，412.下列選項中，不穩(wěn)定的排序方法是()A.希爾排序B.歸并排序C.直接插入排序D.冒泡排序13.一組記錄的關(guān)鍵字為（35，48，47，23，44，88），利用堆排序算法進(jìn)行降序排序，建立的初始堆為()A.23，35，48，47，44，88B.23，35，47，48，44，88C.35，23，47，48，44，88D.35，23，47，44，48，8814.一棵二叉排序樹中，關(guān)鍵字n所在結(jié)點是關(guān)鍵字m所在結(jié)點的孩子，則()A.n一定大于mB.n一定小于mC.n一定等于mD.n與m的大小關(guān)系不確定15.設(shè)敖列表長m=16，散列函數(shù)H（key）=key%15。表中已保存4個關(guān)鍵字：addr（18）=3，addr（35）=5，addr（51）=6，addr（22）=7，其余地址均為開放地址。存儲關(guān)鍵字36時存在沖突，采用線性探測法來處理。則查找關(guān)鍵字36時的探查次數(shù)是()A.1B.2C.3D.4第二部分非選擇題二、填空題：本大題共10小題，每小題2分，共20分。16.數(shù)據(jù)項是具有獨立含義的（）標(biāo)識單位。17.指針P和q分別指向單鏈表L中的兩個相鄰結(jié)點，即q->next=P。若要在q所指結(jié)點后插入指針r所指結(jié)點，則執(zhí)行的語句是r->ne處=p；（）。18.遞歸算法設(shè)計中的最小子問題稱為遞歸的（）。19.廣義表（（a，b），（c，d），e，（f（g，h）））的表尾是（）。20.已知二叉樹的前序遍歷序列和后序遍歷序列，則對應(yīng)的二叉樹（）確定。21.如果有向無環(huán)圖G中僅有一個頂點的入度為0，若要求G的拓?fù)湫蛄胁晃ㄒ?，則G中必須存在一個出度至少為（）的頂點。22.將森林T轉(zhuǎn)換為一棵二叉樹T1，在T中結(jié)點A是結(jié)點B的右鄰的兄弟（下一個兄弟），則在T1中，A是B的（）結(jié)點。23.對含個元素的數(shù)據(jù)序列采用快速排序算法進(jìn)行排序，平均時間復(fù)雜度是（）。24.散列存儲中，常用的解決沖突的方法有開放地址法和（）兩大類。25.假設(shè)順序存儲的有序表R含有8個關(guān)鍵字，進(jìn)行二分查找時，平均查找長度為（）三、解答題：本大題共4小題，每小題5分，共20分。26.設(shè)電文字符集是{el，e2，e3，e4，e5），各字符出現(xiàn)的次數(shù)分別為{36，13，26，18，23}?，F(xiàn)要為該字符集設(shè)計哈夫曼編碼。請回答下列問題。（1）給出構(gòu)造的哈夫曼樹。（2）給出各字符的哈夫曼編碼。（3）計算電文編碼總長。27.已知圖G采用鄰接矩陣存儲，鄰接矩陣如題27圖所示。（1）根據(jù)鄰接矩陣畫出圖G。（2）根據(jù)圖G寫出從頂點A開始圖G的1個深度優(yōu)先搜索遍歷序列。（3）根據(jù)圖G寫出從頂點A開始圖G的1個廣度優(yōu)先搜索遍歷序列。28.有數(shù)據(jù)序列（12，17，05，10，20，24，45，11，10，12），使用希爾排序方法將其排成升序序列。請回答下列問題。（1）分別寫出增量為3和1的希爾排序結(jié)果。（2）計算第一趟希爾排序中數(shù)據(jù)元素之間的總交換次數(shù)（兩個（a）元素之間的交換記1次）。29.設(shè)有二叉排序樹T如題29圖所示?，F(xiàn)需在T中刪除結(jié)點e，請回答下列問題。（1）畫出刪除后的二叉排序樹（僅需畫出一棵）。（2）在你實現(xiàn)的刪除過程中，指針域更新的次數(shù)是多少？四、算法閱讀題：本大題共4小題，每小題5分，共20分。30.順序表類型定義如下：#defineListSize100typedefstruct{intdata[ListSize]；intlength；}SeqList；閱讀下列程序，并回答問題。intpartmin（SeqList*SL1，SeqList*SL2）{intminlength，minvalue，k=0；minlength=SL2->length；minvalue=SL2->data[0]；while（k<minlength）{if（SL1->data[k]<SL2->data[k]&&SL1->data[k]<minvalue）minvalue=SL1->data[k]；elseif（SL2->data[k]<minvalue）minvalue=SL2->data[k]；k++；}returnminvalue;}intf30(SeqList*SL1,SeqList*SL2){32.待排序記錄的數(shù)據(jù)類型定義如下：#defineMAXSIZE100typedefintKeyType；typedefstruct{KeyTypekey；}RecType；typedefRecTypeSeqList[MAXSIZE]；下列函數(shù)實現(xiàn)順序表的直接插入排序，請在空白處填上適當(dāng)內(nèi)容使算法完整。voidf32(SeqListR,intn){Inti,j;RecTypetemp;for(i=l;i<=();i++){temp=R[i];j=i;while(j>0&&temp.key<R[j-1].key){R[j]=R[j-1];();}();}}33.二叉樹的存儲結(jié)構(gòu)類型定義如下：typedefintDataType；typedefstructnode{DataTypekey；//data是數(shù)據(jù)域structnode*lchild，*rehild；//分別指向左右孩子}BinTNode；typedefBinTNode*BinTree；閱讀下列程序，并回答問題。voidf33(BinTreeroot,intleft,intright){if(root=NULL)return;f33(root->lchild,left,right);if(roor->key>=left&&root->key<right)printf("%d",root->key);f33(root->rchild,left,right);}（1）設(shè)二叉樹T如題3