2026年自考數(shù)據(jù)結(jié)構(gòu)重要考點(diǎn)復(fù)習(xí)題含答案一、單項(xiàng)選擇題（共10題，每題2分，共20分）1.在線(xiàn)性表的三種存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)）中，插入和刪除操作最方便的是（）。A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C.索引存儲(chǔ)D.都一樣2.若線(xiàn)性表L的長(zhǎng)度為n，則刪除L中第i個(gè)元素的算法的時(shí)間復(fù)雜度為（）。A.O(1)B.O(n)C.O(logn)D.O(n2)3.在順序存儲(chǔ)的線(xiàn)性表中，邏輯上相鄰的元素在物理存儲(chǔ)中（）。A.一定相鄰B.一定不相鄰C.可能相鄰也可能不相鄰D.以上都不對(duì)4.鏈表不具有的特點(diǎn)是（）。A.可隨機(jī)訪(fǎng)問(wèn)任意元素B.插入和刪除操作方便C.常用指針實(shí)現(xiàn)D.邏輯上相鄰元素物理上不一定相鄰5.若一個(gè)棧的輸入序列為1,2,3,4,5，則通過(guò)棧操作可以得到輸出序列3,2,1,5,4的輸出序列是（）。A.12345B.32154C.54321D.435216.隊(duì)列的“先進(jìn)先出”特性指的是（）。A.先進(jìn)入的元素先離開(kāi)B.后進(jìn)入的元素先離開(kāi)C.元素可以隨意進(jìn)出D.元素按順序進(jìn)出7.在樹(shù)形結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)擁有的子結(jié)點(diǎn)數(shù)稱(chēng)為（）。A.樹(shù)的深度B.樹(shù)的度C.結(jié)點(diǎn)的層次D.結(jié)點(diǎn)的子樹(shù)8.完全二叉樹(shù)的特點(diǎn)是（）。A.每個(gè)結(jié)點(diǎn)都有0個(gè)或2個(gè)子結(jié)點(diǎn)B.最后一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)一定在右側(cè)C.除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有2個(gè)子結(jié)點(diǎn)D.以上都不對(duì)9.在哈希表中，解決沖突的常用方法有（）。A.線(xiàn)性探測(cè)B.平方探測(cè)C.雙哈希D.以上都是10.在二分查找中，查找成功時(shí)，比較次數(shù)最多為（）。A.log?nB.log?(n+1)C.nD.n+1二、填空題（共10題，每題2分，共20分）1.線(xiàn)性表有兩種存儲(chǔ)結(jié)構(gòu)：__順序存儲(chǔ)__和__鏈?zhǔn)酱鎯?chǔ)__。2.在棧中，允許插入和刪除的一端稱(chēng)為_(kāi)_棧頂__，不允許插入和刪除的一端稱(chēng)為_(kāi)_棧底__。3.隊(duì)列的運(yùn)算原則是__先進(jìn)先出__，棧的運(yùn)算原則是__后進(jìn)先出__。4.在樹(shù)形結(jié)構(gòu)中，根結(jié)點(diǎn)的層次為_(kāi)_0__，其他結(jié)點(diǎn)的層次等于其父結(jié)點(diǎn)的層次加__1__。5.哈希表是通過(guò)__哈希函數(shù)__將鍵值映射到表中的存儲(chǔ)位置。6.在二分查找中，每次比較后將查找區(qū)間縮小為原來(lái)的一半，因此其時(shí)間復(fù)雜度為_(kāi)_O(logn)__。7.鏈表相比順序表，優(yōu)點(diǎn)是插入和刪除操作更方便，缺點(diǎn)是不能__隨機(jī)訪(fǎng)問(wèn)__元素。8.圖的兩種存儲(chǔ)結(jié)構(gòu)為_(kāi)_鄰接矩陣__和__鄰接表__。9.在完全二叉樹(shù)中，若結(jié)點(diǎn)的編號(hào)為i（從0開(kāi)始），則其左子結(jié)點(diǎn)的編號(hào)為_(kāi)_2i+1__，右子結(jié)點(diǎn)的編號(hào)為_(kāi)_2i+2__。10.堆是一種特殊的樹(shù)形結(jié)構(gòu)，分為_(kāi)_最大堆__和__最小堆__兩種。三、判斷題（共10題，每題2分，共20分）1.順序存儲(chǔ)的線(xiàn)性表可以隨機(jī)訪(fǎng)問(wèn)任何一個(gè)元素，時(shí)間復(fù)雜度為O(1)。（√）2.鏈表中的元素在物理存儲(chǔ)中一定是連續(xù)的。（×）3.棧是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。（×）4.隊(duì)列是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。（×）5.二叉樹(shù)的遍歷方式有前序遍歷、中序遍歷和后序遍歷三種。（√）6.哈希表的時(shí)間復(fù)雜度總是O(1)。（×）7.完全二叉樹(shù)的所有葉子結(jié)點(diǎn)都在最后一層。（√）8.圖的鄰接矩陣表示法適用于稀疏圖。（×）9.堆排序的時(shí)間復(fù)雜度為O(nlogn)。（√）10.樹(shù)的深度和度是同一個(gè)概念。（×）四、簡(jiǎn)答題（共5題，每題4分，共20分）1.簡(jiǎn)述棧和隊(duì)列的主要區(qū)別。答：棧和隊(duì)列的主要區(qū)別在于操作原則不同。棧是后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，只允許在棧頂進(jìn)行插入和刪除操作；隊(duì)列是先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，允許在隊(duì)頭進(jìn)行刪除操作，在隊(duì)尾進(jìn)行插入操作。2.解釋什么是二分查找，并說(shuō)明其適用條件。答：二分查找是一種在有序序列中查找特定元素的算法，通過(guò)每次將查找區(qū)間縮小一半來(lái)快速定位元素。適用條件：序列必須是有序的，且支持隨機(jī)訪(fǎng)問(wèn)。3.什么是哈希表？簡(jiǎn)述解決哈希沖突的兩種方法。答：哈希表是一種通過(guò)哈希函數(shù)將鍵值映射到表中存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。解決哈希沖突的兩種方法：線(xiàn)性探測(cè)（依次查找下一個(gè)空位）、平方探測(cè)（按平方序列查找空位）、雙哈希（使用另一個(gè)哈希函數(shù)）。4.簡(jiǎn)述完全二叉樹(shù)的特點(diǎn)。答：完全二叉樹(shù)的特點(diǎn)是除最后一層外，其他層都是滿(mǎn)的；最后一層的結(jié)點(diǎn)都集中在左側(cè)。5.什么是圖？簡(jiǎn)述圖的兩種存儲(chǔ)結(jié)構(gòu)及其優(yōu)缺點(diǎn)。答：圖是由頂點(diǎn)和邊組成的非線(xiàn)性結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)：鄰接矩陣（表示邊關(guān)系，適合稠密圖，但空間復(fù)雜度高）、鄰接表（適合稀疏圖，空間效率高，但查找邊較慢）。五、計(jì)算題（共5題，每題6分，共30分）1.已知一個(gè)棧的輸入序列為1,2,3,4,5，請(qǐng)給出一個(gè)通過(guò)棧操作可以得到輸出序列3,1,4,2,5的輸出序列。答：操作步驟：1.push(1)；2.push(2)；3.pop()→2；4.push(3)；5.pop()→3；6.push(4)；7.pop()→4；8.pop()→1；9.push(5)；10.pop()→5。2.設(shè)計(jì)一個(gè)哈希函數(shù)H(key)=keymod11，將鍵值序列{15,38,51,60,75}存入哈希表，使用線(xiàn)性探測(cè)法解決沖突。答：15mod11=4→H(15)=4；38mod11=5→H(38)=5；51mod11=8→H(51)=8；60mod11=5（沖突）→H(60)=6；75mod11=9→H(75)=9。哈希表：[_,_,_,15,38,51,60,_,_,75]。3.寫(xiě)出二分查找算法的遞歸實(shí)現(xiàn)，并說(shuō)明查找過(guò)程。答：pythondefbinary_search(arr,low,high,target):iflow>high:return-1mid=(low+high)//2ifarr[mid]==target:returnmidelifarr[mid]>target:returnbinary_search(arr,low,mid-1,target)else:returnbinary_search(arr,mid+1,high,target)查找過(guò)程：每次將區(qū)間分成兩半，比較中間值與目標(biāo)值，遞歸縮小范圍。4.給定一個(gè)圖G，頂點(diǎn)集V={A,B,C,D}，邊集E={(A,B),(A,C),(B,C),(B,D)}，用鄰接矩陣表示該圖。答：ABCDA0110B1011C1100D01005.已知一個(gè)完全二叉樹(shù)，結(jié)點(diǎn)編號(hào)從1開(kāi)始，結(jié)點(diǎn)D的父結(jié)點(diǎn)是B，結(jié)點(diǎn)B的父結(jié)點(diǎn)是A，求結(jié)點(diǎn)D的子結(jié)點(diǎn)編號(hào)。答：結(jié)點(diǎn)D的父結(jié)點(diǎn)是B，B的編號(hào)為3（假設(shè)根結(jié)點(diǎn)A為1，B為2，D為3），則D的子結(jié)點(diǎn)編號(hào)為6和7。六、應(yīng)用題（共2題，每題10分，共20分）1.設(shè)計(jì)一個(gè)算法，判斷一個(gè)給定序列是否為棧的出棧序列。答：pythondefis_stack_sequence(push_seq,pop_seq):stack=[]push_index=0forpopinpop_seq:whilenotstackorstack[-1]!=pop:ifpush_index>=len(push_seq):returnFalsestack.append(push_seq[push_index])push_index+=1stack.pop()returnTrue例如，push_seq=[1,2,3,4,5]，pop_seq=[3,2,1,5,4]，返回True。2.設(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)哈希表的插入和刪除操作，使用線(xiàn)性探測(cè)法解決沖突。答：插入操作：pythondefinsert_hashTable(hashTable,key,value):hash_val=key%len(hashTable)whilehashTable[hash_val]isnotNone:hash_val=(hash_val+1)%len(hashTable)hashTable[hash_val]=value刪除操作：pythondefdelete_hashTable(hashTable,key):hash_val=key%len(hashTable)whilehashTable[hash_val]isnotNone:ifhashTable[hash_val]==key:hashTable[hash_val]=NonereturnTruehash_val=(hash_val+1)%len(hashTable)returnFalse答案與解析單項(xiàng)選擇題1.B2.B3.A4.A5.B6.A7.B8.B9.D10.D填空題1.順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)2.棧頂、棧底3.先進(jìn)先出、后進(jìn)先出4.0、15.哈希函數(shù)6.O(logn)7.隨機(jī)訪(fǎng)問(wèn)8.鄰接矩陣、鄰接表9.2i+1、2i+210.最大堆、最小堆判斷題1.√2.×3.×4.×5.√6.×7.√8.×9.√10.×簡(jiǎn)答題1.棧是LIFO，隊(duì)列是FIFO；棧操作端固定，隊(duì)列兩端操作不同。2.二分查找在有序序列中每次將區(qū)間減半，時(shí)間復(fù)雜度O(logn)。3.哈希表通過(guò)哈希函數(shù)映射鍵值，沖突解決方法有線(xiàn)性探測(cè)、平方探測(cè)、雙哈希。4.完全二叉樹(shù)除最后一層外其他層滿(mǎn)，最后一層結(jié)點(diǎn)左對(duì)齊。5.圖是頂點(diǎn)和邊的集合，鄰接