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

2023年自考類計(jì)算機(jī)類(工學(xué)類)數(shù)據(jù)結(jié)構(gòu)歷年高頻考題帶答案難題附詳解（圖片大小可自由調(diào)整）第1卷一.歷年考點(diǎn)試題黑鉆版(共50題)1.圖的鄰接表的類型定義如下所示：

#defineMaxVertexNum50

typedefstructnode{

intadjvex;

structnode*next;

}EdgeNode;

typedefstruct{

VertexTypevertex;

EdgeNode*firstedge;

}VertexNode;

typedefVertexNodeAdjList[MaxVertexNum];

typedefstruct{

AdjListadjiist;

intn,e;

}ALGraph;

為便于刪除和插入圖的頂點(diǎn)的操作，可將鄰接表的表頭向量定義為鏈?zhǔn)浇Y(jié)構(gòu)，兩種定義的存儲(chǔ)表示實(shí)例如下圖所示，請(qǐng)寫出重新定義的類型說明。

2.對(duì)于一個(gè)二維數(shù)組A[m][n]，若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素A[i][j]相對(duì)于A[0][0]的地址為______。3.一個(gè)隊(duì)列的輸入序列是1,2,3,4，則隊(duì)列的輸出序列是

A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,14.樹(A(B(E，(F(J，K)))，C(G)，D(H，I)))的度和深度分別是______A.3；3B.2；4C.3；4D.4；45.兩個(gè)字符串相等的條件是

A.串的長(zhǎng)度相等B.含有相同的字符集C.都是非空串D.串的長(zhǎng)度相等且對(duì)應(yīng)的字符相同6.若對(duì)關(guān)鍵字序列(43,02,80,48,26,57,15,73,21,24,66)進(jìn)行一趟增量為3的希爾排序，則得到的結(jié)果為______。7.已知圖G共有4個(gè)結(jié)點(diǎn)，其各個(gè)頂點(diǎn)的度分別為2、4、3、1，那么該圖的邊數(shù)為______A.3B.6C.4D.58.用二叉鏈表表示具有n個(gè)結(jié)點(diǎn)的二叉樹時(shí)，值為空的指針域的個(gè)數(shù)為

A.n-1B.nC.n+1D.2n9.設(shè)有一順序棧S，元素s1，s2，s3，s4，s5，s6依次進(jìn)棧，如果6個(gè)元素出棧的順序是s2，s3，s4，s5，s6，s1，則棧的容量至少應(yīng)該是

A.2B.3C.5D.610.對(duì)序列(8，13，26，55，29，44)從小到大進(jìn)行基數(shù)排序，第一趟排序的結(jié)果是______A.(13，44，55，26，8，29)B.(13，26，55，44，8，29)C.(8，13，26，29，44，55)D.(29，26，8，44，55，13)11.設(shè)有一個(gè)用線性探測(cè)法解決沖突得到的散列表：

散列函數(shù)為H(k)=Kmod11

若要查找元素14，探測(cè)的次數(shù)(比較的次數(shù))是A.8B.9C.3D.612.設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖邊的數(shù)目最多為______A.n-1B.n(n-1)/2C.n(n+1)/2D.n213.廣義表的深度是指______。14.二維數(shù)組A[12][18]采用列優(yōu)先的存儲(chǔ)方法，若每個(gè)元素各占3個(gè)存儲(chǔ)單元，且第1個(gè)元素的地址為150，則元素A[9][7]的地址為

A.429B.432C.435D.43815.以下是圖的廣度優(yōu)先搜索算法，請(qǐng)?jiān)赺_____處填充適當(dāng)?shù)恼Z句。

Bfs(GraphTpg,intv)

{QueptrTpQ;

ArcNodeTp*P;

InitQueue(&Q);

printf("%"”,v);

visited[v]=1;

______

while(!EmptyQueue(Q))

{______;

p=g.adjlist[v].firstarc;

while(p!=NULL)

{if(!visited[p—＞adjvex])

{printf("%"”,p—＞adjvex);

visited[p—＞adjvex]=1);

EnQueue(&Q，p—＞adjvex);

}

______;

}

}

}16.算法的時(shí)間復(fù)雜度表征的是______A.算法的可讀性B.算法的難易程度C.執(zhí)行算法所耗費(fèi)的時(shí)間D.執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間17.______的鄰接矩陣不一定是不對(duì)稱的。18.從樹的根結(jié)點(diǎn)到樹中的其余結(jié)點(diǎn)之間的路徑______惟一的。19.若一棵二叉樹中只有葉結(jié)點(diǎn)和左、右子樹皆非空的結(jié)點(diǎn)，設(shè)葉結(jié)點(diǎn)的個(gè)數(shù)為1，則左右子樹皆非空的結(jié)點(diǎn)個(gè)數(shù)為______。20.ISAM文件采用______索引結(jié)構(gòu)，而VSAM文件采用______索引結(jié)構(gòu)。21.已知下面的一個(gè)圖，請(qǐng)根據(jù)普里姆算法構(gòu)出它的一棵最小生成的樹。

