2023年自考類計(jì)算機(jī)類(工學(xué)類)數(shù)據(jù)結(jié)構(gòu)導(dǎo)論歷年高頻考題帶答案難題附詳解

2023年自考類計(jì)算機(jī)類(工學(xué)類)數(shù)據(jù)結(jié)構(gòu)導(dǎo)論歷年高頻考題帶答案難題附詳解（圖片大小可自由調(diào)整）第1卷一.歷年考點(diǎn)試題黑鉆版(共50題)1.利用克魯斯卡爾(Kruskal)算法構(gòu)造下圖的最小生成樹，畫出它的構(gòu)造過程。

2.______是順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法。3.算法在發(fā)生非法操作時(shí)可以作出處理的特性稱為

A.正確性B.易讀性C.健壯性D.時(shí)空性4.假設(shè)以數(shù)組A[n]存放循環(huán)隊(duì)列的元素，其頭、尾指針分別為front和rear。若設(shè)定尾指針指向隊(duì)列中的隊(duì)尾元素，頭指針指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，則當(dāng)前存于隊(duì)列中的元素個(gè)數(shù)為______A.(rear-front)%nB.(rear-front-1)%nC.(front-rear+1)%nD.(rear-front+n)%n5.試寫出二分查找的遞歸算法。6.下述矩陣表示一個(gè)無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹。

7.在棧結(jié)構(gòu)中，允許插入和刪除的一端稱為______。8.若用一個(gè)有7個(gè)單元的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，rear和front的初值分別為0和3，則從隊(duì)列中刪除一個(gè)元素，再添加兩個(gè)元素后，rear和front的值分別為______A.1和4B.5和2C.2和5D.5和29.對(duì)于下列一組關(guān)鍵字(46，58，15，45，90，18，10，62)，試寫出快速排序每一趟的排序結(jié)果，并標(biāo)出第一趟中各元素的移動(dòng)方向。10.一個(gè)棧的輸入序列是12345，則下列序列中不可能是棧的輸出序列的是

A.23415B.54132C.23145D.1543211.在無向圖G的鄰接矩陣A中，若A[i][j]等于0，則A[j][i]等于______。12.從v1出發(fā)，對(duì)下圖按廣度優(yōu)先搜索遍歷，則可能得到的一種頂點(diǎn)序列為

A.v1v2v3v5v4v6B.v1v2v3v5v6v4C.v1v5v2v3v6v4D.v1v3v6v4v5v213.除根結(jié)點(diǎn)外，樹上每個(gè)結(jié)點(diǎn)______A.可有一個(gè)孩子、任意多個(gè)雙親B.可有任意多個(gè)孩子、任意多個(gè)雙親C.可有任意多個(gè)孩子、一個(gè)雙親D.只有一個(gè)孩子、一個(gè)雙親14.若一棵度為8的樹有9個(gè)度為1的結(jié)點(diǎn)，有8個(gè)度為2的結(jié)點(diǎn)，有7個(gè)度為3的結(jié)點(diǎn)，有6個(gè)度為4的結(jié)點(diǎn)，有5個(gè)度為5的結(jié)點(diǎn)，有4個(gè)度為6的結(jié)點(diǎn)，有3個(gè)度為7的結(jié)點(diǎn)，有2個(gè)度為8的結(jié)點(diǎn)，該樹一共有多少個(gè)葉子結(jié)點(diǎn)______A.44B.58C.113D.11515.二分查找算法要求被查找的表是

