2023年自考類計算機類(工學(xué)類)數(shù)據(jù)結(jié)構(gòu)2010-2022歷年真題選編帶答案難題含解析

2023年自考類計算機類(工學(xué)類)數(shù)據(jù)結(jié)構(gòu)2010-2022歷年真題選編帶答案難題含解析（圖片大小可自由調(diào)整）第1卷一.歷年考點試題黑鉆版(共75題)1.對關(guān)鍵字序列(56,23,78,92,88,67,19,34)進行增量為3的一趟希爾排序的結(jié)果為

A.(19,23,56,34,78,67,88,92)B.(23,56,78,66,88,92,19,34)C.(19,23,34,56,67,78,88,92)D.(19,23,67,56,34,78,92,88)2.稀疏矩陣一般的壓縮存儲方法有2種，它們分別是______和______。3.在單鏈表中，刪除p所指結(jié)點的直接后繼的操作是

A.p—＞next=p—＞next—＞next;B.p=p—＞next;p—＞next=p—＞next—＞next;C.p—＞next=p—＞next;D.p=p—＞next—＞next;4.考慮下列四種排序方法，在排序過程中，關(guān)鍵碼比較的次數(shù)與記錄的初始排列順序無關(guān)的是

A.直接插入排序和快速排序B.快速排序和歸并排序C.直接選擇排序和歸并排序D.直接插入排序和歸并排序5.下面的查找方式中，可以對無序表進行查找的是

A.順序查找B.二分查找C.二叉排序樹D.B-樹上的查找6.假定一棵二叉樹的結(jié)點為18個，則此二叉樹的最大高度為

，最小高度為

A.4B.5C.6D.187.簡述一下算法的功能：

status

A

(1inkedlist

L)

{//L是無表頭結(jié)點的單鏈表

if

(L&&L—＞next)

{Q=L;L=L—＞next;P=L;

while(P—＞next)P=P—＞next;

P—＞next=Q;Q—＞next=NULL;

}

returnok;

)//A8.如果以鏈表作為棧的存儲結(jié)構(gòu)，則退棧操作時

A.必須判別棧是否滿B.判別棧元素的類型C.必須判別棧是否空D.對棧不作任何判別9.鄰接表存儲結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法結(jié)構(gòu)類似于于叉樹的

A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷10.下面程序段的時間復(fù)雜度為

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

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

A[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)11.什么是數(shù)據(jù)的邏輯結(jié)構(gòu)?什么是數(shù)據(jù)的物理結(jié)構(gòu)?12.已知廣義表A=((a,b,c)，(d,e,f))，則運算head(head(tail(tail(A))))=______。13.對于數(shù)組，通常具有的基本操作有______種，它們分別是______。14.有向完全圖有______條邊。(其中圖有n個結(jié)點)15.對于一個具有N個結(jié)點和E條邊的無向圖，若采用鄰接表示，則表頭向量的大小是

A.NB.N+1C.N-ED.N-116.ISAM文件采用______索引結(jié)構(gòu)，而VSAM文件采用______索引結(jié)構(gòu)。17.一個字符串相等的充要條件是______和______。18.一般來說，數(shù)組中的元素具有______的數(shù)據(jù)類型，并且數(shù)組元素的下標的上界和下界都是______的。19.如果在數(shù)據(jù)結(jié)構(gòu)中每個數(shù)據(jù)元素只可能有一個直接前驅(qū)，但可以有多個直接后繼，則該結(jié)構(gòu)是

A.棧B.隊列C.樹D.圖20.棧中有a、b和c三個元素，a是棧底元素，c是棧頂元素，元素d等待進棧，則不可能的出棧序列是______A.dcbaB.cbdaC.cadbD.cdba21.在長度為n的順序表的第i(1≤i≤n)個元素之后插入一個元素時，需向后移動______個元素。22.樹的孩子兄弟表示法又稱為二叉鏈表表示法，請畫出下圖樹T的二叉鏈表。

