2016年10月自考《2331數(shù)據(jù)結(jié)構(gòu)》真題和答案

1、第1頁(yè)共9頁(yè)2016年10月高等教育自學(xué)考試全國(guó)統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)試卷試卷(課程代碼02331)本試卷共本試卷共7頁(yè)，滿分頁(yè)，滿分l00l00分，考試時(shí)間分，考試時(shí)間l50l50分鐘。分鐘?？忌痤}注意事項(xiàng)：考生答題注意事項(xiàng)：1本卷所有試題必須在答題卡上作答。答在試卷上無(wú)效，試卷空白處和背面均可作草稿紙。本卷所有試題必須在答題卡上作答。答在試卷上無(wú)效，試卷空白處和背面均可作草稿紙。2第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用第

2、一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B2B鉛筆將鉛筆將“答題卡答題卡”的相應(yīng)代碼涂黑。的相應(yīng)代碼涂黑。3第二部分為非選擇題。毖須注明大、小題號(hào)，使用第二部分為非選擇題。毖須注明大、小題號(hào)，使用05毫米黑色字跡簽字筆作答。毫米黑色字跡簽字筆作答。4合理安排答題空間，超出答題區(qū)域無(wú)效。合理安排答題空間，超出答題區(qū)域無(wú)效。第一部分第一部分選擇題選擇題(共3030分)一、單項(xiàng)選擇題一、單項(xiàng)選擇題(本大題共本大題共l5l5小題，每小題小題，

3、每小題2分，共分，共3030分在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題答題卡”的相應(yīng)代碼涂黑。錯(cuò)涂、多涂或未涂均無(wú)分。的相應(yīng)代碼涂黑。錯(cuò)涂、多涂或未涂均無(wú)分。1下列選項(xiàng)中，不屬于線性結(jié)構(gòu)特征的是A數(shù)據(jù)元素之間存在線性關(guān)系B結(jié)構(gòu)中只有一個(gè)開始結(jié)點(diǎn)C結(jié)構(gòu)中只有一個(gè)終端結(jié)點(diǎn)D每個(gè)結(jié)點(diǎn)都僅有一個(gè)直接前趨2設(shè)l7個(gè)元素的順序表中，若將第個(gè)元素e移動(dòng)到

4、第個(gè)位置，不改變除e外其他元素之間的相對(duì)次序，則需移動(dòng)的表中元素個(gè)數(shù)是3若用一個(gè)大小為7的數(shù)組作為循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)，且當(dāng)前rew和盤0nt的值分別為2和4，在此之前的操作是從隊(duì)列中刪除了一個(gè)元素及加入兩個(gè)元素，請(qǐng)問(wèn)這3個(gè)操作之前rear和矗0nt的值分別是A0和lB0和3C3和6D4和54已知廣義表LS=(((a))，((b，(c))，(d，(e，f)))，0)，LS的長(zhǎng)度是A2B3C4D.55一棵完全二叉樹T的全部k個(gè)葉結(jié)點(diǎn)都在同一

5、層中且每個(gè)分支結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)。于中包含的結(jié)點(diǎn)數(shù)是AkB.2k1Ck2D2k16如果某二叉樹的前序遍歷序列為abced，中序遍歷序列為cebda，則該二叉樹的后序遍歷序列是AcedbaBdecbaCecdbaDecbad7一個(gè)森林有m棵樹，頂點(diǎn)總數(shù)為n，則森林中含有的總邊數(shù)是AmB.nlCnmDnm8設(shè)圖的鄰接矩陣A如下所示。各頂點(diǎn)的度依次是A1，2，1，2B2，2，1，lC3，4，2，3D4，4，2，29若對(duì)下廈無(wú)向圖進(jìn)行深度優(yōu)先

6、遍歷，得到的正確遍歷序列是第3頁(yè)共9頁(yè)23.已知大根堆中的所有關(guān)鍵字均不相同，最大元素在難項(xiàng)，第2大元素可能存在的位置有2個(gè)，第3大元素可能存在的位置有_______個(gè)。24在有n個(gè)元素組成的順序表上進(jìn)行順序查找。若查找每個(gè)元素的概率相等，則查找成功時(shí)平均查找長(zhǎng)度是__甘肅自考網(wǎng)www.gsks.cc_____。25線性探查法和拉鏈法解決的是散列存儲(chǔ)中的_______問(wèn)題。三、解答題三、解答題(本大題共本大題共4小題，每小題小題，每小題

7、5分，共分，共2020分)26對(duì)題26圖中所給的二叉排序樹T回答下列問(wèn)題。(1)給出能生成r的2種關(guān)鍵字插入序列；(2)給出r的前序遍歷序列。27對(duì)題27圖所示的無(wú)向帶權(quán)圖G，回答下列問(wèn)題。(1)給出圖G的鄰接矩陣；(2)給出圖G的一棵最小生成樹。28現(xiàn)有5個(gè)權(quán)值分別是20、31、16、7和l5的葉結(jié)點(diǎn)，用它們構(gòu)造一棵哈夫曼樹，畫出該樹。29.對(duì)于給定的一組關(guān)鍵字序列26，l8，60，65，45，13，32，寫出使用直接選擇排序方法將其