10月自考數(shù)據(jù)結(jié)構(gòu)02331試題及答案解析資料僅供參考lO月高等教育自學(xué)考試全國(guó)統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)試卷(課程代碼02331)本試卷共8頁(yè)。滿分l00分?？荚嚂r(shí)間l50分鐘?？忌痤}注意事項(xiàng)：1．本卷所有試題必須在答題卡上作答。答在試卷上無(wú)效，試卷空白處和背面均可作草稿紙.2．第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。3．第二部分為非選擇題。必須注明大、小題號(hào)，使用0．5毫米黑色字跡簽字筆作答。4．合理安排答題空間．超出答題區(qū)域無(wú)效。第一部分選擇題一、單項(xiàng)選擇題(本大題共l5小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡”的相應(yīng)代碼涂黑。未涂、錯(cuò)涂或多涂均無(wú)分。1．下列選項(xiàng)中，不屬于線性結(jié)構(gòu)的是A．網(wǎng)B．棧C．隊(duì)列D．線性表2．長(zhǎng)度為n的順序表，刪除位置i上的元素(0≤i≤n一1)，需要移動(dòng)的元素個(gè)數(shù)為A．n—iB．n—i—lC．iD．i+13．棧采用不同的存儲(chǔ)方式時(shí)，下列關(guān)于出棧過(guò)程的敘述中，正確的是A．順序棧需要判定?？?，鏈棧也需要判定B．順序棧需要判定棧空，而鏈棧不需要判定C．順序棧不需要判定?？?，而鏈棧需要判定D．順序棧不需要判定?？?，鏈棧也不需要判定4．若一個(gè)棧以數(shù)組V[0．．n-1]存儲(chǔ)，初始棧頂指針top為n，則x入棧的正確操作是A．top=top+1；V[top]=xB．V[top]=x；top=top+1C．top=top一1；V[mp]=xD．V[top]=x；top=top—l5．在二維數(shù)組a[9][10]中：每個(gè)數(shù)組元素占用3個(gè)存儲(chǔ)空間，從首地址SA開(kāi)始按行優(yōu)先連續(xù)存放，則元素a[8][5]的起始地址是A．SA+141B．SA+144C．SA+222D．SA+2556．廣義表A=(x，((y)，((a))，A))的深度是A．2B．3C．4D．∞7．一棵左子樹(shù)為空的二叉樹(shù)在前序線索化后，其空指針域個(gè)數(shù)為A．0B．1C．2D．不確定8．下列關(guān)于哈夫曼樹(shù)的敘述中，錯(cuò)誤的是A．用n個(gè)結(jié)點(diǎn)構(gòu)造的哈夫曼樹(shù)是唯一的B．哈夫曼樹(shù)中只有度為0或度為2的結(jié)點(diǎn)C．樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)可能是兄弟結(jié)點(diǎn)D．同一結(jié)點(diǎn)集構(gòu)造的二叉樹(shù)中，哈夫曼樹(shù)的WPL最小9．6個(gè)頂點(diǎn)的強(qiáng)連通圖中，含有的邊數(shù)至少是A．4B．5C．6D．710．對(duì)題l0圖進(jìn)行深度優(yōu)先搜索遍歷，下列選項(xiàng)中，正確的遍歷序列是12．有向圖采用鄰接矩陣存儲(chǔ)，某一行中非零元素的個(gè)數(shù)等于A．對(duì)應(yīng)頂點(diǎn)v的度B．對(duì)應(yīng)頂點(diǎn)v的出度C．對(duì)應(yīng)頂點(diǎn)v的入度D．依附于對(duì)應(yīng)頂點(diǎn)v的邊數(shù)13．下列選項(xiàng)中，符合堆定義的是A．{102，24，55，60，89，93}B．{24，89，55，60，93，102}C．{102，93，55，60，89，24}D．{102，60。89，93，55，24}14．已知關(guān)鍵字序列為{66，82，25，51，98，108}，利用快速排序方法，以第一個(gè)元素為基準(zhǔn)得到的一趟排序結(jié)果為A．{25，51，66，82，98，108}B．{25，51，66，98，82，108}C．{51，25，66，108，98，82}D．{51，25，66，82，98，108}15．下列選項(xiàng)中，其平均查找性能與基于二叉排序樹(shù)的查找相當(dāng)?shù)氖茿．二分查找B．順序查找C．分塊查找D．索引順序查找第二部分非選擇題二、填空題(本大題共l0小題，每小題2分，共20分)請(qǐng)?jiān)诖痤}卡上作答。16．線性表(a1，a2，…，an)中，除_______外，每個(gè)元素都有唯一的直接前趨。17．指針P指向單鏈表中某個(gè)結(jié)點(diǎn)，在P所指結(jié)點(diǎn)后插入指針s所指的結(jié)點(diǎn)，正確的操作序列是_______。18．設(shè)Push，、Pop分別表示人棧和出棧操作，x=10，y=20，z=30。依次進(jìn)行下列操作：Push(y)、Push(z)、Push(z)、X=Pop()、Y=Pop()，x,y的值分別是_______。19．廣義表L=(a，(b，e，(e，f，g，h)))，head(L)=_______。20．設(shè)樹(shù)T的度為3，其中度為1、2和3的結(jié)點(diǎn)個(gè)數(shù)分別為3、2和1，則T中葉子結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)______。21．由一棵二叉樹(shù)的后序遍歷序列和_______遍歷序列能夠唯一確定該二叉樹(shù)。22．在有n個(gè)頂點(diǎn)的無(wú)向圖中，任一頂點(diǎn)的度不大于_______。23．借助于一個(gè)棧來(lái)實(shí)現(xiàn)的圖的遍歷算法是_______。24.若有向圖中存在拓?fù)渑判蛐蛄?，則該圖一定不存在_______。25．已知關(guān)鍵字序列為{66，82，25，51，98，108}，一趟二路歸并排序的結(jié)果為_(kāi)______。三、簡(jiǎn)答題(本大題共4小題，每小題5分。共20分)請(qǐng)?jiān)诖痤}卡上作答。26．已知n階對(duì)稱矩陣A的元素為ai,j(0≤i，j≤n一1)，采用“按行優(yōu)先”將下三角部分的元素(含主對(duì)角線)保存在一維數(shù)組sa中，且約定元素a0,0保存在sa[0]中，元素ai,j(≤i，j≤n-1)保存在sa[k]中，請(qǐng)給出由下標(biāo)i，j計(jì)算下標(biāo)k的計(jì)算公式。27.己知二又樹(shù)T如題27圖所示。請(qǐng)問(wèn)答下列問(wèn)題：(1)畫(huà)出該二叉樹(shù)對(duì)應(yīng)的森林。(2)寫(xiě)出對(duì)森林進(jìn)行前序遍歷的遍歷序列i28．題28圖所示為一棵含2個(gè)關(guān)鍵字的3階B樹(shù)T?，F(xiàn)將關(guān)鍵字序列{40，60，70，20，10}依次插入到T中，畫(huà)出每插入一個(gè)關(guān)鍵字后得到的樹(shù)型。29．給定無(wú)向帶權(quán)連通圖G如題29圖所示，從頂點(diǎn)v0開(kāi)始，使用普里姆(Prim)算法，求G的最小生成樹(shù)T。請(qǐng)回答下列問(wèn)題。(1)畫(huà)出最小生成樹(shù)T。(2)計(jì)算T中各邊權(quán)值之和。四、算法閱讀題(本大題共4小題，每小題5分，共20分)請(qǐng)?jiān)诖痤}卡上作答。30．請(qǐng)寫(xiě)出下列程序段的輸出結(jié)果。31．己知存儲(chǔ)稀疏矩陣三元組表的類(lèi)型定義如下：32．已知二叉樹(shù)的二叉鏈表類(lèi)型定義如下：為完成指定功能，請(qǐng)?jiān)诳瞻滋幪顚?xiě)適當(dāng)內(nèi)容，使其功能完整。33．函數(shù)f33的參數(shù)t指向題33圖所示的二叉排序樹(shù)的根，閱讀程序，回答下列問(wèn)題。(1)若連續(xù)3次調(diào)用函數(shù)f33，參數(shù)K的值依次取10、25、10，寫(xiě)出每次調(diào)用后函數(shù)的輸出結(jié)果；(2)說(shuō)明函數(shù)f33的功能。五、算法設(shè)計(jì)題(本大題共l小題。共l0分)請(qǐng)?jiān)诖痤}卡上作答。34．已知順序表SeqList定義如下：typedefstruct{