23.排序的重要目的是為了以后對已排序的數(shù)據(jù)元素進行

A.打印輸出B.分類C.查找D.合并24.二叉樹的存儲結(jié)構(gòu)類型定義如下：

typedefstructnode{

intdata;

structnode*lchild,*rchild;

}BinNode;typedefBinNode*BinTree;編寫遞歸算法，求只有一個孩子結(jié)點的結(jié)點總數(shù)，并計算這些結(jié)點的數(shù)據(jù)值的和。

函數(shù)的原型為：voidf34(BinTreeT,int*count,int*sum)

*count和*sum的初值為0。25.設(shè)二維數(shù)組A[10··20,5··10]按行優(yōu)先存儲·，每個元素占4個存儲單元，A[10,5]的存儲地址是1000，則A[15,10]的存儲地址是______。26.使用二叉線索樹的目的是便于______A.二叉樹中結(jié)點的插入與刪除B.在二叉樹中查找雙親C.確定二叉樹的高度D.查找一個結(jié)點的前驅(qū)和后繼27.棧下溢是指在______時進行出棧操作。28.帶有一個頭結(jié)點的單鏈表head為空的條件是______。29.在對n個關(guān)鍵字進行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元素，則在進行第i趟排序之前，無序區(qū)中關(guān)鍵字元素的個數(shù)為

A.iB.i+1C.n-iD.n-i+130.若序列中關(guān)鍵字相同的記錄在排序前后的相對次序不變，則稱該排序算法是______的。31.在一個長度為n的順序表(順序存儲的線性表)中，向第i個元素(1≤i≤n+1)之前插入一個新元素時，需向后移動

個元素。A.n-iB.n-i+1C.n-i-1D.i32.稱算法的時間復(fù)雜度為O(f(n))，其含義是指算法的執(zhí)行時間和______的數(shù)量級相同。33.請根據(jù)下面所給出的鄰接矩陣畫出相應(yīng)的有向圖或者是無向圖(頂點vi表示)。

34.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有

條邊才能確保是一個連通圖。A.5B.6C.7D.835.如果要求一個線性表適應(yīng)動態(tài)變化的要求，又必須能盡快地進行查找，則可以選擇采用

查找方法。A.分塊B.二分C.順序D.散列36.線性表若采用鏈表存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址

A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)不連續(xù)都可以37.畫出下圖所示樹的孩子鏈表。

38.N個頂點的連通圖，至少有______條邊。39.在有向圖中，以頂點V為終點的邊的數(shù)目稱為V的______。40.在一個按行優(yōu)先順序存儲的二維數(shù)組(M×N)中，假設(shè)數(shù)組的基地址是P，并且數(shù)組的每一個元素所占的存儲空間為d個字節(jié)，則a[ij的地址計算公式為______。41.設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點，則這類二叉樹上所含結(jié)點總數(shù)量少

個。A.k+1B.2kC.2k-1D.2k+142.對于三個函數(shù)f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008和h(n)=8888nlogn+3n2，下列陳述中不成立的是

A.f(n)是O(g(n))B.g(n)是O(f(n))C.h(n)是O(nlogn)D.h(n)是O(n2)43.已知：

typedefstructnode{

intdata;

structnode*next;

}LinkNode;

typedefLinkNode*LinkList;

請編寫原型為intListisequal(LinkListA,LinkListB)的函數(shù)，指針A、B分別指向兩個帶頭結(jié)點的單鏈表。函數(shù)功能是：若單鏈表A、B中全部對應(yīng)結(jié)點的data值相等，則返回1，否則返回0。44.對于一個具有n條邊和e個頂點的圖來說，如果采用鄰接表表示，則其空間復(fù)雜度為______，若采用鄰接矩陣表示，則其空間復(fù)雜度為______。45.帶行表的三元組表是稀疏矩陣的一種

A.順序存儲結(jié)構(gòu)B.鏈式存儲結(jié)構(gòu)C.索引存儲結(jié)構(gòu)D.散列存儲結(jié)構(gòu)46.一組字符(a，b，c，d)在文中出現(xiàn)的次數(shù)分別為(7，6，3，5)，字符'd'的哈夫曼編碼的長度為______。47.ISAM文件采用______索引結(jié)構(gòu)，而VSAM文件采用______索引結(jié)構(gòu)。48.基于三元組的稀疏矩陣轉(zhuǎn)置的處理方法有兩種，以下運算按照矩陣A的列序來進行轉(zhuǎn)置，請在______處用適當?shù)恼Z句予以填充。