22.一個(gè)棧的人棧序列是a,b,c,d,e，則棧的不可能的輸出序列是

A.edcbaB.decbaC.dceabD.abcde23.數(shù)組的長(zhǎng)度是______，線性表的長(zhǎng)度是______。24.具有24個(gè)記錄的序列，采用冒泡排序最少的比較次數(shù)是

A.1B.23C.24D.52925.在用p訪問循環(huán)鏈表(其中，head為頭指針)時(shí)，判斷不是訪問表結(jié)束的條件是______A.p!=headB.p-＞next!=NULLC.p!=NULLD.p-＞next!=head26.Aarr和Barr兩個(gè)數(shù)組的說明如下：

VAR

Aarr:Array[O··7]ofchar;

Barr:Array[-5··2,3,··8]ofchar;這兩個(gè)數(shù)組分別能存放的字符的最大個(gè)數(shù)是

A.7和35B.1和5C.8和48D.1和627.已知一采用開放地址法解決Hash表沖突，要從此Hash表中刪除一個(gè)記錄，正確的做法是

A.將該元素所在的存儲(chǔ)單元清空B.將該元素用一個(gè)特殊的元素替代C.將與該元素有相同Hash地址的后繼元素順次前移一個(gè)位置D.用與該無素有相同Hash地址的最后插入表中的元素替代28.如果一個(gè)圖中有n條邊，則此圖的生成樹含有______條邊，所以生成樹是圖的邊數(shù)______的連通圖。29.下列線性表中，能使用二分查找的是A.順序存儲(chǔ)(2，12，5，6，9，3，89，34，25)B.鏈?zhǔn)酱鎯?chǔ)(2，12，5，6，9，3，89，34，25)C.順序存儲(chǔ)(2，3，5，6，9，12，25，34，89)D.鏈?zhǔn)酱鎯?chǔ)(2，3，5，6，9，12，25，34，89)30.在一棵二叉樹中，度為O的結(jié)點(diǎn)個(gè)數(shù)與度為2的結(jié)點(diǎn)個(gè)數(shù)和度數(shù)之間有什么關(guān)系?在一棵完全二叉樹中，如果共有200個(gè)結(jié)點(diǎn)，則能判斷出葉結(jié)點(diǎn)的個(gè)數(shù)嗎?如果能，請(qǐng)指出會(huì)有多少個(gè)葉結(jié)點(diǎn)，多少個(gè)度為2的結(jié)點(diǎn)?多少個(gè)度為1的結(jié)點(diǎn)?如果有201個(gè)結(jié)點(diǎn)呢?31.以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上的出隊(duì)列，請(qǐng)?jiān)赺_____處用適當(dāng)?shù)恼Z句予以填充。

intOutQueue(QueptrTp*lq,DataType*x)

{LqueueTp*s;

if(1q—＞front==lq—＞rear){error("隊(duì)空");return(0);}

else{s=(lq—＞front)—＞next;

______=s—＞data;

(lq—＞front)—＞next______;

if(s—＞next==NULL)lq—＞rear=lq—＞front;

free(s);

return(1);

}

}32.已知廣義表G，head(G)與tail(G)的深度分別為4和6，則G的深度是______。33.設(shè)樹T的度為4，其中度為1、2、3和4的結(jié)點(diǎn)個(gè)數(shù)分別是4、2、1和1，則T中葉子結(jié)點(diǎn)的個(gè)數(shù)是：______。34.一個(gè)字符串相等的充要條件是______和______。35.對(duì)同一個(gè)基本有序的待排序列分別進(jìn)行堆排序、快速排序和冒泡排序，最省時(shí)間的算法是______。36.對(duì)序列(48,37,63,96,22,31,50,55,11)進(jìn)行升序的堆排序，寫出構(gòu)建的初始(大根)堆及前兩趟重建堆之后的序列狀態(tài)。

初始堆：

第1趟：

第2趟：37.堆是一個(gè)鍵值序列(k1，k2，k…，k1…，k0)，對(duì)i=1，2…，[n/2]，滿足

