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

2023年自考類計算機(jī)類(工學(xué)類)數(shù)據(jù)結(jié)構(gòu)歷年高頻考題帶答案難題附詳解（圖片大小可自由調(diào)整）第1卷一.歷年考點試題黑鉆版(共50題)1.以下將ah，…am，和am+1…an，兩個有序序列(它們相應(yīng)的關(guān)鍵字值滿足Kh≤Km，Km+1≤…Kn，)合并成一個有序序列Rh，…，Rn，(使其關(guān)鍵字值滿足Kh，'≤…≤Kn，')。請分析算法，并在______上填充適當(dāng)?shù)恼Z句。

voidmerge(lista,listR,inth,intm,intn)

{i=h;k=h;j=m+1;

while((i＜m)&&(j＜=n))

{if(a[i].key<=a[i].key){R[k]=______;______;}

else{R[k]=______;______;}

k++;

}

while(i＜=______){R[k]=a[i];i++;k++;)

while(j＜=______){R[k]=a[j];j++;k++;}

}

此算法的執(zhí)行時間為______。2.對于一個具有N個頂點的圖，如果我們采用鄰接矩陣法表示，則此矩陣的維數(shù)應(yīng)該是

A.(N-1)×(N-1)B.N×NC.(N+1)×(N+1)D.不確定3.多維數(shù)組和廣義表是一種非常復(fù)雜的非線性結(jié)構(gòu)，它們的邏輯特點是______。4.寫出向某個有序文件中插入一個記錄的程序。5.在一個長度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點的時間復(fù)雜度為______。6.若對關(guān)鍵字序列(43,02,80,48,26,57,15,73,21,24,66)進(jìn)行一趟增量為3的希爾排序，則得到的結(jié)果為______。7.廣義表的深度是指______。8.假設(shè)有一個容量為5的隊列，假設(shè)其初始狀態(tài)為front=rear=0，則對此隊列進(jìn)行下列操作之后，請畫出此時的頭、尾指針的變化情況和相應(yīng)的隊列內(nèi)元素的存儲情況。

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

(2)A，B，C入隊；

(3)A出隊；

(4)B，C出隊，此時隊列為空。9.假設(shè)以帶頭結(jié)點的單鏈表表示有序表，單鏈表的類型定義如下：

typedefstructnode{

DataTypedata;

structnode*next

}LinkNode,*LinkList;

編寫算法，從有序表A中刪除所有和有序表B中元素相同的結(jié)點。10.在下面的程序中，語句S的執(zhí)行次數(shù)為

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

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

{S;

}

11.一棵樹中非葉子結(jié)點的個數(shù)為n，與樹對應(yīng)的二叉樹中右子樹為空的結(jié)點的個數(shù)為m，則m=______。12.判斷一個有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒?，還可以利用

A.求關(guān)鍵路徑的方法B.求最短路徑的Dijkstra方法C.廣度優(yōu)先遍歷方法D.深度優(yōu)先遍歷方法13.若序列中關(guān)鍵字相同的記錄在排序前后的相對次序不變，則稱該排序算法是______的。14.以下算法在有序表R中用二分查找法查找鍵值等于K的元素，請分析程序，并在______上填充合適的語句。

intbinsearch(sqtableR,keytypeK)

{low=l;hig=R.n;/*置查找區(qū)間初值。low，hig分別標(biāo)記查找區(qū)間的下、上界*/

while(low＜=hig)

{mid=(low+hig)/2;

switch

{caseK==R.item[i].key:return(mid);

/*找到，返回位置mid*/

caseK＜R.item[i].key:______.break;/*縮小區(qū)間*/

caseK＞R.item[i].key:______;break/*縮小區(qū)間*/

}

}

return(0);

/*若區(qū)間長度已為0但仍不成功，則返回0，表示查找不成功*/

}15.在長度為32的有序表中進(jìn)行二分查找時，所需進(jìn)行的關(guān)鍵字比較次數(shù)最多為

A.4B.5C.6D.716.對于如下一個有序的關(guān)鍵字序列{5,9,12,18,23,31,37,46,59,66,71,78,85)，現(xiàn)在要求用二分法進(jìn)行查找值為18的關(guān)鍵字，則經(jīng)過幾次比較之后能查找成功?17.數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的______結(jié)構(gòu)。18.產(chǎn)生沖突現(xiàn)象的兩個關(guān)鍵字稱為該散列函數(shù)的______。19.若序列中關(guān)鍵字相同的記錄在排序前后的相對次序不變，則稱該排序算法是______的。20.就文件而言，按用戶的觀點所確定的基本存儲單元稱為______。按外設(shè)的觀點所確定的基本存儲單元稱為______。21.在循環(huán)雙鏈表的p所指結(jié)點之后插入s所指結(jié)點的操作是