Trans_Sparmat(SpMatrixTpa,SpMatrixTp*b)

{(*b).mum=a.nu;(*b).nu=a.mu;(*b).tu=a.tu

if(a.tu)

{

q=1;

for(col=1;______;col++)

for(p=1;p＜=a.tu;p++)

if(______)==col)

{(*b).data[q].i=a.data[p].j;

(*b).data[q].j=a.data[p].i;

(*b).data[q].v=a.data[p].v;

______;

}

}

}49.一個n×n的對稱矩陣，如果以行為主序或以列為主序存入內(nèi)存，則其容量為______。50.給定一個序列a，b，c，當其按此順序進?；蛉腙牶?，其出棧和出隊序列分別是什么?51.以下運算實現(xiàn)在順序棧上的退棧，請在______處用適當?shù)恼Z句予以填充。

intPop(SqStackTp*sq,DataType*x)

{if(sq—＞top==0){error("下溢");return(0);)

else{*x=______;

______;

return(1);

}

}52.在下圖中，從頂點V1出發(fā)，按廣度優(yōu)選遍歷圖的頂點序列是

A．V1

V5

V3

V4

V2

V6

V7

B．V1

V5

V3

V4

V2

V7

V6

C．V1

V7

V2

V6

V4

V5

V3

D．V1

V2

V4

V7

V6

V5

V3

53.二叉排序樹的類型定義如下：

typedefstruetBSTNode{//二叉排序樹的結(jié)點結(jié)構(gòu)

intdata;//數(shù)據(jù)域

structBSTNode*lchild,*rchild;//左、右孩子指針

}BSTNode,*BSTree;

設(shè)計遞歸算法，統(tǒng)計一棵二叉排序樹T中值小于a的結(jié)點個數(shù)。54.簡述一下算法的功能：

status

A

(1inkedlist

L)

{//L是無表頭結(jié)點的單鏈表

if

(L&&L—＞next)

{Q=L;L=L—＞next;P=L;

while(P—＞next)P=P—＞next;

P—＞next=Q;Q—＞next=NULL;

}

returnok;

)//A55.判斷一個沒有頭結(jié)點的單鏈表head為空的條件是______。56.在下列排序算法中，關(guān)鍵字比較次數(shù)與初始排列次序無關(guān)的是______A.冒泡排序B.希爾排序C.直接插入排序D.直接選擇排序57.已知一棵哈夫曼樹含有60個葉子結(jié)點，則該樹中共有______個非葉子結(jié)點。58.已知一組待排記錄的關(guān)鍵字序列為(15，11，17，59，14，35，13，17，24，84)，請給出對應(yīng)的小根堆序列。59.寫出向某個有序文件中插入一個記錄的程序。60.拓撲排序指的是找一個有向圖的______的過程。61.對快速排序來講，其最好情況下的時間復(fù)雜度是______，其最壞情況下的時間復(fù)雜度是______。62.表頭和表尾均為空表的廣義表是

A.()B.(())C.((()))D.(()，())63.適宜進行批量處理的文件類型是

