2023年自考類計算機類(工學類)數(shù)據結構導論歷年高頻考題帶答案難題附詳解

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

2.______是順序存儲與鏈式存儲相結合的存儲方法。3.算法在發(fā)生非法操作時可以作出處理的特性稱為

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

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

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

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

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

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

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

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.在一個用一維數(shù)組A[N]表示的循環(huán)隊列中，該隊列中的元素個數(shù)最少為______個，最多為______個。第1卷參考答案一.歷年考點試題黑鉆版1.參考答案：利用Kruskal算法構造最小生成樹的過程如下：

[考點]Kruskal算法構造最小生成樹2.參考答案：鄰接表3.參考答案：C[解析]本題主要考查的知識點是算法的健壯性。[要點透析]算法的健壯性是指即使輸入非法數(shù)據，算法也能適當?shù)刈龀龇磻蜻M行處理，不會產生預料不到的運行結果。4.參考答案：A[考點]循環(huán)隊列數(shù)據元素個數(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);

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

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

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

一次交換之后

二次交換之后

三次交換之后

四次交換之后

以上“○”表示當前經比較不交換位置的元素。“□”表示當前經比較交換位置的元索。

第一趟：[10181545]46[905862]

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

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

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

intlist_isrising(LinkListL)

{LinkListp，q；

p=L-＞next；

if(p==NULL)return0；

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

//單個元素是遞增的

while(p-＞next!=NULL)

{q=p-＞next；

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

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

else

p=q；

}

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

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

19.參考答案：關鍵字20.參考答案：A[考點]排序算法[解析]根據排序算法具體步驟，可知選擇和插入排序算法必須進行n-1趟比較。21.參考答案：A[考點]對稱矩陣的壓縮存儲[解析]只需存放上或下三角和主對角線上的元素，共計n(n+1)/2=55個元素。22.參考答案：D[考點]內部排序和外部排序的區(qū)別[解析]外部排序是指在排序的整個過程中，全部數(shù)據在計算機的內存儲器和外存儲器中完成的排序。內部排序僅在內存儲器中進行。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依次進棧后，根據棧結構的特征不能產生排列2，3。[考點]棧存取的原則，即后進先出24.參考答案：所求哈夫曼樹如下圖所示：

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

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

題目選項中的四種排序方法中，只有拓撲排序是對圖中結點進行排序的方法，不屬于內部排序方法，而其他的三種排序方法都屬于內部排序方法。35.參考答案：A[考點]數(shù)字分析法、除留余數(shù)法、平方取中法[解析]解決散列引起的沖突問題，最常用的方法是線性探測法、二次探測法、鏈地址法。36.參考答案：D[考點]本題主要考查的知識點是森林與二叉樹的轉換。

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