A.鍵值有序的鏈表B.鍵值不一定有序的鏈表C.鍵值有序的順序表D.鍵值不一定有序的順序表16.寫出判斷帶頭結(jié)點(diǎn)的單鏈表L的元素值是否是遞增的算法。17.對(duì)相同輸入數(shù)據(jù)量的不同輸入數(shù)據(jù)，算法時(shí)間用量的最大值是指______。18.畫出對(duì)應(yīng)于序列{10，20，7，75，41，67，3，9，30，45}的初始堆(堆頂元素取最小值)。19.用來標(biāo)識(shí)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)稱為______。20.采用排序算法對(duì)n個(gè)元素進(jìn)行排序，其排序趟數(shù)肯定為n-1趟的排序方法是______A.選擇和插入B.冒泡和快速C.插入和快速D.選擇和冒泡21.對(duì)于10階對(duì)稱矩陣，如果以行序或列序放入內(nèi)存中，則需要多少個(gè)存儲(chǔ)單元______A.55B.45C.100D.5022.外部排序是指在排序的整個(gè)過程中，全部數(shù)據(jù)在計(jì)算機(jī)的哪個(gè)中完成的排序______A.內(nèi)存儲(chǔ)器B.外存儲(chǔ)器C.寄存器D.內(nèi)存儲(chǔ)器和外存儲(chǔ)器23.在棧的輸入端，元素的輸入順序?yàn)?，2，3，4，5，6，進(jìn)棧過程中可以退棧，則退棧時(shí)能否排成序列3，2，5，6，4，1和1，5，4，6，2，3?若能，寫出進(jìn)棧、退棧過程；若不能，簡(jiǎn)述理由(用push(x)表示x進(jìn)棧，pop(x)表示x退棧)。24.已知關(guān)鍵字序列R={11，4，3，2，17，30，19}，請(qǐng)構(gòu)造一棵哈夫曼樹，并計(jì)算出它的帶權(quán)路徑長(zhǎng)度WPL。25.具有10個(gè)頂點(diǎn)的無向圖的邊數(shù)最多為______A.11B.110C.45D.22026.如果值相同的元素或者零元素在矩陣中的分布有一定規(guī)律，稱此類矩陣為______。27.線性表是一種線性結(jié)構(gòu)，是具有n個(gè)______的有限序列。28.冒泡排序的時(shí)間復(fù)雜度為______A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)29.排序中關(guān)鍵字比較次數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是

A.插入排序法B.希爾排序法C.直接選擇排序法D.堆排序法30.具有11個(gè)頂點(diǎn)的有向完全圖應(yīng)具有______A.110條弧B.50條弧C.90條弧D.100條弧31.在線性表的下列存儲(chǔ)結(jié)構(gòu)中進(jìn)行插入、刪除運(yùn)算，花費(fèi)時(shí)間最多的是______A.單鏈表B.順序表C.雙鏈表D.單循環(huán)鏈表32.已知一棵二叉樹的先序遍歷序列為ABCDEFGHK，中序遍歷序列為CBEDFAGKH，試建立該二叉樹并寫出它的后序遍歷序列。33.除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)的回路，稱為______。34.在下述的排序方法中，不屬于內(nèi)部排序方法的是______A.插入排序法B.選擇排序法C.拓?fù)渑判蚍―.歸并排序法35.要解決散列引起的沖突問題，最常用的方法是______A.線性探測(cè)法、二次探測(cè)法、鏈地址法B.除留余數(shù)法、線性探測(cè)法、平方取中法C.數(shù)字分析法、除留余數(shù)法、平方取中法D.除留余數(shù)法、線性探測(cè)法、二次探測(cè)法36.已知森林F={T1，T2，T3，T4，T5}，各棵樹Ti(i=1，2，3，4，5)中所含結(jié)點(diǎn)的個(gè)數(shù)分別為7、3、5、1、2，則與F對(duì)應(yīng)的二叉樹的右子樹中的結(jié)點(diǎn)個(gè)數(shù)為______A.2B.3C.8D.1137.算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為______A.正確性B.易讀性C.健壯性D.時(shí)空性38.二維數(shù)組A[12][18]采用行優(yōu)先的存儲(chǔ)方法，若每個(gè)元素各占3個(gè)存儲(chǔ)單元，且第1個(gè)元素的地址為150，則元素A[9][7]的地址為______A.654B.657C.635D.63839.圖的廣度優(yōu)先搜索遍歷的過程類似于樹的______A.前序遍歷B.中序遍歷C.按層次遍歷D.后序遍歷40.一個(gè)10×10階對(duì)稱矩陣A，采用行優(yōu)先順序壓縮存儲(chǔ)下三角矩陣，a00為第一個(gè)元素，其存儲(chǔ)地址為0，每個(gè)元素占用1個(gè)存儲(chǔ)單元，則a33的地址為______。41.試分別寫出二叉樹的先序遍歷和中序遍歷的遞歸算法。42.有10個(gè)葉結(jié)點(diǎn)的哈夫曼樹中共有______A.10個(gè)結(jié)點(diǎn)B.11個(gè)結(jié)點(diǎn)C.19個(gè)結(jié)點(diǎn)D.21個(gè)結(jié)點(diǎn)43.將下圖所示的森林轉(zhuǎn)換為一棵二叉樹。