A.ki≤k2i≤k2i+1B.ki＜k2i＜k2i+1C.ki≤k2i且k≤k2i+1(2i+1≤n)D.ki≤k2i或ki≤k2i+l(2i+1≤n)38.在分塊查找法中，首先查找______，然后再查找相應(yīng)的______。39.在下面的程序中，語句S的執(zhí)行次數(shù)為

for(i=1;i＜=n-1;i++)

{for(j=n;j＞=i;j--)

{S;

}

40.假設(shè)以列優(yōu)先順序存儲(chǔ)二維數(shù)組A[5][8]，其中元素A[0][0]的存儲(chǔ)地址為L(zhǎng)OC(a00)，且每個(gè)元素占4個(gè)存儲(chǔ)單元，則數(shù)組元素A[i][j]的存儲(chǔ)地址為______。41.判斷一個(gè)沒有頭結(jié)點(diǎn)的單鏈表head為空的條件是______。42.對(duì)圖采用鄰接矩陣表示法，那么無向圖的鄰接矩陣是一個(gè)______矩陣。43.由字符集{s,t,a,e,i)及其在電文中出現(xiàn)的頻度構(gòu)建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100，請(qǐng)根據(jù)該哈夫曼樹進(jìn)行譯碼，寫出原來的電文。

44.圖的遍歷方法有很多，但主要常用的是深度優(yōu)先遍歷和______。45.以下為單鏈表按序號(hào)查找的運(yùn)算，分析算法，請(qǐng)?jiān)赺_____處填上正確的語句。

pointerfind_lklist(1klisthead,inti)

{

p=head;j=0;

while(______)

{p=p—＞next;j++;}

if(i==j)return(p);

elsereturn(NULL);

}46.在圖的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中的頂點(diǎn)數(shù)，對(duì)于有向圖來說是______，對(duì)于無向圖來說是______。47.算法分析的目的是

A.辨別數(shù)據(jù)結(jié)構(gòu)的合理性B.評(píng)價(jià)算法的效率C.研究算法中輸入與輸出的關(guān)系D.鑒別算法的可讀性48.假設(shè)一棵具有12個(gè)結(jié)點(diǎn)的二叉樹的存儲(chǔ)結(jié)構(gòu)如下圖所示，其中l(wèi)eft和right分別表示此結(jié)點(diǎn)左、右孩子的序號(hào)，data表示此結(jié)點(diǎn)的數(shù)據(jù)，根結(jié)點(diǎn)為編號(hào)為4的結(jié)點(diǎn)。請(qǐng)根據(jù)此存儲(chǔ)結(jié)構(gòu)畫出對(duì)應(yīng)的二叉樹，然后回答下面的問題：

(1)寫出前序遍歷、中序遍歷和后序遍歷此二叉樹時(shí)的遍歷序列。

(2)求出此樹的高度并分析葉結(jié)點(diǎn)的個(gè)數(shù)。

(3)結(jié)點(diǎn)E的雙親及子孫分別是什么?49.有m個(gè)葉子結(jié)點(diǎn)(又稱外結(jié)點(diǎn))的哈夫曼樹，其結(jié)點(diǎn)總數(shù)是______。50.畫出下圖所示樹的孩子鏈表。

第1卷參考答案一.歷年考點(diǎn)試題黑鉆版1.參考答案：typeclefstructArcNode{

VNode*adjvex;

//該弧所指向的頂點(diǎn)的位置

structArcNode*nextarc;

//指向下一條弧的指針

}ArcNode;

typedefstructVNode{

VertexTypedata;

//頂點(diǎn)信息

structVNode*nextVertex;

//指向下一個(gè)頂點(diǎn)的指針

ArcNode*firstarc;

//指向第一條依附該頂點(diǎn)的弧

}VNode.*AdjList;

typedefstruct{

AdjListadjList;

intn,e;

}ALGraph;2.參考答案：i×j+i全元素位置3.參考答案：B4.參考答案：C[考點(diǎn)]樹的廣義表表示法以及樹的度和深度的定義

[解析]根據(jù)所給樹的廣義表，可以畫出樹形圖，從樹形圖中可以看出結(jié)點(diǎn)的最大度為3，所以樹的度為3；同時(shí)，該樹具有4層，也就是深度為4。5.參考答案：D6.參考答案：15,02,21,24,26,57,43,66,80,48,737.參考答案：D[考點(diǎn)]圖形結(jié)構(gòu)中頂點(diǎn)的度和圖的邊數(shù)的關(guān)系

