2024年高等教育工學類自考-02331數(shù)據(jù)結(jié)構(gòu)考試近5年真題附答案

（圖片大小可自由調(diào)整）2024年高等教育工學類自考-02331數(shù)據(jù)結(jié)構(gòu)考試近5年真題薈萃附答案第I卷一.參考題庫(共100題)1.求解平方根的迭代函數(shù)定義如下： 其中，p是A的近似平方根，e是結(jié)果允許誤差。試寫出相應的遞歸算法，并消除遞歸。2.一棵深度為8（根的層次號為1）的滿二叉樹有（）個結(jié)點。A、256B、255C、128D、1273.數(shù)據(jù)結(jié)構(gòu)主要研究（），（），（）三個方面的內(nèi)容。4.在鏈表中，每個結(jié)點中含8個字符，1個指針域。其中每個字符占1個字節(jié)，每個指針占4個字節(jié)。則該結(jié)點的存儲密度是（）。5.數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映象。6.請利用兩個棧S1和S2來模擬一個隊列。已知棧的三個運算定義如下：PUSH（ST，X）：元素X入ST棧；POP（ST，X）：ST棧頂元素出棧，賦給變量X；Sempty（ST）：判ST棧空否。那么如何用棧的運算來實現(xiàn)該隊列的三個運算：enqueue：插入一個元素入隊列；dequeue：刪除一個元素出隊列；queue_empty：判隊列為空。（請寫明算法的思想及必要的注釋）7.下列對于線性鏈表的描述中正確的是（）。A、存儲空間不一定是連續(xù)，且各元素的存儲順序是任意的B、存儲空間不一定是連續(xù)，且前件元素一定存儲在后件元素的前面C、存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面D、存儲空間必須連續(xù)，且各元素的存儲順序是任意的8.在對n個元素進行冒泡排序的過程中，至少需要（）趟完成。A、1B、nC、n-1D、n/29.若一個元素序列基本有序，則選用（）排序較快。A、堆排序B、快速排序C、直接插入法D、直接選擇排序10.隊列是特殊的線性表，其特殊性在于（）11.數(shù)據(jù)結(jié)構(gòu)里，棧的應用很廣泛，遞歸問題的解決都要靠棧來完成，以下可以遞歸實現(xiàn)的有（）。A、斐波那契數(shù)列B、n！（n的階乘）C、漢諾塔問題D、迷宮問題12.排序是計算機程序設計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列。13.設關(guān)鍵字序列為（71，12，88，53，11，25，65，27，16），散列函數(shù)為H（key）=key%7，采用鏈地址法解決沖突。請回答：請求等概率下查找成功的平均查找長度ASL14.（101，88，46，70，34，39，45，58，66，10）是堆。15.二叉排序樹中，最小值結(jié)點的（）。A、左指針一定為空B、右指針一定為空C、左、右指針均為空D、左、右指針均不為空16.循環(huán)隊列解決了普通隊列的什么問題（）。A、假溢出B、溢出C、空D、都不對17.通常使用隊列來處理函數(shù)或過程的調(diào)用。18.如果要將序列（50，16，23，68，94，70，73）建成堆，只需把16與（）交換。19.散列法的平均檢索長度不隨表中結(jié)點數(shù)目的增加而增加，而是隨負載因子的增大而增大。20.順序表是邏輯結(jié)構(gòu)是線性結(jié)構(gòu)而存儲結(jié)構(gòu)是（）的數(shù)據(jù)結(jié)構(gòu)。A、順序存儲結(jié)構(gòu)B、鏈式存儲結(jié)構(gòu)C、花式存儲結(jié)構(gòu)D、跳躍存儲結(jié)構(gòu)21.通過建立索引表來存取數(shù)據(jù)的文件有（）A、散列文件B、VSAM文件C、ISAM文件D、順序文件E、倒排文件22.在構(gòu)造哈希表的過程中，不可避免地會出現(xiàn)沖突，通常解決它的方法有（）A、平方取中法B、開放地址法C、隨機探查法D、再哈希法E、拉鏈分散法（鏈地址法）23.已知如下所示長度為12的表：（Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。24.在初始數(shù)據(jù)表已經(jīng)有序時，快速排序算法的時間復雜度為O（nlog2n）。25.設有森林如圖所示，請回答： 畫出該二叉樹的中序線索二叉鏈表的圖示并給出C語言描述。26.通常對數(shù)組進行的兩種基本操作是（）。A、建立與刪除B、索引和修改C、查找和修改D、查找與索引27.已知一組元素為（46，25，78，62，12，37，70，29），畫出按元素排列順序輸入生成的一棵二叉搜索樹。28.數(shù)據(jù)結(jié)構(gòu)里，樹是一種特殊的一對多的邏輯結(jié)構(gòu)，當一個結(jié)點也沒有時，它就稱為（）。A、滿樹B、空樹C、二叉樹D、多叉樹29.在散列技術(shù)中，處理沖突的兩種主要方法是（）和（）。30.棧是后進先出（先進后出）的（）。A、線性表B、鏈表C、單鏈表D、索引表31.樸素模式匹配算法，算法運行時間為O（m*n）。32.由帶權(quán)為，9、2.5，7，的四個葉子結(jié)點構(gòu)造一裸哈夫曼樹.該樹的帶權(quán)路徑長度為（）。33.鏈表不具有的特點是（）。A、可隨機訪問任一元素B、插入刪除不需要移動元素C、不必事先估計存儲空間D、所需空間與線性表長度成正比34.什么是算法分析？算法分析主要考慮哪幾方面的內(nèi)容？35.設森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是：（）A、M1B、M1+M2C、M3D、M2+M336.算法中R[n+1]的作用是什么？37.有向圖G可拓撲排序的判別條件是（）。38.鏈式存儲的線性表中的指針指向其（）。A、前趨結(jié)點B、后繼結(jié)點C、物理前趨D、物理后繼39.設輸入序列為20，45，30，89，70，38，62，19依次插入到一棵2-3樹中（初始狀態(tài)為空）。 再刪除38，該B-樹為（）。A、aB、bC、cD、dE、eF、f40.下面程序段的時間復雜度為（）。 i=1； while（iA、O（n）B、O（3n）C、O（log3n）D、O（n3）41.對于雙目操作符，其重載函數(shù)帶有（）個參數(shù)，其中至少有一個為（）的類型。42.數(shù)據(jù)結(jié)構(gòu)里，實參和形參的關(guān)系（）。A、實參傳給形參B、實參的類型要與形參一致C、實參的個數(shù)要與實參一致D、實參的名稱要與形參的一致43.下面程序的時間復雜為（） A、AB、BC、CD、D44.設有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH表中需要做（）次線性探測。 A、AB、BC、CD、D45.若一個圖的邊集為{，，，，，}，則從頂點1開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為（）。A、?1，2，3，4，5B、?1，2，4，3，5C、?1，2，4，5，3D、?1，4，2，5，346.網(wǎng)G的鄰接矩陣如下，試畫出該圖，并畫出它的一棵最小生成樹。 47.二叉樹是否可以為空二叉樹？（）。A、不可以為空B、可以為空C、不確定D、都不對48.n個頂點的強連通有向圖G，最多有（）條邊，最少有（）邊。強連通圖即是任何兩個頂點之間有路徑相通，當所有結(jié)點在一個環(huán)上時，必定是強連通圖。49.找出所有滿足下列條件的二叉樹： （a）它們在先序遍歷和中序遍歷時，得到的節(jié)點訪問序列相同； （b）它們在后序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同； （c）它們在先序遍歷和后序遍歷時，得到的節(jié)點訪問序列相同。50.設有一個棧，按A、B、C的順序進棧，則下列（）為不可能的出棧序列。A、ABCB、CBAC、CABD、ACB51.數(shù)據(jù)結(jié)構(gòu)里，二叉樹中的結(jié)點都是度為2的結(jié)點。52.簡述棧與隊列的相同點與不同點。53.在對n個元素進行冒泡排序的過程中，第一趟排序至多需要進行（）對相鄰元素之間的交換。A、?n／2B、?n-1C、?nD、?n+154.數(shù)據(jù)結(jié)構(gòu)里，在順序表中，插入和刪除時移動元素的個數(shù)與該元素的位置有關(guān)。55.設要將序列（q，h，c，y，p，a，m，s，r，d，f，x）中的關(guān)鍵碼按字母升序重新排序，回答。（）是初始步長為4的shell排序一趟掃描的結(jié)果。A、f，h，c，d，p，a，m，q，r，s，y，xB、p，a，c，s，q，d，f，x，r，h，m，yC、a，d，c，r，f，q，m，s，y，p，h，xD、h，c，q，p，a，m，s，r，d，f，x，yE、h，q，c，y，a，p，m，s，d，r，f，x56.假設一個棧的輸入序列為A，B，C，D，E，則下列序列中不可能是棧的輸出序列的是（）A、B、C、D、A、EB、E、D、A、C、BC、B、C、A、D、ED、A、E、D、C、B57.在順序表（n足夠大）中進行順序查找，其查找不成功的平均長度是（）。A、（n+1）/2B、n/2+1C、nD、n+158.對于一個有向圖，若一個頂點的度為k1，出度為k2，則對應鄰接表中該頂點單鏈表中的邊結(jié)點數(shù)為（）。A、?k1B、?k2C、?k1-k2D、?k1+k259.對于一個有向圖，若一個頂點的入度為k1、出度為k2，則對應逆鄰接表中該頂點單鏈表中的結(jié)點數(shù)為（）。A、k1B、k2C、k1-k2D、k1+k260.求子串在主串中首次出現(xiàn)的位置的運算稱為（）。61.設順序表有19個元素，第一個元素的地址為200，且每個元素占3個字節(jié)，則第14個元素的存儲地址為（）。A、236B、239C、242D、24562.（）遍歷二叉排序樹可得到一個有序序列。63.數(shù)據(jù)結(jié)構(gòu)里，下列選項中關(guān)于順序表的概念理解正確的是（）。A、線性表采用鏈式存儲結(jié)構(gòu)B、線性表采用順序存儲結(jié)構(gòu)C、線性表采用索引存儲結(jié)構(gòu)D、線性表采用散列存儲結(jié)構(gòu)64.具有n個頂點的連通圖至少有多少條邊？65.在深度為7的滿二叉樹中，葉子結(jié)點的個數(shù)為（）A、32B、31C、64D、6366.串是一種特殊的線性表，其特殊性體現(xiàn)在（）A、可以順序存儲B、數(shù)據(jù)元素是一個字符C、可以鏈式存儲D、數(shù)據(jù)元素可以是多個字符67.散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應當以（）取其值域的每個值。A、最大概率B、最小概率C、平均概率D、同等概率68.算法分析的目的是（），算法分析的兩個主要方面是（）。69.下面關(guān)于工程計劃的AOE網(wǎng)的敘述中，不正確的是（）A、關(guān)鍵活動不按期完成就會影響整個工程的完成時間B、任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成C、所有的關(guān)鍵活動都提前完成，那么整個工程將會提前完成D、某些關(guān)鍵活動若提前完成，那么整個工程將會提前完70.（）二叉排序樹可以得到一個從小到大的有序序列。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷71.稀疏多項式采用的順序存儲結(jié)構(gòu)SqPoly定義為： 采用上題給定的條件和存儲結(jié)構(gòu)，編寫求P（x）=Pn1（x）-Pn2（x）的算法，將結(jié)果多項式存放在新辟的空間中，并分析你的算法的時間復雜度。72.有一個n個頂點的有向完全圖的弧數(shù)（）。73.下列選項中屬于算法的特性是（）。A、可行性B、數(shù)據(jù)C、數(shù)據(jù)項D、程序74.廣義表A=（（a），a）的表頭是（）。A、aB、B.C、bD、D.（）75.對稀疏矩陣進行壓縮存儲是為了節(jié)省存儲空間。76.p是一個結(jié)構(gòu)體指針變量，它有一個成員變量叫sex，則使用格式正確的是（）。A、p->sexB、p%sexC、p#sexD、p&sex77.字符在串中的位置，即是字符在該序列中的（）78.設有一個空棧，棧頂指針為1000H，現(xiàn)有輸入序列為12345，push，push，pop，push，pop，push，push后，輸出序列為（），棧頂指針是（）。79.滿二叉樹是完全二叉樹的特例。80.算法的特性包括：輸入、輸出、有窮性、確定性、可行性。81.數(shù)據(jù)結(jié)構(gòu)的基本操作的設置的最重要的準則是，實現(xiàn)應用程序與存儲結(jié)構(gòu)的獨立。82.斐波那契數(shù)列的計算，可以使用遞歸的方式計算，則需要使用哪項來幫助完成。（）A、棧B、圖C、二叉樹D、隊列83.在所有排序方法中，（）方法采用的是兩兩有序表合并的思想。84.假定一組記錄為(46,79,56,38,40,80,46,75,28,46)，對其進行歸并排序的過程中，供需要（）趟完成。85.在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（）。A、p-＞next-＞prior=p-＞prior；?p-＞prior-＞next=p-＞next；B、p-＞next=p-＞next-＞next；?p-＞next-＞prior=p；C、p-＞prior-＞next=p；?p-＞prior=p-＞prior-＞prior；D、p-＞prior=p-＞next-＞next；?p-＞next=p-＞prior-＞prior；86.設二維數(shù)組A[1?m，1?n]按行存儲在數(shù)組B中，則二維數(shù)組元素A[i，j]在一維數(shù)組B中的下標為（）。A、n*（i－1）＋jB、n*（i－1）＋j－1C、i*（j－1）D、j*m＋i－187.一棵二叉樹的廣義表表示為a（b（c，d），e（f（，g））），它含有雙親結(jié)點（）個，單分支結(jié)點（）個，葉子結(jié)點（）個。88.深度為h的非空二叉樹的第i層最多有2i-1個結(jié)點。89.順序表和鏈表中能實現(xiàn)隨機存取的是（），插入、刪除操作效率高的是（）90.n個結(jié)點無向完全圖的的邊數(shù)為（），n個結(jié)點的生成樹的邊數(shù)為（）。91.對于一棵完全二叉樹采用順序存儲，設一個結(jié)點的編號為i（根結(jié)點的編號為1，若它的左孩子結(jié)點存在，則其編號為（）92.在一個帶頭結(jié)點的單循環(huán)鏈表中，P指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用P表示為head=（）。93.設哈希表長度為11，哈希函數(shù)H（K）=（K的第一字母在字母表中的序號）MOD11，若輸入順序為（D，BA，TN，M，CI，I，K，X，TA），處理沖突方法為線性探測再散列或鏈地址法，要求構(gòu)造哈希表，并求出等概率情況下查找成功平均查找長度。94.對一組記錄（5，8，9，2，12，7，56，44，39）進行直接插入排序（由小到大排序），當把第6個記錄7插入有序表，為尋找插入位置需比較（）次。95.鏈式棧與順序棧相比，一個明顯的優(yōu)點是通常不會出現(xiàn)棧滿的情況。96.下列排序方法中，哪一種方法的比較次數(shù)與紀錄的初始排列狀態(tài)無關(guān)（）A、直接插入排序B、起泡排序C、快速排序D、直接選擇排序97.對于給定的n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有（）、（）、（）、（）四種。98.從未排序序列中依次取出元素與已排序序列中的元素作比較，將其放入已排序序列中的正確位置上，此方法稱為（）。A、歸并排序B、選擇排序C、交換排序D、插入排序99.若鄰接表中有奇數(shù)個表結(jié)點，則一定（）A、圖中有奇數(shù)個頂點B、圖中有偶數(shù)個頂點C、圖為無向圖D、圖為有向圖100.序列13，11，14，12，17，15，采用冒泡排序算法，經(jīng)一趟冒泡后，序列的結(jié)果是（）。第I卷參考答案一.參考題庫1.參考答案：2.參考答案：B3.參考答案：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的存儲結(jié)構(gòu)；數(shù)據(jù)的運算4.參考答案：2/35.參考答案：正確6.參考答案：7.參考答案：A8.參考答案：A9.參考答案：C10.參考答案：只允許在表的一端進行元素插入而在另一端進行元素的刪除11.參考答案：A,B,C,D12.參考答案：正確13.參考答案：ASL成功=（1*5+2*2+3*1+4*1）=16/914.參考答案：正確15.參考答案：A16.參考答案：A17.參考答案：錯誤18.參考答案：5019.參考答案：正確20.參考答案：A21.參考答案：B,C,E22.參考答案：B,C,D,E23.參考答案：24.參考答案：錯誤25.參考答案：26.參考答案：C27.參考答案：28.參考答案：B29.參考答案：開放定址法；拉鏈法30.參考答案：A31.參考答案：正確32.參考答案：4433.參考答案：A34.參考答案：算法的研究與實際問題直接相關(guān)，用來解一個問題可以有很多不同的算法，他們之間的效果可能會有很大差異。算法設計者最關(guān)心的就是什么是有效的算法，如何評價一個算法的優(yōu)劣，如何從多種算法中選擇好的算法。除了要首先考慮算法的正確性外，還要分析和評價算法的性能。分析和評價算法的性能主要要考慮以下兩個方面： ①時間代價：執(zhí)行算法所耗費的時間。一個好的算法首先應該比其他算法的運行時間代價要小。算法的時間代價的大小用算法的時間復雜度來度量。 ②空間代價：執(zhí)行算法所耗費的存儲空間，主要是輔助空間。算法運行所需的空間消耗是衡量算法優(yōu)劣的另一個重要因素。算法的空間代價的大小用算法的空間復雜度來度量。35.參考答案：D36.參考答案：哨兵。避免邊界檢測，提高程序運行效率。37.參考答案：沒有回路38.參考答案：B39.參考答案：F40.參考答案：C41.參考答案：2；用戶自定義42.參考答案：A