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

2023年自考類計算機類(工學類)數(shù)據(jù)結構導論歷年高頻考題帶答案難題附詳解（圖片大小可自由調整）第1卷一.歷年考點試題黑鉆版(共50題)1.數(shù)據(jù)的邏輯結構通常包括集合、線性結構、______和圖狀結構。2.試寫一個用鏈表表示的直接插入排序算法。3.向一個不帶頭結點的棧指針為lst的鏈棧中插入一個*s所指結點時，則執(zhí)行語句為______。4.順序查找算法的平均查找長度為______A.log2nB.(n-1)/2C.n/2D.(n+1)/25.已知一個無向圖的頂點集為{a，b，c，d，e}，其鄰接矩陣如下圖所示

(1)畫出該圖的圖形。

(2)根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應的遍歷序列。6.將下圖所示的一棵樹轉換為對應的二叉樹。

7.一個10×10階對稱矩陣A，采用行優(yōu)先順序壓縮存儲下三角矩陣，a00為第一個元素，其存儲地址為0，每個元素占用1個存儲單元，則a33的地址為______。8.索引順序表由______和______兩部分組成。9.索引順序表的索引表在組織形式上是一個______A.順序表B.單鏈表C.隊列D.棧10.下列序列中，符合堆定義的是______A.(100，80，55，60，50，40，58，35，20)B.(100，80，55，58，50，40，60，35，20)C.(100，80，55，60，50，40，35，58，20)D.(100，70，55，60，50，40，58，35，20)11.在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是______A.G中有弧＜Vi，Vj＞B.G中有一條從Vi到Vj的路徑C.G中沒有弧＜Vi，vj＞D.G中有一條從Vj到Vi的路徑12.在一個單鏈表中，若p所指結點不是最后結點，s指向已生成的新結點，則在p之后插入s所指結點的正確操作是______A.s-＞next=p-＞next；p-＞next=s；B.p-＞next=s-＞next；s->next=p；C.s-＞next=p；p-＞next=s；D.s-＞next=p-＞next；p=s；13.一組記錄的鍵值為(12，38，35，25，74，50，63，90)，按二路歸并排序方法對該序列進行一趟歸并后的結果為______A.12，38，25，35，50，74，63，90B.12，38，35，25，74，50，63，90C.12，25，35，38，50，74，63，90D.12，35，38，25，63，50，74，9014.設F是一個森林，B是由F轉換得到的二叉樹。若F中有n個非終端結點，則B中右指針域為空的結點有______個。15.在圖的鄰接表存儲結構上執(zhí)行廣度優(yōu)先搜索遍歷類似于二叉樹上的

A.先根遍歷B.中根遍歷C.后根遍歷D.按層次遍歷16.一維數(shù)組又稱______，它由一組具有相同類型的數(shù)據(jù)元素組成。17.一個順序隊列的第5個元素的存儲地址是200，第10個元素的存儲地址是225。每個元素的長度是5，則第20個元素的地址是______。18.從邏輯關系來看，數(shù)據(jù)元素的直接前驅為0個或1個的數(shù)據(jù)結構只能是______A.線性結構B.樹形結構C.線性結構和樹形結構D.線性結構和圖狀結構19.下列查找中，效率最高的查找方法是______A.順序查找B.二分查找C.索引順序查找D.分塊查找20.下圖所示二叉樹的中序遍歷序列是______