A.P—＞next=s；B.p—＞next=s；

s—＞prior=p；

p—＞next—＞prior=s；

p—＞next—＞prior=s；

s—＞prior=p；

s—＞next=p—＞next；

s—＞next=p—＞nextC.s—＞prior=p；D.s—＞prior=p；

s—＞next=p—＞next；

s—＞next=p—＞next；

p—＞next=s；

p—＞next—＞prior=s；

p—＞next—＞prior=s；

p—＞next=s；22.在一般情況下用直接插入排序、選擇排序和冒泡排序的過程中，所需記錄交換次數(shù)最少的是______。23.非空的單循環(huán)鏈表L的尾結(jié)點P↑，滿足

A.P↑.next=NULL;B.P=NULL;C.P↑.next=L;D.P=L24.已知圖G的鄰接表如下圖所示。

從頂點v1出發(fā)進(jìn)行深度優(yōu)先搜索，得到的深度優(yōu)先搜索序列是______。25.在按照順序存儲方式存儲的數(shù)組中，元素aij的存儲地址應(yīng)該是數(shù)組的______加上排在aij前面的元素所占用的單元數(shù)。26.對序列(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)27.對于如圖所示的二叉樹，請畫出其順序存儲結(jié)構(gòu)圖。

28.假設(shè)Q是一個具有11個元素存儲空間的循環(huán)隊列(隊尾指針指向隊尾元素的下一個位置，隊頭指針指向隊頭元素)，初始狀態(tài)Q.front=Q.rear=0；寫出依次執(zhí)行下列操作后頭、尾指針的當(dāng)前值。

a，b，c，d，e，f入隊，a，b，c，d出隊；(1)Q.front=______；Q.rear=______。

g，h，i，j，k，1入隊，e，f，g，h出隊；(2)Q.front=______；Q.rear=______。

M，n，o，P入隊，i，j，k，l，m出隊；(3)Q.front=______；Q.rear=______。29.設(shè)帶頭結(jié)點的單循環(huán)鏈表的頭指針為head，指針變量P指向尾結(jié)點的條件是______A.p-＞next-＞next==headB.p-＞next==headC.p-＞next-＞next==NULLD.p-＞next==NULL30.如果二叉樹中任何一個結(jié)點的值都小于它的左子樹上所有結(jié)點的值而大于右子樹上所有結(jié)點的值，要得到各結(jié)點值的遞增序列，應(yīng)按下列哪種次序排列結(jié)點

A.先根B.中根C.后根D.層次31.散列函數(shù)的作用是：______。32.INITIATE()的功能是建立一個空表。請在______處填上正確的語句。

lklistinitiate_lklist()

/*建立一空表*/

{______;

______;

return(t);

}33.已知循環(huán)隊列的存儲空間大小為m，隊頭指針front指向隊頭元素，隊尾指針rear指向隊尾元素的下一個位置，則在隊列不滿的情況下，隊列的長度是______。34.在下面的排序方法中，不需要通過比較關(guān)鍵字就能進(jìn)行排序的是

A.箱排序B.快速排序C.插入排序D.希爾排序35.從具有n個結(jié)點的單鏈表中查找值等于x的結(jié)點時，在查找成功的情況下，平均需比較

個結(jié)點。A.nB.n/2C.(n-1)/2D.(n+1)/236.以下運算實現(xiàn)在循環(huán)隊上的入隊列，請在______處用適當(dāng)?shù)恼Z句予以填充。

intEnCycQueue(CycquetaeTp*sq,DataTypex)

{if((sq—＞rear+1)%maxsize==______)

{error("隊滿");return(0);)

else{______;

______;

return(1);

}

}37.______與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。38.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的

A.存儲結(jié)構(gòu)B.存儲實現(xiàn)C.邏輯結(jié)構(gòu)D.運算實現(xiàn)39.對于數(shù)組，通常具有的基本操作有______種，它們分別是______。40.假設(shè)一個循環(huán)隊列的容量為50，對其進(jìn)行人隊和出隊操作，則經(jīng)過一段時間之后，有：

(1)front=35，rear=12；

(2)front=12，rear=35。

其中front和rear分別是隊頭和隊尾指針。

求：循環(huán)隊列中元素的個數(shù)?41.算法分析的目的是

A.辨別數(shù)據(jù)結(jié)構(gòu)的合理性B.評價算法的效率C.研究算法中輸入與輸出的關(guān)系D.鑒別算法的可讀性42.已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，試從下列提供的答案中選擇合適的語句序列。(1)在P結(jié)點之前插入S結(jié)點的語句序列是______；(2)在表首插入S結(jié)點的語句序列是______。

a

