2024年高等教育工學類自考-02331數據結構歷年考試高頻考點試題附帶答案（圖片大小可自由調整）第1卷一.參考題庫(共25題)1.對于一棵具有n個結點的二叉樹，若一個結點的編號為i（1≤i≤n），則它的左孩子結點的編號為（），右孩子結點的編號為（），雙親結點的編號為（）2.如果一個串中的所有字符均在另一串中出現，則說前者是后者的子串。3.以孩子兄弟表示法做存儲結構，求樹中結點x的第i個孩子。4.在高級語言中，不可以定義結構體類型的指針變量。5.算法分析的兩個主要方面是（）。A、空間復雜度和時間復雜度B、正確性和簡單性C、可讀性和文檔性D、數據復雜性和程序復雜性6.隊列操作的原則是（）。A、先進先出B、后進先出C、只能進行插入D、只能進行刪除7.對順序表的優缺點，以下說法錯誤的是（）A、無需為表示結點間的邏輯關系而增加額外的存儲空間B、可以方便地隨機存取表中的任一結點C、插入和刪除運算較為方便D、由于要求占用連續空間，所以存儲分配只能預先進行（靜態分配）8.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為（）。不允許插入和刪除運算的一端稱為（）。9.程序越短，程序運行的時間就越少。10.假設R是集合M上的一個關系，R的定義是什么？對實際問題而言，其含義是什么？11.在樹的概念中，下列選項中關于樹的兄弟描述正確的是（）A、雙親是同一個結點B、雙親是不同的結點C、在樹中不同的層D、都不對12.廣義表（f?，h?，（a?，b，d，c），d?，e?，（（i?，j），k?））的長度是（）。13.如下圖所示，若從頂點a出發，按圖的深度優先搜索法進行遍歷，則可能得到的一種頂點序列為（）。 A、abecdfB、acfebdC、aebcfdD、aedfcb14.結點的層次15.設散列表表長m=14，散列函數H（k）=kmod11。表中已有15、38、61、84四個元素，如果用線性探側法處理沖突，則元素49的存儲地址是（）。A、8B、3C、5D、916.數據結構里，以下字符串處理函數中，返回值不是char的是（）。A、strcatB、strcmpC、strcpyD、strlen17.序列3，1，7，18，6，9，13，12經一趟歸并排序的結果為（）。18.將一棵有100個結點的完全二叉樹從根這一層開始，每一層上從左到右依次對結點進行編號，根結點的編號為1，則編號為49的結點的左孩子編號為（）。A、98B、99C、50D、4819.已知一個無向圖的鄰接表如圖所示，要求：畫出該無向圖20.已知哈希表地址空間為A[0..8]，哈希函數為H（k）=k?mod?7，采用線性探測再散列處理沖突。若依次將數據序列：76，45，88，21，94，77，17存入該散列表中則元素17存儲的下標為（）。A、0B、1C、2D、3E、4F、5G、6H、721.以下程序是前序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為left和right，數據域data為字符型，BT指向根結點）。 22.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為（） A、AB、BC、CD、D23.樹的后跟遍歷24.對一組記錄（5，8，9，2，12，7，56，44，39）進行直接插入排序（由小到大排序），當把第6個記錄7插入有序表，為尋找插入位置需比較（）次。25.從有序表(14，20，33，45，54，72，87，96)中，分別用二分查找法查找45和54元素時，其查找長度分別為（）和（）第2卷一.參考題庫(共25題)1.假定對長度n=50的有序表進行二分查找，則對應的判定樹高度為（），判定樹中前5層的結點數為（），最后一層的結點數為（）。2.對于一個棧，給出輸入項A，B，C。如果輸入項順序為A，B，C所組成，則全部可能的輸出項有（）種，不可能的輸出項為（）。3.數據結構里，線性結構有：順序表、鏈表、棧、隊列。4.在一個具有n個頂點和e條邊的有向圖的鄰接表中，保存頂點單鏈表的表頭指針向量的大小至少為（）。A、?nB、?2nC、?eD、?2e5.已知數據序列為（12，5，9，20，6，31，24），對該數據序列進行排序，寫出插入排序、起泡排序、快速排序、簡單選擇排序、堆排序以及二路歸并排序每趟的結果。6.表達式a*（b+c）-d的后綴表達式是（）。A、abcd+-B、abc+*d-C、abc*+d-D、-+*abcd7.在線性表的下列存儲結構中，讀取元素花費的時間最少的是（）。A、單鏈表B、雙鏈表C、循環鏈表D、順序表8.順序表插入、刪除分別需要移動（）個元素。A、n-iB、n-i+1C、n-1D、n-29.下面程序段中帶下劃線的語句的執行次數的數量級是（） 10.假定一個順序表的長度為40，并假定查找每個元素的概率都相同，則在查找成功情況下的平均查找長度（），在查找不成功情況下的平均查找長度（）。11.下列關于算法的時間復雜度陳述正確的是（）A、算法的時間復雜度是指執行算法程序所需要的時間B、算法的時間復雜度是指算法程序的長度C、算法的時間復雜度是指算法執行過程中所需要的基本運算次數D、算法的時間復雜度是指算法程序中的指令條數12.對于右圖所示的樹： 寫出按層遍歷得到的結點序列。13.在無向圖G的鄰接矩陣A中，若A[i，j]等于1，則A[j，i]等于（）A、i+jB、i-jC、1D、014.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。15.單鏈表的主要優點是（）A、便于隨機查詢B、存儲密度高C、邏輯上相鄰的元素在物理上也是相鄰的D、插入和刪除比較方便16.在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關系都相同。17.假設用于通信的電文由字符集{a，b，c，d，e，f，g，h}中的字母構成，這8個字母在電文中出現的概率分別為{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}，試為這8個字母進行哈夫曼編碼。請回答：求出此哈夫曼樹的帶權路徑長度WPL。18.帶頭結點的單鏈表head為空的判定條件是（）。A、head==NULLB、head->next==NULLC、head->next!=NULLD、head!=NULL19.已知一棵度為m的樹中有：n1個度為1的結點，n2個度為2的結點，……，nm個度為m的結點，問該樹中共有多少個葉子結點？20.哈夫曼樹是指（）的二叉樹。21.在表結構中最常用的是線性表，棧和隊列不太常用。22.樹狀結構中數據元素的位置之間存在（）的關系。A、每一個元素都有一個直接前驅和一個直接后繼B、一對一C、多對多D、一對多23.設二叉排序樹中有n個結點，則在二叉排序樹的平均查找長度為（） A、AB、BC、CD、D24.已知二維數組A[m][n]采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是LOC（A[0][0]），則A[i][j]的地址是（）。25.從存儲結構上可以把數據結構分為（）兩大類。A、動態結構、靜態結構B、順序結構、鏈式結構C、線性結構、非線性結構D、初等結構、構造型結構第3卷一.參考題庫(共25題)1.數據結構里，空格串與空串是一樣的概念。2.下面哪一方法可以判斷出一個有向圖是否有環（回路）（）。A、求節點的度B、拓撲排序C、求最短路徑D、求關鍵路徑3.數據結構里，結構體數組，即定義數組的每個元素都是一個結構體類型的。4.在雙向鏈表中，每個結點含有兩個指針域，一個指向（）結點，另一個指向（）結點。5.數組A[1‥40，1‥30]采用三元組表示，設數組元素與下標均為整型，則在非零元素個數小于（）時，才能節省存儲空間。A、1200B、401C、399D、4006.若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素算法的時間復雜度（）。A、O（log2n）B、O（1）C、O（n）D、O（n2）7.已知一個順序存儲的線性表，設每個結點需占m個存儲單元，若第一個結點的地址為da1，則第I個結點的地址為（）。A、da1+（I-1）*mB、da1+I*mC、da1-I*mD、da1+（I+1）*m8.（1）?設計二次多項式ax2+bx+c的一種抽象數據類型，其數據部分為多項式的三個系數項a、b、c；操作部分包括：初始化數據成員a、b、c，實現兩個多項式相加，給定x求多項式的值，求方程ax2 +bx+c=0的兩個實根，按照ax**2+bx+c的格式輸出二次多項式。??? （2）?假定數據成員a、b、c定義如下： ?????? 請寫出上述各操作的具體實現。9.有一個100×90的稀疏矩陣，非0元素有10，設每個整型數占2個字節，則用三元組表示該矩陣時，所需的字節數是（）。A、20B、66C、18000D、3310.畫出下圖所示有向圖的所有強連通分量。 11.函數重載要求（）、（）或（）有所不同。12.設線性表中有n個數據元素，則在順序存儲結構上實現順序查找的平均時間復雜度為（）在鏈式存儲結構上實現順序查找的平均時間復雜度為（）13.證明任何一棵滿二叉樹T中的分支數B滿足B=2(N0-1)（其中N0為葉子結點數）。14.對于線性表（18，25，63，50，42，32，90）進行散列存儲時，若選用H（K）=K%9作為散列函數，則散列地址為0的元素有（）個，散列地址為5的元素有（）個。15.數據結構里，二叉樹中的結點都是度為2的結點。16.下列關于圖遍歷的說法不正確的是（）。A、連通圖的深度優先搜索是一個遞歸過程B、圖的廣度優先搜索中鄰接點的尋找具有“先進先出”的特征C、非連通圖不能用深度優先搜索法D、圖的遍歷要求每一頂點僅被訪問一次17.在一個單鏈表中，若刪除p所指向結點的后續結點，則執行（）。A、p->next=p->next->next；B、p=p->next；p->next=p->next->next；C、p=p->next；D、p=p->next->next；18.假定一個待散列存儲的線性表為（32，75，29，63，48，94，25，46，18，70），散列地址空間為HT[11]，若采用除留余數法構造散列函數和鏈接法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。19.在一個無向圖中，若兩頂點之間的路徑長度為k，則該路徑上的頂點數為（）。A、?kB、?k+1C、?k+2D、?2k20.已知一個無向圖的鄰接表如圖所示，要求：根據鄰接表，分別寫出用DFS（深度優先搜索）和BFS（廣度優先搜索）算法從頂點V0開始遍歷該圖后所得到的遍歷序列。21.有向樹22.假設有60行70列的二維數組a[1…60，1…70]以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32，58]的存儲地址為。（無第0行第0列元素）（）A、16902B、16904C、14454D、答案A，B，C均不對23.順序棧存儲空間的實現使用（）。A、鏈表B、數組C、循環鏈表D、變量24.下述（）是順序存儲結構的優點？A、存儲密度大B、插入運算方便C、刪除運算方便D、可方便地用于各種邏輯結構的存儲表示25.兩個非遞增有序的順序表可以（）成一個非遞增有序的順序表。A、合并B、插入C、刪除D、修改第1卷參考答案一.參考題庫1.參考答案:2i；2i+1；i/2（或i/2）2.參考答案:錯誤3.參考答案:先在鏈表中進行遍歷，在遍歷過程中查找值等于x的結點，然后由此結點的最左孩子域firstchild找到值為x結點的第一個孩子，再沿右兄弟域rightsib找到值為x結點的第i個孩子并返回指向這個孩子的指針。 樹的孩子兄弟表示法中的結點結構定義如下： 具體算法如下： 4.參考答案:錯誤5.參考答案:A6.參考答案:A7.參考答案:C8.參考答案:棧頂棧底9.參考答案:錯誤10.參考答案:如果R是對集合M自身的笛卡爾積所取的一個子集，那么我們就說“R是集合M上的一個關系”。對實際問題而言，它表示的是集合M中元素的某種相關性。例如，對于參加一個羽毛球比賽的運動員集合，可以用一個二元關系表示出各場比賽的勝負關系。對于一組課程的集合，可以用一個二元關系表示出各門課程之間的先修和后續關系等等。11.參考答案:A12.參考答案:613.參考答案:D14.參考答案:從樹根開始定義，根結點為第1層，它的子結點為第2層，以此類推。15.參考答案:A16.參考答案:B,D17.參考答案:1，3，7，18，6，9，12，1318.參考答案:A19.參考答案:20.參考答案:F21.參考答案:22.參考答案:C23.參考答案:若樹非空，則按從左到右的順序遍歷根結點的每一棵子樹，之后再訪問根結點。其訪問順序與其對應的二叉樹的中序遍歷相同。24.參考答案:425.參考答案:1；3第2卷參考答案一.參考題庫1.參考答案:6；31；192.參考答案:5；CAB3.參考答案:正確4.參考答案:A5.參考答案:用上述排序方法的每趟結果如下： 6.參考答案:B7.參考答案:D8.參考答案:A,B9.參考答案:log2n10.參考答案:20.5；4111.參考答案:C12.參考答案:abcdefghijklm13.參考答案:C14.參考答案:正確15.參考答案:D16.參考答案:正確17.參考答案:18.參考答案:B19.參考答案:設該樹的總結點數為n， 則n=n0+n1+n2+……+nm 又：n=分枝數+1=0×n0+1×n1+2×n2+……+m×nm+1由上述兩式可得： N.0=n2+2n3+……+（m-1）nm+120.參考答案:帶權路徑長度最小21.參考答案:錯誤22.參考答案:D23.參考答案:B24.參考答案:Loc(A[0][0])+(i*N+j)*k25.參考答案:C第3卷參考答案一.參考題庫1.參考答案:錯誤2.參考答案:B3.參考答案:正確4.參考答案:前驅；后繼5.參考答案:D6.參考答案:C