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

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