44.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，并使插入后仍然有序，則該操作的時(shí)間復(fù)雜度為______A.O(1)B.O(n)C.O(nlog2n)D.O(n2)45.設(shè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為head，則判斷該鏈表是否為空的條件是______A.head-＞next==headB.head-＞next==NULLC.head!=NULLD.head==NULL46.在一般情況，下用直接插入排序、選擇排序和冒泡排序的過程中，所需記錄交換次數(shù)最少的是______。47.在雙鏈表中某結(jié)點(diǎn)(已知其地址)前插入一新結(jié)點(diǎn)，其時(shí)間復(fù)雜度為

A.O(n)B.O(1)C.O(n2)D.O(log2n)48.適用于靜態(tài)查找表的方法為

A.二分查找、二叉排序樹查找B.二分查找、索引順序表查找C.二叉排序樹查找、索引順序表查找D.二叉排序樹查找、散列法查找49.下列表述中，正確的是______A.序列(102，81，55，62，50，40，35，58，20)是堆B.序列(102，81，55，62，50，40，58，35，20)是堆C.序列(102，81，55，58，50，40，35，62，20)是堆D.序列(102，71，55，40，50，62，35，58，20)是堆50.在一個(gè)用一維數(shù)組A[N]表示的循環(huán)隊(duì)列中，該隊(duì)列中的元素個(gè)數(shù)最少為______個(gè)，最多為______個(gè)。第1卷參考答案一.歷年考點(diǎn)試題黑鉆版1.參考答案：利用Kruskal算法構(gòu)造最小生成樹的過程如下：

[考點(diǎn)]Kruskal算法構(gòu)造最小生成樹2.參考答案：鄰接表3.參考答案：C[解析]本題主要考查的知識(shí)點(diǎn)是算法的健壯性。[要點(diǎn)透析]算法的健壯性是指即使輸入非法數(shù)據(jù)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生預(yù)料不到的運(yùn)行結(jié)果。4.參考答案：A[考點(diǎn)]循環(huán)隊(duì)列數(shù)據(jù)元素個(gè)數(shù)的求取[解析](rear-front)%n。5.參考答案：intbinsearch_2(SqtableR,KeyTypek,intlow,inthigh)

{

intmid=(low+high)/2;

if(R.elem[mid].key==k)

returnmid;

elseif(R.elem[mid].key＞k)

returnbinsearch_2(R,k,low,mid-1);

elsereturnbinseareh_2(R,k,mid+1,high);

}[考點(diǎn)]二分查找算法遞歸實(shí)現(xiàn)6.參考答案：連通網(wǎng)的最小生成樹如下圖所示：

7.參考答案：棧頂[考點(diǎn)]棧[解析]在棧結(jié)構(gòu)中，允許插入和刪除的一端稱為棧頂。8.參考答案：B[考點(diǎn)]循環(huán)隊(duì)列的刪除[解析]

刪除后，front指向2，插入2個(gè)元素，rear指向5。9.參考答案：第一趟：[46,58,15,45,90,18,10,62]

一次交換之后

二次交換之后

三次交換之后

四次交換之后

以上“○”表示當(dāng)前經(jīng)比較不交換位置的元素?！啊酢北硎井?dāng)前經(jīng)比較交換位置的元索。

第一趟：[10181545]46[905862]

第二趟：10[181545]46[6258]90

第三趟：10[15]18[45]46[58]6290