A.abcdgefB.dbaefcgC.dfebageD.defbagc21.下面關于線性表的敘述中，錯誤的是______A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元C.線性表采用順序存儲，便于進行插入和刪除操作D.線性表采用鏈接存儲，便于進行插入和刪除操作22.寫出將一個無向圖的鄰接表轉換或鄰接矩陣的算法。23.設一個鏈棧的輸入序列為X，Y，Z，試寫出出棧的所有可能的輸出序列及其操作步驟。24.靜態(tài)查找表的運算包括______A.建表、刪除B.建表、查找和讀表中元素C.查找和讀表中元素D.建表、查找和插入25.順序存儲實現(xiàn)的隊列稱為______，是由一個______及兩個分別指示隊列首元素和隊列尾元素的變量組成。26.若用冒泡排序法對序列19，14，6，27，8，12，17，52，10，26，47，29，42，25從小到大進行排序，需要進行比較的次數(shù)是______A.33B.91C.70D.4527.在圖的鄰接表存儲結構上執(zhí)行廣度優(yōu)先搜索遍歷類似于二叉樹上的______A.按層次遍歷B.中序遍歷C.后序遍歷D.先序遍歷28.無向圖中一個頂點的度是指圖中______A.與該頂點相鄰接的頂點數(shù)B.通過該頂點的簡單路徑數(shù)C.通過該頂點的回路數(shù)D.與該頂點連通的頂點數(shù)29.對于循環(huán)隊列，試寫出求隊列含有多少個元素的算法。30.將含有80個結點的完全二叉樹從根這一層開始，每層從左到右依次對結點編號，根結點的編號為1，則關于編號40的結點的左右孩子的說法正確的是______A.左孩子編號為79，右孩子編號為80B.左孩子不存在，右孩子編號為80C.左孩子編號為80，右孩子不存在D.左孩子不存在，右孩子不存在31.設一個棧的輸入序列是a，b，c，d，則所得到的輸出序列(輸入過程中允許出棧)不可能出現(xiàn)的是______A.a，b，c，dB.c，d，a，bC.d，c，b，aD.a，b，d，c32.假設以數(shù)組A[n]存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。若設定尾指針指向隊列中的隊尾元素，頭指針指向隊列中隊頭元素的前一個位置，則當前存于隊列中的元素個數(shù)為______A.(rear-front)%nB.(rear-front-1)%nC.(front-rear+1)%nD.(rear-front+n)%n33.設有一順序隊列sq，容量為5，初始狀態(tài)時sq.front=sq.rear=0，畫出做完下列操作后隊列及其頭尾指針的狀態(tài)變化情況，若不能入隊，請簡述其理由后停止。

(1)d，e，b入隊

(2)d，e出隊

(3)i，j入隊

(4)b出隊

(5)n，o，p入隊34.假設樹采用孩子兄弟鏈表表示法，其結構定義如下：

typedefstructtnode

{DataTypedata;

structtnode*son,*brother;

}*Tree;

試編寫算法voidleveltree(Treeroot)實現(xiàn)樹的按層次遍歷。35.n個頂點且含有環(huán)路的無向連通圖中，至少含有______條邊。36.以二叉鏈表作為存儲結構，編寫求二叉樹葉子數(shù)的算法。37.算法的便于閱讀和理解的特性稱為

A.正確性B.易讀性C.健壯性D.時空性38.算法的時間性能是指算法包含的______。39.______是順序存儲與鏈式存儲相結合的存儲方法。40.下列四種排序方法中，要求附加的內存容量最大的是______A.插入排序B.選擇排序C.快速排序D.歸并排序41.如下圖所示，在棧的輸入端依次輸入元素A，B，C，試寫出在棧的輸出端可以得到的所有輸出序列，并給出每個序列的操作過程(用push(A)表示A進棧，pop(A)表示A出棧)。

42.雙向循環(huán)鏈表找前驅結點和后繼結點的時間復雜度為______。43.下列說法正確的是

A.數(shù)據(jù)是數(shù)據(jù)元素的基本單位B.數(shù)據(jù)元素是數(shù)據(jù)項中不可分割的最小標識單位C.數(shù)據(jù)可由若干個數(shù)據(jù)元素構成D.數(shù)據(jù)項可由若干個數(shù)據(jù)元素構成44.若某二叉樹中度為1的結點數(shù)為4，度為2的結點數(shù)為6，則該樹葉子結點數(shù)為______。45.對于一組數(shù)據(jù)(24，12，22，34，5，44，76，61，100，3，1，120)，寫出該數(shù)據(jù)采用歸并算法的排序過程和排序結果。46.以二叉鏈表作為存儲結構，試編寫求二叉樹中葉子數(shù)的算法。47.已知循環(huán)隊列的存儲空間大小為m，隊頭指針front指向隊頭元素，隊尾指針rear指向隊尾元素的下一個位置，則在隊列不滿的情況下，隊列的長度是______。48.關于算法的描述，不正確的是______A.算法最終必須由計算機程序實現(xiàn)B.所謂最壞時間復雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界C.健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的運行結果D.算法的優(yōu)劣與算法描述語言無關49.滿二叉樹______是完全二叉樹，完全二叉樹______是滿二叉樹。50.分別寫出刪除單向和雙向循環(huán)鏈表中指針p所指結點的直接后繼結點(非尾結點)對應的語句。第1卷參考答案一.歷年考點試題黑鉆版1.參考答案：樹形結構[考點]數(shù)據(jù)的邏輯結構[解析]數(shù)據(jù)的邏輯結構通常包括集合、線性結構、樹形結構和圖狀結構。2.參考答案：voidsort(DLinkListH)

