2025年研考數(shù)據(jù)結(jié)構(gòu)真題及答案

一、單項(xiàng)選擇題1.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，其地址（）。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以答案：D2.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣存儲(chǔ)，則該矩陣的大小是（）。A.nB.(n-1)2C.n2D.(n+1)2答案：C3.若一棵完全二叉樹(shù)有768個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)是（）。A.257B.258C.384D.385答案：C4.已知一個(gè)棧的入棧序列是1,2,3,4,5，下列序列中不可能是棧的輸出序列的是（）。A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,5答案：C5.對(duì)關(guān)鍵碼序列(23,17,14,60,50,25,36)進(jìn)行增量為3的一趟希爾排序的結(jié)果為（）。A.(14,17,23,25,36,50,60)B.(23,17,14,50,25,36,60)C.(14,17,23,50,25,36,60)D.(14,23,17,50,25,36,60)答案：C6.在有n個(gè)關(guān)鍵字的平衡二叉排序樹(shù)中查找一個(gè)關(guān)鍵字，其平均查找長(zhǎng)度的數(shù)量級(jí)為（）。A.O(n)B.O(log?n)C.O(n2)D.O(nlog?n)答案：B7.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m-1]中，則入隊(duì)時(shí)的操作為（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)答案：C8.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為（）。A.O(1)B.O(n)C.O(log?n)D.O(n2)答案：C9.已知廣義表L=((a,b,c),(d,e,f))，則取出原子e的運(yùn)算是（）。A.tail(head(L))B.head(tail(head(L)))C.head(tail(tail(head(L))))D.head(tail(tail(head(tail(L)))))答案：C10.用DFS遍歷一個(gè)無(wú)環(huán)有向圖，并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是（）。A.逆拓?fù)溆行駼.拓?fù)溆行駽.無(wú)序的D.按頂點(diǎn)編號(hào)次序答案：A二、多項(xiàng)選擇題1.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有（）。A.棧B.隊(duì)列C.樹(shù)D.圖答案：AB2.下列關(guān)于二叉排序樹(shù)的說(shuō)法正確的有（）。A.二叉排序樹(shù)左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值B.二叉排序樹(shù)右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值C.二叉排序樹(shù)一定是平衡二叉樹(shù)D.對(duì)二叉排序樹(shù)進(jìn)行中序遍歷可以得到一個(gè)有序序列答案：ABD3.關(guān)于圖的存儲(chǔ)結(jié)構(gòu)，以下說(shuō)法正確的是（）。A.鄰接矩陣適合存儲(chǔ)稠密圖B.鄰接表適合存儲(chǔ)稀疏圖C.十字鏈表是有向圖的一種存儲(chǔ)結(jié)構(gòu)D.鄰接多重表是無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu)答案：ABCD4.排序算法中，屬于穩(wěn)定排序的有（）。A.冒泡排序B.插入排序C.歸并排序D.堆排序答案：ABC5.下列關(guān)于棧和隊(duì)列的說(shuō)法正確的是（）。A.棧是后進(jìn)先出的線性表B.隊(duì)列是先進(jìn)先出的線性表C.棧和隊(duì)列都可以用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)D.棧和隊(duì)列都可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)答案：ABCD6.樹(shù)的遍歷方式有（）。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷答案：ACD7.哈希函數(shù)的構(gòu)造方法有（）。A.直接定址法B.數(shù)字分析法C.平方取中法D.折疊法答案：ABCD8.以下關(guān)于線性表的說(shuō)法正確的是（）。A.順序表可以隨機(jī)存取元素B.鏈表的插入和刪除操作不需要移動(dòng)大量元素C.順序表的存儲(chǔ)密度高D.鏈表適合頻繁的插入和刪除操作答案：ABCD9.對(duì)于一個(gè)帶權(quán)有向圖G，若要計(jì)算單源最短路徑，可采用的算法有（）。A.Dijkstra算法B.Floyd算法C.Prim算法D.Kruskal算法答案：AB10.以下屬于查找算法的有（）。A.順序查找B.二分查找C.哈希查找D.平衡二叉排序樹(shù)查找答案：ABCD三、判斷題1.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更節(jié)省存儲(chǔ)空間。（）答案：×2.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度不能超過(guò)2，所以二叉樹(shù)是一種特殊的樹(shù)。（）答案：×3.圖的廣度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的層次遍歷。（）答案：√4.快速排序在任何情況下的時(shí)間復(fù)雜度都是O(nlog?n)。（）答案：×5.哈希表是一種基于查找關(guān)鍵字直接計(jì)算出該記錄存儲(chǔ)地址的存儲(chǔ)結(jié)構(gòu)。（）答案：√6.棧和隊(duì)列都是限制存取點(diǎn)的線性表。（）答案：√7.一棵滿二叉樹(shù)一定是完全二叉樹(shù)。（）答案：√8.對(duì)于一個(gè)無(wú)向圖，其鄰接矩陣一定是對(duì)稱矩陣。（）答案：√9.插入排序的平均時(shí)間復(fù)雜度為O(n2)。（）答案：√10.霍夫曼樹(shù)中權(quán)值越大的葉子結(jié)點(diǎn)離根結(jié)點(diǎn)越遠(yuǎn)。（）答案：×四、簡(jiǎn)答題1.簡(jiǎn)述順序表和鏈表的優(yōu)缺點(diǎn)。順序表優(yōu)點(diǎn)：可以隨機(jī)存取元素，存儲(chǔ)密度高，存儲(chǔ)空間連續(xù)且緊湊。缺點(diǎn)：插入和刪除操作需要移動(dòng)大量元素，效率低，若預(yù)先分配空間過(guò)大可能造成浪費(fèi)，過(guò)小又可能導(dǎo)致溢出。鏈表優(yōu)點(diǎn)：插入和刪除操作不需要移動(dòng)大量元素，只需要修改指針，靈活性高，動(dòng)態(tài)分配內(nèi)存，無(wú)需預(yù)先知道數(shù)據(jù)量大小。缺點(diǎn)：不能隨機(jī)存取，只能順序訪問(wèn)，需要額外的指針空間，存儲(chǔ)密度低。2.簡(jiǎn)述二叉排序樹(shù)的定義及性質(zhì)。二叉排序樹(shù)是一棵空樹(shù)或者具有如下性質(zhì)的二叉樹(shù)：若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；它的左、右子樹(shù)也分別為二叉排序樹(shù)。二叉排序樹(shù)的中序遍歷序列是一個(gè)遞增的有序序列，利用這一性質(zhì)可方便地對(duì)其進(jìn)行查找、插入和刪除操作。3.簡(jiǎn)述圖的兩種遍歷方式（深度優(yōu)先遍歷和廣度優(yōu)先遍歷）的基本思想。深度優(yōu)先遍歷：從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問(wèn)此頂點(diǎn)，然后從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。廣度優(yōu)先遍歷：從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問(wèn)頂點(diǎn)v，然后依次訪問(wèn)v的各個(gè)未被訪問(wèn)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問(wèn)它們的鄰接點(diǎn)，并使“先被訪問(wèn)頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。4.簡(jiǎn)述堆排序的基本步驟。首先將初始待排序關(guān)鍵字序列構(gòu)建成一個(gè)大頂堆（升序用大頂堆，降序用小頂堆），此時(shí)，堆頂元素為序列中的最大關(guān)鍵字。然后將堆頂元素與堆尾元素交換，此時(shí)堆尾元素為最大關(guān)鍵字，將剩余的n-1個(gè)關(guān)鍵字重新調(diào)整為一個(gè)堆，得到n-1個(gè)關(guān)鍵字的堆中最大關(guān)鍵字，再將堆頂元素與堆尾元素交換，如此反復(fù)進(jìn)行，直到整個(gè)序列有序。五、討論題1.討論在不同應(yīng)用場(chǎng)景下，如何選擇合適的排序算法。在數(shù)據(jù)量較小且對(duì)穩(wěn)定性有要求的場(chǎng)景下，插入排序或冒泡排序較為合適，它們實(shí)現(xiàn)簡(jiǎn)單且穩(wěn)定。當(dāng)數(shù)據(jù)量較大時(shí)，如果對(duì)穩(wěn)定性無(wú)要求，快速排序平均性能最優(yōu)，其平均時(shí)間復(fù)雜度為O(nlog?n)。但快速排序最壞情況時(shí)間復(fù)雜度為O(n2)。歸并排序雖然平均和最壞時(shí)間復(fù)雜度都是O(nlog?n)且穩(wěn)定，但需要額外的輔助空間。堆排序時(shí)間復(fù)雜度穩(wěn)定在O(nlog?n)，空間復(fù)雜度低，但不穩(wěn)定。若數(shù)據(jù)基本有序，插入排序效率高。在外部排序中，歸并排序有獨(dú)特優(yōu)勢(shì)。2.討論線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在實(shí)現(xiàn)某些操作時(shí)的差異。在查找操作上，順序表可隨機(jī)存取，可直接根據(jù)下標(biāo)找到元素，時(shí)間復(fù)雜度為O(1)；鏈表只能順序查找，時(shí)間復(fù)雜度為O(n)。在插入和刪除操作方面，順序表插入和刪除元素需要移動(dòng)大量元素，時(shí)間復(fù)雜度為O(n)；鏈表只需修改指針，時(shí)間復(fù)雜度為O(1)，但需要先找到插入或刪除位置，查找位置時(shí)間復(fù)雜度為O(n)。在內(nèi)存使用上，順序表存儲(chǔ)密度高，但可能存在空間分配不合理問(wèn)題；鏈表需要額外指針空間，存儲(chǔ)密度低，但動(dòng)態(tài)分配內(nèi)存更靈活。3.討論如何判斷一個(gè)圖是否存在環(huán)?？梢允褂蒙疃葍?yōu)先搜索（DFS）來(lái)判斷。從圖中某一頂點(diǎn)開(kāi)始進(jìn)行DFS遍歷，在遍歷過(guò)程中，為每個(gè)訪問(wèn)過(guò)的頂點(diǎn)設(shè)置一個(gè)訪問(wèn)標(biāo)記。如果在DFS過(guò)程中，遇到一個(gè)已訪問(wèn)且在當(dāng)前遞歸調(diào)用棧中的頂點(diǎn)，說(shuō)明存在環(huán)。也可以使用拓?fù)渑判騺?lái)判斷，對(duì)有向圖進(jìn)行拓?fù)渑判?，如果排序后的頂點(diǎn)個(gè)數(shù)小于圖中的頂點(diǎn)個(gè)數(shù)，說(shuō)明圖中存在環(huán)，因?yàn)橥負(fù)渑判蛑荒軐?duì)無(wú)環(huán)有向圖進(jìn)行成功排序。對(duì)于無(wú)向圖，在DFS過(guò)程中，如果存在一條邊連接到一個(gè)已訪問(wèn)且不是當(dāng)前頂點(diǎn)的父頂點(diǎn)的頂點(diǎn)，則存在環(huán)。4.討論哈希表中沖突處