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.在排序算法中，分析算法時(shí)間復(fù)雜度時(shí)，通常以______和______為標(biāo)準(zhǔn)操作。評(píng)價(jià)排序的另一個(gè)主要標(biāo)準(zhǔn)是執(zhí)行算法所需要的______。2.順序棧s中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進(jìn)棧操作的主要語句為

A.s.elem[top]=e;

s.top=s.top+1;B.s.elem[top+1]=e;

s.top=s.top+1;C.s.top=s.top+1;

s.elem[top+1]=e;D.s.top=s.top+1;

s.elem[top]=e;3.設(shè)圖G有n個(gè)頂點(diǎn)，采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，進(jìn)行深度優(yōu)先搜索的時(shí)間復(fù)雜度為______。4.設(shè)某帶頭結(jié)點(diǎn)的單鏈表的結(jié)點(diǎn)結(jié)構(gòu)說明如下：

typedefstructnodel

{

intdata;

structnodel*next;

}node;

試設(shè)計(jì)一個(gè)算法：voidcopy(node*head1,node*head2)，將以head1為頭指針的單鏈表復(fù)制到一個(gè)不帶有頭結(jié)點(diǎn)且以head2為頭指針的單鏈表中。5.有向圖G用鄰接矩陣A[1..n,1..n]存儲(chǔ)，其第i列的所有元素之和等于頂點(diǎn)vi的______。6.堆分為最小堆和最大堆，若鍵值序列{k1，k2，…，kn}，滿足，則這n個(gè)鍵值序列{k1，k2，…，kn}是______。7.線性表若采用鏈表存儲(chǔ)結(jié)構(gòu)，則要求內(nèi)存中可用存儲(chǔ)單元的地址______A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)不連續(xù)都可以8.一組記錄的鍵值為(46，74，18，53，14，20，40，38，86，65)，利用堆排序的方法建立的初始堆為______A.(14，18，38，46，65，40，20，53，86，74)B.(14，38，18，46，65，20，40，53，86，74)C.(14，18，20，38，40，46，53，65，74，86)D.(14，86，20，38，40，46，53，65，74，18)9.由______轉(zhuǎn)換成二叉樹時(shí)，其根結(jié)點(diǎn)的右子樹總是空的，其與二叉樹可相互轉(zhuǎn)換。10.畫出3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。11.所有的存儲(chǔ)結(jié)點(diǎn)存放在一個(gè)連續(xù)的存儲(chǔ)空間，該存儲(chǔ)方式是

存儲(chǔ)方式。A.順序B.鏈?zhǔn)紺.索引D.散列12.在雙鏈表中，前驅(qū)指針和后繼指針分別為prior和next。若使指針p往后移動(dòng)兩個(gè)結(jié)點(diǎn)，則需執(zhí)行語句______。13.下圖所示的無向圖中，從頂點(diǎn)1出發(fā)按照DFS規(guī)則遍歷得到的序列為______

A.ABCDEFHIGB.ABGEFCHDIC.ABGEFCHDID.ABEGCFDHI14.一個(gè)數(shù)組的第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素占2個(gè)存儲(chǔ)單元，則第5個(gè)元素的存儲(chǔ)地址是

A.110B.108C.100D.12015.設(shè)循環(huán)隊(duì)列的容量為40(序號(hào)從0～39)，現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)運(yùn)算后，有(1)front=11，rear=19；(2)front=19，rear=11；問這兩種情況下循環(huán)隊(duì)列中的元素各有幾個(gè)?16.堆排序算法的時(shí)間復(fù)雜度為______。17.一個(gè)棧的入棧序列是a、b、c、d、e，則棧的可能的輸出序列是______A.cdabeB.decbaC.cabdeD.dabec18.已知一棵含50個(gè)結(jié)點(diǎn)的二叉樹中只有一個(gè)葉子結(jié)點(diǎn)，則該樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為______A.0B.1C.48D.4919.寫出計(jì)算方陣A[n][n]與B[n][n]乘積C[n][n]的算法。20.一個(gè)有序表A含有15個(gè)數(shù)據(jù)元素，且第一個(gè)元素的下標(biāo)為1，按二分查找算法查找元素A[14]，所比較的元素下標(biāo)依次是______。21.在最好的情況下，對(duì)于具有n個(gè)元素的有序序列，若采用冒泡排序，所需的比較次數(shù)為______次。22.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷的結(jié)果為______。23.下面關(guān)于線性表的敘述，錯(cuò)誤的是