A.順序文件B.索引順序文件C.散列文件D.多關(guān)鍵字文件64.假設(shè)有一個容量為5的隊列，假設(shè)其初始狀態(tài)為front=rear=0，則對此隊列進行下列操作之后，請畫出此時的頭、尾指針的變化情況和相應(yīng)的隊列內(nèi)元素的存儲情況。

(1)隊列為空(即沒有任何元素進入)；

(2)A，B，C入隊；

(3)A出隊；

(4)B，C出隊，此時隊列為空。65.含n個頂點的無向連通圖中至少含有______條邊。66.非空的循環(huán)單鏈表head的尾結(jié)點(由指針p所指)滿足

A.p—＞next=NULLB.p=NULLC.p—＞next=headD.p=head67.以下算法在指針T所指的二叉排序樹上的查找鍵值等于K的結(jié)點。成功時回送指向該結(jié)點的指針；否則回送空指針。請分析程序，并在______上填充合適的語句。

bitreptrsearch_bst(bitreptrT,keytypeK)

{if(T==NULL)return(NULL);

elseswitch

{caseT—＞key==K:______;

case______:return(search_bst(T—＞lchild,K));

case______:return(search_bst(T—＞rchild,K));

}

}68.設(shè)計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用

數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲結(jié)構(gòu)B.棧C.隊列D.線性表的鏈式存儲結(jié)構(gòu)69.假設(shè)以列優(yōu)先順序存儲二維數(shù)組A[5][8]，其中元素A[0][0]的存儲地址為LOC(a00)，且每個元素占4個存儲單元，則數(shù)組元素A[i][j]的存儲地址為______。70.二維數(shù)組M[i,j]的元素是4個字符(每個字符占一個存儲單元)組成的串，行下標i的范圍從0到4，列下標j的范圍從0到5。M按行存儲時元素M[3,5]的起始地址與M按列存儲時元素

的起始地址相同。A.M[2,4]B.M[3,4]C.M[3,5]D.M[4,4]71.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹

A.其形態(tài)不一定相同，但平均查找長度相同B.其形態(tài)不一定相同，平均查找長度也不一定相同C.其形態(tài)均相同，但平均查找長度不一定相同D.其形態(tài)均相同，平均查找長度也都相同72.采用單鏈表作為存儲結(jié)構(gòu)，試編寫一個函數(shù)來實現(xiàn)用選擇排序方法進行升序排列。73.嚴格地講，二維數(shù)組不是一種線性表，但數(shù)組可以看成是線性表在下述含義上的擴展：二維數(shù)組的數(shù)據(jù)元素是______的線性表。74.廣義表的深度是指______。75.對于棧頂指針為top的順序棧S，判斷?？盏臈l件是______A.S.top=0B.S.top＜0C.S.top=StackSize-1D.S.top=StackSize第1卷參考答案一.歷年考點試題黑鉆版1.參考答案：D2.參考答案：三元組十字鏈表3.參考答案：A4.參考答案：C5.參考答案：A6.參考答案：B7.參考答案：本程序?qū)崿F(xiàn)的功能就是：如果L的長度不小于2，則將首元結(jié)點刪去并插入到表尾。8.參考答案：C9.參考答案：A10.參考答案：C[解析]此程序的時間復(fù)雜度即為程序中循環(huán)次數(shù)的時間耗費。由程序為嵌套循環(huán)，外層循環(huán)的時間復(fù)雜度T(n1)=m，內(nèi)層循環(huán)的時間復(fù)雜度T(n2)=n，則此程序的時間復(fù)雜度T(n)=m*n，即為0(m*n)。11.參考答案：數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)的，它與數(shù)據(jù)元素的存儲結(jié)構(gòu)無關(guān)，是獨立于計算機的。數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)在計算機中的實際存儲形式。[考點]數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的概念12.參考答案：e13.參考答案：兩

查找和修改14.參考答案：n(n-1)[考點]有向完全圖的邊數(shù)

