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

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

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

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

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

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

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

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