2023年10月自考02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

絕密★考試結(jié)束前2023年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼:021421.請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。2.答題前,考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。選擇題部分注意事項(xiàng):每小題選出答案后,用2B鉛筆把答題紙上對應(yīng)題目的答案標(biāo)號涂黑。如需改動,用橡皮擦干凈后,再選涂其他答案標(biāo)號。不能答在試題卷上。一、單項(xiàng)選擇題:本大題共15小題,每小題2分,共30分。在每小題列出的備選項(xiàng)中只有一項(xiàng)是最符合題目要求的,請將其選出。1.時間復(fù)雜度的常數(shù)階表示為()A.O1B.On()C.On(2)()nD.O22.下列關(guān)于單鏈表的描述,錯誤的是??A.所有結(jié)點(diǎn)通過指針鏈接形成鏈表B.頭指針變量不一定非要用head來標(biāo)識D.通常用尾指針來表示一個單鏈表C.尾結(jié)點(diǎn)指針域的值NULL3.線性表實(shí)現(xiàn)順序存儲可使用稱為空指針A.棧B.隊(duì)列4.設(shè)單鏈表中指針p指向結(jié)點(diǎn)A,要刪除A之后的結(jié)點(diǎn)(若存在),則修改指針的操作為A.pnext=pC.p=pnextnextC.數(shù)組D.鏈表nextnextB.p=pnextD.pnext=p5.出隊(duì)列操作使用的賦值語句是A.SQ.rear=SQ.rear+1B.SQ.rear=SQ.rear-1D.SQ.front=SQ.front-1C.SQ.front=SQ.front+16.在一個具有n個單元的順序棧中,假定以地址低端(即0單元)作為棧底,以top為棧頂指針,當(dāng)棧未滿時進(jìn)行進(jìn)棧操作,此時A.top不變B.top--C.top++D.top=0浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第1頁(共4頁)7.帶頭結(jié)點(diǎn)鏈隊(duì)列的頭指針和尾指針分別為front和rear,則判斷隊(duì)列空的條件為!B.front=NULLA.front==rear!C.rear=NULLD.front==NULL8.深度為kk≥1()的二叉樹的結(jié)點(diǎn)數(shù)最多為A.2k-1B.2-1kkC.2+1D.2k+19.下列關(guān)于樹形結(jié)構(gòu)的描述,正確的是A.樹形結(jié)構(gòu)是線性結(jié)構(gòu)B.樹中每個結(jié)點(diǎn)可以有多個直接前驅(qū)結(jié)點(diǎn)D.樹中每個結(jié)點(diǎn)只能有一個直接后繼結(jié)點(diǎn)C.樹可以用順序存儲10.對任何一棵二叉樹,若度數(shù)為0的結(jié)點(diǎn)(葉結(jié)點(diǎn))個數(shù)為n0,度數(shù)為2的結(jié)點(diǎn)個數(shù)為n2,則等于n0A.0B.n-12C.n2D.n+1211.設(shè)有10個頂點(diǎn)的無向圖,若它為連通圖,則它具有的邊數(shù)最少為A.9B.10C.11D.1212.設(shè)含有n個頂點(diǎn),e條弧的有向圖G采用鄰接表存儲,則拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度為()A.On()()C.On(2)B.On+eD.On×e13.當(dāng)查找表中有n個數(shù)據(jù)元素時,假設(shè)(,,…,)為查找第i個元素的概率,在P等概Pi=12nii率的條件下,順序查找算法的平均查找長度為/A.n2()/B.n+12C.nD.n+114.二維數(shù)組A以行為主序存儲,每個元素占1個存儲單元。若元素A1[][]1的存儲地址是420A3,[][]3的存儲地址是446,則A5[][]5的存儲地址是A.470B.471C.472D.47315.冒泡排序?qū)儆贏.插入排序B.歸并排序C.選擇排序D.交換排序非選擇題部分注意事項(xiàng):用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上,不能答在試題卷上。二、填空題:本大題共13小題,每小題2分,共26分。16.在數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)又稱為字段或17.在單鏈表存儲結(jié)構(gòu)中,線性表的表長等于單鏈表中18.二叉樹的順序存儲結(jié)構(gòu)可以用維數(shù)組來實(shí)現(xiàn)。19.在操作系統(tǒng)中,為了保持多個進(jìn)程、、?！慕Y(jié)點(diǎn)個數(shù)?！鳳1P2P3和P4按某種次序依次執(zhí)行,需要一個▲來實(shí)現(xiàn)這個過程。浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第2頁(共4頁)20.對稱矩陣有近一半元素可以通過其對稱元素獲得,因此可將含有n2個元素的對稱矩陣壓個元素的一維數(shù)組中。21.設(shè)有一個帶頭結(jié)點(diǎn)的鏈棧,其頭指針為head,現(xiàn)有一個新結(jié)點(diǎn)入棧,指向該結(jié)點(diǎn)的指針為縮存儲到含有▲p,則入棧操作為和▲headnext=p。22.滿二叉樹一定是二叉樹?！?3.在樹形結(jié)構(gòu)中,結(jié)點(diǎn)間具有24.在圖中,序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為問題。方法和Kruskal方法。27.若在查找過程中,向表中插入不存在的數(shù)據(jù)元素,或者從表中刪除某個數(shù)據(jù)元素,則稱此類查找表。28.在二分查找、索引順序查找和散列查找三種查找方法中,平均查找長度與元素個數(shù)沒有關(guān)關(guān)系。▲路徑?！?5.Dijkstra算法用于求26.求最小生成樹有▲▲表為▲系的查找方法是?！?yīng)用題:本大題共5小題,每小題6分,共30分。29.ABC設(shè)有一個鏈棧的輸入序列為、、,當(dāng)輸出序列分別為ABC和BCA時,請寫出對應(yīng)的進(jìn)棧和出棧過程。30.設(shè)有一森林F如題30圖所示,請分別寫出先序遍歷和中序遍歷的序列。題30圖31.如題31圖所示長度為13的散列表,其散列函數(shù)為Hkey=keymod13(),在表中已填入鍵值分別為163054,,的元素。()1現(xiàn)要插入鍵值為29的元素,應(yīng)用線性探測法,計算填入散列表中單元的序號。(要求給出求解過程)()2線性探測法中,如何減少堆積的機(jī)會?0123456789101112541630題31圖浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第3頁(共4頁)32.如題32圖所示的圖結(jié)構(gòu),請寫出以10為源點(diǎn)的廣度優(yōu)先搜索得到的頂點(diǎn)訪問序列,并畫出搜索過程圖。(同等情況下,值小的結(jié)點(diǎn)優(yōu)先訪問)題32圖33.給定有序表D={006087155188220465505508511586656670700766,,,,,,,,,,,,,},用二分查找法在D中查找511,試給出查找過程。四、算法設(shè)計題:本大題共2小題,每小題7分,共14分。34