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

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

2、量級(jí)復(fù)雜性等于線性階量級(jí)D.兩者之間無(wú)法比較3. 下列關(guān)于線性表的基本操作屮，屬于加工型的操作是（A.初始化、求表長(zhǎng)度、插入操作B.初始化、插入、刪除操作C.求表長(zhǎng)度、讀元素、定位操作D.定位、插入、刪除操作4. 在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，s指向已生成的新結(jié)點(diǎn)，則在 p之后插入S所指結(jié)點(diǎn)的正確操作是(As - >nex1=p - >next;p - >nexlFs;B.4種D.6種）B.按列為主的存儲(chǔ)結(jié)構(gòu)D .具體存儲(chǔ)結(jié)構(gòu)無(wú)法確定）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. 若有三個(gè)字符的字符串序列執(zhí)行入棧操作，則其所有可能的輸出排列共有（A.3種C.5種6. C語(yǔ)言對(duì)數(shù)組元素的存放方式通常采用（A.按行為主的存儲(chǔ)結(jié)構(gòu)C .按行或列為主的存儲(chǔ)結(jié)構(gòu)7. 根據(jù)定義，樹(shù)的葉子結(jié)點(diǎn)其度數(shù)（A.必大于0C.必等于18. 二叉樹(shù)若采用二叉鏈表結(jié)構(gòu)表示，則對(duì)于n個(gè)結(jié)點(diǎn)的二叉樹(shù)一定有（A. 2n個(gè)指針域其中n個(gè)指針為NULLB. 2n個(gè)指針域其屮n+1個(gè)指針為NULLC. 2n-1個(gè)指針域其中n個(gè)指針為NULLD. 2n-1個(gè)指針域其中n+1個(gè)指針為NULL

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

5、（)A.索引表和主文件均必須是有序文件B.索引表和主文件均可以是無(wú)序文件C.索引表必須是有序文件D.主文件必須是有序文件14.直接插入排序算法，其時(shí)間復(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分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16. 從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)，數(shù)據(jù)通?？煞譃槿齻€(gè)層次，即：數(shù)據(jù)、數(shù)據(jù)元素和o17. 用程序設(shè)計(jì)語(yǔ)言、偽程序設(shè)計(jì)語(yǔ)言并混合自然語(yǔ)言描述的算法稱為算法。18. 對(duì)順

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

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