A.順序表是使用一維數(shù)組實(shí)現(xiàn)的線性表B.順序表必須占用一片連續(xù)的存儲(chǔ)單元C.順序表的空間利用率高于鏈表D.在鏈表中，每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域24.具有72個(gè)結(jié)點(diǎn)的完全二叉樹的深度為______。25.除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)的回路，稱為______。26.在一棵度為3的樹中，度為3的結(jié)點(diǎn)有4個(gè)，度為2的結(jié)點(diǎn)有2個(gè)，度為1的結(jié)點(diǎn)有3個(gè)，則度為0的結(jié)點(diǎn)有______A.8個(gè)B.10個(gè)C.11個(gè)D.12個(gè)27.假設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，問此類二叉樹中的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值和最小值各為多少?并說明是什么樣的二叉樹?28.試寫出一個(gè)有向圖的逆鄰接表的建立算法。29.通常從正確性、易讀性、______、時(shí)空性等四個(gè)方面評(píng)價(jià)算法的質(zhì)量。30.順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進(jìn)棧操作的主要語句為______A.s.elem[top]=e;

s.top=s.top+1;B.s.elem[top+1]=e;

s.top=s.top+1;C.s.top=s.top+1;

s.elem[top+1]=e;D.s.top=s.top+1;

s.elem[top]=e;31.下列排序方法中，屬于不穩(wěn)定的排序方法是______A.選擇排序B.冒泡排序法C.基數(shù)排序法D.直接插入排序法32.設(shè)樹T的度為4，其中度為1、2、3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2、1、1則T中的葉子數(shù)為______A.5B.6C.7D.833.給定表(19，14，22，01，66，21，83，27，56，13，10)。試按元素在表中的次序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹，畫出插入完成后的二叉排序樹。并求其在等概率情況下查找成功的平均查找長度。34.一個(gè)10×10階對(duì)稱矩陣A，采用行優(yōu)先順序壓縮存儲(chǔ)下三角矩陣，a00為第一個(gè)元素，其存儲(chǔ)地址為0，每個(gè)元素占用1個(gè)存儲(chǔ)單元，則a33的地址為______。35.在具有6個(gè)頂點(diǎn)的無向圖G至少應(yīng)有多少條邊才能確保是一個(gè)連通圖______A.8B.7C.6D.536.一個(gè)順序隊(duì)列的第5個(gè)元素的存儲(chǔ)地址是200，第10個(gè)元素的存儲(chǔ)地址是225。每個(gè)元素的長度是5，則第20個(gè)元素的地址是______。37.元素的進(jìn)棧次序?yàn)?，2，3，…，n，出棧的第一個(gè)元素是n，則第k個(gè)出棧的元素是______。38.具有10個(gè)頂點(diǎn)的無向圖的邊數(shù)最多為______A.11B.110C.45D.22039.以下程序段的時(shí)間復(fù)雜度為______。

for(i=0；i＜n；i++)

for(j=0；j＜m；j++)

A[i][j]=0；40.直接插入序列在最好情況下時(shí)間復(fù)雜度為

A.O(log2n)B.O(n)C.O(n*log2n)D.O(n2)41.若二叉樹(如下圖所示)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左右子樹的位置，最合適的遍歷方法是______

A.先序遍歷B.中序遍歷C.后序遍歷D.按層次遍歷42.隊(duì)列操作的原則是______。43.設(shè)線性表有n個(gè)元素，以下操作中，

在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。A.輸出第i(1≤i≤n)個(gè)元素值B.交換第1個(gè)元素與第2個(gè)元素的值C.在第i個(gè)元素前插入一個(gè)元素D.刪除第i個(gè)元素44.一組記錄的關(guān)鍵字為{45，80，55，40，42，85)，則利用堆排序的方法建立的初始堆為

A.80，45，55，40，42，85B.40，42，55，80，45，85C.40，42，45，55，80，85D.85，55，80，42，45，4045.快速排序是不穩(wěn)定的，在最壞情況下，其時(shí)間復(fù)雜度為______。46.三個(gè)頂點(diǎn)v1，v2，v3的圖的鄰接矩陣為則該圖中頂點(diǎn)v1的出度為______。47.在隊(duì)列中，新插入的結(jié)點(diǎn)只能添加到______，被刪除的只能是排在______的結(jié)點(diǎn)。48.假設(shè)線性表中結(jié)點(diǎn)是按鍵值遞增的順序排列，試寫一順序查找算法，將崗哨設(shè)在高下標(biāo)端。然后分別求出等概率情況下查找成功和不成功時(shí)的平均查找長度。49.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹______A.其形態(tài)不一定相同，平均查找長度也不一定相同B.其形態(tài)不一定相同，但平均查找長度相同C.其形態(tài)均相同，但平均查找長度不一定相同D.其形態(tài)均相同，平均查找長度也都相同50.在一個(gè)用一維數(shù)組A[N]表示的循環(huán)隊(duì)列中，該隊(duì)列中的元素個(gè)數(shù)最少為______個(gè)，最多為______個(gè)。第1卷參考答案一.歷年考點(diǎn)試題黑鉆版1.參考答案：鍵值比較