結(jié)果：101518454658629010.參考答案：B[解析]本題主要考查的知識(shí)點(diǎn)是棧的輸出序列。[要點(diǎn)透析]此題可用排除法。棧的出入原則是后進(jìn)先出。選項(xiàng)B中顯示5最先輸出，說明其余四個(gè)元素已經(jīng)入棧，其輸出序列應(yīng)為54321。11.參考答案：012.參考答案：B[解析]本題主要考查的知識(shí)點(diǎn)是廣度優(yōu)先搜索遍歷。[要點(diǎn)透析]連通圖廣度優(yōu)先搜索的基本思想是：從圖中某個(gè)頂點(diǎn)vi出發(fā)，在訪問了vi之后依次訪問vi的所有鄰接點(diǎn)，然后依次從這些鄰接點(diǎn)出發(fā)按廣度優(yōu)先搜索方法遍歷圖的其他頂點(diǎn)，重復(fù)這一過程，直至所有頂點(diǎn)都被訪問到。結(jié)合圖形，本題答案應(yīng)選B。13.參考答案：C[考點(diǎn)]本題主要考查的是樹的結(jié)點(diǎn)間關(guān)系[解析]除根結(jié)點(diǎn)外，樹上每個(gè)結(jié)點(diǎn)可有任意多個(gè)孩子、一個(gè)雙親。14.參考答案：C[考點(diǎn)]樹的性質(zhì)[解析]任意一棵樹的結(jié)點(diǎn)個(gè)數(shù)等于所有結(jié)點(diǎn)的出度之和加一，所以葉子結(jié)點(diǎn)個(gè)數(shù)=(1*9+2*8+3*7+4*6+5*5+6*4+7*3+8*2)-(9+8+7+6+5+4+3+2)+1=113。15.參考答案：C[解析]本題主要考查的知識(shí)點(diǎn)是二分查找算法對(duì)被查找表的要求。[要點(diǎn)透析]相比順序查找而言，二分查找要求表元素是排好序的。當(dāng)采用的存儲(chǔ)結(jié)構(gòu)不是順序表，或者順序表中元素未按鍵值的次序(遞增或遞減)排列時(shí)，則不能進(jìn)行二分查找。16.參考答案：算法描述如下：

intlist_isrising(LinkListL)

{LinkListp，q；

p=L-＞next；

if(p==NULL)return0；

if(p-＞next==NULL)return1；

//單個(gè)元素是遞增的

while(p-＞next!=NULL)

{q=p-＞next；

if(q-＞data＜p-＞data)

return0；//單鏈表L的元素值非遞增

else

p=q；

}

return1；//單鏈表L的元素值是遞增

}17.參考答案：最壞時(shí)間復(fù)雜度18.參考答案：所求初始堆如下圖所示：

19.參考答案：關(guān)鍵字20.參考答案：A[考點(diǎn)]排序算法[解析]根據(jù)排序算法具體步驟，可知選擇和插入排序算法必須進(jìn)行n-1趟比較。21.參考答案：A[考點(diǎn)]對(duì)稱矩陣的壓縮存儲(chǔ)[解析]只需存放上或下三角和主對(duì)角線上的元素，共計(jì)n(n+1)/2=55個(gè)元素。22.參考答案：D[考點(diǎn)]內(nèi)部排序和外部排序的區(qū)別[解析]外部排序是指在排序的整個(gè)過程中，全部數(shù)據(jù)在計(jì)算機(jī)的內(nèi)存儲(chǔ)器和外存儲(chǔ)器中完成的排序。內(nèi)部排序僅在內(nèi)存儲(chǔ)器中進(jìn)行。23.參考答案：能排成序列3，2，5，6，4，1。

過程：push(1)；push(2)；push(3)；pop(3)；pop(2)；push(4)；push(5)；pop(5)；push(6)；pop(6)；pop(4)；pop(1)。不能排成序列1，5，4，6，2，3。

理由：在2，3依次進(jìn)棧后，根據(jù)棧結(jié)構(gòu)的特征不能產(chǎn)生排列2，3。[考點(diǎn)]棧存取的原則，即后進(jìn)先出24.參考答案：所求哈夫曼樹如下圖所示：