[解析]有向完全圖的邊數(shù)共有n(n-1)條。15.參考答案：A16.參考答案：靜態(tài)

動態(tài)17.參考答案：兩個字符串的長度相等

對應(yīng)位置的字符相等18.參考答案：統(tǒng)一

固定19.參考答案：C[解析]在樹中，除了根結(jié)點和葉子結(jié)點外，其余結(jié)點都僅有一個直接前驅(qū)而且有一個或多個直接后繼。而根結(jié)點沒有直接前驅(qū)但有一個或多個直接后繼，葉子結(jié)點有一個直接前驅(qū)卻沒有直接后繼。20.參考答案：C[考點]棧的操作

[解析]根據(jù)棧的操作原則，不可能的出棧序列是cadb。21.參考答案：n-i[考點]順序表中元素的插入問題

[解析]在長度為n的順序表的第i(1≤i≤n)個元素之后插入一個元素時，需向后移動n-i個元素。22.參考答案：根據(jù)樹與二叉鏈表的對應(yīng)關(guān)系，樹T的二叉鏈表如下圖所示。

[考點]樹的二叉鏈表表示

[解析]二叉鏈表中每個結(jié)點包含兩個指針域：第一個孩子結(jié)點和下一個兄弟結(jié)點，根據(jù)此原則，樹T的二叉鏈表如上圖所示。23.參考答案：C24.參考答案：voidf34(BinTreeT,int*count,int*sum)

{

if(T)

{if((T-＞lchild&&(!T-＞rchild))||((!T-＞lchild)&&T-＞rchild))

{(*count)++;

*sum+=T-＞data;

}

f34(T-＞lchild,count,sum);

f34(T-＞rchild,count,sum);

}

}[考點]求只有一個孩子結(jié)點的結(jié)點總數(shù)，并計算這些結(jié)點的數(shù)據(jù)值的和的算法25.參考答案：170026.參考答案：D[考點]二叉線索樹的使用目的

[解析]二叉線索樹的使用目的是便于查找一個結(jié)點的前趨和后繼。27.參考答案：?？?8.參考答案：Jaead—＞next=NULL29.參考答案：D30.參考答案：穩(wěn)定31.參考答案：B32.參考答案：f(n)33.參考答案：答：A，B，C對應(yīng)的圖分別為：

34.參考答案：A35.參考答案：A36.參考答案：D37.參考答案：該樹的孩子鏈表為：

