2020年10月全國數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考試題及答案解析

1、精品自學(xué)考料推薦.全國2019年10月高等教育自學(xué)考試 數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題 課程代碼：02142一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列岀的四個備選項屮只有一個是符合題目要求的，請將其代碼填寫在題后的 括號內(nèi)。錯選、多選或未選均無分。1要將現(xiàn)實生活中的數(shù)據(jù)轉(zhuǎn)化為計算機(jī)所能表示的形式，其轉(zhuǎn)化過程依次為（機(jī)外表示邏輯結(jié)構(gòu)A.邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、機(jī)外表示B.存儲結(jié)構(gòu)、邏輯結(jié)構(gòu)、C.機(jī)外表示、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)D.機(jī)外表示、存儲結(jié)構(gòu)、2. 若評價算法的時間復(fù)雜性，比較對數(shù)階量級與線性階量級，通常（A.對數(shù)階量級復(fù)雜性大于線性階量級B .對數(shù)階量級復(fù)雜性小于線性階量級C .對數(shù)階

2、量級復(fù)雜性等于線性階量級D.兩者之間無法比較3. 下列關(guān)于線性表的基本操作屮，屬于加工型的操作是（A.初始化、求表長度、插入操作B.初始化、插入、刪除操作C.求表長度、讀元素、定位操作D.定位、插入、刪除操作4. 在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，s指向已生成的新結(jié)點，則在 p之后插入S所指結(jié)點的正確操作是(As - >nex1=p - >next;p - >nexlFs;B.4種D.6種）B.按列為主的存儲結(jié)構(gòu)D .具體存儲結(jié)構(gòu)無法確定）B.必等于0D.必等于2B.p - >nex!Fs - >next; s - >nextFp ;D .s - &

3、gt;next=p - >next; p二s;C.s - >nexFp ; p - >nex!Fs;5. 若有三個字符的字符串序列執(zhí)行入棧操作，則其所有可能的輸出排列共有（A.3種C.5種6. C語言對數(shù)組元素的存放方式通常采用（A.按行為主的存儲結(jié)構(gòu)C .按行或列為主的存儲結(jié)構(gòu)7. 根據(jù)定義，樹的葉子結(jié)點其度數(shù)（A.必大于0C.必等于18. 二叉樹若采用二叉鏈表結(jié)構(gòu)表示，則對于n個結(jié)點的二叉樹一定有（A. 2n個指針域其中n個指針為NULLB. 2n個指針域其屮n+1個指針為NULLC. 2n-1個指針域其中n個指針為NULLD. 2n-1個指針域其中n+1個指針為NULL

4、9. 在一個無向圖屮，所有頂點的度數(shù)之和等于邊數(shù)的（）A.1倍B.2倍C .3倍D .4倍10. 若采用鄰接表存儲結(jié)構(gòu)，則圖的廣度優(yōu)先搜索類似于二叉樹的（1精品自學(xué)考料推薦.A.先根遍歷B.中根遍歷C. 后根遍歷D.層次遍歷11. 采用順序查找法，若在表頭設(shè)置崗哨，則正確的查找方式通常為（）A. 從第0個元素開始往后查找該數(shù)據(jù)元素B. 從第1個元素開始往后查找該數(shù)據(jù)元素C .從第n個元素開始往前查找該數(shù)據(jù)元素D. 從第n+1個元素開始往前查找該數(shù)據(jù)元素12.下列查找屮，效率最高的查找方法是（)A.順序查找B.折半查找C.索引順序查找D.分塊查找13.索引文件通常由索引表和主文件兩部分構(gòu)成，其中

5、（)A.索引表和主文件均必須是有序文件B.索引表和主文件均可以是無序文件C.索引表必須是有序文件D.主文件必須是有序文件14.直接插入排序算法，其時間復(fù)雜性為（)A.0 (1)B.O (n)C .0 (nbg 2n)D.O (h 2)15.下列排序方法中，屬于穩(wěn)定的排序方法是( )A.直接插入排序法B.快速排序法C.冒泡排序法D.堆排序法二、填空題（本大題共 13小題，每小題2分，共26分）請在每小題的空格中填上正確答案。錯填、不填均無分。16. 從數(shù)據(jù)結(jié)構(gòu)的觀點，數(shù)據(jù)通?？煞譃槿齻€層次，即：數(shù)據(jù)、數(shù)據(jù)元素和o17. 用程序設(shè)計語言、偽程序設(shè)計語言并混合自然語言描述的算法稱為算法。18. 對順

6、序表執(zhí)行插入操作，其插入算法的平均時間復(fù)雜性為 o19. 在具有n個單元、且采用順序存儲的循環(huán)隊列中，隊滿時共有 個元素。20. 若缸nt和xe吐分別表示循環(huán)隊列Q的頭指針和尾指針，m 0表示該隊列的最大容量，貝I循環(huán)隊列為空的條件是 o21. 二維數(shù)組AtlOlO采用按行為主序的存儲方式，每個元素占4個存儲單元，若 AK）O的存儲地址為300,則A1010的地址為o22. 樹的遍歷主要有先根遍歷、后根遍歷和 三種。23. 深度為k的完全二叉樹至少有 個結(jié)點。24. 若圖的鄰接矩陣是一個對稱矩陣，則該圖一定是一個 o25. 對于具有n個元素的數(shù)據(jù)序列，采用二叉排序樹查找，其平均查找長度為 &l

7、t;26. 要完全避免散列所產(chǎn)生的“堆積”現(xiàn)象，通常采用 法。27. EAM其中文含義為方法。28. 在最好的情況下，對于具有n個元素的有序序列，若采用冒泡排序，所需的比較次數(shù)為 次。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）29. 已知某二叉樹如下圖所示，試給出其二叉鏈表及順序存儲結(jié)構(gòu)表示。30. 若某無向圖G的鄰接表如圖所示，試給出以頂點VI為岀發(fā)點，按廣度優(yōu)先搜索所產(chǎn)生的一棵 生成樹。31. 已知某二叉排序樹 10個結(jié)點的值依次為 廣10,其結(jié)構(gòu)如圖所示，試標(biāo)出該二叉樹各結(jié) 點所對應(yīng)的具體值。32. 已知一組鍵值序列(28, 47, 35, 42, 53, 60, 34, 22)，試給出釆用直接插入排序法對 該組序列作升序排序的每一-趟結(jié)果。33. 已知一組鍵值序列(3, 6, 8, 9, 2, 7, 4, 3),試采用快速排序法對該組序列作升序排 序，并給出每一趟的排