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

1、精品自學(xué)考試資料推薦全國 2018年 1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼： 02142一、單項選擇題 (本大題共 15小題，每小題 2 分，共 30分) 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的 括號內(nèi)。錯選、多選或未選均無分。1. 數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)是指 ( )5A. 數(shù)組、鏈表、樹、圖形結(jié)構(gòu)C. 線性結(jié)構(gòu)、鏈表、樹、圖形結(jié)構(gòu)B. 線性表、鏈表、棧隊列、數(shù)組廣義表D. 集合、線性結(jié)構(gòu)、樹、圖形結(jié)構(gòu)2. 數(shù)據(jù)結(jié)構(gòu)中，通常采用兩種方法衡量算法的時間復(fù)雜性，即()A. 最大時間復(fù)雜性和最小時間復(fù)雜性B. 最好時間復(fù)雜性和最壞時間復(fù)雜性C. 部分時間復(fù)

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

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

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

5、B.隨機(jī)存取C.索引存取D.以上三種都可以14. 堆排序?qū)儆谝环N選擇排序，其時間復(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分)請在每小題的空格中填上正確答案。錯填、不填均無分。16. 根據(jù)不同的描述方式，對數(shù)據(jù)的操作運(yùn)算通常可分為加工型運(yùn)算和兩種基本類型。17. 數(shù)據(jù)結(jié)構(gòu)中的算法，通常采用最壞時間復(fù)雜度和 兩種方法衡量其效率。18. 判斷帶頭結(jié)點head的單鏈表為空的條件是 。19. 若順序表每個元

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

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