P—＞nex=S

b

P—＞next=P—＞next—＞next

cP—＞next=S—＞next

dS—＞next=P—＞next

e

S—＞next=L

f

Q=P

gwhile(P—＞next!=Q＞P=P—＞next

hwhile(P—＞next!=NULL)P=P—＞next

i

P=L

j

L=S43.散列表的目的是

A.插入B.刪除C.快速查找D.排序44.在具有n個單元的循環(huán)隊列中，隊滿時共有______個元素。45.棧和隊列均可視為特殊的線性表，所不同的在于對這二種特殊線性表______和______運算的限定不一樣。46.在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置是由______指示。47.請根據(jù)下面所給出的鄰接矩陣畫出相應(yīng)的有向圖或者是無向圖(頂點vi表示)。

48.下面四種內(nèi)排序方法中，要求內(nèi)存容量最大的是

A.插入排序B.選擇排序C.快速排序D.歸并排序49.假設(shè)在圖G中任意的頂點設(shè)為vi，此頂點對應(yīng)的度為D(vi)，此圖的頂點數(shù)為n。則邊數(shù)e和度數(shù)之間的關(guān)系為______。50.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的后序就是T2中結(jié)點的

A.前序B.中序C.后序D.層次序第1卷參考答案一.歷年考點試題黑鉆版1.參考答案：a[i]

i++

a[j]

j++

mn

P(n-h+1)2.參考答案：B3.參考答案：一個數(shù)據(jù)元素可能有多個直接前趨和多個直接后繼4.參考答案：所謂有序文件是指文件的記錄按關(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*/5.參考答案：O(n)6.參考答案：15,02,21,24,26,57,43,66,80,48,737.參考答案：廣義表展開后所含括號的最大層數(shù)8.參考答案：

根據(jù)隊列的操作規(guī)則：進(jìn)隊時，將新元素插入到rear所指的位置，然后將rear加1，front不變，出隊時，刪除front所指的元素，然后將front加1，rear不變，則有：A，B，C進(jìn)隊列后，rear指針指向3，front不變，A出隊列時，刪除A，將front加1，所以front指向1，rear不變，B，C都出隊時，fron加2，rear不變，此時，rear和front相等。9.參考答案：參考答案一：

voidf34(LinkListha,LinkListhb)

{

//hb和hb分剮為存放A和B有序鏈表的頭指針

LinkListp,q,r;

p=ha;

q=hb—＞next;

while(p—＞next&&q){

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

p=p—＞next;

else{

if(p—＞next—＞data==q—＞data){

r=p—＞next;

p—＞next=r—＞next;

free(r);

}

//從A表刪除相同的元素結(jié)點

q=q—＞next;

}

}

}

參考答案二：

voidf34(LinkListha,LinkListhb)

{

//hb和hb分別為存放A和B有序鏈表的頭指針

LinkListp,q,r;

r=ha;p=ha—＞next;

q=hb—＞next;

while(p&&q){

if(p—＞data＜q—＞data){

r=p;p=p-＞next;

}else{

if(p—＞data==q—＞data){

r—＞next=p—＞next;

free(p);

p=r—＞next;

}

//從A表刪除相同的元素結(jié)點

q=q—＞next

}

}

}10.參考答案：B11.參考答案：n+112.參考答案：D13.參考答案：穩(wěn)定14.參考答案：hig=mid-1low—low+115.參考答案：C16.參考答案：根據(jù)二分查找的過程，我們可以得到如下的比較結(jié)果：

第一次比較：[5,9,12,18,23,31,37,46,59,66,71,78,85,]

↑

第二次比較：[5,9,12,18,23,31],37,46,59,66,71,78,85

↑

第三次比較：5,9,12[18,23,31],37,46,59,66,71,78,85

↑

第四次比較：5,9,12[18]23,31,37,46,59,66,71,78,85

↑

則從上面的比較過程我們可以看出：經(jīng)過四次比較之后，就可以查找到值為18的關(guān)鍵字。17.參考答案：邏輯[考點]數(shù)據(jù)的邏輯結(jié)構(gòu)的概念

[解析]數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。18.參考答案：同義詞19.參考答案：穩(wěn)定20.參考答案：邏輯記錄

物理記錄21.參考答案：D22.參考答案：選擇排序23.參考答案：C24.參考答案：v1、v4、v3、v5、v2[考點]圖的遍歷

[解析]深度優(yōu)先搜索(DFS)類似于樹的先根遍歷。深度優(yōu)先遍歷圖的方法是從圖中某頂點v出發(fā)：(1)訪問頂點v；(2)依次從v的未被訪問的鄰接點出發(fā)，對圖進(jìn)行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點都被訪問；(3)若此時圖中尚有頂點