[解析]根據(jù)圖的邊數(shù)等于所有頂點(diǎn)度數(shù)和的一半可知，該圖的邊數(shù)為5。8.參考答案：C9.參考答案：B10.參考答案：A[考點(diǎn)]基數(shù)排序

[解析]根據(jù)基數(shù)排序的方法，第一趟先按個(gè)位數(shù)排序，得到排序結(jié)果為(13，44，55，26，8，29)。11.參考答案：D12.參考答案：B[考點(diǎn)]無向圖的邊數(shù)的問題

[解析]無向圖的邊數(shù)最多為n(n-1)/2。13.參考答案：廣義表展開后所含括號(hào)的最大層數(shù)14.參考答案：A15.參考答案：EnQueue(&Q,v)OutQueue(&Q,&v)p=p—＞nextarc16.參考答案：C[考點(diǎn)]算法的時(shí)間復(fù)雜度定義

[解析](1)執(zhí)行算法所耗費(fèi)的時(shí)間，即時(shí)間復(fù)雜性；(2)執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，主要是輔助空間，即空間復(fù)雜性；(3)算法應(yīng)易于理解、易于編程、易于調(diào)試等，即可讀性和可操作性。因此表征算法時(shí)間復(fù)雜度的是執(zhí)行算法耗費(fèi)的時(shí)間，C正確。17.參考答案：有向圖18.參考答案：是19.參考答案：1-120.參考答案：靜態(tài)

動(dòng)態(tài)21.參考答案：構(gòu)造最小生成樹的過程如下：

22.參考答案：C23.參考答案：固定的

可變的24.參考答案：B25.參考答案：A[考點(diǎn)]循環(huán)鏈表結(jié)束條件的判斷

[解析]在用p訪問循環(huán)鏈表(其中，head為頭指針)時(shí)，p-＞next!=NULL，p!=NULL或者p-＞next!=head是判斷表結(jié)束的條件。26.參考答案：C27.參考答案：B28.參考答案：n-1

最少29.參考答案：C[考點(diǎn)]二分法查找的使用條件

[解析]二分法查找要求查找對(duì)象的線性表必須是順序存儲(chǔ)結(jié)構(gòu)的有序表，因此排除B和D，又因?yàn)锳選項(xiàng)中不是有序表，因此答案選C。30.參考答案：在一棵二叉樹中，度數(shù)為0的結(jié)點(diǎn)(葉結(jié)點(diǎn))的個(gè)數(shù)總是比度為2的結(jié)點(diǎn)的個(gè)數(shù)多1。根據(jù)完全二叉樹的定義：若一棵二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干住置上，則我們可以得出這樣一個(gè)結(jié)論：在一棵完全二叉樹上，或者沒有度為1的結(jié)點(diǎn)。則根據(jù)以上分析，我們可以這樣計(jì)算此題：設(shè)度數(shù)為2的結(jié)點(diǎn)有n個(gè)，則必有n+1個(gè)度為0的結(jié)點(diǎn)，即度數(shù)為2和度數(shù)為0的結(jié)點(diǎn)數(shù)之和為2n+1(是奇數(shù))，于是得出，如果一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為奇數(shù)，則此樹中必然不存在度為1的結(jié)點(diǎn)，若完全二叉樹中結(jié)點(diǎn)總數(shù)為偶數(shù)，則必然有1個(gè)度為1的結(jié)點(diǎn)存在，于是若完全二叉樹中有200個(gè)結(jié)點(diǎn)，就必有100個(gè)對(duì)結(jié)點(diǎn)，99個(gè)度數(shù)為2的結(jié)點(diǎn)，12個(gè)度數(shù)為1的結(jié)點(diǎn)，如果二叉樹中有201個(gè)結(jié)點(diǎn)，則必有101個(gè)葉結(jié)點(diǎn)，100個(gè)度數(shù)為2的結(jié)點(diǎn)，沒有度數(shù)為1的結(jié)點(diǎn)。31.參考答案：*xs—＞next32.參考答案：6[考點(diǎn)]廣義表的深度

[解析]若表尾深度大于表頭深度，那么線性表的深度為表尾的深度。33.參考答案：8個(gè)34.參考答案：兩個(gè)字符串的長(zhǎng)度相等

對(duì)應(yīng)位置的字符相等35.參考答案：冒泡排序[考點(diǎn)]排序方法的選擇

[解析]當(dāng)待排序記錄關(guān)鍵字基本有序時(shí)，宜采用直接插入排序或冒泡排序。36.參考答案：初始堆：(96,55,63,48,22,3