WPL=(30+17+19)×2+11×3+4×4+(2+3)×5=20625.參考答案：C[考點(diǎn)]無向圖邊的個(gè)數(shù)[解析]具有n個(gè)頂點(diǎn)的無向圖的邊數(shù)最多為n(n-1)/2。26.參考答案：特殊矩陣[考點(diǎn)]特殊矩陣的定義[解析]如果值相同的元素或者零元素在矩陣中的分布有一定規(guī)律，稱此類矩陣為特殊矩陣。27.參考答案：數(shù)據(jù)元素[考點(diǎn)]線性表的定義[解析]線性表是具有n個(gè)數(shù)據(jù)元素的有限序列。28.參考答案：C[考點(diǎn)]冒泡排序的時(shí)間復(fù)雜度[解析]冒泡排序是穩(wěn)定的排序方法，其時(shí)間復(fù)雜度是O(n2)。29.參考答案：A[解析]本題主要考查的知識(shí)點(diǎn)是插入排序法。[要點(diǎn)透析]在關(guān)鍵字基本有序的情況下，插入排序每趟的關(guān)鍵字比較次數(shù)為1次，總共進(jìn)行n-1次比較，而在初始關(guān)鍵字無序的情況下，最壞的時(shí)候，其關(guān)鍵字的比較的總次數(shù)為n(n-1)/2次。而選項(xiàng)中的其他三種排序方法中關(guān)鍵字的比較次數(shù)，都與初始狀態(tài)無關(guān)。30.參考答案：A[考點(diǎn)]本題主要考查的是一個(gè)具有n個(gè)頂點(diǎn)的有向完全的弧數(shù)[解析]任何兩點(diǎn)之間都有弧的有向圖稱為有向完全圖?！獋€(gè)具有n個(gè)頂點(diǎn)的有向完全的弧數(shù)為n(n-1)=11*10=110條。31.參考答案：B[考點(diǎn)]線性表的不同存儲(chǔ)結(jié)構(gòu)中進(jìn)行插入、刪除運(yùn)算的時(shí)間復(fù)雜度[解析]線性表的不同存儲(chǔ)結(jié)構(gòu)中進(jìn)行插入、刪除運(yùn)算的時(shí)間復(fù)雜度，花費(fèi)時(shí)間最多的是順序表(由于每次插入、刪除都需要移動(dòng)數(shù)據(jù))。32.參考答案：由先序遍歷序列和中序遍歷序列得到如下二叉樹：

后序遍歷序列為：CEFDBKHGA。[考點(diǎn)]由先序遍歷序列和中序遍歷序列推斷二叉樹。對(duì)二叉樹進(jìn)行后序遍歷，得到后序序列33.參考答案：簡(jiǎn)單回路或簡(jiǎn)單環(huán)[考點(diǎn)]簡(jiǎn)單回路或簡(jiǎn)單環(huán)定義[解析]除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)的回路，稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。34.參考答案：C[考點(diǎn)]本題主要考查的知識(shí)點(diǎn)是內(nèi)部排序方法。

題目選項(xiàng)中的四種排序方法中，只有拓?fù)渑判蚴菍?duì)圖中結(jié)點(diǎn)進(jìn)行排序的方法，不屬于內(nèi)部排序方法，而其他的三種排序方法都屬于內(nèi)部排序方法。35.參考答案：A[考點(diǎn)]數(shù)字分析法、除留余數(shù)法、平方取中法[解析]解決散列引起的沖突問題，最常用的方法是線性探測(cè)法、二次探測(cè)法、鏈地址法。36.參考答案：D[考點(diǎn)]本題主要考查的知識(shí)點(diǎn)是森林與二叉樹的轉(zhuǎn)換。

換二叉樹中右子樹的結(jié)點(diǎn)個(gè)數(shù)為第二棵至第五棵樹中結(jié)點(diǎn)之和。故本題答案為D。37.參考答案：A[考點(diǎn)]算法的評(píng)價(jià)因素[解析]算法的正確性是指能正確地實(shí)現(xiàn)預(yù)定功能，滿足具體問題的需要。38.參考答案：B[考點(diǎn)]本題主要考查的是數(shù)組元素地址的運(yùn)算[解析]對(duì)于m*n的數(shù)組采取，行先存儲(chǔ)，Loc[i,j]=Loc[0,0]+(