{pre=H-＞next;

while(p!=H)

{p=pre-＞next;

q=p-＞next;

while((pre!=H)&&(p-＞data＜pre-＞data))

pre=pre-＞prior;

if(pre!=p-＞prior;

{p-＞prior-＞next=p-＞next;

p-＞next-＞prior-＞p-＞prior;

p-＞next=pre-＞next;

pre-＞next-＞prior=p:

p-＞prior=pre;pre-＞next=p;

}

p=q;

}

}[考點]鏈表的直接插入排序3.參考答案：s-＞next=1st：lst=s：4.參考答案：D[考點]順序查找算法長度[解析]ASL=(n+1)/2。5.參考答案：見下圖

[考點]已知的鄰接矩陣與無向圖的轉換，以及無向圖深度優(yōu)先遍歷序和廣度優(yōu)先遍歷。6.參考答案：結果見下圖：

[考點]一棵樹轉換為對應的二叉樹的算法[解析](1)將所有兄弟結點連接起來。

(2)保留第一個兄弟結點與父結點的連接，斷開其他兄弟結點與父結點的連接，然后以根結點為軸心按順時針方向旋轉45°角。7.參考答案：98.參考答案：一個索引表

一個順序表[考點]索引順序表[解析]索引順序表由兩部分組成：一個索引表和一個順序表。9.參考答案：A10.參考答案：C[考點]堆的定義[解析]根據(jù)堆的定義以及4個選項可知其是最大堆，根據(jù)最大堆的特性，這棵二叉樹中任意一結點的值都不小于它的兩個孩子的值(若存在孩子的話)，只有C選項符合。11.參考答案：D[考點]本題主要考查的知識點是有向圖的拓撲排序序列。

在有向圖G中，若有一條從vj到vi的路徑，則在它的拓撲排序序列中，頂點vj必須出現(xiàn)在頂點vi之前。12.參考答案：A13.參考答案：A14.參考答案：n+115.參考答案：D[解析]本題主要考查的知識點是廣度優(yōu)先搜索。[要點透析]連通圖廣度優(yōu)先搜索的基本思想是：從圖中某個頂點vi出發(fā)，在訪問了vi之后依次訪問vi的所有鄰接點，然后分別從這些鄰接點出發(fā)按廣度優(yōu)先搜索遍歷圖的其他頂點，重復這一過程，直至所有頂點都被訪問到。類似于二叉樹按層次(同一層從左到右)遍歷的算法。16.參考答案：向量17.參考答案：27518.參考答案：C[考點]邏輯結構[解析]從邏輯關系來看，數(shù)據(jù)元素的直接前驅為0個或1個的數(shù)據(jù)結構只能是線性結構和樹形結構。圖形結構的直接前驅可能為2，3……大于1的任意個。19.參考答案：B20.參考答案：C[考點]二叉樹的中序遍歷[解析]二叉樹的中序遍歷順序是、左子樹、根、右子樹。21.參考答案：C[考點]本題主要考查的知識點是線性表。

[解析]順序存儲結構的地址在內存中是連續(xù)的，所以可以通過計算地址實現(xiàn)隨機存取，而鏈式存儲結構的存儲地址不一定是連續(xù)的，只能通過第一個結點的指針順序存取。22.參考答案：算法描述如下：

voidAdjlist_to_Matrix(GraphTP_Adj*ga，GraphTp_Mat*gb)

{inti，j；

ArcNodeTp*p；

gb->vexnum=ga-＞vexnum；

//讀入頂點個數(shù)和邊數(shù)

gb-＞arcnum=ga-＞arcnum；

for(i=0；i＜ga-＞vexnum；i++)

for(j=0；j＜ga-＞vexnum；j++)

gb-＞arcs[i][j]=0；

//初始化鄰接矩陣

for(i=0；i＜ga-＞vexnum；i++)

{p=ga-＞adjlis[i].firstarc；

while(p!=NULL)

{j=p-＞adjvex；

ga-＞arcs[i][j]=1：

p=p-＞nextarc；

}

}

}23.參考答案：

(1)XYZ

(2)XZY

(3)YZX

(4)YXZ

(5)ZYX[考點]棧的應用[解析](1)X進X出，Y進Y出，Z進Z出；(3)X進X出，Y進，Z進Z出，Y出；(3)X進，Y進Y出，Z進Z出，X出；(4)X進，Y進Y出，X出，Z進Z出。24.參考答案：B[考點]靜態(tài)查找表的元素[解析]靜態(tài)查找表是以具有相同特性的數(shù)據(jù)元素集合為邏輯結構，包括三種基本運算：建表、查找和讀表中元素。25.參考答案：順序隊列

一維數(shù)組[考點]順序隊列[解析]順序隊列的定義。26.參考答案：B[考點]冒泡排序法[解析]冒泡排序法總的比較次數(shù)為n(n-1)/2次，n為待排序列元素個數(shù)。27.參考答案：A[考點]廣度優(yōu)先搜索[解析]廣度優(yōu)先搜索的基本思想是：從圖中某個頂點出發(fā)，在訪問該結點后，依次訪問該結點的所有鄰接點，然后從這些鄰接點按廣度優(yōu)先搜索遍歷其他頂點，所以類似于二叉樹按層次(同一層，從左到右)的遍歷算法。28.參考答案：A[考點]無向圖頂點的度[解析]無向圖頂點的度指與該頂點相鄰的頂點數(shù)。29.參考答案：假定循環(huán)隊列的類型定義如下：

constintmaxsize=……；

typedefstructcycqueue

{DataType[maxsize]；

intfront，rear；

}CycqueueTp；

解法一：計數(shù)器初始化為0，從隊首開始沿著隊列順序搜索，每走過一個元素，計數(shù)器加1，直到隊尾，計數(shù)器的最終值即隊列長度。算法描述如下：

intque_length(CycqueueTp*cq)

{intn，k；

n=0；//計數(shù)器

k=cq-＞front;

while(k!=cq-＞rear)

{n++；

k=(k+1)%maxsize；

}

returnn；

}

解法二：利用隊首和隊尾的關系求出隊列的長度。

intque_length(CycqueueTp*cq)

{

return(maxsize+cq-＞rear-cq-＞

front)%maxsize；

}30.參考答案：C[考點]完全二叉樹某結點的左右孩子編號[解析]因為2×40=80，則左孩子編號為80，沒有右孩子。31.參考答案：B[考點]元素的進棧操作[解析]元素的進棧操作。32.參考答案：A[考點]循環(huán)隊列數(shù)據(jù)元素個數(shù)的求取[解析](rear-front)%n。33.參考答案：

(0)初態(tài)

(1)d、e、b入隊

(2)d、e出隊

(3)i、j入隊

(4)b出隊

第5步操作無法進行，因為隊列已滿。34.參考答案：

voidleveltree(Treeroot)

{

InitQueueQ;

If(root)

EnQueue(Q,root);

while(!QueueEmpty(Q))

{

p=DeQueue(Q);

printf(p-＞data);

If(p-＞son)

EnQueue(Q,p-＞son);

r=p-＞brother;

while(r)

{

EnQueue(Q,p-＞brother);

r=r-＞brother;

}

}

}[考點]二叉樹的遍歷[解析]樹的層次遍歷，將結點入隊列，若隊列不空，則出隊列，訪問，并將son所指結點放入隊列，若其brother所指結點存在，則依次放入隊列中。循環(huán)判斷隊列是否為空，不空則重復上述過程。35.參考答案：n[考點]有環(huán)無向圖的特征[解析]n個頂點且含有環(huán)路的無向連通圖中，至少含有n條邊。36.參考答案：算法思想：先求左子樹的葉子數(shù)，再求右子樹的葉子數(shù)，兩者相加就是根結點的葉子數(shù)，也就是對應二叉樹的葉子數(shù)。具體算法如下：

intleafcount(BinTreeT)

{if(T=NULL)leaf=0;

elseif((T-＞lchild==NULL)&&(T-＞rchild==NULL))

leaf=1;

else{L=leafcount(T-＞lchild);

R=leafcount(T-＞rchild);

leaf=L+R;

}

return(leaf)

}37.參考答案：B[解析]本題主要考查的知識點是算法的易讀性。[要點透析]算法的易讀性是指易于閱讀、理解和交流，便于調試、修改和擴充。38.參考答案：計算量39.參考答案：鄰接表40.參考答案：D[考點]本題主要考查的知識點是歸并排序的存儲開銷。

歸并排序算法的時間復雜度為O(nlog2n)，由于要用到和待排記錄等數(shù)量的數(shù)組b來存放結果，所以實現(xiàn)歸并排序需要附加一倍的存儲開銷。41.參考答案：共有5種：

(1)push(A)，pop(A)，push(B)，pop(B)，push(C)，pop(C)輸出序列為：ABC

(2)push(A)，pop(A)，push(B)，push(C)，pop(C)，pop(B)輸出序列為：ACB

(3)push(A)，push(B)，pop(B)，pop(A)，push(C)，pop(C)輸出序列為：BAC

(4)push(A)，push(B)，pop(B)，push(C)，pop(C)，pop(A)輸出序列為：BCA

(5)push(A)，push(B)，push(C)，pop(C)，pop(B)，pop(A)輸出序列為：CBA[考點]棧的存取原則：后進先出42.參考答案：O(1)43.參考答案：C44.參考答案：745.參考答案：[24][12][22][34][5][44][76][61][100][3][1][120]

[12

2