記錄移動(dòng)

附加空間[考點(diǎn)]排序算法中的時(shí)間復(fù)雜度[解析]在排序算法中，分析算法時(shí)間復(fù)雜度時(shí)，通常以鍵值比較和記錄移動(dòng)為標(biāo)準(zhǔn)操作。評(píng)價(jià)排序的另一個(gè)主要標(biāo)準(zhǔn)是執(zhí)行算法所需要的附加空間。2.參考答案：D3.參考答案：O(n2)4.參考答案：算法描述如下：

voidcopy(node*head1,node*head2)

{node*p,*q;

head2=(node*)malloc(sizeof(node))

q=head2;p=head1-＞next;

while(p!=NULL)

{

s=(node*)malloc(sizeof(node));

s-＞data=p-＞data;

q-＞next=s;

q=s;

p=p-＞next;

}

q-＞next=NULL;

p=head2;

head2=head2-＞next;

free(p);

}5.參考答案：入度6.參考答案：最大堆[考點(diǎn)]最大堆的定義[解析]最大堆的定義。7.參考答案：D[考點(diǎn)]本題主要考查的知識(shí)點(diǎn)是線性表。

[解析]由于線性表的順序存儲(chǔ)方式要求占用連續(xù)的空間，存儲(chǔ)分配只能預(yù)先進(jìn)行，為了克服順序表的缺點(diǎn)，采用鏈接方式存儲(chǔ)線性表。8.參考答案：B9.參考答案：樹[考點(diǎn)]樹與二叉樹的轉(zhuǎn)換[解析]由樹轉(zhuǎn)換成二叉樹時(shí)，其根結(jié)點(diǎn)的右子樹總是空的。10.參考答案：含有3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)：

11.參考答案：A[解析]本題主要考查的知識(shí)點(diǎn)是順序存儲(chǔ)方式。[要點(diǎn)透析]順序存儲(chǔ)方式是指所有存儲(chǔ)結(jié)點(diǎn)存放在一個(gè)連續(xù)的存儲(chǔ)區(qū)里。利用結(jié)點(diǎn)在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。12.參考答案：p=p-＞next-＞next[考點(diǎn)]在雙鏈表中刪除結(jié)點(diǎn)需要執(zhí)行的語句[解析]若使指針p往后移動(dòng)兩個(gè)結(jié)點(diǎn)，則需執(zhí)行語句p=p-＞next-＞next。13.參考答案：D[考點(diǎn)]圖的深度優(yōu)先搜索[解析]根據(jù)DFS規(guī)則可知，其深度優(yōu)先遍歷序列如下圖所示：

故本題答案為D。14.參考答案：B15.參考答案：(1)(rear-front+max)%max=(19-11+40)%40=8

(2)(rear-front+max)%max=(11-19+40)%40=32[考點(diǎn)]循環(huán)隊(duì)列的存取規(guī)則16.參考答案：O(nlog2n)[考點(diǎn)]堆排序算法的時(shí)間復(fù)雜度[解析]堆排序算法的時(shí)間復(fù)雜度為O(nlog2n)。17.參考答案：B[考點(diǎn)]棧的存取原則[解析]棧的存取原則是后進(jìn)先出，A選項(xiàng)中cd先出棧，說明ab已入棧且尚未出棧，a不可能先于b出棧，C、D選項(xiàng)中a不可能先于b出棧，故選B。18.參考答案：D[考點(diǎn)]本題主要考查的知識(shí)點(diǎn)是二叉樹的性質(zhì)。

根據(jù)二叉樹性質(zhì)：在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1?？傻胣2=n0-1=0，n1=50-n0-n2=49。19.參考答案：voidmatrixmultiply(intA[][n],intB[][n],intC[][n],intn)

//求n階方陣A與B的乘積C