[考點]樹的孩子鏈表表示法38.參考答案：N—139.參考答案：入度40.參考答案：LOC(a[ij)=P+[i×N+j]×d41.參考答案：C42.參考答案：C[解析]當n充分大時，由題意可得：f(n)與n3是同階的，g(n)與n3是同階的，h(n)與n2是同階的。所以f(n)=O(g(n))，g(n)=O(f(n))，h(n)=O(n2)。43.參考答案：intListisequal(LinkListA，LinkListB){

LinkNode*p,*q;

p=A;q=B;

while(p!=null){

if(p-＞data!=q-＞data)return0;

p=p-＞next;

q=q-＞next;

}

return1;[考點]單鏈表操作

[解析]首先定義兩個指針p，q分別指向單鏈表A，B，然后通過p，q依次后移比較當前指向的元素是否相等，一旦出現(xiàn)不相等則返回0，如果比較到最后都相等則返回1。44.參考答案：O(n+c)

O(n2)45.參考答案：A46.參考答案：2[考點]哈夫曼編碼

[解析]先構(gòu)造出相應(yīng)的哈夫曼樹，然后進行編碼。47.參考答案：靜態(tài)

動態(tài)48.參考答案：col＜=a.nua.data[p].jq++49.參考答案：n×(n+1)/250.參考答案：出棧序列為c，b，a，出隊序列為a，b，c。[考點]棧和隊列的操作

[解析]棧的操作原則是先進后出，所以其輸出序列為c，b，a；隊列的操作原則是先進先出，所以其出隊序列為a，b，c。51.參考答案：sq—＞data[sq—＞top]

sq—＞top--52.參考答案：A53.參考答案：(P71)參考答案之一：

voidcount(BSTreeT,inta,int*sum){

//以sum所指單元統(tǒng)計二叉排序樹中元素值小于a的結(jié)點個數(shù)，其初值為0

if(T){

count(T—＞lchild,a,sum);

if(T—＞data<a){

(*sum)++;

count(T—＞rchild,a,sum);

}

}

}

參考答案之二：

intcount(BSTreeT,inta){

//統(tǒng)計二又排序樹中元素值小于a的結(jié)點個數(shù)

intsum;

if(!T)return0;

else{

sum=count(T—＞lchild,a);

if(T—＞data＜a)

returnsum+1+count(T—＞rchild,a);

elsereturnsum;

}

}54.參考答案：本程序?qū)崿F(xiàn)的功能就是：如果L的長度不小于2，則將首元結(jié)點刪去并插入到表尾。55.參考答案：hcad=NULL56.參考答案：D[考點]內(nèi)部排序方法的分析比較

[解析]關(guān)鍵字比較次數(shù)與記錄的初始順序無關(guān)的排序方法是選擇排序。

(1)若待排序的一組記錄數(shù)目n較小(如n≤50)時，可采用插入排序或選擇排序。

(2)若n較大時，則應(yīng)用采用快速排序、堆排序或歸并排序。

(3)基待排序記錄按關(guān)鍵字基本有序時，則適宜選用直接插入排序或冒泡排序。

(4)當n很大，而且關(guān)鍵字位數(shù)較少時，采用鏈式基數(shù)排序較好。

(5)關(guān)鍵字比較次數(shù)與記錄的初始排列順序無關(guān)的排序方法是選擇排序。57.參考答案：5958.參考答案：11，14，13，17，15，35，17，59，24，84[考點]堆排序59.參考答案：所謂有序文件是指文件的記錄按關(guān)鍵字由小到大(或由大到小)順序存放。為方便起見，可設(shè)文件的每一個記錄是一個整數(shù)，文件上數(shù)據(jù)是按由小到大順序存放。設(shè)插入數(shù)據(jù)是命令行的第3個參數(shù)，且設(shè)為d。若原文件中沒有數(shù)據(jù)，則d寫入文件；若有數(shù)據(jù)，則找到第1個比d大的數(shù)據(jù)i，先寫入d，再將i和其后各數(shù)據(jù)寫回文件中，可通過調(diào)用fseek函數(shù)采實現(xiàn)插入。相應(yīng)程序為：

#include＜stdio.h＞

#include＜stdlib.h＞

#include＜io.h＞

#include＜fcntl.h＞

#defineLENsizeof(int)

voidmain(intargi,char**argc)

{intfp,i,d;

if(argi＜3)

{printf("filenameint\11")

exit(0);

}

d=atoi(argc[2]);

fp=open(argc[1],O_GREAT|O_RDWRIO_BINARY,s_IREAD|S_IWRITE);

while(1)

{if(read(fp,&I,LEN)!=LEN)

{write(fp，&d,LEN):

/*文件結(jié)束，d添加到文件尾端*/

break;)

if(i＞=d)

/*文件中讀出數(shù)據(jù)i，若i＞=d，則先存d*/

{do

{fseek(fp,-1L*lan,SEEK_CUR);

/*文件指針后退1個記錄*/

write(fp,&d,LEN);

/*d寫到文件中*/

d=i;

/*原i作d，以便處理其他數(shù)據(jù)*/

}while(read(fp,&i,LEN)==LEN);

write(fp，&d,LEN);/*繼續(xù)讀數(shù)據(jù)，并判別文件是否結(jié)束*/

break;

}

}

close(fp);

}

/*main*/60.參考答案：拓撲序列61.參考答案：O(nlog2n)