2018年10月自考02331數(shù)據(jù)結(jié)構(gòu)試題及解析含評分標(biāo)準(zhǔn)

1、2018年10月高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)試卷(課程代碼02331)本試卷共7頁，滿分l00分，考試時(shí)間l50分鐘?？忌痤}注意事項(xiàng)：1本卷所有試題必須在答題卡上作答。答在試卷上無效，試卷空白處和背面均可作草稿紙。2第一部分為選擇題。必須對應(yīng)試卷上的題號使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。3第二部分為非選擇題。必須注明大、小題號，使用05毫米黑色字跡簽字筆作答。4合理安排答題空間，超出答題區(qū)域無效。第一部分選擇題一、單項(xiàng)選擇題：本大題共l5小題，每小題2分，共30分。在每小題列出的備選項(xiàng)中 只有一項(xiàng)是最符合題目要求的。請將其選出。1下列數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)不同的是A線性表 B

2、棧 C隊(duì)列D二叉樹2將l6個(gè)數(shù)據(jù)元素的線性表按順序存儲(chǔ)方式存儲(chǔ)在數(shù)組中，若第一個(gè)元素的存儲(chǔ)地 址是l000，第6個(gè)元素的存儲(chǔ)地址是1040，則最后一個(gè)元素的存儲(chǔ)地址是 A1112 B1120 C1124 D11283設(shè)棧的初始狀態(tài)為空，元素1，2，3，4，5依次入棧，不能得到的出棧序列是 A1，2，3，4，5 B4，5，3，2，1 C1，2，5，4，3 D1，2，5，3，44設(shè)指針變量P指向非空單鏈表中的結(jié)點(diǎn)，next是結(jié)點(diǎn)的指針域，則判斷P所指結(jié)點(diǎn) 為尾結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)的邏輯表達(dá)式中，正確的是 A. p->next!=NULL&&p->next一>next-&