{inti,j;

for(i=0;i＜n;i++)

for(j=0,j＜n;j++)

{c[i][j]=0;

for(k=0;k＜n;k++)

C[i][j]+=A[i][k]×B[k][j];

}

}20.參考答案：8、12、14[考點(diǎn)]二分查找算法[解析]所比較元素下標(biāo)依次為：(15+1)/2=8；(9+15)/2=12；(13+15)/2=14。21.參考答案：n-1[考點(diǎn)]冒泡排序的最好情況下的比較次數(shù)[解析]冒泡排序的最好情況下的比較次數(shù)是僅進(jìn)行一趟排序，所以要比較n-1次。22.參考答案：CBEFDA23.參考答案：D[解析]本題主要考查的知識(shí)點(diǎn)是線性表。[要點(diǎn)透析]順序表是用一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)組的下標(biāo)可看成元素的相對(duì)地址，它們是邏輯上相鄰的元素，存儲(chǔ)在物理位置也相鄰的單元中。在鏈表中，單鏈表中每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域，而雙鏈表中的結(jié)點(diǎn)有prior和next兩個(gè)鏈域。24.參考答案：7[考點(diǎn)]本題主要考查的知道點(diǎn)是完全二叉樹的深度[解析]n個(gè)結(jié)點(diǎn)的完全二叉樹的深度=(log272)+1=7。25.參考答案：簡單回路或簡單環(huán)[考點(diǎn)]簡單回路或簡單環(huán)定義[解析]除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)的回路，稱為簡單回路或簡單環(huán)。26.參考答案：C[考點(diǎn)]樹的特點(diǎn)[解析]樹中度的總和為19，即為樹中邊的總數(shù)，結(jié)點(diǎn)總數(shù)為邊個(gè)總和+1，即20，再減去4個(gè)度為3的，2個(gè)度為2的，3個(gè)度為1的結(jié)點(diǎn)，即度為0的結(jié)點(diǎn)個(gè)數(shù)為11。27.參考答案：結(jié)點(diǎn)數(shù)的最大值為2h-1，最小值為2h-1(第一層根結(jié)點(diǎn)，其余每層均兩個(gè)結(jié)點(diǎn)且互為兄弟)。

結(jié)點(diǎn)最多時(shí)為滿二叉樹。

h=5時(shí)最小值的情況之一：

結(jié)點(diǎn)最少時(shí)是類似于上圖的二叉樹。28.參考答案：算法如下：

Create_Inverse_Adjlist(GraphTp*ga)

{intn,e,i,j,k;

ArcNodeTp*p;

scanf("%d%d",&n,&e);//讀入頂點(diǎn)數(shù)和邊數(shù)

ga-＞vexnum=n;ga-＞arcnum=e;

for(i=0;i＜n;i++)

{ga-＞adjlis[i].vertex=i;//初始化逆鄰接表

a-＞adjlis[i].firstarc=NULL;

}

for(k=0;k＜e;k++)

{scanf("%d%d",&i,&j);//讀入?。糹,j＞

p={ArcNodeTp*}malloc(sizeof(ArcNodeTp));

p-＞adjvex=i;

p-＞nextarc=ga-＞adjlis[j].firstarc;

ga-＞adjlis[j].firstarc=p;

}

}[考點(diǎn)]有向圖的鄰接表的建立29.參考答案：健壯性30.參考答案：D[考點(diǎn)]棧的存取時(shí)指針的修改[解析]棧的存取時(shí)指針的修改。31.參考答案：A[考點(diǎn)]排序算法的穩(wěn)定性[解析](1)穩(wěn)定的排序：冒泡排序；直接插入排序；歸并排序；基數(shù)排序。

(2)不穩(wěn)定的排序：希爾排序；選擇排序；快速排序；堆排序。32.參考答案：D[考點(diǎn)]本題主要考查的知識(shí)點(diǎn)是樹中的葉子數(shù)。

由樹的性質(zhì)可知，任意一棵樹的結(jié)點(diǎn)總數(shù)等于所有結(jié)點(diǎn)的出度之和加1?？汕蟮么藰涞某龆戎蜑椋?*4+2*2+3*1+4*1=15。設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為x，可得x+4+2+1+1=15+1，求得x=8。33.參考答案：所求二叉排序樹如下圖所示：

平均查找長度ASL=(1+2×2+3×3十3×4+2×5)/11=36/11。34.參考答案：935.參考答案：D36.參考答案：27537.參考答案：n-k+1[考點(diǎn)]出棧操作[解析]出棧第一個(gè)是n，第二個(gè)是n-1……第k個(gè)是n-k+1。n\k為斜體。38.參考答案：C[考點(diǎn)]無向圖邊的個(gè)數(shù)[解析]具有n個(gè)頂點(diǎn)的無向圖的邊數(shù)最多為n(n-1)/2。39.參考答案：O(n*m)40.參考答案：B41.參考答