2016年高等教育自學(xué)考試《數(shù)據(jù)構(gòu)造》試卷

...wd......wd......wd...2016年10月高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)構(gòu)造試卷(課程代碼02331)本試卷共7頁，總分值l00分，考試時間l50分鐘?？忌痤}本卷須知：1．本卷所有試題必須在答題卡上作答。答在試卷上無效，試卷空白處和反面均可作草稿紙。2．第一局部為選擇題。必須對應(yīng)試卷上的題號使用2B鉛筆將“答題卡〞的相應(yīng)代碼涂黑。3．第二局部為非選擇題。毖須注明大、小題號，使用0．5毫米黑色字跡簽字筆作答。4．合理安排答題空間，超出答題區(qū)域無效。第一局部選擇題(共30分)一、單項選擇題(本大題共l5小題，每題2分，共30分>在每題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題卡〞的相應(yīng)代碼涂黑。錯涂、多涂或未涂均無分。1．以下選項中，不屬于線性構(gòu)造特征的是A．數(shù)據(jù)元素之間存在線性關(guān)系B．構(gòu)造中只有一個開場結(jié)點C．構(gòu)造中只有一個終端結(jié)點D．每個結(jié)點都僅有一個直接前趨2．設(shè)l7個元素的順序表中，假設(shè)將第個元素e移動到第個位置，不改變除e外其他元素之間的相對次序，那么需移動的表中元素個數(shù)是3．假設(shè)用一個大小為7的數(shù)組作為循環(huán)隊列的存儲構(gòu)造，且當前rew和盤0nt的值分別為2和4，在此之前的操作是從隊列中刪除了一個元素及參加兩個元素，請問這3個操作之前rear和矗0nt的值分別是A．0和lB．0和3C．3和6D．4和54．廣義表LS=(((a))，((b，(c))，(d，(e，f)))，0)，LS的長度是A．2B．3C．4D.55．一棵完全二叉樹T的全部k個葉結(jié)點都在同一層中且每個分支結(jié)點都有兩個孩子結(jié)點。于中包含的結(jié)點數(shù)是A．kB.2k-1C．k2D．2k-16．如果某二叉樹的前序遍歷序列為abced，中序遍歷序列為cebda，那么該二叉樹的后序遍歷序列是A．cedbaB．decbaC．ecdbaD．ecbad7．一個森林有m棵樹，頂點總數(shù)為n，那么森林中含有的總邊數(shù)是A．mB.n-lC．n-mD．n+m8．設(shè)圖的鄰接矩陣A如下所示。各頂點的度依次是A．1，2，1，2B．2，2，1，lC．3，4，2，3D．4，4，2，29．假設(shè)對下廈無向圖進展深度優(yōu)先遍歷，得到的正確遍歷序列是A．h，C，a，b，d，e，g，fB．e，a，f，g，b，h，c，dC.d，b，c，a，h，e，f，gD．a(chǎn)，b，C，d，h，e，f，g10．己知有向圖G如下所示，G的拓撲序列是A．a(chǎn)，b，e，c，d，f,gB．a(chǎn)，c，b，f，d，e，gC.a，C，d，e，b，f，gD.a，c，d，f，b，e，g11．以下排序算法中，在每一趟都能選出一個元素放到其最終位置上的是A．插入排序B．希爾排序C．歸并排序D．直接選擇排序12．對一組數(shù)據(jù)(2，l2，16，88，5，10)進展排序，假設(shè)前3趟排序結(jié)果如下：第一趟：2，12，l6，5，10，88第二趟：2，12，5，l0，16，88第三趟：2，5，10，l2，l6，88那么采用的排序方法是A．冒泡排序B．希爾排序C．歸并排序D．基數(shù)排序13．設(shè)有序表為{9，l2，21，32，41，45，52}，當二分查找值為52的結(jié)點時，元素之間的對比次數(shù)是A．1B．2C．3D．414．以下選項中，既熊捌回事存儲構(gòu)造也能在鏈式存儲構(gòu)造上進展查找的方法是A．散列查找B．順序查找C．二分查找D．以上選項均不能15．在一棵5階B樹中，每個非根結(jié)點中所含關(guān)鍵字的個數(shù)最少是A．1B．2C．3D．4第二局部非選擇題(共70分)二、填空題(本大題共l0小題，每題2分，共20分)16．兩個棧S1和S2共用含100個元素的數(shù)組S[0一99]，為充分利用存儲空間，假設(shè)S2的棧底元素保存在S[99]中，那么S1的棧底元素保存在_______中。17．在一個單鏈表中，指針變量q所指結(jié)點不是表尾結(jié)點，假設(shè)在q所指結(jié)點之后插入指針變量S所指結(jié)點，那么正確的執(zhí)行語句是_______。18．設(shè)順序表第1個元素的存儲地址是1000，每個數(shù)據(jù)元素占6個地址單元，那么第11個元素的存儲地址是_______。19．二叉樹采用順序存儲方式保存，結(jié)點Z保存在數(shù)組A[7]中，假設(shè)X有右孩子結(jié)點L那么Y保存在_______中。20．一棵二叉樹中，度數(shù)為l的結(jié)點個數(shù)為n1，度數(shù)為2的結(jié)點個數(shù)為n2，那么葉結(jié)點的個數(shù)為_______。21．廣義表LS=((≈b)，c，d)，head(LS)是_______。22．在無向圖G的鄰接矩陣A中，=_______。23.大根堆中的所有關(guān)鍵字均不一樣，最大元素在難項，第2大元素可能存在的位置有2個，第3大元素可能存在的位置有_______個。24．在有n個元素組成的順序表上進展順序查找。假設(shè)查找每個元素的概率相等，那么查找成功時平均查找長度是__甘肅自考網(wǎng)gsks.cc_____。25．線性探查法和拉鏈法解決的是散列存儲中的_______問題。三、解答題(本大題共4小題，每題5分，共20分)26．對題26圖中所給的二叉排序樹T答復(fù)以下問題。(1)給出能生成r的2種關(guān)鍵字插入序列；(2)給出r的前序遍歷序列。27．對題27圖所示的無向帶權(quán)圖G，答復(fù)以下問題。(1)給出圖G的鄰接矩陣；(2)給出圖G的一棵最小生成樹。28．現(xiàn)有5個權(quán)值分別是20、31、16、7和l5的葉結(jié)點，用它們構(gòu)造一棵哈夫曼樹，畫出該樹。29.對于給定的一組關(guān)鍵字序列{26，l8，60，65，45，13，32}，寫出使用直接選擇排序方法將其排成升序序列的過程。四、算法閱讀題(本大題共4小題，每題5分，共20分)30．設(shè)非空雙向循環(huán)鏈表L的頭指針為head，表結(jié)點類型為DLNode，定義如下。初始時，L中所有結(jié)點的prior域均為空(NULL)，next域和data域中已經(jīng)正確賦值。如題30圖a所示。函數(shù)f30完成的功能是：將L中各結(jié)點的prior域正確賦值，使L成為雙向循環(huán)鏈表。如題30圖b所示。將空白處應(yīng)填寫的內(nèi)容答在答題卡上。31．二叉樹的二叉鏈表類型定義如下，閱讀程序，并答復(fù)以下問題。假設(shè)二叉樹如下所示，寫