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

1、精品自學(xué)考試資料推薦全國(guó) 2018年 1月高等教育自學(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. 數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)是指 ( )5A. 數(shù)組、鏈表、樹(shù)、圖形結(jié)構(gòu)C. 線性結(jié)構(gòu)、鏈表、樹(shù)、圖形結(jié)構(gòu)B. 線性表、鏈表、棧隊(duì)列、數(shù)組廣義表D. 集合、線性結(jié)構(gòu)、樹(shù)、圖形結(jié)構(gòu)2. 數(shù)據(jù)結(jié)構(gòu)中，通常采用兩種方法衡量算法的時(shí)間復(fù)雜性，即()A. 最大時(shí)間復(fù)雜性和最小時(shí)間復(fù)雜性B. 最好時(shí)間復(fù)雜性和最壞時(shí)間復(fù)雜性C. 部分時(shí)間復(fù)

2、雜性和總體時(shí)間復(fù)雜性D. 平均時(shí)間復(fù)雜性和最壞時(shí)間復(fù)雜性3. 下列關(guān)于線性表的敘述中，不正確的是 ()A. 線性表是 n 個(gè)結(jié)點(diǎn)的有窮序列B. 線性表可以為空表C. 線性表的每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)前趨和一個(gè)后繼D. 線性表結(jié)點(diǎn)間的邏輯關(guān)系是 1:1的聯(lián)系4在一個(gè)單鏈表中，若 p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，則刪除 p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的正確操作 是()B.p->next=p->nextD.p->next=pA.p=p->nextC.p->next=p->next->next5.棧和隊(duì)列 ()A. 共同之處在于二者都是先進(jìn)先出的特殊的線性表B. 共同之處在于二者

3、都是先進(jìn)后出的特殊的線性表C. 共同之處在于二者都只允許在頂端執(zhí)行刪除操作D. 沒(méi)有共同之處6二維數(shù)組A : 5: :6采用按列為主序的存儲(chǔ)方式，每個(gè)元素占3個(gè)存儲(chǔ)單元，若 A : 0:0的存儲(chǔ)地址是100,則A : 4: 3的存儲(chǔ)地址是()A.127B.142C.150D.1577深度為k的二叉樹(shù)至多有()A.2k個(gè)結(jié)點(diǎn)B.2k-1個(gè)結(jié)點(diǎn)C.2k-1個(gè)結(jié)點(diǎn)D.2k-1-1個(gè)結(jié)點(diǎn)8對(duì)于如圖所示二叉樹(shù)采用中根遍歷，正確的遍歷序列應(yīng)為()A.ABCDEFB.ABECDFC.CDFBEAD.CBDAEF9下面關(guān)于生成樹(shù)的描述中，不正確的是()A. 生成樹(shù)是樹(shù)的一種表現(xiàn)形式B. 生成樹(shù)一定是連通的C.

4、 生成樹(shù)一定不含有環(huán)D. 若生成樹(shù)頂點(diǎn)個(gè)數(shù)為n,則其邊數(shù)一定為 n-110圖的鄰接表如下所示，從頂點(diǎn) Vi出發(fā)采用深度優(yōu)先搜索法遍歷該圖，則可能的頂點(diǎn)序列 是()A.V 1V2V3V4V5B.V1V2V3V5V4C.V1V4V3V5V211. 下列查找方法中，不屬于動(dòng)態(tài)的查找方法是A.二叉排序樹(shù)法C.散列法12. 要解決散列引起的沖突問(wèn)題，常采用的方法有A. 數(shù)字分析法、平方取中法B. 數(shù)字分析法、線性探測(cè)法D.V1V3V4V5V2( )B.平衡樹(shù)法D.斐波那契查找法( )C. 二次探測(cè)法、平方取中法D. 二次探測(cè)法、鏈地址法13.用于外存儲(chǔ)器的數(shù)據(jù)組織結(jié)構(gòu)散列文件，主要適用于()A.順序存取

5、B.隨機(jī)存取C.索引存取D.以上三種都可以14. 堆排序?qū)儆谝环N選擇排序，其時(shí)間復(fù)雜性為A.O(1)C.O( n)15. 下列排序方法中，屬于不穩(wěn)定的排序方法是A.直接插入排序法( )B.O(nlog 2n)D.O( n2)( )B.冒泡排序法C.基數(shù)排序法二、填空題(本大題共13小題，每小題D.歸并排序法2分，共26分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16. 根據(jù)不同的描述方式，對(duì)數(shù)據(jù)的操作運(yùn)算通?？煞譃榧庸ば瓦\(yùn)算和兩種基本類型。17. 數(shù)據(jù)結(jié)構(gòu)中的算法，通常采用最壞時(shí)間復(fù)雜度和 兩種方法衡量其效率。18. 判斷帶頭結(jié)點(diǎn)head的單鏈表為空的條件是 。19. 若順序表每個(gè)元

6、素長(zhǎng)度均為 5,其中第一個(gè)元素的存儲(chǔ)地址為30,則第6個(gè)元素的存儲(chǔ)地址為。20. 若front和rear分別表示循環(huán)隊(duì)列 Q的頭指針和尾指針，m0表示該隊(duì)列的最大容量，則判斷循環(huán)隊(duì)列為滿的條件是 。21. 對(duì)于順序存儲(chǔ)結(jié)構(gòu)的二維數(shù)組，通常采用 兩種存放方式存儲(chǔ)數(shù)據(jù)元素。22. 若某二叉樹(shù)的先根遍歷序列為CEDBA，中根遍歷序列為 DEBAC，則其后根遍歷序列為23. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其深度為 。24圖主要采用兩種存儲(chǔ)結(jié)構(gòu)存放。25. 索引順序查找通常分兩個(gè)階段進(jìn)行，首先采用順序查找法或二分法確定所要查找的塊，然后再用法在塊中找到具體的元素值。26. 二叉排序樹(shù)是一種特殊的有序表，若要

7、保證輸出序列其鍵值完全按遞增排列，則應(yīng)對(duì)二叉排序樹(shù)采用法遍歷。27. 文件常見(jiàn)的存儲(chǔ)結(jié)構(gòu)有順序文件、鏈接文件、索引文件和四種。28. 在各種內(nèi)部排序中，占用存儲(chǔ)空間較大的排序通常是 排序。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）29. 已知某二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如圖所示，試畫(huà)出該二叉樹(shù)。ABCDEFG30.試用Prim算法構(gòu)造下圖的最小生成樹(shù)，要求分步給出構(gòu)造過(guò)程31. 已知散列函數(shù)為 H（key）=key%7，散列表長(zhǎng)度為 7（散列地址空間為 0.6），待散列序列為: （25，48，32，50，68）。要求：（1）根據(jù)以上條件構(gòu)造一散列表，并用線性探測(cè)法解決有關(guān)地址沖突；（2）若要用該散列表查找元素68,給出所需的比較次數(shù)。32. 已知一組鍵值序列為（38，64，73，52, 40，37，56, 43），試采用快速排序法對(duì)該組序列 作升序排序，并給出每一趟的排序結(jié)果。33. 已知一組鍵值序列 （26， 21，32，56，78，89，90），試采用二路歸并排序法對(duì)該組序列 作升序排序，并給出每一趟的排序結(jié)果。四、設(shè)計(jì)題 （本大題共 2 小題，每小題 7分，共 14分）34.