3、gt;next = NULL Bp->next!=NULL&&p->next->nextNULL Cp->next->next=NULL Dp->nextNULL5已知廣義表LS=(a，b，c)，d)，(e，(fg，(h i)，LS的深度是 A2 B3 C4 D56已知一棵完全二叉樹T的第5層上共有5個(gè)葉結(jié)點(diǎn)，則T中葉結(jié)點(diǎn)個(gè)數(shù)最少是 A5 88 C10 D277已知二叉樹T的前序遍歷序列為a，b，c，e，d，中序遍歷序列為C，e，b，d，a，則T的后序遍歷序列為 Ac，e，d,b，a Bd，e，c，b，a Ce，c，d，b，a De，c，b，

4、a，d8有向圖G有玎個(gè)頂點(diǎn)和e條邊，G保存在鄰接矩陣M中，M中0及1的個(gè)數(shù)差是 An(n+1)2-eBn(n+1)2-2e Cn×n-e Dn×n-2e9有向圖G中所有頂點(diǎn)的度數(shù)之和是24，則G中弧的數(shù)量是 A10 B12 C14 D1610設(shè)有向圖G含有n個(gè)頂點(diǎn)、e條邊，使用鄰接表存儲(chǔ)。對G進(jìn)行深度優(yōu)先搜索遍歷 算法的時(shí)間復(fù)雜度是 AO(n) BO(口) CO(n+e) DO(n×e)11對數(shù)據(jù)序列(26，14，17，12，7，4，3)采用二路歸并排序進(jìn)行升序排序，兩趟排序后，得到的排序結(jié)果為 A14，26，17，l2，4，7，3 B12，l4，l7，26，3，

5、4，7 C14，26，12，l7，3，4，7 D14，26，l2，l7，3，7，412下列選項(xiàng)中，不穩(wěn)定的排序方法是 A希爾排序 B歸并排序 C直接插入排序 D冒泡排序13一組記錄的關(guān)鍵字為(35，48，47，23，44，88)，利用堆排序算法進(jìn)行降序排序，建立 的初始堆為 A23，35，48，47，44，88 B23，35，47，48，44，88 C35，23，47，48，44，88 D35，23，47，44，48，8814一棵二叉排序樹中，關(guān)鍵字n所在結(jié)點(diǎn)是關(guān)鍵字m所在結(jié)點(diǎn)的孩子，則 An一定大于m Bn一定小于m Cn一定等于m Dn及m的大小關(guān)系不確定15設(shè)敖列表長m=16，散列函數(shù)H

6、(key)=key15。表中已保存4個(gè)關(guān)鍵字：addr(18)=3， · addr(35)=5，addr(51)=6，addr(22)=7，其余地址均為開放地址。存儲(chǔ)關(guān)鍵字36時(shí)存 在沖突，采用線性探測法來處理。則查找關(guān)鍵字36時(shí)的探查次數(shù)是 A1 B2 C3 D4第二部分非選擇題二、填空題：本大題共l0小題，每小題2分，共20分。16數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的_標(biāo)識單位。17指針P和q分別指向單鏈表L中的兩個(gè)相鄰結(jié)點(diǎn)，即q->next=P。若要在q所指結(jié) 點(diǎn)后插入指針r所指結(jié)點(diǎn)，則執(zhí)行的語句是r->ne處=p；_。18遞歸算法設(shè)計(jì)中的最小子問題稱為遞歸的_。19廣義表(a，

7、b)，(c，d)，e，(f (g,h)的表尾是_。20已知二叉樹的前序遍歷序列和后序遍歷序列，則對應(yīng)的二叉樹_確定。21如果有向無環(huán)圖G中僅有一個(gè)頂點(diǎn)的入度為0，若要求G的拓?fù)湫蛄胁晃ㄒ?，則G 中必須存在一個(gè)出度至少為_的頂點(diǎn)。22將森林T轉(zhuǎn)換為一棵二叉樹T1，在T中結(jié)點(diǎn)A是結(jié)點(diǎn)B的右鄰的兄弟(下一個(gè)兄 弟)，則在T1中，A是B的_結(jié)點(diǎn)。23對含玎個(gè)元素的數(shù)據(jù)序列采用快速排序算法進(jìn)行排序，平均時(shí)間復(fù)雜度是_。24散列存儲(chǔ)中，常用的解決沖突的方法有開放地址法和_兩大類。25假設(shè)順序存儲(chǔ)的有序表R含有8個(gè)關(guān)鍵字，進(jìn)行二分查找時(shí)，平均查找長度為_。三、解答題：本大題共4小題，每小題5分，共20分。2

8、6設(shè)電文字符集是el，e2，e3，e4，e5)，各字符出現(xiàn)的次數(shù)分別為36，l3，26，l8，23?，F(xiàn)要為該字符集設(shè)計(jì)哈夫曼編碼。請回答下列問題。 (1)給出構(gòu)造的哈夫曼樹。 (2)給出各字符的哈夫曼編碼。 (3)計(jì)算電文編碼總長。27已知圖G采用鄰接矩陣存儲(chǔ)，鄰接矩陣如題27圖所示。(1)根據(jù)鄰接矩陣畫出圖G。(2)根據(jù)圖G寫出從頂點(diǎn)A開始圖G的1個(gè)深度優(yōu)先搜索遍歷序列。(3)根據(jù)圖G寫出從頂點(diǎn)A開始圖G的1個(gè)廣度優(yōu)先搜索遍歷序列。28有數(shù)據(jù)序列(12，l7，O5，l0，20，24，45，ll，l0，l2)，使用希爾排序方法將其排成升序序列。請回答下列問題。 (1)分別寫出增量為3和1的希爾排序結(jié)果。 (2)計(jì)算第一趟希爾排序中數(shù)據(jù)元素之間的總交換次數(shù)(兩個(gè) (a) 元素之間的交換記l次)。29設(shè)有