2024年高等教育工學(xué)類自考-02331數(shù)據(jù)結(jié)構(gòu)筆試歷年真題薈萃含答案

2024年高等教育工學(xué)類自考-02331數(shù)據(jù)結(jié)構(gòu)筆試歷年真題薈萃含答案（圖片大小可自由調(diào)整）答案解析附后卷I一.參考題庫(共25題)1.二叉樹中不存在度大于2的結(jié)點，當(dāng)某個結(jié)點只有一棵予樹時無所謂左、右子樹之分。2.為多個值相同的元素分配一個存儲空間；對零元素不分配空間，稱為（）。3.設(shè)有森林B=（D，S）， D={A，B，C，D，E，F(xiàn)，G，H，I，J}，r∈S r={〈A，B〉，〈A，C〉，〈A，D〉，〈B，E〉，〈C，F(xiàn)〉，〈G，H〉，〈G，I〉，〈I，J〉}請回答：寫出此二叉樹的前序、中序、后序遍歷序列。4.設(shè)無向圖G（如圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。 5.寫出下面函數(shù)被調(diào)用執(zhí)行后，得到的以HL為表頭指針的單鏈表中的數(shù)據(jù)元素序列。 6.數(shù)據(jù)結(jié)構(gòu)中常用的存儲方法有：（）7.對n個記錄的表r[1..n]進(jìn)行簡單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)為（）。8.二叉樹是一棵結(jié)點的度最大為二的樹。9.對用數(shù)組存儲的線性表（16，15，32，11，6，30），用快速排序算法進(jìn)行由小到大排序，若排序下標(biāo)范圍為0~5，選擇元素16作為支點，調(diào)用一趟快速排序算法后，元素16在數(shù)組中的下標(biāo)位置為（）10.若以{4，5，6，7，8}作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶權(quán)路徑長度為（）。A、67B、68C、69D、7011.簡述多重表文件和倒排文件兩種多關(guān)鍵字文件的組織方法。12.在對一組記錄（55，39，97，22，16，73，65，47，88）進(jìn)行直接插入排序時，當(dāng)把第7個記錄65插入到有序表時，為尋找插入位置需比較（）次。（由小到大排序）13.廣義表的（a，（a，b），d，e，（（i?，j），k））深度是（）。14.具有什么性質(zhì)的問題適合貪心策略求解？15.廣義表的組成元素可以是不同形式的元素。16.若L是splist類型的順序表，則表中的第i個數(shù)據(jù)元素是（）。17.在線索化二叉樹中，t所指節(jié)點沒有左子樹的充要條件是（）A、t-＞left=NULLB、t-＞ltag=1C、t-＞ltag=1且t-＞left=NULLD、以上都不對18.如何實現(xiàn)線性表的順序存儲結(jié)構(gòu)？19.已知一個圖的鄰接矩陣表示，刪除所有從第i個結(jié)點出發(fā)的邊的方法是（）20.設(shè)單循環(huán)鏈表L1，對其遍歷的結(jié)果是：x1，x2，x3，…，xn-1，xn。請將該循環(huán)鏈表拆成兩個單循環(huán)鏈表L1和L2，使得L1中含有原L1表中序號為奇數(shù)的結(jié)點且遍歷結(jié)果為：x1，x3，…；L2中含有原L1表中序號為偶數(shù)的結(jié)點且遍歷結(jié)果為：…，x4，x2。21.數(shù)據(jù)結(jié)構(gòu)里，strlen計算字符串長度時候計算’/0’在內(nèi)。22.一個算法應(yīng)該是（）。A、程序B、問題求解步驟的描述C、要滿足五個基本特性D、A和C23.在下面數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[0].next，則該線性表為（）。 24.設(shè)計計算二叉樹中所有結(jié)點值之和的算法。25.有一個順序存儲的棧，最大存儲空間MaxSize=5，棧頂指針top，現(xiàn)有A、B、C、D四個元素。畫出以上四個元素依次進(jìn)棧后的狀態(tài)。卷II一.參考題庫(共25題)1.設(shè)有10階矩陣A，其對角線以上的元素aij均取值為-3，其他矩陣元素為正整數(shù)，現(xiàn)在將矩陣A壓縮存放在一維樹組F[m]中，則m為（）。A、45B、46C、55D、562.設(shè)有串P1=”ABADF”，P2=”ABAFD”，P3=”ABADFA”P4=”ABAF”，四個串中最小的是（）。3.入棧的先后順序為a，b，c，d，e，（入棧和出?？梢蚤g隔進(jìn)行）則出棧順序可能是（）。A、a，b，c，d，eB、e，d，c，b，aC、c，b，a，d，eD、d，b，c，a，e4.在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的（）A、當(dāng)前位置B、任意位置C、前一個位置D、后一個位置5.下列選項中是C語言中的字符串的結(jié)束符是（）。A、‘/0’B、‘/n’C、‘/t’D、‘/a’6.已知線性表的元素按遞增順序排列，并以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu)。試編寫一個刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法。7.為提高在外排序過程中，對長度為N的初始序列進(jìn)行“置換—選擇”排序時，可以得到的最大初始有序段的長度不超過N/2。8.一棵具有5層的完全二叉樹，最后一層有4個結(jié)點，則該樹總共有（）個結(jié)點。A、14B、15C、19D、189.設(shè)有森林如圖所示，請回答： 畫出該二叉樹的中序線索二叉鏈表的圖示并給出C語言描述。10.線性表就是順序存儲的表11.對于一棵具有n個結(jié)點，其高度為h的任何二叉樹，進(jìn)行任一種次序遍歷的時間復(fù)雜度均為O(h)。12.具有n個頂點的強連通圖至少有多少條邊？這樣的圖應(yīng)該是什么形狀？13.設(shè)與一棵樹T所對應(yīng)的二叉樹為BT，則與T中的葉子結(jié)點所對應(yīng)的BT中的結(jié)點也一定是葉子結(jié)點。14.已知關(guān)鍵字序列（38，12，21，77，65，7，38，53）給出采用快速排序方法按關(guān)鍵字增序排序時的第一趟塊排過程，并舉出一個反例說明快速排序是不穩(wěn)定排序。15.表長為0的線性表稱為（）16.在索引順序結(jié)構(gòu)的搜索中，對索引表既可以采取順序搜索，也可以采用折半搜索。17.折半搜索與二叉搜索樹的時間性能（）A、相同B、完全不同C、有時不相同D、數(shù)量級都是O（log2n）18.一個棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是（）。A、54321B、45321C、43512D、1234519.樹的先根遍歷20.二維數(shù)組A的每個元素是由10個字符組成的串，其行下標(biāo)i=0，1，?，8，列下標(biāo)j=1，2，?，10。若A按行先存儲，元素A[8，5]的起始地址與當(dāng)A按列先存儲時的元素（）的起始地址相同。設(shè)每個字符占一個字節(jié)。A、A[8，5]B、A[3，10]C、A[5，8]D、A[0，9]21.計算機算法指的是（）A、計算方法B、調(diào)度方法C、排序方法D、解決某一問題的有限運算序列22.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。23.數(shù)據(jù)結(jié)構(gòu)里，抽象數(shù)據(jù)類型是由（）組成的。A、一個數(shù)學(xué)模型B、定義在該模型上一組操作C、抽象的概念D、數(shù)據(jù)的概念24.引入二叉線索樹的目的是（）A、加快查找結(jié)點的前驅(qū)或后繼的速度B、為了能在二叉樹中方便的進(jìn)行插入與刪除C、為了能方便的找到雙親D、使二叉樹的遍歷結(jié)果唯一25.稀疏矩陣一般壓縮存儲方法有兩種，分別是（）和（）。卷III一.參考題庫(共25題)1.設(shè)哈希函數(shù)H（key）=keyMOD13，用線性探測再散列法解決沖突.對關(guān)鍵字序列{55，19，01，68，23，27，20，84}在地址空間為0-10的散列區(qū)中建哈希表，畫出此表，并求等概率情況下查找成功時的平均查找長度.2.假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣表示的空間復(fù)雜性為（），采用鄰接表表示的空間復(fù)雜性為（）3.在棧中存取數(shù)據(jù)遵從的原則是（）。4.對一個具有n個元素的線性表，建立其單鏈表的時間復(fù)雜度為（）A、O（n）B、O（1）C、O（n2）D、O（nlog2n）5.棧的特性是先進(jìn)先出。6.假定一個待散列存儲的線性表為（32，75，29，63，48，94，25，46，18，70），散列地址空間為HT[11]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和鏈接法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。7.設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。A、2m-1B、2mC、2m+1D、4m8.已知一棵二叉樹的中序遍歷結(jié)果為D、G、B、A、E、C、H、F、I，后序遍歷結(jié)果為G、D、B、E、H、I、F、C、A，請給出該二叉樹的先序遍歷結(jié)果。9.從未排序序列中選擇一個元素，該元素將當(dāng)前參加排序的那些元素分成前后兩個部分，前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時所選元素處在排序的最終位置。這種排序法稱為（）排序法。10.輸入一個正整數(shù)序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序樹，要求： ⑴畫出該二叉排序樹； ⑵畫出刪除結(jié)點302后的二叉排序樹。11.完全二叉樹12.每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運算：插入、刪除和搜索。13.下面程序段的時間復(fù)雜度為（） 14.二又樹第i（i>=1）層上至多有（）個結(jié)點。15.如果待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。（）就是不穩(wěn)定的排序方法。A、起泡排序B、歸并排序C、Shell排序D、直接插入排序16.對一組記錄（1，3，9，2，12，7，5，4，6）進(jìn)行直接插入排序（由小到大排序），當(dāng)把第6個記錄7插入有序表，為尋找插入位置需比較（）次。17.假設(shè)在算法描述語言中引入指針的二元運算“異或”，若a和b為指針，則a⊕b的運算結(jié)果仍為原指針類型，且a⊕（a⊕b）=（a⊕a）⊕b=b；（a⊕b）⊕b=a⊕（b⊕b）=a。則可利用一個指針域來實現(xiàn)雙向鏈表L。鏈表L中的每個結(jié)點只含兩個域：data域和LRPtr域，其中LRPtr域存放該結(jié)點的左鄰與右鄰結(jié)點指針（不存在時為NULL）的異或。若設(shè)指針L.Left指向鏈表中的最左結(jié)點，L.Right指向鏈表中的最右結(jié)點，則可實現(xiàn)從左向右或從右向左遍歷此雙向鏈表的操作。試寫一算法按任一方向依次輸出鏈表中各元素的值。18.一棵具有n個結(jié)點的二叉樹采用順序存儲結(jié)構(gòu)，編寫算法對該二叉樹進(jìn)行前序遍歷。19.某內(nèi)排序方法的穩(wěn)定性是指（）。A、該排序算法不允許有相同的關(guān)鍵字記錄B、該排序算法允許有相同的關(guān)鍵字記錄C、平均時間為0（nlogn）的排序方法D、以上都不對20.表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）。21.一個圖的（）表示法是惟一的。22.查找相同結(jié)點的效率折半查找總比順序查找高。23.具有n個結(jié)點的滿二叉樹，其葉結(jié)點的個數(shù)為（n+1）/2。24.關(guān)于順序表、鏈表，以下描述錯誤的是（）。A、鏈表中的頭結(jié)點僅起到標(biāo)識的作用。B、順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶?。C、順序存儲方式只能用于存儲線性結(jié)構(gòu)。D、線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。25.一棵深度為h的B-樹，任一個葉子結(jié)點所處的層數(shù)為（），當(dāng)向B-樹中插入一個新關(guān)鍵字時，為檢索插入位置需讀?。ǎ﹤€結(jié)點。卷I參考答案一.參考題庫1.參考答案:錯誤2.參考答案:壓縮存儲3.參考答案:前序遍歷序列：ABECFDGHIJ 中序遍歷序列：EBFCDAHJIG 后序遍歷序列：EFDCBJIHGA4.參考答案:5.參考答案:（12，26，9，8，15，30，50）6.參考答案:順序，鏈接，索引，散列7.參考答案:n（n-1）/28.參考答案:錯誤9.參考答案:310.參考答案:C11.參考答案:多重表文件是將索引方法和鏈接方法相結(jié)合的一種文件組織方式，對主關(guān)鍵字建立的索引稱為主索引，對每個需做查詢操作的次關(guān)鍵字建立的索引稱為次索引。在多重表文件中，記錄通常按主關(guān)鍵字順序排列，同時將具有相同次關(guān)鍵字值的記錄鏈接成一個鏈表，并將此鏈表的頭指針、鏈表長度及次關(guān)鍵字作為對應(yīng)次索引表中的索引項。 與多重表文件不同，倒排文件中具有相同次關(guān)鍵字的記錄之間不進(jìn)行鏈接，而是在對次關(guān)鍵字建立的索引中列出具有該次關(guān)鍵字值的所有記錄的物理地址。倒排文件中的次關(guān)鍵字索引稱為倒排表，倒排表與主文件一起就構(gòu)成了倒排文件。12.參考答案:313.參考答案:314.參考答案:具有如下性質(zhì)： 第一、最優(yōu)子結(jié)構(gòu)性質(zhì)； 第二、貪心選擇性質(zhì)。15.參考答案:正確16.參考答案:Lelem[i-1]17.參考答案:B18.參考答案:把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里就構(gòu)成了線性表的順序存儲，采用順序存儲結(jié)構(gòu)的線性表簡稱順序表。線性表的順序存儲結(jié)構(gòu)有如下特點： 線性表中所有元素所占的存儲空間是連續(xù)的； 線性表的邏輯順序與物理順序一致； 數(shù)組中的每一個元素的位置可以用公式來確定。假設(shè)線性表中的第一個數(shù)據(jù)元素的存儲地址（指第一個字節(jié)的地址，即首地址）為LOC（e1），每一個數(shù)據(jù)元素占k個字節(jié)，則線性表中第i個元素ei在計算機存儲空間中的存儲地址為：19.參考答案:將矩陣第i行全部置為020.參考答案:算法如下： 21.參考答案:錯誤22.參考答案:B23.參考答案:（38，56，25，60，42，74）24.參考答案:25.參考答案:卷II參考答案一.參考題庫1.參考答案:D2.參考答案:P13.參考答案:A,B,C4.參考答案:C5.參考答案:A6.參考答案:7.參考答案:錯誤8.參考答案:C9.參考答案:10.參考答案:錯誤11.參考答案:錯誤12.參考答案:具有n個頂點的強連通圖至少有n條邊，這樣的圖是一個由n個頂點構(gòu)成的環(huán)。 強連通圖是相對于有向圖而言的。由于強連通圖要求圖中任何兩個頂點之間能夠相互連通，因此每個頂點至少要有一條以該頂點為弧頭的弧和一條以該頂點為弧尾的弧，每個頂點的入度和出度至少各為1，即頂點的度至少為2，這樣根據(jù)圖的頂點數(shù)、邊數(shù)以及各項點的度三者之間的關(guān)系計算可得：邊數(shù)=2×n/2=n。13.參考答案:錯誤14.參考答案:15.參考答案:空表16.參考答案:正確17.參考答案:C18.參考答案:C19.參考答案:若樹非空，則先訪問根結(jié)點，再按從左到右的順序遍歷根節(jié)點的每一顆子樹。其訪問順序與這棵樹對應(yīng)的二叉樹的線序遍歷順序相同。20.參考答案:B21.參考答案:D22.參考答案:正確23.參考答案:A,B24.參考答案:A25.參考答案:三元組順序表；十字鏈表卷III參考答案一.參考題庫1.參考答案: ASLsucc=(1+2+1+2+1+1+3+1)/8=1.52.參考答案: